Yjs Internals: Origins, YATA and State Vectors

This is Part 2 of a two-part series. Start with Part 1: No Effect Before Its Cause

Part 2 of a very long free weekend

Welcome back. In Part 1: No Effect Before Its Cause, I spent a perfectly good free weekend chasing Einstein’s trains, Lamport’s arrows and a 2,500-year-old Buddhist idea, all to learn one thing: two edits are concurrent when neither knew about the other, no matter what the clock said. This part is about how Yjs turns that idea into actual code.

If you landed here straight from a search, here’s the 20-second version. Alice and Bob are editing the same sentence: “The car is “. Alice types “fast” at the end. Bob is offline in a train tunnel and types “slow” in the same spot. Neither saw the other’s edit, so the two edits are concurrent. When Bob reconnects, both screens must end up with exactly the same text, nothing can be lost, and nobody is allowed to trust a clock.

So how does Yjs pull that off? Let’s see.

Yjs: every edit carries its own light cone

Here’s the genius move. Yjs never records when an edit happened. It doesn’t trust clocks. It has been hurt before. Instead, every piece of inserted text records what its author could see at the moment it was typed. That record is a tiny, portable light cone.

Every insert becomes an Item with three important fields:

• ID = (clientID, clock). Every Y.Doc gets a random clientID, basically its own worldline. Each client counts its own inserted characters with clock. Despite the name, this is not a clock. It's a counter wearing a clock costume, and it's never compared across clients to decide who came first.
• origin is the ID of the character immediately to the left when you typed.
• rightOrigin is the ID of the character immediately to the right when you typed.

import * as Y from 'yjs'
//
const doc = new Y.Doc()
const text = doc.getText('body')
//
text.insert(0, 'The car is ')
// Item { id: {client: 1842, clock: 0},
//        origin: null, rightOrigin: null,
//        content: 'The car is ' }     // clocks 0 to 10
//
text.insert(11, 'fast')
// Item { id: {client: 1842, clock: 11},
//        origin: {client: 1842, clock: 10},  // the space before it
//        rightOrigin: null,                  // nothing after it
//        content: 'fast' }

And here’s the bonus: Yjs spots concurrent edits for free. In the cart example from Part 1, every write had to carry extra version data, just so the database could tell if two writes were concurrent. Yjs doesn’t need that. Every character already stores its origin, the neighbour on its left at the moment it was typed, because it needs that to know where to sit. That field also happens to record what the author could see. So the check is already built in.

Take Alice and Bob. The text is “The car is “, and its last character has the ID 1842:10. Alice types “fast” right after it.

• If Bob had seen “fast”: he would type after it, so his origin would be the last letter of “fast” (1842:14). That is different from Alice’s origin, so his edit simply comes after hers. No conflict.
• If Bob had not seen “fast”: he types in the same gap, so his origin is the same 1842:10. Same origin means he could not have seen her text, so the two edits are concurrent.

No extra data, no comparing version numbers. Yjs only looked at the origin it was already storing. Zero clocks were consulted. Zero clocks were harmed.

Resolving concurrent inserts: YATA

Physics says events in each other’s elsewhere have no true order. Very deep. Very zen. Completely useless for a text editor, because the characters have to go somewhere. You can’t ship a product where the sentence says “The car is [quantum superposition]”.

So Yjs does the most engineer thing possible: it picks one arbitrary reference frame and makes every replica swear loyalty to it.

The algorithm is called YATA, short for “Yet Another Transformation Approach”. Yes, that is the real name. Researchers name things like tired parents naming their fifth kid. It was published by Nicolaescu, Jahns, Derntl and Klamma in 2016. Here’s what happens when Alice’s and Bob’s edits finally meet:

Shared state:  "The car is "   (last character has ID 1842:10)
--
Alice (client 1842) inserts "fast"
  origin = 1842:10, rightOrigin = null
--
Bob (client 7731), in the tunnel, inserts "slow"
  origin = 1842:10, rightOrigin = null
--
Same origins, neither saw the other  =>  concurrent (each in the other's elsewhere)

When a replica integrates an incoming item, it looks at the other items already squatting in the same gap. It compares their origins, and if those tie, it falls back to comparing client IDs. Client IDs say nothing about time, and that’s the whole point. They’re a fixed, boring, shared convention, like everyone agreeing to describe events from the platform’s point of view and telling the guy on the train to sit down.

Both items point back to the same origin, which is how Yjs knows they’re concurrent. Then the client ID settles it, identically on every replica, like a coin toss where the coin is rigged but at least everyone uses the same coin.

The final result is “The car is fastslow”, on every replica, in whatever order the updates arrive. Is it a good sentence? No. It’s terrible. But nothing was lost. Alice and Bob will see it, sigh, and fix it themselves. That’s the honest deal: the software can’t read their minds, but it promises never to secretly delete one of them. Which is more than I can say for some group chats.

Why your words don’t come out as alphabet soup

A lazy rule like “just sort concurrent characters by ID” could interleave them into “fsalsotw”, which sounds like a Swedish furniture brand. YATA avoids this because each character’s origin is the character typed right before it. Alice’s “a” has origin “f”, not the space. Once the first letters are sorted out, each word follows its own first letter like ducklings, and the words stay whole.

Guarantees so strong they’re basically physics

Because integration depends only on IDs and origins, applying updates is:

• Commutative: Alice-then-Bob and Bob-then-Alice give the same document. Order doesn’t matter.
• Idempotent: receiving the same update twice changes nothing. Yjs does not get excited twice about the same news.
• Associative: updates can be merged in any grouping, which is why Y.mergeUpdates works without even loading a document.

Together, these mean the result depends on what happened, not on the route the information took. That’s why Yjs works over WebSockets, WebRTC, a database column, or a USB stick handed over in a dark parking lot. (Please don’t do that last one. Or do. I’m not your manager.)

State vectors: your replica’s entire life story in a few bytes

An item’s origins describe one edit’s light cone. A state vector describes an entire replica’s: everything it has ever seen, from every worldline. It’s like a “seen” receipt for the whole document.

It’s a map from clientID to the next clock expected from that client. Since each client’s items form an unbroken run of numbers, “I’ve seen everything from client 1842 up to clock 15” fits in a single number. This is the classic version vector, on a strict diet.

// Decoded for readability; the real encoding is binary
Y.encodeStateVector(aliceDoc)  // { 1842: 15 }
Y.encodeStateVector(bobDoc)    // { 1842: 11, 7731: 4 }

Reading these is like two friends comparing which episodes they’ve watched:

• Alice has seen 1842’s clocks 11 to 14 (“fast”). Bob hasn’t. No spoilers yet.
• Bob has seen all of 7731’s clocks (“slow”). Alice hasn’t.
• Neither vector contains the other, so each replica holds events from the other’s elsewhere. Classic.

The handshake: “what have you seen?” “you first”

When Bob crawls out of the tunnel, the y-protocols/sync protocol has the two sides swap notes, then send only what's missing:

1. SyncStep1: each side sends its state vector. (“Here’s what I’ve seen.”)
2. SyncStep2: each side replies with Y.encodeStateAsUpdate(doc, remoteStateVector), which contains only what the other side hasn't seen. ("Here's what you missed, you absolute caveman.")
3. Update: from then on, every local change gets broadcast as it happens.

// Server, on a new connection
const diff = Y.encodeStateAsUpdate(serverDoc, clientStateVector)
send(client, diff)                 // SyncStep2

// Client
Y.applyUpdate(clientDoc, diff)     // arrival order and duplicates don't matter

Deletes are the awkward exception

Deleting text doesn’t create a new item, so it doesn’t bump any clock, so the state vector has no idea it happened. Yjs handles this with a separate delete set: compressed ranges of (clientID, clock, length) marking items as deleted. Every update carries its full delete set, and merging two delete sets is a simple union. The catch: if your users delete a lot (we all have that one coworker who rewrites everything), the delete set gets chunkier on every sync.

No effect before its cause (Pratītyasamutpāda)

In our universe you never see a glass shatter before it falls. Buddhism has a name for this idea: Pratītyasamutpāda, or dependent origination. Nothing arises on its own, it only arises because of the conditions before it. Yjs enforces the same rule. If an update shows up before the updates it depends on, Yjs doesn’t panic. It puts it in a waiting room and applies it the moment its cause walks in.

The waiting room is doc.store.pendingStructs (plus pendingDs for deletes aimed at items it hasn't met yet). The network can deliver messages in any random order it likes, and the document still never shows an effect without its cause.

const a = new Y.Doc(), b = new Y.Doc()
const updates: Uint8Array[] = []
a.on('update', u => updates.push(u))
//
a.getText('t').insert(0, 'Hello')     // update 0
a.getText('t').insert(5, ' world')    // update 1, its origin lives in update 0
//
Y.applyUpdate(b, updates[1])          // the effect arrives first: parked
b.getText('t').toString()             // '' (patiently waiting)
Y.applyUpdate(b, updates[0])          // the cause arrives: both integrate
b.getText('t').toString()             // 'Hello world'

Offline is just a really slow speed of light

To Yjs, Bob’s tunnel is nothing special. A laptop that’s offline for three hours looks exactly like a message that got stuck in traffic for three hours. Bob’s edits carry their origins, his state vector remembers what he saw, and when he reconnects, the handshake trades whatever each side is missing. Every edit he made is concurrent with every remote edit he hadn’t received, and YATA sorts them like any others.

This is the ragged light cone in real life. Hours apart on the clock, yet concurrent, because no information could flow between them. Einstein would be proud. Or confused. Probably both.

The laws of this universe, for people who actually have to ship it

Once you see Yjs as a tiny relativistic universe, a bunch of production “wait, WHAT?” moments suddenly make sense.

There is no “latest” in a Y.Map

Two users call map.set('status', ...) at the same time. Who wins? Not the person who clicked last. The same integration rule decides, so the tie breaks on client ID, not wall time. It's deterministic, but it has nothing to do with who was actually faster. If your product manager insists that "the most recent click wins", you'll have to build that yourself, for example by storing a timestamp inside the value, and then accept that clock skew is now your problem. Good luck.

You cannot erase the past

A deleted character can’t just vanish, because some edit still floating around in someone’s elsewhere might be using it as an origin. So Yjs keeps the item’s ID and position as a tombstone and, with garbage collection on (gc: true, the default), throws away only its content. The document structure still grows with every edit ever made, like the photo gallery on your phone. Only turn GC off (gc: false) if you need snapshots or version history, and prepare for chunkier documents.

Every worldline must be unique

The pair (clientID, clock) only works as an identity if every live session owns its own clientID. If you save a clientID and reuse it in two tabs or two server processes, you get two different items with the same ID. That’s two particles claiming to be the same particle. Physics breaks. Your document can corrupt. Your weekend is gone. Just let each Y.Doc generate its own.

Undo is not time travel

Y.UndoManager does not rewind history. Nothing rewinds history; we've been over this. It creates new edits that cancel out your earlier ones, scoped to tracked origins so you only undo your own mess, not your coworker's. Those new edits land in your future and merge with everyone else's edits by the same rules as always.

Store events, not snapshots of “now”

Because updates commute and are idempotent, a server can just append raw updates as they arrive and squash them later with Y.mergeUpdates, without even loading the document. Just never let a server timestamp pretend to be the source of truth for ordering. It's not. It's a train passenger with opinions.

CREATE TABLE doc_updates (
  doc_id     uuid        NOT NULL,
  seq        bigserial   PRIMARY KEY,
  payload    bytea       NOT NULL,
  created_at timestamptz NOT NULL DEFAULT now()
);
CREATE INDEX doc_updates_doc_seq ON doc_updates (doc_id, seq);
-- created_at is the server's own frame of reference.
-- Use it for retention and debugging. Yjs ignores it for ordering, and so should you.

The maestro behind all this

Time for a confession inside the confession. My free afternoon didn’t come from nowhere. It was inspired by real code.

My colleague Tharaka Ariyarathna built a Notion-style collaborative editor on Yjs, where a bunch of people edit the same pages at once and every replica has to end up with exactly the same document.

Watching his editor work is what dragged me from “how do I use this library?” to “why the hell does this work at all?”, and from there straight into Lamport, Einstein, and way too many trains. Everything in this article, from origins to state vectors to tombstones, is stuff a system like his has to get right for real, not just on a whiteboard with a nice marker.

If you want to say hi to the maestro behind it, or you’d like to work with him, you can find Tharaka on LinkedIn.

Further reading

• Part 1: No Effect Before Its Cause, for the physics, the trains, and the Dynamo shopping cart.
• Nicolaescu, Jahns, Derntl and Klamma, “Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types” (GROUP 2016), the YATA paper.
• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 5, “Detecting Concurrent Writes”.
• Yjs documentation and the Yjs source on GitHub.