{"thread":{"id":"53035","subject":"[RFC PATCH] fetch-pack: lazy fetch using tree:0","startedAt":"2020-03-19T17:44:47Z","lastAt":"2020-03-27T09:37:14Z","messageCount":5,"participants":["Jonathan Tan","Derrick Stolee","Jeff King","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"393483","messageId":"20200319174439.230969-1-jonathantanmy@google.com","threadId":"53035","inReplyTo":null,"subject":"[RFC PATCH] fetch-pack: lazy fetch using tree:0","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-03-19T17:44:39Z","receivedAt":"2020-03-19T17:44:47Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Support for partial clones with filtered trees was added in bc5975d24f\n(\"list-objects-filter: implement filter tree:0\", 2018-10-07), but\nwhenever a lazy fetch of a tree is done, besides the tree itself, some\nother objects that it references are also fetched.\n\nThe \"blob:none\" filter was added to lazy fetches in 4c7f9567ea\n(\"fetch-pack: exclude blobs when lazy-fetching trees\", 2018-10-04) to\nrestrict blobs from being fetched, but it didn't restrict trees.\n(\"tree:0\", which would restrict all trees as well, wasn't added then\nbecause \"tree:0\" was itself new and may not have been supported by Git\nservers, as you can see from the dates of the commits.)\n\nNow that \"tree:0\" has been supported in Git for a while, teach lazy\nfetches to use \"tree:0\" instead of \"blob:none\".\n\n(An alternative to doing this is to teach Git a new filter that only\nreturns exactly the objects requested, no more - but \"tree:0\" already\ndoes that for us for now, hence this patch. If we were to support\nfiltering of commits in partial clones later, I think that specifying a\ndepth will work to restrict the commits returned, so we won't need an\nadditional filter anyway.)\n---\nThis looks like a good change to me - in particular, it makes Git align\nwith the (in my opinion, reasonable) mental model that when we lazily\nfetch something, we only fetch that thing. Some issues that I can think\nabout:\n\n - Some hosts like GitHub support some partial clone filters, but not\n   \"tree:0\".\n - I haven't figured out the performance implications yet. If we want a\n   tree, I think that we typically will want some of its subtrees, but\n   not all.\n\nAny thoughts?\n---\n fetch-pack.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 1734a573b0..655ec5d4a3 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -1747,14 +1747,14 @@ struct ref *fetch_pack(struct fetch_pack_args *args,\n \t\t/*\n \t\t * The protocol does not support requesting that only the\n \t\t * wanted objects be sent, so approximate this by setting a\n-\t\t * \"blob:none\" filter if no filter is already set. This works\n-\t\t * for all object types: note that wanted blobs will still be\n+\t\t * \"tree:0\" filter if no filter is already set. This works\n+\t\t * for all object types: note that wanted blobs and trees will still be\n \t\t * sent because they are directly specified as a \"want\".\n \t\t *\n \t\t * NEEDSWORK: Add an option in the protocol to request that\n \t\t * only the wanted objects be sent, and implement it.\n \t\t */\n-\t\tparse_list_objects_filter(&args->filter_options, \"blob:none\");\n+\t\tparse_list_objects_filter(&args->filter_options, \"tree:0\");\n \t}\n \n \tif (version != protocol_v2 && !ref) {\n-- \n2.25.1.696.g5e7596f4ac-goog\n\n"},{"id":"393485","messageId":"593efac4-75f8-df74-259d-83dd8297aa3f@gmail.com","threadId":"53035","inReplyTo":"20200319174439.230969-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] fetch-pack: lazy fetch using tree:0","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-19T19:58:33Z","receivedAt":"2020-03-19T19:58:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/19/2020 1:44 PM, Jonathan Tan wrote:\n> Support for partial clones with filtered trees was added in bc5975d24f\n> (\"list-objects-filter: implement filter tree:0\", 2018-10-07), but\n> whenever a lazy fetch of a tree is done, besides the tree itself, some\n> other objects that it references are also fetched.\n> \n> The \"blob:none\" filter was added to lazy fetches in 4c7f9567ea\n> (\"fetch-pack: exclude blobs when lazy-fetching trees\", 2018-10-04) to\n> restrict blobs from being fetched, but it didn't restrict trees.\n> (\"tree:0\", which would restrict all trees as well, wasn't added then\n> because \"tree:0\" was itself new and may not have been supported by Git\n> servers, as you can see from the dates of the commits.)\n> \n> Now that \"tree:0\" has been supported in Git for a while, teach lazy\n> fetches to use \"tree:0\" instead of \"blob:none\".\n> \n> (An alternative to doing this is to teach Git a new filter that only\n> returns exactly the objects requested, no more - but \"tree:0\" already\n> does that for us for now, hence this patch. If we were to support\n> filtering of commits in partial clones later, I think that specifying a\n> depth will work to restrict the commits returned, so we won't need an\n> additional filter anyway.)\n> ---\n> This looks like a good change to me - in particular, it makes Git align\n> with the (in my opinion, reasonable) mental model that when we lazily\n> fetch something, we only fetch that thing. Some issues that I can think\n> about:\n> \n>  - Some hosts like GitHub support some partial clone filters, but not\n>    \"tree:0\".\n>  - I haven't figured out the performance implications yet. If we want a\n>    tree, I think that we typically will want some of its subtrees, but\n>    not all.\n> \n> Any thoughts?\n\nThe end result of fetching missing objects one-by-one matches how the\nGVFS protocol has handled these tree misses in the past. While there\nmay be a lot more round trips, it saves on excess data since a\nmissing tree likely can reach several known trees and blobs.\n\nThe real unknown here is how the \"boundary\" of missing trees is\ncreated. In the GVFS protocol, missing trees happen mostly when our\npre-computed \"prefetch pack-files\" of commits and trees are behind the\nref tips.\n\nThe usage pattern for depth-limited or path-scoped filters is not\nquite as established as the blob-limited patterns (because they are\nsimilar to the behavior in VFS for Git and Scalar).\n\nThe code seems to be doing what you say, but I highly recommend taking\nthis for a spin on a real repository with a real remote, if possible.\nThe more that we could get some numbers for which situations do better\nin one case or the other, the more this change can be adopted with\nconfidence.\n\nThanks,\n-Stolee\n"},{"id":"393519","messageId":"20200320061214.GA511478@coredump.intra.peff.net","threadId":"53035","inReplyTo":"20200319174439.230969-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] fetch-pack: lazy fetch using tree:0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-20T06:12:14Z","receivedAt":"2020-03-20T06:12:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 19, 2020 at 10:44:39AM -0700, Jonathan Tan wrote:\n\n> Support for partial clones with filtered trees was added in bc5975d24f\n> (\"list-objects-filter: implement filter tree:0\", 2018-10-07), but\n> whenever a lazy fetch of a tree is done, besides the tree itself, some\n> other objects that it references are also fetched.\n> \n> The \"blob:none\" filter was added to lazy fetches in 4c7f9567ea\n> (\"fetch-pack: exclude blobs when lazy-fetching trees\", 2018-10-04) to\n> restrict blobs from being fetched, but it didn't restrict trees.\n> (\"tree:0\", which would restrict all trees as well, wasn't added then\n> because \"tree:0\" was itself new and may not have been supported by Git\n> servers, as you can see from the dates of the commits.)\n> \n> Now that \"tree:0\" has been supported in Git for a while, teach lazy\n> fetches to use \"tree:0\" instead of \"blob:none\".\n\nThis does mean a new client fetching objects for a partial clone from an\nolder server (pre-bc5975d24f) used to work, but now won't (we couldn't\nhave fetched from it with a tree filter, but this patch makes the use of\ntree:0 unconditional; so even a blob:none followup fetch would use it).\nI'm not _too_ broken up about that, given that partial clone support at\nthat era was pretty clearly labeled as experimental. But it would be a\nnice bonus to make it work everywhere.\n\n> (An alternative to doing this is to teach Git a new filter that only\n> returns exactly the objects requested, no more - but \"tree:0\" already\n> does that for us for now, hence this patch. If we were to support\n> filtering of commits in partial clones later, I think that specifying a\n> depth will work to restrict the commits returned, so we won't need an\n> additional filter anyway.)\n\nThe depth thing might work for commits, though there are a lot of\nspecial code paths taken when the client is asking for shallow commits\nthat might be better avoided.\n\nBeing able to say \"only send me the objects I'm asking for\" seems like a\nmuch more direct way. It doesn't even need to be a filter, really; it\ncould be a protocol capability. And in fact I think we'd want a\ncapability either way, because clients would ideally be able to send the\nold \"blob:none\" for older servers, or the new \"only what I'm asking for\"\nwith new servers.\n\n> ---\n> This looks like a good change to me - in particular, it makes Git align\n> with the (in my opinion, reasonable) mental model that when we lazily\n> fetch something, we only fetch that thing. Some issues that I can think\n> about:\n\nYeah, I like the mental model. I just think it should be expressed even\nmore explicitly. :)\n\n>  - Some hosts like GitHub support some partial clone filters, but not\n>    \"tree:0\".\n\nYes, this is going to fail against GitHub servers, just like it would\nfor older servers. One way to prevent that would be to use a \"blob\"\nfilter if that's what we originally partial-cloned with. I don't know if\nthat information always reliably makes it into this code path, though.\nI think I'd prefer a capability-based fix in the long run.\n\nWe may support \"tree:0\" eventually at GitHub. It's quick to compute with\nbitmaps, just like \"blob:none\" is. But \"tree:1\" isn't.\n\nOne side note (for Taylor, cc'd): our patches elsewhere to limit the\nallowed filters don't make it possible to express the difference between\n\"tree:0\" and \"tree:1\". It may be worth thinking about that, especially\nif it influences the config schema (since we'll have to support it\nforever once it makes it into a release).\n\n>  - I haven't figured out the performance implications yet. If we want a\n>    tree, I think that we typically will want some of its subtrees, but\n>    not all.\n\nI could imagine a scenario where you want to get trees one level at a\ntime in order to only grab the sub-trees you want based on pathnames\n(sort of like sparse-checkout's cone mode). Though you do get into \"n+1\"\nfetches based on tree depth there. If the latency for a fetch is high,\nit will be pretty painful.\n\nI can equally imagine there are cases where you want to grab the whole\nsubtree in one go, but I think that raises another performance issue:\nyou might already have most of it. E.g., consider a root tree with one\ntoplevel subtree that contains a million files. You already have the\nroot tree at some commit A. Now you want to diff against its parent, B.\nYou ask the server for B^{tree}, and it sends you the million-entry\ntree, too (and maybe some blobs?). You could tell it you already have\nthem, but you don't actually know what's in B^{tree} until you get it.\nAnd advertising all of your trees and blobs is prohibitively expensive.\n\nSo I think that pushes us back towards wanting an \"n+1\" scheme, even if\nthe latency is bad. And is really why partial clone is _so_ much easier\nif you just resign yourself to giving the client all the commits and\ntrees. :)\n\n-Peff\n"},{"id":"394110","messageId":"20200326195058.GA8613@syl.local","threadId":"53035","inReplyTo":"20200320061214.GA511478@coredump.intra.peff.net","subject":"Re: [RFC PATCH] fetch-pack: lazy fetch using tree:0","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-03-26T19:50:58Z","receivedAt":"2020-03-26T19:51:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Peff,\n\nOn Fri, Mar 20, 2020 at 02:12:14AM -0400, Jeff King wrote:\n> On Thu, Mar 19, 2020 at 10:44:39AM -0700, Jonathan Tan wrote:\n> >  - Some hosts like GitHub support some partial clone filters, but not\n> >    \"tree:0\".\n>\n> Yes, this is going to fail against GitHub servers, just like it would\n> for older servers. One way to prevent that would be to use a \"blob\"\n> filter if that's what we originally partial-cloned with. I don't know if\n> that information always reliably makes it into this code path, though.\n> I think I'd prefer a capability-based fix in the long run.\n>\n> We may support \"tree:0\" eventually at GitHub. It's quick to compute with\n> bitmaps, just like \"blob:none\" is. But \"tree:1\" isn't.\n\nI'm rolling this out shortly :).\n\n> One side note (for Taylor, cc'd): our patches elsewhere to limit the\n> allowed filters don't make it possible to express the difference between\n> \"tree:0\" and \"tree:1\". It may be worth thinking about that, especially\n> if it influences the config schema (since we'll have to support it\n> forever once it makes it into a release).\n\nThey do now, mostly thanks to Peff's original thinking about separating\nout each filter choice into its own subsection, so that we can write not\njust:\n\n  [uploadpack \"filter.tree:depth\"]\n    allow = true\n\nbut also:\n\n  [uploadpack \"filter.tree:depth\"]\n    allow = true\n    maxDepth = <n>\n\nI have some patches that I'm rolling out to GitHub in the next day or so\nthat do just that. I think that we will likely just support the no-trees\nversion of this filter (i.e., '--filter=tree:0'), since that is the only\ncase that is helped by having up-to-date bitmaps enabled. I assume that\nother administrators will do the same.\n\nI'm going to send these patches upstream in the not-too-distant future,\nbecause I want to address the original issues that I talked about in my\nRFC about adding these filter subsections to 'upload-pack's\nconfiguration in the first place in [1].\n\nMy hope is that I can do that while these patches are being vetted in\nthe wild before I send them to the list.\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/cover.1584477196.git.me@ttaylorr.com/\n"},{"id":"394162","messageId":"20200327093710.GA611304@coredump.intra.peff.net","threadId":"53035","inReplyTo":"20200326195058.GA8613@syl.local","subject":"Re: [RFC PATCH] fetch-pack: lazy fetch using tree:0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-27T09:37:10Z","receivedAt":"2020-03-27T09:37:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 26, 2020 at 01:50:58PM -0600, Taylor Blau wrote:\n\n> > One side note (for Taylor, cc'd): our patches elsewhere to limit the\n> > allowed filters don't make it possible to express the difference between\n> > \"tree:0\" and \"tree:1\". It may be worth thinking about that, especially\n> > if it influences the config schema (since we'll have to support it\n> > forever once it makes it into a release).\n> [...]\n>   [uploadpack \"filter.tree:depth\"]\n>     allow = true\n>     maxDepth = <n>\n\nYeah, that scheme solves the problem very neatly, and removes any worry\nI had about painting ourselves into a corner. Thanks.\n\n-Peff\n"}]}