Replace message Tree with a topologically sorted varint delimited stream of Directory messages

[EdSchouten]

I know that on numerous occasions we've had discussions within the working group on whether the Tree vs. Directory dichotomy is truly necessary, and whether there are ways to eliminate it. Let me make it clear up front that this issue is filed under the assumption that we do want to keep these separate like we have today, which is why I'm not posting this under #159 or #170. It's just low hanging fruit.

The last couple of days I've worked on optimising handling of large Tree objects in bb-clientd. Whereas some of the other Protobuf messages can sometimes become hundreds of kilobytes in size (e.g., Command), it's not impossible for Trees to become dozens of megabytes. While working on optimising this area, I realised that my life would have been a lot easier if Trees were stored as a varint delimited stream of Directory messages (just like Bazel --build_event_binary_file). My suggestion would be to make it topologically sorted (parents before children), so that the root of the Tree comes first. Some advantages:

1. Because of the topological sorting, you can instantiate the contents of a Tree on a native file system in a streaming manner. Memory consumption of such an extraction tool would only be proportional to the number of referenced child directories that have not yet been observed.
2. Similarly, you can do one-shot path lookups (for paths without "..") by doing a forward scan against the stream, only unmarshaling directory objects that match the length and hash yielded by the parent.
3. Right now you see that consumers of Tree first unmarshal the message, and then marshal each of the child directories again, just so that their hash can be computed. This implicitly assumes that the producer and consumer use the same strategy for marshaling. By using a varint delimited stream, consumers have direct access to directories in marshaled form, meaning that both this assumption and the redundant marshaling are eliminated.
4. In bb-clientd I need to be able to have fast random access to Tree objects. To facilitate this, I'm basically storing the Tree object in the client-side CAS just once, but creating n+1 entries in the index. One for the Tree as a whole, and one for each of the child directories, pointing to byte ranges in the Tree's bytestream that correspond to the individual directory messages. That way these directory messages become directly addressable. This happens to be possible today, only because Protobuf messages are encoded identically regardless of the depth at which they are placed. The format I'm proposing not only allows me to eliminate this assumption, it means I can also compute the n additional entries in a streaming manner.

[EdSchouten]

It looks like I've been able to solve (3) and (4) on the Buildbarn side without making any protocol changes, as it turns out that Protobuf's wire format has some interesting properties:

• Nested messages use the same encoding as string and bytes fields. This means that nested messages are prefixed with their own length.
• There is no difference in how singular and repeated fields are encoded. It's just that repeated fields may occur in the output multiple times.

So if you look at an REv2 Tree's binary representation, it's typically little more than this:

• Root directory:
  • Tag of field number 1 of and type 2 (bytes): (1 << 3) | 2 == 0x0a
  • Varint encoded length of Directory message
  • Directory message
• Child directory 1:
  • Tag of field number 2 of and type 2 (bytes): (2 << 3) | 2 == 0x12
  • Varint encoded length of Directory message
  • Directory message
• Child directory 2:
  • Tag of field number 2 of and type 2 (bytes): (2 << 3) | 2 == 0x12
  • Varint encoded length of Directory message
  • Directory message
• ...

Basically the same as what I proposed above, except for the presence of field tags and a lack of topological sorting.

Anyway, I've successfully managed to patch up Buildbarn to deal with Tree objects in a streaming manner as follows:

• Added a library for iterating over marshaled Protobuf messages, consisting only of 'bytes' fields: buildbarn/bb-storage@93aba14
• Modified CompletenessCheckingBlobAccess (used by GetActionResult to touch objects referenced by ActionResult) to use the new API: buildbarn/bb-storage@1b84fa8
• Modified BlobAccessDirectoryFetcher (used by bb_clientd to access Tree objects) to use the new API: buildbarn/bb-remote-execution@85954ef

With these changes in place, I'm capable of efficiently working with Tree objects that are hundreds of megabytes in size.

I'm still going to leave this issue open, as issues (1) and (2) remain. Furthermore, I'm not too happy about maintaining my own Protobuf message parser. My solution would break as soon as someone adds a simple integer field to the Tree message, as my parser is only capable of processing 'bytes' fields.