{"thread":{"id":"5509","subject":"Re: A look at some alternative PACK file encodings","startedAt":"2006-09-07T09:07:56Z","lastAt":"2006-09-07T19:22:30Z","messageCount":10,"participants":["linux@horizon.com","Jon Smirl","Richard Curnow","A Large Angry SCM","Nicolas Pitre","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26505","messageId":"20060907090756.30111.qmail@science.horizon.com","threadId":"5509","inReplyTo":null,"subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T09:07:56Z","receivedAt":"2006-09-07T09:07:56Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Support for 'thin' packs would pretty much require mixing IDs and\n> (relative) offsets in the same pack file.\n\nAn alternative would be to create a small \"placeholder\" object that\njust gives an ID, then refer to it by offset.\n\nThat would avoid the need for an id/offset bit with every offset,\nand possibly save more space if the same object was referenced\nmultiple times.\n\nAnd it just seems simpler.\n"},{"id":"26516","messageId":"9e4733910609070557jd8cfc57nd4f7a8973b69f6ed@mail.gmail.com","threadId":"5509","inReplyTo":"20060907090756.30111.qmail@science.horizon.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T12:57:02Z","receivedAt":"2006-09-07T12:57:02Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 7 Sep 2006 05:07:56 -0400, linux@horizon.com wrote:\n> > Support for 'thin' packs would pretty much require mixing IDs and\n> > (relative) offsets in the same pack file.\n>\n> An alternative would be to create a small \"placeholder\" object that\n> just gives an ID, then refer to it by offset.\n>\n> That would avoid the need for an id/offset bit with every offset,\n> and possibly save more space if the same object was referenced\n> multiple times.\n>\n> And it just seems simpler.\n\nThere are 2 million objects in the Mozilla pack. This table would take:\n2M * (20b (sha) + 10b(object index/overhead) = 60MB\nThis 60MB is pretty much incompressible and increases download time.\n\nMuch better if storage of the sha1s can be totally eliminated and\nreplaced by something smaller. Alternatively this map could be\nstripped for transmission and rebuilt locally.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26522","messageId":"20060907133456.24226.qmail@science.horizon.com","threadId":"5509","inReplyTo":"9e4733910609070557jd8cfc57nd4f7a8973b69f6ed@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T13:34:56Z","receivedAt":"2006-09-07T13:34:56Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":">> An alternative would be to create a small \"placeholder\" object that\n>> just gives an ID, then refer to it by offset.\n>>\n>> That would avoid the need for an id/offset bit with every offset,\n>> and possibly save more space if the same object was referenced\n>> multiple times.\n>>\n>> And it just seems simpler.\n\n> There are 2 million objects in the Mozilla pack. This table would take:\n> 2M * (20b (sha) + 10b(object index/overhead) = 60MB\n> This 60MB is pretty much incompressible and increases download time.\n> \n> Much better if storage of the sha1s can be totally eliminated and\n> replaced by something smaller. Alternatively this map could be\n> stripped for transmission and rebuilt locally.\n\nUm, I think I wasn't clear. Objects in a \"thin\" pack (for network\nupdating of a different pack) that are referred to but not included\nwould have stand-ins containing just the object ID. Objects that *are*\npresent would simply be present and referred to by offset as usual.\n\nImagine you have a \"thin\" pack containing a delta to an object that the\nrecipient has, so isn't in the pack. The delta has to specify the\nbase object somehow. If the base object is in the pack, you can\nspecify it by offset. If it's not, you can either:\n\n- Generalize the base object pointer to allow an object ID option, or\n- Provide a pointer to a magic kind of \"external reference\" pointer\n object.\n\nI was proposing the latter.\n\nFor regular packs, such objects wouldn't even be present, because\nall base objects are in the pack itself.\n\nAnd, of course, you'd only create such objects if you needed to,\nif there was at least one pointer to them.\n\nCompared to putting the object ID directly in the pointer, it has\nCost:\tAn extra offset pointer and object header.\n\tExtra time follwoing the indirection resolving the pointer.\nBenefit: Non-indirect object pointers are a bit smaller.\n\tThe code is simpler.\n\tSecond and later references to the same external object are\n\tanother offset, not another 20 bytes.\n"},{"id":"26523","messageId":"9e4733910609070719g42ff7d9buf4b798a9c6b3a7ee@mail.gmail.com","threadId":"5509","inReplyTo":"20060907133456.24226.qmail@science.horizon.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T14:19:03Z","receivedAt":"2006-09-07T14:19:03Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 7 Sep 2006 09:34:56 -0400, linux@horizon.com wrote:\n> >> An alternative would be to create a small \"placeholder\" object that\n> >> just gives an ID, then refer to it by offset.\n> >>\n> >> That would avoid the need for an id/offset bit with every offset,\n> >> and possibly save more space if the same object was referenced\n> >> multiple times.\n> >>\n> >> And it just seems simpler.\n>\n> > There are 2 million objects in the Mozilla pack. This table would take:\n> > 2M * (20b (sha) + 10b(object index/overhead) = 60MB\n> > This 60MB is pretty much incompressible and increases download time.\n> >\n> > Much better if storage of the sha1s can be totally eliminated and\n> > replaced by something smaller. Alternatively this map could be\n> > stripped for transmission and rebuilt locally.\n>\n> Um, I think I wasn't clear. Objects in a \"thin\" pack (for network\n> updating of a different pack) that are referred to but not included\n> would have stand-ins containing just the object ID. Objects that *are*\n> present would simply be present and referred to by offset as usual.\n\nYes I missed the thin pack context. Has anyone tried building a thin\npack? Having thin packs would address major concerns with the download\ntime of the initial Mozilla checkout. Right now you have to download\n450MB of data that 99% of the people are never going to look at.\n\nThin packs would also set an 'archival' bit as discussed earlier. The\n'archival' bit tells the local tools to leave these packs alone. You\ndon't want to accidentally trigger a 450MB down just because you did a\ngit-repack. Of course git would need to developer error messages\nindicating that you asked for something in the archive that isn't\npresent.\n\nI'm not sure I would mix these external references in with other\nobjects. Instead I would make a pair of packs, one only contains\nexternal reference stubs and is tiny. The second is the full version\nof the same data. That makes getting the old data easy, it just\nreplaces the stub pack. The stub pack doesn't need to contain stubs\nfor all the objects, only the ones referenced upstream.\n\nI haven't tried doing this, does the current git code support having\nmultiple pack files covering difference pieces of the project? Can we\nhave an archive pack and a local current pack that get merged\ntogether?\n\n> Imagine you have a \"thin\" pack containing a delta to an object that the\n> recipient has, so isn't in the pack. The delta has to specify the\n> base object somehow. If the base object is in the pack, you can\n> specify it by offset. If it's not, you can either:\n>\n> - Generalize the base object pointer to allow an object ID option, or\n> - Provide a pointer to a magic kind of \"external reference\" pointer\n> object.\n>\n> I was proposing the latter.\n>\n> For regular packs, such objects wouldn't even be present, because\n> all base objects are in the pack itself.\n>\n> And, of course, you'd only create such objects if you needed to,\n> if there was at least one pointer to them.\n>\n> Compared to putting the object ID directly in the pointer, it has\n> Cost: An extra offset pointer and object header.\n> Extra time follwoing the indirection resolving the pointer.\n> Benefit: Non-indirect object pointers are a bit smaller.\n> The code is simpler.\n> Second and later references to the same external object are\n> another offset, not another 20 bytes.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26526","messageId":"loom.20060907T163036-849@post.gmane.org","threadId":"5509","inReplyTo":"20060907133456.24226.qmail@science.horizon.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Richard Curnow","fromEmail":"rc@rc0.org.uk","sentAt":"2006-09-07T14:39:39Z","receivedAt":"2006-09-07T14:39:39Z","isPatch":false,"sender":{"key":"rc@rc0.org.uk","avatar":null},"body":" horizon.com> writes:\n\n> \n> For regular packs, such objects wouldn't even be present, because\n> all base objects are in the pack itself.\n> \n\nIt would actually be useful if this restriction were lifted.\n\nGranted, for working repositories there's not much point, because 'git repack -a\n-d' can be run regularly these days.\n\nBut for repositories served by the dumb http:// transport it makes some sense. \nYou don't want to run 'repack -a -d' on those, because anybody tracking them\nends up having to download the entire history again every time they pull. But\nif you pack too often, you incur the cost of the packs containing lots of base\nobjects - it's as though the delta chain lengths can only ever be about 1 or 2.\n\nIf the packs were thin, regular pullers would already have the base objects, and\noccasional pullers would just have to download more of the intervening (thin)\npacks to get the missing deltas in the middle of the chains. (I think everyone\nhas to download all the .idx files in any case.)\n"},{"id":"26527","messageId":"20060907150143.14238.qmail@science.horizon.com","threadId":"5509","inReplyTo":"9e4733910609070719g42ff7d9buf4b798a9c6b3a7ee@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T15:01:43Z","receivedAt":"2006-09-07T15:01:43Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Yes I missed the thin pack context. Has anyone tried building a thin\n> pack? Having thin packs would address major concerns with the download\n> time of the initial Mozilla checkout. Right now you have to download\n> 450MB of data that 99% of the people are never going to look at.\n\nUnfortunately, no, it wouldn't. There's a second misunderstanding here:\nthin packs are used by the git on-the-wire protocol to send a delta\nrelative to an object *that you know the recipient already has*.\n\nThis can greatly speed up incremental updates. It does NOT have\nany effect on the initial checkout, because you know the recipient\nhas nothing, so you have to send everything.\n\n\nWhat you seem to be talking about is what people call a \"shallow clone\".\nUnfortunately, making a shallow clone is difficult for reasons that\nare deeply embedded in git's incremental update protocol.\n\nWhen you fetch from a remote repository, it needs to figure out what\nyou need and what you already have. The fundamental assumption which\nthe protocol uses to send this efficiently is that if you have a commit\nobject, you have all its ancestors, and their trees and blobs.\n\nSo you can say \"I have 60d4684068ff1eec78f55b5888d0bd2d4cca1520\"\n(which is the commit behind tags/v2.6.18-rc5 from the Linux kernel)\nand the server you're pulling from knows a lot about what you have.\n\nThe first hard part about a shallow repository is describing *efficiently*\nto git-upload-pack what you don't have.\n\nThe second is figuring out what you should get.\n\nSuppose that you clone from a repository that has a linear chain\nof development, and you cut off everything before version X.\nSimple enough so far.\n\nThen you try to pull from someone whose work branched off at version\nX-1. Do you want to fetch everything back to the common ancestor?\nIf you want to cut off their branch, where do we cut it off? A simple\ntimestamp limit? What if you get a bogus timestamp on a commit?\n\nThis has been considered by git developers quite carefully and is NOT\nan easy problem. A solution is welcomed, but if you come up with an\neasy one, please spend a few minutes considering the possibility that\nthe reason it's so easy is that your solution is flawed.\n\nThere are also problems giving sensible error messages if you try to\nrefer to a missing object and making your clone deeper if desired,\nbut those are secondary to the big problems.\n\n> I'm not sure I would mix these external references in with other\n> objects. Instead I would make a pair of packs, one only contains\n> external reference stubs and is tiny. The second is the full version\n> of the same data. That makes getting the old data easy, it just\n> replaces the stub pack. The stub pack doesn't need to contain stubs\n> for all the objects, only the ones referenced upstream.\n\nHuh?? This is flatly impossible, and completely defeats the purpose.\nThis is one of those \"Pray, Mr. Babbage, if you put into the machine\nwrong figures, will the right answers come out?\" questions.\nI think there is a *serious* miscommunication here.\n\nI have a delta-compressed object. It is stored in the pack as a series\nof changes to some base object. To be of any use, it needs to identify\nthat base object. If the base object identification takes the form of\nan intra-pack offset (the new proposal) as opposed to a global 20-byte\nobject ID, then the base object needs to be stored *intra-pack*.\nWithin the same pack.\n\nThe whole idea is \"hey, we don't allow delta-ing relative to objects\nnot in the pack anyway, so why waste space storing such large pointers?\"\n\nThis would make the currently forbidden case of a delta relative to\nan object not in the same pack completely impossible. It's like\nasking for the square root of 2 in roman numerals.\n\n> I haven't tried doing this, does the current git code support having\n> multiple pack files covering difference pieces of the project? Can we\n> have an archive pack and a local current pack that get merged\n> together?\n\nYes, it supports it perfectly. A pack is just a bag of objects. There is\nzero required higher-level structure. In particular, you can have a\n\"100% blobs\" pack with no tree or commit objects at all.\n\nGit uses the object relationships in its compression heuristics, but\nit has no effect on correctness.\n\nThe only thing is that the original pack was a *self-contained* bag of\nobjects; every object in the pack could be reconstructed given only the\npack itself. In particular, cross-pack deltas were forbidden.\n\nHowever, then someone realized that making an exception for git protocol\nupdates would be easy and a Really Good Thing. A pack that is missing\none or more base objects is called a \"thin pack\".\n\nSo the rule I mentioned above has already been broken. Supporting\nthat is what I'm talking about.\n"},{"id":"26529","messageId":"4500556E.7070803@gmail.com","threadId":"5509","inReplyTo":"9e4733910609070557jd8cfc57nd4f7a8973b69f6ed@mail.gmail.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-07T17:22:54Z","receivedAt":"2006-09-07T17:22:54Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 7 Sep 2006 05:07:56 -0400, linux@horizon.com wrote:\n>> > Support for 'thin' packs would pretty much require mixing IDs and\n>> > (relative) offsets in the same pack file.\n>>\n>> An alternative would be to create a small \"placeholder\" object that\n>> just gives an ID, then refer to it by offset.\n>>\n>> That would avoid the need for an id/offset bit with every offset,\n>> and possibly save more space if the same object was referenced\n>> multiple times.\n>>\n>> And it just seems simpler.\n> \n> There are 2 million objects in the Mozilla pack. This table would take:\n> 2M * (20b (sha) + 10b(object index/overhead) = 60MB\n> This 60MB is pretty much incompressible and increases download time.\n> \n> Much better if storage of the sha1s can be totally eliminated and\n> replaced by something smaller. Alternatively this map could be\n> stripped for transmission and rebuilt locally.\n> \n\nYou've lost me. What are you attempting to do again?\n"},{"id":"26531","messageId":"Pine.LNX.4.64.0609071322010.18635@xanadu.home","threadId":"5509","inReplyTo":"20060907090756.30111.qmail@science.horizon.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T17:32:47Z","receivedAt":"2006-09-07T17:32:47Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 7 Sep 2006, linux@horizon.com wrote:\n\n> > Support for 'thin' packs would pretty much require mixing IDs and\n> > (relative) offsets in the same pack file.\n> \n> An alternative would be to create a small \"placeholder\" object that\n> just gives an ID, then refer to it by offset.\n> \n> That would avoid the need for an id/offset bit with every offset,\n> and possibly save more space if the same object was referenced\n> multiple times.\n\nWell... I'm using object type 6 for deltas with offset reference \n(instead of object type 7 that is delta with sha1 reference). So \nthere is no extra bit needed and no backward compatibility breakage.\n\nThere could be of course a new object type which payload is only a sha1 \nthat deltas type 6 reference. But that can be introduced at a later date \nif it turns out to be worthwhile (i.e. the actual saving in real use \nscenarios is worth the (small but still) added complexity).\n\n> And it just seems simpler.\n\nWell I would not say so. Simply prefixing a delta with the sha1 of its \nbase object cannot be simpler when streaming out a pack.\n\n\nNicolas\n"},{"id":"26532","messageId":"7v4pvj1sp9.fsf@assigned-by-dhcp.cox.net","threadId":"5509","inReplyTo":"loom.20060907T163036-849@post.gmane.org","subject":"Re: A look at some alternative PACK file encodings","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T17:40:02Z","receivedAt":"2006-09-07T17:40:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Richard Curnow writes:\n\n> horizon.com> writes:\n>\n>> For regular packs, such objects wouldn't even be present, because\n>> all base objects are in the pack itself.\n>\n> It would actually be useful if this restriction were lifted.\n\nThe primary reason why we require the base object to be present\nin the same pack is because our assumption has always been we\nmmap a pack as a whole, and we assumed that we can make sure\nthat the address space of a process to be enough to mmap at\nleast one pack (otherwise the user will be given a way to keep\nsize of each pack down to a size that is a mmapable piece) but\nnot necessarily more than one. In other words, while unpacking\none object that is deltified, we wanted to make sure everything\nthat is necessary is availble in memory. Otherwise, when\nmultiple packs are needed to reconstitute a single object\nbecause the object is a delta in one pack and its base is in the\nother pack, we might not be able to mmap both of them into the\naddress space at the same time.\n\nThe \"mmap only parts of a huge packfile into map windows\" update\nShawn Pearce is working on would lift that worry, so it would be\nless of a reason.\n\nHaving said that, people must realize that keeping thin packs on\ndisk, indexed, is a major undertaking. It can be made to work,\nbut it will be painful.\n\nPeople can grab a thin pack via rsync or http without realizing\nit is thin, try to use it and then later (possibly much later,\nwhen a delta that is against a missing object happens to be\nneeded) discover some of the pack data is unusable. To avoid\nthis, the dumb transports need to walk the ancestry chains of\ncommits and their associated objects while fetching as they do\nright now, but also need to walk the delta chains to make sure\ntheir base objects are available.\n\nI like the proposal by Linus to have stub objects that records\nwhat the missing base object is in the thin pack stream. It\nsimplifies things for the offset representation of bases. But\nif we were to do so, I suspect indexing such a thing would need\nmore surgery to the .idx format. The question is if we should\nrecord the stub object in the .idx file.\n\nRight now we record the beginning of data for each object\n(either base or delta) without storing anything to say about\nwhere it ends -- the pack is assumed to be dense, so the point\nwhere next object begins should be where the current one ends.\nThis means that we need to build a reverse index to list the\nobjects in the pack in offset order, when we want to find the\nend of each object efficiently.\n\nWe work this around when using a pack by not doing the full\nverification. We start decoding the header from the beginning\nand in either base or delta the deflated stream sits at the end.\nWe inflate that deflated stream until zlib says it got enough,\nand we do not check if that \"enough\" point stepped into the\nlocation that is supposed to be inside the \"next\" object (if it\ndid so then it is an error in the packfile we missed to detect).\nIf things inflate well and delta applies cleanly, we are happy.\n\nBut pack-objects, when reusing the data from an existing pack,\nwants to be careful, so it _does_ build a reverse index itself\nand makes sure that inflate() ends at the location we expect it\nto. For that process to remain the correct way to determine\nwhere each object ends, the .idx file must record the presense\nof stub objects.\n\nHowever, if we write the names of stub objects in the .idx file,\nwe have another problem. Currently, the existence of an object\nname in the .idx means that such an object exists in the\ncorresponding .pack; this will not hold true anymore.\n\nSo if we were to do this, we need to give one extra bit to each\nof the .idx entries to mark which ones are stub and which ones\nare not. This would allow the reverse index to properly notice\nwhere each object ends, and allow the dumb transports to walk\nthe .idx for missing base objects efficiently. The code that\nlooks at .idx at runtime to determine which pack has needed\nobject needs to notice this bit.\n\nAgain, all of this can be made to work, but it will be painful.\n"},{"id":"26535","messageId":"20060907192230.8764.qmail@science.horizon.com","threadId":"5509","inReplyTo":"Pine.LNX.4.64.0609071322010.18635@xanadu.home","subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T19:22:30Z","receivedAt":"2006-09-07T19:22:30Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Well... I'm using object type 6 for deltas with offset reference \n> (instead of object type 7 that is delta with sha1 reference). So \n> there is no extra bit needed and no backward compatibility breakage.\n\nAh, my apologies! I didn't realize that you weren't constructing a\nwhole new pack format, or using a global flag. In this case,\nthe overhead is already bought and paid for, so there's no point\nto not taking advantage of it.\n\nAnd thin packs should Just Work, once the builder is taught to\nuse type 7 objects when necessary.\n\n> There could be of course a new object type which payload is only a sha1 \n> that deltas type 6 reference. But that can be introduced at a later date \n> if it turns out to be worthwhile (i.e. the actual saving in real use \n> scenarios is worth the (small but still) added complexity).\n\nIn this case, it's only of potential benefit if there is more than\none reference to an object, and figuring it out is almost certainly\nmore trouble than it's worth. Deltas usually form long skinny\nchains, not high branching factor bushes.\n"}]}