{"thread":{"id":"14713","subject":"Re: GTP/0.1 terminology 101: commit reels and references","startedAt":"2008-07-28T07:02:50Z","lastAt":"2008-07-29T07:00:47Z","messageCount":7,"participants":["Sam Vilain","Junio C Hamano","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"85256","messageId":"1217228570.6750.24.camel@maia.lan","threadId":"14713","inReplyTo":"488D42B6.4030701@gmail.com","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2008-07-28T07:02:50Z","receivedAt":"2008-07-28T07:02:50Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Josh, I'm cc:'ing the main list with this one as well, as I think it\nfalls into the scope of discussions of wider interest than the rfc- and\nimplementation-specific discussions that (I envisaged would) happen on\nthe gittorrent list.\n\nOn Sun, 2008-07-27 at 23:53 -0400, Joshua Roys wrote:\n> Here's some terms, as best as I understand them.\n> \n> The *Commit Reel* is a sequence of objects between two reference points, \n> sorted in a deterministic fashion.  The two reference points are \n> *Reference* objects, or a signed tag containing a collection of git refs \n> (similar to the output from `git show-ref`).\n\nYes, that's right.  We have the two slightly ambiguous terms, \"refs\",\nwhich mean the same thing as the rest of git, and \"References\", which\nare more like .git/packed-refs.  Perhaps this is a good time to pick a\nbetter name.  \"Slice\" would be an accurate term, though it's certainly\ntempting to pick another term from the tape taxonomy, such as \"Splice\"¹\nor \"Mark\"².\n\n>   Commit reels can also, and generally do, include the objects required\n>  for a specific commit.\n\nYes.  The only times where they wouldn't contain all the objects\nrequired for the commits within the reel, is when those objects happened\nto be contained by a previous reel.\n\nThis is one of the design decisions which I think may be a mistake; a\nless expensive to calculate definition of a reel would be *all* objects\nbetween the starting and ending Reference objects.  The current\ndefinition requires a hash index of objects in each reel, which must be\nconsulted once for all objects when creating the reel index.\n\n> As an example, a commit reel could be the set of objects between the \n> v2.6.25 and v2.6.26 tags of the Linux kernel.  The only thing we would \n> need added to those tags is the list of heads (and tags) at the time of \n> the tagging.\n\nCorrect.  It represents all of the changes in a given repository over a\nperiod of time.\n\n> Those two structures form the basis for two *Peer Wire Protocol* (PWP) \n> messages, Reels and References.\n> \n> Any questions, corrections, or rotten vegetables?\n\nNo, I think that's all good so far...\n\nCheers,\nSam.\n\n¹ - see\nhttp://en.wikipedia.org/wiki/Reel-to-reel_audio_tape_recording#Description\n² - as used by the old unix \"mt\", see eg\nhttp://docs.sun.com/app/docs/doc/816-0210/6m6nb7mf3?a=view\n"},{"id":"85259","messageId":"7vk5f6tqsj.fsf@gitster.siamese.dyndns.org","threadId":"14713","inReplyTo":"1217228570.6750.24.camel@maia.lan","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-28T07:24:12Z","receivedAt":"2008-07-28T07:24:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sam Vilain <sam@vilain.net> writes:\n\n>>   Commit reels can also, and generally do, include the objects required\n>>  for a specific commit.\n>\n> Yes.  The only times where they wouldn't contain all the objects\n> required for the commits within the reel, is when those objects happened\n> to be contained by a previous reel.\n\nWhat do you mean by \"previous\" reel?  It is not quite defined in your\nmessage but perhaps defined elsewhere?\n\nHow is this different from a bundle?  Does a reel, unlike a bundle,\ncontain the full tree for the bottom commits? \n\n> This is one of the design decisions which I think may be a mistake; a\n> less expensive to calculate definition of a reel would be *all* objects\n> between the starting and ending Reference objects.\n\nDo you mean all such objects and nothing else?  That would imply that a\nreel is quite similar to a bundle (but neither rev-list --objects-edge\nnor bundle guarantees that the result is minimal).\n"},{"id":"85265","messageId":"1217239419.6750.73.camel@maia.lan","threadId":"14713","inReplyTo":"7vk5f6tqsj.fsf@gitster.siamese.dyndns.org","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2008-07-28T10:03:39Z","receivedAt":"2008-07-28T10:03:39Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Mon, 2008-07-28 at 00:24 -0700, Junio C Hamano wrote:\n> >>   Commit reels can also, and generally do, include the objects required\n> >>  for a specific commit.\n> >\n> > Yes.  The only times where they wouldn't contain all the objects\n> > required for the commits within the reel, is when those objects happened\n> > to be contained by a previous reel.\n> \n> What do you mean by \"previous\" reel?  It is not quite defined in your\n> message but perhaps defined elsewhere?\n> \n> How is this different from a bundle?  Does a reel, unlike a bundle,\n> contain the full tree for the bottom commits? \n\nThey are almost identical, both being defined by a set of starting and\nending refs.  And now that you mention it, I feel slightly embarrassed\nfor not spotting the connection before.  I only really compared reels to\npacks, which is what the original specification tried to chop up bitwise\nand distribute chunk by chunk.\n\nThe differences are:\n\n  - the reel has a defined object order (which as I hoped to demonstrate\n    in the test cases, is just a refinement of rev-list --date-order)\n\n  - deltas always point in one direction, to objects \"earlier\" on\n    the reel, so that slices of the reel sent on the network can be made\n    thin without resulting in unresolvable deltas (which should be\n    possible to do on commit boundaries using rev-list --objects-edge)\n\n  - the behaviour at the beginning of the reel is precisely defined\n    (although as I said, I think that the decision might be worth\n    revisiting - perhaps getting just the latest reel is a useful\n    'shallow clone')\n\n> > This is one of the design decisions which I think may be a mistake; a\n> > less expensive to calculate definition of a reel would be *all* objects\n> > between the starting and ending Reference objects.\n> \n> Do you mean all such objects and nothing else?  That would imply that a\n> reel is quite similar to a bundle (but neither rev-list --objects-edge\n> nor bundle guarantees that the result is minimal).\n\nIt's the lack of guarantees which is the issue, really.  In order to\ntake the download work of the entire pack and distribute it over\nmultiple peers, you need a way to carve the bundle up.  This has to\nhappen in such a way that the fragments that you get back will actually\nfit together at the end, and also in such a way that you don't lose the\nbenefits of delta compression.\n\nThe way I thought would be best to do that would be to line up all the\nobjects in an exactly defined way - hence, the \"reel\" concept - and then\nchop that up.\n\nIf a pack is already arranged to line up with the commit reel's\nstructure, then it's possible that the amount of work required to answer\na \"play\" request is as little as looking up in the reel index the local\non-disk location within the local pack, and copying that to the network.\n\nI've certainly wondered how much baggage could be removed from this\nwhole thing, like replacing the \"tracker\" with a simple git-daemon\nmessage that holds a register of mirrors/peers, possibly layering things\nover git:// instead of the bittorrent-like protocol, dividing up blocks\nby the commit graph and not all objects, etc.  But I think that it would\nbe best to defer that kind of design change until the conclusion of this\nprototype experiment.\n\nThat being said, anything which does shortcut the distance to the finish\nline and can be agreed on wouldn't go amiss.\n\nSam\n"},{"id":"85281","messageId":"alpine.DEB.1.00.0807281350590.2725@eeepc-johanness","threadId":"14713","inReplyTo":"1217239419.6750.73.camel@maia.lan","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-28T12:01:35Z","receivedAt":"2008-07-28T12:01:35Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 28 Jul 2008, Sam Vilain wrote:\n\n> On Mon, 2008-07-28 at 00:24 -0700, Junio C Hamano wrote:\n>\n> >\n> > >\n> > >> Commit reels can also, and generally do, include the objects \n> > >> required for a specific commit.\n> > >\n> > > Yes.  The only times where they wouldn't contain all the objects \n> > > required for the commits within the reel, is when those objects \n> > > happened to be contained by a previous reel.\n> > \n> > What do you mean by \"previous\" reel?  It is not quite defined in your \n> > message but perhaps defined elsewhere?\n> > \n> > How is this different from a bundle?  Does a reel, unlike a bundle, \n> > contain the full tree for the bottom commits?\n\nAFAICT no, the reel should not contain the full tree for the bottom \ncommit.\n\n> They are almost identical, both being defined by a set of starting and \n> ending refs.  And now that you mention it, I feel slightly embarrassed \n> for not spotting the connection before.  I only really compared reels to \n> packs, which is what the original specification tried to chop up bitwise \n> and distribute chunk by chunk.\n> \n> The differences are:\n> \n>   - the reel has a defined object order (which as I hoped to demonstrate\n>     in the test cases, is just a refinement of rev-list --date-order)\n\nDo you mean that the commit reel is a list pointing to bundles that can be \nsorted topologically by their contained commits?\n\n>   - deltas always point in one direction, to objects \"earlier\" on\n>     the reel, so that slices of the reel sent on the network can be made\n>     thin without resulting in unresolvable deltas (which should be\n>     possible to do on commit boundaries using rev-list --objects-edge)\n\nThat is exactly what bundles do.  They are thin, as they assume that a few \n\"preconditions\", i.e. refs, are present.\n\n>   - the behaviour at the beginning of the reel is precisely defined\n>     (although as I said, I think that the decision might be worth\n>     revisiting - perhaps getting just the latest reel is a useful\n>     'shallow clone')\n\nIf you want to allow shallow clones, you must make the bundles non-thin.  \nThat would be a major bandwidth penalty.\n\nI'd rather not allow shallow clones with Gitorrent.\n\n> > > This is one of the design decisions which I think may be a mistake; \n> > > a less expensive to calculate definition of a reel would be *all* \n> > > objects between the starting and ending Reference objects.\n> > \n> > Do you mean all such objects and nothing else?  That would imply that \n> > a reel is quite similar to a bundle (but neither rev-list \n> > --objects-edge nor bundle guarantees that the result is minimal).\n> \n> It's the lack of guarantees which is the issue, really.\n\nIt should not be too difficult to provide a rev-list option (which is \ninherited by git-bundle, then) to pay an extra time to make sure that the \nbundle is minimal.\n\nBTW this is a good example how communication on the Git mailing list can \nhelp a GSoC project.\n\n> In order to take the download work of the entire pack and distribute it \n> over multiple peers, you need a way to carve the bundle up.  This has to \n> happen in such a way that the fragments that you get back will actually \n> fit together at the end, and also in such a way that you don't lose the \n> benefits of delta compression.\n\nThat should be relatively easy.\n\n> The way I thought would be best to do that would be to line up all the \n> objects in an exactly defined way - hence, the \"reel\" concept - and then \n> chop that up.\n\nWhat exactly is that exact definition?\n\nIs it the output of \"rev-list --all --objects\", chopped into equal chunks \nat commit boundaries?  If so, it should probably be equal in terms of \nsize, right?\n\nThe tricky thing, of course, is to make that thing incremental, i.e. \nreplace only a minimal amount of items in the \"commit reel\" (if I \nunderstood correctly, and the commit reel refers to a list of sets of \ncommits with their objects) when a branch was modified.\n\nHmm.  Maybe it would be time for you to draw a tiny diagram for all the \npeople too lazy like me, which shows roughly how the communication between \nthe peers should look like, and how the reel fits in.\n\nCiao,\nDscho\n"},{"id":"85324","messageId":"1217273166.25690.20.camel@maia.lan","threadId":"14713","inReplyTo":"alpine.DEB.1.00.0807281350590.2725@eeepc-johanness","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2008-07-28T19:26:06Z","receivedAt":"2008-07-28T19:26:06Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Mon, 2008-07-28 at 14:01 +0200, Johannes Schindelin wrote:\n> >   - the reel has a defined object order (which as I hoped to demonstrate\n> >     in the test cases, is just a refinement of rev-list --date-order)\n> \n> Do you mean that the commit reel is a list pointing to bundles that can be \n> sorted topologically by their contained commits?\n\nYes, but it is more defined than that.  There are still ambiguities with\ntopological sort, so the gittorrent spec specified exactly how all ties\nare broken.  They happen to be a further refinement of --date-order,\nwith respect to the ordering of commits.\n\n> >   - deltas always point in one direction, to objects \"earlier\" on\n> >     the reel, so that slices of the reel sent on the network can be made\n> >     thin without resulting in unresolvable deltas (which should be\n> >     possible to do on commit boundaries using rev-list --objects-edge)\n> That is exactly what bundles do.  They are thin, as they assume that a few \n> \"preconditions\", i.e. refs, are present.\n\nOk.  I think there are also some other trivial differences such as\nbundles containing refs (which in the context of gittorrent will be\nuseless).\n\n> >   - the behaviour at the beginning of the reel is precisely defined\n> >     (although as I said, I think that the decision might be worth\n> >     revisiting - perhaps getting just the latest reel is a useful\n> >     'shallow clone')\n> \n> If you want to allow shallow clones, you must make the bundles non-thin.  \n> That would be a major bandwidth penalty.\n> \n> I'd rather not allow shallow clones with Gitorrent.\n\nBy \"Shallow\" I think I mean a different thing to you.  I mean something\nakin to just the last pack's worth of commits.\n\n> > It's the lack of guarantees which is the issue, really.\n> \n> It should not be too difficult to provide a rev-list option (which is \n> inherited by git-bundle, then) to pay an extra time to make sure that the \n> bundle is minimal.\n\nOk.  But from the current implementation's perspective, this is not yet\nneeded, we are just using the existing API.\n\nActually what would be useful would be for the thin pack generation to\nalso allow any object to be specified as its input list, not just\ncommits... then we wouldn't have to break blocks on commit boundaries\n(see http://gittorrent.utsl.gen.nz/rfc.html#org-blocks).\n\n> > In order to take the download work of the entire pack and distribute it \n> > over multiple peers, you need a way to carve the bundle up.  This has to \n> > happen in such a way that the fragments that you get back will actually \n> > fit together at the end, and also in such a way that you don't lose the \n> > benefits of delta compression.\n> \n> That should be relatively easy.\n> \n> > The way I thought would be best to do that would be to line up all the \n> > objects in an exactly defined way - hence, the \"reel\" concept - and then \n> > chop that up.\n> \n> What exactly is that exact definition?\n\nhttp://gittorrent.utsl.gen.nz/rfc.html#org-reels\n\n> Is it the output of \"rev-list --all --objects\", chopped into equal chunks \n> at commit boundaries?  If so, it should probably be equal in terms of \n> size, right?\n\nNo.  It's chopped by uncompressed size.\n\nhttp://gittorrent.utsl.gen.nz/rfc.html#org-blocks\n\n> The tricky thing, of course, is to make that thing incremental, i.e. \n> replace only a minimal amount of items in the \"commit reel\" (if I \n> understood correctly, and the commit reel refers to a list of sets of \n> commits with their objects) when a branch was modified.\n\nYou would make a new reel to cover a new bunch of updates.  It's\nimportant that the reels don't change too often for reasons I describe\nin the RFC.\n\n> Hmm.  Maybe it would be time for you to draw a tiny diagram for all the \n> people too lazy like me, which shows roughly how the communication between \n> the peers should look like, and how the reel fits in.\n\nAs I said in my recent message to the list, I wrote another top level\noverview here:\n\nhttp://gittorrent.utsl.gen.nz/rfc.html#org-blocks\n\nCheers,\nSam.\n"},{"id":"85347","messageId":"alpine.DEB.1.00.0807290014110.2725@eeepc-johanness","threadId":"14713","inReplyTo":"1217273166.25690.20.camel@maia.lan","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-28T22:30:49Z","receivedAt":"2008-07-28T22:30:49Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Sam Vilain wrote:\n\n> On Mon, 2008-07-28 at 14:01 +0200, Johannes Schindelin wrote:\n> > >   - the reel has a defined object order (which as I hoped to \n> > >     demonstrate in the test cases, is just a refinement of rev-list \n> > >     --date-order)\n> > \n> > Do you mean that the commit reel is a list pointing to bundles that \n> > can be sorted topologically by their contained commits?\n> \n> Yes, but it is more defined than that.  There are still ambiguities with \n> topological sort, so the gittorrent spec specified exactly how all ties \n> are broken.  They happen to be a further refinement of --date-order, \n> with respect to the ordering of commits.\n\nBut does that not mean that any new ref branching off of an ancient commit \nchanges all the pack boundaries?\n\nI'd rather have an intelligent incremental updater, and keep most of the \nexisting bundles immutable.  That way, a new ref, or a changed one, can be \nmostly served from peers, not exclusively from the seeders.\n\n> > >   - deltas always point in one direction, to objects \"earlier\" on \n> > >     the reel, so that slices of the reel sent on the network can be \n> > >     made thin without resulting in unresolvable deltas (which should \n> > >     be possible to do on commit boundaries using rev-list \n> > >     --objects-edge)\n> >\n> > That is exactly what bundles do.  They are thin, as they assume that a \n> > few \"preconditions\", i.e. refs, are present.\n> \n> Ok.  I think there are also some other trivial differences such as \n> bundles containing refs (which in the context of gittorrent will be \n> useless).\n\nYeah, I think that bundles themselves are pretty useless in gitorrent.  \nBut what they _contain_ is pretty much what you need as blocks.\n\n> > >   - the behaviour at the beginning of the reel is precisely defined \n> > >     (although as I said, I think that the decision might be worth \n> > >     revisiting - perhaps getting just the latest reel is a useful \n> > >     'shallow clone')\n> > \n> > If you want to allow shallow clones, you must make the bundles \n> > non-thin.  That would be a major bandwidth penalty.\n> > \n> > I'd rather not allow shallow clones with Gitorrent.\n> \n> By \"Shallow\" I think I mean a different thing to you.  I mean something \n> akin to just the last pack's worth of commits.\n\nThat _is_ a shallow clone.  And that is exactly what I meant.  If you want \nto have all objects of the commits in the same pack, then you are \nbasically making fat packs.  Which come with a hefty bandwidth penalty.\n\nThat is why I would suggest not allowing shallow clones; if you want to \nallow them, I have to ask myself why bother with a torrent at all...  It \nis not like the shallow clones are large, or that the people fetching them \nwill stay around long to seed anything, and the packs would change \nfrequently, making the whole torrent business pretty inefficient.\n\n> > > It's the lack of guarantees which is the issue, really.\n> > \n> > It should not be too difficult to provide a rev-list option (which is \n> > inherited by git-bundle, then) to pay an extra time to make sure that \n> > the bundle is minimal.\n> \n> Ok.  But from the current implementation's perspective, this is not yet \n> needed, we are just using the existing API.\n\nWhy make it hard?  We have a lively community with brilliant people, and \nthey frequently have fun solving puzzles like this: what is the best \nstrategy to make equally sized, rarely (or maybe never?) changing packs \nfrom a set of given refs.\n\n> Actually what would be useful would be for the thin pack generation to \n> also allow any object to be specified as its input list, not just \n> commits... then we wouldn't have to break blocks on commit boundaries \n> (see http://gittorrent.utsl.gen.nz/rfc.html#org-blocks).\n\nThat should be easy, but I think that it would be _even better_ if we ask \npack-objects to generate several packs from the needed objects.  Ooops.  \nThat already exists: \n\n\t$ git pack-objects --max-pack-size=<n>\n\nStoring the packs in a second GIT_OBJECT_DIRECTORY that has the \noriginal as an alternate, together with the --local flag, should help even \nfurther: You can mark the last pack (which does not reach max-pack-size, \nmost likely), remove it and just rerun the packing.\n\nOf course, this needs some thought when large chunks of the object \ndatabase become stale when a long branch was just deleted.  Not a major \nobstacle, though.\n\nCiao,\nDscho\n"},{"id":"85427","messageId":"1217314847.28919.98.camel@maia.lan","threadId":"14713","inReplyTo":"alpine.DEB.1.00.0807290014110.2725@eeepc-johanness","subject":"Re: GTP/0.1 terminology 101: commit reels and references","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2008-07-29T07:00:47Z","receivedAt":"2008-07-29T07:00:47Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Tue, 2008-07-29 at 00:30 +0200, Johannes Schindelin wrote:\n> > Yes, but it is more defined than that.  There are still ambiguities with \n> > topological sort, so the gittorrent spec specified exactly how all ties \n> > are broken.  They happen to be a further refinement of --date-order, \n> > with respect to the ordering of commits.\n> \n> But does that not mean that any new ref branching off of an ancient commit \n> changes all the pack boundaries?\n\nNo.  A \"References\" object is a snapshot of all refs at a particular\ntime.  If you want to make a new ref you make a new \"References\" object.\n*all* of the new objects are contained in the new reel, and the new\nreels do not affect the old reels.\n\n> That should be easy, but I think that it would be _even better_ if we ask \n> pack-objects to generate several packs from the needed objects.  Ooops.  \n> That already exists: \n> \n> \t$ git pack-objects --max-pack-size=<n>\n\nThis does not deterministically generate the same pack for a given set of\nrefs across all git versions.\n\nYour ideas would have been excellent earlier on, perhaps if developed\nthey might have resulted in something quite a bit simpler with all of\nthe features the current protocol has - but given we are in the second\nhalf of a GSoC project of which the end is in sight then I think we\nshould shelve them until the project finishes.  There has certainly been\na lot of useful things come out of them!\n\nCheers,\nSam.\n"}]}