{"thread":{"id":"38573","subject":"Multi-threaded 'git clone'","startedAt":"2015-02-16T13:16:46Z","lastAt":"2015-02-17T03:16:24Z","messageCount":9,"participants":["Koosha Khajehmoogahi","David Lang","Jeff King","Junio C Hamano","Duy Nguyen","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"256149","messageId":"CACSCj9yoso1oLHzySx1F3O+DFAPiz-XEz1YNCEUMu1pj7KmX7w@mail.gmail.com","threadId":"38573","inReplyTo":null,"subject":"Multi-threaded 'git clone'","fromName":"Koosha Khajehmoogahi","fromEmail":"koosha.khajeh@gmail.com","sentAt":"2015-02-16T13:16:46Z","receivedAt":"2015-02-16T13:16:46Z","isPatch":false,"sender":{"key":"koosha.khajeh@gmail.com","avatar":"https://gravatar.com/avatar/f19f87f411bad2d1f9f84c0c73c4c97cfffebd9871a77f374ab3cad0af9ee764?d=mp&s=160"},"body":"Greetings,\n\nCloning huge repositories like Linux kernel takes considerable amount\nof time. Is it possible to incorporate a multi-threaded simultaneous\nconnections functionality for cloning? To what extent do we need to\nchange the architecture of the current code and how large would be the\nscope of the work? That just seems an interesting idea to me and would\nliked to share it with the community.\n\nRegards\n\n-- \nKoosha\n"},{"id":"256151","messageId":"alpine.DEB.2.02.1502160521030.23770@nftneq.ynat.uz","threadId":"38573","inReplyTo":"CACSCj9yoso1oLHzySx1F3O+DFAPiz-XEz1YNCEUMu1pj7KmX7w@mail.gmail.com","subject":"Re: Multi-threaded 'git clone'","fromName":"David Lang","fromEmail":"david@lang.hm","sentAt":"2015-02-16T13:31:13Z","receivedAt":"2015-02-16T13:31:13Z","isPatch":false,"sender":{"key":"david@lang.hm","avatar":null},"body":"On Mon, 16 Feb 2015, Koosha Khajehmoogahi wrote:\n\n> Cloning huge repositories like Linux kernel takes considerable amount\n> of time. Is it possible to incorporate a multi-threaded simultaneous\n> connections functionality for cloning? To what extent do we need to\n> change the architecture of the current code and how large would be the\n> scope of the work? That just seems an interesting idea to me and would\n> liked to share it with the community.\n\nThey key question is what is it that takes the time in clonding and can that be \nmulti-threaded.\n\nIf it's the netwrok traffic that takes the most time, where is the bottleneck?\n\nIs it in the server software assembling what will be sent? Is it in the \nreceiving software processing it? If so, multiple threads could help.\n\nIs it in network bandwidth? If so doing multiple connections won't help much. \nTCP connections favour a few connections passing a lot of data rather than many \nconnections passing a little. The one place where multiple connections can help \nis when you have non-congestion induced packet loss as a lost packet on a \nconnection will cause the throughput of that connection to drop (if the drop is \ndue to congestion, this is TCP working as designed, throttling back to match the \navailable bandwidth). This can be a significant effect if you have a very high \nbandwidth, high latency connection (think multiple Gb on international \nconnections), but for lower bandwidth connections it's much less of a factor. \nYou can look at projects like bbcp\n\nI think it's an interesting question to look at, but before you start looking at \nchanging the architecture of the current code, I would suggest doing a bit more \nanalisys of the problem to see if the bottleneck is really where you think it \nis.\n\nFirst measure, then optimize :-)\n\nDavid Lang\n"},{"id":"256152","messageId":"20150216150305.GA8279@peff.net","threadId":"38573","inReplyTo":"alpine.DEB.2.02.1502160521030.23770@nftneq.ynat.uz","subject":"Re: Multi-threaded 'git clone'","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-16T15:03:06Z","receivedAt":"2015-02-16T15:03:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 16, 2015 at 05:31:13AM -0800, David Lang wrote:\n\n> I think it's an interesting question to look at, but before you start\n> looking at changing the architecture of the current code, I would suggest\n> doing a bit more analisys of the problem to see if the bottleneck is really\n> where you think it is.\n> \n> First measure, then optimize :-)\n\nYes, very much so. Fortunately some people have already done some of\nthis work. :)\n\nOn the server side of a clone, the things that must be done before\nsending any data are:\n\n  1. Count up all of the objects that must be sent by traversing the\n     object graph.\n\n  2. Find any pairs for delta compression (this is the \"Compressing\n     objects\" phase of the progress reporting).\n\nStep (1) naively takes 30-45 seconds for a kernel repo. However, with\nreachability bitmaps, it's instant-ish. I just did a clone from\nkernel.org, and it looks like they've turned on bitmaps.\n\nFor step (2), git will reuse deltas that already exist in the on-disk\npackfile, and will not consider new deltas between objects that are\nalready in the same pack (because we would already have considered them\nwhen packing in the first place). So the key for servers is to keep\nthings pretty packed. My kernel.org clone shows that they could probably\nstand to repack torvalds/linux.git, but it's not too terrible.\n\nThis part is multithreaded, so what work we do happens in parallel. But\nnote that some servers may turn pack.threads down to 1 (since their many\nCPUs are kept busy by multiple requests, rather than trying to finish a\nsingle one).\n\nThen the server streams the data to the client. It might do some light\nwork transforming the data as it comes off the disk, but most of it is\njust blitted straight from disk, and the network is the bottleneck.\n\nOn the client side, the incoming data streams into an index-pack\nprocess. For each full object it sees, it hashes and records the name of\nthe object as it comes in. For deltas, it queues them for resolution\nafter the complete pack arrives.\n\nOnce the full pack arrives, then it resolves all of the deltas. This\npart is also multithreaded. If you check out \"top\" during the \"resolving\ndeltas\" phase of the clone, you should see multiple cores in use.\n\nSo I don't think there is any room for \"just multithread it\" in this\nprocess. The CPU intensive bits are already multithreaded. There may be\nroom for optimizing that, though (e.g., reducing lock contention or\nsimilar).\n\nIt would also be possible to resolve deltas while the pack is streaming\nin, rather than waiting until the whole thing arrives. That's not\npossible in all cases (an object may be a delta against a base that\ncomes later in the pack), but in practice git puts bases before their\ndeltas. However, it's overall less efficient, because you may end up\nwalking through the same parts of the delta chain more than once. For\nexample, imagine you see a stream of objects A, B, C, D. You get B and\nsee that it's a delta against A. So you resolve it, hash the object, and\nare good. Now you see C, which is a delta against B. To generate C, you\nhave to compute B again. Now you get to D, which is another delta\nagainst B. So now we compute B again.\n\nYou can get around this somewhat with a cache of intermediate object\ncontents, but of course there may be hundreds or thousands of chains\nlike this in use at once, so you're going to end up with some cache\nmisses.\n\nWhat index-pack does instead is to wait until it has all of the objects,\nthen finds A and says \"what objects use A as a base?\". Then it computes\nB, hashes it, and says \"what objects use B as a base?\". And finds C and\nD, after which it nows it can drop the intermediate result B.\n\nSo that's less work over all, though in some workloads it may finish\nfaster if you were to stream it (because your many processors are\nsitting idle while we are blocked on network bandwidth). So that's a\npotential area of exploration.\n\n-Peff\n"},{"id":"256154","messageId":"alpine.DEB.2.02.1502160727480.23770@nftneq.ynat.uz","threadId":"38573","inReplyTo":"20150216150305.GA8279@peff.net","subject":"Re: Multi-threaded 'git clone'","fromName":"David Lang","fromEmail":"david@lang.hm","sentAt":"2015-02-16T15:31:33Z","receivedAt":"2015-02-16T15:31:33Z","isPatch":false,"sender":{"key":"david@lang.hm","avatar":null},"body":"On Mon, 16 Feb 2015, Jeff King wrote:\n\n> On Mon, Feb 16, 2015 at 05:31:13AM -0800, David Lang wrote:\n>\n>> I think it's an interesting question to look at, but before you start\n>> looking at changing the architecture of the current code, I would suggest\n>> doing a bit more analisys of the problem to see if the bottleneck is really\n>> where you think it is.\n>>\n>> First measure, then optimize :-)\n>\n> Yes, very much so. Fortunately some people have already done some of\n> this work. :)\n\nnice summary\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\nDepending on how close to full the WAN link is, it may be possible to improve \nthis with multiple connections (again, referencing bbcp), but there's also the \nquestion of if it's worth trying to use the entire WAN for a single user. The \nvast majority of the time the server is doing more than one thing and would \nrather let any individual user wait a bit and service the other users.\n\nDavid Lang\n"},{"id":"256155","messageId":"20150216154745.GA10120@peff.net","threadId":"38573","inReplyTo":"alpine.DEB.2.02.1502160727480.23770@nftneq.ynat.uz","subject":"Re: Multi-threaded 'git clone'","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-16T15:47:45Z","receivedAt":"2015-02-16T15:47:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"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\nYeah, I have seen clients that make multiple TCP connections to each\nrequest a chunk of a file in parallel. The short answer is that this is\ngoing to be very hard with git. Each clone generates the pack on the fly\nbased on what's on disk and streams it out. It should _usually_ be the\nsame, but there's nothing to guarantee byte-for-byte equality between\ninvocations. So you'd have to multiplex all of the connections into the\nsame server process. And even then it's hard; that process knows its\ngoing to send you byte the bytes for object X, but it doesn't know at\nexactly which offset until it gets there, which makes sending things out\nof order tricky. And the whole output is checksummed by a single sha1\nover the whole stream that comes at the end.\n\nI think the most feasible thing would be to quickly spool it to a server\non the LAN, and then use an existing fetch-in-parallel tool to grab it\nfrom there over the WAN.\n\n-Peff\n"},{"id":"256163","messageId":"xmqq1tlp7l3w.fsf@gitster.dls.corp.google.com","threadId":"38573","inReplyTo":"20150216154745.GA10120@peff.net","subject":"Re: Multi-threaded 'git clone'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-16T18:43:47Z","receivedAt":"2015-02-16T18:43:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ... 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\n> server on the LAN, and then use an existing fetch-in-parallel tool\n> to grab it from there over the WAN.\n\nOne possibility would be for the server to prepare a static bundle\nfile to bootstrap all the \"clone\" clients with and publish it on a\nCDN.  A protocol extension would tell the client where to download\nthe bundle from, the client can then grab the bundle to clone from\nit to become \"slightly stale but mostly up to date\", and then do a\nusual incremental update with the server after that to be complete.\n\nThe server would update the bundle used to bootstrap clone clients\nperiodically in order to keep the incrementals to the minimum, and\nwould make sure their bitmap is anchored at the tips of bundles to\nminimize the object counting load during the incremental phase.\n\nI think \"repo\" used by folks who do AOSP does something similar to\nthat by scripting around \"git clone\".  I'd imagine that they would\nbe happy to see if \"git clone\" did all that inside.\n"},{"id":"256175","messageId":"CACsJy8Brnu7rBxtCq_ac58BW7dOK=wtzMxVL-gsOUXJB2Jss9w@mail.gmail.com","threadId":"38573","inReplyTo":"20150216154745.GA10120@peff.net","subject":"Re: Multi-threaded 'git clone'","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-16T23:16:39Z","receivedAt":"2015-02-16T23:16:39Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Feb 16, 2015 at 10:47 PM, Jeff King <peff@peff.net> wrote:\n> 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.\n\nIt's usually _not_ the same. I tried when I wanted to produce stable\npacks. The first condition is single-threaded pack-objects. Otherwise\nthread scheduler could make object order unpredictable.\n-- \nDuy\n"},{"id":"256178","messageId":"20150217005632.GA13001@peff.net","threadId":"38573","inReplyTo":"CACsJy8Brnu7rBxtCq_ac58BW7dOK=wtzMxVL-gsOUXJB2Jss9w@mail.gmail.com","subject":"Re: Multi-threaded 'git clone'","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-17T00:56:32Z","receivedAt":"2015-02-17T00:56:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 17, 2015 at 06:16:39AM +0700, Duy Nguyen wrote:\n\n> On Mon, Feb 16, 2015 at 10:47 PM, Jeff King <peff@peff.net> wrote:\n> > 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.\n> \n> It's usually _not_ the same. I tried when I wanted to produce stable\n> packs. The first condition is single-threaded pack-objects. Otherwise\n> thread scheduler could make object order unpredictable.\n\nTrue. If you keep your server repositories fully packed, that eliminates\nthe delta search (and/or makes it feasible to turn pack.threads to 1 to\nmake it deterministic). But any change in the repository (e.g., somebody\nelse pushing, even to a ref you are not fetching) can cause unexpected\nchanges in the bytes.\n\n-Peff\n"},{"id":"256179","messageId":"CAJo=hJt8FU9wJBidivdwa-ryZsE-=EMT_DY--bX4FYKBDXsY5w@mail.gmail.com","threadId":"38573","inReplyTo":"xmqq1tlp7l3w.fsf@gitster.dls.corp.google.com","subject":"Re: Multi-threaded 'git clone'","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-02-17T03:16:24Z","receivedAt":"2015-02-17T03:16:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Feb 16, 2015 at 10:43 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Jeff King <peff@peff.net> writes:\n>\n>> ... 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\n>> server on the LAN, and then use an existing fetch-in-parallel tool\n>> to grab it from there over the WAN.\n>\n> One possibility would be for the server to prepare a static bundle\n> file to bootstrap all the \"clone\" clients with and publish it on a\n> CDN.  A protocol extension would tell the client where to download\n> the bundle from, the client can then grab the bundle to clone from\n> it to become \"slightly stale but mostly up to date\", and then do a\n> usual incremental update with the server after that to be complete.\n>\n> The server would update the bundle used to bootstrap clone clients\n> periodically in order to keep the incrementals to the minimum, and\n> would make sure their bitmap is anchored at the tips of bundles to\n> minimize the object counting load during the incremental phase.\n>\n> I think \"repo\" used by folks who do AOSP does something similar to\n> that by scripting around \"git clone\".  I'd imagine that they would\n> be happy to see if \"git clone\" did all that inside.\n\nYes, the \"repo\" tool used by Android uses curl to download a\npreviously cached $URL/clone.bundle using resumable HTTP. For Android\nthe file is only updated ~every 6 months at major releases and is\neasily cached by CDNs and HTTP proxy servers.\n\nThis is spooled to a temporary file on disk then unpacked using `git\nfetch $path/clone.bundle refs/heads/*:refs/remotes/origin/*`.\nAfterwards a normal git fetch is run to bring the new clone current\nwith the server, picking up any delta that happened since the bundle\nwas created and cached.\n\nThe Android Git servers at android.googlesource.com just recognize\n*/clone.bundle GET requests and issue 302 redirects to the CDN farm\nthat actually stores and serves the precreated bundle files.\n\nWe really want to see this in stock git clone for HTTP transports, as\nother projects like Chromium want to use it for their ~3 GiB\nrepository. Being able to build the bulk of the repo every few months\nand serve it out using a CDN to bootstrap new clients would really\nhelp developers on slower or flaky network connections.\n"}]}