7 ms·

Supercharging the Git Commit Graph IV: Bloom Filters

205 points by matthewwarren 8y ago

jaytaylor 8y ago
This is interesting work. I've never noticed the referenced git operation as being slow. In my experience, git log -- <path/to/file/or/dir> 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 filters in use in widely-used software in real life, in any case!
- tzahola 8y ago
  >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: https://github.com/Microsoft/gvfs https://github.com/Microsoft/gvfs
  - edejong 8y ago
    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-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... [2] On monolithic repositories (2014) https://gregoryszorc.com/blog/2014/09/09/on-monolithic-repositories/ https://gregoryszorc.com/blog/2014/09/09/on-monolithic-repos...
    - influx 8y ago
      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 developer laptops had to have their SSD upgraded as they didn't have enough space to get the whole thing and do work. I'm sure they've improved it since then, but this was one of many things Twitter simply cargo culted from Google without any real benefit.
      - avar 8y ago
        [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...
        influx 8y ago
        Sure, that was the justification, but when you literally can’t switch branches without waiting for a minute, I fail to see the benefit. As I recall the developers authoring the custom git patches left the company around that time. I don’t know what happened after that. There was talk of moving to mercurial with facebooks patches, but I had already left.
  - shoo 8y ago
    further monorepo reading: Paul Hammant also likes to write about this and related subjects. https://paulhammant.com/categories.html#Monorepos https://paulhammant.com/categories.html#Monorepos
- masklinn 8y ago
  > 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 <command> | head -n1) and respectively 10 and 4 for complete data generation (time <command> > /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.
  - deleted 8y ago
    [deleted]
- dingo_bat 8y ago
  > 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.
  - tzahola 8y ago
    Magnificent! Which company is this?
  - mwcampbell 8y ago
    Sounds like your team would benefit from GVFS [1]. [1]: https://github.com/Microsoft/GVFS https://github.com/Microsoft/GVFS
    - Sir_Cmpwn 8y ago
      No sane team is running on Windows, so probably not.
      - guhidalg 8y ago
        Please don't feed the trolls.
      - therealdrag0 8y ago
        Get over it. My company gives every employee the system of their choice. Some choose Mac, some PC, some Linux. Everyone works on the same stuff and is productive.
      - voltagex_ 8y ago
        I respect your open source work, but bashing Windows isn't going to help anyone. You're not going to convert anyone to Linux that way and you're not really achieving anything.
lozenge 8y ago
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?
- deleted 8y ago
  [deleted]
- tempay 8y ago
  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.
  - lozenge 8y ago
    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.
  - masklinn 8y ago
    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 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).
- stolee 8y ago
  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.
  - 8y ago
avar 8y ago
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/ 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.
- gilleain 8y ago
  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 https://arxiv.org/abs/1104.5261)
kanox 8y ago
Can you make `$ git branch` fast? Because it takes 5-10 seconds for me on linux.
- ninkendo 8y ago
  How big of a repository? It should be a near-instantaneous operation. I’m in a repo with 40GB in .git (hundreds of thousands of commits) and `git branch newbranch` is pretty much immediate.
- stolee 8y ago
  Do you mean `git branch --contains` or `git branch -vv`? There are many options to `git branch` that cause Git to be very slow. The commit-graph feature in general will make these faster by reducing time spent parsing commits. You can compute a commit-graph right now if you have Git 2.18 installed: https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/ https://blogs.msdn.microsoft.com/devops/2018/06/25/superchar... Generation numbers will make these operations much faster in Git 2.19. Here are the related commits: `git branch --contains`: https://github.com/git/git/commit/f9b8908b85247ef60001a683c281af0080e9ee77 https://github.com/git/git/commit/f9b8908b85247ef60001a683c2... `git tag --contains`: https://github.com/git/git/commit/819807b33f820dc17d96f043747daf18c5e38516 https://github.com/git/git/commit/819807b33f820dc17d96f04374...
  - jwilk 8y ago
    On HN: https://news.ycombinator.com/item?id=17408985 https://news.ycombinator.com/item?id=17408985
  - kanox 8y ago
    A long time ago I made an alias always passes -v to git branch and this is the problem: on large repos it can take a long time to compute the "ahead X, behind Y" information. It can be fixed by aliasing to some git branch --format without %(upstream:track) Those numbers not really useful interactively when very large, for example it doesn't help to print that one of my branches is "behind 132132". Maybe git could print "ahead 7, behind 1000+" for old stale branches stuff? This way it would limit the number of commits examined.
ythn 8y ago
Coming from a game programming background - before clicking the link I was expecting a VFX "bloom filter" effect on a visual commit graph where "light sources" are exaggerated and seem to "glow".
- Heliophite 8y ago
  That was my reaction as well. "Oh, neat, visualization!" ".. oh, the óther bloom."
crb002 8y ago
Glad MS poached Stolee from Iowa State.

205 points by matthewwarren 8y ago

This is interesting work. I've never noticed the referenced git operation as being slow. In my experience, git log -- <path/to/file/or/dir> 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 filters in use in widely-used software in real life, in any case!

tzahola 8y ago
>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: https://github.com/Microsoft/gvfs https://github.com/Microsoft/gvfs
- edejong 8y ago
  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-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... [2] On monolithic repositories (2014) https://gregoryszorc.com/blog/2014/09/09/on-monolithic-repositories/ https://gregoryszorc.com/blog/2014/09/09/on-monolithic-repos...
  - influx 8y ago
    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 developer laptops had to have their SSD upgraded as they didn't have enough space to get the whole thing and do work. I'm sure they've improved it since then, but this was one of many things Twitter simply cargo culted from Google without any real benefit.
    - avar 8y ago
      [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...
      - influx 8y ago
        Sure, that was the justification, but when you literally can’t switch branches without waiting for a minute, I fail to see the benefit. As I recall the developers authoring the custom git patches left the company around that time. I don’t know what happened after that. There was talk of moving to mercurial with facebooks patches, but I had already left.
- shoo 8y ago
  further monorepo reading: Paul Hammant also likes to write about this and related subjects. https://paulhammant.com/categories.html#Monorepos https://paulhammant.com/categories.html#Monorepos
masklinn 8y ago
> 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 <command> | head -n1) and respectively 10 and 4 for complete data generation (time <command> > /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.
- deleted 8y ago
  [deleted]
dingo_bat 8y ago
> 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.
- tzahola 8y ago
  Magnificent! Which company is this?
- mwcampbell 8y ago
  Sounds like your team would benefit from GVFS [1]. [1]: https://github.com/Microsoft/GVFS https://github.com/Microsoft/GVFS
  - Sir_Cmpwn 8y ago
    No sane team is running on Windows, so probably not.
    - guhidalg 8y ago
      Please don't feed the trolls.
    - therealdrag0 8y ago
      Get over it. My company gives every employee the system of their choice. Some choose Mac, some PC, some Linux. Everyone works on the same stuff and is productive.
    - voltagex_ 8y ago
      I respect your open source work, but bashing Windows isn't going to help anyone. You're not going to convert anyone to Linux that way and you're not really achieving anything.

lozenge 8y ago

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?

deleted 8y ago
[deleted]
tempay 8y ago
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.
- lozenge 8y ago
  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.
- masklinn 8y ago
  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 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).
stolee 8y ago
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.
- 8y ago

avar 8y ago

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

gilleain 8y ago
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 https://arxiv.org/abs/1104.5261)

kanox 8y ago

Can you make `$ git branch` fast? Because it takes 5-10 seconds for me on linux.

ninkendo 8y ago
How big of a repository? It should be a near-instantaneous operation. I’m in a repo with 40GB in .git (hundreds of thousands of commits) and `git branch newbranch` is pretty much immediate.
stolee 8y ago
Do you mean `git branch --contains` or `git branch -vv`? There are many options to `git branch` that cause Git to be very slow. The commit-graph feature in general will make these faster by reducing time spent parsing commits. You can compute a commit-graph right now if you have Git 2.18 installed: https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/ https://blogs.msdn.microsoft.com/devops/2018/06/25/superchar... Generation numbers will make these operations much faster in Git 2.19. Here are the related commits: `git branch --contains`: https://github.com/git/git/commit/f9b8908b85247ef60001a683c281af0080e9ee77 https://github.com/git/git/commit/f9b8908b85247ef60001a683c2... `git tag --contains`: https://github.com/git/git/commit/819807b33f820dc17d96f043747daf18c5e38516 https://github.com/git/git/commit/819807b33f820dc17d96f04374...
- jwilk 8y ago
  On HN: https://news.ycombinator.com/item?id=17408985 https://news.ycombinator.com/item?id=17408985
- kanox 8y ago
  A long time ago I made an alias always passes -v to git branch and this is the problem: on large repos it can take a long time to compute the "ahead X, behind Y" information. It can be fixed by aliasing to some git branch --format without %(upstream:track) Those numbers not really useful interactively when very large, for example it doesn't help to print that one of my branches is "behind 132132". Maybe git could print "ahead 7, behind 1000+" for old stale branches stuff? This way it would limit the number of commits examined.

ythn 8y ago

Coming from a game programming background - before clicking the link I was expecting a VFX "bloom filter" effect on a visual commit graph where "light sources" are exaggerated and seem to "glow".

Heliophite 8y ago
That was my reaction as well. "Oh, neat, visualization!" ".. oh, the óther bloom."

crb002 8y ago

Glad MS poached Stolee from Iowa State.