{"thread":{"id":"41620","subject":"Resumable clone","startedAt":"2016-03-05T09:23:04Z","lastAt":"2016-03-09T02:04:50Z","messageCount":14,"participants":["Kevin Wern","Duy Nguyen","Junio C Hamano","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"280241","messageId":"CANtyZjSJf5_xbsBC5tUaazFT3uiEgJnx2_kHLwYwKcn50Jy_qg@mail.gmail.com","threadId":"41620","inReplyTo":null,"subject":"Resumable clone","fromName":"Kevin Wern","fromEmail":"kevin.m.wern@gmail.com","sentAt":"2016-03-05T09:23:04Z","receivedAt":"2016-03-05T09:23:04Z","isPatch":false,"sender":{"key":"kevin.m.wern@gmail.com","avatar":null},"body":"Hey, all,\n\nA while ago, I noticed that if a clone is interrupted, it has to be\nrestarted completely. When I looked up the issue, I saw that someone\nsuggested resumable clones as a feature as early as 2007.  It doesn't\nseem like any progress has been made on this issue, so I began looking\nat relevant code yesterday to start working on it.\n\nIs someone working on this currently?  Are there any things I should\nknow moving forward?  Is there a certain way I should break\ndown/organize the feature when writing patches?\n\nAny information is appreciated.\n\nThanks,\nKevin\n"},{"id":"280242","messageId":"CACsJy8CESL6vH22mGSLRE1OKTEbGz2Vqmsv5bY3mn_E+03wADw@mail.gmail.com","threadId":"41620","inReplyTo":"CANtyZjSJf5_xbsBC5tUaazFT3uiEgJnx2_kHLwYwKcn50Jy_qg@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-03-05T09:40:15Z","receivedAt":"2016-03-05T09:40:15Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 5, 2016 at 4:23 PM, Kevin Wern <kevin.m.wern@gmail.com> wrote:\n> Hey, all,\n>\n> A while ago, I noticed that if a clone is interrupted, it has to be\n> restarted completely. When I looked up the issue, I saw that someone\n> suggested resumable clones as a feature as early as 2007.  It doesn't\n> seem like any progress has been made on this issue, so I began looking\n> at relevant code yesterday to start working on it.\n>\n> Is someone working on this currently?  Are there any things I should\n> know moving forward?  Is there a certain way I should break\n> down/organize the feature when writing patches?\n\nResumable clone is happening. See [1] for the basic idea, [2] and [3]\nfor some preparation work. I'm sure you can help. Once you've gone\nthrough at least [1], I think you can pick something (e.g. finalizing\nthe protocol, update the server side, or git-clone....)\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/285921\n[2] http://thread.gmane.org/gmane.comp.version-control.git/288080/focus=288150\n[3] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n-- \nDuy\n"},{"id":"280252","messageId":"xmqqoaasvkrt.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"CACsJy8CESL6vH22mGSLRE1OKTEbGz2Vqmsv5bY3mn_E+03wADw@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-05T18:31:50Z","receivedAt":"2016-03-05T18:31:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> Resumable clone is happening. See [1] for the basic idea, [2] and [3]\n> for some preparation work. I'm sure you can help. Once you've gone\n> through at least [1], I think you can pick something (e.g. finalizing\n> the protocol, update the server side, or git-clone....)\n>\n> [1] http://thread.gmane.org/gmane.comp.version-control.git/285921\n> [2] http://thread.gmane.org/gmane.comp.version-control.git/288080/focus=288150\n> [3] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n\nI think your response needs to be refined with a bit higher level\noverview, though.  Here are some thoughts to summarize the\ndiscussion and to extend it.\n\nI think the right way to think about this is that we are adding a\ncapability for the server to instruct the clients: I prefer not to\nserve a full clone to you in the usual route if I can avoid it.  You\ncan help me by going to an alternate resource and populate your\nhistory first and then coming back to me for an additional fetch to\ncomplete the history if you want to.  Doing so would also help you\nbecause that alternate resource can be a static file (or two) that\nyou can download over a resumable transport (like static files\nserved over HTTPS).\n\nThat alternate resource could be just an old-style bundle file\n(e.g. kernel.org prepares such a bundle file for Linus's kernel\nrepository and makes it available on CDN on a weekly basis;\ncf. https://kernel.org/cloning-linux-from-a-bundle.html).\n\nOne downside of using the old-style bundle is that it would weigh\nabout the same as the fully repacked bare repository itself, and\nwould require the same amount of CPU and disk resource to generate\nas it would take to repack.  The \"split bundle\" discussion with Jeff\nKing is about one possible way to reduce that waste.  The old-style\nbundle is just a header file tucked in front of a packfile, and by\nintroducing a new bundle format that stores only the header part in\na file that points at an existing packfile, we can reduce the waste.\nA few patches from me on \"bundle\" and \"index-pack --clone-bundle\"\nsent for the past several days are about that approach.  During a\nrepack the server operators periodically make, we can also create\nthe header part of the new bundle format that points at the full\npackfile that is produced in order to serve the regular \"fetch/push\"\ntraffic.\n\nMy response to [3] in the thread further points at a new direction.\nThe \"alternate resource\" does not have to be a bundle, but can be\njust a full packfile (i.e. pack-$name.pack).  After a full repack,\nthe server operators can make the packfile available to clients over\na resumable transport.  The client has to run \"index-pack\" on the\ndownloaded pack-$name.pack to generate the \"pack-$name.idx\" file in\norder to make it usable, so the logic to implement \"--clone-bundle\"\nintroduced initially for the \"split bundle\" approach can be\nrepurposed to be run on the client.  With a single pack-$name.pack\nfile, the client can\n\n - Place it in .git/objects/pack in an empty repository;\n\n - Generate corresponding pack-$name.idx file next to it;\n\n - Learn where the tips of histories (i.e. \"all objects that are\n   reachable from these objects are already available in this\n   repository\") are.\n\nAnd the above is sufficient to do the \"coming back to me for an\nadditional fetch\" efficiently.  The tips of histories can be sent as\nextra \"have\" records during such a fetch with a minor update to the\n\"fetch\" code.\n\nSo what remains?  Here is a rough and still slushy outline:\n\n - A new method, prime_clone(), in \"struct transport\" for \"git\n   clone\" client to first call to learn the location of the\n   \"alternate resource\" from the server.\n\n   - The server side endpoint does not have to be, and I think it\n     should not be, implemented as an extension to the current\n     upload-pack protocol.  It is perfectly fine to add a new \"git\n     prime-clone\" program next to existing \"git upload-pack\" and\n     \"git receive-pack\" programs and drive it through the\n     git-daemon, curl remote helper, and direct execution over ssh.\n\n   - The format of the returned \"answer\" needs to be designed.  It\n     must be able to express:\n\n     - the location of the resource, i.e. a URL;\n\n     - the type of resource, if we want this to be extensible.  I\n       think we should initially limit it to \"a single full history\n       .pack\", so from that point of view this may not be absolutely\n       necessary, but we already know that we may want to say \"go\n       there and you will find an old-style bundle file\" to support\n       the kernel.org CDN, and we may also want to support Jeff's\n       \"split bundle\" or Shawn's \".info\" file.  A resource poor\n       (read: personal) machine that hosts a personal of a popular\n       project might want to name a \"git clone\" URL for that popular\n       project it forked from (e.g. \"Clone Linus's repository from\n       kernel.org and then come back here for incremental fetch\").\n\n - A new method, download_primer(), in \"struct transport\" to\n   download the \"alternate resource\" learned from an earlier call to\n   the prime_clone() method.\n\n   - I expect that a typical answer to the \"prime-clone\" (see above)\n     request would be an HTTP(s) URL for a single pack file, or the\n     header file of a \"split bundle\" pair.  The curl remote helper\n     would implement this as an equivalent of \"wget -c\" of these\n     files.\n\n   - The answer to \"prime-clone\" request could name \"git://\" URL,\n     and it is OK to design a new server-side endpoint to respond to\n     download_primer() method, aka \"a minimal resumable download\n     service via git-daemon\" Duy mentioned in [1].\n\n - To support the case where the server responds with \"a single full\n   .pack file\" to prime_clone():\n\n   - \"index-pack\" needs to be extended to compute the tips of the\n     history contained within (the logic is already done, but if the\n     \"split bundle\" output is not the best one to use, we may need\n     to update the output format);\n\n   - The way the \"tips of the history\" is told to \"fetch-pack\" that\n     does the final incremental fetch to the original site needs to\n     be designed.  It could be a \"throw-away temporary sub-hierarchy\n     somewhere in refs/\" I alluded to in [2], but there may be\n     better designs (e.g. naming a split bundle as \"--reference\" to\n     a fresh invocation of the \"git clone\" command).\n\n - Update \"git clone\" (builtin/clone.c).\n\n   - Refactor it to make it easier to wedge in the new code (below),\n     if necessary.\n\n   - Teach it a new \"--resume\" option.\n\n     - When the command is run with this option, no other option\n       must be given.\n\n     - If the existing (half cloned) repository is not marked as\n       resumable, the command must fail.\n\n     - The first few steps below are skipped (i.e. we do not create\n       worktree and gitdir, we do not do init_db(), we do not write\n       refspec configuration).\n\n   - Let the original code run up to the point where it creates\n     worktree and gitdir, does init_db(), and writes the refspec\n     configuration.\n\n   - If some options are given that makes it less efficient to do\n     the \"prime from an alternate resource and then fetch\", do not\n     do anything special and let the original code run to the end\n     (i.e. no resuming).  This may include cases where \"--reference\"\n     is given, indicating that the bulk of objects are already\n     available locally.  The details of this determination need to\n     be worked out.\n\n   - If we are doing the \"prime from an alternate and then fetch\",\n     before the current code calls transport_fetch_refs(), call a\n     new transport API function, transport_prime_clone(), to learn\n     if the server wants us to prime from an \"alternate resource\".\n     If not, let the original code run to the end.\n\n   - If we are still doing the \"prime from an alternate and then\n     fetch\", mark the repository as resumable, and call\n     transport_download_primer(), a new transport API function.\n     This will implement the \"retry until successfully download the\n     whole thing\" and \"continue from where its earlier incarnation\n     was killed\".\n\n   - Once transport_download_primer() finishes downloading the\n     \"alternate resource\", prime the object store and record the\n     tips of the history.\n\n   - Perform an incremental \"fetch\" against the original repository.\n\n   - Finalize the clone, e.g. point our HEAD to a correct branch,\n     start our 'master' (or whatever primary branch name is) branch\n     at a correct place in the history and check the files out to\n     the working tree.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/288080/focus=288161\n[2] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n"},{"id":"280253","messageId":"xmqqk2lgvke6.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"xmqqoaasvkrt.fsf@gitster.mtv.corp.google.com","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-05T18:40:01Z","receivedAt":"2016-03-05T18:40:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> So what remains?  Here is a rough and still slushy outline:\n>\n>  - A new method, prime_clone(), in \"struct transport\" for \"git\n>    clone\" client to first call to learn the location of the\n>    \"alternate resource\" from the server.\n>\n>    ...\n>    - The format of the returned \"answer\" needs to be designed.  It\n>      must be able to express:\n>\n>      - the location of the resource, i.e. a URL;\n>\n>      - the type of resource, if we want this to be extensible.  I\n>        think we should initially limit it to \"a single full history\n>        .pack\", so from that point of view this may not be absolutely\n>        necessary, but we already know that we may want to say \"go\n>        there and you will find an old-style bundle file\" to support\n>        the kernel.org CDN, and we may also want to support Jeff's\n>        \"split bundle\" or Shawn's \".info\" file.  A resource poor\n>        (read: personal) machine that hosts a personal of a popular\n\nSorry for a typo: s/of a/fork &/;\n\n>        project might want to name a \"git clone\" URL for that popular\n>        project it forked from (e.g. \"Clone Linus's repository from\n>        kernel.org and then come back here for incremental fetch\").\n"},{"id":"280273","messageId":"alpine.DEB.2.20.1603060831570.3152@virtualbox","threadId":"41620","inReplyTo":"xmqqoaasvkrt.fsf@gitster.mtv.corp.google.com","subject":"Re: Resumable clone","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-03-06T07:59:10Z","receivedAt":"2016-03-06T07:59:10Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio & Duy,\n\nOn Sat, 5 Mar 2016, Junio C Hamano wrote:\n\n> Duy Nguyen <pclouds@gmail.com> writes:\n> \n> > Resumable clone is happening. See [1] for the basic idea, [2] and [3]\n> > for some preparation work. I'm sure you can help. Once you've gone\n> > through at least [1], I think you can pick something (e.g. finalizing\n> > the protocol, update the server side, or git-clone....)\n> >\n> > [1] http://thread.gmane.org/gmane.comp.version-control.git/285921\n> > [2] http://thread.gmane.org/gmane.comp.version-control.git/288080/focus=288150\n> > [3] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n> \n> I think your response needs to be refined with a bit higher level\n> overview, though.  Here are some thoughts to summarize the discussion\n> and to extend it.\n> \n> I think the right way to think about this is that we are adding a\n> capability for the server to instruct the clients: I prefer not to\n> serve a full clone to you in the usual route if I can avoid it.  You\n> can help me by going to an alternate resource and populate your\n> history first and then coming back to me for an additional fetch to\n> complete the history if you want to.  Doing so would also help you\n> because that alternate resource can be a static file (or two) that\n> you can download over a resumable transport (like static files\n> served over HTTPS).\n\nFor quite some time I considered presenting some alternate/additional\nideas. I feel a little bad for mentioning them here because I *really*\nhave no time to follow up on them whatsoever. But maybe they turn out to\ncontribute something to the final solution.\n\nI tried to follow the discussion as much as possible, sometimes failing\ndue to time constraints, therefore I'd like to apologize in advance if any\nof these ideas have been mentioned already.\n\nFirst of all: my main gripe with the discussed approach is that it uses\nbundles. I know, I introduced bundles, but they just seem too klunky and\ntoo static for the resumable clone feature.\n\nSo I wonder whether it would be possible to come up with a subset of the\nrevs with a stable order, with associated thin packs (using prior revs as\nnegative revs in the commit range) such that each thin pack weighs roughly\n1MB (or whatever granularity you desire). My thinking was that it should\nbe possible to follow a similar strategy as bisect to come up with said\nlist.\n\nThe client could then state that it was interrupted at downloading a given\nrev's pack, with a specific offset, and the (thin) pack could be\nregenerated on the fly (or cached), serving only the desired chunk. The\nserver would then also automatically know where in the list of\nstable-ordered revs the clone was interrupted and continue with the next\none.\n\nOh, and if regenerating the thin pack instead of caching it, we need to\nensure a stable packing (i.e. no threads!). That is, given a commit range,\nwe need to (re-)generate bytewise-identical thin packs.\n\nOf course this stable-ordered rev list would have to be persisted when the\nserver serves its first resumable clone and then extended with future\nresumable clones whenever new revisions were pushed. (And there would also\nhave to be some way to evict no-longer-reachable revs, maybe by simply\nregenerating the whole shebang.)\n\nFor all of this to work, the most crucial idea would be this one: a clone\ncan *always* start as-is. Only when interrupted, and when the server\nsupports the \"resumable clone\" capability, and only when \"resuming\"\nthe clone, the client could *actually* ask for a resumable clone.\n\nYes, this could potentially waste a bit of bandwidth on the part of the\nuser with a flakey connection (because whatever was transferred during the\nfirst, non-resumable clone would be blown out of the window), but it might\nmake it easier for us to provide a non-fragile upgrade path because the\ncloning process would still default to the current one.\n\nFood for thought?\n\nCiao,\nDscho\n"},{"id":"280274","messageId":"CACsJy8Donxwx0LE0jDwpLbS4D-m4JzWne29GHAG0jfh2CH3pdQ@mail.gmail.com","threadId":"41620","inReplyTo":"alpine.DEB.2.20.1603060831570.3152@virtualbox","subject":"Re: Resumable clone","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-03-06T08:49:49Z","receivedAt":"2016-03-06T08:49:49Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 6, 2016 at 2:59 PM, Johannes Schindelin\n<Johannes.Schindelin@gmx.de> wrote:\n> First of all: my main gripe with the discussed approach is that it uses\n> bundles. I know, I introduced bundles, but they just seem too klunky and\n> too static for the resumable clone feature.\n\nOne thing Junio didn't mention in his summary is the use of pack\nbitmap [1]. Jeff talked about GitHub specific needs, but I think it\nhas values even outside of GitHub: if people store some secret refs in\nthe initial pack (e.g. hidden by ref namespace, or in reflog - imagine\nsomeone committed a password and did a reset --hard then pushed\nagain), they probably do not want to publish initial pack as-is. With\npack bitmap, we can sort of recreate the \"clean initial pack\" on the\nfly relatively cheaply because all object order is stable in this\nparticular pack. We go a tiny bit less static with this resume+pack\nbitmap combination.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n\n> So I wonder whether it would be possible to come up with a subset of the\n> revs with a stable order, with associated thin packs (using prior revs as\n> negative revs in the commit range) such that each thin pack weighs roughly\n> 1MB (or whatever granularity you desire). My thinking was that it should\n> be possible to follow a similar strategy as bisect to come up with said\n> list.\n>\n> The client could then state that it was interrupted at downloading a given\n> rev's pack, with a specific offset, and the (thin) pack could be\n> regenerated on the fly (or cached), serving only the desired chunk. The\n> server would then also automatically know where in the list of\n> stable-ordered revs the clone was interrupted and continue with the next\n> one.\n>\n> Oh, and if regenerating the thin pack instead of caching it, we need to\n> ensure a stable packing (i.e. no threads!). That is, given a commit range,\n> we need to (re-)generate bytewise-identical thin packs.\n\nThe bytewise-identical idea is already shot down. But I like the\nsplitting into multiple thin packs (and re-downloading the whole thin\npack when failed). Multiple thin packs allow resume capability.\nChaining thin packs saves bandwidth. And pack-objects still has\nfreedom doing anything inside each thin pack. For gigantic repos and\ngood-enough connections, this could work (even for fetch/pull).\n\nThe biggest problem I see is it's hard for rev-list to split thin\npacks based on pack size because we do not know that until\npack-objects has consumed all revs and produced the pack.\nApproximation based on the number of objects should probably be ok\nunless there are very large blobs. But that probably should be\naddressed separately by the resurrection of Junio's split-blob series.\n-- \nDuy\n"},{"id":"280275","messageId":"CACsJy8BgZ+62mLnNLLAuKbAjyfaoNGm3Zhxe4N-XEo-w9a17DA@mail.gmail.com","threadId":"41620","inReplyTo":"CACsJy8Donxwx0LE0jDwpLbS4D-m4JzWne29GHAG0jfh2CH3pdQ@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-03-06T08:52:11Z","receivedAt":"2016-03-06T08:52:11Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 6, 2016 at 3:49 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n> One thing Junio didn't mention in his summary is the use of pack\n> bitmap [1]. ....\n>\n> [1] http://thread.gmane.org/gmane.comp.version-control.git/288205/focus=288222\n\nOops, wrong link. Should be this one\n\nhttp://article.gmane.org/gmane.comp.version-control.git/288258\n-- \nDuy\n"},{"id":"280300","messageId":"xmqqh9gjtmkq.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"CACsJy8Donxwx0LE0jDwpLbS4D-m4JzWne29GHAG0jfh2CH3pdQ@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-06T19:48:05Z","receivedAt":"2016-03-06T19:48:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> One thing Junio didn't mention in his summary is the use of pack\n> bitmap [1]. Jeff talked about GitHub specific needs,...\n\nDo not take it as the \"summary of the whole discussion\".\n\nI deliberately tried to limit the list to absolute minimum to allow\nbuilding a workable initial version while leaving the door open for\nfuture extension.  There are other things that I didn't mention\nbecause they would not have to be in the absolute minimum necessary\nfor such an initial design.\n"},{"id":"280315","messageId":"xmqq37s3rlg4.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"alpine.DEB.2.20.1603060831570.3152@virtualbox","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-07T03:55:23Z","receivedAt":"2016-03-07T03:55:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> First of all: my main gripe with the discussed approach is that it uses\n> bundles. I know, I introduced bundles, but they just seem too klunky and\n> too static for the resumable clone feature.\n\nWe should make the mechanism extensible so that we can later support\nmultiple \"alternate resource\" formats, and \"bundle\" could be one of\nthe options, my current thinking is that the initial version should\nuse just a bare packfile to bootstramp, not a bundle.\n\nThe format being \"static\" is both a feature and a practical\ncompromise.  It is a feature to allow clone traffic, which is a\nsignificant portion of the whole traffic to hosting sites, diverted\noff of the core server network for a busy hosting site, saving both\nnetworking and CPU cost.  And that benefit will be felt even if the\nclient has a good enough connection to the server that it does not\nhave to worry about resuming.  It is a practical compromise that the\nmechanism will not be extensible for helping incremental fetch but I\nheard that the server side statistics tells us that there aren't\nmany \"duplicate incremental fetch\" requests (i.e. many clients\nhaving the same set of \"have\"s so that the server side can prepare,\nserve, and cache the same incremental pack, which can be served on a\nresumable transport, to help resuming clients by supporting\npartial/range requests), I do not think it is practical to try to\nuse the same mechanism to help incremental and clone traffic.  One\nsize would not fit both here.\n\nI think a better approach to help incremental fetches is along the\nline of what was discussed in the discussion with Al Viro and others\nthe other day.  You'd need various building blocks implemented anew,\nincluding:\n\n - A protocol extension to allow the client to tell the server a\n   list of \"not necessarily connected\" objects that it has, so that\n   the server side can exclude them from the set of objects the\n   traditional \"have\"-\"ack\" exchange would determine to be sent when\n   building a pack.\n\n   - A design of deciding what \"list of objects\" is worth sending to\n     the server side.  The total number of objects in the receiving\n     end is an obvious upper bound, and it might be sufficient to\n     send the whole thing as-is, but there may be more efficient way\n     to determine this set [*1*]\n\n - A way to salvage objects from a truncated pack, as there is no\n   such tool in core-git.\n\n\n[Footnote]\n\n*1* Once the traditional \"have\"-\"ack\" determines the set of objects\n    the sender thinks the receiver may not have, we need to figure\n    out the ones that happen to exist on the receiver end already,\n    either because they were salvaged from a truncated pack data it\n    received earlier, or perhaps because they already existed by\n    fetching from a side branch (e.g. two repositories derived from\n    the same upstream, updating from Linus's kernel tree by somebody\n    who regularly interacts with linux-next tree), and exclude them\n    from the set of objects sent from the sender.\n\n    I've long felt that Eppstein's invertible bloom filter might be\n    a good way to determine efficiently, among the set of objects\n    the sending and the receiving ends have, which ones are common,\n    but I didn't look into this deeply myself.\n"},{"id":"280348","messageId":"CANtyZjRZzXabeWEhwCrwN_q_Zsrm1f_d+j2uDhTZeEjv3LjxaA@mail.gmail.com","threadId":"41620","inReplyTo":"xmqqoaasvkrt.fsf@gitster.mtv.corp.google.com","subject":"Re: Resumable clone","fromName":"Kevin Wern","fromEmail":"kevin.m.wern@gmail.com","sentAt":"2016-03-08T03:33:40Z","receivedAt":"2016-03-08T03:33:40Z","isPatch":false,"sender":{"key":"kevin.m.wern@gmail.com","avatar":null},"body":"Hey Junio and Duy,\n\nThank you for your thorough responses! I'm new to git dev, so it's\nextremely helpful.\n\n> - The server side endpoint does not have to be, and I think it\n> should not be, implemented as an extension to the current\n> upload-pack protocol. It is perfectly fine to add a new \"git\n> prime-clone\" program next to existing \"git upload-pack\" and\n> \"git receive-pack\" programs and drive it through the\n> git-daemon, curl remote helper, and direct execution over ssh.\n\nI'd like to work on this, and continue through to implementing the\nprime_clone() client-side function.\n\n>From what I understand, a pattern exists in clone to download a\npackfile when a desired object isn't found as a resource. In this\ncase, if no alternative is listed in http-alternatives, the client\nautomatically checks the pack index(es) to see which packfile contains\nthe object it needs.\n\nHowever, the above is a fallback. What I believe *doesn't* exist is a\nway for the server to say, \"I have a resource, in this case a\nfull-history packfile, and I *prefer* you get that file instead of\nattempting to traverse the object tree.\" This should be implemented in\na way that is extensible to other resource types moving forward.\n\nI'm not sure how the server should determine the returned resource. A\npackfile alone does not guarantee the full repo history, and I'm not\npositive checking the idx file for HEAD's commit hash ensures every\nsub-object is in that file (though I feel it should, because it is\ndelta-compressed). With that in mind, my best guess at the server\nlogic for packfiles is something like:\n\nDo I have a full history packfile, and am I configured to return one?\n- If yes, then return an answer specifying the file url and type (packfile)\n- Otherwise, return some other answer indicating the client must go\nthrough the original cloning process (or possibly return a different\nkind of file and type, once we expand that capability)\n\nWhich leaves me with questions on how to test the above condition. Is\nthere an expected place, such as config, where the user will specify\nthe type of alternate resource, and should we assume some default if\nit isn't specified? Can the user optionally specify the exact file to\nuse (I can't see why because it only invites more errors)? Should the\nspecification of this option change git's behavior on update, such as\nmaking sure the full history is compressed? Does the existence of the\nHEAD object in the packfile ensure the repo's entire history is\ncontained in that file?\n\nAlso, for now I'm assuming the same options should be available for\nprime-clone as are available for upload-pack (--strict,\n--timeout=<n>). Let me know if any other features are necessary.\nAlso, let me know if I'm headed in the complete wrong direction...\n\nThank you so much for your help!\n"},{"id":"280360","messageId":"CACsJy8A_jkvdJPgBQ_huP-t8a0ra2RfP7jZ7C-ONNm87ktYaiA@mail.gmail.com","threadId":"41620","inReplyTo":"CANtyZjRZzXabeWEhwCrwN_q_Zsrm1f_d+j2uDhTZeEjv3LjxaA@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-03-08T11:11:19Z","receivedAt":"2016-03-08T11:11:19Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 8, 2016 at 10:33 AM, Kevin Wern <kevin.m.wern@gmail.com> wrote:\n> Hey Junio and Duy,\n>\n> Thank you for your thorough responses! I'm new to git dev, so it's\n> extremely helpful.\n>\n>> - The server side endpoint does not have to be, and I think it\n>> should not be, implemented as an extension to the current\n>> upload-pack protocol. It is perfectly fine to add a new \"git\n>> prime-clone\" program next to existing \"git upload-pack\" and\n>> \"git receive-pack\" programs and drive it through the\n>> git-daemon, curl remote helper, and direct execution over ssh.\n>\n> I'd like to work on this, and continue through to implementing the\n> prime_clone() client-side function.\n\nGreat! Although I think you started with the most configurable part,\nsomething to work out I guess.\n\n> From what I understand, a pattern exists in clone to download a\n> packfile when a desired object isn't found as a resource. In this\n> case, if no alternative is listed in http-alternatives, the client\n> automatically checks the pack index(es) to see which packfile contains\n> the object it needs.\n\nI don't follow this. What is \"a resource\"?\n\n> However, the above is a fallback. What I believe *doesn't* exist is a\n> way for the server to say, \"I have a resource, in this case a\n> full-history packfile\n\nah a resource could be the pack file to be downloaded, ok..\n\n> , and I *prefer* you get that file instead of\n> attempting to traverse the object tree.\" This should be implemented in\n> a way that is extensible to other resource types moving forward.\n>\n> I'm not sure how the server should determine the returned resource. A\n> packfile alone does not guarantee the full repo history\n\nThat's for the later part. At this point, I think the update \"git\nclone\" will request the new service you're writing and ask \"do you\nhave a resumable pack I can download?\" and it can return an URL. Then\nprime_clone() proceeds to download and figure out what's in that pack.\n\nYeah the determination is tricky, it depends on server setup. Let's\nstart with select the pack for download first because there could be\nmany of them. A heuristic (*) of choosing the biggest one in\n$GIT_DIR/objects/pack is probably ok for now (we don't need full\nhistory, \"the biggest part of history\" is good enough). Then we get\nthe pack file name, which can be used as pack ID.\n\nFor the simplest setup, I suppose the admin would give us an URL\nprefix (or multiple prefixes), e.g. http://myserver.com/cache-here/\nand we are supposed to append the pack file name to it, and the full\nURL would be http://myserver.com/cache-here/pack-$SHA1.pack. This is\nwhat the new service will return to git-clone.\n\nFor more complex setup, I guess the admin can provide a script that\ntakes pack id as key and returns the list of URLs for us. They can\ngive us the path to this script via config file.\n\n(*) The source of producing this cached pack (and maybe sending them\nto CDN) is git-repack. But when it's done and how it's done is really\nup to admins. So the admin really needs to provide us a script or\nsomething that provides this info back, if we want to avoid\nheuristics. Such a script can even choose to ignore the given pack id\nand output URLs based on repository identify only.\n\n> , and I'm not\n> positive checking the idx file for HEAD's commit hash ensures every\n> sub-object is in that file (though I feel it should, because it is\n> delta-compressed). With that in mind, my best guess at the server\n> logic for packfiles is something like:\n>\n> Do I have a full history packfile, and am I configured to return one?\n> - If yes, then return an answer specifying the file url and type (packfile)\n> - Otherwise, return some other answer indicating the client must go\n> through the original cloning process (or possibly return a different\n> kind of file and type, once we expand that capability)\n\nWell, the lack of this new service should be enough for git-clone to\nfall back to normal cloning protocol. The admin must enable this\nservice in git-daemon first if they want to use it. If there's no\nsuitable URL to show, it's ok to just disconnect. git-clone must be\nable to deal with that and fall back.\n\n> Which leaves me with questions on how to test the above condition. Is\n> there an expected place, such as config, where the user will specify\n> the type of alternate resource, and should we assume some default if\n> it isn't specified? Can the user optionally specify the exact file to\n> use (I can't see why because it only invites more errors)? Should the\n> specification of this option change git's behavior on update, such as\n> making sure the full history is compressed? Does the existence of the\n> HEAD object in the packfile ensure the repo's entire history is\n> contained in that file?\n\nI think some of these questions are basically \"ask admins\", the other\nhalf we can deal with when implementing prime_clone().\n\nFollowing up what I wrote above. Suppose your service's name is\nclone-download (or any other name), the config variable\ndaemon.clonedownload must be set in order to turn this service on.\nWithout it, git-clone falls back to normal clone. Then we could either\nhave config clonedownload.prefix or clonedownload.script. Or something\nlike that.\n\nAlso, we made a mistake before with transport protocol where the\nserver talks first. I'm thinking this time, maybe we do it\ndifferently. git-clone connects to the service, then tells the server\nabout its capability and whatever else (e.g. physical localtion, the\nmax number of URLs it wants to receive...). The server waits for that\nfirst, then it can send URLs back to the client, then disconnect.\n\nUnless there's something very sepcial, I think we just follow current\nprotocol and use pkt-line for communication (see \"pkt-line Format\" in\nDocumentation/technical/pack-protocol.txt). We send one URL per\npkt-line, terminated with null pkt-line.\n\nAll this is about full duplex connections (git:// or ssh://). Smart\nhttp is not mentioned. But I think a simple GET request is enough for\nthis (you'll have to touch http.c, but that can wait).\n\n> Also, for now I'm assuming the same options should be available for\n> prime-clone as are available for upload-pack (--strict,\n> --timeout=<n>). Let me know if any other features are necessary.\n> Also, let me know if I'm headed in the complete wrong direction...\n\nHeh.. I didn't know upload-pack took  --timeout :D --strict should be\nthere (repository discovery is the same everywhere). Not so sure about\n--timeout (upload-pack can take a long time so timeout gives more\nresource control, this new services should be instant)\n-- \nDuy\n"},{"id":"280374","messageId":"xmqq4mcgnbkb.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"CANtyZjRZzXabeWEhwCrwN_q_Zsrm1f_d+j2uDhTZeEjv3LjxaA@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-08T17:07:00Z","receivedAt":"2016-03-08T17:07:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Wern <kevin.m.wern@gmail.com> writes:\n\n> From what I understand, a pattern exists in clone to download a\n> packfile when a desired object isn't found as a resource. In this\n> case, if no alternative is listed in http-alternatives, the client\n> automatically checks the pack index(es) to see which packfile contains\n> the object it needs.\n\nYou sound as if you are describing how a fetch over the dumb commit\nwalker http transport works.  That does not have anything to do with\nthe discussion of resumable clone, though, so I am not sure where\nyou are going with this.\n\n> What I believe *doesn't* exist is a\n> way for the server to say, \"I have a resource, in this case a\n> full-history packfile, and I *prefer* you get that file instead of\n> attempting to traverse the object tree.\" This should be implemented in\n> a way that is extensible to other resource types moving forward.\n\nYes, that is very close to what I said in the \"what remains?\"\nsection, but with a crucial difference in a detail.  Perhaps reading\nthe message you are respoinding to again more carefully will clear\nthe confusion.  This is what we want to allow the server to say\n(from the message you are responding to, but rephrased slightly,\nhoping that it would help unconfuse you):\n\n    I prefer not to serve a full clone to you in the usual route if\n    I can avoid it.  You can help me by populate your history first\n    with something else (which would bring you to a state as if you\n    cloned potentially a bit older version of me) and then coming\n    back to me for an additional fetch to complete the history.\n\nThat \"something else\" does not have to be, and is not expected to\nbe, the \"full\" history of the current state.  As long as it can be\nused to bring the cloner to a reasonably recent state, sufficient to\nmake a follow up incremental fetch inexpesive enough, it is\nappropriate.\n\n> I'm not sure how the server should determine the returned resource. A\n> packfile alone does not guarantee the full repo history, and I'm not\n> positive checking the idx file for HEAD's commit hash ensures every\n> sub-object is in that file (though I feel it should, because it is\n> delta-compressed).\n\nThe above reasoning does not make much technical sense.  delta\ncompression does not ensure connectivity in the commit history and\ncommit->tree->blob containment.  Again I am not sure where you are\ngoing with this.\n\n> With that in mind, my best guess at the server\n> logic for packfiles is something like:\n>\n> Do I have a full history packfile, and am I configured to return one?\n> - If yes, then return an answer specifying the file url and type (packfile)\n> - Otherwise, return some other answer indicating the client must go\n> through the original cloning process (or possibly return a different\n> kind of file and type, once we expand that capability)\n\nRoughly speaking, yes.\n\n> Which leaves me with questions on how to test the above condition. Is\n> there an expected place, such as config, where the user will specify\n> the type of alternate resource, and should we assume some default if\n> it isn't specified? Can the user optionally specify the exact file to\n> use (I can't see why because it only invites more errors)? Should the\n> specification of this option change git's behavior on update, such as\n> making sure the full history is compressed? Does the existence of the\n> HEAD object in the packfile ensure the repo's entire history is\n> contained in that file?\n\nThose (except for your assumption that no follow-up fetch is\nallowed, which requires you to limit yourself to \"full\" history,\nwhich is an unnecessary requirement) are good points one should be\nmaking design decisions on when building this part of the system.\n"},{"id":"280375","messageId":"xmqqy49slw54.fsf@gitster.mtv.corp.google.com","threadId":"41620","inReplyTo":"CACsJy8A_jkvdJPgBQ_huP-t8a0ra2RfP7jZ7C-ONNm87ktYaiA@mail.gmail.com","subject":"Re: Resumable clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-08T17:25:27Z","receivedAt":"2016-03-08T17:25:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> Yeah the determination is tricky, it depends on server setup. Let's\n> start with select the pack for download first because there could be\n> many of them. A heuristic (*) of choosing the biggest one in\n> $GIT_DIR/objects/pack is probably ok for now (we don't need full\n> history, \"the biggest part of history\" is good enough).\n\nYou need to choose a pack that is fully connected, though.  I was\nenvisioning that an updated \"git repack\" would have an extra option\nthat help server operators to manage it easily.  You would need to\nconsider for example:\n\n - You may not want to rebuild such a base pack too frequently\n   (e.g. you may want to repack a busy repository twice a day, but\n   you would want to redo the base pack only once a week).  It is\n   possible to mark it with .keep for subsequent repacks to leave it\n   alone, but there needs a mechanism to manage that .keep marker.\n\n - You may not want to have all refs in such a base pack (e.g. you\n   may want to exclude refs/changes/ from it).  There need to be a\n   configuration to specify which refs are included in the base\n   pack.\n\nwhile designing such an update.  Then the repack with such an option\nwould roughly be:\n\n    - If it is time to redo a base repack, then\n\n      - unplug the .keep bit the previous base pack has;\n\n      - create a pack that contains full history reachable from the\n        specified refs;\n\n      - mark the new base pack as such;\n\n    - Pack all objects that are not in the base pack that are\n      reachable from any refs (and other anchoring points, such as\n      reflogs and the index) into a separate pack.\n\nAnd the prime_clone() advertisement would be just the matter of\nknowing how the \"base\" pack is marked in the above process.\n"},{"id":"280405","messageId":"CANtyZjRw57kru=7RvF1Q+uTsoF+0YKynA2Y0FQYK5PBFxSoPNQ@mail.gmail.com","threadId":"41620","inReplyTo":"xmqq4mcgnbkb.fsf@gitster.mtv.corp.google.com","subject":"Re: Resumable clone","fromName":"Kevin Wern","fromEmail":"kevin.m.wern@gmail.com","sentAt":"2016-03-09T02:04:50Z","receivedAt":"2016-03-09T02:04:50Z","isPatch":false,"sender":{"key":"kevin.m.wern@gmail.com","avatar":null},"body":"Junio,\n\n> Yes, that is very close to what I said in the \"what remains?\"\n> section, but with a crucial difference in a detail.  Perhaps reading\n> the message you are respoinding to again more carefully will clear\n> the confusion.  This is what we want to allow the server to say\n> (from the message you are responding to, but rephrased slightly,\n> hoping that it would help unconfuse you):\n>\n>     I prefer not to serve a full clone to you in the usual route if\n>     I can avoid it.  You can help me by populate your history first\n>     with something else (which would bring you to a state as if you\n>     cloned potentially a bit older version of me) and then coming\n>     back to me for an additional fetch to complete the history.\n>\n> That \"something else\" does not have to be, and is not expected to\n> be, the \"full\" history of the current state.  As long as it can be\n> used to bring the cloner to a reasonably recent state, sufficient to\n> make a follow up incremental fetch inexpesive enough, it is\n> appropriate.\n\nSorry, I was thrown off by:\n\n> - the type of resource, if we want this to be extensible.  I\n>   think we should initially limit it to \"a single full history\n>   .pack\",\n\nI misinterpreted what you meant by \"a single full history .pack,\" and\nused that to limit what you said earlier. A lot of my reasoning from\nthere misses the point, then, because it involved finding some way to\ndetermine if a history .pack contains the full history, which\nobviously is irrelevant.\n\n>> I'm not sure how the server should determine the returned resource. A\n>> packfile alone does not guarantee the full repo history, and I'm not\n>> positive checking the idx file for HEAD's commit hash ensures every\n>> sub-object is in that file (though I feel it should, because it is\n>> delta-compressed).\n>\n> The above reasoning does not make much technical sense.  delta\n> compression does not ensure connectivity in the commit history and\n> commit->tree->blob containment.  Again I am not sure where you are\n> going with this.\n\nRelated to the above, I was trying to find a way to determine if the\npackfile contained the full history, which actually doesn't matter. My\ntechnical reasoning was affected by the way deltas represent changes\nin other VCS's, but I realize now that git's delta compression is\nbased around the similarity of objects, not their historical relation\nto each other.\n\n>> Which leaves me with questions on how to test the above condition. Is\n>> there an expected place, such as config, where the user will specify\n>> the type of alternate resource, and should we assume some default if\n>> it isn't specified? Can the user optionally specify the exact file to\n>> use (I can't see why because it only invites more errors)? Should the\n>> specification of this option change git's behavior on update, such as\n>> making sure the full history is compressed? Does the existence of the\n>> HEAD object in the packfile ensure the repo's entire history is\n>> contained in that file?\n>\n> Those (except for your assumption that no follow-up fetch is\n> allowed, which requires you to limit yourself to \"full\" history,\n> which is an unnecessary requirement) are good points one should be\n> making design decisions on when building this part of the system.\n\nAwesome, all of this is enough info to get me started. Thanks!\n\nKevin\n"}]}