{"thread":{"id":"53868","subject":"Compressing packed-refs","startedAt":"2020-07-16T22:10:31Z","lastAt":"2020-07-20T17:32:22Z","messageCount":6,"participants":["Konstantin Ryabitsev","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"401666","messageId":"20200716221026.dgduvxful32gkhwy@chatter.i7.local","threadId":"53868","inReplyTo":null,"subject":"Compressing packed-refs","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2020-07-16T22:10:26Z","receivedAt":"2020-07-16T22:10:31Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"Hi, all:\n\nI know repos with too many refs is a corner-case for most people, but \nit's looming large in my world, so I'm wondering if it makes sense to \ncompress the packed-refs file when \"git pack-refs\" is performed?\n\nWhat would the implications be, other than minor performance degradation \nwhen reading it?\n\n-K\n"},{"id":"401667","messageId":"20200716225429.i7pb6xorkwdsf5fn@chatter.i7.local","threadId":"53868","inReplyTo":"xmqqsgdrf64c.fsf@gitster.c.googlers.com","subject":"Re: Compressing packed-refs","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2020-07-16T22:54:29Z","receivedAt":"2020-07-16T23:09:57Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"On Thu, Jul 16, 2020 at 03:27:15PM -0700, Junio C Hamano wrote:\n> I think the reftable is the longer term direction, but let's see if\n> there is easy enough optimization opportunity that we can afford the\n> development and maintenance cost for the short term.\n> \n> My .git/packed-refs file begins like so:\n> \n>     # pack-refs with: peeled fully-peeled sorted \n>     c3808ca6982b0ad7ee9b87eca9b50b9a24ec08b0 refs/heads/maint-2.10\n>     3b9e3c2cede15057af3ff8076c45ad5f33829436 refs/heads/maint-2.11\n>     584f8975d2d9530a34bd0b936ae774f82fe30fed refs/heads/master\n>     2cccc8116438182c988c7f26d9559a1c22e78f1c refs/heads/next\n>     8300349bc1f0a0e2623d5824266bd72c1f4b5f24 refs/notes/commits\n>     ...\n\nLet me offer a more special-case (but not crazy) example from \ngit.kernel.org. The newer version of grokmirror that I'm working on is \nbuilt to take advantage of the pack-islands feature that was added a \nwhile back. We fetch all linux forks into a single \"object storage\" \nrepo, with each fork going into its own \nrefs/virtual/[uniquename]/(heads|tags) place. This means there's lots of \nduplicates in packed-refs, as all the tags from torvalds/linux.git will \nend up duplicated in almost every fork.\n\nSo, after running git pack-refs --all, the packed-refs file is 50-ish MB \nin size, with a lot of same stuff like:\n\n5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c refs/virtual/00018460b026/tags/v2.6.11\n^c39ae07f393806ccf406ef966e9a15afc43cc36a\n...\n5dc01c595e6c6ec9ccda4f6f69c131c0dd945f8c refs/virtual/00bcef8138af/tags/v2.6.11\n^c39ae07f393806ccf406ef966e9a15afc43cc36a\n\netc, duplicated 600 times with each fork. It compresses decently well \nwith gzip -9, and *amazingly* well with xz -9:\n\n$ ls -ahl packed-refs\n-rw-r--r--. 1 mirror mirror 46M Jul 16 22:37 packed-refs\n$ ls -ahl packed-refs.gz\n-rw-r--r--. 1 mirror mirror 19M Jul 16 22:47 packed-refs.gz\n$ ls -ahl packed-refs.xz\n-rw-r--r--. 1 mirror mirror 2.3M Jul 16 22:47 packed-refs.xz\n\nWhich really just indicates how much duplicated data is in that file. If \nreftables will eventually replace refs entirely, then we probably \nshouldn't expend too much effort super-optimizing it, especially if I'm \none of the very few people who would benefit from it. However, I'm \ncurious if a different sorting strategy would help remove most of the \nduplication without requiring too much engineering time.\n\n-K\n"},{"id":"401670","messageId":"xmqqsgdrf64c.fsf@gitster.c.googlers.com","threadId":"53868","inReplyTo":"20200716221026.dgduvxful32gkhwy@chatter.i7.local","subject":"Re: Compressing packed-refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-16T22:27:15Z","receivedAt":"2020-07-16T23:24:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Konstantin Ryabitsev <konstantin@linuxfoundation.org> writes:\n\n> I know repos with too many refs is a corner-case for most people, but \n> it's looming large in my world, so I'm wondering if it makes sense to \n> compress the packed-refs file when \"git pack-refs\" is performed?\n\nI think the reftable is the longer term direction, but let's see if\nthere is easy enough optimization opportunity that we can afford the\ndevelopment and maintenance cost for the short term.\n\nMy .git/packed-refs file begins like so:\n\n    # pack-refs with: peeled fully-peeled sorted \n    c3808ca6982b0ad7ee9b87eca9b50b9a24ec08b0 refs/heads/maint-2.10\n    3b9e3c2cede15057af3ff8076c45ad5f33829436 refs/heads/maint-2.11\n    584f8975d2d9530a34bd0b936ae774f82fe30fed refs/heads/master\n    2cccc8116438182c988c7f26d9559a1c22e78f1c refs/heads/next\n    8300349bc1f0a0e2623d5824266bd72c1f4b5f24 refs/notes/commits\n    ...\n\nA few observations that can lead to easy design elements are\n\n - Typically more than half of each records is consumed by the\n   object name that is hard to \"compress\".\n\n - The file is sorted, so it could use the prefix compression like\n   we do in the v4 index files.\n\nSo perhaps a new format could be\n\n - The header \"# pack-refs with: \" lists a new trait, \"compressed\";\n\n - Object names will be expressed in binary, saving 20 bytes per a\n   record;\n\n - Prefix compression of the refnames similar to v4 index would save\n   a bit more.\n\nStoring binary object names would actually be favourable for\nperformance, as the in-core data structure we use to store the\nresult of parsing the file uses binary.\n\n\n"},{"id":"401676","messageId":"20200717062723.GA1179001@coredump.intra.peff.net","threadId":"53868","inReplyTo":"20200716225429.i7pb6xorkwdsf5fn@chatter.i7.local","subject":"Re: Compressing packed-refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-07-17T06:27:23Z","receivedAt":"2020-07-17T06:27:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 16, 2020 at 06:54:29PM -0400, Konstantin Ryabitsev wrote:\n\n> Let me offer a more special-case (but not crazy) example from \n> git.kernel.org. The newer version of grokmirror that I'm working on is \n> built to take advantage of the pack-islands feature that was added a \n> while back. We fetch all linux forks into a single \"object storage\" \n> repo, with each fork going into its own \n> refs/virtual/[uniquename]/(heads|tags) place. This means there's lots of \n> duplicates in packed-refs, as all the tags from torvalds/linux.git will \n> end up duplicated in almost every fork.\n> \n> So, after running git pack-refs --all, the packed-refs file is 50-ish MB \n> in size, with a lot of same stuff like:\n\nWe do the same thing at GitHub. 50MB is on the easy side. We have cases\nin the gigabytes.\n\n> etc, duplicated 600 times with each fork. It compresses decently well \n> with gzip -9, and *amazingly* well with xz -9:\n> \n> $ ls -ahl packed-refs\n> -rw-r--r--. 1 mirror mirror 46M Jul 16 22:37 packed-refs\n> $ ls -ahl packed-refs.gz\n> -rw-r--r--. 1 mirror mirror 19M Jul 16 22:47 packed-refs.gz\n> $ ls -ahl packed-refs.xz\n> -rw-r--r--. 1 mirror mirror 2.3M Jul 16 22:47 packed-refs.xz\n\nYes, it does compress well. Just gzipping like that would have worked\nonce upon a time, when accessing it meant reading the whole thing\nlinearly. These days, though, we mmap() the file and binary-search it.\nThat lets us examine a subset of the refs quickly (this is from our\ntorvalds/linux.git fork network):\n\n\n  $ wc -c packed-refs \n  2394623761 packed-refs\n\n  $ time git for-each-ref | wc -l\n  19552978\n  \n  real\t1m12.297s\n  user\t1m2.441s\n  sys\t0m10.235s\n\n  $ time git for-each-ref refs/remotes/2325298 | wc -l\n  2590\n  \n  real\t0m0.077s\n  user\t0m0.025s\n  sys\t0m0.055s\n\n> Which really just indicates how much duplicated data is in that file. If \n> reftables will eventually replace refs entirely, then we probably \n> shouldn't expend too much effort super-optimizing it, especially if I'm \n> one of the very few people who would benefit from it. However, I'm \n> curious if a different sorting strategy would help remove most of the \n> duplication without requiring too much engineering time.\n\nYou definitely could store it in a more efficient way. Reftables will\nhave most of the things you'd want: prefix compression, binary oids,\netc.  I wouldn't be opposed to a tweak to packed-refs in the meantime if\nit was simple to implement. But definitely we'd want to retain the\nability to find a subset of refs in sub-linear time. That might get\ntricky and push it from \"simple\" to \"let's just invest in reftable\".\n\nYou might also consider whether you need all of those refs at all in the\nobject storage repo. The main uses are:\n\n  - determining reachability during repacks; but you could generate this\n    on the fly from the refs in the individual forks (de-duplicating as\n    you go). We don't do this at GitHub, because the information in the\n    duplicates is useful to our delta-islands config.\n\n  - getting new objects into the object store. It sounds like you might\n    do this with \"git fetch\", which does need up-to-date refs. We used\n    to do that, too, but it can be quite slow. These days we migrate the\n    objects directly via hardlinks, and then use \"update-ref --stdin\" to\n    sync the refs into the shared storage repo.\n\n  - advertising alternate ref tips in receive-pack (i.e., saying \"we\n    already know about object X\" if it's in somebody else's fork, which\n    means people pulling from Linus and then pushing to their fork don't\n    have to send the objects again). You probably don't want to\n    advertise all of them (just sifting the duplicates is too\n    expensive). We use core.alternateRefsCommand to pick out just the\n    ones from the parent fork. We _do_ still use the copy of the refs in\n    our shared storage, not the ones in the actual fork. But that's\n    because we migrate objects to shared storage asynchronously (so it's\n    possible for one fork to have refs pointing to objects that aren't\n    yet available to the other forks).\n\nSo it's definitely not a no-brainer, but possibly something to explore.\n\n-Peff\n"},{"id":"401736","messageId":"20200718182618.yqo5dcljf3h6q57q@chatter.i7.local","threadId":"53868","inReplyTo":"20200717062723.GA1179001@coredump.intra.peff.net","subject":"Re: Compressing packed-refs","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2020-07-18T18:26:18Z","receivedAt":"2020-07-18T18:26:24Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"On Fri, Jul 17, 2020 at 02:27:23AM -0400, Jeff King wrote:\n> > Which really just indicates how much duplicated data is in that \n> > file. If reftables will eventually replace refs entirely, then we \n> > probably shouldn't expend too much effort super-optimizing it, \n> > especially if I'm one of the very few people who would benefit from \n> > it. However, I'm curious if a different sorting strategy would help \n> > remove most of the duplication without requiring too much \n> > engineering time.\n> \n> You definitely could store it in a more efficient way. Reftables will\n> have most of the things you'd want: prefix compression, binary oids,\n> etc.  I wouldn't be opposed to a tweak to packed-refs in the meantime if\n> it was simple to implement. But definitely we'd want to retain the\n> ability to find a subset of refs in sub-linear time. That might get\n> tricky and push it from \"simple\" to \"let's just invest in reftable\".\n\nI'm fine either way, but a better approach seems to wait for reftables \nto land.\n\n> You might also consider whether you need all of those refs at all in the\n> object storage repo. The main uses are:\n> \n>   - determining reachability during repacks; but you could generate this\n>     on the fly from the refs in the individual forks (de-duplicating as\n>     you go). We don't do this at GitHub, because the information in the\n>     duplicates is useful to our delta-islands config.\n>   - getting new objects into the object store. It sounds like you might\n>     do this with \"git fetch\", which does need up-to-date refs. We used\n>     to do that, too, but it can be quite slow. These days we migrate the\n>     objects directly via hardlinks, and then use \"update-ref --stdin\" to\n>     sync the refs into the shared storage repo.\n\nThis is definitely interesting to me, as git fetch runs into objstore \nrepos do take a long time, even after I move them into a \"lazy\" thread.  \nIt's not so much a problem for git.kernel.org where pushes come in \nsporadically, but for CAF, their automation usually pushes several \nhundred repo updates at the same time, and the subsequent fetch into \nobjstore takes several hours to complete.\n\nCan you elaborate on the details of that operation, if it's not secret \nsauce? Say, I have two repos:\n\nrepoA/objects/\nrepoS/objects/\n\ndoes this properly describe the operation:\n\n1. locate all pack/* and XX/* files in repoA/objects (what about the \n   info/packs file, or do you loosen all packs first?)\n2. hardlink them into the same location in repoS/objects\n3. use git-show-ref from repoA to generate stdin for git-update-ref in \n   repoS\n4. Consequent runs of repack in repoA should unreference the hardlinked \n   files in repoA/objects and leave only their copy in repoS\n\nI'm not sure I'm quite comfortable doing this kind of spinal surgery on \ngit repos yet, but I'm willing to wet my feet in some safe environments.  \n:)\n\n>   - advertising alternate ref tips in receive-pack (i.e., saying \"we\n>     already know about object X\" if it's in somebody else's fork, which\n>     means people pulling from Linus and then pushing to their fork don't\n>     have to send the objects again). You probably don't want to\n>     advertise all of them (just sifting the duplicates is too\n>     expensive). We use core.alternateRefsCommand to pick out just the\n>     ones from the parent fork. We _do_ still use the copy of the refs in\n>     our shared storage, not the ones in the actual fork. But that's\n>     because we migrate objects to shared storage asynchronously (so it's\n>     possible for one fork to have refs pointing to objects that aren't\n>     yet available to the other forks).\n\nYes, I did ponder using this, especially when dealing with objstore \nrepos with hundreds of thousands of refs -- thanks for another nudge in \nthis direction. I am planning to add a concept of indicating \"baseline\" \nrepos to grokmirror, which allows us to:\n\n1. set them as islandCore in objstore repositories\n2. return only their refs via alternateRefsCommand\n\nThis one seems fairly straightforward and I will probably add that in \nnext week.\n\n> So it's definitely not a no-brainer, but possibly something to \n> explore.\n\nIndeed -- at this point I'm more comfortable letting git itself do all \nobject moving, but as I get more familiar with how object-storage repos \nwork, I can optimize various aspects of it.\n\nThanks for your help!\n\n-K\n"},{"id":"401770","messageId":"20200720173220.GB2045458@coredump.intra.peff.net","threadId":"53868","inReplyTo":"20200718182618.yqo5dcljf3h6q57q@chatter.i7.local","subject":"Re: Compressing packed-refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-07-20T17:32:20Z","receivedAt":"2020-07-20T17:32:22Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 18, 2020 at 02:26:18PM -0400, Konstantin Ryabitsev wrote:\n\n> >   - getting new objects into the object store. It sounds like you might\n> >     do this with \"git fetch\", which does need up-to-date refs. We used\n> >     to do that, too, but it can be quite slow. These days we migrate the\n> >     objects directly via hardlinks, and then use \"update-ref --stdin\" to\n> >     sync the refs into the shared storage repo.\n> [...]\n> Can you elaborate on the details of that operation, if it's not secret \n> sauce? Say, I have two repos:\n\nNo secret sauce, but it's pretty much what you wrote out. A few\ncomments:\n\n> 1. locate all pack/* and XX/* files in repoA/objects (what about the \n>    info/packs file, or do you loosen all packs first?)\n\nWe only copy the pack and loose object files. We don't generate\ninfo/packs at all, since we don't allow dumb-http access. Nor do we copy\nany commit-graph files over (those are generated only in the shared\nstorage repo, and then every fork gets to use them).\n\nDefinitely don't loosen packs. It's very expensive. :)\n\n> 2. hardlink them into the same location in repoS/objects\n\nYep. And now they're available atomically in both places.\n\n> 3. use git-show-ref from repoA to generate stdin for git-update-ref in \n>    repoS\n\nUse for-each-ref for this. It's received more optimizations over the\nyears (especially around looking at the minimum of packed-refs when it\ncan). Don't forget to delete refs that have gone away. We do something\nlike (typed in email, so watch out for errors):\n\n  id=123\n  git --git-dir=repoA for-each-ref \\\n    --format=\"%(objectname) refs/remotes/$id/%(refname)' >want\n  git --git-dir=repoS for-each-ref \\\n    --format=\"%(objectname) %(refname)\" refs/remotes/$id/ >have\n\nand then compare the results (our code is in ruby using hashes, but you\ncould do it with comm or similar). And then you should end up with a set\nof updates and deletions, which you can feed to \"git update-ref --stdin\"\n(which is smart enough to do deletions before additions to save you from\ndirectory/file conflicts in the namespace).\n\n(There's no particular reason you need to use refs/remotes/ in the\nshared repo; for us it's just historical since we really did define\nconfigure remotes for each fork many many years ago).\n\n> 4. Consequent runs of repack in repoA should unreference the hardlinked \n>    files in repoA/objects and leave only their copy in repoS\n\nYeah, I think it would do so, but we just unlink them immediately.\n\n> I'm not sure I'm quite comfortable doing this kind of spinal surgery on \n> git repos yet, but I'm willing to wet my feet in some safe environments.  \n> :)\n\nWe resisted it for a long time, too, because I didn't want to violate\nany of Git's assumptions. But the cost of fetches was just getting too\nhigh (especially because we queue a sync job after every push, and some\nusers like to push a _lot_).\n\n> Yes, I did ponder using this, especially when dealing with objstore \n> repos with hundreds of thousands of refs -- thanks for another nudge in \n> this direction. I am planning to add a concept of indicating \"baseline\" \n> repos to grokmirror, which allows us to:\n> \n> 1. set them as islandCore in objstore repositories\n> 2. return only their refs via alternateRefsCommand\n> \n> This one seems fairly straightforward and I will probably add that in \n> next week.\n\nYeah, it is. Our alternateRefsCommand is a script that basically does:\n\n  # receive parent id info out-of-band in environment; if it's not\n  # there, then show no alternate tips\n  test -z \"$parent_repo_id\" && exit 0\n\n  git --git-dir=\"$1\" for-each-ref \\\n    --format='%(objectname)' refs/remotes/$i/heads/\n\nNote that we only advertise \"heads/\" from the fork, and ignore the tags.\nI don't know that we did a very rigorous study, but our general finding\nwas that tags don't often help much, and do clutter up the response for\nsome repos (again, some users think that 50,000 tags is reasonable).\n\n-Peff\n"}]}