threads / discuss / 40067

pack negotiation algorithm between 2 share-nothing repos

Subject: pack negotiation algorithm between 2 share-nothing repos

## tl;dr

3 messages between Aug 12, 2015 and Aug 26, 2015.

replies: 2people: 2as markdown or json

Duy Nguyen· Aug 12, 2015, 11:27 UTC · lore

This is a corner case that has a real use case:

git clone linux-2.6.git cd linux-2.6 git remote add history git-history.git git fetch history # graft graft graft

Because history.gi and linux-2.6.git have nothing in common, the server side keeps asking for more "have"s and the client keeps sending in "git fetch history". Negotiation phase takes longer than my patience so I abort it, hack git to send no "have"s and retry.

I know this is a corner case, but because it has a valid use case, maybe we should do something about it. Immediate reaction is to add an option to send no "have"s. But maybe you guys have better ideas.

PS. I know i'm behind my git inbox. Looking into it soon.

-- 
Duy

Junio C Hamano· Aug 12, 2015, 15:55 UTC · re: Duy Nguyen · lore

Re: pack negotiation algorithm between 2 share-nothing repos

Duy Nguyen <pclouds@gmail.com> writes:

> I know this is a corner case, but because it has a valid use case,
> maybe we should do something about it. Immediate reaction is to add an
> option to send no "have"s. But maybe you guys have better ideas.

This and similar corner cases were discussed in very early days of Git.

One interesting idea floated back then but was not pursued was to dig and send have's sparsely and then back up. Instead of digging and sending _all_ commits in a contiguous history, after sending the tip, you skip the commits from the history before sending the next one, and progressively make the skipping larger (e.g. Fibonacci, or exponential). You need to remember what you sent and for each of what you sent its topologically-oldest descendant you sent earlier that you heard the other side does not have.

Then, when you get an Ack, you know a stretch of history between a commit that is known to be common (i.e. the one you heard an Ack just now) and its descendant that is known only to you (i.e. the topologically-oldest one you remember that you did send and they didn't say is common). At that point, you and the other end can bisect that range.

Junio C Hamano· Aug 26, 2015, 16:49 UTC · re: Junio C Hamano · lore

Re: pack negotiation algorithm between 2 share-nothing repos

Junio C Hamano <gitster@pobox.com> writes:

Show 24 quoted lines

> Duy Nguyen <pclouds@gmail.com> writes:
>
>> I know this is a corner case, but because it has a valid use case,
>> maybe we should do something about it. Immediate reaction is to add an
>> option to send no "have"s. But maybe you guys have better ideas.
>
> This and similar corner cases were discussed in very early days of
> Git.
>
> One interesting idea floated back then but was not pursued was to
> dig and send have's sparsely and then back up.  Instead of digging
> and sending _all_ commits in a contiguous history, after sending the
> tip, you skip the commits from the history before sending the next
> one, and progressively make the skipping larger (e.g. Fibonacci, or
> exponential).  You need to remember what you sent and for each of
> what you sent its topologically-oldest descendant you sent earlier
> that you heard the other side does not have.
>
> Then, when you get an Ack, you know a stretch of history between a
> commit that is known to be common (i.e. the one you heard an Ack
> just now) and its descendant that is known only to you (i.e. the
> topologically-oldest one you remember that you did send and they
> didn't say is common).  At that point, you and the other end can
> bisect that range.

If anybody is interested, here is a good place to start:

http://thread.gmane.org/gmane.comp.version-control.git/96149/focus=102485

[Cc'ed Stefan as I think he was collecting possible enhancement to put in the protocol v2].