Git packs friendly to block-level deduplication

If you have a bunch of git repositories cloned of the same project on the same filesystem, it would be nice of the packs that are produced would be friendly to block-level deduplication.

This would save space, and the blocks would be more likely to be in cache when you access them, likely speeding up git operations even if the packing itself is less efficient.

Here's a hacky one-liner that clones git/git and peff/git (almost the same content) and md5sums each 4k packed block, and sort | uniq -c's them to see how many are the same:

    (
       cd /tmp &&
       rm -rf git*;
       git clone --reference ~/g/git --dissociate git@github.com:git/git.git git1 &&
       git clone --reference ~/g/git --dissociate git@github.com:peff/git.git git2 &&
       for repo in git1 git2
       do
           (
               cd $repo &&
               git repack -A -d --max-pack-size=10m
           )
       done &&
       parallel "perl -MDigest::MD5=md5_hex -wE 'open my \$fh, q[<], shift; my \$s; while (read \$fh, \$s, 2**12) { say md5_hex(\$s) }' {}" ::: \
           $(find /tmp/git*/.git/objects/pack -type f)|sort|uniq -c|sort -nr|awk '{print $1}'|sort|uniq -c|sort -nr
    )

This produces a total of 0 blocks that are the same. If after the repack we throw this in there after the repack:

    echo 5be1f00a9a | git pack-objects --no-reuse-delta --no-reuse-object --revs .git/objects/pack/manual

Just over 8% of the blocks are the same, and of course this pack entirely duplicates the existing packs, and I don't know how to coerce repack/pack-objects into keeping this manual-* pack and re-packing the rest, removing any objects that exist in the manual-* pack.

Documentation/technical/pack-heuristics.txt goes over some of the ideas behind the algorithm, and Junio's 1b4bb16b9e ("pack-objects: optimize "recency order"", 2011-06-30) seems to be the last major tweak to it.

I couldn't find any references to someone trying to get this particular use-case working on-list. I.e. to pack different repositories with a shared history in such a way as to optimize for getting the most amount of identical blocks within packs.

It should be possible to produce such a pack, e.g. by having a repack mode that would say:

 1. Find what the main branch is
 2. Get its commits in reverse order, produce packs of some chunk-size
    of commit batches.
 3. Pack all the remaining content

This would delta much less efficiently, but as noted above the block-level deduplication might make up for it, and in any case some might want to use less disk space.

Has anyone here barked up this tree before? Suggestions? Tips on where to start hacking the repack code to accomplish this would be most welcome.

On Wed, Jan 24, 2018 at 11:03:47PM +0100, Ævar Arnfjörð Bjarmason wrote:

FWIW, I sidestep the problem entirely by using alternatives.

Mike

Mike Hommey <mh@glandium.org> writes:

That's a funny way to use the word "side-step", I would say, as the alternate object store support is there exactly for this use case.

On Wed, Jan 24, 2018 at 02:23:57PM -0800, Junio C Hamano wrote:

It's footgunny, though.

Mike

On Wed, Jan 24 2018, Junio C. Hamano jotted:

Things you can't do with alternates that block-level de-duplication gives you:

 1. Your filesystem may be mounted from some NFS host that does
    block-level deduplication internally against other content you don't
    have permission to access, think the /home of a bunch of dev VMs you
    know will have the same repos cloned (along with most of the same FS
    content, e.g. the OS).

    In this case the storage can de-duplicate blocks purely as an
    implementation without git knowing about it, as long as git (or any
    other program using the FS) can be coerced into writing the same
    blocks other gits on other machines write, at least most of the
    time.

 2. Ditto NFS, but e.g. chroot'd /home on a local non-NFS.

 3. Even if the repos are all on the same host they may just be ad-hoc
    cloned in /home by different users, it's easy to write something in
    /etc/gitconfig to give them the same repack settings, less so to
    maintain some git-clone wrapper that implictily adds --reference
    (they'll not know, or forget) to all clones, or goes hunting around
    for checkouts and adding alternates after the fact.

 4. With alternates you always need to maintain some blessed "clone from
    this" repo that can't go away least everything cloned from it become
    corrupt and needs manual repair. If you're aiming to just save
    storage block-level deduplication may be a better trade-off.

Also once you clone with --reference doesn't the local clone only add new objects as you "git fetch", never pruning those if the same objects appear in the alternate later on, or am I misremembering things?

I mainly have use-case #1 & #3, although they could both be made to use alternates with some hassle (e.g. for #1 exposing a separate read-only copy of "these are alternates" to each VM) it seemed worthwhile to see if repack could be made to be more block-level deduplication friendly, as deploying that is easier.

Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Fwiw, I currently get around this when mirroring by having all the remotes I care about mirrored to a "hidden" root repo, and having other repos point to the hidden root objects via object/info/alternates. Not that great for usability and probably potentially racy...

The Debian version of gzip(1) has an --rsyncable patch which might be of help.

On Wed, Jan 24, 2018 at 2:03 PM, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

<snip>

Does this overlap with the desire to have resumable clones? I'm curious what would happen if you did the same experiment with two separate clones of git/git, cloned one right after the other so that hopefully the upstream git/git didn't receive any updates between your two separate clones. (In other words, how much do packfiles differ in practice for different packings of the same data?)

On Wed, Jan 24 2018, Elijah Newren jotted:

If you clone git/git from Github twice in a row you get the exact same pack, and AFAICT this is true of git in general (but may change between versions).

If you make a local commit to that, copy the dir, and repack -A -d you get the exact same packs again.

If you then make just one local commit to one copy (even with --allow-empty) and repack, you get entirely differnt packs, in my test 2.5% of the blocks remain the same.

Obviously you could pack *that* new content incrementally and keep the existing pack, but that won't help you with de-duping the initially cloned data, which is what matters.

On Thu, Jan 25, 2018 at 12:06:59AM +0100, Ævar Arnfjörð Bjarmason wrote:

That's definitely not guaranteed. It _tends_ to be the case over the short term because we use --threads=1 on the server. But it may differ if:

  - we repack on the server, which we do based on pushes

  - somebody pushes, even to another fork. The exact results depend
    on the packs in which we find the objects, and a new push may
    duplicate some existing objects but with a different representation,
    (e.g., a different delta base).

I'm actually interested in adding an etags-like protocol extension that would work something like this:

  - server says "here's a pack, and its opaque tag is XYZ".

  - on resume, the client says "can I resume pack with tag XYZ"?

  - the server then decides if the on-disk state is sufficient for it to
    agree to recreate XYZ (e.g., number and identity of packs). If yes,
    then it resumes. If no, then it says "nope" and the two sides go
    through a normal fetch again.

The important thing is that the tag is opaque to the client. So a stock implementation could use the on-disk state to decide. But a server could choose to cache the packs it sends for a period of time (especially if the client hangs up before we've sent the whole thing). We already do this to a limited degree at GitHub in order to efficiently serve multiple clients simultaneously fetching the same pack (e.g., imagine a fleet of AWS machines all triggering "git fetch" at once).

I think that's a tangent to what you're looking for in this thread, though.

-Peff

On Wed, Jan 24, 2018 at 11:03:47PM +0100, Ævar Arnfjörð Bjarmason wrote:

I think touching manual-*.keep would do what you want (followed by "repack -ad" to drop the duplicate objects).

You may also want to use "--threads=1" to avoid non-determinism in the generated packs. In theory, both repos would then produce identical base packs, though it does not seem to do so in practice (I didn't dig in to what the different may be).

I don't recall any discussion on this topic before.

I think you're fighting against two things here:

  - the order in which we find deltas; obviously a delta of A against B
    is quite different than B against A

  - the order of objects written to disk

Those mostly work backwards through the history graph, so adding new history on top of old will cause changes at the beginning of the file, and "shift" the rest so that the blocks don't match.

If you reverse the order of those, then the shared history is more likely to provide a common start to the pack. See compute_write_order() and the final line of type_size_sort().

We do something a bit like this at GitHub. There we have a single pack holding all of the objects for many forks. So the deduplication is done already, but we want to avoid deltas that cross fork boundaries (since they mean throwing away the delta and recomputing from scratch when somebody fetches). And then we write the result in layers, although right now there are only 2 layers (some "base" fork gets all of its objects, and then everybody else's objects are dumped on top).

I suspect some of the same concepts could be applied. If you're interested in playing with it, I happened to extract it into a single patch recently (it's on my list of "stuff to send upstream" but I haven't gotten around to polishing it fully). It's the "jk/delta-islands" branch of https://github.com/peff/git (which I happen to know you already have a clone of ;) ).

-Peff

On Wed, Jan 24 2018, Jeff King jotted:

Thanks, that got the number of identical blocks just north of 15%...

..and north of 20% with --threads=1.

I'll have to poke at what compute_write_order() is doing, but FWIW this to type_size_sort() got shared blocks down to 3%:

    diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
    index 81ad914cfc..c9ada1bd1c 100644
    --- a/builtin/pack-objects.c
    +++ b/builtin/pack-objects.c
    @@ -1764,7 +1764,7 @@ static int type_size_sort(const void *_a, const void *_b)
                    return -1;
            if (a->size < b->size)
                    return 1;
    -       return a < b ? -1 : (a > b);  /* newest first */
    +       return b < a ? -1 : (b > a);  /* newest first */
     }

     struct unpacked {

Thanks. I'll look into that, although the above results (sans hacking on the core pack-objects logic) suggest that even once I create an island I'm getting at most 20%.

On Thu, Jan 25, 2018 at 01:03:25AM +0100, Ævar Arnfjörð Bjarmason wrote:

I think it may be worth figuring out where the two differ. With --no-reuse-object and --no-reuse-delta, I'd think that the pack generated for a particular apex commit would be totally deterministic, regardless of other objects available in the repo. But it's not for some reason.

-Peff

On Wed, Jan 24, 2018 at 07:10:15PM -0500, Jeff King wrote:

I think I see it. If I compare the objects in pack-order of the two packs:

  diff -u <(git show-index <$one | sort -n) <(git show-index <$two | sort -n)

I get:

  6281 fac64e011f1b1ecabcccf7ad2511efcac3e26bdc (9381a4f9)
  6585 59c276cf4da0705064c32c9dba54baefa282ea55 (1b02a1c0)
  6869 8279ed033f703d4115bee620dccd32a9ec94d9aa (ca7acf33)
 -7042 298d861208d71089dd308761ae96738e81ad3e68 (135aefd7)
 -7222 ea7b5de1c1187294d3d4dca93b129e049ca7ca76 (3708bbfc)
 -7512 b6947af2294ea0c814f5b4cb8737c782895519b2 (719fad14)
 -8004 e26f7f19b6c7485f04234946a59ab8f4fd21d6d1 (59127876)
 -8826 2512f15446149235156528dafbe75930c712b29e (fc72468e)
  [...]
 +7042 2512f15446149235156528dafbe75930c712b29e (fc72468e)
 +7215 c6c75c93aaeb97bab6fd25b672a641c84dd85d59 (68fe0b8d)
 +7391 36438dc19dd2a305dddebd44bf7a65f1a220075b (c424e726)
 +7565 1eaabe34fc6f486367a176207420378f587d3b48 (4a27450b)

So the write order differs; one pack stuck 2512f15446 much earlier.

That's probably due to this line from compute_write_order():

     /*
      * Mark objects that are at the tip of tags.
      */
     for_each_tag_ref(mark_tagged, NULL);

If I remove that line, then your manual pack (with --threads=1) gives me identical packs for each repo.

And if I then mark each with a .keep, then "git repack -ad" to remove duplicates, your block-dedup check yields:

   17742 2
    1939 1

which is 90%, and about what I'd expect between those two repos. So I think the idea of computing a "base" pack (either as a separate pack, or as a layer in the pack) is a viable strategy.

-Peff