Build Your Own CRDT

Jun 23, 2026 · 9 min read

reviously I'd described an envelope format for CRDT ops https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222 however this left the actual ops undefined.

Thanks to @hyl.st for sharing out that document. So without further ado here's a take on the actual operations.

[
    {
        "$type": "local.crdt.ops#set",
        "opId": "c1",
        "target": "ROOT",
        "value": {
            "$type": "app.bsky.feed.post",
            "langs": ["en"],
            "createdAt": "2026-06-21T22:04:19.568Z"
        }
    },
    {
        "$type": "local.crdt.ops#insert", 
        "opId": "c2",
        "target": "text",
        "anchor": "BEGIN",
        "value": "@chris.pardy.family "
    },
    {
        "$type": "local.crdt.ops#assign",
        "opId": "c3",
        "target": "ROOT",
        "previousOpIds": ["c1","c2"],
        "value": {
            "text": { "$ref": "text" }
        }
    },
    {
        "$type": "local.crdt.ops#add",
        "opId": "c4",
        "previousOpIds": ["c2"],
        "target": "facets",
        "value": {
            "$type": "app.bsky.richtext.facet",
            "index": {
              "byteEnd": { "$idx": { "target": "text", "id": "c2", "idx": 18}},
              "byteStart": { "$idx": { "target": "text", "id": "c2", "idx": 0}}
            },
            "features": [
              {
                "did": "did:plc:dp7v5b5kejmmzzpwmqyf5wj6",
                "$type": "app.bsky.richtext.facet#mention"
              }
            ]
          }
    },
    {
        "$type": "local.crdt.ops#assign",
        "opId": "c5",
        "previousOpIds": ["c1", "c4"],
        "target": "ROOT",
        "value": { "facets": { "$ref": "facets" } }
    },
    {
        "$type": "local.crdt.ops#insert",
        "opId": "c6",
        "previousOpIds": ["c2"],
        "target": "text",
        "anchor": "c2.19",
        "value": "wrote some thoughts on using CRDTs in atproto: "
    },
    {
        "$type": "local.crdt.ops#insert",
        "opId": "c7",
        "previousOpIds": ["c6"],
        "target": "text",
        "anchor": "c6.46",
        "value": "leaflet.pub/p/did:plc:dp..."
    },
    {
        "$type": "local.crdt.ops#add", 
        "opId": "c8",
        "previousOpIds": ["c7"],
        "target": "facets",
        "value": {
            "index": {
              "byteEnd": { "$idx": { "target": "text", "id": "c7", "idx": 26}},
              "byteStart": { "$idx": { "target": "text", "id": "c7", "idx": 0}}
            },
            "features": [
              {
                "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
                "$type": "app.bsky.richtext.facet#link"
              }
            ]
          }
    },
    {
        "$type": "local.crdt.ops#set", 
        "opId": "c9",
        "previousOpIds": ["c7"],
        "target": "embed",
        "value": {
            "$type": "app.bsky.embed.external",
            "external": {
              "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
              "thumb": {
                "ref": {
                  "$link": "bafkreifqtyzu2zamy7267fhluzfwyqdkgnzs4qyfnegpmgpulv4geobyy4"
                },
                "size": 344619,
                "$type": "blob",
                "mimeType": "image/jpeg"
              },
              "title": "CRDT's on ATProto",
              "description": ""
            }
          }
    },
    {
        "$type": "local.crdt.ops#assign",
        "opId": "c10",
        "previousOpIds": ["c1", "c9"],
        "target": "ROOT",
        "value": { "embed": { "$ref": "embed" } }
    },
    {
        "$type": "local.crdt.ops#insert",
        "opId": "c11",
        "previousOpIds": ["c7"],
        "target": "text",
        "anchor": "c7.26",
        "value": "\n\nHe's looking for feedback and thoughts, I'm formulating my own, but I think it's an excellent start!"
    }
  ]

We can apply a reducer function over the op log to produce the following document:

[
  {
    "$type": "local.crdt.document#value",
    "id": "ROOT",
    "value": {
      "$type": "app.bsky.feed.post",
      "text": { "$ref": "text" },
      "embed": { "$ref": "embed" },
      "langs": ["en"],
      "facets": { "$ref": "facets" },
      "createdAt": "2026-06-21T22:04:19.568Z"
    },
    "lastOpId": "c10"
  },
  {
    "$type": "local.crdt.document#sequence",
    "id": "text",
    "seq": [
      {
        "$type": "local.crdt.document#seqValues",
        "id": "c2",
        "startIdx": 0,
        "values": "@chris.pardy.family "
      },
      {
        "$type": "local.crdt.document#seqValues",
        "id": "c6",
        "startIdx": 0,
        "values": "wrote some thoughts on using CRDTs in atproto: "
      },
      {
        "$type": "local.crdt.document#seqValues",
        "id": "c7",
        "startIdx": 0,
        "values": "leaflet.pub/p/did:plc:dp..."
      },
      {
        "$type": "local.crdt.document#seqValues",
        "id": "c11",
        "startIdx": 0,
        "values": "\n\nHe's looking for feedback and thoughts, I'm formulating my own, but I think it's an excellent start!"
      }
    ],
    "lastOpId": "c11"
  },
  {
    "$type": "local.crdt.document#set",
    "id": "facets",
    "set": {
      "c4": {
          "$type": "app.bsky.richtext.facet",
          "index": {
            "byteEnd": { "$idx": { "target": "text", "id": "c2", "idx": 18, "after": true}},
            "byteStart": { "$idx": { "target": "text", "id": "c2", "idx": 0}}
          },
          "features": [
            {
              "did": "did:plc:dp7v5b5kejmmzzpwmqyf5wj6",
              "$type": "app.bsky.richtext.facet#mention"
            }
          ]
        },
        "c8": {
          "index": {
            "byteEnd": { "$idx": { "target": "text", "id": "c7", "idx": 26, "after": true}},
            "byteStart": { "$idx": { "target": "text", "id": "c7", "idx": 0}}
          },
          "features": [
            {
              "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
              "$type": "app.bsky.richtext.facet#link"
            }
          ]
        }
    },
    "lastOpId": "c8"
  },
  {
    "$type": "local.crdt.document#value",
    "id": "embed",
    "value": {
      "$type": "app.bsky.embed.external",
      "external": {
        "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
        "thumb": {
          "ref": {
            "$link": "bafkreifqtyzu2zamy7267fhluzfwyqdkgnzs4qyfnegpmgpulv4geobyy4"
          },
          "size": 344619,
          "$type": "blob",
          "mimeType": "image/jpeg"
        },
        "title": "CRDT's on ATProto",
        "description": ""
      }
    },
    "lastOpId": "c9"
  }
]

And then finally a materializer function over the document to produce

{
    "$type": "app.bsky.feed.post",
    "text": "@chris.pardy.family wrote some thoughts on using CRDTs in atproto: leaflet.pub/p/did:plc:dp...\n\nHe's looking for feedback and thoughts, I'm formulating my own, but I think it's an excellent start!",
    "embed": {
      "$type": "app.bsky.embed.external",
      "external": {
        "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
        "thumb": {
          "ref": {
            "$link": "bafkreifqtyzu2zamy7267fhluzfwyqdkgnzs4qyfnegpmgpulv4geobyy4"
          },
          "size": 344619,
          "$type": "blob",
          "mimeType": "image/jpeg"
        },
        "title": "CRDT's on ATProto",
        "description": ""
      }
    },
    "langs": [
      "en"
    ],
    "facets": [
      {
        "$type": "app.bsky.richtext.facet",
        "index": {
          "byteEnd": 19,
          "byteStart": 0
        },
        "features": [
          {
            "did": "did:plc:dp7v5b5kejmmzzpwmqyf5wj6",
            "$type": "app.bsky.richtext.facet#mention"
          }
        ]
      },
      {
        "index": {
          "byteEnd": 94,
          "byteStart": 67
        },
        "features": [
          {
            "uri": "https://leaflet.pub/p/did:plc:dp7v5b5kejmmzzpwmqyf5wj6/3motaq6j3g222",
            "$type": "app.bsky.richtext.facet#link"
          }
        ]
      }
    ],
    "createdAt": "2026-06-21T22:04:19.568Z"
  }

Here's the tangled repo with the POC for this:

https://tangled.org/chris.pardy.family/crdt

Breaking it Down

Having played with CRDTs a bunch one of the realizations I've had is that they work better when you can work on small targets – the simplest operation for a CRDT is Last Write Wins (LWW) which gets you really far if the targets that you're apply your LWW operation to are generally data that changes together.

You can see in the document view above we've broken the json object down into component parts linked from the root with refs. We could use paths instead of breaking into component parts like this but we want stable ids that make it easy to move items around. In a block based document like a leaflet post this lets us move text between blocks without losing edits to the text.

Every document has a special part called ROOT which starts off as an empty object. When materializing the final result we start from ROOT and work our way through refs. Each operation defines a target - if that target exists in our current doc we modify it, if it doesn't exist we create it.

Simple Ops: Set, Assign, Incr

We start with three really simple operations, set - LWW, assign - shallow merge, and incr - integer increment

These are likely simple enough to not require explanation but what is notable is that we define rules for what happens when they're applied after each other in different sequences. You can see in the example above that we start with a set on the ROOT target and subsequently use assign operations to specify single properties that are appended.

Sets

Sets are built on the Observed Remove or OR Set concept. Add operations add items to the set assigning them a unique id - either the unique id of the operation that added them or a supplied id. Remove operations target 1 or more previous adds via their id.

Sets like this have a few emergent properties:

If an item has a meaningful identity (such as the target of a ref) then two ops adding the same item with the same identity produce a LWW set operation on that id
Multiple deletes of the same item are idempotent.
You can "re-add" an item by ensuring that it's sequenced after a known delete

Sets provide for an unordered collection of elements they're generally easier to reason about than the ordered collections we'll talk about next so if it's possible for data to be unordered you should encode it in a set.

Sequences

Sequences are built from a Replicated Growable Array or RGA. These encode runs of values and deletion tombstones. Because tombstones exist for all values that have been deleted you can insert data into sections of the sequence that have been deleted concurrently.

We define two operations for RGA - insert and delete. Our insert operation defines an anchor point and an insert side (before or after - the default). When we apply our RGA insert it will add a new value run to the rga document, it may split existing delete or value runs to do this. What makes RGA work is that every item in the sequence is given a unique id, we encode these as <opId>.<index> so in the example above c2.2 would refer to the character "h" in our text.

RGA inserts can either include data as an array or a string. This allows us to generate arbitrary order dependent arrays.

Deleting from an RGA sequence is specified by supplying a start and end (inclusive) range of ids. These are expanded by iterating through the range numerically, not based on the document. We'll get more into an example of what that means. Deletion writes a tombstone run allowing subsequent deletion or insertion ops to anchor content on deleted elements.

Sorting

We've got a number of operations that are sequence dependent, such as LWW. How do we establish time in a distributed system like this.

Firstly each operation is given a globally unique op id.

Secondly each operation can define 1 or more operationIds that proceed it. A sequencer sorts all the ops with the following rules.

If there are no previous op ids then ops are placed in bucket 0
If there are previous op ids then an op is placed in bucket MAX(previous op buckets) + 1
Within each bucket ops are sorted by op id lexicographically

When declaring previous ops we generally pick ones that we depend on, although simply choosing the most recent op id for a whole document is also viable. If you look in the above example the ops to modify the root document list the op that did the initial set as well as the op that created the target we're adding a reference to as the previous ops.

$ref and $idx

There are two special types that are handled by materialization

$ref is resolved as a reference to a specific target, this is used to turn a list of sections into a single json document

$idx is resolved as the "index" into a rga sequence. It's useful for things like facets and transforms the stable anchor points into byte or element indexes.

Making Moves

One of the goals of this CRDT is to make it easy to move content, this also covers things like symlinks and renames. By storing a document as a series of sections that are referenced by each other we can implement a move by simply writing a new reference to the existing section and deleting the old reference.

Markdown

Now we come to the real sticking point of most crdts - Markdown

With Markdown (and other markup languages) our marks are inline with our content. This is different than the facets that are used by systems like Bluesky's posts.

Let's start with a simple statement:

This is an important statement

I want to emphasize how important it is:

This is an **important** statement

Someone else has another idea though - they delete some of the text:

This is an import

If we deleted items from the RGA using a range over the realized text we would have:

This is an **import

Our approach takes the tact of only deleting explicitly enumerated items which produces the following:

This is an **import**

This approach isn't without it's downsides let's say we make a typo:

Here's some texp with a typo

In parallel we have two edits:

Here's some examples

Here's some text with a typo

the result will be:

Here's some examples t

What's next

There's still a lot to do - namely we need to actually wire this CRDT into editors, figure out the how to assign op ids. As well as sort out a million edge cases. However as a line in the sand this is an open source crdt implementation, with test cases that can be used for any programming language, that allows you to collaboratively produce any valid atproto record, that makes this the first part in what could be a standard for collaborative editing of blogs, posts, etc.

Did you enjoy this article?

Recommend it — Standard Reader surfaces well-loved writing to more readers across the network.