Have you heard about CRDTs and wondered what they are? Maybe you’ve looked into them a bit, but ran into a wall of academic papers and math jargon? That was me before I started my Recurse CenterThe Recurse CenterThe Recurse Center is a self-directed, community-driven educational retreat for programmers in New York City.www.recurse.com/ batch. But I’ve spent the past month or so doing research and writing code, and it turns out that you can build a lot with just a few simple things!

In this two-part series, we’ll learn what a CRDT is. Then we’ll write a primitive CRDT, compose it into more complex data structures, and finally use what we’ve learned to build a collaborative pixel art editor. All of this assumes no prior knowledge about CRDTs, and only a rudimentary knowledge of TypeScript.

To pique your curiosity, this is what we’ll end up with:

Draw by clicking and dragging with your mouse. Change the paint color by using the color input on the bottom left. You can draw on either canvas and your changes will show up on the other, as if they were collaborating on the same picture.

Clicking the network button prevents changes from reaching the other canvas (although they’ll sync up again when they come back “online”). The latency slider adds a delay before changes on one canvas show up on the other.

We’ll build that in the next post. First, we need to learn about CRDTs!

What is a CRDT?

Okay, let’s start from the top. CRDT stands for “Conflict-free Replicated Data Type”. That’s a long acronym, but the concept isn’t too complicated. It’s a kind of data structure that can be stored on different computers (peers). Each peer can update its own state instantly, without a network request to check with other peers. Peers may have different states at different points in time, but are guaranteed to eventually converge on a single agreed-upon state. That makes CRDTs great for building rich collaborative apps, like Google Docs and Figma — without requiring a central server to sync changes.

Broadly, there are two kinds of CRDTs: state-based and operation-based.¹ State-based CRDTs transmit their full state between peers, and a new state is obtained by merging all the states together. Operation-based CRDTs transmit only the actions that users take, which can be used to calculate a new state.

That might make operation-based CRDTs sound way better. For example, if a user updates one item in a list, an operation-based CRDT can send a description of only that update, while a state-based CRDT has to send the whole list! The drawback is that operation-based CRDTs impose constraints on the communication channel: messages must be delivered exactly once, in causal order, to each peer.²

This post will exclusively focus on on state-based CRDTs. For brevity, I’ll just say “CRDTs” from here on out, but know that I’m referring specifically to state-based CRDTs.

I’ve been talking about what CRDTs do, but what is a CRDT? Let’s make it concrete: a CRDT is any data structure that implements this interface:³

interface CRDT<T, S> {
  value: T;
  state: S;
  merge(state: S): void;
}

That is to say, a CRDT contains at least three things:

• A value, T. This is the part the rest of our program cares about. The entire point of the CRDT is to reliably sync the value between peers.
• A state, S. This is the metadata needed for peers to agree on the same value. To update other peers, the whole state is serialized and sent to them.
• A merge function. This is a function that takes some state (probably received from another peer) and merges it with the local state.

The merge function must satisfy three properties to ensure that all peers arrive at the same result (I’ll use the notation A ∨ B to indicate merging state A into state B):

• Commutativity: states can be merged in any order; A ∨ B = B ∨ A. If Alice and Bob exchange states, they can each merge the other’s state into their own and arrive at the same result.
• Associativity: when merging three (or more) states, it doesn’t matter which are merged first; (A ∨ B) ∨ C = A ∨ (B ∨ C). If Alice receives states from both Bob and Carol, she can merge them into her own state in any order and the result will be the same.⁴
• Idempotence: merging a state with itself doesn’t change the state; A ∨ A = A. If Alice merges her own state with itself, the result will be the same state she started with.

Mathematically proving that a merge function has all these properties might sound hard. But luckily, we don’t have to do that! Instead, we can just combine CRDTs that already exist, leaning on the fact that someone has proven these things for us.

Speaking of CRDTs that already exist: let’s learn about one!

Last Write Wins Register

A register is a CRDT that holds a single value. There are a couple kinds of registers, but the simplest is the Last Write Wins Register (or LWW Register).

LWW Registers, as the name suggests, simply overwrite their current value with the last value written. They determine which write occurred last using timestamps, represented here by integers that increment whenever the value is updated.⁵ Here’s the algorithm:

• If the received timestamp is less than the local timestamp, the register doesn’t change its state.
• If the received timestamp is greater than the local timestamp, the register overwrites its local value with the received value. It also stores the received timestamp and some sort of identifier unique to the peer that last wrote the value (the peer ID).
• Ties are broken by comparing the local peer ID to the peer ID in the received state.

Try it out with the playground below.

Did you get a sense for how LWW Registers work? Here are a couple specific scenarios to try:

• Turn the network off, make a bunch of updates to bob, and then turn it back on. When you send updates from alice, they’ll be rejected until the timestamp exceeds bob’s timestamp.
• Perform the same setup, but once you turn the network back on, send an update from bob to alice. Notice how the timestamps are now synced up and alice can write to bob again!
• Increase the latency and send an update from both peers simultaneously. alice will accept bob’s update, but bob will reject alice‘s. Since bob’s peer ID is greater, it breaks the timestamp tie.

Here’s the code for the LWW Register:

class LWWRegister<T> {
  readonly id: string;
  state: [peer: string, timestamp: number, value: T];

  get value() {
    return this.state[2];
  }

  constructor(id: string, state: [string, number, T]) {
    this.id = id;
    this.state = state;
  }

  set(value: T) {
    
    this.state = [this.id, this.state[1] + 1, value];
  }

  merge(state: [peer: string, timestamp: number, value: T]) {
    const [remotePeer, remoteTimestamp] = state;
    const [localPeer, localTimestamp] = this.state;

    
    if (localTimestamp > remoteTimestamp) return;

    
    if (localTimestamp === remoteTimestamp && localPeer > remotePeer) return;

    
    this.state = state;
  }
}

Let’s see how this stacks up to the CRDT interface:

• state is a tuple of the peer ID that last wrote to the register, the timestamp of the last write and the value stored in the register.
• value is simply the last element of the state tuple.
• merge is a method that implements the algorithm described above.

LWW Registers have one more method named set, which is called locally to set the register’s value. It also updates the local metadata, recording the local peer ID as the last writer and incrementing the local timestamp by one.

That’s it! Although it appears simple, the humble LWW Register is a powerful building block with which we can create actual applications.

Last Write Wins Map

Most programs involve more than one value,⁶ which means we’ll need a more complex CRDT than the LWW Register. The one we’ll learn about today is called the Last Write Wins Map (or LWW Map).

Let’s start by defining a couple types. First, our value type:

type Value<T> = {
  [key: string]: T;
};

If each individual map value holds type T, then the value of the entire LWW Map is a mapping of string keys t