threads / discuss / 4506

'sparse' clone idea

Subject: 'sparse' clone idea

## tl;dr

3 messages between Jun 14, 2006 and Jun 14, 2006.

replies: 2people: 2as markdown or json

Jakub Narebski· Jun 14, 2006, 08:23 UTC · lore

I wonder if 'sparse clone' idea described below would avoid the most difficult part of 'shallow clone' idea, namely the [sometimes] need to un-cauterize history. See: (<7vac8lidwi.fsf@assigned-by-dhcp.cox.net>).

'sparse clone' begins like 'shallow clone': full history is copied down to specified point of history (cut-off or cauterization point for shallow clone), but instead of cauterizing the history from that point downwards, the history is simplified using grafts.

In the sparse part we need:
 * all commits pointed by tags (if we clone/copy tags) 
   and other refs (if we clone/copy those tags)
 * merge bases for all commits in full, and in the sparse part,
   _including_ merge bases themselves
 * all roots

Commits in sparse part would be connected like in original history, only skipping "uniteresting" commits.

Thoughts? Comments?
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
Johannes Schindelin· Jun 14, 2006, 09:20 UTC · re: Jakub Narebski · lore

Re: 'sparse' clone idea

Hi,
On Wed, 14 Jun 2006, Jakub Narebski wrote:
> I wonder if 'sparse clone' idea described below would avoid the most
> difficult part of 'shallow clone' idea, namely the [sometimes] need to
> un-cauterize history. See: (<7vac8lidwi.fsf@assigned-by-dhcp.cox.net>).

I do not think that is the hardest problem. The hardest thing is to tell the server in an efficient manner which objects we have.

Example:
A - B - C - D
    ^ cutoff
        ^ current HEAD

Suppose B is your fake root, C is your HEAD, you want to fetch D. Now, make it a difficult example: both A and D contain a certain blob Z, but neither B nor C do. You have to tell the server _in an efficient manner_ to send Z also.

And by efficient manner I mean: you may not bring the server down just because 5 people with shallow clones decide to fetch from it.

Show 10 quoted lines
> 'sparse clone' begins like 'shallow clone': full history is copied down to
> specified point of history (cut-off or cauterization point for shallow
> clone), but instead of cauterizing the history from that point downwards,
> the history is simplified using grafts.
> 
> In the sparse part we need:
>  * all commits pointed by tags (if we clone/copy tags) 
>    and other refs (if we clone/copy those tags)
>  * merge bases for all commits in full, and in the sparse part,
>    _including_ merge bases themselves

Hmmm. You cannot know _all_ merge bases beforehand, because you do not decide where other people fork off.

>  * all roots
Why?
> Commits in sparse part would be connected like in original history, only
> skipping "uniteresting" commits.

Interesting idea, though I do not think it solves the most pressing problems we have with shallow clones.

Ciao, Dscho

P.S.: I think the problems of a lazy clone are much easier to solve...
Jakub Narebski· Jun 14, 2006, 09:44 UTC · re: Johannes Schindelin · lore

Re: 'sparse' clone idea

Johannes Schindelin wrote:
Show 22 quoted lines
> On Wed, 14 Jun 2006, Jakub Narebski wrote:
> 
>> I wonder if 'sparse clone' idea described below would avoid the most
>> difficult part of 'shallow clone' idea, namely the [sometimes] need to
>> un-cauterize history. See: (<7vac8lidwi.fsf@assigned-by-dhcp.cox.net>).
> 
> I do not think that is the hardest problem. The hardest thing is to tell 
> the server in an efficient manner which objects we have.
> 
> Example:
> 
> A - B - C - D
>     ^ cutoff
>         ^ current HEAD
> 
> Suppose B is your fake root, C is your HEAD, you want to fetch D. Now, 
> make it a difficult example: both A and D contain a certain blob Z, but 
> neither B nor C do. You have to tell the server _in an efficient manner_ 
> to send Z also.
> 
> And by efficient manner I mean: you may not bring the server down just 
> because 5 people with shallow clones decide to fetch from it.

Nah, that I think is solved. Check the mentioned post by Junio C Hamano in the "Re: Figured out how to get Mozilla into git" post:

 http://permalink.gmane.org/gmane.comp.version-control.git/21603

(although it would need extension to the git protocol). Client and server do graft exchange both ways, limiting the commit ancestry graph the both ends walk to the intersection of the fake view of the ancestry graph both ends have. Then server uses those virtual grafts to calculate which objects to send.

The rest is done (or should be done) by history grafting code.
Show 5 quoted lines
>>  * merge bases for all commits in full, and in the sparse part,
>>    _including_ merge bases themselves
> 
> Hmmm. You cannot know _all_ merge bases beforehand, because you do not 
> decide where other people fork off.
By all merge bases I mean merge bases for all commits in full part, merge
bases for all commits in full part and commits pointed by tags in sparse
part, merge bases for all commits in full part and tagged in sparse part
and merge bases in sparse part etc. recursively.
 
>>  * all roots
> 
> Why?
Just in case, as an ultimate merge bases.
 
> P.S.: I think the problems of a lazy clone are much easier to solve...

I still think that the correct idea for the lazy clone is to have soft grafts, so you have to solve at least part of shallo clone/sparse clone problems first.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

← back to recent threads