阅读中文版本

Build a CRDT Text Collab

A last-write-wins text CRDT that supports concurrent insert and delete from multiple peers, converges without coordination, and serializes ops for transport.

crdt-text-collab/
├── src/crdt.ts
├── src/merge.ts
├── src/serialize.ts
├── tests/crdt.test.ts
└── package.json

const node = {id: [peer, clock++], left: leftId, right: rightId, ch, dead:false};

nodes.get(id).dead = true;

if (!nodes.has(op.id)) nodes.set(op.id, op.node); else applyTombstone(op);

return [...nodes.values()].sort(byLeftNeighbor).filter(n=>!n.dead).map(n=>n.ch).join("");

Project overview

A text editor that locks on every keystroke is not collaborative, it is serial. A CRDT lets multiple peers edit the same text concurrently and converge without coordination, because every operation is defined to commute. Two peers that insert at the same position both create a node with a unique id and the same left neighbor, and the merge resolves the tie by id order, so both peers end up with the same text regardless of who inserted first.

The character is a node, not a slot in an array. A node has a unique id, a left neighbor id, a character, and a tombstone. The id is a peer id and a lamport clock, so it is unique without a central coordinator. The left neighbor id is the anchor that orders the node in the text. The tombstone marks a deleted node, which stays in the structure so a concurrent insert after it still orders correctly.

The insert creates a node between two neighbors. The left neighbor id is the left neighbor id, and the node is placed after it in the order. A concurrent insert at the same position creates a second node with the same left neighbor, and the merge orders the two by id, so the text is the same on every peer.

The delete marks a node dead by id. The character is removed from the rendered text, but the node stays, because a concurrent insert that references it as a left neighbor needs it to exist. Removing the node would orphan the insert, and the text would diverge.

The value of this project is the convergence, not the editing. Editing text is trivial; proving that two peers that apply the same ops in different orders reach the same text is the part worth learning, because that guarantee is what lets a collaborative editor work without a central lock.

What you will build

The project delivers five capabilities, each driven by a test:

• Concurrent insert and delete
• Convergence without coordination
• Operation serialization for transport
• Peer-local tombstones
• Causal ordering via lamport clocks

Each character is a node with a unique id (peer, lamport), a left neighbor id, and a tombstone. Insert creates a node between two neighbors; delete marks a node tombstoned. Merge applies remote ops by id, ignoring duplicates. The text is the non-tombstoned nodes in left-neighbor order.

Architecture and data model

The node id is a pair of a peer id and a lamport clock. The peer id is a unique string per peer, and the lamport clock is a per-peer counter incremented on every op and updated to max(local, remote) on merge. The pair is unique without coordination, because two peers never share a peer id and a lamport clock is monotonic per peer.

The left neighbor id is the id of the node to the left, or null for the start of the text. The order of nodes is by left neighbor id, with ties broken by node id. This is a total order, so every peer that has the same set of nodes renders the same text.

The merge applies remote ops by id. If the node is new, it is inserted. If the node exists, only the tombstone is applied, because a delete may arrive before the insert that created the node. The merge is idempotent, because applying the same op twice has no effect: the node is already present, and the tombstone is already set.

The tombstone is a boolean on the node. A deleted node stays in the map but is skipped in the render. The tombstone is necessary for convergence, because removing the node would lose the ordering anchor for concurrent inserts.

The render walks the nodes, sorts by left neighbor id with id tie-break, filters out tombstones, and joins the characters. The sort is the expensive part, O(n log n), but it is only needed on render, not on every op. An incremental render that maintains the order on insert is faster but more complex.

The serialization writes the ops, not the nodes, because the ops are smaller and the nodes can be rebuilt by replaying. A peer that joins late receives the op log and replays it to build the current state. The op log is append-only, so it is cheap to serialize and transport.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A transport for op exchange (WebSocket or postMessage)

The dependencies cover the core needs:

• node:crypto (built-in) — Unique node id generation

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

crdt-text-collab/ is organized so each concern is testable in isolation:

crdt-text-collab/
├── src/crdt.ts
├── src/merge.ts
├── src/serialize.ts
├── tests/crdt.test.ts
└── package.json

Phase 1: Insert

Create a node with a unique id between the left and right neighbor ids.

const node = {id: [peer, clock++], left: leftId, right: rightId, ch, dead:false};

The id is a peer id and a lamport clock, so it is unique without coordination.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Delete

Mark a node dead by id; the character is removed but the node stays for ordering.

nodes.get(id).dead = true;

A tombstone keeps the node so a concurrent insert after it still orders correctly.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Merge

Apply remote ops by id, ignoring duplicates; conflicts on left-neighbor resolve by id order.

if (!nodes.has(op.id)) nodes.set(op.id, op.node); else applyTombstone(op);

Idempotent merge means receiving the same op twice is harmless.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Render text

Walk the nodes in left-neighbor order, skipping tombstones, to produce the text.

return [...nodes.values()].sort(byLeftNeighbor).filter(n=>!n.dead).map(n=>n.ch).join("");

The order is by left-neighbor id, so concurrent inserts at the same spot resolve deterministically.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Two peers insert at the same position concurrently, exchange ops in both orders, and assert both converge to the same text; one peer deletes a character another is inserting after, exchange ops, and assert convergence; merge the same op twice and assert idempotence.

The convergence test is the core test. Two peers start with the same empty text. Peer A inserts “a” at position 0, peer B inserts “b” at position 0, concurrently. They exchange ops, in both orders, and assert both render the same text, either “ab” or “ba”, but the same on both.

The delete-during-insert test has peer A insert “a” at 0, then peer B inserts “b” after “a”, and peer A deletes “a”, concurrently. They exchange ops and assert both converge, with “b” present and “a” gone, and the order is the same on both.

The idempotence test merges the same op twice and asserts the text is unchanged, proving duplicate ops are harmless. The commutativity test applies ops in two different orders on two peers and asserts the same text.

The tombstone test deletes a node, renders, and asserts the character is gone but the node is still in the map. A concurrent insert after the deleted node is merged and asserted to order correctly, proving the tombstone preserved the anchor.

The lamport test merges an op with a higher clock and asserts the local clock advances to the remote, so the next local op has a higher clock than any remote op seen.

pnpm vitest run

Observability

Track the concurrent insert and delete rate, the crdt resource usage, and the error count as the three primary signals for the crdt-text-collab system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the convergence without coordination alongside the concurrent insert and delete so a correlation is visible at a glance, because a rising convergence without coordination with a stable concurrent insert and delete means the system is doing more work per unit, not that it is failing.

Log every insert transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the crdt identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the concurrent insert and delete error rate crossing a threshold, the crdt utilization exceeding a percentage, and the convergence without coordination latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The crdt-text-collab system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Exchange ops over any transport: WebSocket for real-time, postMessage for same-browser, or even a shared file for offline. The CRDT does not require a central server, because the ops commute and the merge is idempotent. A relay helps peers that are not simultaneously online, by buffering ops and delivering them on reconnect.

Persist the op log, not the node map, so a restart replays the log and rebuilds the state. The op log is append-only, so it is cheap to persist and transport. A periodic snapshot of the node map reduces replay time on restart, but the log is the source of truth.

Keep the peer id stable across restarts, so the lamport clock stays monotonic. A peer that changes its id on restart may reuse a lamport clock and create a duplicate node id, which the merge would silently drop. Persist the peer id and the lamport clock together.

Do not garbage-collect tombstones without a quorum. A tombstone can be removed only when every peer has seen the delete, because a peer that has not may still insert after the tombstoned node. A quorum protocol to confirm tombstone visibility is out of scope, so tombstones grow unboundedly in this build.

Security considerations

Treat every input to the crdt-text-collab system as untrusted, because the concurrent insert and delete path is the one place an external caller controls what the system processes. Validate the input shape before any crdt operation, and reject early with a clear error rather than letting a malformed input propagate into the insert phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:crypto credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured crdt-text-collab fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the concurrent insert and delete endpoint per caller, because an unbounded crdt operation is a resource leak as much as a security problem. A caller that can trigger the delete path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the insert logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The crdt-text-collab system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the crdt structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• Tombstones grow unboundedly; a periodic GC needs a quorum that this build does not have.
• No rich text; this is plain text only.
• The lamport clock is per-peer and not persisted; a restart loses the clock and may reuse ids.

Tombstones grow unboundedly. Every deleted character stays in the node map forever, because removing it could orphan a concurrent insert. A garbage collection protocol that removes tombstones only when every peer has seen the delete needs a quorum, which this build does not have, so the map grows with edits.

There is no rich text. The CRDT handles plain text characters, not formatting, because formatting is a separate CRDT that composes with the text CRDT but is not built here. Bold, italic, and links are out of scope.

The lamport clock is per-peer and not persisted by default. A restart that loses the clock may reuse a clock value and create a duplicate node id, which the merge drops silently. Persisting the peer id and the clock avoids this, and the deployment notes describe it, but the default is in-memory and vulnerable.