Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

about.gitlab.com

Post reply on HN
Print view View original

221–230 of 273 posts

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

#221

Post by hinkley »

crote wrote: post #191
hinkley wrote: post #164

Earlier quoted context omitted.

Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can on…

That only matters when the constants are nontrivial and N has a potential to get big. Not every app is a B2C product intending to grow to billions of users. If the costs start out as near-zero and are going to grow to still be negligible at 100% market share, who cares that it's _technically_ suboptimal? Sure, you could spend expensive developer-hours trying to find a better way of doing it, but YAGNI.

I just exited a B2B that discovered they invested in luxury features and the market tightened their belts by going with cheaper and simpler competitors. Their n wasn’t really that high but they sure tried their damnedest to make it cubic complexity. “Power” and “flexibility” outnumbered, “straightforward” and even “robust” but at least three to one in conversations. A lot of my favorite people saw there was no winning that conversation and noped out long before I did.

The devs voted with their feet and the customers with their wallets.

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

#222

Post by hinkley »

saagarjha wrote: post #200
delusional wrote: post #169

Earlier quoted context omitted.

All of modern Neural Network AI is based on GEMM which are O(n^2) algorithms. There are sub-cubic alternatives, but it's my understanding that the cache behavior of those variants mean they aren't practically faster when memory bound. n is only rarely related to "customers". As long as n doesn't grow, the asymptotic complexity doesn't actually matter.

The GEMM is O(n^3) actually. Transformers are quadratic in the size of their context window.

I read that as a typo given the next sentence.

I’m on the fence about cubic time. I was mostly thinking of exponential and factorial problems. I think some very clever people can make cubic work despite my warnings. But most of us shouldn’t. General advice is to be ignored by masters when appropriate. That’s also the story arc of about half of kung fu movies.

Did chess solvers really progress much before there was a cubic approximation?

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

#223

Post by hinkley »

Tainnor wrote: post #197
hinkley wrote: post #164

Earlier quoted context omitted.

Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can on…

Gaussian elimination (for square matrices) is O(n^3) arithmetic operations and it's one of the most important algorithms in any scientific domain.

I’ll allow that perhaps I should have said “cubic” instead of “quadratic” - there are much worse orders in the menagerie than n^3. But it’s a constraint we bang into over and over again. We use these systems because they’re cheaper than humans, yes? People are still trying to shave off hundredths of the exponent in matrix multiplication for instance. It makes the front page of HN every time someone makes a “breakthrough”.

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

#224

Post by hinkley »

david422 wrote: post #104
koala_man wrote: post #45

Earlier quoted context omitted.

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.

First big project I worked on a couple of us sped up the db initialization scripts so we could use a less trivial set of test data to stop this sort of shenanigans.

Things like inserting the test data first and turning on constraints and possibly indexes afterward.

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

#225

Post by hinkley »

esprehn wrote: post #147
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.

Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index.…

A lot of computations are really higher complexity order functions with stair steps at certain intervals based on hardware trying to pretend they are constant time. All operations cost the same amount until n doubles again and then it’s slower. If you zoom out toward infinity, the stair steps smooth out into a logarithmic curve. It becomes logarithmic in the former case and square root in the latter. Even dividing two numbers or doing a memory address lookup stops being C, which is part of why prime factoring worked for RSA for so long.

If anyone had made clockless logic work you would see that adding 1 + 1 is in fact faster than adding 2^63 + 1.

If you put enough data into a hash table the key length has to increase logarithmically to the table size in order to have distinct keys per record. Even Knuth points out that hash tables are really nlogn - something I’m pretty sure my CS professors left out. In multiple classes. Man, did I get tired of hash tables, but I see now why they harped on them. Case on point, this article.

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

#226

Post by rjmunro »

6LLvveMx2koXfwn wrote: post #157
1oooqooq wrote: post #117

Earlier quoted context omitted.

it could have been longer. I still don't know why they were doing backup bundles with two refs :)

They weren't, if you look at the fix [1] the dedupe loop was run in all cases, not just those with known dupes, so the performance hit was any bundle with lots of refs. 1. https://github.com/git/git/commit/bb74c0abbc31da35be52999569...

But why couldn't they just dedupe the refs from the command line before starting the actual bundling - surely there are never more than a couple of hundred of those (one per branch)?

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

#227

Post by mdaniel »

KETpXDDzR wrote: post #149

With git it should be straightforward to implement an incremental, dedup backup solution since all objects are stored with their hashs in filename.

Run `man git-repack` or its `man git-gc` friend and recall that most filesystems hate dealing with a bazillion small files

I think there have been several attempts to use S3-ish blobstores as git backends but of the two major git hosters, only one of them is MIT licensed and they don't attempt that stunt, so safe to assume it's not a viable approach

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

#228

Post by m104 »

SoftTalker wrote: post #48

Cool discovery but the article could have been about 1/10 as long and still communicated effectively. At least they didn't post it as a video, so it was easy to skim to the important details.

It's the "impact" style of technical write-ups: sell the problem and the scale, then present the solution, which is thus presented and understood through the lens of business and customer success.

Generously, this writing style is supposed to show the business value of teams and individuals, for promotions or other recognition. But yeah, it can be frustrating to read this style.

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

#229

Post by brucedawson »

EdwardCoffin wrote: post #87
paulddraper wrote: post #85

Earlier quoted context omitted.

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

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...

Should it be my second law?

https://bsky.app/profile/randomascii.bsky.social/post/3lr24s...

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

#230

Post by patrick451 »

hinkley wrote: post #164
dieortin wrote: post #119

Earlier quoted context omitted.

They’re too ridiculous… unless a more optimal solution does not exist

Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can on…

There are two many obvious exceptions to even start taking this seriously. If we all followed this advice, we would never even multiply matrices.
Post reply on HN