How we decreased GitLab repo backup times from 48 hours to 41 minutes • Hacker News Board

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#101

Post by hinkley » Fri, Jun 06, 2025, 8:58 PM UTC

EdwardCoffin wrote: post #67

LgWoodenBadger wrote: post #18

IME, it has always turned out to be the correct decision to eliminate any n^2 operation in anything I’ve written. I don’t write exotic algorithms, but it’s always astounding how small n needs to be to become observably problematic.

Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

I made the “mistake” in an interview of equating two super-quadratic solutions in an interview. What I meant was what Dawson meant. It doesn’t matter because they’re both too ridiculous to even discuss.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#102

Post by hinkley » Fri, Jun 06, 2025, 8:59 PM UTC

paulddraper wrote: post #85

EdwardCoffin wrote: post #67

Earlier quoted context omitted.

Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

The second law is that O(n * log n) is for practical intents and purposes O(n).

But sometimes a big enough C can flip which solution helps you hit your margins.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#103

Post by hinkley » Fri, Jun 06, 2025, 9:01 PM UTC

to11mtm wrote: post #100

EdwardCoffin wrote: post #87

Earlier quoted context omitted.

To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up. Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Js…

Not often but occasionally I will chose the nlogn algorithm which obviously has no bugs over the O(n) algorithm with no obvious bugs.

Less brittleness is worth paying a few percent. Especially if it unmuddies the waters enough for someone to spot other accidental (time) complexity.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#104

Post by david422 » Fri, Jun 06, 2025, 9:03 PM UTC

koala_man wrote: post #45

LgWoodenBadger wrote: post #18

IME, it has always turned out to be the correct decision to eliminate any n^2 operation in anything I’ve written. I don’t write exotic algorithms, but it’s always astounding how small n needs to be to become observably problematic.

Good call. O(N^2) is the worst time complexity because it's fast enough to be instantaneous in all your testing, but slow enough to explode in prod. I've seen it several times before, and it's exactly what happened here.

We just had this exact problem. Tests ran great, production slowed to a crawl.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#105

Post by Dylan16807 » Fri, Jun 06, 2025, 9:04 PM UTC

rubit_xxx22___ wrote: post #98

nightpool wrote: post #91

Earlier quoted context omitted.

Why are you making a new account for each comment? You seem to be deliberately avoiding HN's moderation system

[flagged]

> I don’t want something gathering all my thoughts historically together and tying it to something else; nothing good comes from that; I’m not writing a serial novel.

Yeah but you should want your thoughts on a single post to tie together.

> Many years ago I had a user with thousands of karma points. I used to get really annoyed with other users downvoting my valid and thoughtful comments because it affected my karma. Despite attempts to rally the community around getting rid of downvoting, that never happened.

Sorry you had that reaction. While I get annoyed by downvotes sometimes, I've never cared about losing some points from the mostly useless pile.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#106

Post by remram » Fri, Jun 06, 2025, 9:06 PM UTC

blharr wrote: post #68

cvoss wrote: post #47

Earlier quoted context omitted.

You shouldn't use a word that can carry a precise mathematical meaning in a sentence that literally uses mathematical notation in order to speak precisely and then expect readers not to interpret the word in the precise mathematical way.

I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch

"a lot"

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#107

Post by to11mtm » Fri, Jun 06, 2025, 9:06 PM UTC

bob1029 wrote: post #66

nonameiguess wrote: post #60

Earlier quoted context omitted.

Gitlab isn't just a managed service. They release the software for self-hosted instances as well. There is no guarantee or requirement that users all run Gitlab on the same filesystem or even a filesystem that supports block level snapshots at all. Presumably, they want a universal backup system that works for all Gitlabs.

I've never heard of a .git folder that spanned multiple filesystems. It sounds like we are now conflating the git workspace with everything else in the product. There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.

I think GP's point is that the filesystems used by someone self-hosting gitlab may not be the same as what gitlab themselves are using.

File systems can be weird. Sometimes the OS can be weird and fsync type calls may not do what you expect. At least at one point MacOS fsync didn't behave the same way as Linux (i.e. Linux should ensure the write is truly done and not just in cache so long as the drive isn't lying). [0]

> There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.

Gitlab has a community edition. Not handling data well would be bad for their public image.

[0] - https://news.ycombinator.com/item?id=30372218

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#108

Post by einpoklum » Fri, Jun 06, 2025, 9:10 PM UTC

I had a somewhat similar experience when writing a "remove duplicates" extension for Thunderbird:

https://addons.thunderbird.net/en-US/thunderbird/addon/remov...

I used a hash to begin with, using a simplistic digest function to the message headers I was comparing, getting me a 4-byte hash key.

That worked, but was kind of slow.

Finally, the idea came to me to not apply _any_ digesting, and use the combined concatenated headers of the messages as hash keys. About 2k bytes per hash key!

The result: About 20x perf improvement if memory serves.

How is that possible? The reason is that the code all runs in a Javascript machine; and applying the digest was not a built-in function, it was looping over the headers and doing the arithmetic. Thousands upon thousands of JS abstract machine steps. The use of the large hash key may be inefficient, but - it's just one JS object / dictionary operation, and one of the most heavily-optimized in any implementation.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#109

Post by sneak » Fri, Jun 06, 2025, 9:15 PM UTC

…and they say leetcode-style problems are out of date.

While perhaps implementing low level sorts is silly, knowing which data structures to use and when, and what underlying big-o performance they have, is critical, as demonstrated here.

Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes

#110

Post by nonameiguess » Fri, Jun 06, 2025, 9:17 PM UTC

bob1029 wrote: post #66

nonameiguess wrote: post #60

Earlier quoted context omitted.

Gitlab isn't just a managed service. They release the software for self-hosted instances as well. There is no guarantee or requirement that users all run Gitlab on the same filesystem or even a filesystem that supports block level snapshots at all. Presumably, they want a universal backup system that works for all Gitlabs.

I've never heard of a .git folder that spanned multiple filesystems. It sounds like we are now conflating the git workspace with everything else in the product. There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.

I can't reply to the other reply for some reason, but what they said is indeed what I meant. gitlab.com might be running their Gitaly servers on btrfs or zfs or lvm volumes or whatever, but other customers may be using ext2. Gitlab the company could require customers to only run Gitaly on a specific filesystem, but up to now, they never have, it would be pretty shitty to suddenly change their minds after a decade plus of establishing one expectation, and whoever the developer is who submitted the patch to upstream Git and got a technical blog post out of it has absolutely no power to dictate contract terms to enterprise customers personally and instead did what is actually in their power to do.