Chord: replicated state, deltas and hot reload

Learning goals. After this chapter you should be able to:

• explain what Chord is for, and which parts of it Durable actually uses;
• use Context to pass cancellation and values explicitly, and explain why Chord avoids implicit async context;
• follow a change through the delta tracker: draft, prepare, adopt, replay;
• read and produce the six delta operations, and explain the wire encoder's path interning;
• explain the array diff (LCS and longest increasing subsequence) and the piece table behind array drafts;
• describe Chord's object model, its contract compatibility rule, and the prepare/gate/commit protocol of hot reload.

17.1 What Chord is#

Chord is the lowest layer in the Durable stack. Its README describes it:

Chord builds applications out of objects that live in several processes (a server, workers, browser tabs) and can be hot reloaded while they run.

It has one runtime dependency, typebox. Its spec makes that a hard constraint: "Chord's runtime depends only on its own delta module ... and Node/browser built-ins plus typebox for schemas. No other Pi packages." Keeping the bottom of a dependency graph this small is deliberate. Everything above can depend on it without cycles, and it can run in a browser.

Chord is several libraries in one package, exposed as separate entry points:

The chapter goes bottom-up: context, deltas, replicated state, then the object runtime.

17.2 Context: explicit invocation scope#

Almost every Durable signature ends with context: Context. The definition is small:

// packages/chord/src/context/index.ts
/** Immutable invocation-scoped values passed explicitly through operations. */
export interface Context {
	readonly abortSignal: AbortSignal | undefined;
	value<T>(key: ContextKey<T>): T | undefined;
	toString(): string;
}

The design is borrowed from Go's context.Context, down to the names BACKGROUND_CONTEXT and TODO_CONTEXT. A context is an immutable linked list. withContextValue(key, value, parent) returns a new node pointing at its parent; lookup walks up the chain until it finds the key:

value<Value>(key: ContextKey<Value>): Value | undefined {
	if (key.token === this.#key.token) return this.#value as unknown as Value;
	return this.#parent.value(key);
}

Keys are unique Symbols, so two libraries cannot collide on a string name. Because nodes are never mutated, a child can never change what its parent sees. Deriving a context is O(1) and a lookup is O(depth): the classic persistent-list trade-off.

The abort signal is just a value under a private key. Three helpers manipulate it:

• withAbortSignal(signal, ctx) combines the parent's and the new signal with AbortSignal.any, so cancellation flows down the tree;
• withCancel(ctx) returns a child context plus its own cancel function;
• withoutAbortSignal(ctx) removes cancellation while keeping every other value. Its comment states the intended use: "Intended for mandatory cleanup only."

That last one matters. When a task is aborted, its cleanup (closing a file, committing an aborted outcome) must still run. If the cleanup inherited the aborted signal, it would fail immediately. Durable uses withoutAbortSignal in harness/view.ts and harness/task-graph.ts for exactly this.

Why not AsyncLocalStorage? Node can carry values implicitly across await (AsyncLocalStorage). The Chord spec rejects it: "Explicit; no AsyncLocalStorage dependency". Implicit context is invisible in signatures, does not exist in browsers, and is easy to lose across callbacks. Explicit context costs a parameter but makes cancellation part of every function's type: a function without a context parameter visibly cannot be cancelled.

awaitWithContext(promise, ctx) shows the limits of cooperative cancellation (Chapter 6). It rejects the waiter on abort, but "it does not cancel the underlying promise". JavaScript promises have no cancel operation; only the code that created the work can stop it.

17.3 Immutable revisions and the ownership contract#

Durable's documents, views and task graphs are JSON values that change over time and are observed by others: UIs, remote replicas, storage. Chord's delta module produces, for each change, two things:

1. a new immutable revision of the value;
2. an exact operation batch that turns the previous revision into the new one.

Revisions use structural sharing: unchanged subtrees are the same objects in both revisions. Changing one field of a 10 MB document allocates a new path from the root to that field, nothing else. This is how persistent data structures work in Clojure, Immer and Git trees.

The interesting decision is how immutability is enforced. It isn't:

Immutability is an ownership contract. Nothing is frozen or defensively copied, so an illegal mutation is not detected. It silently corrupts state.

Object.freeze on every node costs time; deep-copying at every boundary costs more. Chord instead documents who may mutate what, in a table, and trusts callers:

This is Rust's ownership model without the compiler: move semantics (passing a root transfers it) plus borrowing (a draft is a mutable borrow that ends at prepare()). The README's "Do and don't" list is the borrow checker, written in English.

Full roots are "trusted": track() takes ownership in O(1) without walking the tree. Values placed into a draft are copied, and the copy validates them as strict JSON. Cycles, class instances, undefined, NaN, sparse arrays and accessors are rejected with a TypeError before the draft changes. Validation therefore happens once, at the boundary where untrusted data enters.

17.4 The tracker lifecycle#

delta tracker lifecycle · begin, prepare, adopt, replay

In Durable the ops reach storage between prepare() and adopt(). Replicas replay the same ops onto the base revision they already hold.

// from packages/chord/src/delta/README.md
const tracker = track(initial); // `initial` is transferred: never mutate it again

const change = tracker.beginChange();
change.state.output += "done\n"; // the draft is mutable only while the change is open
change.state.entries.push({ id: 1 }); // placed values are cloned; the caller keeps its object
const prepared = change.prepare(); // draft handles are unusable from here on

tracker.adopt(prepared); // tracker.value === prepared.value

const replica = applyImmutable(prepared.base, prepared.ops);

Four verbs, each with a precise meaning:

• beginChange() opens an overlay draft over the current revision. The draft is a Proxy: reads fall through to the base revision, writes are recorded in the overlay. The base is never touched. A draft may stay open across await.
• prepare() materialises the candidate value and the ops, but "does not change authority". Nothing is published yet.
• adopt(prepared) validates the preparation and swaps the root pointer. This is the single atomic step.
• abort() discards the change.

Several changes can be open against one revision. Adopting one makes all others stale: "open drafts become unusable and their prepare() throws, and prepared competitors are rejected by adopt()". This is optimistic concurrency control: everyone works against a snapshot, and the first to commit wins. It is the same rule as a compare-and-swap on a version number.

Splitting prepare from adopt is what Durable needs for its transactions (Chapter 14). In session/transaction.ts each document touched by a transaction gets a beginChange(). At commit time Durable calls prepare() on every document, writes the ops to storage, and only after the storage write succeeds calls adopt():

// packages/durable/src/session/transaction.ts
if (document.change !== undefined) document.prepared = document.change.prepare();
...
adopt(seq: Seq): DocumentCommitChange[] {
	...
	if (loaded === undefined ? !plan.retire : prepared.ops.length > 0) tracker.adopt(prepared);

If the write fails, nothing was adopted and memory still matches disk. This is the shape of two-phase commit: prepare everything, make the decision durable, then apply. The stored ops are exactly the document deltas from Chapter 13 ("documents as bases plus deltas").

17.5 The six operations#

A batch is a list of tuples:

The string ops are chosen for the workload. The commonest change in an agent UI is streaming output: text appended at the end and, once a buffer limit is hit, truncated at the front. a and t express that in a few bytes, where s would resend the whole string at every token. The string diff tries them in that order:

// packages/chord/src/delta/diff.ts
const emitString = (before: string, after: string, path: NonEmptyPath, operations: Op[]): void => {
	if (before === after) return;
	if (after.length > before.length && after.slice(0, before.length) === before) {
		emitOperation(operations, ["a", path, after.slice(before.length)]);
		return;
	}
	const shared = overlap(before, after, DEFAULT_OVERLAP_SCAN);
	if (shared === 0) {
		emitOperation(operations, ["s", path, after]);
		return;
	}
	emitOperation(operations, ["t", path, before.length - shared]);
	if (after.length > shared) emitOperation(operations, ["a", path, after.slice(shared)]);
};

overlap finds the longest suffix of before that is a prefix of after, the overlap between a sliding window's old and new contents. The answer becomes "drop this many from the front, append this".

Two rules keep batches safe:

• Exact but not canonical. "The same change may use different tuples, and large edit sets may fold into a region splice, an ancestor s, or r." Consumers must apply ops, never interpret their shape. There is also a cap: past MAX_DELTA_OPERATIONS = 4_096 operations, the batch folds into a coarser one. A huge diff is then no worse than resending the value.
• Prototype-pollution defence. The tracker never emits __proto__, constructor or prototype as a path segment, and the appliers reject them (UnsafePathError). Without this, a malicious batch ["s", ["__proto__", "isAdmin"], true] applied with naive assignment would modify Object.prototype for the whole process. That is the well-known prototype pollution vulnerability class.

17.6 Diffing arrays: LCS and patience#

When a whole new value replaces an old one (cell.replace(ctx, value)), Chord computes the ops by structural diff. For objects this is easy: compare keys. Arrays are the hard case, and diff.ts uses two classic algorithms.

Longest common subsequence (LCS) by dynamic programming. lengths[i][j] is the LCS length of before[i..] and after[j..], filled from the back:

// packages/chord/src/delta/diff.ts
lengths[at] = equal(before[left]!, after[right]!)
	? lengths[(left + 1) * width + right + 1]! + 1
	: Math.max(lengths[(left + 1) * width + right]!, lengths[left * width + right + 1]!);

This is O(n·m) time and memory, so it only runs when before.length * after.length is at most MAX_SEMANTIC_CELLS = 65_536. The table is a flat Uint32Array indexed left * width + right, a standard trick to store a 2-D table in one contiguous allocation.

Identity anchors via longest increasing subsequence. For larger arrays, Chord matches elements by identity: thanks to structural sharing, an unchanged element is often the very same object in both revisions. It records each object's positions in before, walks after, and finds the longest increasing subsequence of matched before positions with the patience-sorting technique (a tails array plus binary search lowerBound). That is O(k log k) in the number of candidate matches. Elements in that subsequence stay put; everything else becomes splices and moves. This is the core of the Hunt–Szymanski and patience diff algorithms used by version-control systems. Past MAX_IDENTITY_CANDIDATES = 200_000, it falls back to a greedy match, another bounded-cost fallback.

17.7 The draft's array: a piece table in a treap#

Inside a draft, array edits (splice, unshift, sort) must be cheap even on large arrays, and the tracker must still emit exact ops. tracker.ts represents an edited array as a piece table: a sequence of pieces, each pointing to a run of the original array or of an insert buffer:

// packages/chord/src/delta/tracker.ts
type BasePiece = { kind: "base"; start: number; length: number; step: 1 | -1 };
type InsertPiece = { kind: "insert"; source: InsertSource; start: number; length: number; step: 1 | -1 };

Piece tables are what text editors (VS Code, Word) use for documents: the original is never copied, and an insert in the middle splits one piece into three. step: -1 lets reverse() flip a piece without moving elements.

The pieces are kept in a treap, a binary search tree whose nodes also carry random priorities and are kept in heap order on them. Each node stores the element count of its subtree, so finding "element 40,000" is a walk down the tree in O(log n):

function mergePieceTrees(left: PieceNode | undefined, right: PieceNode | undefined): PieceNode | undefined {
	if (left === undefined) return right;
	if (right === undefined) return left;
	if (left.priority >= right.priority) {
		left.right = mergePieceTrees(left.right, right);
		updatePieceNode(left);
		return left;
	}
	...

The priorities come from an xorshift pseudo-random generator seeded with 0x9e3779b9, a constant derived from the golden ratio:

function nextPiecePriority(overlay: ArrayOverlay): number {
	let value = overlay.seed;
	value ^= value << 13;
	value ^= value >>> 17;
	value ^= value << 5;
	overlay.seed = value >>> 0;
	return overlay.seed;
}

A fixed seed keeps the tracker deterministic: the same edits produce the same tree and the same ops. With random priorities, the expected depth is O(log n) for any sequence of edits. Split and merge are the only two primitives, and both are a few lines. That simplicity is why treaps are a favourite "implicit key" structure (a rope) in competitive programming.

17.8 The wire codec: interning on second use#

Ops travel between processes. Paths repeat a lot: a streaming field ["view", "messages", 41, "text"] is appended to hundreds of times. encoder() compresses them with a per-stream dictionary:

// packages/chord/src/delta/index.ts
/**
 * Intern on SECOND use. A definition costs more than the path it replaces, so
 * interning on first use loses on the many paths written exactly once.
 */
export function encoder(): Encoder {

That comment is a small lesson in compression economics: a dictionary entry pays off only if the symbol recurs. Within a batch, consecutive ops on the same path also drop the path entirely ("arity omission").

The encoder also defines recovery points. A r op resets both dictionaries:

// A base batch is a RECOVERY POINT: a reader replays from the last one
// with a fresh decoder. So everything after it must be self-contained.

This is the keyframe idea from video codecs (an I-frame followed by P-frames). A late joiner, or a reader that hit a decode error, discards its state and waits for the next r. The rule "one encoder/decoder pair per ordered state stream" follows. The dictionary is shared state between exactly two endpoints, and any reordering or skipping between them breaks it.

17.9 Replicated state#

replicatedState(initial) wraps a tracker as an observable value. change(ctx, draft => ...) publishes exactly one atomic revision, or none if the callback throws. Durable uses it for documents, views and the task graph.

Subscriptions are deliberately lossy under pressure:

Each subscription retains at most 100 pending complete-value deliveries, excluding the running callback. On overflow, only the newest pending value, context, and delivery metadata are retained ... Thus public delivery sequences may skip.

This is conflation, also called "latest value wins". For state (not events) a slow consumer only needs the current value, not every intermediate one. A bounded queue that drops the middle keeps a slow UI from growing memory without limit. Compare Chapter 12, where the TUI renders at most every 16 ms whatever the change rate.

17.10 Bounded output and paced progress#

@earendil-works/chord/output holds the pieces Chapter 16 used for tool output. OutputBuffer keeps a head or tail window of a stream with OutputSkip records for what it dropped. Progress paces commits of a changing value:

// packages/chord/src/output.ts
/**
 * Adaptive progress commits: the first change after an idle period commits at once; each commit then delays the next
 * by at least `minIntervalMs` and by its written size at 100 KiB/s. At most one commit is in flight; changes made
 * meanwhile coalesce into the next one.
 */
export class Progress {

Three ideas combine here:

• leading-edge throttling: the first change goes out immediately, so a quiet process feels responsive;
• cost-proportional backoff: a big write buys a longer pause, so bandwidth is bounded at about 100 KiB/s;
• coalescing: at most one commit in flight, and later changes merge into the next.

This is why a bash tool printing megabytes does not turn into megabytes of durable commits.

17.11 The object runtime#

The rest of Chord is a distributed object system. Durable itself does not need it, but applications that put Durable sessions behind a server, workers and browser tabs do. The core terms (packages/chord/docs/spec.md):

• object: one instance of a type, with stable identity per (type, canonicalInput, principalKey);
• reference: "a late-bound claim on an object, never the object or its implementation". An object lives while referenced;
• principal: who is calling. An owner and a guest get different objects, with different methods (variants);
• host: a process that serves some object types; hosts are connected by links (in memory, Node IPC, WebSocket).

Contracts as runtime values. Types are declared with TypeBox schemas, because shipped bundles and third-party plugins have no TypeScript at runtime:

// packages/chord/README.md
export const Counter = remote("demo.counter", {
	version: 1,
	input: Type.Object({ name: Type.String() }),
	host: hostNamed("server"), // where its objects live; callers never name a host
	variants: {
		default: {
			state: { count: Type.Number() },
			methods: { increment: method(Type.Object({ by: Type.Number() })) },
		},
	},
});

Compatibility as subtyping. A consumer built against version M binds to a provider at version N only if N = M and "the provider's description covers the consumer's". Covers is defined precisely: the provider accepts every argument the consumer can send, and the provider's results fit the consumer's expected results. In type-theory terms, arguments are contravariant (the provider may accept more) and results are covariant (the provider may return more fields). Additive changes need no version bump; breaking ones do, and a same-version non-covering change is refused as a "forgotten bump". This is the formal version of the rules behind protobuf and API versioning.

Location transparency. A reference's address is the type, the normalized input and the principal, never a host name. Placement is part of the contract (hostNamed, hostFamily), and the runtime decides whether a get is local or remote. The caller code is the same either way.

Resource lifetime by reference counting. "An object lives while referenced". Disposal happens after the last release plus an optional linger. Disposal cascades through the object's own references, in waves "referrers before what they reference". In-host reference graphs must be acyclic (checked at get), because reference counting cannot collect cycles.

Remote state. A remote reference receives a snapshot of each state member, then delta batches from a per-stream encoder (17.8). Links have flow control: unacknowledged frames are bounded by a window (default 256 KiB of JSON). When too many ops wait, "the oldest streams become a reset of their current value built at flush". That is conflation again, now at the network level.

17.12 Hot reload as a distributed transaction#

Chord's most ambitious feature is replacing code while objects keep running. The spec's rule for in-flight work: "Work in flight finishes on the code it started with, state is kept, and incompatible changes migrate at a safe point."

Two mechanisms make this possible.

Code versions per root. Every short call tree (a root) carries { rootId, codeVersion }. "A call with code version E runs the object's implementation for E. A host retains at most current and previous code versions (two-version rule)." An old call can therefore finish on old code while new calls use new code. A call for a version the host no longer has is rejected superseded and retried, never silently run on different code.

A two-phase commit across hosts. The reload protocol (spec §7):

Prepare is side-effect free by construction (writes throw), so aborting it costs nothing. The gate is a quiescence barrier, needed only when state must migrate. Compatible changes "skip the gate: no waiting". The commit is a single synchronous step on each host. JavaScript's run-to-completion semantics then guarantee that no other code observes a half-installed reload.

State migration is versioned per cell: self.state("status", Schema, initial, { version: 2, migrate }). The rule mirrors database schema migrations. "Schema changed without a raised version: reload refused. A lowered version: refused."

The spec is also honest about what is not solved. The commit decision is not persisted, and the plugin loader leaks old module copies ("TODO(loader): replace with an isolating, evicting loader"). Reading a system's list of known limitations is one of the fastest ways to understand where its hard problems are.

Concepts in this chapter#

• Explicit context. Cancellation and request-scoped values passed as an immutable parameter, Go-style; cancellation flows down, never up.
• Persistent data structures and structural sharing. New versions share unchanged subtrees with old ones.
• Ownership and move semantics. Who may mutate what, as a documented contract instead of runtime checks.
• Optimistic concurrency control. Work against a snapshot; the first adopter wins and competitors go stale.
• Two-phase commit. Prepare, make the decision durable, then apply.
• Operational deltas. Small typed ops (set, delete, append, truncate-front, splice, move) that replicas replay in order.
• Prototype pollution. Why path segments like __proto__ must be refused.
• LCS by dynamic programming; LIS by patience sorting. The two cores of practical diff algorithms.
• Piece tables and treaps. Edit large sequences without copying; random priorities give expected O(log n).
• Xorshift PRNG. A fast deterministic generator from three shift-xor steps.
• Dictionary compression and keyframes. Intern repeated symbols; reset at recovery points.
• Conflation. For state, drop intermediate values under pressure and keep the latest.
• Leading-edge throttling and coalescing.
• Variance. Contravariant arguments and covariant results define safe API evolution.
• Reference counting. Lifetime by outstanding references; cycles must be prevented.
• Hot code swapping. Versioned code per call, prepare/gate/commit/retire.

Exercises#

1. Context. Implement withTimeout(ms, ctx) on top of withCancel. Then write a function that must close a file even when ctx is aborted, and show why it needs withoutAbortSignal.
2. Stale drafts. Using track(), open two changes on the same revision, prepare both, and adopt one. What happens to the other? Explain how this prevents a lost update.
3. Front truncation. Given before = "abcdef" and after = "defgh", what ops does emitString produce? Then do it for after = "xyz".
4. Prototype pollution. Write a naive applyOps that sets obj[path[0]][path[1]] = value. Show that ["s", ["__proto__", "polluted"], true] makes ({}).polluted === true. Fix it the way Chord does.
5. Patience diff. Implement LIS with a tails array and binary search. Use it to align [A, B, C, D, E] with [B, A, C, E, D] by identity, and list which elements a splice-based diff must move.
6. Treap. Implement an implicit treap with split(root, k) and merge(a, b) storing subtree sizes. Use it to implement insertAt and removeAt, and measure depth after 100,000 random inserts.
7. Interning. For the path sequence P1, P2, P1, P3, P1, P1 (one op each, separate batches), write what the encoder sends under intern-on-first-use and intern-on-second-use. Which is smaller, and when would the answer flip?
8. Compatibility. A provider changes search(args: { query: string }) to search(args: { query: string; limit?: number }) and adds a field to its result. Is this covering? What if limit were required?