{"thread":{"id":"57379","subject":"[RFC] Bidirectional communication with a long-running Git process","startedAt":"2022-02-07T19:09:53Z","lastAt":"2022-02-07T19:09:53Z","messageCount":1,"participants":["Jonathan Tan"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"447899","messageId":"20220207190320.2960362-1-jonathantanmy@google.com","threadId":"57379","inReplyTo":null,"subject":"[RFC] Bidirectional communication with a long-running Git process","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-02-07T19:03:19Z","receivedAt":"2022-02-07T19:09:53Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Here's a proposal of what we (the Git team at Google) are planning to\nbuild, about bidirectional communication between a long-running Git\nprocess and another long-running process. We're planning to build this\nto help with a virtual file system layer that we're also building (as\ndescribed below), but we envision this to also be useful for anyone that\nneeds deeper integration with Git repositories beyond running Git\ncommands one at a time.\n \nAny comments or suggestions are welcome.\n \n-----\n# Git API extensions (external)\n\nAuthors: Jose Lopes (jabolopes@google.com), Jonathan Tan\n(jonathantanmy@google.com)\n\n## Objective\n\nGoogle is working to improve development workflows for large Git repositories,\nby means of a virtual file system layer (vfsd) which downloads contents lazily.\nWe have an internal prototype vfsd that we're using to experiment with this.\n\nThere are a number of correctness and performance challenges in materializing\nthe filesystem that we cannot address today with the currently available Git\nAPIs. For this reason, this document proposes several Git API extensions to:\n\n*   List entries from the Git index file that match a certain path prefix\n*   Obtain specific fields from the entries stored in the Git index file\n*   Batch fetches by sending out a single network request with a variable number\n    of Git objects\n*   Obtain file sizes for a variable number of Git objects efficiently (via\n    object-info)\n\nThe API extensions proposed in this document are not the only ones that we will\never need. As the project development progresses, our developers will need to\ndesign, implement and propose new API extensions to Git to address future needs.\n\nThe APIs will be called on a persistent connection between Git and vfsd to avoid\nthe performance cost of running one-off Git commands during filesystem\noperations. This communication mechanism will be used for both the APIs proposed\nin this doc and future ones, too.\n\nTo establish the connection, vfsd spawns Git and runs a new Git command that we\nalso propose in this document. Then vfsd and Git can communicate over stdin/out.\nvfsd can use this to pipe commands to Git and obtain results. Conversely Git can\nalso send commands to vfsd and obtain results. vfsd and Git will communicate\nusing the pkt-line format because it’s already supported by Git.\n\nIn summary, this document proposes:\n\n*   a generic RPC protocol based on the pkt-line format, that can be used as the\n    basis of communication between Git and vfsd, but it is generic enough so\n    that it can be used by any external process to talk to Git.\n*   API extensions on top of this pkt-line RPC protocol, which are useful for\n    virtual filesystem layers built on top of Git.\n*   A new command, called *git-batch*, which implements the pkt-line RPC\n    protocol and these API extensions.\n\n## Background\n\nToday vfsd interacts with Git in 2 different ways, namely, via the Git cat-file\ndaemon and by spawning one-off Git processes.\n\nThe Git cat-file daemon (i.e., *git cat-file --batch*) is a long-lived process\nthat accepts commands from vfsd via stdin and returns output via stdout /\nstderr. The commands accepted by git-cat-file are limited (see\n[git-rev-parse](https://git-scm.com/docs/git-rev-parse#_specifying_revisions)).\nvfsd uses the Git cat-file daemon to obtain file contents for files displayed in\nthe FUSE filesystem. This results in a full connection setup/teardown with the\nGit remote server for every object that is fetched, which results in user\nvisible latency and impacts performance.\n\nvfsd needs to read tree objects, obtain object sizes, obtain the contents of the\nGit index file, among others, which are not supported by the Git cat-file\ndaemon. In this case, vfsd ends up running other Git commands, such as,\n`git-cat-file -s`, `git-fetch`, `git-ls-files`, etc. These commands are run by\nspawning one-off Git processes. This incurs a performance penalty every time\nvfsd needs to run a Git command since it requires creating a new system process\n(via `fork`/`exec`).\n\nFor obtaining file sizes, vfsd uses a one-off Git process (`git-cat-file -s`),\nbut we would like to use the Git cat-file daemon to obtain size information\nalso. This would allow us to reuse the existing infrastructure for the Git\ncat-file daemon and also get better performance by avoiding spawning one-off\nprocesses to obtain size information. Also, vfsd needs a performant API to\nobtain size information for a variable number of objects. This API does not\nexist yet.\n\nFor batch fetching, vfsd uses a one-off Git process (`git fetch`) with several\nflags, one of which is the `--filter` which tells Git which types of objects to\nleave out of the fetch. Just like when obtaining file sizes, we would like to\nmove away from one-off Git processes and employ the Git cat-file daemon for\nbatch fetching.\n\nFor parsing the contents of the index file, vfsd also uses a one-off Git process\n(`git ls-files -st`). It’s worth mentioning that the `-s` option is used to\nobtain the staged contents’ mode bits, object name (aka SHA1 hash), and stage\nnumber. And the `-t` option is used to obtain the file status (`H` - cached,\n`S` - skip-worktree, `C` - changed, etc). This `ls-files` command parses the\ncontents of the Git index file in full, but we would like to have the option to\nparse only the entries that match a certain path prefix. This is an important\noptimization especially when dealing with large repositories.\n\n## Design\n\nWe propose to introduce a new command called `git-batch` which is similar to\n`git-cat-file --batch` but uses the pkt-line RPC format (described in this\ndocument) instead of `git-rev-parse` patterns.\n\nUsing this new command, we will implement the following new APIs:\n\n*   API to list the contents of the index file\n*   API to obtain file sizes\n*   API to fetch in batch\n\n### pkt-line RPC\n\nWe start by introducing the pkt-line RPC protocol. The external process (i.e.,\nvfsd) and Git will communicate via stdin/out using the protocol described in\nthis section, which is embedded in the\n[pkt-line format](https://git-scm.com/docs/protocol-common#_pkt_line_format):\n\nSyntax:\n\n```\nPKT_LINE := $PKT_LEN_HEX $FRAME\n\nFRAME := $ID $STREAM_OP [$MSG]\n\nSTREAM_OP := b|e|k|be\n\nMSG = $MSG_TYPE [$DATA]\n\nMSG_TYPE := o|E|c\n```\n\nThe pkt-line RPC protocol is different, e.g., from HTTPv1, in which one process\nis the client and the other is the server, and only the client can initiate\nrequests to the server. In pkt-line RPC, both processes act as the sender and\nreceiver to exchange frames. So the term sender and receiver is not a role of\nthe process. Rather for each frame that is sent, one process is the sender and\nthe other the receiver.\n\nThe protocol is full duplex, i.e., the sender and receiver can exchange frames\nwithout having to wait for the full request or full response to be sent /\nreceived.\n\n#### Terminology\n\nTerminology used in the subsequent sections that describe the protocol:\n\n*   Frame: piece data of known length containing both protocol metadata and\n    application data.\n*   Sender: process that sent a frame.\n*   Receiver: process that received a frame.\n*   Stream: ordered sequence of 1 or more messages\n*   Message: ordered sequence of 1 or more frames\n*   Stream operation: protocol metadata that indicates if a stream begins,\n    continues, or ends.\n*   Request: a stream started and completed by the sender.\n*   Response: a stream started and completed by the receiver that pairs with a\n    request via `$ID`.\n*   Application: either the Git process or the external process talking to Git.\n*   Control frame: a frame containing only protocol metadata and no message.\n*   RPC: a pair of request and response with the same ID.\n\n#### FRAME\n\nThe `$FRAME` contains a protocol frame and it is embedded in a pkt-line. To\navoid head-of-line blocking problems, frames can be interleaved. Frames are\nalways sent in streams. Streams group 1 or more frames. The sender and receiver\nkeep track of open streams. A stream is initiated by a request from either side\nand terminated by a response with the same `$ID` as the request.\n\nThe limit of a pkt-line is 65516 bytes, so large requests / responses / blobs\nmay not fit in a single frame. To overcome this, messages can span multiple\nframes. A continuation mechanism is used to indicate that the message is\nincomplete and continues on the next frame of the same stream. The sender and\nreceiver keep track of whether there is an active continuation on a stream or\nnot.\n\n#### ID\n\nThe `$ID` field is an alphanumeric identifier and it is multi-purpose:\n\n*   Identifies frames belonging to the same stream.\n*   Pairs requests with responses.\n*   Allows frames to be interleaved.\n\nIDs can be reused provided they are free. The sender and receiver keep track of\nbusy IDs. An ID is busy (or not free) if there is an open stream with that ID,\nwhich is the same as saying that a request was sent with that ID but the\nresponse was not yet received. An ID is free (or not busy) either because no\nrequest has been sent with that ID or because a response with the same ID has\nalready been received.\n\nTo avoid the sender and receiver accidentally choosing the same ID concurrently,\nthe external process will use positive IDs and Git will use negative IDs.\n\nAn RPC is a request and response with the same `$ID`. If the sender wants to\ninitiate a request but does not have a message to send, it can send a control\nframe (i.e., a frame without `$MSG`) as a request. Conversely, if the receiver\nwants to send a response but does not have a message to return, it can send a\ncontrol frame. These control frames are essential for senders and receivers to\nknow when IDs become free.\n\nIt is a protocol error to reuse an ID that is still being used. It’s a protocol\nerror to omit a request or response in an RPC.\n\n#### STREAM\\_OP\n\nThe `$STREAM_OP` field is used to control stream operations:\n\n*   A value of `b` (aka begin) indicates the beginning of a stream.\n*   A value of `k` (aka keep) sends a message on an open stream.\n*   A value of `e` (aka end) indicates the end of a stream.\n*   A value of `be` is an optimization to avoid sending empty frames. This is\n    only used in streams that have a single message\n    <span style=\"text-decoration:underline;\">and</span> a single frame. It is\n    equivalent to sending a `b` frame and an `e` frame, where the `e` frame has\n    no `$MSG`.\n\nIt is a protocol error to mishandle stream operations, for example, to begin a\nstream that is already started, or end a stream that is not started, or send a\n`k` frame on a stream that is not started.\n\n#### MSG\n\nThe `$MSG` contains an application message. If this is omitted, then the frame\nis a control frame, containing only protocol data. If `$MSG` is specified, then\nthis frame contains application data meant to be delivered to the receiver\napplication.\n\n#### MSG\\_TYPE\n\nThe `$MSG_TYPE` field is the message type.\n\nA value of `o` (aka ok) contains a whole message if there is no active\ncontinuation. Otherwise, it contains the last part of a message and marks the\nend of the active continuation.\n\nA value of `E` (aka error) contains a whole error message. If there is an active\ncontinuation, this continuation ends, and messages sent in those continuation\nframes are discarded. The error is delivered to the application.\n\nA value of `c` (aka continuation) contains part of a message. If there is no\nactive continuation, this also starts an active continuation. Otherwise, it\nindicates that the active continuation continues onto the next frame.\n\nIt is a protocol error to start a continuation and not finish it either with an\n`o` frame or an `E` frame. A `be` frame does not automatically finish an active\ncontinuation because it does not indicate whether the message is an error or\nnot.\n\nThe `$MSG_TYPE` is optional. If omitted, then `$DATA` must also be omitted, in\nwhich case this frame is a control frame and no message is delivered to the\napplication.\n\n#### DATA\n\nThe `$DATA` field is optional and can contain an empty or non-empty message. An\nempty message is not given special treatment and it’s delivered to the\napplication like non-empty messages. This allows APIs to return an OK message\nwithout any actual data to indicate that the request was successful, for\nexample:\n\n```\n> 1 be o fetch $SHA1\n< 1 be o\n```\n\nSender (i.e., >) sends a request to fetch an object. Receiver (i.e. &lt;)\nresponds with an OK message with empty `$DATA`.\n\n#### Examples\n\n```\n1 be o hello world\n```\n\nSend a single message. This uses the `be` optimization because it’s a stream\nwith a single message and single frame.\n\n```\n1 be E no such file or directory\n```\n\nSend a single error message. This uses the `be` optimization for the same\nreasons as above.\n\n```\n1 b c $LONG_DATA1\n1 k c $LONG_DATA2\n1 e o $LONG_DATA3\n```\n\nSend a single long message. The `$LONG_DATA` message is too large, therefore\nit’s split into `$LONG_DATA1`, `$LONG_DATA2`, and `$LONG_DATA3`, using `c` to\nindicate the continuation frames. The receiver reassembles the continuation\nframes and delivers a single message to the application.\n\n```\n1 b o $SMALL_BLOB1\n1 k o $SMALL_BLOB2\n1 e o $SMALL_BLOB3\n```\n\nSend 3 individual messages on a stream without errors.\n\n```\n1 b o $SMALL_BLOB1\n1 k o $SMALL_BLOB2\n1 e E $SMALL_ERROR\n```\n\nSend 3 individual messages on a stream. The last message is an error message.\nThe receiver delivers 3 messages to the application.\n\n```\n1 b c $A_DATA1\n1 k o $A_DATA2\n1 k c $B_DATA1\n1 e o $B_DATA2\n```\n\nSend multiple long messages without errors. The `$A_DATA` message is split into\n2 frames ($`A_DATA1` and $`A_DATA2`) using continuation frames. The same is done\nfor the `$B_DATA` message. The receiver reassembles the continuation frames and\ndelivers 2 messages to the application.\n\n```\n1 b c $A_DATA1\n1 k o $A_DATA2\n1 k c $B_DATA1\n1 e E $ERROR\n```\n\nSend multiple long messages with errors. The receiver delivers `$A_DATA`\n(`$A_DATA1` + `$A_DATA2`) to the application. The `$B_DATA1` is discarded, and\n`$ERROR` is delivered to the application.\n\n#### Nuanced cases\n\nThere are some nuanced cases, so we want to make sure that the protocol works as\nexpected and that there are no ambiguities.\n\n```\n1 b m hello\n1 e\n```\n\nSend a single message to the receiver in 2 frames. The second frame is empty and\ndoes not contain a message, but it contains a stream operation to end the\nstream. This is equivalent to sending a single `be` frame but without the\noptimization that saves the empty frame.\n\n```\n1 be\n```\n\nSend a control frame without any messages. No messages are delivered to the\napplication.\n\n```\n1 be o\n```\n\nSend an empty message. An empty message is delivered to the application.\n\nNow that we have the protocol basics (framing, interleaving and streaming), we\ncan now define the APIs. The APIs below fit in the `$DATA` part shown in the\nsyntax above.\n\n### API to list contents of the index file\n\nvfsd needs an API to parse the Git index file, to extract certain fields from\nit, and match only certain paths.\n\nRequest syntax:\n\n```\nls-index [path:$PATH\\0] [fields:%($FIELD1)%($FIELD2)...]\n```\n\nResponse syntax:\n\n```\n[$FIELD1:$VALUE1] [file:$PATH\\0] [$FIELD2:$VALUE2 ...]\n```\n\nThe command `ls-index` lists the contents of the index file.\n\nThe argument `path:` is a path selector to list paths that match the given\nprefix. The wildcard `*` matches immediate subentries. The wildcard `**`\nrecursively matches all subentries.\n\nThe argument `fields:` is a field selector to select which fields to return from\nthe matched entries.\n\nIn the response, the filename has a variable length so it’s terminated by NULL\n('\\0').\n\nExamples:\n\n```\npath:dir/*\n```\n\nmatches all immediate children of `dir/` and returns the Git index entries for\nthe paths `dir/myfile` and `dir/mydir`, but not for `dir/mydir/file`.\n\n```\npath:*\n```\n\nmatches all immediate children of the root directory, e.g., `myfile` and\n`mydir`, but it doesn’t match `mydir/file`.\n\n```\npath:dir/**\n```\n\nmatches all entries from the Git index file that have the prefix `dir/` in their\npath, so all of `dir/myfile`, `dir/mydir`, and `dir/mydir/file` match.\n\n```\nfields:%(status)%(mode)%(name)%(stage)%(file)\n```\n\nreturns the file status (H, S, C, etc), file mode, object name (aka SHA1 hash),\nstage number (0, 1, 2) and file name (e.g., README). This uses the\n[git-log format string](https://git-scm.com/docs/git-log).\n\nFor performance reasons, wildcards are employed in path selectors instead of\nregular expressions. Wildcards can only appear as the last component of a path\nand they cannot be combined with other stanzas, so a pattern like `myfile*` with\nthe intention of matching `myfile1` and `myfileabc` is not allowed, and a\npattern like `dir/*/myfile` with the intention of matching all intermediate\nsubdirectories is also not allowed.\n\n### API to get blob size\n\nvfsd needs this API either to obtain file sizes. For performance reasons, it’s\ncritical that vfsd can batch requests, i.e., send a single network request for a\nnumber of objects in parallel.\n\nRequest syntax:\n\n```\nsize $NAME1 [$NAME2 ...]\n```\n\nResponse syntax:\n\n```\n$SIZE1 [$SIZE2 ...]\n```\n\nExample:\n\n```\nsize 6363ba80dc6f90ac2b016adef8b9186cec3e431e\n```\n\nReturns the size of the blob with the given name.\n\n```\nsize 6adef8b9186cec3e431e6363ba80dc6f90ac2b01 cec3e431e6363ba80dc6f90ac2b016adef8b9186\n```\n\nreturns the sizes of the blobs with the given names.\n\n### API to fetch in batch\n\nvfsd needs this API to fetch several objects in a batch so that subsequent\ncommands that interact with those objects do not block on the network.\n\nRequest syntax:\n\n```\nfetch $NAME1 [$NAME2 ...]\n```\n\nResponse syntax:\n\n```\nNo response.\n```\n\nExample:\n\n```\nfetch 6adef8b9186cec3e431e6363ba80dc6f90ac2b01 cec3e431e6363ba80dc6f90ac2b016adef8b9186\n```\n\nfetches the given objects in a single network request from the remote and stores\nthem locally. It may be necessary to extend this with the name of the remote in\norder to accommodate Git repositories with multiple remotes.\n\n## Experimental\n\nThe new Git command `git-batch` will be first released as\n`git-batch-experimental` because it:\n\n*   Communicates to the users that the API is in development, it can drastically\n    change or even be removed\n*   Communicates to the users that backwards compatibility for this API is not\n    guaranteed\n*   Allows the Git maintainers to accept a feature in Git for development\n    purposes but without the risk of maintaining backwards compatibility for a\n    feature that is not useful\n*   Allows our developers to continue developing these APIs incrementally /\n    iteratively.\n\nWhen these APIs are stable, we can then start a discussion to stabilize these\nAPIs and define a path to remove the experimental bit.\n"}]}