Re: Balanced packing strategy

From: Petr Baudis <pasky@suse.cz>
Date: Nov 13, 2005, 11:00 UTC
Message-ID: <20051113110024.GM30496@pasky.or.cz>
In-Reply-To: <7vveyxcm3p.fsf@assigned-by-dhcp.cox.net>

Dear diary, on Sun, Nov 13, 2005 at 03:34:02AM CET, I got a letter where Junio C Hamano <junkio@cox.net> said that...

Show 8 quoted lines

> Craig Schlenter <craig@codefountain.com> writes:
> 
> > Does the pack index file contain enough information to enable a client
> > to send http byte range requests to grab individual objects from a pack?
> > It does seem to store object offsets...
> 
> Yes, it is certainly doable; there is enough information.  I am
> not sure if it is worth the complexity, though.

I think we need either the balanced packing or this.

Show 6 quoted lines

> Many objects are stored delitified, so your byte range requests
> would return delta and base object name.  After you read what
> was returned and find out the base object name, you would need
> to get it, which can be another delta against its base object.
> This would make tangling a delta chain would become a serialized
> sequence of requests.

Sort the objects topologically, then get everything from the old heads on. Obviously, this will not work so well when we get multiple heads in single pack, but either don't do that (would it be actually so bad if we would create one pack per head?), or:

  (i) objects are topologically sorted
  (ii) objects introduced by a commit/tree are right after the commit or
       tree in the pack file
  (iii) index file contains parents list for each commit

This way, you can possibly run through the gaps, or if the gap is big enough, restart the request. You still will miss objects introduced by commits in different branches, but in case of trees you can slurp the trees at once again, and pick the individual objects otherwise; while doing this second pass, you can apply the gaps strategy again.

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
VI has two modes: the one in which it beeps and the one in which
it doesn't.