{"thread":{"id":"26203","subject":"Resumable clone/Gittorrent (again)","startedAt":"2011-01-05T16:23:32Z","lastAt":"2011-01-16T02:11:36Z","messageCount":25,"participants":["Nguyen Thai Ngoc Duy","Luke Kenneth Casson Leighton","Thomas Rast","Maaartin","Maaartin-1","Nicolas Pitre","Sam Vilain"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"158965","messageId":"AANLkTinUV9Z_w85Gz13J+bm8xqnxJ9jBJXJm9bn5Y2ec@mail.gmail.com","threadId":"26203","inReplyTo":null,"subject":"Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-05T16:23:32Z","receivedAt":"2011-01-05T16:23:32Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Hi,\n\nI've been analyzing bittorrent protocol and come up with this. The\nlast idea about a similar thing [1], gittorrent, was given by Nicolas.\nThis keeps close to that idea (i.e the transfer protocol must be around git\nobjects, not file chunks) with a bit difference.\n\nThe idea is to transfer a chain of objects (trees or blobs), including\nbase object and delta chain. Objects are chained in according to\nworktree layout, e.g. all objects of path/to/any/blob will form a\nchain, from a commit tip down to the root commits. Chains can have\ngaps, and don't need to start from commit tip. The transfer is\nresumable because if a delta chain is corrupt at some point, we can\njust request another chain from where it stops. Base object is\nobviously resumable.\n\nWe start by fetching all commit contents reachable from a commit tip.\nThis is a chain, therefore resumable. From there each commit can be\nexamined. Missing trees and blobs will be fetched as chains. Everytime\na delta is received, we can recreate the new object and verify it (we\nshould have its SHA-1 from its parent trees/commits).\n\nBecause these chains are quite independent, in a sense that a blob\nchain is independent from another blob chain (but requires tree\nchains, of course). We can fetch as many as we want in parallel, once\nwe're done with the commit chain.\n\nThe last thing I like about these chains is that the number of chains\nis reasonable. It won't increase too fast over time (as compared to\nthe number of commits). As such it maps well to BitTorrent's \"pieces\".\nWhen a new gittorrent comes in, a running client can advertise what\nchain it has with a bitmap (*).\n\nSo it all looks good to me. It is resumable and verifiable. It can be\nfetched in parallel from many servers. It maps pretty good to\nBitTorrent (which means we can reuse BitTorrent design). All transfer\nshould be compressed so the amount of transfer is also acceptable (not\nas optimized as upload-pack, but hopefully overhead is low). A minor\npoint is latest commit (in full) will be available as soon as\npossible.\n\nOne thing about reachability test. In order to avoid this test in an\nexpensive way every time a chain is requested, the requested chain\nmust be in SHA-1 extended form, starting from commit tip (e.g.\n$SHA1~12^2~34...). Parsing and following that syntax is cheaper, I\nhope.\n\nComments?\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/155222\n\n(*) BitTorrent stores list of pieces in .torrent file. The bitmap\nreflects what pieces a client has so other clients can ask for pieces\nfrom it. If we follow the same way, we can create a list of all\npossible directories/files in a repository in .gittorrent file, then\ngittorrent client can advertise with bitmaps too, perhaps two-bit map\n(not fetched, fetching, fully fetched).\n-- \nDuy\n"},{"id":"158970","messageId":"AANLkTimHb8O6s_KfhSGqvStZkEGWvPeAVcqQkYoyk49j@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTinUV9Z_w85Gz13J+bm8xqnxJ9jBJXJm9bn5Y2ec@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-05T16:56:09Z","receivedAt":"2011-01-05T16:56:09Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Wed, Jan 5, 2011 at 4:23 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n> Hi,\n>\n> I've been analyzing bittorrent protocol and come up with this. The\n> last idea about a similar thing [1], gittorrent, was given by Nicolas.\n> This keeps close to that idea (i.e the transfer protocol must be around git\n> objects, not file chunks) with a bit difference.\n\n> So it all looks good to me. It is resumable and verifiable. It can be\n> fetched in parallel from many servers. It maps pretty good to\n> BitTorrent (which means we can reuse BitTorrent design). All transfer\n> should be compressed so the amount of transfer is also acceptable (not\n> as optimized as upload-pack, but hopefully overhead is low). A minor\n> point is latest commit (in full) will be available as soon as\n> possible.\n\n ok.  what i wasn't aware of, about the bittorrent protocol, was that\nmultiple files, when placed into the same .torrent, are just\nconcatenated as one monolithic data block.  the \"chunking\" is just\nthen slapped on top of that.  the end result is that it's possible\nthat, if you want to get one specific file (or, in this case \"object\"\nwhether it be commit, blob or tree) then you *might* end up getting\ntwo more \"chunks\" than you actually need, which, worst case could end\nup being 2.999x the actual data really required.\n\n _this_ is the reason why people such as cameron dale criticised\nbittorrent as a hierarchical / multi-file delivery mechanism (and\nabandoned it in favour of apt-p2p), and i didn't understand this at\nthe time enough to be able to point out that i'd assumed they knew\nwhat i was thinking :)\n\n what i was thinking was \"duhh!\" don't slap multiple files into a\nsingle .torrent, put each file (or, in this case \"object\" whether it\nbe commit, blob, tree or other) into a separate torrent!  that's all -\nproblem goes away!\n\n now that of course leaves you with the problem that you now have\npotentially hundreds if not thousands or tens of thousands of\n.torrents to deal with, publish, find etc. etc.   and the solution to\n_that_ is to give the name of the .torrent file something\nmeaningful.... like.... ooo, how about... the object's md5 sum? :)\n\n so _that_ problem's solved, which leaves just one more problem: how\nto find such a ridiculously large number of objects in the first\nplace, and, surprise-surprise, there's a perfect solution to that, as\nwell, called DHTs.  and, surprise-surprise, what do you need as the\nDHT key?  something like a 128-bit key?   ooo, how about ... the\nobject's md5 sum? that's 128-bit, that'll do :)\n\n but, better than that: there happens to have been announced very\nrecently an upgraded version of a bittorrent client, which claims to\nbe fantastic as it's no longer dependent on \"internet search\" sites,\nbecause surprise-surprise, it uses peer-to-peer DHT to do the search\nqueries.\n\n so not only is there a solution to the problems but also there's even\na suitable codebase to work from in order to create a working\nprototype.\n\n now i just have to find the damn thing... ah yes, it's called Tribler.\n\n l.\n"},{"id":"158971","messageId":"201101051813.57603.trast@student.ethz.ch","threadId":"26203","inReplyTo":"AANLkTimHb8O6s_KfhSGqvStZkEGWvPeAVcqQkYoyk49j@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-01-05T17:13:57Z","receivedAt":"2011-01-05T17:13:57Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Luke Kenneth Casson Leighton wrote:\n>  now that of course leaves you with the problem that you now have\n> potentially hundreds if not thousands or tens of thousands of\n> .torrents to deal with, publish, find etc. etc.\n\nUmm, I'm counting 202400 objects in my git.git and 1799525 in a clone\nof linux-2.6.git.  So I'm not sure how far you want to split things\ninto single transfers, but going all the way down to objects will\nmassively hurt performance.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"158974","messageId":"AANLkTikn+89iGbkt90Bv1Hndiimf4brcCNOo0HBX-oPy@mail.gmail.com","threadId":"26203","inReplyTo":"201101051813.57603.trast@student.ethz.ch","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-05T18:07:19Z","receivedAt":"2011-01-05T18:07:19Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Wed, Jan 5, 2011 at 5:13 PM, Thomas Rast <trast@student.ethz.ch> wrote:\n> Luke Kenneth Casson Leighton wrote:\n>>  now that of course leaves you with the problem that you now have\n>> potentially hundreds if not thousands or tens of thousands of\n>> .torrents to deal with, publish, find etc. etc.\n>\n> Umm, I'm counting 202400 objects in my git.git and 1799525 in a clone\n> of linux-2.6.git.  So I'm not sure how far you want to split things\n> into single transfers, but going all the way down to objects will\n> massively hurt performance.\n\n yeah... this is a key reason why i came up with a protocol which\ntransferred the exact same pack-objects that HTTP and all the other\n\"point-to-point\" git protocols use, to such good effect.\n\nthe problem was that i was going to rely on multiple clients being\nable to genereate the exact same pack-object, given the exact same\ninput, and then share that pack-object.  ok, that's not the problem,\nthat was just the plan :)\n\n nicolas kindly pointed out, at some length, that in a distributed\nenvironment, however, that plan was naive, becauuuse whenever you\nrequest a pack-object for use e.g. normally with HTTP or other git\npoint-to-point protocol, it's generated there-and-then using\nheuristics and multi-threading that pretty much guarantees that even\nif you were to make the exact same request of exactly the same system,\nyou'd get *different* pack-objects!  not to mention the fact that\ndifferent people have the same git objects stored in *different* ways\nbecause the object stores, despite having the same commits in them,\nwere pulled at different times and end up with a completely different\nset of git objects that represent those exact same commits that\neveryone else has.\n\nthat's all a bit wordy, but you get the idea.\n\n so, nicolas recommended a \"simpler\" approach, which, well, apologies\nnicolas but i didn't really like it - it seemed far too simplistic and\ni'm not really one for spending time doing these kinds of\n\"intermediate baby steps\" (wrong choice of words, no offense implied,\nbut i'm sure you know what i mean).  i much prefer to just hit all the\nissues head-on, right from the start :)\n\n\nso, in the intervening time since this was last discussed i've given\nthe pack-objects-distributing idea some thought (and NO, nicolas, just\nto clarify, this is NOT grabbing the git packed objects that are\nactually in the .git/objects store, so NO, this does NOT end up\nbypassing security by giving people objects that are from another\nbranch, it really IS getting that lovely varying data which is\nheuristic, store and threadnum dependent!).\n\n the plan is to turn that variation in the git pack-objects responses,\nacross multiple peers, into an *advantage* not a liability.  how?\nlike this:\n\n * a client requiring objects from commit abcd0123 up to commit\nefga3456 sends out a DHT broadcast query to all and sundry who have\ncommits abcd0123 and everything in between up to efga3456.\n\n * those clients that can be bothered to respond, do so [refinements below]\n\n * the requestor selects a few of them, and asks them to create git\npack-objects.  this takes time, but that's ok.  once created, the size\nof the git pack-object is sent as part of the acknowledgement.\n\n * the requestor, on receipt of all the sizes, selects the *smallest*\none to begin the p2p (.torrent) from (by asking the remote client to\ncreate a .torrent specifically for that purpose, with the filename\nabcd0123-ebga3456).\n\n in this way you end up with not only an efficient git pack-object but\nyou get, to 99.5% certainty *THE* most efficient git pack-object.\ndistributed computing at its best :)\n\n now, an immediately obvious refinement of this is that those .torrent\n(pack-objects) \"stick around\", in a cache (with a hard limit defined\non the cache size of course).  and so, when the client that requires a\npack-object makes the request, of course, those remote clients that\n*already* have that cached pack-object for that specific commit-range\nshould be given first priority, to avoid other clients from having to\nmake massive amounts of git pack-objects.\n\n a further refinement is of course to collect statistics on the number\nof peers doing downloads at the time, prioritising those pack-objects\nwhich are most being distributed at the time.  this has fairly obvious\nbenefits :)\n\n yet *another* refinement is slightly less obvious, and it's this:\nthere *COULD* happen to be some existing pack-objects in the cache,\nnot of commit abcd0123-efga3456 but in a ready-made \"chain\": commits\nabcd01234-beef7890 packed already and in the cache, and commits\nbeef7890-efga3456 likewise packed already and in the cache.  again:\nthe requestor should be informed of these, and make their mind up as\nto what to do.\n\n it gets rather more complex when you have *part* of the chain already\npre-cached (and have to work out err, i got this bit and this bit, but\ni'd have to generate a git pack-object for the bit in the middle, i'll\ninform the requestor of this, they can make up their mind what to do),\nbut again i do not imagine for one second that this would be anything\nmore than an intriguing coding challenge and, importantly, an\noptimisation challenge for gittorrent version 3.0 somewhere down the\nline, rather than an all-out absolute requirement that it must, must\nbe done now, now, now.\n\n what else can i mention, that occurred to me... yeah - abandoning of\na download.  if, for some reason it becomes blindingly obvious that\nthe p2p transfer just isn't working out, then the requestor simply\nstops the process and starts again.  a refinement of this, which is a\nbit cheeky i know, is to keep *two* simultaneous requests and\ndownloads for the *exact* same git pack-object commit-chain but with\ndifferent data from different groups of peers, for a short period of\ntime, and then abandon one of them once it's clear which one is best.\nthis does seem a bit cheeky, but it has the advantage that if the one\nthat _was_ fastest goes tits-up, you can at least go back to the\nprevious one and, assuming that the cache hasn't been cleared, just\njoin in again.  but this is _really_ something that's wayyy down the\nline, for gittorrent version 4.0 or 5.0 or so.\n\nso, can you see that a) this is a far cry from the \"simplistic\ntransfer of blobs and trees\" b) it's *not* going to overload peoples'\nsystems by splattering (eek!) millions of md5 sums across the internet\nas bittorrent files c) it _does_ fit neatly into the bittorrent\nprotocol d) it combines the best of git with the best of p2p\ndistributed networking principles...\n\n... all of which creates a system which people will _still_ say is a\n\"hammer looking for nails\" :)\n\n... right up until the point where some idiot in the USA government\ndecides to seize sourceforge.net, github.com, gitorious.org and\nsavannah.gnu.org because they contain source code of software that\nMIGHT be used for copyright infringement.  whilst i realise that the\nonly one of those that might be missed is sourceforget, you cannot\nignore the fact that the trust placed in governments and large\ncorporations to run the internet infrastructure is now completely\ngone, and that the USA and other countries are now putting in place\nhypocritical policies that put them into the same category that used\nto be reserved for China, Saudi Arabia, Iran and other regimes accused\nof being \"Totalitarian\".\n\n thoughts, anyone?  (other than on the last paragraph, please, if that's ok).\n\nl.\n"},{"id":"159004","messageId":"loom.20110105T222915-261@post.gmane.org","threadId":"26203","inReplyTo":"AANLkTinUV9Z_w85Gz13J+bm8xqnxJ9jBJXJm9bn5Y2ec@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Maaartin","fromEmail":"grajcar1@seznam.cz","sentAt":"2011-01-05T23:28:11Z","receivedAt":"2011-01-05T23:28:11Z","isPatch":false,"sender":{"key":"grajcar1@seznam.cz","avatar":null},"body":"Nguyen Thai Ngoc Duy <pclouds <at> gmail.com> writes:\n\n> I've been analyzing bittorrent protocol and come up with this. The\n> last idea about a similar thing [1], gittorrent, was given by Nicolas.\n> This keeps close to that idea (i.e the transfer protocol must be around git\n> objects, not file chunks) with a bit difference.\n>\n> The idea is to transfer a chain of objects (trees or blobs), including\n> base object and delta chain. Objects are chained in according to\n> worktree layout, e.g. all objects of path/to/any/blob will form a\n> chain, from a commit tip down to the root commits. Chains can have\n> gaps, and don't need to start from commit tip. The transfer is\n> resumable because if a delta chain is corrupt at some point, we can\n> just request another chain from where it stops. Base object is\n> obviously resumable.\n\nI may be talking nonsense, please bare with me.\n\nI'm not sure if it works well, since chains defined this way change over time. \nI may request commits A and B while declaring to possess commits C and D. One \nserver may be ahead of A, so should it send me more data or repack the chain so \nthat the non-requested versions get excluded? At the same time the server may \nbe missing B and posses only some ancestors of it. Should it send me only a \npart of the chain or should I better ask a different server?\n\nMoreover, in case a directory gets renamed, the content may get transfered \nneedlessly. This is probably no big problem.\n\nI haven't read the whole other thread yet, but what about going the other way \nround? Use a single commit as a chain, create deltas assuming that all \nancestors are already available. The packs may arrive out of order, so the \ndecompression may have to wait. The number of commits may be one order of \nmagnitude larger than the the number of paths (there are currently 2254 paths \nand 24235 commits in git.git), so grouping consequent commits into one larger \npack may be useful.\n\nThe advantage is that the packs stays stable over time, you may create them \nusing the most aggressive and time-consuming settings and store them forever. \nYou could create packs for single commits, packs for non-overlapping \nconsecutive pairs of them, for non-overlapping pairs of pairs, etc. I mean with \ncommits numbered 0, 1, 2, ... create packs [0,1], [2,3], ..., [0,3], [4,7], \netc. The reason for this is obviously to allow reading groups of commits from \ndifferent servers so that they fit together (similar to Buddy memory \nallocation). Of course, there are things like branches bringing chaos in this \nsimple scheme, but I'm sure this can be solved somehow.\n\nAnother problem is the client requesting commits A and B while declaring to \npossess commits C and D. When both C and D are ancestors of either A or B, you \ncan ignore it (as you assume this while packing, anyway). The other case is \nless probable, unless e.g. C is the master and A is a developing branch. \nCurrently. I've no idea how to optimize this and whether this could be \nimportant.\n\nI see no disadvantage when compared to path-based chains, but am probably \noverlooking something obvious.\n"},{"id":"159014","messageId":"AANLkTi=_R53fm5Er0CdtZCFvDpE-Dqt8tMHAubcjOUBb@mail.gmail.com","threadId":"26203","inReplyTo":"loom.20110105T222915-261@post.gmane.org","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-06T01:32:12Z","receivedAt":"2011-01-06T01:32:12Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Jan 6, 2011 at 6:28 AM, Maaartin <grajcar1@seznam.cz> wrote:\n> Nguyen Thai Ngoc Duy <pclouds <at> gmail.com> writes:\n>\n>> I've been analyzing bittorrent protocol and come up with this. The\n>> last idea about a similar thing [1], gittorrent, was given by Nicolas.\n>> This keeps close to that idea (i.e the transfer protocol must be around git\n>> objects, not file chunks) with a bit difference.\n>>\n>> The idea is to transfer a chain of objects (trees or blobs), including\n>> base object and delta chain. Objects are chained in according to\n>> worktree layout, e.g. all objects of path/to/any/blob will form a\n>> chain, from a commit tip down to the root commits. Chains can have\n>> gaps, and don't need to start from commit tip. The transfer is\n>> resumable because if a delta chain is corrupt at some point, we can\n>> just request another chain from where it stops. Base object is\n>> obviously resumable.\n>\n> I may be talking nonsense, please bare with me.\n>\n> I'm not sure if it works well, since chains defined this way change over time.\n> I may request commits A and B while declaring to possess commits C and D. One\n> server may be ahead of A, so should it send me more data or repack the chain so\n> that the non-requested versions get excluded? At the same time the server may\n> be missing B and posses only some ancestors of it. Should it send me only a\n> part of the chain or should I better ask a different server?\n\nI'll keep it simple. A chain is defined by one commit head. Such a\nchain can't change over time. But you can ask for just part of the\nchain, rev-list syntax can be used here. For example if you already\nhave commits C and D and 10 delta in the chain (linear history for\nsimplicity here), requesting \"give me A~10 ^C ^D\" should give required\ncommits.\n\n> Moreover, in case a directory gets renamed, the content may get transfered\n> needlessly. This is probably no big problem.\n\nYes, the chain constraint can backfire in these cases. We can mix\nstandard upload-pack/fetch-pack and this if the server can recognize\nthese cases, by cutting commit history into chunks. The dir rename\nchunks can be fetched with git-fetch.\n\n> I haven't read the whole other thread yet, but what about going the other way\n> round? Use a single commit as a chain, create deltas assuming that all\n> ancestors are already available. The packs may arrive out of order, so the\n> decompression may have to wait. The number of commits may be one order of\n> magnitude larger than the the number of paths (there are currently 2254 paths\n> and 24235 commits in git.git), so grouping consequent commits into one larger\n> pack may be useful.\n\nThe number of commits can increase fast. I'd rather have a\nsmall/stable number over time. And commits depend on other commits so\nyou can't verify a commit until you have got all of its parents. That\ndoes apply to file, but then this file chain does not interfere other\nfile chains.\n\n> The advantage is that the packs stays stable over time, you may create them\n> using the most aggressive and time-consuming settings and store them forever.\n> You could create packs for single commits, packs for non-overlapping\n> consecutive pairs of them, for non-overlapping pairs of pairs, etc. I mean with\n> commits numbered 0, 1, 2, ... create packs [0,1], [2,3], ..., [0,3], [4,7],\n> etc. The reason for this is obviously to allow reading groups of commits from\n> different servers so that they fit together (similar to Buddy memory\n> allocation). Of course, there are things like branches bringing chaos in this\n> simple scheme, but I'm sure this can be solved somehow.\n\nPack encoding can change. And packs can contain objects you don't want\nto share (i.e. hidden from public view).\n\n> Another problem is the client requesting commits A and B while declaring to\n> possess commits C and D. When both C and D are ancestors of either A or B, you\n> can ignore it (as you assume this while packing, anyway). The other case is\n> less probable, unless e.g. C is the master and A is a developing branch.\n> Currently. I've no idea how to optimize this and whether this could be\n> important.\n\nAs I said, we can request just part of a chain (from A+B to C+D).\ngit-fetch should be used if the repo is quite uptodate though. It's\njust more efficient.\n-- \nDuy\n"},{"id":"159015","messageId":"AANLkTi=-gomYOpX6+RSboBXBytPry1Qhf31ohmv1dC5d@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTikn+89iGbkt90Bv1Hndiimf4brcCNOo0HBX-oPy@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-06T01:47:40Z","receivedAt":"2011-01-06T01:47:40Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Jan 6, 2011 at 1:07 AM, Luke Kenneth Casson Leighton\n<luke.leighton@gmail.com> wrote:\n>  the plan is to turn that variation in the git pack-objects responses,\n> across multiple peers, into an *advantage* not a liability.  how?\n> like this:\n>\n>  * a client requiring objects from commit abcd0123 up to commit\n> efga3456 sends out a DHT broadcast query to all and sundry who have\n> commits abcd0123 and everything in between up to efga3456.\n>\n>  * those clients that can be bothered to respond, do so [refinements below]\n>\n>  * the requestor selects a few of them, and asks them to create git\n> pack-objects.  this takes time, but that's ok.  once created, the size\n> of the git pack-object is sent as part of the acknowledgement.\n>\n>  * the requestor, on receipt of all the sizes, selects the *smallest*\n> one to begin the p2p (.torrent) from (by asking the remote client to\n> create a .torrent specifically for that purpose, with the filename\n> abcd0123-ebga3456).\n\nThat defeats the purpose of distributing. You are putting pressure on\ncertain peers.\n\n>  now, an immediately obvious refinement of this is that those .torrent\n> (pack-objects) \"stick around\", in a cache (with a hard limit defined\n> on the cache size of course).  and so, when the client that requires a\n> pack-object makes the request, of course, those remote clients that\n> *already* have that cached pack-object for that specific commit-range\n> should be given first priority, to avoid other clients from having to\n> make massive amounts of git pack-objects.\n\nCache have its limits too. Suppose I half-fetch a pack then stop and\ngo wild for a month. The next month I restart the fetch, the pack may\nno longer in cache. A new pack may or may not be identical to the old\npack.\n\nAlso if you go with packs, you are tied to the peer that generates\nthat pack. Two different peers can, in theory, generate different\npacks (in encoding) for the same input.\n\nAnother thing with packs (ok, not exactly with packs) is how you\nverify that's you have got what you asked. Bittorrent can verify every\npiece a peer receives because sha-1 sum of those pieces are recorded\nin .torrent file. We have SHA-1 all over the place, but if you don't\nhave base objects to undeltify, you can't use those SHA-1 to verify.\nVerification is an important step before you advertise to other peers\n\"I have these\".\n\n> so, can you see that a) this is a far cry from the \"simplistic\n> transfer of blobs and trees\" b) it's *not* going to overload peoples'\n> systems by splattering (eek!) millions of md5 sums across the internet\n> as bittorrent files c) it _does_ fit neatly into the bittorrent\n> protocol d) it combines the best of git with the best of p2p\n> distributed networking principles...\n\nHow can you advertise what you have to another peer?\n-- \nDuy\n"},{"id":"159017","messageId":"4D25385B.3010103@seznam.cz","threadId":"26203","inReplyTo":"AANLkTi=_R53fm5Er0CdtZCFvDpE-Dqt8tMHAubcjOUBb@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Maaartin-1","fromEmail":"grajcar1@seznam.cz","sentAt":"2011-01-06T03:34:51Z","receivedAt":"2011-01-06T03:34:51Z","isPatch":false,"sender":{"key":"grajcar1@seznam.cz","avatar":null},"body":"On 11-01-06 02:32, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Jan 6, 2011 at 6:28 AM, Maaartin <grajcar1@seznam.cz> wrote:\n>> Nguyen Thai Ngoc Duy <pclouds <at> gmail.com> writes:\n\n>> I haven't read the whole other thread yet, but what about going the other way\n>> round? Use a single commit as a chain, create deltas assuming that all\n>> ancestors are already available. The packs may arrive out of order, so the\n>> decompression may have to wait. The number of commits may be one order of\n>> magnitude larger than the the number of paths (there are currently 2254 paths\n>> and 24235 commits in git.git), so grouping consequent commits into one larger\n>> pack may be useful.\n> \n> The number of commits can increase fast. I'd rather have a\n> small/stable number over time.\n\nIn theory, I could create many commits per seconds. I could create many\nunique paths per seconds, too. But I don't think it really happens. I do\nknow no larger repository than git.git and I don't want to download it\njust to see how many commits, paths, and object it contains, but I'd\nsuppose it's less than one million commits, which should be manageable,\nespecially when commits get grouped together as I described below.\n\n> And commits depend on other commits so\n> you can't verify a commit until you have got all of its parents. That\n> does apply to file, but then this file chain does not interfere other\n> file chains.\n\nThat's true, but the verification is something done locally on the\nclient, it consumes no network traffic and no server resources, so I\nconsider it to be cheap. I need less than half a minute (using only a\nsingle core) for verifying of the whole git.git repository (36 MB). This\nis no problem, even when it had to wait until the download finishes. I'm\nsure, the OP of [1] would be happy if he could wait for this.\n\n>> The advantage is that the packs stays stable over time, you may create them\n>> using the most aggressive and time-consuming settings and store them forever.\n>> You could create packs for single commits, packs for non-overlapping\n>> consecutive pairs of them, for non-overlapping pairs of pairs, etc. I mean with\n>> commits numbered 0, 1, 2, ... create packs [0,1], [2,3], ..., [0,3], [4,7],\n>> etc. The reason for this is obviously to allow reading groups of commits from\n>> different servers so that they fit together (similar to Buddy memory\n>> allocation). Of course, there are things like branches bringing chaos in this\n>> simple scheme, but I'm sure this can be solved somehow.\n> \n> Pack encoding can change.\n\nI see I didn't explain it clear enough (or am missing something\ncompletely). I know why the packs normally used by git can't be used for\nthis purpose. Let me retry: Let's assume there's a commit chain\nA-B-C-D-E-F-..., the client has already commit B and requests commit F.\nIt may send requests to up to 4 servers, asking for C, D, E, and F,\nrespectively. The server being asked for E _creates_ a pack containing\nall the information needed to create E given _all of_ A, B, C, D. As\nbase for any blob/whatever in E it may choose any blob contained in any\nof these commits. Of course, it may also choose a blob already packed in\nthis pack. It may not choose any other blob, so any client having all\nancestors of E can use the pack. Different server and/or program\nversions may create different packs for E, but all of them are\n_interchangeable_. Because of this, it makes sense to _store_ it for\nfuture reuse.\n\nCompared to the way git packing normally works, this is a restriction,\nbut I don't think it leads to significantly worse compression. You guys\nworking on git can confirm or disprove it.\n\n> And packs can contain objects you don't want\n> to share (i.e. hidden from public view).\n\nThis pack would contain only commit E. I also described pairing intended\nfor greater efficiency. In this case a server creates a pack allowing\ne.g. to create commits E and F given all their ancestors (while other\nserver creates a pack for C and D). This way the number of packs needed\nmay be a fraction of the total number of commits requested.\n\n>> Another problem is the client requesting commits A and B while declaring to\n>> possess commits C and D. When both C and D are ancestors of either A or B, you\n>> can ignore it (as you assume this while packing, anyway). The other case is\n>> less probable, unless e.g. C is the master and A is a developing branch.\n>> Currently. I've no idea how to optimize this and whether this could be\n>> important.\n> \n> As I said, we can request just part of a chain (from A+B to C+D).\n> git-fetch should be used if the repo is quite uptodate though. It's\n> just more efficient.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/164564\n"},{"id":"159020","messageId":"AANLkTikXcrZqhCw+2u2HObUZz5QCStY6BCHTTYYfngMN@mail.gmail.com","threadId":"26203","inReplyTo":"4D25385B.3010103@seznam.cz","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-06T06:36:57Z","receivedAt":"2011-01-06T06:36:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Jan 6, 2011 at 10:34 AM, Maaartin-1 <grajcar1@seznam.cz> wrote:\n> In theory, I could create many commits per seconds. I could create many\n> unique paths per seconds, too. But I don't think it really happens. I do\n> know no larger repository than git.git and I don't want to download it\n> just to see how many commits, paths, and object it contains, but I'd\n> suppose it's less than one million commits, which should be manageable,\n> especially when commits get grouped together as I described below.\n\nIn pratice, commits are created every day in an active project. Paths\non the other hand are added less often (perhaps except webkit).\n\nI've got some numbers:\n\n - wine.git has 72k commits, 260k trees, 200k blobs, 12k paths\n - git.git has 24k commits, 39k trees, 24k blobs, 2.7k paths\n - linux-2.6.git has 160k commits, 760k trees, 442k blobs, 46k paths\n\nLarge repos are more interesting because small ones can be cloned with\ngit-clone.\n\nListing all those commits in linux-2.6.git takes 160k*20=3M (I suppose\ncompressing is useless because SHA-1 is random). A compressed listing\nof those 46k paths takes 200k.\n\n>> And commits depend on other commits so\n>> you can't verify a commit until you have got all of its parents. That\n>> does apply to file, but then this file chain does not interfere other\n>> file chains.\n>\n> That's true, but the verification is something done locally on the\n> client, it consumes no network traffic and no server resources, so I\n> consider it to be cheap. I need less than half a minute (using only a\n> single core) for verifying of the whole git.git repository (36 MB). This\n> is no problem, even when it had to wait until the download finishes. I'm\n> sure, the OP of [1] would be happy if he could wait for this.\n\nThe point is you need to fetch its parent commits first in order to\nverify a commit. Fetching a whole commit is more expensive than a\nfile. So while you can fetch a few commit bases and request for packs\nfrom those bases in parallel, the cost of initial commit bases will be\nhigh.\n\n> I see I didn't explain it clear enough (or am missing something\n> completely). I know why the packs normally used by git can't be used for\n> this purpose. Let me retry: Let's assume there's a commit chain\n> A-B-C-D-E-F-..., the client has already commit B and requests commit F.\n> It may send requests to up to 4 servers, asking for C, D, E, and F,\n> respectively. The server being asked for E _creates_ a pack containing\n> all the information needed to create E given _all of_ A, B, C, D. As\n> base for any blob/whatever in E it may choose any blob contained in any\n> of these commits. Of course, it may also choose a blob already packed in\n> this pack. It may not choose any other blob, so any client having all\n> ancestors of E can use the pack. Different server and/or program\n> versions may create different packs for E, but all of them are\n> _interchangeable_. Because of this, it makes sense to _store_ it for\n> future reuse.\n\nThey are interchangeable as a whole, yes. But you cannot fetch half\nthe pack from server A and the other half from server B. You can try\nto recover as many deltas as possible in a broken pack, but how do you\nrequest a server to send the rest of the pack to you?\n-- \nDuy\n"},{"id":"159044","messageId":"AANLkTimgpbzbu-cD0+fFPie4U2R_ZoG46cDJkNt43R83@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTi=-gomYOpX6+RSboBXBytPry1Qhf31ohmv1dC5d@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-06T17:50:24Z","receivedAt":"2011-01-06T17:50:24Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Thu, Jan 6, 2011 at 1:47 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n> On Thu, Jan 6, 2011 at 1:07 AM, Luke Kenneth Casson Leighton\n> <luke.leighton@gmail.com> wrote:\n>>  the plan is to turn that variation in the git pack-objects responses,\n>> across multiple peers, into an *advantage* not a liability.  how?\n>> like this:\n>>\n>>  * a client requiring objects from commit abcd0123 up to commit\n>> efga3456 sends out a DHT broadcast query to all and sundry who have\n>> commits abcd0123 and everything in between up to efga3456.\n>>\n>>  * those clients that can be bothered to respond, do so [refinements below]\n>>\n>>  * the requestor selects a few of them, and asks them to create git\n>> pack-objects.  this takes time, but that's ok.  once created, the size\n>> of the git pack-object is sent as part of the acknowledgement.\n>>\n>>  * the requestor, on receipt of all the sizes, selects the *smallest*\n>> one to begin the p2p (.torrent) from (by asking the remote client to\n>> create a .torrent specifically for that purpose, with the filename\n>> abcd0123-ebga3456).\n>\n> That defeats the purpose of distributing. You are putting pressure on\n> certain peers.\n\n that's unavoidable, but it's not actually as bad as it seems.  think\nabout it.  normally, \"pressure\" is put onto a git server, by forcing\nthat server to perform multiple \"git pack-object\" calculations,\nrepeatedly, for each and every \"git pull\".\n\n so, the principle behind this RFC (is it an RFC? yes, kinda...) is\nthat a) you cache those git pack-objects, thus avoiding heavy CPU\nusage b) you make the requests to _many_ peers that you'll likely find\nalready are in the process of distributing that particular\ncommit-range _anyway_ so will _definitely_ have it  ... etc. etc.\n\n so there's a ton of reasons why it's quite a big improvement over the\npresent star-network arrangement.\n\n>\n>>  now, an immediately obvious refinement of this is that those .torrent\n>> (pack-objects) \"stick around\", in a cache (with a hard limit defined\n>> on the cache size of course).  and so, when the client that requires a\n>> pack-object makes the request, of course, those remote clients that\n>> *already* have that cached pack-object for that specific commit-range\n>> should be given first priority, to avoid other clients from having to\n>> make massive amounts of git pack-objects.\n>\n> Cache have its limits too. Suppose I half-fetch a pack then stop and\n> go wild for a month. The next month I restart the fetch, the pack may\n> no longer in cache. A new pack may or may not be identical to the old\n> pack.\n\n correct.  that's not in the slightest bit a problem.  the peer which\nhas that new pack will be asked to make a new .torrent for _that_\npack.  with a new name that uniquely identifies it (the md5sum of the\npack would do as the .torrent filename)\n\n> Also if you go with packs, you are tied to the peer that generates\n> that pack. Two different peers can, in theory, generate different\n> packs (in encoding) for the same input.\n\n yes.  correct.  i _did_ say that you pick the one that is the\nsmallest of the two (or three.  or 10).  in this way you actually do\nmuch better than you would otherwise in a \"star network\" such as a\nstandard HTTP git server, because you've asked 2, 3 or 10 (whatever)\npeers, and you'll end up with _the_ most efficient representation of\nthat commit-range.  statistically speaking, of course :)\n\n\n> Another thing with packs (ok, not exactly with packs) is how you\n> verify that's you have got what you asked.\n\n ok - how do you verify that you've got what you asked, when you ask\nfrom a git server using HTTP?\n\n> Bittorrent can verify every\n> piece a peer receives because sha-1 sum of those pieces are recorded\n> in .torrent file.\n\n yes.  this is simply a part of the bittorrent protocol, to ensure\nthat the file being transferred is correctly transferred.\n\n these verifications steps should be _trusted_ and should _not_ be\nconfused with anything else (i've deleted the rest of the paragraph\nyou wrote, in order to reduce any opportunity for confusion).\n\n if you mentally keep git separate from bittorrent it helps.  imagine\nthat bittorrent is merely a drop-in replacement for git over HTTP\n(nicolas kindly explained the plugin system for git which would add\nanother protocol for downloading of git repos, and yes this can all be\nimplemented as a plugin)\n\n\n>> so, can you see that a) this is a far cry from the \"simplistic\n>> transfer of blobs and trees\" b) it's *not* going to overload peoples'\n>> systems by splattering (eek!) millions of md5 sums across the internet\n>> as bittorrent files c) it _does_ fit neatly into the bittorrent\n>> protocol d) it combines the best of git with the best of p2p\n>> distributed networking principles...\n>\n> How can you advertise what you have to another peer?\n\n you don't.  it's done \"on-demand\".\n\n the concept of \"git push\" becomes virtually a null-op, updating the\nbittorrent tracker and that's... about it.\n\n it's where \"git pull\" that all the work is done, starting with that\nDHT query [no i know \"bittorrent the protocol\" doesn't have DHT, but\nmany bittorrent clients _do_ have DHT, and Tribler has an extremely\ngood one].\n\n l.\n"},{"id":"159093","messageId":"alpine.LFD.2.00.1101061956470.22191@xanadu.home","threadId":"26203","inReplyTo":"AANLkTinUV9Z_w85Gz13J+bm8xqnxJ9jBJXJm9bn5Y2ec@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-01-07T03:21:36Z","receivedAt":"2011-01-07T03:21:36Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 5 Jan 2011, Nguyen Thai Ngoc Duy wrote:\n\n> Hi,\n> \n> I've been analyzing bittorrent protocol and come up with this. The\n> last idea about a similar thing [1], gittorrent, was given by Nicolas.\n> This keeps close to that idea (i.e the transfer protocol must be around git\n> objects, not file chunks) with a bit difference.\n> \n> The idea is to transfer a chain of objects (trees or blobs), including\n> base object and delta chain. Objects are chained in according to\n> worktree layout, e.g. all objects of path/to/any/blob will form a\n> chain, from a commit tip down to the root commits. Chains can have\n> gaps, and don't need to start from commit tip. The transfer is\n> resumable because if a delta chain is corrupt at some point, we can\n> just request another chain from where it stops. Base object is\n> obviously resumable.\n\nHow do you actually define your chain?  Given that Git is conceptually \nsnapshot based, there is currently no relationship between two blobs \nforming the content for two different versions of the same file.  Even \ndelta objects are not really part of the Git data model as they are only \nan encoding variation of a given primary object.  In fact, we may and \nactually do have deltas where the base object is not from the same \nworktree file as the delta object itself.\n\nThe only thing that \nties this all together is the commit graph.  And that graph might have \nmultiple forks and merges so any attempt at a linearity representation \ninto a chain is rather futile.  Therefore it is not clear to me how you \ncan define a chain with a beginning and an end, and how this can be \nresumed midway.\n\n> We start by fetching all commit contents reachable from a commit tip.\n\nSure.  This is doable today and is called a shalow clone with depth=1.\n\n> This is a chain, therefore resumable.\n\nI don't get that part though.  How is this resumable?  That's the very \nissue we have with a clone.\n\nI proposed a solution to that already, which is to use \ngit-upload-archive for one of the tip commit since the data stream \nproduced by upload-archive (once decompressed) is actually \ndeterministic.  Once completed, this can be converted into a shalow \nclone on the client side, and can be deepened in smaller steps \nafterwards.\n\n> From there each commit can be\n> examined. Missing trees and blobs will be fetched as chains. Everytime\n> a delta is received, we can recreate the new object and verify it (we\n> should have its SHA-1 from its parent trees/commits).\n\nWhat if the delta is based on an object from another chain?  How do you \ndetermine which chain to ask for to get that base?\n\n> Because these chains are quite independent, in a sense that a blob\n> chain is independent from another blob chain (but requires tree\n> chains, of course). We can fetch as many as we want in parallel, once\n> we're done with the commit chain.\n\nBut in practice, most of those chains will end up containing objects \nwhich are duplicate of objects in another chain.  How do you tell the \nremote that you want part of a chain because you've got 96% of it in \nanother chain already?\n\n> The last thing I like about these chains is that the number of chains\n> is reasonable. It won't increase too fast over time (as compared to\n> the number of commits). As such it maps well to BitTorrent's \"pieces\".\n\nMy problem right now is that I don't see how this maps well to Git.\n\n\nNicolas\n"},{"id":"159097","messageId":"AANLkTik_Q-W2yjnyB3=NKGQcn-MeFwnPQqnrGgWN_Q7C@mail.gmail.com","threadId":"26203","inReplyTo":"alpine.LFD.2.00.1101061956470.22191@xanadu.home","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-07T06:34:31Z","receivedAt":"2011-01-07T06:34:31Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jan 7, 2011 at 10:21 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> How do you actually define your chain?  Given that Git is conceptually\n> snapshot based, there is currently no relationship between two blobs\n> forming the content for two different versions of the same file.  Even\n> delta objects are not really part of the Git data model as they are only\n> an encoding variation of a given primary object.  In fact, we may and\n> actually do have deltas where the base object is not from the same\n> worktree file as the delta object itself.\n>\n> The only thing that\n> ties this all together is the commit graph.  And that graph might have\n> multiple forks and merges so any attempt at a linearity representation\n> into a chain is rather futile.  Therefore it is not clear to me how you\n> can define a chain with a beginning and an end, and how this can be\n> resumed midway.\n\nThere's no need to be linear. OK it's not a chain, but a DAG of\nobjects that has the same path, in the same structure of commit DAG.\n\n>> We start by fetching all commit contents reachable from a commit tip.\n>\n> Sure.  This is doable today and is called a shalow clone with depth=1.\n\nI meant only commit objects, no trees nor blobs.\n\n>> This is a chain, therefore resumable.\n>\n> I don't get that part though.  How is this resumable?  That's the very\n> issue we have with a clone.\n\nI assume that all commits are sent in an order that parent commits are\nalways after the commit in question. We can make a pack of undeltified\ncommit objects in such order. That would make sure we could recover a\ncontinuous commit DAG from the tip if the pack cannot be sent\ncompletely to client.\n\nWe can traverse commit graph we have, and request for a pack of\nmissing commits to grow the commit DAG until we have all commits.\n\n> I proposed a solution to that already, which is to use\n> git-upload-archive for one of the tip commit since the data stream\n> produced by upload-archive (once decompressed) is actually\n> deterministic.  Once completed, this can be converted into a shalow\n> clone on the client side, and can be deepened in smaller steps\n> afterwards.\n\nYou see, I don't send trees and blobs in this phase. There are three\nphases. Phase 1 fetches all commits. Once we have all commits. We can\nuse them to request packs of trees of the same path. Those packs are\nlike the commit pack, but deltified. That's phase 2. When we have\nenough trees, we can proceed to phase 3: fetching packs of blobs.\n\n>> From there each commit can be\n>> examined. Missing trees and blobs will be fetched as chains. Everytime\n>> a delta is received, we can recreate the new object and verify it (we\n>> should have its SHA-1 from its parent trees/commits).\n>\n> What if the delta is based on an object from another chain?  How do you\n> determine which chain to ask for to get that base?\n\nChains should be independent. If a chain is based on another chain and\nwe have not got its base yet (because the other chain is not\ncompleted), we can fetch the base separately. In theory we need to\nfetch a version of all paths once for them to become bases. So it's\nlike a broken down version of git-upload-archive.\n\n>> Because these chains are quite independent, in a sense that a blob\n>> chain is independent from another blob chain (but requires tree\n>> chains, of course). We can fetch as many as we want in parallel, once\n>> we're done with the commit chain.\n>\n> But in practice, most of those chains will end up containing objects\n> which are duplicate of objects in another chain.  How do you tell the\n> remote that you want part of a chain because you've got 96% of it in\n> another chain already?\n\nBecause all clients should have full commit graph (without trees and\nblobs) before doing anything, they should be able to specify a rev\nlist for the chain they need. So if you only need SHA1~76..SHA1~100 of\na path, say so to remote side. SHA-1 must be one of the refs on remote\nside, so it can parse the syntax and verify quickly if \"SHA1~76\" is\nreachable/allowed to transfer.\n\n>> The last thing I like about these chains is that the number of chains\n>> is reasonable. It won't increase too fast over time (as compared to\n>> the number of commits). As such it maps well to BitTorrent's \"pieces\".\n>\n> My problem right now is that I don't see how this maps well to Git.\n\nGit sees a repository as history of snapshots. This way I see it as a\nbunch of \"git log -- path\", not that bad.\n-- \nDuy\n"},{"id":"159114","messageId":"AANLkTikKn1+2OX1KPy+9US_yX=E6+CiaCTTB6yqnAWwW@mail.gmail.com","threadId":"26203","inReplyTo":"alpine.LFD.2.00.1101061956470.22191@xanadu.home","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-07T15:59:56Z","receivedAt":"2011-01-07T15:59:56Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Fri, Jan 7, 2011 at 3:21 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n\n>> The last thing I like about these chains is that the number of chains\n>> is reasonable. It won't increase too fast over time (as compared to\n>> the number of commits). As such it maps well to BitTorrent's \"pieces\".\n>\n> My problem right now is that I don't see how this maps well to Git.\n\n bittorrent as \"just another file getting method\" maps very well.\n\n only with some modifications to the bittorrent protocol would the\nconcept map well to bittorrent \"pieces\" because the pieces are at\npresent a) fixed size b) defined by a heuristic based on the file size\n(logarithmic) so that the number of pieces are kept to within a\nreasonable limit.\n\n bottom line: my take on this is (sorry to say, nguyen) that i don't\nbelieve bittorrent \"pieces\" map well to the chains concept, unless the\nchains are perfectly fixed identical sizes [which they could well be?\nam i mistaken about this?]\n\n l.\n"},{"id":"159194","messageId":"4D27B828.8020108@seznam.cz","threadId":"26203","inReplyTo":"AANLkTikXcrZqhCw+2u2HObUZz5QCStY6BCHTTYYfngMN@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Maaartin-1","fromEmail":"grajcar1@seznam.cz","sentAt":"2011-01-08T01:04:40Z","receivedAt":"2011-01-08T01:04:40Z","isPatch":false,"sender":{"key":"grajcar1@seznam.cz","avatar":null},"body":"On 11-01-06 07:36, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Jan 6, 2011 at 10:34 AM, Maaartin-1 <grajcar1@seznam.cz> wrote:\n>> In theory, I could create many commits per seconds. I could create many\n>> unique paths per seconds, too. But I don't think it really happens. I do\n>> know no larger repository than git.git and I don't want to download it\n>> just to see how many commits, paths, and object it contains, but I'd\n>> suppose it's less than one million commits, which should be manageable,\n>> especially when commits get grouped together as I described below.\n> \n> In pratice, commits are created every day in an active project. Paths\n> on the other hand are added less often (perhaps except webkit).\n> \n> I've got some numbers:\n> \n>  - wine.git has 72k commits, 260k trees, 200k blobs, 12k paths\n>  - git.git has 24k commits, 39k trees, 24k blobs, 2.7k paths\n>  - linux-2.6.git has 160k commits, 760k trees, 442k blobs, 46k paths\n> \n> Large repos are more interesting because small ones can be cloned with\n> git-clone.\n\nSure. Linux is the winner and has 4 times as much commits as paths.\n\n> Listing all those commits in linux-2.6.git takes 160k*20=3M (I suppose\n> compressing is useless because SHA-1 is random). A compressed listing\n> of those 46k paths takes 200k.\n\nSure, Linux has only 4 times as much commits as paths, but the commits\nneed 30 times more storage. What does it tell us?\n\nIMHO it speaks in favor of my proposal. Imagine a path changing with\nnearly every commit. The root directory is such a path and near top\ndirectories come close to (as may other files like todo-lists do). For\neach such file you need 3MB for storing the commits SHAs only. Of\ncourse, you can invent a schema making storing all the SHAs unnecessary,\nbut this is another complication.\n\nOTOH, with the commits used as directory entries we get quite a large\ndirectory. Is this a problem you wanted me to get aware of?\n\n> The point is you need to fetch its parent commits first in order to\n> verify a commit. Fetching a whole commit is more expensive than a\n> file. So while you can fetch a few commit bases and request for packs\n> from those bases in parallel, the cost of initial commit bases will be\n> high.\n\nYou've lost me. I assume you mean that something like that there may be\nvery large commits (e.g., in a project not versioned from the very\nbeginning). I'd suggest to split such commits in two parts by\nclassifying the blobs (and trees) using a fixed bit of their SHAs. Of\ncourse, this can be repeated in order to get even smaller parts. Let's\nassume a commit X gets split into X0 and X1. As before, for compressing\nof X0 you may use the content any predecessor of X. For compressing of\nX0 you may additionally use the content of X0. This way the compression\nrate could stay close to optimal, IMHO.\n\n> They are interchangeable as a whole, yes. But you cannot fetch half\n> the pack from server A and the other half from server B. You can try\n> to recover as many deltas as possible in a broken pack, but how do you\n> request a server to send the rest of the pack to you?\n\nIndeed, it's not resumable. For most commits it's not needed since they\nare very small. Why? There are more commits than paths, so the commits\nare smaller than paths on the average. I expect my schema to allow for\nnearly as good compression as git usually does, especially I'd hope it's\nno worse than when packing paths.\n\nHowever, there may be very large commits in my schema (and maybe also\nvery large \"path-packs\" in yours). Such large commits get split as I\ndescribed above. Small commits get paired (possibly multiple times) as I\ndescribed earlier. You end up with only reasonably sized pieces of data,\nlet's say between 256 and 512 kB, so you don't need to resume.\n\nActually, with a really bad connection, you could ask the very server\nfrom which you obtained an incomplete pack to resume from a given byte\noffset (similar to HTTP ranges). The server may or may not have it. This\ntime it should try to keep it available for you in case you connections\nabort again. Don't get me wrong -- this is just an additional help for\nvery badly connected people.\n"},{"id":"159195","messageId":"AANLkTimgn2_BWYjbGKbGoeGJ=erKundX4umfy=s16dB1@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTikKn1+2OX1KPy+9US_yX=E6+CiaCTTB6yqnAWwW@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-08T02:17:57Z","receivedAt":"2011-01-08T02:17:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jan 7, 2011 at 10:59 PM, Luke Kenneth Casson Leighton\n<luke.leighton@gmail.com> wrote:\n>  bottom line: my take on this is (sorry to say, nguyen) that i don't\n> believe bittorrent \"pieces\" map well to the chains concept, unless the\n> chains are perfectly fixed identical sizes [which they could well be?\n> am i mistaken about this?]\n\nthere are a few characteristics of bittorrent pieces that i see:\nverifiable, resumable, uniquely identifiable across peers and\nreasonbly small in count.\n\nThe fixed size helps peers uniquely identify any pieces by splitting\nthe whole transfer equally and indexing them in 1-dimension. It's a\nrule to help identify pieces, not the only valid rule. In git, given a\ncommit SHA-1 we can identify any parts (or \"pieces\") that are\nreachable from that commit using rev-list syntax. Therefore the\n\"identifiable\" characteristics still holds even we don't split in\nfixed size pieces.\n-- \nDuy\n"},{"id":"159197","messageId":"AANLkTinbCkTvkZ3GVJJH7cV-a+YRSM=XzfsXcVBCTifd@mail.gmail.com","threadId":"26203","inReplyTo":"4D27B828.8020108@seznam.cz","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-08T02:40:43Z","receivedAt":"2011-01-08T02:40:43Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Jan 8, 2011 at 8:04 AM, Maaartin-1 <grajcar1@seznam.cz> wrote:\n>> Listing all those commits in linux-2.6.git takes 160k*20=3M (I suppose\n>> compressing is useless because SHA-1 is random). A compressed listing\n>> of those 46k paths takes 200k.\n>\n> Sure, Linux has only 4 times as much commits as paths, but the commits\n> need 30 times more storage. What does it tell us?\n>\n> IMHO it speaks in favor of my proposal. Imagine a path changing with\n> nearly every commit. The root directory is such a path and near top\n> directories come close to (as may other files like todo-lists do). For\n> each such file you need 3MB for storing the commits SHAs only. Of\n> course, you can invent a schema making storing all the SHAs unnecessary,\n> but this is another complication.\n>\n> OTOH, with the commits used as directory entries we get quite a large\n> directory. Is this a problem you wanted me to get aware of?\n\nI merely point out that if we use commit sha-1 as \"pieces\". Then when\na new peer comes in and ask a running peer \"what pieces have you got\n(so that I can start fetching from you)?\", you will need more\nbandwidth for that kind of information.\n\n>> The point is you need to fetch its parent commits first in order to\n>> verify a commit. Fetching a whole commit is more expensive than a\n>> file. So while you can fetch a few commit bases and request for packs\n>> from those bases in parallel, the cost of initial commit bases will be\n>> high.\n>\n> You've lost me. I assume you mean that something like that there may be\n> very large commits (e.g., in a project not versioned from the very\n> beginning). I'd suggest to split such commits in two parts by\n> classifying the blobs (and trees) using a fixed bit of their SHAs. Of\n> course, this can be repeated in order to get even smaller parts. Let's\n> assume a commit X gets split into X0 and X1. As before, for compressing\n> of X0 you may use the content any predecessor of X. For compressing of\n> X0 you may additionally use the content of X0. This way the compression\n> rate could stay close to optimal, IMHO.\n\nWell if you are going to split a commit, then splitting by paths\nsounds more natural to me (assume that people don't often move files).\n\n>> They are interchangeable as a whole, yes. But you cannot fetch half\n>> the pack from server A and the other half from server B. You can try\n>> to recover as many deltas as possible in a broken pack, but how do you\n>> request a server to send the rest of the pack to you?\n>\n> Indeed, it's not resumable. For most commits it's not needed since they\n> are very small. Why? There are more commits than paths, so the commits\n> are smaller than paths on the average. I expect my schema to allow for\n> nearly as good compression as git usually does, especially I'd hope it's\n> no worse than when packing paths.\n\nA commit diff consists of all tree and blobs diff compared to the\nparent commit (let's ignore merges). How can it be smaller than just a\nsingle tree/blob diff (of the same path, compared to the parent\ncommit)?\n\n> However, there may be very large commits in my schema (and maybe also\n> very large \"path-packs\" in yours). Such large commits get split as I\n> described above. Small commits get paired (possibly multiple times) as I\n> described earlier. You end up with only reasonably sized pieces of data,\n> let's say between 256 and 512 kB, so you don't need to resume.\n\nYeah, I started thinking how to transfer effieciently and I came to\nsimilar thing: assume we have good order of packing and know what to\npack, then we close the pack when its size is greater than a limit and\nstart sending another pack. If this pack stream is corrupt, resume\nfrom the corrupt pack forward. I currently hardcode the limit 4k, not\ngreater because pack overhead is very low already (12 header bytes and\n20 sha1 trailer bytes each pack).\n\n> Actually, with a really bad connection, you could ask the very server\n> from which you obtained an incomplete pack to resume from a given byte\n> offset (similar to HTTP ranges). The server may or may not have it. This\n> time it should try to keep it available for you in case you connections\n> abort again. Don't get me wrong -- this is just an additional help for\n> very badly connected people.\n\nReplace \"byte range\" with rev-list syntax (SHA1~10..SHA1-20) then we\nhave quite fine-grained way of asking for data. Deltas are usually\nvery small (I observed cache.h only so this could be a wrong\nassumption). But if SHA1~10..SHA1~11 has too big diff that keeps\nfailing, sending byte ranges of the blob in SHA1~11 is probably the\nonly way left.\n-- \nDuy\n"},{"id":"159227","messageId":"AANLkTim2A4=y=XcuPuPiYGDGZyKAUEk-yv2cZVEGhQ3C@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTimgn2_BWYjbGKbGoeGJ=erKundX4umfy=s16dB1@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-08T17:21:47Z","receivedAt":"2011-01-08T17:21:47Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Sat, Jan 8, 2011 at 2:17 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n> On Fri, Jan 7, 2011 at 10:59 PM, Luke Kenneth Casson Leighton\n> <luke.leighton@gmail.com> wrote:\n>>  bottom line: my take on this is (sorry to say, nguyen) that i don't\n>> believe bittorrent \"pieces\" map well to the chains concept, unless the\n>> chains are perfectly fixed identical sizes [which they could well be?\n>> am i mistaken about this?]\n>\n> there are a few characteristics of bittorrent pieces that i see:\n> verifiable, resumable, uniquely identifiable across peers and\n> reasonbly small in count.\n>\n> The fixed size helps peers uniquely identify any pieces by splitting\n> the whole transfer equally and indexing them in 1-dimension.\n\n ok - you haven't answered the question: are the chains perfectly\nfixed identical sizes?\n\n if so they can be slotted into the bittorrent protocol by simply\npre-selecting the size to match.  with the downside that if there are\na million such \"chains\" you now pretty much overwhelm the peers with\nthe amount of processing, network traffic and memory requirements to\nmaintain the \"pieces\" map.\n\n if not then you now need to modify the bittorrent protocol to cope\nwith variable-length block sizes: the protocol only allows for the\nlast block to be of variable-length.\n\n also, it's worth pointing out that the entire code-base of every\nsingle bittorrent client that you will ever be able to find revolves\naround the concept of reassembly of files from \"pieces\".\n\n bottom line: the bittorrent protocol and the available bittorrent\nsource code libraries, both of which save you a great deal of time in\ngetting something up-and-running, is _not_ the right fit for the\nconcept of placing the proposed \"chains\" into bittorrent \"pieces\".\n\n translation: if you wish to pursue the \"chains\" concept, either a\nheavily-modified bittorrent protocol and client _or_ an entirely new\npeer-to-peer protocol is far more appropriate.\n\n orrr, doing what i initially suggested, which is to leave the\nbittorrent protocol as-is and to open one .torrent per \"chain\".\nespecially if these \"chains\" vary considerably in size (k to gb)\n\nl.\n"},{"id":"159237","messageId":"AANLkTi=KPVMEviQhyJeWHynPa2q6NJpQ2VyAhbRcmQ1D@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTim2A4=y=XcuPuPiYGDGZyKAUEk-yv2cZVEGhQ3C@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-09T03:34:27Z","receivedAt":"2011-01-09T03:34:27Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jan 9, 2011 at 12:21 AM, Luke Kenneth Casson Leighton\n<luke.leighton@gmail.com> wrote:\n>  ok - you haven't answered the question: are the chains perfectly\n> fixed identical sizes?\n\nNo.\n\n>  if so they can be slotted into the bittorrent protocol by simply\n> pre-selecting the size to match.  with the downside that if there are\n> a million such \"chains\" you now pretty much overwhelm the peers with\n> the amount of processing, network traffic and memory requirements to\n> maintain the \"pieces\" map.\n\nNo, there are thousands of them only (less than 100k for repos I\nexamined). It's precisely the reason I stay away from commits as\npieces because commits can potentially go up to millions.\n\n>  if not then you now need to modify the bittorrent protocol to cope\n> with variable-length block sizes: the protocol only allows for the\n> last block to be of variable-length.\n\nAh I see. I do not reuse bittorrent code out there. Just its ideas,\nadapted to git model. If you don't want to modify bittorrent protocol\nat all, seed a bundle (as mentioned in another thread).\n-- \nDuy\n"},{"id":"159243","messageId":"AANLkTinwb8orMBjcQjK0ogXd6rMEtRwT8SV41k8D3AXL@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTi=KPVMEviQhyJeWHynPa2q6NJpQ2VyAhbRcmQ1D@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-09T13:55:04Z","receivedAt":"2011-01-09T13:55:04Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Sun, Jan 9, 2011 at 3:34 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n> On Sun, Jan 9, 2011 at 12:21 AM, Luke Kenneth Casson Leighton\n> <luke.leighton@gmail.com> wrote:\n>>  ok - you haven't answered the question: are the chains perfectly\n>> fixed identical sizes?\n>\n> No.\n>\n>>  if so they can be slotted into the bittorrent protocol by simply\n>> pre-selecting the size to match.  with the downside that if there are\n>> a million such \"chains\" you now pretty much overwhelm the peers with\n>> the amount of processing, network traffic and memory requirements to\n>> maintain the \"pieces\" map.\n>\n> No, there are thousands of them only (less than 100k for repos I\n> examined). It's precisely the reason I stay away from commits as\n> pieces because commits can potentially go up to millions.\n\n ok - thousands is still a lot.  i recommend that you examine:\n\n * the heuristics algorithm in bittorrent for piece-selection\n * large repositories such as webkit (1.2gb) and the linux kernel (600mb)\n\n you still have to come up with a mapping from \"chains\" to \"pieces\".\nin the bittorrent protocol the mapping is done *entirely* implicitly\nand algorithmically.  the \"meta\" info in the .torrent contains\nfilenames and file lengths.  stack the files one after the other in a\nbig long data block, get a chopper and just go \"whack, whack, whack\"\nat regular piece-long points, that's your \"pieces\".  so, reassembly is\na complete bitch, and picking just _one_ file to download rather than\nthe whole lot becomes a total pain.\n\nwhy the bloody hell the bittorrent protocol doesn't just have a file\nid i _really_ don't know, it would have made things a damn sight\neasier.  anyway - if you're going to modify and \"be inspired by\" the\nbittorrent protocol, you really should look at adding some sort of\n\"chain\" identification - f*** the \"chains\"-to-\"pieces\" algorithm, just\nadd a unique chain id to the relevant bittorrent[-like] command.\n\n\n>>  if not then you now need to modify the bittorrent protocol to cope\n>> with variable-length block sizes: the protocol only allows for the\n>> last block to be of variable-length.\n>\n> Ah I see. I do not reuse bittorrent code out there. Just its ideas,\n> adapted to git model.\n\n that's hard work and you're now into \"unproven\" territory.  the\nsuccessful R&D proof-of-concept code that i wrote i _deliberately_\nstayed away from \"adapting\" a proven bittorrent protocol, and as a\nresult managed to get that proof-of-concept up and running within ...\ni think it was... 3 days.  most of the time was spent arseing about\nadding in a VFS layer into bittornado, in order to libratise it.\n\ni mention that just to give you something to think about.  if you're\nup to the challenge of writing your own p2p protocol, however, GREAT!\nyou'll become a world expert on _both_ peer-to-peer protocols _and_\ngit :)\n\n l.\n"},{"id":"159248","messageId":"AANLkTimkDYCL7+N-Rno1-0p3Gy6o0wYrnuStV_n5k4Hk@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTinwb8orMBjcQjK0ogXd6rMEtRwT8SV41k8D3AXL@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-01-09T17:48:28Z","receivedAt":"2011-01-09T17:48:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jan 9, 2011 at 8:55 PM, Luke Kenneth Casson Leighton\n<luke.leighton@gmail.com> wrote:\n>  you still have to come up with a mapping from \"chains\" to \"pieces\".\n> in the bittorrent protocol the mapping is done *entirely* implicitly\n> and algorithmically.\n\nGiven a commit SHA-1, the mapping can be done algorithmically because\nthe graph from the commit tip is fixed. Perhaps not mapping all at\nonce, but as you have more pieces in the graph, you can map more.\n\n> the \"meta\" info in the .torrent contains\n> filenames and file lengths.  stack the files one after the other in a\n> big long data block, get a chopper and just go \"whack, whack, whack\"\n> at regular piece-long points, that's your \"pieces\".  so, reassembly is\n> a complete bitch, and picking just _one_ file to download rather than\n> the whole lot becomes a total pain.\n\nWell, there won't be .torrent files. Torrent files serve as checksums\nfor file pieces (let's forget the tracker part). We do sha-1 checksum\non every objects in git. The object graph without real content _is_\n\"info\" part in .torrent files. Instead of passing around torrent\nfiles, I only need to pass around the sha-1 of the commit tip(s). That\nshould be enough for any peer to discover the rest.\n\nReassembling, in its simplest way, is to just dump loose objects to\n$GIT_DIR/objects. But it's been six years since git's birth now, I'll\npack them instead.\n\n>  that's hard work and you're now into \"unproven\" territory.  the\n> successful R&D proof-of-concept code that i wrote i _deliberately_\n> stayed away from \"adapting\" a proven bittorrent protocol, and as a\n> result managed to get that proof-of-concept up and running within ...\n> i think it was... 3 days.  most of the time was spent arseing about\n> adding in a VFS layer into bittornado, in order to libratise it.\n>\n> i mention that just to give you something to think about.  if you're\n> up to the challenge of writing your own p2p protocol, however, GREAT!\n> you'll become a world expert on _both_ peer-to-peer protocols _and_\n> git :)\n\nMaybe I have gone insane ;) But I have another aim for this work: to\nadjust narrow clone area (pretty much path-based clones). So while it\nmay not become real torrent for git (i.e p2p exchanging, depends on my\nneeds), restartable clone from multiple sources is still worth it.\n-- \nDuy\n"},{"id":"159289","messageId":"4D2B7C68.1010200@vilain.net","threadId":"26203","inReplyTo":"AANLkTim2A4=y=XcuPuPiYGDGZyKAUEk-yv2cZVEGhQ3C@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2011-01-10T21:38:48Z","receivedAt":"2011-01-10T21:38:48Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On 09/01/11 06:21, Luke Kenneth Casson Leighton wrote:\n> On Sat, Jan 8, 2011 at 2:17 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n>> there are a few characteristics of bittorrent pieces that i see:\n>> verifiable, resumable, uniquely identifiable across peers and\n>> reasonbly small in count.\n>>\n>> The fixed size helps peers uniquely identify any pieces by splitting\n>> the whole transfer equally and indexing them in 1-dimension.\n>  ok - you haven't answered the question: are the chains perfectly\n> fixed identical sizes?\n>\n>  if so they can be slotted into the bittorrent protocol by simply\n> pre-selecting the size to match.  with the downside that if there are\n> a million such \"chains\" you now pretty much overwhelm the peers with\n> the amount of processing, network traffic and memory requirements to\n> maintain the \"pieces\" map.\n\nI'll respond also to this sub-point.  This can be done; but instead of\ndoing it at the pack level, you take the list of objects between A and B\n(for a fetch from A to B), order them by some deterministic order\n(called the \"commit reel\" in the Gittorrent RFC) and then carve that\nlist up into chunks based on the uncompressed object sizes.\n\nThe ordering defined in the RFC is such that it is possible to create\n\"thin\" packs for discrete ranges of commits using existing plumbing, so\nthat the total transfer size is relatively similar to a complete clone. \nIn experiments the network overhead was found to be around 10-20% in\nthis way.\n\nHowever I must discourage looking for \"inspiration\" from the Bittorrent\nprotocol; it reinvents many wheels unnecessarily, and contains much\nshonky advice in it.  See the revision history for the gittorrent RFC\n(github.com/samv/gittorrent) for the gory details.\n\nSam\n"},{"id":"159436","messageId":"AANLkTi=3ikJ2UNNCW582CT7LQ7o2DBZ1hXJhPfMUNbKk@mail.gmail.com","threadId":"26203","inReplyTo":"AANLkTimkDYCL7+N-Rno1-0p3Gy6o0wYrnuStV_n5k4Hk@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-13T11:39:05Z","receivedAt":"2011-01-13T11:39:05Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Sun, Jan 9, 2011 at 5:48 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n> On Sun, Jan 9, 2011 at 8:55 PM, Luke Kenneth Casson Leighton\n> <luke.leighton@gmail.com> wrote:\n>>  you still have to come up with a mapping from \"chains\" to \"pieces\".\n>> in the bittorrent protocol the mapping is done *entirely* implicitly\n>> and algorithmically.\n>\n> Given a commit SHA-1, the mapping can be done algorithmically because\n> the graph from the commit tip is fixed. Perhaps not mapping all at\n> once, but as you have more pieces in the graph, you can map more.\n\n you're _sure_ about this?  what happens when new commits get added,\nand change that graph?  are you _certain_ that you can write an\nalgorithm which is capable of generating exactly the same mapping,\neven as more commits are added to the repository being mirrored, or,\ndoes that situation not matter?\n\nl.\n"},{"id":"159455","messageId":"4D2F8D7E.6030305@vilain.net","threadId":"26203","inReplyTo":"AANLkTi=3ikJ2UNNCW582CT7LQ7o2DBZ1hXJhPfMUNbKk@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2011-01-13T23:40:46Z","receivedAt":"2011-01-13T23:40:46Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On 14/01/11 00:39, Luke Kenneth Casson Leighton wrote:\n> On Sun, Jan 9, 2011 at 5:48 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:\n>> On Sun, Jan 9, 2011 at 8:55 PM, Luke Kenneth Casson Leighton\n>> <luke.leighton@gmail.com> wrote:\n>>>  you still have to come up with a mapping from \"chains\" to \"pieces\".\n>>> in the bittorrent protocol the mapping is done *entirely* implicitly\n>>> and algorithmically.\n>> Given a commit SHA-1, the mapping can be done algorithmically because\n>> the graph from the commit tip is fixed. Perhaps not mapping all at\n>> once, but as you have more pieces in the graph, you can map more.\n>  you're _sure_ about this?  what happens when new commits get added,\n> and change that graph?  are you _certain_ that you can write an\n> algorithm which is capable of generating exactly the same mapping,\n> even as more commits are added to the repository being mirrored, or,\n> does that situation not matter?\n\nFor a given set of start and end points, and a given sort algorithm,\nwalking the commit tree can yield deterministic results.\n\nYou need to first make sure topological sanity prevails, then order by\ncommit date where there are ties.  git rev-list --date-order does this. \nThere is the possibility of commits with the same commit date, so if you\nneed to be really particular you can tie break on those, too.\n\nDid you look at any of the previous research I linked to before?\n\nSam\n"},{"id":"159489","messageId":"AANLkTi=8s4mjreC1yiJi4R5Y3G6_kErmBfk0B9ALcBO8@mail.gmail.com","threadId":"26203","inReplyTo":"4D2F8D7E.6030305@vilain.net","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Luke Kenneth Casson Leighton","fromEmail":"luke.leighton@gmail.com","sentAt":"2011-01-14T14:26:42Z","receivedAt":"2011-01-14T14:26:42Z","isPatch":false,"sender":{"key":"luke.leighton@gmail.com","avatar":null},"body":"On Thu, Jan 13, 2011 at 11:40 PM, Sam Vilain <sam@vilain.net> wrote:\n> On 14/01/11 00:39, Luke Kenneth Casson Leighton wrote:\n\n>> and change that graph?  are you _certain_ that you can write an\n>> algorithm which is capable of generating exactly the same mapping,\n>> even as more commits are added to the repository being mirrored, or,\n>> does that situation not matter?\n>\n> For a given set of start and end points, and a given sort algorithm,\n> walking the commit tree can yield deterministic results.\n\n excellent.  out of curiosity, is it as efficient as git pack-objects\nfor the same start and end points?\n\n> Did you look at any of the previous research I linked to before?\n\n i've been following this since you first originally started it, sam\n:)  it would have been be nice if it was a completed implementation\nthat i could test and see \"for real\" what you're referring to (above)\n- the fact that it's in perl and has \"TODO\" at some of the critical\npoints, after trying to work with it for several days i stopped and\nwent \"i'm not getting anywhere with this\" and focussed on bittorrent\n\"as a black box\" instead.\n\n if i recall, the original gittorrent work that you did (mirror-sync),\nthe primary aim was to rely solely and exclusively on a one-to-one\ndirect link between one machine and another.  in other words, whilst\nsyncing, if that peer went \"offline\", you're screwed - you have to\nstart again.  is that a fair assessment?  please do correct any\nassumptions that i've made.\n\n because on the basis _of_ that assumption, i decided not to proceed\nwith mirror-sync, instead to pursue a \"cache git pack-objects\"\napproach and to use bittorrent \"black-box-style\".  which i\ndemonstrated (minus the cacheing) works perfectly well, several months\nback.\n\n in this way (i know i didn't reply earlier - apologies), there is\nabsolutely no need to \"take bittorrent apart\", no need to modify it,\ntinker with it, adjust it, redesign it, learn from it \"for\ninspiration\" - you just get on with it, using the code, protocol and\neverything about it as a black-box. \"get this file to everyone and\nanyone wot needs it\".\n\n as well, after nicolas and others went to all the trouble to explain\nwhat git pack-objects is, how it works, and how damn efficient it is,\ni'm pretty much convinced that an approach to uniquely identify, then\npick and cache the *best* git pack-object made [by all the peers\nrequested to provide a particular commit range], is the best, most\nefficient - and importantly simplest and easiest to understand -\napproach so far that i've heard.  perhaps that's because i came up\nwith it, i dunno :)  but the important thing is that i can _show_ that\nit works (http://gitorious.org/python-libbittorrent/pybtlib - go back\na few revisions)\n\n so - perhaps it would help if mirrorsync was revived, so that it can\nbe used to demonstrate what you mean (there aren't any instructions on\nhow to set up mirrorsync, for example).  that would then allow people\nto do a comparative analysis of the approaches being taken.\n\n i'd be *very* interested - and i'm sure that there are others\nlikewise equally as interested - to see if the mirrorsync \"commit tree\nwalking\" algorithm can come up with a more efficient method of\ntransferring git repositories than git pack-objects can.\n\nl.\n"},{"id":"159536","messageId":"4D3253D8.8030302@vilain.net","threadId":"26203","inReplyTo":"AANLkTi=8s4mjreC1yiJi4R5Y3G6_kErmBfk0B9ALcBO8@mail.gmail.com","subject":"Re: Resumable clone/Gittorrent (again)","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2011-01-16T02:11:36Z","receivedAt":"2011-01-16T02:11:36Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On 15/01/11 03:26, Luke Kenneth Casson Leighton wrote:\n>>> and change that graph?  are you _certain_ that you can write an\n>>> algorithm which is capable of generating exactly the same mapping,\n>>> even as more commits are added to the repository being mirrored, or,\n>>> does that situation not matter?\n>> For a given set of start and end points, and a given sort algorithm,\n>> walking the commit tree can yield deterministic results.\n>  excellent.  out of curiosity, is it as efficient as git pack-objects\n> for the same start and end points?\n\nThat isn't a sensible question; walking the revision tree is something\nthat many commands, including git pack-objects, do internally.\n\n>> Did you look at any of the previous research I linked to before?\n>  i've been following this since you first originally started it, sam\n> :)  it would have been be nice if it was a completed implementation\n> that i could test and see \"for real\" what you're referring to (above)\n> - the fact that it's in perl and has \"TODO\" at some of the critical\n> points, after trying to work with it for several days i stopped and\n> went \"i'm not getting anywhere with this\" and focussed on bittorrent\n> \"as a black box\" instead.\n>\n>  if i recall, the original gittorrent work that you did (mirror-sync),\n> the primary aim was to rely solely and exclusively on a one-to-one\n> direct link between one machine and another.  in other words, whilst\n> syncing, if that peer went \"offline\", you're screwed - you have to\n> start again.  is that a fair assessment?  please do correct any\n> assumptions that i've made.\n\nOk.  Well, first off - I didn't start gittorrent; that was Jonas\nFonseca, it was his Masters thesis.  Criticism about not having a\ncompleted implementation to work with is therefore shared between him\nand people who have come along since such as myself.\n\nI don't know why you got the idea that the protocol is one to one.  It's\none to one just like BitTorrent is - every communication is between two\nnodes who share information about what they have and what they need,\nbefore transferring data.  It is supposed to be restartable and it is\nnot supposed to matter which node data is exchanged with.  In that way,\nyou could in principle download from multiple nodes at once, or you\ncould have restartable transfers.  If you lose connectivity then the\nmost that should have to be re-transferred are incomplete blocks.\n\n>  because on the basis _of_ that assumption, i decided not to proceed\n> with mirror-sync, instead to pursue a \"cache git pack-objects\"\n> approach and to use bittorrent \"black-box-style\".  which i\n> demonstrated (minus the cacheing) works perfectly well, several months\n> back.\n\nRight, but as others have noted, there are significant drawbacks with\nthis approach.  For a start, to participate in such a network, you need\nto get the particular exact pack that is currently being torrented; just\nhaving a clone is not enough.  This is because the result of git\npack-objects is not repeatable.\n\nThat being said for many projects that would be an acceptable compromise\nfor the advantages of a restartable clone.  That is why I suggest that a\ntorrent transfer, treated as a mirror which is infrequently updated, may\nbe a better approach than trying to overly automate everything.\n\n>  as well, after nicolas and others went to all the trouble to explain\n> what git pack-objects is, how it works, and how damn efficient it is,\n> i'm pretty much convinced that an approach to uniquely identify, then\n> pick and cache the *best* git pack-object made [by all the peers\n> requested to provide a particular commit range], is the best, most\n> efficient - and importantly simplest and easiest to understand -\n> approach so far that i've heard.  perhaps that's because i came up\n> with it, i dunno :)  but the important thing is that i can _show_ that\n> it works (http://gitorious.org/python-libbittorrent/pybtlib - go back\n> a few revisions)\n\nThat's great.  If you want to continue this simple approach and ignore\nthe gittorrent/mirror-sync path altogether, that's fine too.\n\nTrying to determine the \"best\" pack-object may be counter-productive. \nHere's a simple approach which allows the repository owner to easily\narrange for efficient torrenting of essential object files:\n\nAdd to the .torrent manifest just these files:\n\n  .git/objects/pack/pack-*.pack - just the files with .keep files\n  .git/packed-refs - just the references which are completely available\nvia the .keep packs\n\nIn that way, a repository owner can periodically re-pack their repo,\nmark the new pack files as .keep, then re-generate the .torrent file. \nAll nodes will just have to transfer the new packs, not everything.\n\n>  so - perhaps it would help if mirrorsync was revived, so that it can\n> be used to demonstrate what you mean (there aren't any instructions on\n> how to set up mirrorsync, for example).  that would then allow people\n> to do a comparative analysis of the approaches being taken.\n\nOk, that sounds like a good plan - I'll see if I can devote some time to\nan explanatory series with working examples with reference to the\nexisting code etc over the coming months.\n\nCheers,\nSam\n"}]}