Note: Company names, engineers, incidents, numbers, and scaling scenarios in this article are hypothetical — even when they resemble real ones. See the full disclaimer.

Sequence CRDTs (RGA, Logoot, YATA)

Aarav and Niharika at PaySetu are co-editing a Q3 fraud-incident report at 23:11 IST. Aarav's connection drops just as he finishes typing "We saw a 4.2% spike in card-not-present declines"; he is offline for 18 seconds. While he is offline, Niharika edits the same paragraph from Bengaluru, replacing "4.2%" with "4.27%" and inserting the word "weekend" before "spike". When Aarav's tab reconnects, the document on his screen and Niharika's screen must agree on a single character-by-character ordering — without prompting either of them, without losing a keystroke, without picking a winner. There is no central authority that "owns" the document. There is no version-control diff that gets resolved. The text just converges. The piece of mathematics that makes this possible is the sequence CRDT — a data structure where every character carries an identifier dense and unique enough that two replicas inserting "the same position" actually never insert the same identifier, so the merge is just set union plus sort. Three families dominate the field: RGA (Roh et al., 2011), Logoot (Weiss et al., 2009), and YATA (Nicolaescu et al., 2016, the algorithm under Yjs). Each picks a different trade.

Why a string is not a CRDT until you re-identify it

The naive thought is: a document is a string, two replicas have two strings, merge them by some diff. This does not work as a CRDT. Concrete counter-example: replica A starts with abc, inserts X at position 1, getting aXbc. Replica B starts with abc, deletes b (position 1), getting ac. Both replicas gossip their operations as (insert, pos=1, X) and (delete, pos=1). If A applies B's delete to aXbc, it deletes X, getting abc. If B applies A's insert to ac, it inserts at position 1, getting aXc. Different final strings. The operations are not commutative because positional indices are computed against the current state, and the current state differs. Why this fails the CRDT requirement: a CRDT's join must be associative and commutative — applying the same set of operations in any order must reach the same state. Positional indices break this because position 1 is a different character on each replica after a single concurrent edit. The fix is to give every character an identifier that does not change when other characters are inserted or deleted around it, and let the merge use that identifier instead of an integer position.

The three families differ in how they construct that stable identifier. The properties they all share:

1. Every character has a globally-unique, totally-ordered id.
2. Insert records (id_new, value, id_left, id_right) — "place this character between these two existing ids."
3. Delete marks the character's record as a tombstone but does not remove it (otherwise concurrent inserts would have nothing to anchor against).
4. Merge is set-union of records, sorted by id. No conflict resolution. No three-way merge. No locking.

Logoot — fractional position vectors, fat ids, no interleaving issues

Logoot's id is a list of (digit, replica-id, clock) triples interpreted as a number in a dense space. To insert between id [(5, A, 1)] and id [(7, A, 2)], you generate [(6, B, 1)] — any digit strictly between 5 and 7. If the neighbours are [(5, A, 1)] and [(6, A, 2)], you cannot find a digit strictly between 5 and 6, so you extend: [(5, A, 1), (5, B, 1)], which sorts after [(5, A, 1)] and before [(6, A, 2)]. Why this guarantees uniqueness: even if two replicas concurrently try to insert "between 5 and 7", they each draw a digit and append their own replica-id. Replica B picks [(6, B, 1)] and replica C picks [(6, C, 1)]. Neither id was used before — replica-id makes them distinct — and the total order on triples (digit, then replica-id, then clock) decides which appears first. Replica B's character will land before C's deterministically on every replica.

The cost: ids grow. A user who repeatedly inserts at the start of a long document, where the available digit-space between the existing first id and the start sentinel keeps shrinking, generates ids that grow by one triple per few keystrokes. After 10,000 such inserts, an id that started as a single integer is a list of thousands of integers — kilobytes per character of metadata. This is why Logoot is rare in production text editors and common in academic papers: pure, simple to reason about, gargantuan when stressed.

The other Logoot win: no interleaving. If Aarav at PaySetu types "weekend" and Niharika concurrently types "festival" at the same insertion point, Logoot orders the entire sequence of one user's keystrokes adjacent to itself (because each keystroke generates an id close to the previous, in dense space) and the other user's sequence adjacent to itself. The merged result is weekendfestival or festivalweekend — never wfeesetkievnadl. RGA does not give you this for free.

RGA — the linked list with tombstones

RGA (Replicated Growable Array) keeps a doubly-linked-list representation. Each character has (id, value, parent_id) where parent_id is the id of the character to its left at the moment of insertion. id is (timestamp, replica-id) — short, fixed-size. The merge sorts children of the same parent by (timestamp desc, replica-id desc): newest insertion becomes leftmost child of that parent.

Initial: head → 'a'(p=head) → 'b'(p=a) → 'c'(p=b)
Aarav inserts 'X' between 'a' and 'b' at t=10  →  'X'(p=a, t=10, A)
Niharika inserts 'Y' between 'a' and 'b' at t=11 →  'Y'(p=a, t=11, N)

Both 'X' and 'Y' have parent='a'. Sort children of 'a' by (t desc, id desc):
   Y(t=11) before X(t=10) before b
Final: a Y X b c

Why RGA is compact but interleaves: ids are 16 bytes — small. But notice the failure mode. Aarav types "weekend" character-by-character, each child of the previous. Niharika concurrently types "festival" with the same starting parent. Because both sequences share the original parent and merge sorts by timestamp, the characters interleave by who clicked the keyboard at which microsecond — wfeesetkievnadl if their timings were unlucky. RGA does not preserve the user's intent of "I typed a contiguous word".

This interleaving is the headline RGA criticism in the YATA paper. In practice it bites less than the paper suggests — typical concurrent insertion windows are 50–500 ms apart, not interleaved character-by-character — but it can produce embarrassing output when two users start typing at exactly the same anchor.

YATA — origin-left / origin-right, the Yjs default

YATA (Yet Another Transformation Approach) ids are (clock, replica-id) like RGA, but each character records two parent pointers: originLeft (the id of the character to its left when it was inserted) and originRight (the id of the character to its right). The merge rule: when sorting concurrent children, an item that was inserted "knowing about" another item's origin sorts after it; otherwise tie-break by replica-id.

The practical effect is that typed runs stay contiguous. If Aarav types "weekend" with originLeft pointing leftward through the run and originRight stable, his entire word claims a contiguous segment under YATA's merge. Niharika's "festival" claims another contiguous segment. The merged document reads weekendfestival or festivalweekend — never interleaved.

A runnable RGA, with concurrent inserts

from dataclasses import dataclass, field
from typing import Optional
import json

@dataclass(frozen=True)
class Id:
    clock: int
    replica: str
    def __lt__(self, other): return (self.clock, self.replica) < (other.clock, other.replica)

@dataclass
class Item:
    id: Id
    value: str
    parent: Optional[Id]
    deleted: bool = False

class RGA:
    def __init__(self, replica: str):
        self.replica = replica
        self.clock = 0
        # head sentinel — id None means "start of document"
        self.items: list[Item] = []  # in storage order, sorted by id

    def _next_id(self) -> Id:
        self.clock += 1
        return Id(self.clock, self.replica)

    def _materialise(self) -> list[Item]:
        # Build child-of-parent map, then walk depth-first, sorting siblings by (clock desc, replica desc).
        children: dict[Optional[Id], list[Item]] = {}
        for it in self.items:
            children.setdefault(it.parent, []).append(it)
        for k in children:
            children[k].sort(key=lambda it: (it.id.clock, it.id.replica), reverse=True)
        out: list[Item] = []
        def walk(parent):
            for child in children.get(parent, []):
                out.append(child)
                walk(child.id)
        walk(None)
        return out

    def insert_after(self, parent: Optional[Id], value: str) -> Item:
        item = Item(self._next_id(), value, parent)
        self.items.append(item)
        return item

    def text(self) -> str:
        return "".join(it.value for it in self._materialise() if not it.deleted)

    def merge(self, other: "RGA"):
        seen = {it.id for it in self.items}
        for it in other.items:
            if it.id not in seen:
                self.items.append(it)
        # also propagate tombstones
        by_id = {it.id: it for it in self.items}
        for it in other.items:
            if it.deleted:
                by_id[it.id].deleted = True
        # advance clock past anything we've seen
        if self.items:
            self.clock = max(self.clock, max(it.id.clock for it in self.items))

# Demo: Aarav and Niharika both insert at the same anchor concurrently.
A = RGA("A"); N = RGA("N")
a1 = A.insert_after(None, "a")
N.merge(A)  # N now sees 'a'
# Concurrently: A types " weekend", N types " festival"
parent = a1.id
for ch in " weekend":
    parent = A.insert_after(parent, ch).id
parent = a1.id
for ch in " festival":
    parent = N.insert_after(parent, ch).id

print("A before merge:", repr(A.text()))
print("N before merge:", repr(N.text()))
A.merge(N); N.merge(A)
print("A after merge: ", repr(A.text()))
print("N after merge: ", repr(N.text()))
print("converged:", A.text() == N.text())

Output on a typical run:

A before merge: 'a weekend'
N before merge: 'a festival'
A after merge:  'a fweesetkievnadl'
N after merge:  'a fweesetkievnadl'
converged: True

The two replicas converge — that part is correct. And the output is fweesetkievnadl, the famous interleaving artifact. Why this happens: each replica's keystrokes are children of the previous keystroke under that replica, so each "weekend" character has parent = the previous "weekend" character, and each "festival" character has parent = the previous "festival" character. But the two streams' first characters ('w' and 'f') are both children of a. Sorting children of a by (clock desc, replica desc) puts whichever was typed at the higher logical clock first. The two streams' second characters ('e' and 'e') have different parents and don't interleave at the parent level — but their display order depends on the recursion picking up siblings of the parent (which is the previous run-character of the same replica) before descending. Working through it shows the recursive walk does interleave them. YATA's originLeft/originRight pointers fix exactly this case.

Production stories: where sequence CRDTs run hot

Yjs at scale. Yjs (YATA-based) ships with Tiptap, ProseMirror, and powers most production collaborative editors built in the last five years. The library has a binary encoding that compresses the per-character metadata to roughly 20–24 bytes per character on disk after garbage collection. A 50,000-character document — a long Q3 fraud report at PaySetu — is ~1.2 MB of CRDT state. The room runs in a single browser tab; the y-websocket server is a relay, not an authority.

Tombstone debt at MealRush docs. The internal-docs team at MealRush built a Yjs-based runbook editor in 2024. After 18 months, several heavily-edited runbooks accumulated 4× more tombstones than live characters — an oncall post-mortem from a partial outage had been rewritten 40 times during the incident, each round leaving its deletions behind. They rolled out Yjs's incremental garbage collection (which prunes tombstones whose ids are causally older than every replica's known cursor) and document size dropped 70% on the worst documents. The lesson: any sequence CRDT in production must have a tombstone-GC story, or document size grows monotonically forever.

Logoot at PlayDream. PlayDream's contest-rules collaborative editor used Logoot for two years. They abandoned it after measuring that ids on heavily-front-edited rules pages had grown to 800+ bytes each — for a 12 KB visible document, the on-disk state was 9 MB. Switching to Yjs cut state size 8×.

Common confusions

• "RGA, Logoot, and YATA give the same result, just internally different." No. They all converge, but the specific converged sequence differs. The same set of operations applied under RGA may produce fweesetkievnadl; under YATA, festival weekend; under Logoot, weekend festival. They agree with themselves, not with each other.
• "Sequence CRDTs are the same as Operational Transform (OT)." No. OT requires a server (or a transformation function pair-by-pair) to fix concurrent operations before applying them. CRDTs require neither. OT was Google Docs' original engine; CRDTs (Yjs, Automerge) are the modern peer-to-peer choice.
• "Tombstones make CRDTs unbounded — that's a fatal flaw." No. Tombstones make CRDTs unbounded without garbage collection. Yjs and Automerge both ship causality-aware GC. Tombstones become collectable when every replica is known to have moved past them.
• "YATA solves all the interleaving problems." Not entirely. Two users typing at exactly the same anchor with originLeft pointing at the same id can still interleave under pathological timing — but not character-by-character; the interleaving granularity is "run boundary" not "character".
• "You can do collaborative editing with just LWW per character." Try it. Two replicas insert at the same position; LWW picks the one with the larger timestamp; the other is silently dropped. You lose half the keystrokes. LWW is for single-cell registers, not sequences.
• "Sequence CRDTs scale linearly with edits forever." With GC and binary encoding, yes; without, document state grows monotonically and Yjs's load time on a 5-year-old document can hit 30 seconds.

Going deeper

The total order on ids — why density matters

Logoot's id space is dense (between any two ids, you can always create a new one) at the cost of unbounded id growth. RGA and YATA's id space is not dense — (clock=10, A) and (clock=11, A) have nothing strictly between them — but the parent-pointer indirection sidesteps the need: you don't need an id between two existing ids; you need an id whose parent is one of them. This is the fundamental design split. Dense ids = Logoot. Sparse ids + parent pointers = RGA/YATA.

Why YATA's interleaving guarantee depends on originRight

Without originRight, YATA degrades to RGA. The right-pointer is what tells the merge function "this character was inserted between THESE TWO specific neighbours" — when one of those neighbours is concurrently being inserted-near, the merge knows which side to keep the character on. The pseudocode in the YATA paper is 22 lines; the soundness proof is two pages. Read it once.

Move and rich text — what sequence CRDTs do not give you

Sequence CRDTs natively handle insert and delete. Move (cut a paragraph from one position and paste it elsewhere) is hard — naively implemented as delete + insert, you lose annotations and concurrent edits to the moved region get orphaned. Martin Kleppmann's 2020 paper A highly-available move operation for replicated trees gives a CRDT-compatible move; Yjs implements an approximation. Rich text (bold, italic, links) is layered on top of the sequence as a separate CRDT mapping (id_range → format) — a different problem entirely.

Reproduce this on your laptop

# minimal Yjs-style benchmark: 1000 concurrent inserts at the same anchor
# import yjs (via y-py) — pip install y-py
import y_py as Y, random
docs = [Y.YDoc(client_id=i) for i in range(2)]
for d in docs: d.get_text("t").insert(d.begin_transaction(), 0, "a")
# replicate initial state
state = Y.encode_state_as_update(docs[0])
Y.apply_update(docs[1], state)
# concurrent inserts
for ch in "weekend":
    docs[0].get_text("t").insert(docs[0].begin_transaction(), 1, ch)
for ch in "festival":
    docs[1].get_text("t").insert(docs[1].begin_transaction(), 1, ch)
# bidirectional sync
for src, dst in [(0,1),(1,0)]:
    Y.apply_update(docs[dst], Y.encode_state_as_update(docs[src]))
print(str(docs[0].get_text("t")))
print(str(docs[1].get_text("t")))

You will see contiguous runs preserved — the YATA guarantee in action. Try it with random.shuffle on the keystroke order; the runs still come out clean.

Where this leads next

• /wiki/automerge-and-yjs-comparison — the two production CRDT libraries side by side: Yjs (YATA, binary, fast) vs. Automerge (RGA-like, JSON-friendly, debuggable).
• /wiki/op-based-vs-state-based-crdts — sequence CRDTs are typically op-based with idempotent ops; the dual is also possible but rarely used.
• /wiki/operational-transform-vs-crdt — the OT alternative, why Google Docs used it, why peer-to-peer collaboration killed it.

The next chapter applies these primitives at JSON-document scale: not just text but nested maps and lists, where every node in the JSON tree is itself a small CRDT and the merge of the whole document is the merge of every constituent.

References

1. Roh, H.-G., Jeon, M., Kim, J.-S., Lee, J. (2011). Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing — the RGA paper.
2. Weiss, S., Urso, P., Molli, P. (2009). Logoot: A scalable optimistic replication algorithm for collaborative editing on P2P networks. ICDCS — the Logoot paper.
3. Nicolaescu, P., Jahns, K., Derntl, M., Klamma, R. (2016). Near real-time peer-to-peer shared editing on extensible data types. GROUP '16 — the YATA paper.
4. Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M. (2011). Conflict-free replicated data types. SSS — the foundational CRDT framework paper.
5. Kleppmann, M., Beresford, A. (2017). A conflict-free replicated JSON datatype. IEEE TPDS — Automerge's underlying algorithm.
6. Kleppmann, M. (2020). A highly-available move operation for replicated trees. — extends sequence CRDTs to move ops.
7. Yjs documentation — production YATA implementation.
8. /wiki/lww-registers-and-their-gotchas — why per-character LWW does not work for collaborative text.