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

Supercharging the Git Commit Graph IV: Bloom Filters

blogs.msdn.microsoft.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#11

Post by lozenge »

tempay wrote: post #6
lozenge wrote: post #3

Does it work when I'm looking for all commits changing a directory? I.e. Do directories get added to the bloom filter or just filenames?

I thought git didn't have a concept of directories, just blobs that have a path? If so, I presume "all commits changing a directory" is found by individually checking each file contained by the directory.

As the article mentions, each folder is a tree object containing (referencing) subfolders and blobs (files). Run git show HEAD^{tree} to see it.

Finding the list of all filenames that were ever in a particular path is very expensive.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#12

Post by masklinn »

jaytaylor wrote: post #2

This is interesting work. I've never noticed the referenced git operation as being slow. In my experience, git log -- has always seemed instantaneous or nearly so. It's quick even on code bases that are quite large (years of work from large teams, 10's of thousands of commits). Maybe data and performance information on before vs. after bloom filters would help clarify the specific design goals. I love seeing bloom fi…

> has always seemed instantaneous or nearly so. It's quick even on code bases that are quite large (years of work from large teams, 10's of thousands of commits).

The issue tends to be mostly graph log, note that while this applies to all commit walks it's work mostly done in the context of the commit-graph feature as graphlogging can get fairly slow on big complex repos (mega-scale commit counts).

For example on $dayjob's main repository (~120k commits on master, ~160k total) `log --graph` has a time-to-first-byte of 2.5s, compared to 0.5s for regular log (time | head -n1) and respectively 10 and 4 for complete data generation (time > /dev/null). So there's a 5x difference between log and log --graph for TTFB compared to a 2.5 difference in total difference, log --graph cost is much more "front-loaded". And I expect that difference to grow as the repository grows.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#13

Post by avar »

influx wrote: post #8
edejong wrote: post #7

Earlier quoted context omitted.

Well, Google has succesfully defended their monorepo approach on multiple occasions. So, before dissing this approach as 'non-SV-canon', read Google's [1] and Twitters [2] accounts on why they do what they do. [1] Why Google Stores Billions of Lines of Code in a Single Repository (2016) https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... [2] On monolithic repositories (2014) https://gregoryszorc.com/blog/…

Odd that people are including Twitter as a data point in the monorepo debate. I was there when they transitioned to a Git monorepo, and it nearly killed the companies productivity. Imagine having to torrent a starter pack of the repo, then trying to sync and failing multiple times. Then after it syncs, it could take minutes to do common operations such as change a branch, or check in a file. Not to mention many devel…

[Source: I contribute to Git and talked to Twitter's "git guys" at the time at Git Merge, am not affiliated with Twitter in any way]

My understanding is that they didn't cargo-cult anything. They made a conscious choice at Twitter to pursue the monorepo model.

One reason they mentioned is that while they have a lot of services running all over the place, those services tend to heavily use the same underlying base libraries.

Think the library that validates Twitter usernames, parses out the text of a tweet etc. By having a monorepo they can easily atomically change those libraries for all their consumers. This tends to be why companies go for the monorepo model in general.

This is all information from 2016-ish. Around that time users with *@twopensource.com E-Mail addresses stopped contributing to git.git. I have no idea why, presumably changed internal priorities or something like that. Maybe their internal repository structure changed so they didn't need to author their own performance patches anymore, maybe not...

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#14

Post by masklinn »

tempay wrote: post #6
lozenge wrote: post #3

Does it work when I'm looking for all commits changing a directory? I.e. Do directories get added to the bloom filter or just filenames?

I thought git didn't have a concept of directories, just blobs that have a path? If so, I presume "all commits changing a directory" is found by individually checking each file contained by the directory.

Git very much has directories, it calls them "tree": a commit links to a tree, which links to a number of trees or blobs associating each with a name: https://git-scm.com/book/gr/v2/Git-Internals-Git-Objects

A blob is a file (ish, it can also be use for some other things since it's not intrinsically named), a tree is a directory.

However Git doesn't treat filesystem directories themselves as first-class e.g. you can't version an empty directory. A tree only exists in order to contain sub-items (ultimately blobs).

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#16

Post by Orphis »

tzahola wrote: post #10
edejong wrote: post #7

Earlier quoted context omitted.

Well, Google has succesfully defended their monorepo approach on multiple occasions. So, before dissing this approach as 'non-SV-canon', read Google's [1] and Twitters [2] accounts on why they do what they do. [1] Why Google Stores Billions of Lines of Code in a Single Repository (2016) https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... [2] On monolithic repositories (2014) https://gregoryszorc.com/blog/…

Wait a sec, I thought the monorepo was the SV canon. As in, "we have to keep our velocity high, to deliver customer value multiple times a day, so everyone should be able to make changes across the whole stack in a single commit, and release to production in five minutes." In my opinion it boils down to a single factor: if you don't have proper APIs between your components, then you will need to make cross-cutting ch…

At large scale, you still need to have proper API boundaries, even with a monorepo. Otherwise, even with the best tooling, you will never be able to change anything.

The APIs are there to ensure the behavior won't change and break anything. In a monorepo, that is easier to check by running all the tests that are affected by your code changes. The actual programming "syntax" is a detail though, and that can be changed (atomically everywhere) anytime with proper tooling.

It's only in the old traditional split model that APIs are supposed to be a guarantee for syntax + behavior (+ sometimes ABI).

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#17

Post by stolee »

lozenge wrote: post #3

Does it work when I'm looking for all commits changing a directory? I.e. Do directories get added to the bloom filter or just filenames?

It does! The Bloom filter stores every path that changed, including paths to trees (except the root tree, which is expected to be changed by default). When you change a file, you also change every tree above it.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#18

Post by shoo »

tzahola wrote: post #4
jaytaylor wrote: post #2

This is interesting work. I've never noticed the referenced git operation as being slow. In my experience, git log -- has always seemed instantaneous or nearly so. It's quick even on code bases that are quite large (years of work from large teams, 10's of thousands of commits). Maybe data and performance information on before vs. after bloom filters would help clarify the specific design goals. I love seeing bloom fi…

>10s of thousands of commits Lol! The scale at which these companies are (ab)using git is multiple orders of magnitudes greater than that. You see, they think it’s a good idea to put every piece of code ever written in the whole company in the same repo. They call it the “monorepo”, and it’s hundreds of gigabytes with many millions of commits. Microsoft even created a virtual filesystem which they run git on top of:…

further monorepo reading: Paul Hammant also likes to write about this and related subjects. https://paulhammant.com/categories.html#Monorepos

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#19

Post by dingo_bat »

jaytaylor wrote: post #2

This is interesting work. I've never noticed the referenced git operation as being slow. In my experience, git log -- has always seemed instantaneous or nearly so. It's quick even on code bases that are quite large (years of work from large teams, 10's of thousands of commits). Maybe data and performance information on before vs. after bloom filters would help clarify the specific design goals. I love seeing bloom fi…

> I've never noticed the referenced git operation as being slow

On our monorepo, a simple 'git log -- random_file.cpp' can take anywhere from 10s to a couple of minutes.

Edit: This is on VMware instances with 16 Xeon cores and 32 gigs of memory with SSD backed storage. My puny laptop would probably struggle to even clone the repo.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#20

Post by gilleain »

avar wrote: post #15

This thread on the Git mailing list from back in May has some more technical details: https://public-inbox.org/git/86zi1fus3t.fsf@gmail.com/ Derrick Stolee, the author of this post, chimes in with some more details about how this works under the hood.

Huh I wondered why his github had so much on git lately.

I know his work from generating graphs (eg https://arxiv.org/abs/1104.5261)

Post reply on HN