{"thread":{"id":"47684","subject":"Git packs friendly to block-level deduplication","startedAt":"2018-01-24T22:03:56Z","lastAt":"2018-01-25T00:29:49Z","messageCount":13,"participants":["Ævar Arnfjörð Bjarmason","Mike Hommey","Junio C Hamano","Eric Wong","Elijah Newren","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"337325","messageId":"87bmhiykvw.fsf@evledraar.gmail.com","threadId":"47684","inReplyTo":null,"subject":"Git packs friendly to block-level deduplication","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-24T22:03:47Z","receivedAt":"2018-01-24T22:03:56Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"If you have a bunch of git repositories cloned of the same project on\nthe same filesystem, it would be nice of the packs that are produced\nwould be friendly to block-level deduplication.\n\nThis would save space, and the blocks would be more likely to be in\ncache when you access them, likely speeding up git operations even if\nthe packing itself is less efficient.\n\nHere's a hacky one-liner that clones git/git and peff/git (almost the\nsame content) and md5sums each 4k packed block, and sort | uniq -c's\nthem to see how many are the same:\n\n (\n cd /tmp &&\n rm -rf git*;\n git clone --reference ~/g/git --dissociate git@github.com:git/git.git git1 &&\n git clone --reference ~/g/git --dissociate git@github.com:peff/git.git git2 &&\n for repo in git1 git2\n do\n (\n cd $repo &&\n git repack -A -d --max-pack-size=10m\n )\n done &&\n parallel \"perl -MDigest::MD5=md5_hex -wE 'open my \\$fh, q[<], shift; my \\$s; while (read \\$fh, \\$s, 2**12) { say md5_hex(\\$s) }' {}\" ::: \\\n $(find /tmp/git*/.git/objects/pack -type f)|sort|uniq -c|sort -nr|awk '{print $1}'|sort|uniq -c|sort -nr\n )\n\nThis produces a total of 0 blocks that are the same. If after the repack\nwe throw this in there after the repack:\n\n echo 5be1f00a9a | git pack-objects --no-reuse-delta --no-reuse-object --revs .git/objects/pack/manual\n\nJust over 8% of the blocks are the same, and of course this pack\nentirely duplicates the existing packs, and I don't know how to coerce\nrepack/pack-objects into keeping this manual-* pack and re-packing the\nrest, removing any objects that exist in the manual-* pack.\n\nDocumentation/technical/pack-heuristics.txt goes over some of the ideas\nbehind the algorithm, and Junio's 1b4bb16b9e (\"pack-objects: optimize\n\"recency order\"\", 2011-06-30) seems to be the last major tweak to it.\n\nI couldn't find any references to someone trying to get this particular\nuse-case working on-list. I.e. to pack different repositories with a\nshared history in such a way as to optimize for getting the most amount\nof identical blocks within packs.\n\nIt should be possible to produce such a pack, e.g. by having a repack\nmode that would say:\n\n 1. Find what the main branch is\n 2. Get its commits in reverse order, produce packs of some chunk-size\n of commit batches.\n 3. Pack all the remaining content\n\nThis would delta much less efficiently, but as noted above the\nblock-level deduplication might make up for it, and in any case some\nmight want to use less disk space.\n\nHas anyone here barked up this tree before? Suggestions? Tips on where\nto start hacking the repack code to accomplish this would be most\nwelcome.\n"},{"id":"337326","messageId":"20180124221932.v6up7j67llwhjox4@glandium.org","threadId":"47684","inReplyTo":"87bmhiykvw.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2018-01-24T22:19:34Z","receivedAt":"2018-01-24T22:19:43Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Wed, Jan 24, 2018 at 11:03:47PM +0100, Ævar Arnfjörð Bjarmason wrote:\n> If you have a bunch of git repositories cloned of the same project on\n> the same filesystem, it would be nice of the packs that are produced\n> would be friendly to block-level deduplication.\n> \n> This would save space, and the blocks would be more likely to be in\n> cache when you access them, likely speeding up git operations even if\n> the packing itself is less efficient.\n> \n> Here's a hacky one-liner that clones git/git and peff/git (almost the\n> same content) and md5sums each 4k packed block, and sort | uniq -c's\n> them to see how many are the same:\n> \n> (\n> cd /tmp &&\n> rm -rf git*;\n> git clone --reference ~/g/git --dissociate git@github.com:git/git.git git1 &&\n> git clone --reference ~/g/git --dissociate git@github.com:peff/git.git git2 &&\n> for repo in git1 git2\n> do\n> (\n> cd $repo &&\n> git repack -A -d --max-pack-size=10m\n> )\n> done &&\n> parallel \"perl -MDigest::MD5=md5_hex -wE 'open my \\$fh, q[<], shift; my \\$s; while (read \\$fh, \\$s, 2**12) { say md5_hex(\\$s) }' {}\" ::: \\\n> $(find /tmp/git*/.git/objects/pack -type f)|sort|uniq -c|sort -nr|awk '{print $1}'|sort|uniq -c|sort -nr\n> )\n> \n> This produces a total of 0 blocks that are the same. If after the repack\n> we throw this in there after the repack:\n> \n> echo 5be1f00a9a | git pack-objects --no-reuse-delta --no-reuse-object --revs .git/objects/pack/manual\n> \n> Just over 8% of the blocks are the same, and of course this pack\n> entirely duplicates the existing packs, and I don't know how to coerce\n> repack/pack-objects into keeping this manual-* pack and re-packing the\n> rest, removing any objects that exist in the manual-* pack.\n> \n> Documentation/technical/pack-heuristics.txt goes over some of the ideas\n> behind the algorithm, and Junio's 1b4bb16b9e (\"pack-objects: optimize\n> \"recency order\"\", 2011-06-30) seems to be the last major tweak to it.\n> \n> I couldn't find any references to someone trying to get this particular\n> use-case working on-list. I.e. to pack different repositories with a\n> shared history in such a way as to optimize for getting the most amount\n> of identical blocks within packs.\n> \n> It should be possible to produce such a pack, e.g. by having a repack\n> mode that would say:\n> \n> 1. Find what the main branch is\n> 2. Get its commits in reverse order, produce packs of some chunk-size\n> of commit batches.\n> 3. Pack all the remaining content\n> \n> This would delta much less efficiently, but as noted above the\n> block-level deduplication might make up for it, and in any case some\n> might want to use less disk space.\n> \n> Has anyone here barked up this tree before? Suggestions? Tips on where\n> to start hacking the repack code to accomplish this would be most\n> welcome.\n\nFWIW, I sidestep the problem entirely by using alternatives.\n\nMike\n"},{"id":"337327","messageId":"xmqq607qc2v6.fsf@gitster.mtv.corp.google.com","threadId":"47684","inReplyTo":"20180124221932.v6up7j67llwhjox4@glandium.org","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-24T22:23:57Z","receivedAt":"2018-01-24T22:24:04Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Mike Hommey writes:\n\n> FWIW, I sidestep the problem entirely by using alternatives.\n\nThat's a funny way to use the word \"side-step\", I would say, as the\nalternate object store support is there exactly for this use case.\n"},{"id":"337328","messageId":"20180124222518.GA24157@whir","threadId":"47684","inReplyTo":"87bmhiykvw.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2018-01-24T22:25:18Z","receivedAt":"2018-01-24T22:25:23Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Ævar Arnfjörð Bjarmason wrote:\n> If you have a bunch of git repositories cloned of the same project on\n> the same filesystem, it would be nice of the packs that are produced\n> would be friendly to block-level deduplication.\n\nFwiw, I currently get around this when mirroring by having all\nthe remotes I care about mirrored to a \"hidden\" root repo, and\nhaving other repos point to the hidden root objects via\nobject/info/alternates. Not that great for usability and\nprobably potentially racy...\n\n> Has anyone here barked up this tree before? Suggestions? Tips on where\n> to start hacking the repack code to accomplish this would be most\n> welcome.\n\nThe Debian version of gzip(1) has an --rsyncable patch which\nmight be of help.\n"},{"id":"337330","messageId":"20180124223047.iwi2ju7wvh7bptg2@glandium.org","threadId":"47684","inReplyTo":"xmqq607qc2v6.fsf@gitster.mtv.corp.google.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2018-01-24T22:30:49Z","receivedAt":"2018-01-24T22:31:03Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Wed, Jan 24, 2018 at 02:23:57PM -0800, Junio C Hamano wrote:\n> Mike Hommey writes:\n> \n> > FWIW, I sidestep the problem entirely by using alternatives.\n> \n> That's a funny way to use the word \"side-step\", I would say, as the\n> alternate object store support is there exactly for this use case.\n\nIt's footgunny, though.\n\nMike\n"},{"id":"337331","messageId":"CABPp-BE0u9x_TtEHmfS11ZV-50rSvCi_y7cmTVV7z=2zT3atvg@mail.gmail.com","threadId":"47684","inReplyTo":"87bmhiykvw.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-01-24T22:37:34Z","receivedAt":"2018-01-24T22:37:40Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jan 24, 2018 at 2:03 PM, Ævar Arnfjörð Bjarmason\n wrote:\n> If you have a bunch of git repositories cloned of the same project on\n> the same filesystem, it would be nice of the packs that are produced\n> would be friendly to block-level deduplication.\n>\n> This would save space, and the blocks would be more likely to be in\n> cache when you access them, likely speeding up git operations even if\n> the packing itself is less efficient.\n>\n> Here's a hacky one-liner that clones git/git and peff/git (almost the\n> same content) and md5sums each 4k packed block, and sort | uniq -c's\n> them to see how many are the same:\n\n\n\n>\n> Has anyone here barked up this tree before? Suggestions? Tips on where\n> to start hacking the repack code to accomplish this would be most\n> welcome.\n\nDoes this overlap with the desire to have resumable clones? I'm\ncurious what would happen if you did the same experiment with two\nseparate clones of git/git, cloned one right after the other so that\nhopefully the upstream git/git didn't receive any updates between your\ntwo separate clones. (In other words, how much do packfiles differ in\npractice for different packings of the same data?)\n"},{"id":"337334","messageId":"87a7x2yiv4.fsf@evledraar.gmail.com","threadId":"47684","inReplyTo":"xmqq607qc2v6.fsf@gitster.mtv.corp.google.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-24T22:47:27Z","receivedAt":"2018-01-24T22:47:35Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jan 24 2018, Junio C. Hamano jotted:\n\n> Mike Hommey writes:\n>\n>> FWIW, I sidestep the problem entirely by using alternatives.\n>\n> That's a funny way to use the word \"side-step\", I would say, as the\n> alternate object store support is there exactly for this use case.\n\nThings you can't do with alternates that block-level de-duplication\ngives you:\n\n 1. Your filesystem may be mounted from some NFS host that does\n block-level deduplication internally against other content you don't\n have permission to access, think the /home of a bunch of dev VMs you\n know will have the same repos cloned (along with most of the same FS\n content, e.g. the OS).\n\n In this case the storage can de-duplicate blocks purely as an\n implementation without git knowing about it, as long as git (or any\n other program using the FS) can be coerced into writing the same\n blocks other gits on other machines write, at least most of the\n time.\n\n 2. Ditto NFS, but e.g. chroot'd /home on a local non-NFS.\n\n 3. Even if the repos are all on the same host they may just be ad-hoc\n cloned in /home by different users, it's easy to write something in\n /etc/gitconfig to give them the same repack settings, less so to\n maintain some git-clone wrapper that implictily adds --reference\n (they'll not know, or forget) to all clones, or goes hunting around\n for checkouts and adding alternates after the fact.\n\n 4. With alternates you always need to maintain some blessed \"clone from\n this\" repo that can't go away least everything cloned from it become\n corrupt and needs manual repair. If you're aiming to just save\n storage block-level deduplication may be a better trade-off.\n\nAlso once you clone with --reference doesn't the local clone only add\nnew objects as you \"git fetch\", never pruning those if the same objects\nappear in the alternate later on, or am I misremembering things?\n\nI mainly have use-case #1 & #3, although they could both be made to use\nalternates with some hassle (e.g. for #1 exposing a separate read-only\ncopy of \"these are alternates\" to each VM) it seemed worthwhile to see\nif repack could be made to be more block-level deduplication friendly,\nas deploying that is easier.\n"},{"id":"337336","messageId":"878tcmyhyk.fsf@evledraar.gmail.com","threadId":"47684","inReplyTo":"CABPp-BE0u9x_TtEHmfS11ZV-50rSvCi_y7cmTVV7z=2zT3atvg@mail.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-24T23:06:59Z","receivedAt":"2018-01-24T23:07:09Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jan 24 2018, Elijah Newren jotted:\n\n> On Wed, Jan 24, 2018 at 2:03 PM, Ævar Arnfjörð Bjarmason\n> wrote:\n>> If you have a bunch of git repositories cloned of the same project on\n>> the same filesystem, it would be nice of the packs that are produced\n>> would be friendly to block-level deduplication.\n>>\n>> This would save space, and the blocks would be more likely to be in\n>> cache when you access them, likely speeding up git operations even if\n>> the packing itself is less efficient.\n>>\n>> Here's a hacky one-liner that clones git/git and peff/git (almost the\n>> same content) and md5sums each 4k packed block, and sort | uniq -c's\n>> them to see how many are the same:\n>\n> \n>\n>>\n>> Has anyone here barked up this tree before? Suggestions? Tips on where\n>> to start hacking the repack code to accomplish this would be most\n>> welcome.\n>\n> Does this overlap with the desire to have resumable clones? I'm\n> curious what would happen if you did the same experiment with two\n> separate clones of git/git, cloned one right after the other so that\n> hopefully the upstream git/git didn't receive any updates between your\n> two separate clones. (In other words, how much do packfiles differ in\n> practice for different packings of the same data?)\n\nIf you clone git/git from Github twice in a row you get the exact same\npack, and AFAICT this is true of git in general (but may change between\nversions).\n\nIf you make a local commit to that, copy the dir, and repack -A -d you\nget the exact same packs again.\n\nIf you then make just one local commit to one copy (even with\n--allow-empty) and repack, you get entirely differnt packs, in my test\n2.5% of the blocks remain the same.\n\nObviously you could pack *that* new content incrementally and keep the\nexisting pack, but that won't help you with de-duping the initially\ncloned data, which is what matters.\n"},{"id":"337337","messageId":"20180124232214.GA11348@sigill.intra.peff.net","threadId":"47684","inReplyTo":"87bmhiykvw.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T23:22:14Z","receivedAt":"2018-01-24T23:22:25Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 11:03:47PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> This produces a total of 0 blocks that are the same. If after the repack\n> we throw this in there after the repack:\n> \n> echo 5be1f00a9a | git pack-objects --no-reuse-delta --no-reuse-object --revs .git/objects/pack/manual\n> \n> Just over 8% of the blocks are the same, and of course this pack\n> entirely duplicates the existing packs, and I don't know how to coerce\n> repack/pack-objects into keeping this manual-* pack and re-packing the\n> rest, removing any objects that exist in the manual-* pack.\n\nI think touching manual-*.keep would do what you want (followed by\n\"repack -ad\" to drop the duplicate objects).\n\nYou may also want to use \"--threads=1\" to avoid non-determinism in the\ngenerated packs. In theory, both repos would then produce identical base\npacks, though it does not seem to do so in practice (I didn't dig in to\nwhat the different may be).\n\n> I couldn't find any references to someone trying to get this particular\n> use-case working on-list. I.e. to pack different repositories with a\n> shared history in such a way as to optimize for getting the most amount\n> of identical blocks within packs.\n\nI don't recall any discussion on this topic before.\n\nI think you're fighting against two things here:\n\n - the order in which we find deltas; obviously a delta of A against B\n is quite different than B against A\n\n - the order of objects written to disk\n\nThose mostly work backwards through the history graph, so adding new\nhistory on top of old will cause changes at the beginning of the file,\nand \"shift\" the rest so that the blocks don't match.\n\nIf you reverse the order of those, then the shared history is more\nlikely to provide a common start to the pack. See compute_write_order()\nand the final line of type_size_sort().\n\n> It should be possible to produce such a pack, e.g. by having a repack\n> mode that would say:\n> \n> 1. Find what the main branch is\n> 2. Get its commits in reverse order, produce packs of some chunk-size\n> of commit batches.\n> 3. Pack all the remaining content\n> \n> This would delta much less efficiently, but as noted above the\n> block-level deduplication might make up for it, and in any case some\n> might want to use less disk space.\n\nWe do something a bit like this at GitHub. There we have a single pack\nholding all of the objects for many forks. So the deduplication is done\nalready, but we want to avoid deltas that cross fork boundaries (since\nthey mean throwing away the delta and recomputing from scratch when\nsomebody fetches). And then we write the result in layers, although\nright now there are only 2 layers (some \"base\" fork gets all of its\nobjects, and then everybody else's objects are dumped on top).\n\nI suspect some of the same concepts could be applied. If you're\ninterested in playing with it, I happened to extract it into a single\npatch recently (it's on my list of \"stuff to send upstream\" but I\nhaven't gotten around to polishing it fully). It's the\n\"jk/delta-islands\" branch of https://github.com/peff/git (which I happen\nto know you already have a clone of ;) ).\n\n-Peff\n"},{"id":"337339","messageId":"20180124233220.GB11348@sigill.intra.peff.net","threadId":"47684","inReplyTo":"878tcmyhyk.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T23:32:20Z","receivedAt":"2018-01-24T23:32:26Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 25, 2018 at 12:06:59AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> >> Has anyone here barked up this tree before? Suggestions? Tips on where\n> >> to start hacking the repack code to accomplish this would be most\n> >> welcome.\n> >\n> > Does this overlap with the desire to have resumable clones? I'm\n> > curious what would happen if you did the same experiment with two\n> > separate clones of git/git, cloned one right after the other so that\n> > hopefully the upstream git/git didn't receive any updates between your\n> > two separate clones. (In other words, how much do packfiles differ in\n> > practice for different packings of the same data?)\n> \n> If you clone git/git from Github twice in a row you get the exact same\n> pack, and AFAICT this is true of git in general (but may change between\n> versions).\n\nThat's definitely not guaranteed. It _tends_ to be the case over the\nshort term because we use --threads=1 on the server. But it may differ\nif:\n\n - we repack on the server, which we do based on pushes\n\n - somebody pushes, even to another fork. The exact results depend\n on the packs in which we find the objects, and a new push may\n duplicate some existing objects but with a different representation,\n (e.g., a different delta base).\n\nI'm actually interested in adding an etags-like protocol extension that\nwould work something like this:\n\n - server says \"here's a pack, and its opaque tag is XYZ\".\n\n - on resume, the client says \"can I resume pack with tag XYZ\"?\n\n - the server then decides if the on-disk state is sufficient for it to\n agree to recreate XYZ (e.g., number and identity of packs). If yes,\n then it resumes. If no, then it says \"nope\" and the two sides go\n through a normal fetch again.\n\nThe important thing is that the tag is opaque to the client. So a stock\nimplementation could use the on-disk state to decide. But a server could\nchoose to cache the packs it sends for a period of time (especially if\nthe client hangs up before we've sent the whole thing). We already do\nthis to a limited degree at GitHub in order to efficiently serve\nmultiple clients simultaneously fetching the same pack (e.g., imagine a\nfleet of AWS machines all triggering \"git fetch\" at once).\n\nI think that's a tangent to what you're looking for in this thread,\nthough.\n\n-Peff\n"},{"id":"337342","messageId":"87607qyfci.fsf@evledraar.gmail.com","threadId":"47684","inReplyTo":"20180124232214.GA11348@sigill.intra.peff.net","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-25T00:03:25Z","receivedAt":"2018-01-25T00:03:34Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jan 24 2018, Jeff King jotted:\n\n> On Wed, Jan 24, 2018 at 11:03:47PM +0100, Ævar Arnfjörð Bjarmason wrote:\n>\n>> This produces a total of 0 blocks that are the same. If after the repack\n>> we throw this in there after the repack:\n>>\n>> echo 5be1f00a9a | git pack-objects --no-reuse-delta --no-reuse-object --revs .git/objects/pack/manual\n>>\n>> Just over 8% of the blocks are the same, and of course this pack\n>> entirely duplicates the existing packs, and I don't know how to coerce\n>> repack/pack-objects into keeping this manual-* pack and re-packing the\n>> rest, removing any objects that exist in the manual-* pack.\n>\n> I think touching manual-*.keep would do what you want (followed by\n> \"repack -ad\" to drop the duplicate objects).\n\nThanks, that got the number of identical blocks just north of 15%...\n\n> You may also want to use \"--threads=1\" to avoid non-determinism in the\n> generated packs. In theory, both repos would then produce identical base\n> packs, though it does not seem to do so in practice (I didn't dig in to\n> what the different may be).\n\n..and north of 20% with --threads=1.\n\n>> I couldn't find any references to someone trying to get this particular\n>> use-case working on-list. I.e. to pack different repositories with a\n>> shared history in such a way as to optimize for getting the most amount\n>> of identical blocks within packs.\n>\n> I don't recall any discussion on this topic before.\n>\n> I think you're fighting against two things here:\n>\n> - the order in which we find deltas; obviously a delta of A against B\n> is quite different than B against A\n>\n> - the order of objects written to disk\n>\n> Those mostly work backwards through the history graph, so adding new\n> history on top of old will cause changes at the beginning of the file,\n> and \"shift\" the rest so that the blocks don't match.\n>\n> If you reverse the order of those, then the shared history is more\n> likely to provide a common start to the pack. See compute_write_order()\n> and the final line of type_size_sort().\n\nI'll have to poke at what compute_write_order() is doing, but FWIW this\nto type_size_sort() got shared blocks down to 3%:\n\n diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n index 81ad914cfc..c9ada1bd1c 100644\n --- a/builtin/pack-objects.c\n +++ b/builtin/pack-objects.c\n @@ -1764,7 +1764,7 @@ static int type_size_sort(const void *_a, const void *_b)\n return -1;\n if (a->size < b->size)\n return 1;\n - return a < b ? -1 : (a > b); /* newest first */\n + return b < a ? -1 : (b > a); /* newest first */\n }\n\n struct unpacked {\n\n>> It should be possible to produce such a pack, e.g. by having a repack\n>> mode that would say:\n>>\n>> 1. Find what the main branch is\n>> 2. Get its commits in reverse order, produce packs of some chunk-size\n>> of commit batches.\n>> 3. Pack all the remaining content\n>>\n>> This would delta much less efficiently, but as noted above the\n>> block-level deduplication might make up for it, and in any case some\n>> might want to use less disk space.\n>\n> We do something a bit like this at GitHub. There we have a single pack\n> holding all of the objects for many forks. So the deduplication is done\n> already, but we want to avoid deltas that cross fork boundaries (since\n> they mean throwing away the delta and recomputing from scratch when\n> somebody fetches). And then we write the result in layers, although\n> right now there are only 2 layers (some \"base\" fork gets all of its\n> objects, and then everybody else's objects are dumped on top).\n>\n> I suspect some of the same concepts could be applied. If you're\n> interested in playing with it, I happened to extract it into a single\n> patch recently (it's on my list of \"stuff to send upstream\" but I\n> haven't gotten around to polishing it fully). It's the\n> \"jk/delta-islands\" branch of https://github.com/peff/git (which I happen\n> to know you already have a clone of ;) ).\n\nThanks. I'll look into that, although the above results (sans hacking on\nthe core pack-objects logic) suggest that even once I create an island\nI'm getting at most 20%.\n"},{"id":"337343","messageId":"20180125001015.GA17856@sigill.intra.peff.net","threadId":"47684","inReplyTo":"87607qyfci.fsf@evledraar.gmail.com","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-25T00:10:15Z","receivedAt":"2018-01-25T00:10:21Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 25, 2018 at 01:03:25AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> > You may also want to use \"--threads=1\" to avoid non-determinism in the\n> > generated packs. In theory, both repos would then produce identical base\n> > packs, though it does not seem to do so in practice (I didn't dig in to\n> > what the different may be).\n> \n> ..and north of 20% with --threads=1.\n>\n> [...]\n>\n> Thanks. I'll look into that, although the above results (sans hacking on\n> the core pack-objects logic) suggest that even once I create an island\n> I'm getting at most 20%.\n\nI think it may be worth figuring out where the two differ. With\n--no-reuse-object and --no-reuse-delta, I'd think that the pack\ngenerated for a particular apex commit would be totally deterministic,\nregardless of other objects available in the repo. But it's not for some\nreason.\n\n-Peff\n"},{"id":"337344","messageId":"20180125002942.GA21184@sigill.intra.peff.net","threadId":"47684","inReplyTo":"20180125001015.GA17856@sigill.intra.peff.net","subject":"Re: Git packs friendly to block-level deduplication","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-25T00:29:42Z","receivedAt":"2018-01-25T00:29:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 07:10:15PM -0500, Jeff King wrote:\n\n> On Thu, Jan 25, 2018 at 01:03:25AM +0100, Ævar Arnfjörð Bjarmason wrote:\n> \n> > > You may also want to use \"--threads=1\" to avoid non-determinism in the\n> > > generated packs. In theory, both repos would then produce identical base\n> > > packs, though it does not seem to do so in practice (I didn't dig in to\n> > > what the different may be).\n> > \n> > ..and north of 20% with --threads=1.\n> >\n> > [...]\n> >\n> > Thanks. I'll look into that, although the above results (sans hacking on\n> > the core pack-objects logic) suggest that even once I create an island\n> > I'm getting at most 20%.\n> \n> I think it may be worth figuring out where the two differ. With\n> --no-reuse-object and --no-reuse-delta, I'd think that the pack\n> generated for a particular apex commit would be totally deterministic,\n> regardless of other objects available in the repo. But it's not for some\n> reason.\n\nI think I see it. If I compare the objects in pack-order of the two\npacks:\n\n diff -u <(git show-index <$one | sort -n) <(git show-index <$two | sort -n)\n\nI get:\n\n 6281 fac64e011f1b1ecabcccf7ad2511efcac3e26bdc (9381a4f9)\n 6585 59c276cf4da0705064c32c9dba54baefa282ea55 (1b02a1c0)\n 6869 8279ed033f703d4115bee620dccd32a9ec94d9aa (ca7acf33)\n -7042 298d861208d71089dd308761ae96738e81ad3e68 (135aefd7)\n -7222 ea7b5de1c1187294d3d4dca93b129e049ca7ca76 (3708bbfc)\n -7512 b6947af2294ea0c814f5b4cb8737c782895519b2 (719fad14)\n -8004 e26f7f19b6c7485f04234946a59ab8f4fd21d6d1 (59127876)\n -8826 2512f15446149235156528dafbe75930c712b29e (fc72468e)\n [...]\n +7042 2512f15446149235156528dafbe75930c712b29e (fc72468e)\n +7215 c6c75c93aaeb97bab6fd25b672a641c84dd85d59 (68fe0b8d)\n +7391 36438dc19dd2a305dddebd44bf7a65f1a220075b (c424e726)\n +7565 1eaabe34fc6f486367a176207420378f587d3b48 (4a27450b)\n\nSo the write order differs; one pack stuck 2512f15446 much earlier.\n\nThat's probably due to this line from compute_write_order():\n\n /*\n * Mark objects that are at the tip of tags.\n */\n for_each_tag_ref(mark_tagged, NULL);\n\nIf I remove that line, then your manual pack (with --threads=1) gives me\nidentical packs for each repo.\n\nAnd if I then mark each with a .keep, then \"git repack -ad\" to remove\nduplicates, your block-dedup check yields:\n\n 17742 2\n 1939 1\n\nwhich is 90%, and about what I'd expect between those two repos. So I\nthink the idea of computing a \"base\" pack (either as a separate pack, or\nas a layer in the pack) is a viable strategy.\n\n-Peff\n"}]}