Re: Change set based shallow clone

From: Jakub Narebski <jnareb@gmail.com>
Date: Sep 7, 2006, 22:40 UTC
Message-ID: <edq74k$cuu$1@sea.gmane.org>
In-Reply-To: <7vpse7tjp0.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano wrote:

Show 30 quoted lines

> One way to do so is to send grafts information from downloader
> to uploader.  If the uploader _knows_ that the altered history
> ends at the leftmost '*' commit on the mainline, then it can 
> take it into account the fact that the downloader does not have
> commit 'F'.  That, however, introduces another problem.  Where
> should it stop?  Obviously X needs to be sent, so is X^, but
> how do we know which 'x' commit to stop at?  Do we record the
> initial cut-off criteria (remember, we started the clone with
> 5-commit cutoff) somewhere in the downloader's repository and
> send that to the uploader so that the uploader can apply the
> same rule to include only 5 commits from the new side branch?
> What happens if there are less than 5 commits on that new side
> branch?  Would we end up including 'F', which the downloader
> specifically did not want when making this shallow clone
> initially?
> 
> I won't go into the details, but when you think about what needs
> to happen when fetching _from_ a shallow clone (i.e. the
> uploader side is incomplete), your head will explode ;-).  It is
> solvable in the same sense that you can solve the previous
> "fetching to update" problem by trying to define a reasonable
> semantics to the operation by answering the questions I posed in
> the above paragraph (which obviously is no way an exhaustive
> set), but the result will be quite complex.  It would involve
> sending graft information both from uploader and downloader
> (after all the downloader side can also be shallow but with
> different cut-off points from the uploader) and somehow coming
> up with the intersection of both to arrive at a shared view of
> altered history before starting the traversal to find what to
> send.

The proposed solution was to send graft information and cutoff from downloader to uploader, coming up with the effective graft points which would be intersection of downloader and uploader grafts[*1*], and then use this intersection as graft information when calculating what to send.

With sparse clone we would have:

 #---o---#---o---o---*---*---*---*---*
          \      ^              /    ^ 
           \   HEAD~5          /    HEAD
            \                 /
             o---o---*---*---*
                 ^           ^
             HEAD^^2~3     HEAD^^2

where # and * are the commit which the downloader has (# are additional commits for sparse rather thatn shallow clone).

                 x---x---x---x---x---x
                /                     \
               /                       \
              /                         \
 #---o---#---F---o---*---*---*---*---H---x---X
          \                     /
           \                   /
            \                 /
             o---o---*---*---*

Now, when we are shallow fetching, we should have remembered somewhere the cutoff used (or use the same cutoff). So we sould get then

                 x---*---*---*---*---*
                /                     \
               /                       \
              /                         \
 #---o---#---#---o---*---*---*---*---*---*---*
          \                     /
           \                   /
            \                 /
             o---o---*---*---*

Footnotes: [*1*] It would be some kind of graph intersection. Note that the repository we clone from might be shallow clone, shallower in parts than our repository, or might be repository with historic repository grafted on (grafts adding history, not simplyfying it).

[*2*] I agree that shallow/sparse clone is hard. Lazy clone (or remote alternatives) is also hard: when we do download objects, do we download-ahead, do we cache downloaded object or move them to local repository, how often we clean cache etc.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git