Distributed Build System (Bazel Remote Execution-class) #

This note models a Bazel remote-execution-class build system where clients submit build actions, a scheduler assigns them to executors, artifacts are stored by content address, and results are reused through caching.

Step 1 - Normalize #

Assume the baseline prompt is:

• design a distributed build system
• clients submit builds made of many actions
• actions run remotely on executors
• outputs are uploaded and reused through cache
• system scales across many workers

Normalize into state-affecting paths.

Notes on normalization #

Important choices:

• build submission is append event
  • build intent is immutable fact recording
• runnable action creation is also append event
  • action requests are materialized work items
• executor claim is state transition
  • action moves from ready to claimed/running
• artifact upload is append event
  • CAS/blob storage is immutable by digest
• action result commit is state transition
  • current execution/result state changes
• retries and ownership are explicit because this is distributed infra

This system is a hybrid of:

• claimable execution queue
• content-addressed immutable storage
• build graph orchestration

Step 2 - Critical Path Selection #

Baseline critical paths #

Main C1 paths:

• P1 submit build / action requests
• P2 claim action
• P3 upload artifacts
• P4 commit action result
• P5 retry timed-out or failed action
• P6 route to shard owner
• P7 reassign shard ownership

Main R1 path:

• P8 read action cache / CAS

This design is driven by:

• immutable artifact addressing
• one active executor claim per action attempt
• guarded action completion
• result reuse through cache keys and digests

Step 3 - Primary State Extraction #

For a distributed build system, the minimal primary state is the build request, runnable action, action execution lifecycle, immutable content blobs, action result metadata, and routing/ownership state.

Important modeling choices #

BuildRequest #

Primary because:

• build submission is immutable request recording
• captures target set, platform, and request metadata

ActionRequest #

Primary because:

• scheduler materializes runnable work as distinct action items
• action identity is central to remote execution

ActionExecutionState #

This is the main execution lifecycle object. It captures states like:

• READY
• CLAIMED(executor_id, claim_token, expiry)
• RUNNING
• SUCCEEDED
• FAILED
• RETRY_PENDING

ContentBlob #

Primary because:

• artifacts are immutable and addressed by digest
• CAS storage is one of the core correctness layers

ActionResult #

Primary because:

• action cache lookup uses current result metadata
• links action digest to output digests and execution metadata

PartitionOwnership / PartitionMap #

Needed because:

• scheduler and executors must consistently route action claims and state updates to authoritative owners

Minimal strict primary set #

The strongest minimal set is:

• BuildRequest
• ActionRequest
• ActionExecutionState
• ContentBlob
• ActionResult
• PartitionOwnership
• PartitionMap

Step 4 - Hard Invariants #

For a Bazel remote-execution-class system, the hard invariants are about durable action existence, one active executor claim per action attempt, immutable blob addressing, and correct result linkage.

What matters most #

1. One active executor claim per action #

This is the execution-control invariant.

2. CAS immutability by digest #

Artifacts with the same digest must mean the same bytes.

3. Action result must only point to valid blobs #

Result metadata cannot reference outputs that were never durably stored.

4. Duplicate execution may still happen under retry #

At-most-once execution is usually not the baseline guarantee. Systems rely on deterministic actions and cacheability rather than exactly-once execution.

Step 5 - Execution Context #

For the strict baseline distributed build system:

Derived implications #

• holder_may_crash = true

  • executors can crash while holding claimed actions

• cross_service_write = false

  • baseline keeps action state, CAS metadata, and ownership in one logical service

• bounded_staleness_allowed = false

  • claim/result-commit paths need authoritative current state

• cross_service_atomicity_required = false

  • no multi-service transaction across unrelated services in baseline

• exclusive_claim_required = true

  • one executor should hold an action attempt at a time

• guarded_by_current_state = true

  • claim, commit, retry, and failover depend on current action state

What this implies #

This pushes us toward:

• one authoritative owner per action shard
• explicit action execution state machine
• claim timeout modeled as lease-like executor ownership
• immutable CAS storage with digest validation

Step 6 - Deterministic Mechanism Selection #

Why these fit #

Build / action submission #

These are immutable workload facts, so append-only fits.

Action claim #

Executor ownership is temporary and exclusive, so lease semantics fit.

Artifact upload #

CAS storage is immutable by digest, so append-only content-addressed writes fit.

Result commit #

Committing an action result is not a blind write. It must verify:

• current action state
• current claim token
• referenced output digests exist

So it is a guarded transition.

Canonical substrate implied #

The baseline now points to:

• sharded build scheduler / action queue
• one owner per action shard
• immutable content-addressed blob store
• per-action execution lifecycle state
• guarded result commit after artifact upload

Step 7 - Read Model / Source of Truth #

For a Bazel remote-execution-class system, truth is mostly direct source state. Status dashboards are derived.

Important point #

For the core semantics:

• cache lookup reads authoritative ActionResult
• output downloads read authoritative CAS blobs
• claim/commit paths operate on authoritative ActionExecutionState
• dashboards are projections

Step 8 - Failure Handling #

What matters most #

1. Claim-token fencing #

This is the scheduler/executor safety mechanism.

Bad case:

• executor A claims action
• action times out
• executor B reclaims action
• A later uploads result and tries to commit it

Without fencing:

• A could incorrectly publish a stale result

So result commit must be tied to the current claim token.

2. CAS first, result commit second #

Artifact bytes should be durably stored and digest-verified before publishing ActionResult.

3. Duplicate execution is tolerated #

If an executor crashes after doing work but before result commit:

• another executor may rerun the action

The system relies on deterministic execution and cache keys, not exactly-once execution.

Step 9 - Scale Adjustments #

What scales well #

This system scales by:

• sharding action scheduling
• giving each shard one authoritative owner
• keeping claim/commit local to that owner
• storing blobs in content-addressed immutable storage that can scale independently

What fails first #

Usually:

• scheduler shard hot spots
• CAS bandwidth bottlenecks
• stale-result fencing mistakes
• retry storms after executor failures

Canonical design conclusion #

The mechanical outcome is:

• primary state:
  • BuildRequest
  • ActionRequest
  • ActionExecutionState
  • ContentBlob
  • ActionResult
  • PartitionOwnership
  • PartitionMap
• critical invariants:
  • durable build/action submission
  • one active executor claim per action attempt
  • immutable CAS blobs by digest
  • result commit valid only for current claim token and existing output digests
  • timed-out or retryable actions become runnable again safely
• mechanisms:
  • append log
  • lease
  • content-addressed immutable storage
  • guarded result commit / retry transitions
  • fenced shard ownership
• reads:
  • direct authoritative reads for action/result/CAS state
  • projections only for build status and queue stats

Polished interview answer #

“I’d design the distributed build system as a sharded remote-execution service with one leader per action shard. Build submission records immutable build and action requests. Executors reserve actions through a lease-like claim that issues a claim token and expiry, upload outputs into a content-addressed blob store by digest, and then commit action results through a guarded transition that succeeds only for the current claim token and only if referenced output digests already exist. If an executor crashes or times out, the action is safely requeued for at-least-once execution, while cache hits come from authoritative action-result metadata plus immutable CAS blobs. The main scaling levers are more scheduler shards, independent CAS scaling, locality-aware caches, and retry backoff control.”

Concrete Substrate #

I’ll choose a service-owned sharded build scheduler with executor fleet plus separate content-addressed storage as the concrete baseline, because it matches the mechanics we derived:

• append-only build/action submission
• lease-like action claim
• immutable CAS artifact uploads
• guarded action-result commit
• one owner per shard

Concrete tech family:

• scheduler service in Go or Java
• local durable metadata storage:
  • RocksDB or replicated metadata DB
• shard replication:
  • Raft or leader-follower replication with commit index
• CAS storage:
  • object storage or blob service addressed by digest
• metadata/control:
  • etcd or internal metadata quorum

Each shard leader stores:

• action records
• current ActionExecutionState
• ready-action queue
• claim-expiry index
• build-to-action tracking metadata

CAS stores:

• immutable input/output blobs
• directory trees / manifests by digest

Operation Layer #

1. Submit build #

API

• SubmitBuild(build_request, request_id?)

Initiator

• client/build tool

Entry point

• gateway or scheduler frontend

Authoritative decider

• scheduler shard owner(s)

Precondition

• request id optional for dedup

Transition

• append BuildRequest
• materialize runnable ActionRequest records for ready actions

Response

• {build_id}

2. Claim action #

API

• ReserveAction(worker_capabilities, max_actions, lease_timeout)

Initiator

• executor/client

Entry point

• scheduler frontend or shard leader

Authoritative decider

• shard leader owning the action

Precondition

• action chosen must currently be READY
• executor capabilities satisfy action requirements

Transition

• selected action:
  • READY -> CLAIMED(executor_id, claim_token, expiry)
• remove from ready queue
• insert into claim-expiry index

Response

• {actions: [{action_id, command_digest, input_root_digest, claim_token, lease_expiry}]}

3. Upload artifact #

API

• PutBlob(digest, bytes)

Initiator

• executor/client

Entry point

• CAS service

Authoritative decider

• CAS blob store

Precondition

• uploaded bytes hash to stated digest

Transition

• store immutable ContentBlob(digest)

Response

• success / already exists

4. Commit action result #

API

• CommitActionResult(action_id, claim_token, result_metadata)

Initiator

• executor/client

Entry point

• scheduler frontend or shard leader

Authoritative decider

• shard leader owning the action

Precondition

• current ActionExecutionState is CLAIMED
• claim_token matches current holder
• referenced output digests exist in CAS

Transition

• CLAIMED -> SUCCEEDED
• overwrite ActionResult(action_digest)

Response

• success

5. Requeue timed-out or failed action #

API

• internal background process

Initiator

• system

Entry point

• shard leader

Authoritative decider

• shard leader

Precondition

• action is still CLAIMED and expired
• or action is failed and retryable by policy

Transition

• move action back to READY
• clear current claim token
• reinsert into ready queue

6. Lookup cached result #

API

• GetActionResult(action_digest)

Initiator

• client/build tool or scheduler

Entry point

• result service / shard owner

Authoritative decider

• authoritative result store

Precondition

• none

Transition

• none

Response

• result metadata if present

Entry Point vs Decider vs Responder #

Concrete HLD #

Main components:

• build frontend / API gateway
  • receives build submissions
• scheduler shard leaders
  • authoritative owners for action lifecycle
  • manage ready, claimed, and retry indexes
• executor fleet
  • pulls runnable actions
  • downloads inputs and uploads outputs
• CAS / blob store
  • stores immutable inputs and outputs by digest
• metadata/control service
  • tracks shard ownership and routing
• background timeout / retry workers
  • usually run on shard leaders

Short Interview Version #

I’d build the distributed build system as a sharded remote-execution service with one scheduler leader per action shard plus a separate content-addressed blob store. Build submission records immutable build and action requests. Executors reserve actions through a lease-like claim with a claim token and expiry, execute remotely, upload outputs to CAS by digest, and then publish action results through a guarded transition that succeeds only for the current claim token and only if referenced output digests exist. If an executor crashes or times out, the action is safely requeued for at-least-once execution, while cache hits come from authoritative action-result metadata plus immutable CAS blobs.