Remote Execution and Content-Addressed Input Trees

Sending a build action to another machine turns a local scheduling problem into a distributed one, and the difficulty is not the scheduling but the representation. The worker must be able to run the action without access to the requester’s filesystem, and the requester must be able to verify that the worker ran the right thing on the right bytes. Both requirements are satisfied by describing the action and its inputs as values identified by content digests, so that the message on the wire is a reference rather than a payload.

An action is a small message, not a command line

The Remote Execution API, an open specification used by several build systems, models an action as a structure whose fields are the digest of a command, the digest of the root of the input tree, and a timeout. The command structure contains the argument vector, a working directory relative to the input root, environment variable settings, and the output paths the action is expected to create. The argument vector is a list, not a shell string, so no shell is required on the worker and no quoting rules leak into the protocol.

This indirection is the whole point. Because the action is a value, it has a digest, and the digest is the same wherever the action was computed. It can be sent to a worker, stored in an action cache, compared against a previous invocation, or used to detect that two machines are attempting identical work. The same structure that describes work to a worker also describes work to a cache, which is why the action cache described in Action Cache Keys and Shared Build Caches and the execution service share a data model.

The input tree as a Merkle DAG

The input root is a directory tree, and it is represented as a recursive structure: a directory node lists its entries in sorted order, each entry naming a file, a directory, or a symbolic link, with the digest of the referenced node. A file’s digest is over its bytes and includes its size, so the pair of hash and length identifies it; the length is carried explicitly because it lets an implementation check a transfer before reading the content. An executable bit is part of the node’s metadata, which is how permission information survives the round trip.

Because directories refer to children by digest, the tree is a Merkle DAG, and identical subtrees are shared without copying. Two modules with the same set of vendored files hash to the same directory node; a change to one file changes only the path of nodes from that file to the root. The practical effect is that a large input tree with a small change requires uploading only the changed file, because every other node’s digest is already on the server.

The upload itself is a negotiation rather than a push. The requester asks which of a set of digests the server is missing, and uploads only those. Blobs below a size threshold can be sent in batches within a single request; larger blobs go over a streaming interface, which is what allows a multi-gigabyte toolchain blob to be transferred without materialising it in memory. Since the transport is HTTP/2 with length-prefixed binary messages, several requests and their responses share one connection, and a large transfer does not block small metadata calls.

The size threshold is where the two cost curves cross. Small requests have fixed overhead per round trip, so batching amortises it; a single very large message ties up a stream and forces the sender to buffer, so streaming wins above a certain size. The exact crossover depends on the implementation and the network, and the protocol leaves it as a tuning parameter rather than fixing it.

import hashlib

def blob_digest(data: bytes) -> tuple[str, int]:
    # The digest identity in the protocol is the pair (hash, size_bytes);
    # the size is carried separately so a transfer can be validated early.
    return hashlib.sha256(data).hexdigest(), len(data)

def directory_digest(entries):
    # entries: sorted list of (name, kind, digest, executable)
    h = hashlib.sha256()
    for name, kind, digest, exec_bit in sorted(entries):
        h.update(kind.encode()); h.update(b'\0')
        h.update(name.encode()); h.update(b'\0')
        h.update(digest.encode()); h.update(b'\0')
        h.update(b'x' if exec_bit else b'-')
    return h.hexdigest()

The separators in that sketch are doing real work. Without a byte that cannot appear in a name, two different entry lists can serialise to the same byte string, and a directory digest stops being an unambiguous identity. Every content-addressed format carries some such canonicalisation rule, and disagreements about it between implementations produce two systems that appear to speak the same protocol and never share a cache entry.

What a worker owes the requester

A worker that receives an action must, before running it, possess every input blob the tree references. If any are missing, it must either fetch them from the content-addressed store by digest or refuse the action; it must not substitute a path from its own filesystem, because the requester’s guarantee is that the action sees exactly the bytes it asked for. After fetching, it materialises the tree in a private directory, runs the command there, and collects the declared outputs.

The isolation requirements are the same as those described in Hermetic Actions and Undeclared Inputs, and for the same reason: a worker that lets an action read the host filesystem produces results that are cached under a key which claims the opposite. A non-hermetic worker is worse than no remote execution, because it silently converts a local correctness problem into a fleet-wide one. The minimum a worker must do is provide a private filesystem view containing only the inputs, a scrubbed environment containing only the variables in the command message, and no network access unless the action is explicitly configured to permit it.

Outputs are collected by path, hashed, and returned in the result message along with the exit code and the digests of the standard output and standard error streams. A successful result is a small message: digests, sizes, and metadata, with the actual bytes uploaded to the store separately. The requester fetches only the outputs it needs, and if it is another cache it may not need them at all. If the action failed, the exit code is a field of the result rather than a transport error, because a failing compilation is a normal outcome that must be reported to the user and, in some designs, recorded so that the failure is not retried blindly.

Failure modes of a build fleet

Actions in flight can fail in ways that have nothing to do with the build.

The blob store can lose data between the moment a worker checks and the moment it fetches, if entries expire under a policy that is not coordinated with the executors. The result is an action that fails with a digest it cannot obtain. Making the store’s expiry horizon longer than the longest plausible execution, and having workers re-request missing blobs rather than fail permanently, are the standard mitigations.

The operation representing a running action can be lost: the requester’s connection drops, the scheduler restarts, or the worker itself dies after producing the outputs. The protocol models an execution as a long-lived, resumable operation with status, so reattaching is possible rather than starting over. Where reattachment is not possible, the action must be re-executed, which is safe only if actions are deterministic and free of external side effects. That combination is precisely what hermeticity buys: an action that reads only its declared inputs and writes only its declared outputs can be re-run any number of times.

Timeouts are the third source. A timeout that is too short kills actions that would have completed, wasting the work already done; too long and the worker is occupied by something that will never finish. The workable setting derives from the duration distribution of the action class, not from a global constant, and the protocol makes the timeout part of the action message so that it is chosen per action and, because it is part of the message, is reflected in the digest.

The final reminder is that remote execution does not remove the graph from the picture. The requester still builds a dependency graph, resolves what it can from caches, computes an order, and dispatches. What changes is that dispatch is a network operation with its own latency, and the scheduler must account for the round trip and the transfer as part of each action’s cost. Graphs whose actions are individually cheap relative to a round trip gain nothing from a fleet; graphs with a few expensive actions gain the most.