{"thread":{"id":"38578","subject":"Re: Multi-threaded 'git clone'","startedAt":"2015-02-17T05:20:02Z","lastAt":"2015-02-18T03:14:05Z","messageCount":3,"participants":["Martin Fick","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"256183","messageId":"20150217052007.CC8B713FECF@smtp.codeaurora.org","threadId":"38578","inReplyTo":null,"subject":"Re: Multi-threaded 'git clone'","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2015-02-17T05:20:02Z","receivedAt":"2015-02-17T05:20:02Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"There currently is a thread on the Gerrit list about how much faster cloning can be when using Gerrit/jgit GCed packs with bitmaps versus C git GCed packs with bitmaps.\n\nSome differences outlined are that jgit seems to have more bitmaps, it creates one for every refs/heads, is C git doing that?  Another difference seems to be that jgit creates two packs, splitting stuff not reachable from refs/heads into its own pack.  This makes a clone have zero CPU server side in the pristine case.  In the Gerrit use case, this second \"unreachable\" packfile can be sizeable, I wonder if there are other use cases where this might also be the case (and this slowing down clones for C git GCed repos)?\n\nIf there is not a lot of parallelism left to squeak out, perhaps a focus with better returns is trying to do whatever is possible to make all clones (and potentially any fetch use case deemed important on a particular server) have zero CPU?  Depending on what a server's primary mission is, I could envision certain admins willing to sacrifice significant amounts of disk space to speed up their fetches.  Perhaps some more extreme thinking (such as what must have led to bitmaps) is worth brainstorming about to improve server use cases?\n\nWhat if an admin were willing to sacrifice a packfile for every use case he deemed important, could git be made to support that easily?  For example, maybe the admin considers a clone or a fetch from master to be important, could zero percent CPU be achieved regularly for those two use cases?  Cloning is possible if the repository were repacked in the jgit style after any push to a head.  Is it worth exploring ways of making GC efficient enough to make this feasible?  Can bitmaps be leveraged to make repacking faster?  I believe that at least reachability checking could potentially be improved with bitmaps? Are there potentially any ways to make better deltification reuse during repacking (not bitmap related), by somehow reversing or translating deltas to new objects that were just received, without actually recalculating them, but yet still getting most objects deltified against the newest objects (achieving the same packs as git GC would achieve today, but faster)? What other pieces need to be improved to make repacking faster?\n\nAs for the single branch fetch case, could this somehow be improved by allocating one or more packfiles to this use case?  The simplest single branch fetch use case is likely someone doing a git init followed by a single branch fetch.  I think the android repo tool can be used in this way, so this may actually be a common use case?  With a packfile dedicated to this branch, git should be able to just stream it out without any CPU.  But I think git would need to know this packfile exists to be able to use it.  It would be nice if bitmaps could help here, but I believe bitmaps can so far only be used for one packfile.  I understand that making bitmaps span multiple packfiles would be very complicated, but maybe it would not be so hard to support bitmaps on multiple packfiles if each of these were \"self contained\"?  By self contained I mean that all objects referenced by objects in the packfile were contained in that packfile.\n\nWhat other still unimplemented caching techniques could be used to improve clone/fetch use cases? \n\n- Shallow clones (dedicate a special packfile to this, what about another bitmap format that only maps objects in a single tree to help this)?\n\n- Small fetches (simple branch FF updates), I suspect these are fast enough, but if not, maybe caching some thin packs (that could result in zero CPU requests for many clients) would be useful?  Maybe spread these out exponentially over time so that many will be available for recent updates and fewer for older updates?  I know git normally throws away thin packs after receiving them and resolving them, but if it kept them around (maybe in a special directory), it seems that they could be useful for updating other clients with zero CPU?  A thin pack cache might be something really easy to manage based on file timestamps, an admin may simply need to set a max cache size.  But how can git know what thin packs it has, and what they would be useful for, name them with their start and ending shas?\n\nSorry for the long winded rant. I suspect that some variation of all my suggestions have already been suggested, but maybe they will rekindle some older, now useful thoughts, or inspire some new ones.  And maybe some of these are better to pursue then more parallelism?\n\n-Martin\n\nQualcomm Innovation Center, Inc.\nThe Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative ProjectOn Feb 16, 2015 8:47 AM, Jeff King <peff@peff.net> wrote:\n>\n> On Mon, Feb 16, 2015 at 07:31:33AM -0800, David Lang wrote: \n>\n> > >Then the server streams the data to the client. It might do some light \n> > >work transforming the data as it comes off the disk, but most of it is \n> > >just blitted straight from disk, and the network is the bottleneck. \n> > \n> > Depending on how close to full the WAN link is, it may be possible to \n> > improve this with multiple connections (again, referencing bbcp), but \n> > there's also the question of if it's worth trying to use the entire WAN for \n> > a single user. The vast majority of the time the server is doing more than \n> > one thing and would rather let any individual user wait a bit and service \n> > the other users. \n>\n> Yeah, I have seen clients that make multiple TCP connections to each \n> request a chunk of a file in parallel. The short answer is that this is \n> going to be very hard with git. Each clone generates the pack on the fly \n> based on what's on disk and streams it out. It should _usually_ be the \n> same, but there's nothing to guarantee byte-for-byte equality between \n> invocations. So you'd have to multiplex all of the connections into the \n> same server process. And even then it's hard; that process knows its \n> going to send you byte the bytes for object X, but it doesn't know at \n> exactly which offset until it gets there, which makes sending things out \n> of order tricky. And the whole output is checksummed by a single sha1 \n> over the whole stream that comes at the end. \n>\n> I think the most feasible thing would be to quickly spool it to a server \n> on the LAN, and then use an existing fetch-in-parallel tool to grab it \n> from there over the WAN. \n>\n> -Peff \n> -- \n> To unsubscribe from this list: send the line \"unsubscribe git\" in \n> the body of a message to majordomo@vger.kernel.org \n> More majordomo info at  http://vger.kernel.org/majordomo-info.html \n"},{"id":"256251","messageId":"xmqqegpoxgf3.fsf@gitster.dls.corp.google.com","threadId":"38578","inReplyTo":"20150217052007.CC8B713FECF@smtp.codeaurora.org","subject":"Re: Multi-threaded 'git clone'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-17T23:32:48Z","receivedAt":"2015-02-17T23:32:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick <mfick@codeaurora.org> writes:\n\n> Sorry for the long winded rant. I suspect that some variation of all\n> my suggestions have already been suggested, but maybe they will\n> rekindle some older, now useful thoughts, or inspire some new ones.\n> And maybe some of these are better to pursue then more parallelism?\n\nWe avoid doing a grand design document without having some prototype\nimplementation, but I think the limitation of the current protocol\nhas become apparent enough that we should do something about it, and\nwe should do it in a way that different implementations of Git can\nall implement.\n\nI think \"multi-threaded clone\" is a wrong title for this discussion,\nin that the user does not care if it is done by multi-threading the\ncurrent logic or in any other way.  The user just wants a faster\nclone.\n\nIn addition, the current \"fetch\" protocol has the following problems\nthat limit us:\n\n - It is not easy to make it resumable, because we recompute every\n   time.  This is especially problematic for the initial fetch aka\n   \"clone\" as we will be talking about a large transfer [*1*].\n\n - The protocol extension has a fairly low length limit [*2*].\n\n - Because the protocol exchange starts by the server side\n   advertising all its refs, even when the fetcher is interested in\n   a single ref, the initial overhead is nontrivial, especially when\n   you are doing a small incremental update.  The worst case is an\n   auto-builder that polls every five minutes, even when there is no\n   new commits to be fetched [*3*].\n\n - Because we recompute every time, taking into account of what the\n   fetcher has, in addition to what the fetcher obtained earlier\n   from us in order to reduce the transferred bytes, the payload for\n   incremental updates become tailor-made for each fetch and cannot\n   be easily reused [*4*].\n\nI'd like to see a new protocol that lets us overcome the above\nlimitations (did I miss others? I am sure people can help here)\nsometime this year.\n\n\n\n[Footnotes]\n\n*1* The \"first fetch this bundle from elsewhere and then come back\n    here for incremental updates\" raised earlier in this thread may\n    be a way to alleviate this, as the large bundle can be served\n    from a static file.\n\n*2* An earlier \"this symbolic ref points at that concrete ref\"\n    attempt failed because of this and we only talk about HEAD.\n\n*3* A new \"fetch\" protocol must avoid this \"one side blindly gives a\n    large message as the first thing\".  I have been toying with the\n    idea of making the fetcher talk first, by declaring \"I am\n    interested in your refs that match refs/heads/* or refs/tags/*,\n    and I have a superset of objects that are reachable from the\n    set of refs' values X you gave me earlier\", where X is a small\n    token generated by hashing the output from \"git ls-remote $there\n    refs/heads/* refs/tags/*\".  In the best case where the server\n    understands what X is and has a cached pack data, it can then\n    send:\n\n    - differences in the refs that match the wildcards (e.g. \"Back\n      then at X I did not have refs/heads/next but now I do and it\n      points at this commit.  My refs/heads/master is now at that\n      commit.  I no longer have refs/heads/pu.  Everything else in\n      the refs/ hierarchy you are interested in is the same as state\n      X\").\n\n    - The new name of the state Y (again, the hashed value of the\n      output from \"git ls-remote $there refs/heads/* refs/tags/*\")\n      to make sure the above differences can be verified at the\n      receiving end.\n\n    - the cached pack data that contains all necessary objects\n      between X and Y.\n\n    Note that the above would work if and only if we accept that it\n    is OK to send objects between the remote tracking branches the\n    fetcher has (i.e. the objects it last fetched from the server)\n    and the current tips of branches the server has, without\n    optimizing by taking into account that some commits in that set\n    may have already been obtained by the fetcher from a\n    third-party.\n\n    If the server does not recognize state X (after all it is just a\n    SHA-1 hash value, so the server cannot recreate the set of refs\n    and their values from it unless it remembers), the exchange\n    would have to degenerate to the traditional transfer.\n\n    The server would want to recognize the result of hashing an\n    empty string, though.  The fetcher is saying \"I have nothing\"\n    in that case.\n\n\n*4* The scheme in *3* can be extended to bring the fetcher\n    step-wise.  If the server's state was X when the fetcher last\n    contacted it, and since then the server received multiple pushes\n    and has two snapshots of states, Y and Z, then the exchange may\n    go like this:\n\n    fetcher: I am interested in refs/heads/* and refs/tags/* and I\n             have your state X.\n\n    server:  Here is the incremental difference to the refs and the\n             end result should hash to Y.  Here comes the pack data\n             to bring you up to date.\n\n    fetcher: (after receiving, unpacking and updating the\n             remote-tracking refs) Thanks.  Do you have more?\n\n    server:  Yes, here is the incremental difference to the refs and the\n             end result should hash to Z.  Here comes the pack data\n             to bring you up to date.\n\n    fetcher: (after receiving, unpacking and updating the\n             remote-tracking refs) Thanks.  Do you have more?\n\n    server:  No, you are now fully up to date with me.  Bye.\n\n\n    \n"},{"id":"256254","messageId":"CAPc5daWK-GbjL=YEyW55bcBELoq05dy4umh11upG=YxKQuFMpQ@mail.gmail.com","threadId":"38578","inReplyTo":"xmqqegpoxgf3.fsf@gitster.dls.corp.google.com","subject":"Re: Multi-threaded 'git clone'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-18T03:14:05Z","receivedAt":"2015-02-18T03:14:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"On Tue, Feb 17, 2015 at 3:32 PM, Junio C Hamano <gitster@pobox.com> wrote:\n\nA few typofixes and clarifications.\n\n> *4* The scheme in *3* can be extended to bring the fetcher\n>     step-wise.  If the server's state was X when the fetcher last\n\n\"bring the fetcher up-to-date step-wise\", or \"update the fetcher step-wise\".\n\n>     contacted it, and since then the server received multiple pushes\n>     and has two snapshots of states, Y and Z, then the exchange may\n>     go like this:\n>\n>     fetcher: I am interested in refs/heads/* and refs/tags/* and I\n>              have your state X.\n>\n>     server:  Here is the incremental difference to the refs and the\n>              end result should hash to Y.  Here comes the pack data\n>              to bring you up to date.\n>\n>     fetcher: (after receiving, unpacking and updating the\n>              remote-tracking refs) Thanks.  Do you have more?\n>\n>     server:  Yes, here is the incremental difference to the refs and the\n>              end result should hash to Z.  Here comes the pack data\n>              to bring you up to date.\n>\n>     fetcher: (after receiving, unpacking and updating the\n>              remote-tracking refs) Thanks.  Do you have more?\n>\n>     server:  No, you are now fully up to date with me.  Bye.\n\nThe initial part of this exchange may go like this, if the state the\nfetcher grabbed the last time from this server is even older than X:\n\n  fetcher: I am interested in refs/heads/* and refs/tags/* and I have\n        your state W (or \"I know I am too old that I do not know what\n        you call that state\").\n\n  server: Sorry, I do not know what W is. Please be more specific.\n\n  fetcher: Here are the refs and their objects: refs/heads/master points\n        at commit A, refs/heads/maint points at commit B, ...\n\n  server: (goes and checks and finds out that fetcher is behind X).\n        OK, I'll compute a custom pack to bring you up to date with\n        one of my states. Here is the incremental difference to the refs,\n        and the end result should hash to X. Here comes the pack data.\n\n  fetcher: (after receiving, unpacking and updating the\n        remote-tracking refs) Thanks. Do you have more?\n\nAfter that, the server would update this client to state Y and then\nstate Z as above.\n\nNeedless to say, this would naturally extend to a case where you\nfollow only a single branch (you would say \"I am interested in your\nrefs/heads/dev\" with a wildcard that matches exactly that branch).\nOf course, depending on the access pattern by common project\nparticipants, the server side may choose what set of refs to prepare\nsuch snapshots and uncommon requests may always be served by\nthe traditional object enumeration codepath.\n"}]}