Multi-threaded 'git clone'

Greetings,

Cloning huge repositories like Linux kernel takes considerable amount of time. Is it possible to incorporate a multi-threaded simultaneous connections functionality for cloning? To what extent do we need to change the architecture of the current code and how large would be the scope of the work? That just seems an interesting idea to me and would liked to share it with the community.

Regards

On Mon, 16 Feb 2015, Koosha Khajehmoogahi wrote:

They key question is what is it that takes the time in clonding and can that be multi-threaded.

If it's the netwrok traffic that takes the most time, where is the bottleneck?

Is it in the server software assembling what will be sent? Is it in the receiving software processing it? If so, multiple threads could help.

Is it in network bandwidth? If so doing multiple connections won't help much. TCP connections favour a few connections passing a lot of data rather than many connections passing a little. The one place where multiple connections can help is when you have non-congestion induced packet loss as a lost packet on a connection will cause the throughput of that connection to drop (if the drop is due to congestion, this is TCP working as designed, throttling back to match the available bandwidth). This can be a significant effect if you have a very high bandwidth, high latency connection (think multiple Gb on international connections), but for lower bandwidth connections it's much less of a factor. You can look at projects like bbcp

I think it's an interesting question to look at, but before you start looking at changing the architecture of the current code, I would suggest doing a bit more analisys of the problem to see if the bottleneck is really where you think it is.

First measure, then optimize :-)

David Lang

On Mon, Feb 16, 2015 at 05:31:13AM -0800, David Lang wrote:

Yes, very much so. Fortunately some people have already done some of this work. :)

On the server side of a clone, the things that must be done before sending any data are:

  1. Count up all of the objects that must be sent by traversing the
     object graph.

  2. Find any pairs for delta compression (this is the "Compressing
     objects" phase of the progress reporting).

Step (1) naively takes 30-45 seconds for a kernel repo. However, with reachability bitmaps, it's instant-ish. I just did a clone from kernel.org, and it looks like they've turned on bitmaps.

For step (2), git will reuse deltas that already exist in the on-disk packfile, and will not consider new deltas between objects that are already in the same pack (because we would already have considered them when packing in the first place). So the key for servers is to keep things pretty packed. My kernel.org clone shows that they could probably stand to repack torvalds/linux.git, but it's not too terrible.

This part is multithreaded, so what work we do happens in parallel. But note that some servers may turn pack.threads down to 1 (since their many CPUs are kept busy by multiple requests, rather than trying to finish a single one).

Then the server streams the data to the client. It might do some light work transforming the data as it comes off the disk, but most of it is just blitted straight from disk, and the network is the bottleneck.

On the client side, the incoming data streams into an index-pack process. For each full object it sees, it hashes and records the name of the object as it comes in. For deltas, it queues them for resolution after the complete pack arrives.

Once the full pack arrives, then it resolves all of the deltas. This part is also multithreaded. If you check out "top" during the "resolving deltas" phase of the clone, you should see multiple cores in use.

So I don't think there is any room for "just multithread it" in this process. The CPU intensive bits are already multithreaded. There may be room for optimizing that, though (e.g., reducing lock contention or similar).

It would also be possible to resolve deltas while the pack is streaming in, rather than waiting until the whole thing arrives. That's not possible in all cases (an object may be a delta against a base that comes later in the pack), but in practice git puts bases before their deltas. However, it's overall less efficient, because you may end up walking through the same parts of the delta chain more than once. For example, imagine you see a stream of objects A, B, C, D. You get B and see that it's a delta against A. So you resolve it, hash the object, and are good. Now you see C, which is a delta against B. To generate C, you have to compute B again. Now you get to D, which is another delta against B. So now we compute B again.

You can get around this somewhat with a cache of intermediate object contents, but of course there may be hundreds or thousands of chains like this in use at once, so you're going to end up with some cache misses.

What index-pack does instead is to wait until it has all of the objects, then finds A and says "what objects use A as a base?". Then it computes B, hashes it, and says "what objects use B as a base?". And finds C and D, after which it nows it can drop the intermediate result B.

So that's less work over all, though in some workloads it may finish faster if you were to stream it (because your many processors are sitting idle while we are blocked on network bandwidth). So that's a potential area of exploration.

-Peff

On Mon, 16 Feb 2015, Jeff King wrote:

nice summary

Depending on how close to full the WAN link is, it may be possible to improve this with multiple connections (again, referencing bbcp), but there's also the question of if it's worth trying to use the entire WAN for a single user. The vast majority of the time the server is doing more than one thing and would rather let any individual user wait a bit and service the other users.

David Lang

On Mon, Feb 16, 2015 at 07:31:33AM -0800, David Lang wrote:

Yeah, I have seen clients that make multiple TCP connections to each request a chunk of a file in parallel. The short answer is that this is going to be very hard with git. Each clone generates the pack on the fly based on what's on disk and streams it out. It should _usually_ be the same, but there's nothing to guarantee byte-for-byte equality between invocations. So you'd have to multiplex all of the connections into the same server process. And even then it's hard; that process knows its going to send you byte the bytes for object X, but it doesn't know at exactly which offset until it gets there, which makes sending things out of order tricky. And the whole output is checksummed by a single sha1 over the whole stream that comes at the end.

I think the most feasible thing would be to quickly spool it to a server on the LAN, and then use an existing fetch-in-parallel tool to grab it from there over the WAN.

-Peff

Jeff King <peff@peff.net> writes:

One possibility would be for the server to prepare a static bundle file to bootstrap all the "clone" clients with and publish it on a CDN. A protocol extension would tell the client where to download the bundle from, the client can then grab the bundle to clone from it to become "slightly stale but mostly up to date", and then do a usual incremental update with the server after that to be complete.

The server would update the bundle used to bootstrap clone clients periodically in order to keep the incrementals to the minimum, and would make sure their bitmap is anchored at the tips of bundles to minimize the object counting load during the incremental phase.

I think "repo" used by folks who do AOSP does something similar to that by scripting around "git clone". I'd imagine that they would be happy to see if "git clone" did all that inside.

On Mon, Feb 16, 2015 at 10:43 AM, Junio C Hamano <gitster@pobox.com> wrote:

Yes, the "repo" tool used by Android uses curl to download a previously cached $URL/clone.bundle using resumable HTTP. For Android the file is only updated ~every 6 months at major releases and is easily cached by CDNs and HTTP proxy servers.

This is spooled to a temporary file on disk then unpacked using `git fetch $path/clone.bundle refs/heads/*:refs/remotes/origin/*`. Afterwards a normal git fetch is run to bring the new clone current with the server, picking up any delta that happened since the bundle was created and cached.

The Android Git servers at android.googlesource.com just recognize */clone.bundle GET requests and issue 302 redirects to the CDN farm that actually stores and serves the precreated bundle files.

We really want to see this in stock git clone for HTTP transports, as other projects like Chromium want to use it for their ~3 GiB repository. Being able to build the bulk of the repo every few months and serve it out using a CDN to bootstrap new clients would really help developers on slower or flaky network connections.

On Mon, Feb 16, 2015 at 10:47 PM, Jeff King <peff@peff.net> wrote:

It's usually _not_ the same. I tried when I wanted to produce stable packs. The first condition is single-threaded pack-objects. Otherwise thread scheduler could make object order unpredictable.

On Tue, Feb 17, 2015 at 06:16:39AM +0700, Duy Nguyen wrote:

True. If you keep your server repositories fully packed, that eliminates the delta search (and/or makes it feasible to turn pack.threads to 1 to make it deterministic). But any change in the repository (e.g., somebody else pushing, even to a ref you are not fetching) can cause unexpected changes in the bytes.

-Peff