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

https://about.gitlab.com/blog/2025/06/05/how-we-decreased-gitlab-repo-backup-times-from-48-hours-to-41-minutes/

by nayak • 1 year ago

593 243 1 year ago

about.gitlab.com

judofyr• 1 year ago

Quadratic complexity sits in an awkward sweet spot: Fast enough for medium-sized n to pass first QA, but doomed to fail eventually as n grows.

vjerancrnjak• 1 year ago

This particular change was not accidental. It was announced as quadratic.

hinkley19• 1 year ago

We have a habit of taking our eye off of old problems by trying to juggle several new ones. By the time someone notices that we have a problem, the dogleg in the graphs where the n² solution stopped fitting into the CPU cache has been obvious for months but nobody was looking, and we dance around that fact that we had time to take a reasonable approach to fix the problem if we had noticed it when it became measurable, by adding anxiety to the cleanup work.

And then someone learns from this experience, gets the bright idea to set up an alert for such things, but the alert doesn’t factor in things like customer base growth or feature creep slowly pushing up the expected runtime. Eventually organic load gets close to the alarm and then the fucking thing goes off on a three day weekend (why is it always a long weekend or just before one?) and then we wage war on alarm overreach and the whole cycle repeats itself.

We like to think of ourselves as blazing trails in the wilderness but most of the time we are doing laps around the parking lot.

jeffbee• 1 year ago

Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.

landr0id2• 1 year ago

https://github.com/GitoxideLabs/gitoxide

umanwizard3• 1 year ago

Ignoring your inaccurate flamebait and answering the underlying question: there are several reimplementations of git, including "got" (Game of Trees) from the OpenBSD developers, jgit (reimplementation in Java), the Haskell git package, the gitoxide rust crate (and I assume several more half-finished Rust hobby projects), and probably others; that's just what I found with a cursory google.

Vilian• 1 year ago

Git, but as it was intended to be used

kgeist• 1 year ago

We use go-git in one of our Go projects that relies on Git for version control of its data.

gonzus• 1 year ago

https://github.com/libgit2/libgit2

fHr2• 1 year ago

lmao

hiddew• 1 year ago

"fixed it with an algorithmic change, reducing backup times exponentially"

If the backup times were O(n^2), are they now O(n^2 / 2^n)? I would guess not.

umanwizard3• 1 year ago

This is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".

cvoss• 1 year ago

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.

morepedantic11• 1 year ago

Ultimately, we traced the issue to a 15-year-old Git function with O(N²) complexity and fixed it with an algorithmic change, reducing backup times exponentially.

No, not in the exact same sentence as a big-O. That's either author error, or an intentional troll. Either way it's egg on their faces.

marcellus23• 1 year ago

Meaningless and non-constructive pedantry.

chrisweekly• 1 year ago

I'm not the OP you're responding to, but to be fair, in a sentence about big-O perf characteristics, which includes the word "algorithms", using "exponentially" in a colloquial non-technical sense is an absolutely terrible word choice.

msgodel• 1 year ago

I disagree. Misuse of the word "exponential" is a major pet peeve of mine. It's a particular case of the much more common "use mathematically precise phrasing to sound careful/precise" that you often find in less than honest writing.

Here they are actually using it to refer to growth functions (which is rare for this error) and being honest (which is also rare IMO) but it's still wrong. They should have written about quadratic or quadratic vs linear.

Regardless sloppy language leads to sloppy thought.

morepedantic11• 1 year ago

pedantry

I wasted 2 minutes of my life looking for the exponential reduction. So did many others.

Now I'm wasting more of my life shit posting about it, but at least that's a conscious choice.

csnweb2• 1 year ago

If you replace an n^2 algorithm with a log(n) lookup you get an exponential speed up. Although a hashmap lookup is usually O(1), which is even faster.

ryao2• 1 year ago

That is not true unless n^C / e^n = log(n) where C is some constant, which it is not. The difference between log(n) and some polynomial is logarithmic, not exponential.

ndriscoll4• 1 year ago

They're still using the map in a loop, so it'd be nlogn for a tree-based map or n for a hash map.

sn93• 1 year ago

The algorithm complexity went down in the function they patched (6x improvement in their benchmark), but in the context of how they benefited with how they were using the algorithm the impact was much larger (improved to taking 1% of the time), which is plausibly exponential (and figuring out the actual complexity is neither relevant nor an economic use of time).

ndriscoll4• 1 year ago

figuring out the actual complexity is neither relevant nor an economic use of time

The fix was replacing a nested loop with a map. Figuring out that this goes from O(n^2) to O(n) (modulo details like bucket count) is immediate if you know what the words mean and understand enough to identify the problem and make the fix in the first place.

wasabi9910112• 1 year ago

I interpreted that as n->log(n) since log and exp are inverses.

Also because I've often heard tha the quantum Fourier transform is an exponential speedup over the discrete Fourier transform, and there the scaling goes n^2->nlogn.

morepedantic11• 1 year ago

I was also looking for the exponential algorithm.

abhashanand15012• 1 year ago

In fact O(n^2) is exponentially more than O(log n).

gre• 1 year ago

looks like the commit is here: https://github.com/git/git/commit/a52d459e72b890c192485002ec...

throawayonthe• 1 year ago

* Warning: this function uses an O(N^2) algorithm.

mortar• 1 year ago

Thanks, this helped me find the submission and related discussion thread - https://lore.kernel.org/git/20250401-488-generating-bundles-...

SomaticPirate• 1 year ago

How was the flame graph created? (Not very familiar with C and the performance tools around it)

plorkyeran• 1 year ago

https://github.com/brendangregg/FlameGraph

You record performance data with `perf`, then use the scripts there to turn it into a SVG.

immortaljoe• 1 year ago

OP here. In this particular case, I used https://github.com/flamegraph-rs/flamegraph

IshKebab5• 1 year ago

I strongly recommend not using this. Instead use pprof - it has a MUCH better interactive flamegraph, plus other nice performance visualisations (e.g. a call graph):

https://github.com/google/pprof

    go install github.com/google/pprof@latest
    pprof -http=: prof.out

I normally collect the profiles with gperftools (https://github.com/gperftools/gperftools) and then just

    LD_PRELOAD=/usr/lib/libtcmalloc_and_profiler.so CPUPROFILE=prof.out <your command>

I've been meaning to try Samply though. Not sure if it works with pprof.

landr0id2• 1 year ago

You can also use https://github.com/mstange/samply to make recording and viewing in the Firefox profiler easier.

It will spin up a localhost server after the trace ends, the profiler uses the localhost server and nothing is shared with Firefox servers unless you explicitly choose to upload the data and create a permalink.

edflsafoiewq• 1 year ago

So they replaced a nested for loop for checking for duplicates with a set data structure. Surprised such a common thing was in git.

tomxor3• 1 year ago

One of the many reasons I moved to self hosting. I use ZFS to backup every 15 minutes, ... could do it even more frequently but that seems a little pointless.

Also moved away from Gitlab because it's so damn slow.

glookler• 1 year ago

ZFS is great, getting off gitlab would also be great, what did you switch to?

tomxor3• 1 year ago

Gitea, i can't recommend it enough. Lightening fast compared to the proprietary offerings, clean simple UI like an older Github, and super simple to self host.

haroldp• 1 year ago

This was my thought too, but I figured I just didn't understand the problem. Why use git commands to backup when a file system copy seems like it would do? zfs snapshot takes less than a second on any size repo. zfs send transfers just the changes since the last backup, as fast as your network, more or less.

tomxor3• 1 year ago

Yup, once you've used snapshots for backups once, doing any kind of filesystem level backup just seems absurd. I now use it as the basis for every piece of infrastructure I add that holds valuable data. The only place it doesn't really fit is distributed databases.

mdaniel4• 1 year ago

It for sure has an excruciatingly slow UI, but I haven't yet been able to stomach the Ruby magick enough to dig in and find out if it's all of GitLab that's slow, and thus their culture of who-cares just propagates to the UI, or it's literally just the web frontend that's molasses yet because so many folks interact with it over the web that's where the conclusion ends up

I know their backend git proxy is written in golang, their runner agent is written in golang, it spawns CI jobs using containerd, written in golang, and they use postgresql and a redis-esque KV -- although for that part I do believe they're still using Sidekick (ruby) for doing job dispatch, so that one could very easily lolol back into not actioning tasks efficiently

GitHub Actions sure does enjoy just sitting there twiddling its thumbs when I push "run job," and is also both Ruby and their own crazypants ajax-y web framework, so I don't think it's exactly the shining star of performance itself

treesknees• 1 year ago

Duplicate of https://news.ycombinator.com/item?id=44197061

mdaniel4• 1 year ago

Since that one only has one comment, I'm pretty sure that means the HN front-page is luck of the draw and I wouldn't have bothered even commenting about the other one

LgWoodenBadger• 1 year ago

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.

parthdesai• 1 year ago

My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.

anttihaapala• 1 year ago

This is not a complicated algorithm. A hash map (dictionary) or a hash set is how you would always do deduplication in Python, because it is easiest to write / least keystrokes anyway. That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.

paulddraper3• 1 year ago

This isn't knapsack. This is a dict lookup.

LtWorf• 1 year ago

I wrote a funny algorithm to group together words that end the same way to write them once in my binary wordlist file, since there is an array that points to the start character and a \0 to end the word. My initial solution was O(n²) but it was too slow on a real wordlist so I had to come up with something better. In the end I just sort the list with quicksort, but revert the order of the words and then the groupable ones end up nearby each other.

koala_man• 1 year ago

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.

david422• 1 year ago

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

SAI_Peregrinus• 1 year ago

I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent on an OBDII connector can be O(n^(2)) since n will always be between 1 and 4). If you wouldn't have to physically replace hardware for `n` to increase, you really need to avoid n^2 operations. And even then consider them carefully, perhaps explicitly failing if `n` gets too big to allow for noticing rework is needed before new hardware hits the field.

echelon• 1 year ago

perhaps explicitly failing if `n` gets too big

That's the problem. A lot of these quadratic time algorithms don't set limits.

Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.

EdwardCoffin3• 1 year ago

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

paulddraper3• 1 year ago

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

hinkley19• 1 year ago

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.

vlovich123• 1 year ago

I have an n^3 operation that's currently a huge bottleneck at only 10k elements. Not sure how to fix it.

IshKebab5• 1 year ago

I once looked into tree diffing algorithms (the literature is all about diffing XML even though it's really trees). The obvious dumb algorithm (which seems to be what everyone uses) is n^4.

esprehn• 1 year ago

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. On the other hand for small sibling counts it turned out the cache overhead was noticably worse than just doing an n^2. (See the end of the linked comment).

This turns out to be true in a lot of surprising places, both where linear search beats constant time maps, and where n^2 is better than fancy algorithms to compensate.

Memory latency and instruction timing is the gotcha of many fun algorithms in the real world.

throwaway20372• 1 year ago

    > where linear search beats constant time maps

Can you give an example? You said lots of good things in your post, but I struggling to believe this one. Also, it would help to see some wall clock times or real world impact.

kevincox• 1 year ago

This is true. But unless you are sure that current and future inputs will always be small I find it is better to start with the algorithm that scales better. Then you can add a special case for small sizes if it turns up in a hot path.

This is because performance is typically less important for the fast/small case and it is generally acceptable for processing twice as much to be twice (or slightly more than twice) as slow, but users are far more likely to hit and really burned by n^2 algorithms in things you thought would almost always be small and you never tested large enough sizes in testing to notice.

I wrote more on this topic here https://kevincox.ca/2023/05/09/less-than-quadratic/

hinkley19• 1 year ago

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.

solardev• 1 year ago

For those of us without a formal comp sci background, is there a way for the IDE to detect and warn about these automatically? Or any other easy telltale signs to look for?

As a self taught dev, when I encounter nested loops, I have to mentally go through them and try to see if they iterate through each item more than once. But that's not a very foolproof method.

chacha102• 1 year ago

Too much domain knowledge for an IDE to catch. I'm self taught as well, and it comes down to spending more time thinking about the code than writing the code.

It's a fairly simple thought experiment to ask yourself what if there was 10x items in this array? 100x? That is essentially what the O(n) notation is trying to quantify. You just don't need to do it that formally.

Arcuru• 1 year ago

48 hours is a crazy amount of time to spend just to compress a git folder, it's only a couple GB. 41 minutes still seems like quite a long time.

Why aren't they just snapshotting and archiving the full git repo? Does `git bundle` add something over frequent ZFS backups?

bombela3• 1 year ago

Be aware that even with these recommendations, syncing in this way has some risk since it bypasses Git’s normal integrity checking for repositories, so having backups is advised. You may also wish to do a git fsck to verify the integrity of your data on the destination system after syncing.

https://git-scm.com/docs/gitfaq#_transfers

It doesn't tell you how to make a backup safely though.

On a personal scale, Syncthing and Btrfs snapshots work plenty good enough. It's as fast as the storage/network too.

nightfly2• 1 year ago

Syncthing is the only way I've ever corrupted a git repo before

ndriscoll4• 1 year ago

If filesystem snapshots weren't safe, wouldn't that also mean git is prone to corrupting your repo in the event of a power loss or crash? That seems like a bad bug.

unsnap_biceps• 1 year ago

zfs snapshots are difficult to offsite in non-zfs replicas, say like an S3 bucket.

That said, there's another less known feature that bundles help out with when used with `git clone --bundle-uri` The client can specify a location to a bundle, or the server can send the client the bundle location in the clone results and the client can fetch the bundle, unpack it, and then update the delta via the git server, so it's a lot lighter weight on the server for cloning large repos, and a ton faster for the client for initial clones.

nightfly2• 1 year ago

ZFS can send to file or whatever you want to pipe to, you can have incremental sends, and if you convert to bookmarks on the sender you don't have to keep the historical data after you send it

benlivengood• 1 year ago

I think if you want consistent snapshot backups on non-zfs destinations the safest thing is to clone the snapshot and rsync from the clone. Not a single-step operation but preserves the atomicity of the snapshot.

EDIT: you could also rsync from a .zfs snapshot directory if you have them enabled.

AtlasBarfed• 1 year ago

... so they added caching to things that should have been cached?

... is this really the way people "back up" git repos? I mean, it is git, so isn't there some way to mirror changes to the repo in another repo and just use ZFS / snapshots / backup software / etc to do that? It's a distributed version control system. Just make sure the version control information is ... distributed?

broken_broken_• 1 year ago

Reading the article I thought exactly the same! I‘d be curious to know how much time the same would take with zfs.

gregorvand• 1 year ago

15 years also seems like a long time

DamonHD4• 1 year ago

Here comes an unpopular nitpick: "... we traced the issue to a 15-year-old Git function with O(N²) complexity and fixed it with an algorithmic change, reducing backup times exponentially."

Uh no you didn't. Not possible. At most a polynomial reduction is possible else complexity theory needs a re-write.

(OK, yes, k could be doing some heavy lifting here, but I doubt it.)

If you are going to quote a maths formula then please don't use "exponetially" to mean "lots".

I stopped reading there: I don't want to have to read each word and wonder if they actually meant it, or it's just bad hype.

nayak4• 1 year ago

OP here. Feedback is always welcome, I did mean exponentially in the colloquial sense. I do see how it is confusing here, will change it.

DamonHD4• 1 year ago

Thank you.

(I don't think that anyone should use "exponentially" that way: it is an art term with a specific and particular meaning, so find another word if you mean something else! Like misusing specific legal or sporting terms...)

serial_dev2• 1 year ago

You can’t use exponentially in the colloquial sense in a post about software performance.

If my barista says that his new coffee is exponentially better, it’s ok to use it colloquially.

If my git hosting provider writes about an impactful performance improvement, it’s not.

DamonHD4• 1 year ago

I'm disappointed that the page has not been fixed...

bombela3• 1 year ago

I can forgive exponential as a figure of speech. You missed when they describe using a map for the side effect of [key] dedupliction.

Instead of saying "set". The code itself uses the type "strset".

Lammy• 1 year ago

What this means for GitLab customers — [a bunch of stuff about how customers can now back up more frequently and more robustly]

Realtalk: They should rewrite this post's headline to be in a positive tense instead of leading with a negative word. I'm glad I read the post, because it is a cool and good fix, but I saw “Decreasing […] repo backup” and my first thought was that it was an announcement of some service downgrade like some sort of cost-cutting measure.

serial_dev2• 1 year ago

I don’t think it’s unreasonable to expect interested people to read five words from the title. I know people don’t always do that, but complaining about it as if they did something wrong is ridiculous.

robertlagrant• 1 year ago

No one was complaining.

divbzero2• 1 year ago

The performance improvement that GitLab contributed to Git is slated to be released with v2.50.0:

https://github.com/git/git/commit/bb74c0abbc31da35be52999569...

Nemo_bis2• 1 year ago

Nice that GitLab is active upstream! Do I see correctly that the most active contributors to git are currently GitLab employees?

dfc2• 1 year ago

I dont know how you came to that conclusion. Just looking at the top 4 contributors over the last 2 years[1] it looks like one works for google(gitster), two work at Github and one works at GitLab(pks-t).

[1] https://github.com/git/git/graphs/contributors?from=6%2F3%2F...

pjmlp2• 1 year ago

A very good example that writing code in C doesn't help for performance, when the algorithms or data structures aren't properly taken into consideration.

IshKebab5• 1 year ago

I would say C makes this sort of thing far more likely because it's usually a ton of effort to obtain suitable containers. In C++ or Rust they have plenty of things like `unordered_set`/`HashSet` built in, so people are much more likely to use it and not go "eh, I'll use a for loop".

In this case Git already had a string set, but it's still not standard so there's a good chance the original author just didn't know about it.

pjmlp2• 1 year ago

Yeah, not something that WG14 will ever care about.

masklinn3• 1 year ago

In this case Git already had a string set, but it's still not standard so there's a good chance the original author just didn't know about it.

The original commit was made in January 2009 (https://github.com/git/git/commit/b2a6d1c6868b6d5e7d2b4fa912...), strmap was added in November 2020 (https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99..., strset was added a few days later: https://github.com/git/git/commit/1201eb628ac753af5751258466...). It was first proposed in 2018 (https://lore.kernel.org/git/20180906191203.GA26184@sigill.in... the proposal specifically mentions it fixing possibly quadratic sites).

As noted in the comment, git did have a sorted string list with bisection search, and that's from 2008 (and it actually dates back to 2006 as the "path list" API, before it was renamed following the realisation that it was a generalised string list). Though as the hashmap proposal notes, it's a bit tricky because there's a single type with functions for sorted and functions for unsorted operations, you need to know whether your list is sorted or not independent of its type.

morepedantic11• 1 year ago

I've seen this exact problem in C code many times in my life, especially in kernel space where data structures and memory allocations are fun.

Ironically, this is much _faster_ for small sets. Sometimes the error is intentional, because the programmer believes that all inputs will be small. IME, those programmers were wrong, but that's the inverse of survival bias.

account424• 1 year ago

C does help with the C that is often conveniently omitted in the big O notation. That matters just as much as the algorithmic complexity - both need to be reasonable or the software will be slow. No one ever claimed C affects algorithmic complexity.

ashishb• 1 year ago

O(n^2) is fast enough to end up I'm production and slow enough to cause problems at scale.

The worst troublesome cases of inefficient production are almost always O(n^2).

hinkley19• 1 year ago

Had a modular monorepo back when UML was still a thing people did. People were having trouble opening a TogetherJ project - it was taking 30 minutes. I dug into it, and I don’t recall how I timed it but I kept adding more submodules and the runtime went up ridiculously fast. I stopped at a project that took 18 hours to load. Started it before going home one day and timed it the next morning.

When I plotted the runtime, I got n^5 for the fitting curve. That’s the largest polynomial I’ve encountered in the wild. Second place has always been cubic.

Their response was that it had something to do with processing config files per module, and a suggestion to rearrange them as a workaround. They fixed the problem in the next patch and the load time went from 18 hours to a couple minutes.

divbzero2• 1 year ago

There seems to be a lesson here about the balance between premature vs. anticipatory optimization. We’re generally warned against premature optimization but perhaps, as a rule of thumb, we should look for optimizations in frequently-called functions that are obvious and not onerous to implement.

Quekid5• 1 year ago

If a set-of-strings was trivially available in the source language (at time of implementation) the original programmer would probably have done this (relatively) trivial optimization... This is a symptom of anemic languages like C.

prymitive• 1 year ago

Well done, next maybe make the web ui usable because right now there’s absolutely no distinction between the UI itself and the user content, which IMHO combined with action buttons in the middle of the page makes for a really poor ux.

SoftTalker• 1 year ago

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.

kokada• 1 year ago

Yes. I read the whole article thinking that this must have been generated by LLM, because at least the style remembers it.

ruuda• 1 year ago

That was also my thought.

Scaevolus• 1 year ago

Em dashes and bullet points!

jaygreco• 1 year ago

Glad I wasn’t the only one who thought this. The post is also missing one obvious thing that I expect in any technical post: code snippets. Let me see the code.

ChatGPT has ruined bullet points for the rest of us…

No offense but writing this blog post couldn’t take more than a few minutes, why spoil it with LLM? Shoot, use one to check grammar and recommend edits even.

bearjaws• 1 year ago

Don't take my bullet points away from me

djdeutschebahn• 1 year ago

Exactly thought the same. Reading experience of the post would have been definitely improved, with less text.

1oooqooq• 1 year ago

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

6LLvveMx2koXfwn2• 1 year ago

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

davidron• 1 year ago

For those that haven't read the article yet, scroll down to the flame graph and start reading unit it starts talking about back porting the fix. Then stop.

wgjordan• 1 year ago

"How we decreased reading 'How we decreased GitLab repo backup times from 48 hours to 41 minutes' times from 4.8 minutes to 41 seconds"

hliyan• 1 year ago

Interesting that multiple people are noticing this same thing. For me, this could have been:

"We found that a large portion of the 48 hours taken to backup our rails respository was due to a function in `git bundle create` that checks for duplicate references entered as command line arguments. The check contained a nested for loop ( O(N2) ), which we replaced with a map data structure in an upstream fix to Git. The patch was accepted, but we also backported fix without waiting for the next Git version. With this change, backup time dropped to 41 minutes."

m104• 1 year ago

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.

bob10292• 1 year ago

I'm confused why you wouldn't simply snapshot the block-level device if the protocol of the information on top is going to cause this much headache. Quiescing git operations for block level activity is probably not trivial, but it sounds like an easier problem to solve to me.

This is the approach I've taken with SQLite in production environments. Turn on WAL and the problem gets even easier to solve. Customer configures the VM for snapshots every X minutes. Git presumably doesn't have something approximating a WAL, so I understand the hesitation with this path. But, I still think the overall strategy is much more viable and robust to weird edges within git.

nonameiguess2• 1 year ago

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.

bob10292• 1 year ago

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.

amtamt• 1 year ago

This is the approach I've taken with SQLite in production environments. Turn on WAL and the problem gets even easier to solve.

A few months back a better solution was provided by SQLite: sqlite3_rsync

https://www.sqlite.org/rsync.html

lbotos• 1 year ago

Git presumably doesn't have something approximating a WAL, so I understand the hesitation with this path.

Bingo. One of the worst problems is helping a client piece back together a corrupted repo when they are using snapshots. Check my profile to see how I know. :)

It's usually an OMG down scenario, and then you are adding in the "oh no, now the restore is corrupted."

It's fixable but it's definitely annoying.

einpoklum• 1 year ago

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.

sneak3• 1 year ago

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

kristianp• 1 year ago

It would have been nice if the post included some details, such as before and after code.

niffydroid• 1 year ago

Why use this method over just having a script do a clone or pull elsewhere? Got is about distribution right?

iamcreasy• 1 year ago

Cool! Please post another flame graph after applying the patch.

tcdent• 1 year ago

TLDR if you only add objects to an array that are already not contained in said array you won't have to iterate back through it to remove the duplicates you created.

wild that this a pattern like this would be part of git-core, but I guess we all overlook stuff on a regular basis

katella• 1 year ago

I don't know much about git backups, but why would there be race conditions if you just create the backup off the local repo instead of remote?

KETpXDDzR• 1 year ago

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

mdaniel4• 1 year ago

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

DeepYogurt• 1 year ago

I miss a good tech blog post. Cheers for this

ianks• 1 year ago

Reminds me of the timeless advice I got for acing leet code interviews: “remember to use a hash map.” Tends to work out pretty well.

SkiFire13• 1 year ago

Ultimately, we traced the issue to a 15-year-old Git function with O(N²) complexity and fixed it with an algorithmic change, reducing backup times exponentially.

I have yet to finish the article, but this means they improved the complexity to something like O(logN), right? I hate when people confuse quadratic improvement for exponential ones.

globular-toast3• 1 year ago

Really annoying to see someone use exponential wrong when they're talking about performance of algorithms. We're supposed to know what this means! They went from quadratic to linear.

jas39• 1 year ago

What a poor write-up, neither defining the problem nor the solution with any clearity. Did anyone come away with any information that can be used for anything?

fHr2• 1 year ago

absolute chads, nice!

hinkley19• 1 year ago

This feels like some of the problems I’ve ended up tackling. The people too close to the problem don’t see it so someone has to reach across the aisle and make something happen in code they normally wouldn’t touch.

Even with the quadratic complexity I suspect this problem has been brewing for a while. This commit has been biding its time for 16 years waiting to ruin someone’s day (let’s not confuse the utility of Make it Work early in a project with justifying retaining that code in perpetuity. Make it Right, Make it Fast.) Backups have probably been going over six hours for years and steadily climbing.

“We” feels a lot like one or two people jumping on a grenade.

gbacon• 1 year ago

Algorithmic improvements beat micro-optimizations.

James_K• 1 year ago

Perhaps nested for loops should be some kind of compiler warning.

abhashanand15012• 1 year ago

Lot of comments complaining that going from O(n^2) to O(log n) is not an exponential improvement, but it is indeed an exponential improvement. In fact O(n) is exponentially more than O(log n).

SergeAx• 1 year ago

I can't shake off the feeling that the second half of the article is generated by a neural network.

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

Related Stories