Re: Resumable clone/Gittorrent (again)

From: Sam Vilain <sam@vilain.net>
Date: Jan 13, 2011, 23:40 UTC
Message-ID: <4D2F8D7E.6030305@vilain.net>
In-Reply-To: <AANLkTi=3ikJ2UNNCW582CT7LQ7o2DBZ1hXJhPfMUNbKk@mail.gmail.com>

On 14/01/11 00:39, Luke Kenneth Casson Leighton wrote:

Show 14 quoted lines

> On Sun, Jan 9, 2011 at 5:48 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> On Sun, Jan 9, 2011 at 8:55 PM, Luke Kenneth Casson Leighton
>> <luke.leighton@gmail.com> wrote:
>>>  you still have to come up with a mapping from "chains" to "pieces".
>>> in the bittorrent protocol the mapping is done *entirely* implicitly
>>> and algorithmically.
>> Given a commit SHA-1, the mapping can be done algorithmically because
>> the graph from the commit tip is fixed. Perhaps not mapping all at
>> once, but as you have more pieces in the graph, you can map more.
>  you're _sure_ about this?  what happens when new commits get added,
> and change that graph?  are you _certain_ that you can write an
> algorithm which is capable of generating exactly the same mapping,
> even as more commits are added to the repository being mirrored, or,
> does that situation not matter?

For a given set of start and end points, and a given sort algorithm, walking the commit tree can yield deterministic results.

You need to first make sure topological sanity prevails, then order by commit date where there are ties. git rev-list --date-order does this. There is the possibility of commits with the same commit date, so if you need to be really particular you can tie break on those, too.

Did you look at any of the previous research I linked to before?

Sam