Re: [PATCH 09/16] documentation: add documentation for the bitmap format

From: Jeff King <peff@peff.net>
Date: Jun 26, 2013, 05:11 UTC
Message-ID: <20130626051117.GB26755@sigill.intra.peff.net>
In-Reply-To: <CAFFjANRwBBcORhu4mwjESBfr4GJ3zDrgYvUhY=VxK9abv7k2MA@mail.gmail.com>

On Tue, Jun 25, 2013 at 09:33:11PM +0200, Vicent Martí wrote:

Show 11 quoted lines

> > One way we side-stepped the size inflation problem in JGit was to only
> > use the bitmap index information when sending data on the wire to a
> > client. Here delta reuse plays a significant factor in building the
> > pack, and we don't have to be as accurate on matching deltas. During
> > the equivalent of `git repack` bitmaps are not used, allowing the
> > traditional graph enumeration algorithm to generate path hash
> > information.
> 
> OH BOY HERE WE GO. This is worth its own thread, lots to discuss here.
> I think peff will have a patchset regarding this to upstream soon,
> we'll get back to it later.

We do the same thing (only use bitmaps during on-the-wire fetches). But there a few problems with assuming delta reuse.

For us (GitHub), the foremost one is that we pack many "forks" of a repository together into a single packfile. That means when you clone torvalds/linux, an object you want may be stored in the on-disk pack with a delta against an object that you are not going to get. So we have to throw out that delta and find a new one.

I'm dealing with that by adding an option to respect "islands" during packing, where an island is a set of common objects (we split it by fork, since we expect those objects to be fetched together, but you could use other criteria). The rule is that an object cannot delta against another object that is not in all of its islands. So everybody can delta against shared history, but objects in your fork can only delta against other objects in the fork. You are guaranteed to be able to reuse such deltas during a full clone of a fork, and the on-disk pack size does not suffer all that much (because there is usually a good alternate delta base within your reachable history).

So with that series, we can get good reuse for clones. But there are still two cases worth considering:

  1. When you fetch a subset of the commits, git marks only the edges as
     preferred bases, and does not walk the full object graph down to
     the roots. So any object you want that is delta'd against something
     older will not get reused. If you have reachability bitmaps, I
     don't think there is any reason that we cannot use the entire
     object graph (starting at the "have" tips, of course) as preferred
     bases.

  2. The server is not necessarily fully packed. In an active repo, you
     may have a large "base" pack with bitmaps, with several recently
     pushed packs on top. You still need to delta the recently pushed
     objects against the base objects.

I don't have measurements on how much the deltas suffer in those two cases. I know they suffered quite badly for clones without the name hashes in our alternates repos, but that part should go away with my patch series.

-Peff