Ryan Ziegler

A brief introduction to CRDTs and YATA

CRDTs are data structures which may be replicated across multiple clients, and which do not require a central server to mediate concurrent edits. They allow clients to make edits without a network connection and still eventually arrive at the same end result.

This simplifies collaborative editing applications even when we do have a server: the server is just implemented as another client, which never makes edits.

Operation-based CRDTs

In this post, we'll focus on operation-based CRDTs. Changes to an operation-based CRDT are expressed using a CRDT-specific set of operations. As a hypothetical example, the list of operations to write a string "hello" might be:

  1. insert(h)
  2. insert(e)
  3. insert(l)
  4. insert(l)
  5. insert(o)

Operations must be commutative and associative to ensure the order in which they are applied does not matter. As such, after applying the same set of operations in arbitrary order, two clients will always see the same result.

Based on this requirement, what's wrong with insert(character) as an operation? It is not commutative. If one client receives insert(o);insert(n) they end up with "on," while a client who receives insert(n);insert(o) ends up with "no."

Some trivial operation-based CRDTs

A single integer N which starts out as 0, with operation add(X) is an operation-based CRDT since addition is both commutative and associative.

Consider a single boolean B which starts out false, and may only be set to true. There is exactly one operation, setTrue. This is an operation-based CRDT: setTrue is trivially associative and commutative. We'll call this CRDT "Flag" and use it later.

Yjs and YATA

Yjs is arguably the most well-known collaborative editing library in the JS ecosystem, and through the Yrs Rust port and associated bindings has robust cross-language compatibility. It introduced the YATA (Yet Another Transformation Approach) CRDT, which is an operation-based CRDT for sequences.

The YATA CRDT

A YATA stores a list of operations, with sentinel nodes at the start and end.

startendoperations...

Operations are tuples (left_op_id, right_op_id, id, content), where id is a globally unique identifier. We track both left_op_id and right_op_id as a proxy for intent: users expect characters to be inserted at the location of their cursor, which we may uniquely determine by what's to the left and the right of it. It would be a strange experience if characcters you typed appeared arbitrarily after your cursor!

startendyata(start, end, 0, y)(0, end, 1, a)(1, end, 2, t)(2, end, 3, t)

Handling conflicts

attata(1, 2, 5, t)(5, 2, 6, a)(6, 2, 7, t)(7, 2, 8, t)(0, end, 1, a)(1, end, 2, t)atz(1, 2, 9, z)(0, end, 1, a)AliceBob

Alice and Bob have made conflicting edits. Alice edited the string to say Yatatata and Bob edited the string to say Yazta. We'd like them to arrive at the same string after applying the other's operations while preserving intent. To do so, we may find an ordering for the conflicting operations which is the the same for both Alice and Bob. This is sufficient for commutativity: after seeing the same set of operations, Alice and Bob can sort according to this order and get the same result.

How can we order conflicting operations consistently between Alice and Bob? Recall that operations are defined as (id, left_op_id, right_op_id, content), and only id is guaranteed to be unique. And, Alice and Bob see the same operation ids, so ordering by id is consistent between them.
How can we guarantee that one user's changes always appear before another's? We need to track user IDs associated with each operation, and order operations by inserting user ID instead of operation ID. The inserting user ID is still unique, and seen by both Alice and Bob. This isn't strictly required for our CRDT, but provides a more consistent user experience.

Handling deletion

We cannot remove operations from a YATA straightaway: while Alice removes an operation, Bob may insert using a reference to that operation. Deletion for an operation O thus proceeds in two phases:

  1. Tombstoning: Make sure every editor knows the operation is deleted. An editor should never reference deleted operations in their insert operations.
  2. Garbage collection: Once noone is making edits referencing O, it can be safely removed from everyone's YATA

To implement the tombstoning phase, we store a flag is_deleted with each operation. Recall that this itself is a CRDT. How we determine that every editor has received the new value is out of scope for this post, so we'll treat that as a black box and assume it just happens by magic.

Garbage collection is typically implemented periodically on each client, and is not particularly interesting: just remove any operations for which is_deleted == true and everyone else has received this value.

Beyond sequences

A YATA is just a sequence CRDT, but Yjs supports other structures, like trees and replaceables. We can express such structures using only sequence CRDTs, YATA or otherwise.

Trees

A tree is represented by a YATA whose elements contain other YATAs.

startendn1n2n3n4startendn1n2
Do internal (non-leaf) YATAs need a consistent operation order for operations to be commutative? No! The order of children in a tree does not matter. Thus, if Alice inserts nodes in the reverse of Bob's order, they still have the same tree.

Replaceable content

Sometimes, keeping both Alice and Bob's changes doesn't make sense: consider concurrently selecting an option from a dropdown. We can't coherently merge "United States" and "Greenland," we just need to pick one and make sure all clients agree on what we picked.

Recall that a sequence CRDT ensures everyone will eventually agree on the content at any index i. To represent replaceable content, we'll pick index 0 to hold the current value. Users change the value by inserting a new item at index 0.

startendabcurrent value
Why shouldn't we use a nonzero index to hold the current value? This is partially a trick question. Using the last element of the sequence, and changing the value via append is symmetric to our index 0 and prepend approach. Any index in between requires storing at least one always-unused element, though, and should be avoided.

Conclusion

This post was a very high level, intuition-focused introduction to the YATA CRDT. I've swept some details and formality under the rug to hopefully make things easier to understand; I highly recommend the original YATA paper for more details.