{"thread":{"id":"31660","subject":"Using bitmaps to accelerate fetch and clone","startedAt":"2012-09-27T00:47:47Z","lastAt":"2012-10-02T15:00:54Z","messageCount":20,"participants":["Shawn Pearce","Nguyen Thai Ngoc Duy","Jeff King","David Michael Barr","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"199988","messageId":"CAJo=hJstK1tGrWhtBt3s+R1a6C0ge3wMtJnoo43Fjfg5A57eVw@mail.gmail.com","threadId":"31660","inReplyTo":null,"subject":"Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T00:47:47Z","receivedAt":"2012-09-27T00:47:47Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Google has published a series of patches (see links below) to JGit to\nimprove fetch and clone performance by adding compressed bitmaps to\nthe pack-*.idx structure.\n\nOperation Index V2 Index VE003\nClone 37530ms (524.06 MiB) 82ms (524.06 MiB)\nFetch (1 commit back) 75ms 107ms\nFetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\nFetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\nFetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\nFetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\nFetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n\nIn the table the repository tested was Android's\nplatform/frameworks/base. The time shown is the time spent in the\n\"Counting objects\" phase of creating a pack for a client using the\ngit:// protocol. The byte size shown is the size of the pack\ntransferred to the client, and \"commits back\" describes how far behind\nthe client was from the server when it started the fetch. In all test\nruns the client was git-core and the server was JGit on the same\nmachine.\n\nThe amount of disk space used by the compressed bitmaps is tunable,\nbut averages 10-15% of the pack-*.idx file size. So about 8 MiB of\nadditional space for this repository. A repository owner can reduce\nthe worst case time used in the 100000 commit back case by using\nslightly more disk and positioning more bitmaps more frequently\nthroughout history. The code doesn't do this by default because the\nexpectation is that a client is probably not 100k commits behind.\nInstead it populates bitmaps at all branch and tag tips, and densely\n(every few hundred commits) near the tips, and spaces them out more\nthe further back in history it goes. We assume the older history is\naccessed less often, and doesn't need to waste additional disk space\nor precious buffer cache.\n\nThe basic gist of the implementation is a bitmap has a 1 bit set for\neach object that is reachable from the commit the bitmap is associated\nwith. An index file may have a unique bitmap for hundreds of commits\nin the corresponding pack file. The set of objects to send is\nperformed by doing a simple computation:\n\n OR (all want lines) AND NOT OR (all have lines)\n\nThere are two key patches in the series that implement the file format\nchange and logic involved:\n\n* https://git.eclipse.org/r/7939\n\n Defines the new E003 index format and the bit set\n implementation logic.\n\n* https://git.eclipse.org/r/7940\n\n Uses E003 indexes when available to make packs, and\n the logic required to make E003 format indexes during GC.\n\n:-)\n"},{"id":"200006","messageId":"CACsJy8D0vkyEArNChXE0igUkanH6PwjmPitq22a9sudfmWF4kA@mail.gmail.com","threadId":"31660","inReplyTo":"CAJo=hJstK1tGrWhtBt3s+R1a6C0ge3wMtJnoo43Fjfg5A57eVw@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-27T12:17:42Z","receivedAt":"2012-09-27T12:17:42Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 27, 2012 at 7:47 AM, Shawn Pearce wrote:\n> Google has published a series of patches (see links below) to JGit to\n\nShould discussions about this series happen in here, jgit mailing or\ngerrit? I just want to make sure I'll discuss it at the right place.\n\n> improve fetch and clone performance by adding compressed bitmaps to\n> the pack-*.idx structure.\n>\n> Operation Index V2 Index VE003\n> Clone 37530ms (524.06 MiB) 82ms (524.06 MiB)\n> Fetch (1 commit back) 75ms 107ms\n> Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\n> Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\n> Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\n> Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\n> Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n\nBeautiful. And curious, why do 100->1000 and 10000->10000 have such\nbig leaps in time (V2)?\n\n> The basic gist of the implementation is a bitmap has a 1 bit set for\n> each object that is reachable from the commit the bitmap is associated\n> with. An index file may have a unique bitmap for hundreds of commits\n> in the corresponding pack file. The set of objects to send is\n> performed by doing a simple computation:\n>\n> OR (all want lines) AND NOT OR (all have lines)\n>\n> There are two key patches in the series that implement the file format\n> change and logic involved:\n>\n> * https://git.eclipse.org/r/7939\n>\n> Defines the new E003 index format and the bit set\n> implementation logic.\n\nI suppose the index format is not set in stone yet? My java-foo is\nrusty and I'm not familiar with jgit, so I more likely read things\nwrong.\n\nIt seems the bitmap data follows directly after regular index content.\nI'd like to see some sort of extension mechanism like in\n$GIT_DIR/index, so that we don't have to increase pack index version\noften. What I have in mind is optional commit cache to speed up\nrev-list and merge, which could be stored in pack index too.\n\nIn PackIndexVE003 class\n\n+ // Read the bitmaps for the Git types\n+ SimpleDataInput dataInput = new SimpleDataInput(fd);\n+ this.commits = readBitmap(dataInput);\n+ this.trees = readBitmap(dataInput);\n+ this.blobs = readBitmap(dataInput);\n+ this.tags = readBitmap(dataInput);\n\nAm I correct in saying that you have four different on-disk bitmaps,\none for each object type? If so, for compression efficient reasons?\n\n> :-)\n\nDefinitely :-). I have shown my interest in this topic before. So I\nshould probably say that I'm going to work on this on C Git, but\nsllloooowwwly. As this benefits the server side greatly, perhaps a\nGitHubber ;-) might want to work on this on C Git, for GitHub itself\nof course, and, as a side effect, make the rest of us happy?\n-- \nDuy\n"},{"id":"200011","messageId":"CAJo=hJt0PdpDT5ROUSfZ80Zh2ep=r5Sg1BS=v7Ve-djydHhp-w@mail.gmail.com","threadId":"31660","inReplyTo":"CACsJy8D0vkyEArNChXE0igUkanH6PwjmPitq22a9sudfmWF4kA@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T14:33:30Z","receivedAt":"2012-09-27T14:33:30Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Sep 27, 2012 at 7:47 AM, Shawn Pearce wrote:\n>> Google has published a series of patches (see links below) to JGit to\n>\n> Should discussions about this series happen in here, jgit mailing or\n> gerrit? I just want to make sure I'll discuss it at the right place.\n\nI think we should have a concrete discussion about the implementation\nin Java on the Gerrit changes (e.g. \"you should fix this comment it\ndoesn't sufficiently describe the method\"), and a discussion about the\nfile format and algorithm here where everyone can contribute.\n\nThe format is named E003 because its still experimental. Its not set\nin stone. Future iterations might be named E004, etc. If we get\nsomething final we will look to rename it to just version 3.\n\n>> improve fetch and clone performance by adding compressed bitmaps to\n>> the pack-*.idx structure.\n>>\n>> Operation Index V2 Index VE003\n>> Clone 37530ms (524.06 MiB) 82ms (524.06 MiB)\n>> Fetch (1 commit back) 75ms 107ms\n>> Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\n>> Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\n>> Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\n>> Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\n>> Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n>\n> Beautiful. And curious, why do 100->1000 and 10000->10000 have such\n> big leaps in time (V2)?\n\nWe didn't investigate this. Colby just reported on what the current\nJGit code does. I suspect there is something specific about the shape\nof the history graph for this repository combined with the way JGit\nwrote the pack file that caused these sorts of large increases.\nPerhaps they could be smaller. Not sure I care anymore when the E003\napproach gives us such low times. :-)\n\n>> The basic gist of the implementation is a bitmap has a 1 bit set for\n>> each object that is reachable from the commit the bitmap is associated\n>> with. An index file may have a unique bitmap for hundreds of commits\n>> in the corresponding pack file. The set of objects to send is\n>> performed by doing a simple computation:\n>>\n>> OR (all want lines) AND NOT OR (all have lines)\n>>\n>> There are two key patches in the series that implement the file format\n>> change and logic involved:\n>>\n>> * https://git.eclipse.org/r/7939\n>>\n>> Defines the new E003 index format and the bit set\n>> implementation logic.\n>\n> I suppose the index format is not set in stone yet?\n\nFor E003, yes, we already have some data encoded with it. But as a\nfile format change, no. We are willing to iterate on this if there is\ntangible benefit displayed by an alternative. Future versions would\nhave to be E004 or some other new version number to disambiguate from\nE003.\n\n> My java-foo is\n> rusty and I'm not familiar with jgit, so I more likely read things\n> wrong.\n\nOr maybe not. :-)\n\n> It seems the bitmap data follows directly after regular index content.\n\nCorrect. It is after the regular content, but before the 2 SHA-1 trailers.\n\n> I'd like to see some sort of extension mechanism like in\n> $GIT_DIR/index, so that we don't have to increase pack index version\n> often.\n\nThis might be worthwhile. I dislike the way $GIT_DIR/index encodes\nextensions. Forcing an extension to fully materialize itself to\ndetermine its length so the length can be placed before the data is\npainful to work with when writing the file out to disk. I would prefer\nwriting an index catalog at the trailer of the file. We already\nrequire random access to the index file, so its possible for a reader\nto read a fixed size trailer record that has the 2 SHA-1s we normally\nend an index with, and an extension catalog footer that has a length\nand CRC-32 of the catalog. The catalog would immediately appear before\nthe footer, so a reader can find the start of the extension catalog by\nsubtracting from the end of the file the catalog length and the file\nfooter and catalog footer lengths. The catalog can then supply a\nstarting offset for each extension section, and writers don't need to\npredict in advance how much data they need to store. Readers trying to\nuse extensions aren't really hurt, Git already randomly seeks to read\nthe tail of an index file to compare the pack SHA-1 before assuming\nthe index is valid.\n\n> What I have in mind is optional commit cache to speed up\n> rev-list and merge, which could be stored in pack index too.\n\nWe should also look into using the commit bitmap data to feed the\nrev-list traversal. The bitmaps can tell us which objects are commits,\nand their rough ordering given the packing rules. That may be\nsufficient to feed the walker without having a priority queue.\n\n> In PackIndexVE003 class\n>\n> + // Read the bitmaps for the Git types\n> + SimpleDataInput dataInput = new SimpleDataInput(fd);\n> + this.commits = readBitmap(dataInput);\n> + this.trees = readBitmap(dataInput);\n> + this.blobs = readBitmap(dataInput);\n> + this.tags = readBitmap(dataInput);\n>\n> Am I correct in saying that you have four different on-disk bitmaps,\n> one for each object type? If so, for compression efficient reasons?\n\nYes. The packer needs to know the type of each object its going to\npack. Instead of reading this from the individual object headers in\nthe pack files, we store them in compressed type bitmaps. This is much\nfaster to test than reading in the base data from the pack file.\n\n> Definitely :-). I have shown my interest in this topic before. So I\n> should probably say that I'm going to work on this on C Git, but\n> sllloooowwwly. As this benefits the server side greatly, perhaps a\n> GitHubber ;-) might want to work on this on C Git, for GitHub itself\n> of course, and, as a side effect, make the rest of us happy?\n\nGoogle may also contribute towards this work, we really want to see an\nimprovement in git-core too. Its just a lot of work, and we are also a\nlimited team. :-)\n"},{"id":"200020","messageId":"20120927172037.GB1547@sigill.intra.peff.net","threadId":"31660","inReplyTo":"CACsJy8D0vkyEArNChXE0igUkanH6PwjmPitq22a9sudfmWF4kA@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T17:20:37Z","receivedAt":"2012-09-27T17:20:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 07:17:42PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > Operation Index V2 Index VE003\n> > Clone 37530ms (524.06 MiB) 82ms (524.06 MiB)\n> > Fetch (1 commit back) 75ms 107ms\n> > Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\n> > Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\n> > Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\n> > Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\n> > Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n> \n> Beautiful. And curious, why do 100->1000 and 10000->10000 have such\n> big leaps in time (V2)?\n\nAgreed. I'm very excited about these numbers.\n\n> > Defines the new E003 index format and the bit set\n> > implementation logic.\n> [...]\n> It seems the bitmap data follows directly after regular index content.\n> I'd like to see some sort of extension mechanism like in\n> $GIT_DIR/index, so that we don't have to increase pack index version\n> often. What I have in mind is optional commit cache to speed up\n> rev-list and merge, which could be stored in pack index too.\n\nAs I understand it, both the bitmaps and a commit cache are\ntheoretically optional. That is, git can do the job without them, but\nthey speed things up. If that is the case, do we need to bump the index\nversion at all? Why not store a plain v2 index, and then store an\nadditional file \"pack-XXX.reachable\" that contains the bitmaps and an\nindependent version number.\n\nThe sha1 in the filename makes sure that the reachability file is always\nin sync with the actual pack data and index. Old readers won't know\nabout the new file, and will ignore it. For new readers, if the file is\nthere they can use it; if it's missing (or its version is not\nunderstood), they can fall back to the regular index.\n\nI haven't looked at the details of the format change yet. If it is\npurely an extra chunk of data at the end, this Just Works. If there are\nchanges to the earlier parts of the pack (e.g., I seem to recall the\ncommit cache idea wanted separate indices for each object type), we may\nstill need a v3. But it would be nice if we could make those changes\ngeneric (e.g., just the separate indices, which might support many\ndifferent enhancements), and then let the actual feature work happen in\nthe separate files.\n\n> Definitely :-). I have shown my interest in this topic before. So I\n> should probably say that I'm going to work on this on C Git, but\n> sllloooowwwly. As this benefits the server side greatly, perhaps a\n> GitHubber ;-) might want to work on this on C Git, for GitHub itself\n> of course, and, as a side effect, make the rest of us happy?\n\nYeah, GitHub is definitely interested in this. I may take a shot at it,\nbut I know David Barr (cc'd) is also interested in such things.\n\n-Peff\n"},{"id":"200024","messageId":"CAJo=hJuXCYa=MKSqCRsxmwFdFYZamK_94zc3fE0tmvwUAVA2Ow@mail.gmail.com","threadId":"31660","inReplyTo":"20120927172037.GB1547@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T17:35:47Z","receivedAt":"2012-09-27T17:35:47Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 10:20 AM, Jeff King wrote:\n> On Thu, Sep 27, 2012 at 07:17:42PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> > Operation Index V2 Index VE003\n>> > Clone 37530ms (524.06 MiB) 82ms (524.06 MiB)\n>> > Fetch (1 commit back) 75ms 107ms\n>> > Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\n>> > Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\n>> > Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\n>> > Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\n>> > Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n>>\n>> Beautiful. And curious, why do 100->1000 and 10000->10000 have such\n>> big leaps in time (V2)?\n>\n> Agreed. I'm very excited about these numbers.\n>\n>> > Defines the new E003 index format and the bit set\n>> > implementation logic.\n>> [...]\n>> It seems the bitmap data follows directly after regular index content.\n>> I'd like to see some sort of extension mechanism like in\n>> $GIT_DIR/index, so that we don't have to increase pack index version\n>> often. What I have in mind is optional commit cache to speed up\n>> rev-list and merge, which could be stored in pack index too.\n>\n> As I understand it, both the bitmaps and a commit cache are\n> theoretically optional. That is, git can do the job without them, but\n> they speed things up.\n\nYes, entirely true.\n\n> If that is the case, do we need to bump the index\n> version at all? Why not store a plain v2 index, and then store an\n> additional file \"pack-XXX.reachable\" that contains the bitmaps and an\n> independent version number.\n\nThis is the alternate version we considered internally. It was a bit\nmore work to define a 3rd file stream per pack in our backend storage\nsystem, so we opted for a revision of an existing stream. We could\nspend a bit more time and add a 3rd stream, keeping the index format\nunmodified.\n\nBut we could have also done this with the CRC-32 table in index v2. We\ndidn't. If the data should almost always be there in order to provide\ngood service then we should really be embedding into the files.\n\nI'm on the fence. I could go either way on this. E003 was just the\nfastest way to prototype and start testing. We would probably be\nequally happy with the 3rd stream.\n\n> The sha1 in the filename makes sure that the reachability file is always\n> in sync with the actual pack data and index.\n\nDepending on the extension dependencies, you may need to also use the\ntrailer SHA-1 from the pack file itself, like the index does. E.g. the\nbitmap data depends heavily on object order in the pack and is invalid\nif you repack with a different ordering algorithm, or a different\ndelta set of results from delta compression.\n\n> Old readers won't know\n> about the new file, and will ignore it. For new readers, if the file is\n> there they can use it; if it's missing (or its version is not\n> understood), they can fall back to the regular index.\n>\n> I haven't looked at the details of the format change yet. If it is\n> purely an extra chunk of data at the end, this Just Works.\n\nYes, its just extra chunk on the end.\n\n> If there are\n> changes to the earlier parts of the pack (e.g., I seem to recall the\n> commit cache idea wanted separate indices for each object type), we may\n> still need a v3. But it would be nice if we could make those changes\n> generic (e.g., just the separate indices, which might support many\n> different enhancements), and then let the actual feature work happen in\n> the separate files.\n\nYes. One downside is these separate streams aren't removed when you\nrun git repack. But this could be fixed by a modification to git\nrepack to clean up additional extensions with the same pack base name.\n\n>> Definitely :-). I have shown my interest in this topic before. So I\n>> should probably say that I'm going to work on this on C Git, but\n>> sllloooowwwly. As this benefits the server side greatly, perhaps a\n>> GitHubber ;-) might want to work on this on C Git, for GitHub itself\n>> of course, and, as a side effect, make the rest of us happy?\n>\n> Yeah, GitHub is definitely interested in this. I may take a shot at it,\n> but I know David Barr (cc'd) is also interested in such things.\n\nBuilding this in C is also dependent on having a good implementation\nof EWAH compressed bitmaps available. So its a bit more work, but not\ninsurmountable by any means.\n"},{"id":"200033","messageId":"20120927182233.GA2519@sigill.intra.peff.net","threadId":"31660","inReplyTo":"CAJo=hJuXCYa=MKSqCRsxmwFdFYZamK_94zc3fE0tmvwUAVA2Ow@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T18:22:33Z","receivedAt":"2012-09-27T18:22:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 10:35:47AM -0700, Shawn O. Pearce wrote:\n\n> > If that is the case, do we need to bump the index\n> > version at all? Why not store a plain v2 index, and then store an\n> > additional file \"pack-XXX.reachable\" that contains the bitmaps and an\n> > independent version number.\n> \n> This is the alternate version we considered internally. It was a bit\n> more work to define a 3rd file stream per pack in our backend storage\n> system, so we opted for a revision of an existing stream. We could\n> spend a bit more time and add a 3rd stream, keeping the index format\n> unmodified.\n\nI'd rather make the choice that provides the best user experience, even\nif it is a bit more code refactoring.\n\n> But we could have also done this with the CRC-32 table in index v2. We\n> didn't. If the data should almost always be there in order to provide\n> good service then we should really be embedding into the files.\n\nYes, although there were other changes in v2, also (e.g., the fanout to\nhandle larger packfiles). Bumping the version also made the transition\ntake a lot longer. We introduced the reading and writing code, but then\ncouldn't flip the default for quite a while. For big server providers\nthis is not as big a deal (we know which versions of git we will use,\nand are OK with flipping a config bit). But it's one more tuning thing\nto deal with for small or single-person servers.\n\nI think clients will also want it. If we can make \"git rev-list\n--objects --all\" faster (which this should be able to do), we can speed\nup \"git prune\", which in turn is by far the slowest part of \"git gc\n--auto\", since in the typical case we are only incrementally packing.\n\nI also like that the general technique can be reused easily. We've\ntalked about a generation-number cache in the past. That would fit this\nmodel as well. Removing a backwards-compatibility barrier makes it a lot\neasier to experiment with these sorts of things.\n\n> > The sha1 in the filename makes sure that the reachability file is always\n> > in sync with the actual pack data and index.\n> \n> Depending on the extension dependencies, you may need to also use the\n> trailer SHA-1 from the pack file itself, like the index does. E.g. the\n> bitmap data depends heavily on object order in the pack and is invalid\n> if you repack with a different ordering algorithm, or a different\n> delta set of results from delta compression.\n\nInteresting. I would have assumed it depended on order in the index. But\nlike I said, I haven't looked. I think you are still OK, though, because\nthe filename comes from the sha1 over the index file, which in turn\nincludes the sha1 over the packfile. Thus any change in the packfile\nwould give you a new pack and index name.\n\n> Yes. One downside is these separate streams aren't removed when you\n> run git repack. But this could be fixed by a modification to git\n> repack to clean up additional extensions with the same pack base name.\n\nI don't think that's a big deal. We already do it with \".keep\" files. If\nyou repack with an older version of git, you may have a stale\nsupplementary file wasting space. But that's OK. The next time you gc\nwith a newer version of git, we could detect and clean up such stale\nfiles (we already do so for tmp_pack_* files).\n\n-Peff\n"},{"id":"200035","messageId":"CAJo=hJs4NXatb2vsZWWCamLGLmi+FoWkTaf3Ky-nereXkHEptA@mail.gmail.com","threadId":"31660","inReplyTo":"20120927182233.GA2519@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T18:36:19Z","receivedAt":"2012-09-27T18:36:19Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 11:22 AM, Jeff King wrote:\n>\n> I think clients will also want it. If we can make \"git rev-list\n> --objects --all\" faster (which this should be able to do), we can speed\n> up \"git prune\", which in turn is by far the slowest part of \"git gc\n> --auto\", since in the typical case we are only incrementally packing.\n\nYes, the bitmap can also accelerate prune. We didn't implement this\nbut it is a trivial use of the existing bitmap.\n\n>> > The sha1 in the filename makes sure that the reachability file is always\n>> > in sync with the actual pack data and index.\n>>\n>> Depending on the extension dependencies, you may need to also use the\n>> trailer SHA-1 from the pack file itself, like the index does. E.g. the\n>> bitmap data depends heavily on object order in the pack and is invalid\n>> if you repack with a different ordering algorithm, or a different\n>> delta set of results from delta compression.\n>\n> Interesting. I would have assumed it depended on order in the index.\n\nNo. We tried that. Assigning bits by order in index (aka order of\nSHA-1s sorted) results in horrible compression of the bitmap itself\nbecause of the uniform distribution of SHA-1. Encoding instead by pack\norder gets us really good bitmap compression, because object graph\ntraversal order tends to take reachability into account. So we see\nlong contiguous runs of 1s and get good compression. Sorting by SHA-1\njust makes the space into swiss cheese.\n\n> I think you are still OK, though, because\n> the filename comes from the sha1 over the index file, which in turn\n> includes the sha1 over the packfile. Thus any change in the packfile\n> would give you a new pack and index name.\n\nNo. The pack file name is composed from the SHA-1 of the sorted SHA-1s\nin the pack. Any change in compression settings or delta windows or\neven just random scheduling variations when repacking can cause\noffsets to slide, even if the set of objects being repacked has not\ndiffered. The resulting pack and index will have the same file names\n(as its the same set of objects), but the offset information and\nordering is now different.\n\nNaming a pack after a SHA-1 is a fun feature. Naming it after the\nSHA-1 of the object list was a mistake. It should have been named\nafter the SHA-1 in the trailer of the file, so that any single bit\nmodified within the pack stream itself would have caused a different\nname to be used on the filesystem. But alas this is water under the\nbridge and not likely to change anytime soon.\n\n>> Yes. One downside is these separate streams aren't removed when you\n>> run git repack. But this could be fixed by a modification to git\n>> repack to clean up additional extensions with the same pack base name.\n>\n> I don't think that's a big deal. We already do it with \".keep\" files. If\n> you repack with an older version of git, you may have a stale\n> supplementary file wasting space. But that's OK. The next time you gc\n> with a newer version of git, we could detect and clean up such stale\n> files (we already do so for tmp_pack_* files).\n\nYes, obviously.\n"},{"id":"200037","messageId":"20120927185229.GD2519@sigill.intra.peff.net","threadId":"31660","inReplyTo":"CAJo=hJs4NXatb2vsZWWCamLGLmi+FoWkTaf3Ky-nereXkHEptA@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T18:52:29Z","receivedAt":"2012-09-27T18:52:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 11:36:19AM -0700, Shawn O. Pearce wrote:\n\n> > Interesting. I would have assumed it depended on order in the index.\n> \n> No. We tried that. Assigning bits by order in index (aka order of\n> SHA-1s sorted) results in horrible compression of the bitmap itself\n> because of the uniform distribution of SHA-1. Encoding instead by pack\n> order gets us really good bitmap compression, because object graph\n> traversal order tends to take reachability into account. So we see\n> long contiguous runs of 1s and get good compression. Sorting by SHA-1\n> just makes the space into swiss cheese.\n\nRight, that makes a lot of sense.\n\n> > I think you are still OK, though, because\n> > the filename comes from the sha1 over the index file, which in turn\n> > includes the sha1 over the packfile. Thus any change in the packfile\n> > would give you a new pack and index name.\n> \n> No. The pack file name is composed from the SHA-1 of the sorted SHA-1s\n> in the pack. Any change in compression settings or delta windows or\n> even just random scheduling variations when repacking can cause\n> offsets to slide, even if the set of objects being repacked has not\n> differed. The resulting pack and index will have the same file names\n> (as its the same set of objects), but the offset information and\n> ordering is now different.\n\nAre you sure? The trailer is computed over the sha1 of the actual pack\ndata (ordering, delta choices, and all), and is computed and written to\nthe packfile via sha1close (see pack-objects.c, ll. 753-763). That\ntrailer sha1 is fed into finish_tmp_packfile (l. 793). That function\nfeeds it to write_idx_file, which starts a new sha1 computation that\nincludes the sorted sha1 list and other index info. But before we\nsha1close that computation, we write the _original_ trailer sha1, adding\nit to the new sha1 calculation. See pack-write.c, ll. 178-180.\n\nAnd then that sha1 gets returned to finish_tmp_packfile, which uses it\nto name the resulting files.\n\nAm I reading the code wrong?\n\n-Peff\n"},{"id":"200042","messageId":"CACPE+fsErzT3MyQdQj5XEvvMwnBam7LBU4XeNVZ+-zG+XYN0cA@mail.gmail.com","threadId":"31660","inReplyTo":"20120927172037.GB1547@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"David Michael Barr","fromEmail":"b@rr-dav.id.au","sentAt":"2012-09-27T19:47:46Z","receivedAt":"2012-09-27T19:47:46Z","isPatch":false,"sender":{"key":"b@rr-dav.id.au","avatar":"https://gravatar.com/avatar/1c0f0df262aa1749c478ee3586cef5da6d58382c06cb220882b7ef9b93cbec6f?d=mp&s=160"},"body":"Hi all,\n\nOn Fri, Sep 28, 2012 at 3:20 AM, Jeff King wrote:\n> On Thu, Sep 27, 2012 at 07:17:42PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> > Operation Index V2 Index VE003\n>> > Clone 37530ms (524.06 MiB) 82ms (524.06 MiB)\n>> > Fetch (1 commit back) 75ms 107ms\n>> > Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB)\n>> > Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB)\n>> > Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB)\n>> > Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB)\n>> > Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB)\n>>\n>> Beautiful. And curious, why do 100->1000 and 10000->10000 have such\n>> big leaps in time (V2)?\n>\n> Agreed. I'm very excited about these numbers.\n\n+1\n\n>> Definitely :-). I have shown my interest in this topic before. So I\n>> should probably say that I'm going to work on this on C Git, but\n>> sllloooowwwly. As this benefits the server side greatly, perhaps a\n>> GitHubber ;-) might want to work on this on C Git, for GitHub itself\n>> of course, and, as a side effect, make the rest of us happy?\n>\n> Yeah, GitHub is definitely interested in this. I may take a shot at it,\n> but I know David Barr (cc'd) is also interested in such things.\n\nYeah, I'm definitely interested, I love this stuff.\n\n--\nDavid Michael Barr\n"},{"id":"200046","messageId":"20120927201809.GA11772@sigill.intra.peff.net","threadId":"31660","inReplyTo":"20120927185229.GD2519@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T20:18:09Z","receivedAt":"2012-09-27T20:18:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 02:52:29PM -0400, Jeff King wrote:\n\n> > No. The pack file name is composed from the SHA-1 of the sorted SHA-1s\n> > in the pack. Any change in compression settings or delta windows or\n> > even just random scheduling variations when repacking can cause\n> > offsets to slide, even if the set of objects being repacked has not\n> > differed. The resulting pack and index will have the same file names\n> > (as its the same set of objects), but the offset information and\n> > ordering is now different.\n> \n> Are you sure? The trailer is computed over the sha1 of the actual pack\n> data (ordering, delta choices, and all), and is computed and written to\n> the packfile via sha1close (see pack-objects.c, ll. 753-763). That\n> trailer sha1 is fed into finish_tmp_packfile (l. 793). That function\n> feeds it to write_idx_file, which starts a new sha1 computation that\n> includes the sorted sha1 list and other index info. But before we\n> sha1close that computation, we write the _original_ trailer sha1, adding\n> it to the new sha1 calculation. See pack-write.c, ll. 178-180.\n> \n> And then that sha1 gets returned to finish_tmp_packfile, which uses it\n> to name the resulting files.\n> \n> Am I reading the code wrong?\n\nAnd the answer is...yes. I'm blind.\n\nThe final bit of code in write_idx_file is:\n\n sha1write(f, sha1, 20);\n sha1close(f, NULL, ((opts->flags & WRITE_IDX_VERIFY)\n ? CSUM_CLOSE : CSUM_FSYNC));\n git_SHA1_Final(sha1, &ctx);\n\nSo we write the trailer, but the sha1 we pull out is _not_ the sha1 over\nthe index format. It is from \"ctx\", not \"f\"; and hte former is from the\nobject list. Just like you said. :)\n\nSo yeah, we would want to put the pack trailer sha1 into the\nsupplementary index file, and check that it matches when we open it.\nIt's a slight annoyance, but it's O(1).\n\nAnything which rewrote the pack and index would also want to rewrite\nthese supplementary files. So the worst case would be:\n\n 1. Pack with a new version which builds the supplementary file.\n\n 2. Repack with an old version which generates a pack with identical\n objects, but different ordering. It does not regenerate the\n supplementary file, because it does not know about it.\n\n 3. Try to read with newer git.\n\nWithout the extra trailer check, we get a wrong answer. With the check,\nwe notice that the supplementary file is bogus, and fallback to the slow\npath. Which I think is OK, considering that this is a reasonably\nunlikely scenario to come up often (and it is no slower than it would be\nif you generated a _new_ packfile in step 2).\n\n-Peff\n"},{"id":"200050","messageId":"7vfw63p2wi.fsf@alter.siamese.dyndns.org","threadId":"31660","inReplyTo":"20120927201809.GA11772@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-27T21:33:01Z","receivedAt":"2012-09-27T21:33:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So yeah, we would want to put the pack trailer sha1 into the\n> supplementary index file, and check that it matches when we open it.\n> It's a slight annoyance, but it's O(1).\n\nYes. If I am not mistaken, that is exactly how an .idx file makes\nsure that it describes the matching .pack file (it has packfile\nchecksum in its trailer). Otherwise you can repack the same set of\nobjects into a new .pack file and make existing .idx very confused.\n"},{"id":"200051","messageId":"20120927213602.GA12512@sigill.intra.peff.net","threadId":"31660","inReplyTo":"7vfw63p2wi.fsf@alter.siamese.dyndns.org","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T21:36:02Z","receivedAt":"2012-09-27T21:36:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 02:33:01PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > So yeah, we would want to put the pack trailer sha1 into the\n> > supplementary index file, and check that it matches when we open it.\n> > It's a slight annoyance, but it's O(1).\n> \n> Yes. If I am not mistaken, that is exactly how an .idx file makes\n> sure that it describes the matching .pack file (it has packfile\n> checksum in its trailer). Otherwise you can repack the same set of\n> objects into a new .pack file and make existing .idx very confused.\n\nYeah. In theory you wouldn't name the new packfile into place without\nalso generating a new index for it. But even if you do it right, there's\na race condition, and checking the trailer sha1 at least lets us know\nthat they don't match (I assume we just reject the index, then; I guess\nthis can result in an operation failing, but in practice it doesn't\nreally happen, as we don't bother packing unless there are actually new\nobjects).\n\n-Peff\n"},{"id":"200061","messageId":"CACsJy8AbVi-uR2-5Ndz3cTAzz_=xahOSpTBGOsB2XdYTsYtG6w@mail.gmail.com","threadId":"31660","inReplyTo":"CAJo=hJt0PdpDT5ROUSfZ80Zh2ep=r5Sg1BS=v7Ve-djydHhp-w@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-28T01:37:09Z","receivedAt":"2012-09-28T01:37:09Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 27, 2012 at 9:33 PM, Shawn Pearce wrote:\n>> I'd like to see some sort of extension mechanism like in\n>> $GIT_DIR/index, so that we don't have to increase pack index version\n>> often.\n>\n> This might be worthwhile. I dislike the way $GIT_DIR/index encodes\n> extensions. Forcing an extension to fully materialize itself to\n> determine its length so the length can be placed before the data is\n> painful to work with when writing the file out to disk. I would prefer\n> writing an index catalog at the trailer of the file. We already\n> require random access to the index file, so its possible for a reader\n> to read a fixed size trailer record that has the 2 SHA-1s we normally\n> end an index with, and an extension catalog footer that has a length\n> and CRC-32 of the catalog. The catalog would immediately appear before\n> the footer, so a reader can find the start of the extension catalog by\n> subtracting from the end of the file the catalog length and the file\n> footer and catalog footer lengths. The catalog can then supply a\n> starting offset for each extension section, and writers don't need to\n> predict in advance how much data they need to store. Readers trying to\n> use extensions aren't really hurt, Git already randomly seeks to read\n> the tail of an index file to compare the pack SHA-1 before assuming\n> the index is valid.\n\nYeah, that's exactly what I had in mind. But perhaps a separate file\n(or files?) may be better. On that point, should all extensions be in\none new extra file, or one extension per file? I prefer all extensions\nin one file, so we only need a single additional stat() for extension\ncheck instead of probing for the entire pack-XXX.* range. In that\ncase, the catalog trailer idea still applies.\n-- \nDuy\n"},{"id":"200062","messageId":"CACsJy8BCoCqD=CGxbibpUiW2f1D9nn3MPFvRASqad1RPeehSow@mail.gmail.com","threadId":"31660","inReplyTo":"20120927172037.GB1547@sigill.intra.peff.net","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-28T01:38:15Z","receivedAt":"2012-09-28T01:38:15Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Sep 28, 2012 at 12:20 AM, Jeff King wrote:\n>> Definitely :-). I have shown my interest in this topic before. So I\n>> should probably say that I'm going to work on this on C Git, but\n>> sllloooowwwly. As this benefits the server side greatly, perhaps a\n>> GitHubber ;-) might want to work on this on C Git, for GitHub itself\n>> of course, and, as a side effect, make the rest of us happy?\n>\n> Yeah, GitHub is definitely interested in this. I may take a shot at it,\n> but I know David Barr (cc'd) is also interested in such things.\n\nGreat. Now I can just sit back and enjoy :)\n-- \nDuy\n"},{"id":"200085","messageId":"CACsJy8AUdRyjSrAgM+ABzWet2NKz7N7M4re2QVoRPrrA=zfvvg@mail.gmail.com","threadId":"31660","inReplyTo":"CAJo=hJstK1tGrWhtBt3s+R1a6C0ge3wMtJnoo43Fjfg5A57eVw@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-28T12:00:28Z","receivedAt":"2012-09-28T12:00:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 27, 2012 at 7:47 AM, Shawn Pearce wrote:\n> * https://git.eclipse.org/r/7939\n>\n> Defines the new E003 index format and the bit set\n> implementation logic.\n\nQuote from the patch's message:\n\n\"Currently, the new index format can only be used with pack files that\ncontain a complete closure of the object graph e.g. the result of a\ngarbage collection.\"\n\nYou mentioned this before in your idea mail a while back. I wonder if\nit's worth storing bitmaps for all packs, not just the self contained\nones. We could have one leaf bitmap per pack to mark all leaves where\nwe'll need to traverse outside the pack. Commit leaves are the best as\nwe can potentially reuse commit bitmaps from other packs. Tree leaves\nwill be followed in the normal/slow way.\n\nFor connectivity check, fewer trees/commits to deflate/parse means\nless time. And connectivity check is done on every git-fetch (I\nsuspect the other end of a push also has the same check). It's not\nunusual for me to fetch some repos once every few months so these\nincomplete packs could be quite big and it'll take some time for gc\n--auto to kick in (of course we could adjust gc --auto to start based\non the number of non-bitmapped objects, in additional to number of\npacks).\n-- \nDuy\n"},{"id":"200228","messageId":"CAJo=hJsWczUqhvj6Kqsomeh9WxAAJO-Yc-=61k94jos6vVtEjQ@mail.gmail.com","threadId":"31660","inReplyTo":"CACsJy8AUdRyjSrAgM+ABzWet2NKz7N7M4re2QVoRPrrA=zfvvg@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-01T01:07:45Z","receivedAt":"2012-10-01T01:07:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Sep 28, 2012 at 5:00 AM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Sep 27, 2012 at 7:47 AM, Shawn Pearce wrote:\n>> * https://git.eclipse.org/r/7939\n>>\n>> Defines the new E003 index format and the bit set\n>> implementation logic.\n>\n> Quote from the patch's message:\n>\n> \"Currently, the new index format can only be used with pack files that\n> contain a complete closure of the object graph e.g. the result of a\n> garbage collection.\"\n>\n> You mentioned this before in your idea mail a while back. I wonder if\n> it's worth storing bitmaps for all packs, not just the self contained\n> ones.\n\nColby and I started talking about this late last week too. It seems\nfeasible, but does add a bit more complexity to the algorithm used\nwhen enumerating.\n\n> We could have one leaf bitmap per pack to mark all leaves where\n> we'll need to traverse outside the pack. Commit leaves are the best as\n> we can potentially reuse commit bitmaps from other packs. Tree leaves\n> will be followed in the normal/slow way.\n\nYes, Colby proposed the same idea.\n\nWe cannot make a \"leaf bitmap per pack\". The leaf SHA-1s are not in\nthe pack and therefore cannot have a bit assigned to them. We could\nadd a new section that listed the unique leaf SHA-1s in their own\nprivate table, and then assigned per bitmap a leaf bitmap that set to\n1 for any leaf object that is outside of the pack. This would probably\ntake up the least amount of disk space, vs. storing the list of leaf\nSHA-1s after each bitmap. If a pack has only 1 bitmap (e.g. it is a\nsmall chunk of recent history) there is really no difference in disk\nusage. If the pack has 2 or 3 commit bitmaps along a string of\napproximately 300 commits, you will have an identical leaf set for\neach of those bitmaps so using a single leaf SHA-1 table would support\nreusing the redundant leaf pointers.\n\nOne of the problems we have seen with these non-closed packs is they\nwaste an incredible amount of disk. As an example, do a `git fetch`\nfrom Linus tree when you are more than a few weeks behind. You will\nget back more than 100 objects, so the thin pack will be saved and\ncompleted with additional base objects. That thin pack will go from a\nfew MiBs to more than 40 MiB of data on disk, thanks to the redundant\nbase objects being appended to the end of the pack. For most uses\nthese packs are best eliminated and replaced with a new complete\nclosure pack. The redundant base objects disappear, and Git stops\nwasting a huge amount of disk.\n\n> For connectivity check, fewer trees/commits to deflate/parse means\n> less time. And connectivity check is done on every git-fetch (I\n> suspect the other end of a push also has the same check). It's not\n> unusual for me to fetch some repos once every few months so these\n> incomplete packs could be quite big and it'll take some time for gc\n> --auto to kick in (of course we could adjust gc --auto to start based\n> on the number of non-bitmapped objects, in additional to number of\n> packs).\n\nYes, of course.\n"},{"id":"200231","messageId":"CACsJy8D5AXSWAdK7tgtXnE4Ro_+okaYM=zf9JnQfObkcx=FCOw@mail.gmail.com","threadId":"31660","inReplyTo":"CAJo=hJsWczUqhvj6Kqsomeh9WxAAJO-Yc-=61k94jos6vVtEjQ@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-01T01:59:17Z","receivedAt":"2012-10-01T01:59:17Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Oct 1, 2012 at 8:07 AM, Shawn Pearce wrote:\n>> You mentioned this before in your idea mail a while back. I wonder if\n>> it's worth storing bitmaps for all packs, not just the self contained\n>> ones.\n>\n> Colby and I started talking about this late last week too. It seems\n> feasible, but does add a bit more complexity to the algorithm used\n> when enumerating.\n\nYes. Though at server side, if it's too much trouble, the packer can\njust ignore open packs and use only closed ones.\n\n>> We could have one leaf bitmap per pack to mark all leaves where\n>> we'll need to traverse outside the pack. Commit leaves are the best as\n>> we can potentially reuse commit bitmaps from other packs. Tree leaves\n>> will be followed in the normal/slow way.\n>\n> Yes, Colby proposed the same idea.\n>\n> We cannot make a \"leaf bitmap per pack\". The leaf SHA-1s are not in\n> the pack and therefore cannot have a bit assigned to them.\n\nWe could mark all objects _in_ the pack that lead to an external\nobject. That's what I meant by leaves. We need to parse the leaves to\nfind out actual SHA-1s that are outside the pack. Or we could go with\nyour approach below too.\n\n> We could\n> add a new section that listed the unique leaf SHA-1s in their own\n> private table, and then assigned per bitmap a leaf bitmap that set to\n> 1 for any leaf object that is outside of the pack.\n\n\n> One of the problems we have seen with these non-closed packs is they\n> waste an incredible amount of disk. As an example, do a `git fetch`\n> from Linus tree when you are more than a few weeks behind. You will\n> get back more than 100 objects, so the thin pack will be saved and\n> completed with additional base objects. That thin pack will go from a\n> few MiBs to more than 40 MiB of data on disk, thanks to the redundant\n> base objects being appended to the end of the pack. For most uses\n> these packs are best eliminated and replaced with a new complete\n> closure pack. The redundant base objects disappear, and Git stops\n> wasting a huge amount of disk.\n\nThat's probably a different problem. I appreciate disk savings but I\nwould not want to wait a few more minutes for repack on every\ngit-fetch. But if this bitmap thing makes repack much faster than\ncurrently, repacking after every git-fetch may become practical.\n-- \nDuy\n"},{"id":"200233","messageId":"CAJo=hJs8TcU=Vvq4Re2aqTUrgRqiSyHs1rA+fPDHUkvrhwc3OA@mail.gmail.com","threadId":"31660","inReplyTo":"CACsJy8D5AXSWAdK7tgtXnE4Ro_+okaYM=zf9JnQfObkcx=FCOw@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-01T02:26:44Z","receivedAt":"2012-10-01T02:26:44Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Sep 30, 2012 at 6:59 PM, Nguyen Thai Ngoc Duy wrote:\n> On Mon, Oct 1, 2012 at 8:07 AM, Shawn Pearce wrote:\n>>> You mentioned this before in your idea mail a while back. I wonder if\n>>> it's worth storing bitmaps for all packs, not just the self contained\n>>> ones.\n>>\n>> Colby and I started talking about this late last week too. It seems\n>> feasible, but does add a bit more complexity to the algorithm used\n>> when enumerating.\n>\n> Yes. Though at server side, if it's too much trouble, the packer can\n> just ignore open packs and use only closed ones.\n\nIts not trouble once the code is written. We were just trying to be\nexpedient in producing a prototype that we could start to deploy on\nreal-world workloads. Enumerating the non-closed-pack objects using\nthe classical implementation is still slow and consumes CPU time at\nthe server, using partial bitmaps should eliminate most of that CPU\nusage and reduce server loads.\n\nOne of the more troublesome problems is building the bitmaps is\ndifficult from a streaming processor like index-pack. You need the\nreachability graph for all objects, which is not currently produced\nwhen moving data over the wire. We do an fsck after-the-fact to verify\nwe didn't get corrupt data, but this is optional and currently after\nthe pack is stored. We need to refactor this code to run earlier to\nget the bitmap built. If we take Peff's idea and put the bitmap data\ninto a new stream rather than the pack-*.idx file we can produce the\nbitmap at the same time as the fsck check, which is probably a simpler\nchange.\n\n>>> We could have one leaf bitmap per pack to mark all leaves where\n>>> we'll need to traverse outside the pack. Commit leaves are the best as\n>>> we can potentially reuse commit bitmaps from other packs. Tree leaves\n>>> will be followed in the normal/slow way.\n>>\n>> Yes, Colby proposed the same idea.\n>>\n>> We cannot make a \"leaf bitmap per pack\". The leaf SHA-1s are not in\n>> the pack and therefore cannot have a bit assigned to them.\n>\n> We could mark all objects _in_ the pack that lead to an external\n> object. That's what I meant by leaves. We need to parse the leaves to\n> find out actual SHA-1s that are outside the pack.\n\nOK, yes, I was being pretty stupid. Of course we could mark the\nobjects _in_ the pack as leaves and parse the leaves when we need to\nfind the external pointers.\n\n> Or we could go with\n> your approach below too.\n\nI actually think my approach may be better. The root tree of a leaf\ncommit would need to be scanned every time to identify trees that are\nreachable from this leaf commit, but are not reachable in the ancestry\nof the leaf's parents. This turns out to be rather expensive to\ncompute every time a server or an fsck algorithm considers the partial\npack. Its also somewhat uncommon for such an object to exist, it has\nto happen by an unrelated side branch introducing the same object and\nthe creator of the pack seeing that object already exist and not\nincluding it in the pack.\n\nDefining the pack's \"edge\" as a list of SHA-1s not in this pack but\nknown to be required allows us to compute that leaf root tree\nreachability once, and never consider parsing it again. Which saves\nservers that host frequently accessed Git repositories but aren't\nrepacking all of the time. (FWIW we repack frequently, I hear GitHub\ndoes too, because a fully repacked repository serves clients better\nthan a partially packed one.)\n\n>> We could\n>> add a new section that listed the unique leaf SHA-1s in their own\n>> private table, and then assigned per bitmap a leaf bitmap that set to\n>> 1 for any leaf object that is outside of the pack.\n>\n>> One of the problems we have seen with these non-closed packs is they\n>> waste an incredible amount of disk. As an example, do a `git fetch`\n>> from Linus tree when you are more than a few weeks behind. You will\n>> get back more than 100 objects, so the thin pack will be saved and\n>> completed with additional base objects. That thin pack will go from a\n>> few MiBs to more than 40 MiB of data on disk, thanks to the redundant\n>> base objects being appended to the end of the pack. For most uses\n>> these packs are best eliminated and replaced with a new complete\n>> closure pack. The redundant base objects disappear, and Git stops\n>> wasting a huge amount of disk.\n>\n> That's probably a different problem. I appreciate disk savings but I\n> would not want to wait a few more minutes for repack on every\n> git-fetch. But if this bitmap thing makes repack much faster than\n> currently, repacking after every git-fetch may become practical.\n\nI know the \"Counting objects\" phase of a repack is very expensive, but\nso too is the time required to do the IO in and out of every object in\nthe repository. Spinning disks only transfer data so fast. Assuming\nthe drive can move 50 MiB/s each way, a 500 MiB repository will take\n10 seconds just to write back out the new pack. You aren't ever going\nto want to wait for repacking during git-fetch.\n"},{"id":"200256","messageId":"CACsJy8Aikmf5vwNhLbELLKfyLLPTppWFvoqGOdSBZ2JoL1C_JQ@mail.gmail.com","threadId":"31660","inReplyTo":"CAJo=hJs8TcU=Vvq4Re2aqTUrgRqiSyHs1rA+fPDHUkvrhwc3OA@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-01T12:48:41Z","receivedAt":"2012-10-01T12:48:41Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Oct 1, 2012 at 9:26 AM, Shawn Pearce wrote:\n> One of the more troublesome problems is building the bitmaps is\n> difficult from a streaming processor like index-pack. You need the\n> reachability graph for all objects, which is not currently produced\n> when moving data over the wire. We do an fsck after-the-fact to verify\n> we didn't get corrupt data, but this is optional and currently after\n> the pack is stored. We need to refactor this code to run earlier to\n> get the bitmap built. If we take Peff's idea and put the bitmap data\n> into a new stream rather than the pack-*.idx file we can produce the\n> bitmap at the same time as the fsck check, which is probably a simpler\n> change.\n\nIf we need to go through the whole pack, not random sha-1 access, then\nindex-pack's traversal is more efficient. I have some patches that\nremove pack-check.c and make fsck use index-pack to walk through\npacks. It takes much less time. But rev walk for building bitmaps\nprobably does not fit this style of traversal because rev walk does\nnot align with delta walk.\n\n> Defining the pack's \"edge\" as a list of SHA-1s not in this pack but\n> known to be required allows us to compute that leaf root tree\n> reachability once, and never consider parsing it again. Which saves\n> servers that host frequently accessed Git repositories but aren't\n> repacking all of the time. (FWIW we repack frequently, I hear GitHub\n> does too, because a fully repacked repository serves clients better\n> than a partially packed one.)\n\nProbably off topic. Does saving a list of missing bases in the pack\nindex help storing thin packs directly? I may be missing some points\nbecause I don't see why thin packs cannot be stored on disk in the\nfirst place.\n-- \nDuy\n"},{"id":"200323","messageId":"CAJo=hJtUVLpQaiR==DGdpeH5V5DGh9eF-Ez+gMNNKOyp_HbwVg@mail.gmail.com","threadId":"31660","inReplyTo":"CACsJy8Aikmf5vwNhLbELLKfyLLPTppWFvoqGOdSBZ2JoL1C_JQ@mail.gmail.com","subject":"Re: Using bitmaps to accelerate fetch and clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-02T15:00:54Z","receivedAt":"2012-10-02T15:00:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Oct 1, 2012 at 5:48 AM, Nguyen Thai Ngoc Duy wrote:\n> Probably off topic. Does saving a list of missing bases in the pack\n> index help storing thin packs directly? I may be missing some points\n> because I don't see why thin packs cannot be stored on disk in the\n> first place.\n\nPacks are supposed to be completely self contained. We require all\ndelta bases to be in the pack so that we can always recover the\nobjects stored within it, even if there is no other pack available.\nThis simplifies things like git gc such that they don't need to worry\nabout retaining delta bases for other packs, or avoiding delta chain\ncycles between packs. I have managed to create a A->B->A delta chain\nonce that made the repository corrupt as soon as the last non-delta\ncopy of A as removed. Both A and B became unreadable as A needed B\nwhich needed A which needed B... :-(\n\nTo keep things simple and easily verified as correct, we don't allow this.\n"}]}