Multi-head fetch proposal

Multi-head fetch proposal

[Johannes Schindelin]

Hi,

I reported a while ago that a fetch downloaded objects which were already 
in the repository. While that was true, it was not the whole truth: This 
only happened with multi-head fetch.

As far as I can tell, what happened was this:

- fetch-pack connected to the server
- it asked correctly for the remote refs
- it then opened a (local) pipe to git-rev-list
- it sent quite a few refs from that pipe over the wire
- on the other side, upload-pack marked these refs as "fetcher got those"
- since upload-pack has a limit on that list (only 16) it soon said STFU 
- it turned out that quite a few common refs were not yet marked
- so upload-pack would upload these

The reason is that git-rev-list would happily output parents of refs 
which were already acknowledged by upload-pack to be common refs.

I just sent out a patch which makes this irrelevant for the case that most 
or all of these heads are already fetched.

Now, to really solve the multi-head problem, which really is the problem 
"how to find the edges of the common commits", I propose the following:

For each remote ref known to be not in the local repository, find the 1st, 
2nd, 4th, 8th, ... parents. Send these to upload-pack to be marked. For 
each ack'ed ref (i.e. remote side also has it), do a binary search to find 
the edge (i.e. the youngest common ref) on that DAG branch.

(To ease the burden on the server side, one coul mark only the edges 
as stop gaps for upload-pack. However, it might make things too 
complicated.)

Of course, the trick is to do that asynchronously, so that the network 
bandwidth is used optimally. This means that not each ack'ed ref 
leads to a binary search, but only those refs where no descendant was 
ack'ed.

BTW this does not need any change of the protocol. In fact, it only needs 
a change to fetch-pack.

I'd also increase MAX_HAS in upload-pack.

Ciao,
Dscho

Re: Multi-head fetch proposal

[Junio C Hamano]

I was wondering why I always end up fetching 35 or so objects
when I ask master, maint and pu from my public repository, and
wanted to spend today digging on this one.  Instead I ended up
wasting the day on something else (I just sent it out), but I am
glad you were looking into it.

Of course, with your patch the problem does not happen anymore.