# Re: Git Scaling: What factors most affect Git performance for a large repo? 5 messages from 2015-02-20 to 2015-02-21. Participants: Martin Fick, David Turner, Randall S. Becker. Thread: https://gitlist.dev/t/38608 ## Martin Fick, 2015-02-20 06:57 Subject: Re: Git Scaling: What factors most affect Git performance for a large repo? Message-ID: <20150220065801.7CDC7140BE4@smtp.codeaurora.org> URL: https://gitlist.dev/e/20150220065801.7CDC7140BE4%40smtp.codeaurora.org ``` On Feb 19, 2015 5:42 PM, David Turner wrote: > > On Fri, 2015-02-20 at 06:38 +0700, Duy Nguyen wrote: > > >    * 'git push'? > > > > This one is not affected by how deep your repo's history is, or how > > wide your tree is, so should be quick.. > > > > Ah the number of refs may affect both git-push and git-pull. I think > > Stefan knows better than I in this area. > > I can tell you that this is a bit of a problem for us at Twitter.  We > have over 100k refs, which adds ~20MiB of downstream traffic to every > push. > > I added a hack to improve this locally inside Twitter: The client sends > a bloom filter of shas that it believes that the server knows about; the > server sends only the sha of master and any refs that are not in the > bloom filter.  The client  uses its local version of the servers' refs > as if they had just been sent.  This means that some packs will be > suboptimal, due to false positives in the bloom filter leading some new > refs to not be sent.  Also, if there were a repack between the pull and > the push, some refs might have been deleted on the server; we repack > rarely enough and pull frequently enough that this is hopefully not an > issue. > > We're still testing to see if this works.  But due to the number of > assumptions it makes, it's probably not that great an idea for general > use. Good to hear that others are starting to experiment with solutions to this problem! I hope to hear more updates on this. I have a prototype of a simpler, and I believe more robust solution, but aimed at a smaller use case I think. On connecting, the client sends a sha of all its refs/shas as defined by a refspec, which it also sends to the server, which it believes the server might have the same refs/shas values for. The server can then calculate the value of its refs/shas which meet the same refspec, and then omit sending those refs if the "verification" sha matches, and instead send only a confirmation that they matched (along with any refs outside of the refspec). On a match, the client can inject the local values of the refs which met the refspec and be guaranteed that they match the server's values. This optimization is aimed at the worst case scenario (and is thus the potentially best case "compression"), when the client and server match for all refs (a refs/* refspec) This is something that happens often on Gerrit server startup, when it verifies that its mirrors are up-to-date. One reason I chose this as a starting optimization, is because I think it is one use case which will actually not benefit from "fixing" the git protocol to only send relevant refs since all the refs are in fact relevant here! So something like this will likely be needed in any future git protocol in order for it to be efficient for this use case. And I believe this use case is likely to stick around. With a minor tweak, this optimization should work when replicating actual expected updates also by excluding the expected updating refs from the verification so that the server always sends their values since they will likely not match and would wreck the optimization. However, for this use case it is not clear whether it is actually even worth caring about the non updating refs? In theory the knowledge of the non updating refs can potentially reduce the amount of data transmitted, but I suspect that as the ref count increases, this has diminishing returns and mostly ends up chewing up CPU and memory in a vain attempt to reduce network traffic. Please do keep us up-to-date of your results, -Martin Qualcomm Innovation Center, Inc. The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project ``` ## David Turner, 2015-02-20 18:29 Subject: Re: Git Scaling: What factors most affect Git performance for a large repo? Message-ID: <1424456952.31528.6.camel@leckie> URL: https://gitlist.dev/e/1424456952.31528.6.camel%40leckie In-Reply-To: <20150220065801.7CDC7140BE4@smtp.codeaurora.org> ``` On Thu, 2015-02-19 at 23:57 -0700, Martin Fick wrote: > On Feb 19, 2015 5:42 PM, David Turner wrote: > > > > On Fri, 2015-02-20 at 06:38 +0700, Duy Nguyen wrote: > > > > * 'git push'? > > > > > > This one is not affected by how deep your repo's history is, or how > > > wide your tree is, so should be quick.. > > > > > > Ah the number of refs may affect both git-push and git-pull. I think > > > Stefan knows better than I in this area. > > > > I can tell you that this is a bit of a problem for us at Twitter. We > > have over 100k refs, which adds ~20MiB of downstream traffic to every > > push. > > > > I added a hack to improve this locally inside Twitter: The client sends > > a bloom filter of shas that it believes that the server knows about; the > > server sends only the sha of master and any refs that are not in the > > bloom filter. The client uses its local version of the servers' refs > > as if they had just been sent. This means that some packs will be > > suboptimal, due to false positives in the bloom filter leading some new > > refs to not be sent. Also, if there were a repack between the pull and > > the push, some refs might have been deleted on the server; we repack > > rarely enough and pull frequently enough that this is hopefully not an > > issue. > > > > We're still testing to see if this works. But due to the number of > > assumptions it makes, it's probably not that great an idea for general > > use. > > Good to hear that others are starting to experiment with solutions to this problem! I hope to hear more updates on this. > > I have a prototype of a simpler, and > I believe more robust solution, but aimed at a smaller use case I think. On connecting, the client sends a sha of all its refs/shas as defined by a refspec, which it also sends to the server, which it believes the server might have the same refs/shas values for. The server can then calculate the value of its refs/shas which meet the same refspec, and then omit sending those refs if the "verification" sha matches, and instead send only a confirmation that they matched (along with any refs outside of the refspec). On a match, the client can inject the local values of the refs which met the refspec and be guaranteed that they match the server's values. > > This optimization is aimed at the worst case scenario (and is thus the potentially best case "compression"), when the client and server match for all refs (a refs/* refspec) This is something that happens often on Gerrit server startup, when it verifies that its mirrors are up-to-date. One reason I chose this as a starting optimization, is because I think it is one use case which will actually not benefit from "fixing" the git protocol to only send relevant refs since all the refs are in fact relevant here! So something like this will likely be needed in any future git protocol in order for it to be efficient for this use case. And I believe this use case is likely to stick around. > > With a minor tweak, this optimization should work when replicating actual expected updates also by excluding the expected updating refs from the verification so that the server always sends their values since they will likely not match and would wreck the optimization. However, for this use case it is not clear whether it is actually even worth caring about the non updating refs? In theory the knowledge of the non updating refs can potentially reduce the amount of data transmitted, but I suspect that as the ref count increases, this has diminishing returns and mostly ends up chewing up CPU and memory in a vain attempt to reduce network traffic. For a more general solution, perhaps a log of ref updates could be used. Every time a ref is updated on the server, that ref would be written into an append-only log. Every time a client pulls, their pull data includes an index into that log. Then on push, the client could say, "I have refs as-of $index", and the server could read the log (or do something more-optimized) and send only refs updated since that index. ``` ## Randall S. Becker, 2015-02-20 19:27 Subject: RE: Git Scaling: What factors most affect Git performance for a large repo? Message-ID: <00b701d04d43$514ddfb0$f3e99f10$@nexbridge.com> URL: https://gitlist.dev/e/00b701d04d43%24514ddfb0%24f3e99f10%24%40nexbridge.com In-Reply-To: <20150220065801.7CDC7140BE4@smtp.codeaurora.org> ``` -----Original Message----- On Feb 20, 2015 1:58AM Martin Fick wrote: >On Feb 19, 2015 5:42 PM, David Turner wrote: > > This one is not affected by how deep your repo's history is, or how > > wide your tree is, so should be quick.. >Good to hear that others are starting to experiment with solutions to this problem! I hope to hear more updates on this. Now that Jojo and I have git 2.3.0 ported to the HP NonStop platform, there are some very large code bases out there that may start being managed using git. These will tend to initially shallow histories (100's not 1000's of commits, and fairly linear) but large source and binaries - I know of a few where just the distributed set of sources are above 1Gb and are unlikely to be managed in multiple repos despite my previous best efforts to change that. Fortunately, It is a relatively simple matter to profile the code on the platform for various operations so data on where to improve may be available - I hope. With that said, for NonStop file system tends to be heavier weight than on Linux (many more moving parts by virtue of the MPP nature of the OS and hardware). Packing up changes seems pretty good, but any operating involving creating a large number of small files does hurt a bunch. ``` ## Martin Fick, 2015-02-20 20:37 Subject: Re: Git Scaling: What factors most affect Git performance for a large repo? Message-ID: <3770789.lx2BnZ41U2@mfick1-lnx> URL: https://gitlist.dev/e/3770789.lx2BnZ41U2%40mfick1-lnx In-Reply-To: <1424456952.31528.6.camel@leckie> ``` On Friday, February 20, 2015 01:29:12 PM David Turner wrote: >... > For a more general solution, perhaps a log of ref updates > could be used. Every time a ref is updated on the server, > that ref would be written into an append-only log. Every > time a client pulls, their pull data includes an index > into that log. Then on push, the client could say, "I > have refs as-of $index", and the server could read the > log (or do something more-optimized) and send only refs > updated since that index. Interesting idea, I like it. How would you make this reliable? It relies on updates being reliably recorded which would mean that you would have to ensure that any tool which touches the repo follows this convention. That is unfortunately a tough thing to enforce for most people. But perhaps, instead of logging updates, the server could log snapshots of all refs using an atomically increasing sequence number. Then missed updates do not matter, a sequence number is simplly an opaque handle to some full ref state that can be diffed against. The snapshots need not even be taken inline with the client connection, or with every update for this to work. It might mean that some extra updates are sent when they don't need to be, but at least they will be accurate. I know in the past similar ideas have been passed around, but they typically relied on the server keeping track of the state of each client. Instead, here we are talking about clients keeping track of state for a particular server. Clients already store info about remotes. A very neat idea indeed, thanks! -Martin -- The Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation ``` ## David Turner, 2015-02-21 00:41 Subject: Re: Git Scaling: What factors most affect Git performance for a large repo? Message-ID: <1424479319.31528.18.camel@leckie> URL: https://gitlist.dev/e/1424479319.31528.18.camel%40leckie In-Reply-To: <3770789.lx2BnZ41U2@mfick1-lnx> ``` On Fri, 2015-02-20 at 13:37 -0700, Martin Fick wrote: > On Friday, February 20, 2015 01:29:12 PM David Turner wrote: > >... > > For a more general solution, perhaps a log of ref updates > > could be used. Every time a ref is updated on the server, > > that ref would be written into an append-only log. Every > > time a client pulls, their pull data includes an index > > into that log. Then on push, the client could say, "I > > have refs as-of $index", and the server could read the > > log (or do something more-optimized) and send only refs > > updated since that index. > > Interesting idea, I like it. > > How would you make this reliable? It relies on updates > being reliably recorded which would mean that you would have > to ensure that any tool which touches the repo follows this > convention. That is unfortunately a tough thing to enforce > for most people. I think it only truly relies on the server reliably updating its state on ref updates. Which of course the server will do because why would you let arbitrary processes write to your central git repo? (That is, most people use git in a roughly-centralized way, and if you turn on this config option, you promise to only do ref updates that write to the log). If the client fails to update its state (on a fetch), it will send larger-than-necessary packs but not otherwise fail. And this situation is sometimes be detectable on the client side -- if mtime(.git/refs/remotes/$remote ) > mtime (.git/server-ref-log-index/$remote), then we know our server-ref-log-index is out-of-date. ```