{"thread":{"id":"47443","subject":"[PATCH v3] Partial clone design document","startedAt":"2017-12-14T21:09:41Z","lastAt":"2017-12-14T21:09:43Z","messageCount":2,"participants":["Jeff Hostetler"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"334839","messageId":"20171214210923.55225-1-git@jeffhostetler.com","threadId":"47443","inReplyTo":null,"subject":"[PATCH v3] Partial clone design document","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-12-14T21:09:22Z","receivedAt":"2017-12-14T21:09:41Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nThis patch contains V3 os the partial clone design document.\nIt incorporates feedback from Philip that I missed before\nsending V2 and today's comments from Junio.\n\nJeff Hostetler (1):\n  partial-clone: design doc\n\n Documentation/technical/partial-clone.txt | 324 ++++++++++++++++++++++++++++++\n 1 file changed, 324 insertions(+)\n create mode 100644 Documentation/technical/partial-clone.txt\n\n-- \n2.9.3\n\n"},{"id":"334840","messageId":"20171214210923.55225-2-git@jeffhostetler.com","threadId":"47443","inReplyTo":"20171214210923.55225-1-git@jeffhostetler.com","subject":"[PATCH v3] partial-clone: design doc","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-12-14T21:09:23Z","receivedAt":"2017-12-14T21:09:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nDesign document for partial clone feature.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n Documentation/technical/partial-clone.txt | 324 ++++++++++++++++++++++++++++++\n 1 file changed, 324 insertions(+)\n create mode 100644 Documentation/technical/partial-clone.txt\n\ndiff --git a/Documentation/technical/partial-clone.txt b/Documentation/technical/partial-clone.txt\nnew file mode 100644\nindex 0000000..f78fa32\n--- /dev/null\n+++ b/Documentation/technical/partial-clone.txt\n@@ -0,0 +1,324 @@\n+Partial Clone Design Notes\n+==========================\n+\n+The \"Partial Clone\" feature is a performance optimization for Git that\n+allows Git to function without having a complete copy of the repository.\n+The goal of this work is to allow Git better handle extremely large\n+repositories.\n+\n+During clone and fetch operations, Git downloads the complete contents\n+and history of the repository.  This includes all commits, trees, and\n+blobs for the complete life of the repository.  For extremely large\n+repositories, clones can take hours (or days) and consume 100+GiB of disk\n+space.\n+\n+Often in these repositories there are many blobs and trees that the user\n+does not need such as:\n+\n+  1. files outside of the user's work area in the tree.  For example, in\n+     a repository with 500K directories and 3.5M files in every commit,\n+     we can avoid downloading many objects if the user only needs a\n+     narrow \"cone\" of the source tree.\n+\n+  2. large binary assets.  For example, in a repository where large build\n+     artifacts are checked into the tree, we can avoid downloading all\n+     previous versions of these non-mergeable binary assets and only\n+     download versions that are actually referenced.\n+\n+Partial clone allows us to avoid downloading such unneeded objects *in\n+advance* during clone and fetch operations and thereby reduce download\n+times and disk usage.  Missing objects can later be \"demand fetched\"\n+if/when needed.\n+\n+Use of partial clone requires that the user be online and the origin\n+remote be available for on-demand fetching of missing objects.  This may\n+or may not be problematic for the user.  For example, if the user can\n+stay within the pre-selected subset of the source tree, they may not\n+encounter any missing objects.  Alternatively, the user could try to\n+pre-fetch various objects if they know that they are going offline.\n+\n+\n+Non-Goals\n+---------\n+\n+Partial clone is a mechanism to limit the number of blobs and trees downloaded\n+*within* a given range of commits -- and is therefore independent of and not\n+intended to conflict with existing DAG-level mechanisms to limit the set of\n+requested commits (i.e. shallow clone, single branch, or fetch '<refspec>').\n+\n+\n+Design Overview\n+---------------\n+\n+Partial clone logically consists of the following parts:\n+\n+- A mechanism for the client to describe unneeded or unwanted objects to\n+  the server.\n+\n+- A mechanism for the server to omit such unwanted objects from packfiles\n+  sent to the client.\n+\n+- A mechanism for the client to gracefully handle missing objects (that\n+  were previously omitted by the server).\n+\n+- A mechanism for the client to backfill missing objects as needed.\n+\n+\n+Design Details\n+--------------\n+\n+- A new pack-protocol capability \"filter\" is added to the fetch-pack and\n+  upload-pack negotiation.\n+\n+  This uses the existing capability discovery mechanism.\n+  See \"filter\" in Documentation/technical/pack-protocol.txt.\n+\n+- Clients pass a \"filter-spec\" to clone and fetch which is passed to the\n+  server to request filtering during packfile construction.\n+\n+  There are various filters available to accommodate different situations.\n+  See \"--filter=<filter-spec>\" in Documentation/rev-list-options.txt.\n+\n+- On the server pack-objects applies the requested filter-spec as it\n+  creates \"filtered\" packfiles for the client.\n+\n+  These filtered packfiles are *incomplete* in the traditional sense because\n+  they may contain objects that reference objects not contained in the\n+  packfile and that the client doesn't already have.  For example, the\n+  filtered packfile may contain trees or tags that reference missing blobs\n+  or commits that reference missing trees.\n+\n+- On the client these incomplete packfiles are marked as \"promisor packfiles\"\n+  and treated differently by various commands.\n+\n+- On the client a repository extension is added to the local config to\n+  prevent older versions of git from failing mid-operation because of\n+  missing objects that they cannot handle.\n+  See \"extensions.partialClone\" in Documentation/technical/repository-version.txt\"\n+\n+\n+Handling Missing Objects\n+------------------------\n+\n+- An object may be missing due to a partial clone or fetch, or missing due\n+  to repository corruption.  To differentiate these cases, the local\n+  repository specially indicates such filtered packfiles obtained from the\n+  promisor remote as \"promisor packfiles\".\n+\n+  These promisor packfiles consist of a \"<name>.promisor\" file with\n+  arbitrary contents (like the \"<name>.keep\" files), in addition to\n+  their \"<name>.pack\" and \"<name>.idx\" files.\n+\n+- The local repository considers a \"promisor object\" to be an object that\n+  it knows (to the best of its ability) that the promisor remote has promised\n+  that it has, either because the local repository has that object in one of\n+  its promisor packfiles, or because another promisor object refers to it.\n+\n+  When Git encounters a missing object, Git can see if it a promisor object\n+  and handle it appropriately.  If not, Git can report a corruption.\n+\n+  This means that there is no need for the client to explicitly maintain an\n+  expensive-to-modify list of missing objects.[a]\n+\n+- Since almost all Git code currently expects any referenced object to be\n+  present locally and because we do not want to force every command to do\n+  a dry-run first, a fallback mechanism is added to allow Git to attempt\n+  to dynamically fetch missing objects from the promisor remote.\n+\n+  When the normal object lookup fails to find an object, Git invokes\n+  fetch-object to try to get the object from the server and then retry\n+  the object lookup.  This allows objects to be \"faulted in\" without\n+  complicated prediction algorithms.\n+\n+  For efficiency reasons, no check as to whether the missing object is\n+  actually a promisor object is performed.\n+\n+  Dynamic object fetching tends to be slow as objects are fetched one at\n+  a time.\n+\n+- `checkout` (and any other command using `unpack-trees`) has been taught\n+  to bulk pre-fetch all required missing blobs in a single batch.\n+\n+- `rev-list` has been taught to print missing objects.\n+\n+  This can be used by other commands to bulk prefetch objects.\n+  For example, a \"git log -p A..B\" may internally want to first do\n+  something like \"git rev-list --objects --quiet --missing=print A..B\"\n+  and prefetch those objects in bulk.\n+\n+- `fsck` has been updated to be fully aware of promisor objects.\n+\n+- `repack` in GC has been updated to not touch promisor packfiles at all,\n+  and to only repack other objects.\n+\n+- The global variable \"fetch_if_missing\" is used to control whether an\n+  object lookup will attempt to dynamically fetch a missing object or\n+  report an error.\n+\n+  We are not happy with this global variable and would like to remove it,\n+  but that requires significant refactoring of the object code to pass an\n+  additional flag.  We hope that concurrent efforts to add an ODB API can\n+  encompass this.\n+\n+\n+Fetching Missing Objects\n+------------------------\n+\n+- Fetching of objects is done using the existing transport mechanism using\n+  transport_fetch_refs(), setting a new transport option\n+  TRANS_OPT_NO_DEPENDENTS to indicate that only the objects themselves are\n+  desired, not any object that they refer to.\n+\n+  Because some transports invoke fetch_pack() in the same process, fetch_pack()\n+  has been updated to not use any object flags when the corresponding argument\n+  (no_dependents) is set.\n+\n+- The local repository sends a request with the hashes of all requested\n+  objects as \"want\" lines, and does not perform any packfile negotiation.\n+  It then receives a packfile.\n+\n+- Because we are reusing the existing fetch-pack mechanism, fetching\n+  currently fetches all objects referred to by the requested objects, even\n+  though they are not necessary.\n+\n+\n+Current Limitations\n+-------------------\n+\n+- The remote used for a partial clone (or the first partial fetch\n+  following a regular clone) is marked as the \"promisor remote\".\n+\n+  We are currently limited to a single promisor remote and only that\n+  remote may be used for subsequent partial fetches.\n+\n+  We accept this limitation because we believe initial users of this\n+  feature will be using it on repositories with a strong single central\n+  server.\n+\n+- Dynamic object fetching will only ask the promisor remote for missing\n+  objects.  We assume that the promisor remote has a complete view of the\n+  repository and can satisfy all such requests.\n+\n+- Repack essentially treats promisor and non-promisor packfiles as 2\n+  distinct partitions and does not mix them.  Repack currently only works\n+  on non-promisor packfiles and loose objects.\n+\n+- Dynamic object fetching invokes fetch-pack once *for each item*\n+  because most algorithms stumble upon a missing object and need to have\n+  it resolved before continuing their work.  This may incur significant\n+  overhead -- and multiple authentication requests -- if many objects are\n+  needed.\n+\n+- Dynamic object fetching currently uses the existing pack protocol V0\n+  which means that each object is requested via fetch-pack.  The server\n+  will send a full set of info/refs when the connection is established.\n+  If there are large number of refs, this may incur significant overhead.\n+\n+\n+Future Work\n+-----------\n+\n+- Allow more than one promisor remote and define a strategy for fetching\n+  missing objects from specific promisor remotes or of iterating over the\n+  set of promisor remotes until a missing object is found.\n+\n+  A user might want to have multiple geographically-close cache servers\n+  for fetching missing blobs while continuing to do filtered `git-fetch`\n+  commands from the central server, for example.\n+\n+  Or the user might want to work in a triangular work flow with multiple\n+  promisor remotes that each have an incomplete view of the repository.\n+\n+- Allow repack to work on promisor packfiles (while keeping them distinct\n+  from non-promisor packfiles).\n+\n+- Allow non-pathname-based filters to make use of packfile bitmaps (when\n+  present).  This was just an omission during the initial implementation.\n+\n+- Investigate use of a long-running process to dynamically fetch a series\n+  of objects, such as proposed in [5,6] to reduce process startup and\n+  overhead costs.\n+\n+  It would be nice if pack protocol V2 could allow that long-running\n+  process to make a series of requests over a single long-running\n+  connection.\n+\n+- Investigate pack protocol V2 to avoid the info/refs broadcast on\n+  each connection with the server to dynamically fetch missing objects.\n+\n+- Investigate the need to handle loose promisor objects.\n+\n+  Objects in promisor packfiles are allowed to reference missing objects\n+  that can be dynamically fetched from the server.  An assumption was\n+  made that loose objects are only created locally and therefore should\n+  not reference a missing object.  We may need to revisit that assumption\n+  if, for example, we dynamically fetch a missing tree and store it as a\n+  loose object rather than a single object packfile.\n+\n+  This does not necessarily mean we need to mark loose objects as promisor;\n+  it may be sufficient to relax the object lookup or is-promisor functions.\n+\n+\n+Non-Tasks\n+---------\n+\n+- Every time the subject of \"demand loading blobs\" comes up it seems\n+  that someone suggests that the server be allowed to \"guess\" and send\n+  additional objects that may be related to the requested objects.\n+\n+  No work has gone into actually doing that; we're just documenting that\n+  it is a common suggestion.  We're not sure how it would work and have\n+  no plans to work on it.\n+\n+  It is valid for the server to send more objects than requested (even\n+  for a dynamic object fetch), but we are not building on that.\n+\n+\n+Footnotes\n+---------\n+\n+[a] expensive-to-modify list of missing objects:  Earlier in the design of\n+    partial clone we discussed the need for a single list of missing objects.\n+    This would essentially be a sorted linear list of OIDs that the were\n+    omitted by the server during a clone or subsequent fetches.\n+\n+    This file would need to be loaded into memory on every object lookup.\n+    It would need to be read, updated, and re-written (like the .git/index)\n+    on every explicit \"git fetch\" command *and* on any dynamic object fetch.\n+\n+    The cost to read, update, and write this file could add significant\n+    overhead to every command if there are many missing objects.  For example,\n+    if there are 100M missing blobs, this file would be at least 2GiB on disk.\n+\n+    With the \"promisor\" concept, we *infer* a missing object based upon the\n+    type of packfile that references it.\n+\n+\n+Related Links\n+-------------\n+[0] https://bugs.chromium.org/p/git/issues/detail?id=2\n+    Chromium work item for: Partial Clone \n+\n+[1] https://public-inbox.org/git/20170113155253.1644-1-benpeart@microsoft.com/\n+    Subject: [RFC] Add support for downloading blobs on demand\n+    Date: Fri, 13 Jan 2017 10:52:53 -0500\n+\n+[2] https://public-inbox.org/git/cover.1506714999.git.jonathantanmy@google.com/\n+    Subject: [PATCH 00/18] Partial clone (from clone to lazy fetch in 18 patches)\n+    Date: Fri, 29 Sep 2017 13:11:36 -0700\n+\n+[3] https://public-inbox.org/git/20170426221346.25337-1-jonathantanmy@google.com/\n+    Subject: Proposal for missing blob support in Git repos\n+    Date: Wed, 26 Apr 2017 15:13:46 -0700\n+\n+[4] https://public-inbox.org/git/1488999039-37631-1-git-send-email-git@jeffhostetler.com/\n+    Subject: [PATCH 00/10] RFC Partial Clone and Fetch\n+    Date: Wed,  8 Mar 2017 18:50:29 +0000\n+\n+[5] https://public-inbox.org/git/20170505152802.6724-1-benpeart@microsoft.com/\n+    Subject: [PATCH v7 00/10] refactor the filter process code into a reusable module\n+    Date: Fri,  5 May 2017 11:27:52 -0400\n+\n+[6] https://public-inbox.org/git/20170714132651.170708-1-benpeart@microsoft.com/\n+    Subject: [RFC/PATCH v2 0/1] Add support for downloading blobs on demand\n+    Date: Fri, 14 Jul 2017 09:26:50 -0400\n-- \n2.9.3\n\n"}]}