watershed Collaborative data structures for Gleam

← watershed · Data structures / Convergence models

Three ways to
agree on state.

Every structure watershed ships has to answer one question: when two clients change the same thing at once, how does everyone end up in the same state? watershed has three answers: order it, merge it, or transform it. Each is the right one somewhere.

DDS

Distributed Data Structure

Converges by one server’s total order.

A DDS here follows Fluid Framework’s collaborative-object model. Every client applies its own ops optimistically, sends them to a central sequencer, and receives one authoritative order back. Because every replica replays the same ordered stream, they all land in the same state.

The conflict policy applies on top of that order: last-write-wins for a map, first-writer-wins for a claim, FIFO for a queue, quorum for a pact. The order is the source of truth; the policy just decides what the order means.

Simple and cheap, but it needs a sequencer, and offline correctness is only as good as the policy you layer on.

CRDT

Conflict-free Replicated Data Type

Converges by a merge function, no order required.

A CRDT is designed so its merge is commutative, associative, and idempotent. Feed two replicas the same set of updates in any order, any number of times, and they converge. No central authority is needed to referee.

watershed still delivers CRDT ops over the same sequenced stream, but their correctness does not depend on it. That is why the demo can feed a duplicate delta straight to the kernel and watch the merge absorb it with no double-count. Commutativity, associativity, and idempotence provide that safety; an order-based DDS relies on the runtime deduping by sequence number.

Its merge can tolerate duplicate and reordered state or deltas, but offline editing still needs durable local storage and a reconnect protocol. Metadata costs depend on the type: some keep per-replica counters, while removable collections retain tags or tombstones.

OT

Operational Transform

Converges by transforming ops past one another.

OT takes the opposite tack from CRDTs. Instead of designing merges that commute, it transforms each op against the concurrent ops it did not see, rewriting indices and positions until any apply order lands in the same place.

watershed ships two OT kernels on the same single-op-in-flight client protocol. json_ot is a faithful port of the ottypes json0 algebra for structured JSON documents. SharedRichText runs that protocol over quill-delta's rich-text algebra (retain/insert/delete spans, attribute patches, embeds) for collaborative Quill editors. In both, concurrent ops have their positions transformed so every replica converges identically.

Minimal per-op metadata and a natural fit for ordered sequences and rich text (SharedSequence now covers similar ground by merge). The cost: transform functions must be correct for every pair of op types.

Side by side

The same axes, three answers. None of these is strictly better; they trade a sequencer, metadata, and offline behavior against one another.

Property DDS CRDT OT
Converges via one server’s total order a commutative merge function pairwise op transforms
Needs a sequencer Yes: the order is the truth No (watershed uses one anyway) Yes: to assign the order to transform against
Duplicate / reordered delivery runtime orders and deduplicates by sequence number merge is designed to absorb repeats and reordering client protocol buffers and transforms the ordered stream
Per-item metadata structure-dependent; often a value plus sequence data type-dependent; may include replica slots, tags, or tombstones document state plus in-flight and buffered ops
Offline / unreliable links policy and client persistence determine safety merge supports it; storage and transport still required requires buffered ops and ordered reconnect
Best fit clear authority, coordination offline-first, at-least-once delivery text and ordered sequences

Which model fits?

  1. Start with a DDS. If a central server is already in the loop and last-write-wins or explicit coordination is acceptable, an order-based DDS is the least machinery for the job. Use SharedMap, Claims, or PactMap.
  2. Use a CRDT when delivery is unreliable. Offline edits backed by durable local storage, at-least-once delivery, or a counter that must survive a re-sent delta all call for a merge that does not care about order: PN counter, OR-set, or OR-map.
  3. Use OT for ordered sequences and rich text. Collaborative text and lists, where positions shift as others edit, are what transform functions were built for. See the json_ot demo for structured JSON or the SharedRichText demo for a three-editor Quill session.