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

191–200 of 273 posts

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

#191

Post by crote »

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…

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.

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

#192

Post by tux3 »

crabmusket wrote: post #175
Retric wrote: post #165

Earlier quoted context omitted.

Chess engines faced worse than quadratic scaling and came out the other side… Software operates in a crazy number of different domains with wildly different constraints.

I believe hinkley was commenting on things that are quadratic in the number of users. It doesn't sound like a chess engine would have that property.

They did make it sound like almost anything would necessarily have n scale with new users. That assumption is already questionnable

There's a bit of a "What Computational Complexity Taught Me About B2B SaaS" bias going.

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

#193

Post by crote »

throwaway2037 wrote: post #152
esprehn wrote: post #147

Earlier quoted context omitted.

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

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

You've got to keep in mind that computers aren't the 1-instruction-at-a-time purely sequential machines anymore.

Let's say you've got a linear array of bytes, and you want to see if it contains a specific value. What would a modern CPU need to execute? Well, we can actually compare 64 values at a time with _mm512_mask_cmp_epu8_mask! You still need a little bit of setup and a final "did any of them match" check, of course. Want to compare 512 values? You can probably do that in less than 10 clock cycles with modern machines

Doing the same with a hash set? Better make sure that hash algorithm is fast. Sure it's O(1), but if calculating the hash takes 20 cycles it doesn't matter.

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

#194

Post by bayindirh »

friggles wrote: post #148
bayindirh wrote: post #137

Earlier quoted context omitted.

This is why I said "We are discussing (mostly) tech here". I don't agree that creating a throwaway for every comment is "superior". It's basically spamming and it's even noted in the guidelines. Nazi Germany & Jews issue is different. There's an aspect of forcing, and this is unethical and wrong on so many levels, and I'll just leave the subject here. OTOH, from my perspective if you're afraid that you're writing a s…

You assume the homogeneity and conformity of your thinking will save you. There were plenty of Germans that did that also. Germany lost the war. It’s fine to be fearless. But don’t persecute someone for trying to protect themselves.

You assume that people who say the same thing, think the same way. Your assumptions about me lost you the argument.

As I said, I asked genuine questions. They might be blunt and unpopular questions, but they are questions, and it's totally OP's decision to answer me or not.

I respect them in every case.

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

#195

Post by broken_broken_ »

Arcuru wrote: post #23

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?

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

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

#196

Post by MyFedora »

cvoss wrote: post #47
School-Cotton wrote: post #8

Earlier quoted context omitted.

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

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.

We simplify the big O notation in computer science. This is standard practice.

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

#197

Post by Tainnor »

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…

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

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

#198

Post by gregorvand »

Arcuru wrote: post #23

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?

15 years also seems like a long time

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

#199

Post by ndriscoll »

bombela wrote: post #27
Arcuru wrote: post #23

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?

> 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, Syncth…

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.

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

#200

Post by saagarjha »

delusional wrote: post #169
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…

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.
Post reply on HN