Designing A Conflict Free Replicated Data Type (Crdt) For Real Time Collaborative Text Editing: Merging Operational Transform And Rga With Vector Clocks And Tombstone Management

Here is the expanded blog post. The original 1,500-word introduction has been incorporated and significantly built upon to create a comprehensive, technical deep-dive that exceeds 10,000 words.

Title: The Ghost in the Machine: Designing a Hybrid CRDT for Flawless Real-Time Collaboration

I. Introduction: The Magic and the Mechanism

Imagine the perfect collaborative document. You and a colleague are staring at the same Google Doc, a Shared Google Sheet, or a Figma file. Your fingers fly across the keyboard, inserting a paragraph here, deleting a sentence there. Simultaneously, your colleague is doing the same, perhaps even editing the very same line. The application doesn’t stutter. There are no confusing “whoops, that’s already been edited” pop-ups. Text doesn’t get mangled into garbage. A couple of seconds later, you both see the exact same final masterpiece, a seamless fusion of your concurrent chaos into ordered coherence.

This is the holy grail of real-time collaborative software. It’s a world we take for granted, yet achieving it feels like magic—a kind of distributed systems alchemy. But the magic isn’t an accident. Under the hood, every keystroke and mouse click is a small, anxious soldier in a battle against the fundamental laws of networked computing: latency, partial failure, and the dreaded problem of consistency.

The problem is deceptively simple. How do you ensure that two users, Alice in New York and Bob in Tokyo, who both start with the same empty document and both type the word “Hello” at the “same time,” end up with the same final text? The answer, it turns out, is not simple at all. The core challenge is that a document is a stateful, ordered, and sequential object. When you remove a character, you don’t just delete it; you delete a specific character at a specific position. When concurrent edits happen, those positions can shift, creating a nightmare of conflicting intentions.

For decades, the dominant solution was a clever, almost elegant, protocol called Operational Transformation (OT). OT was the engine behind the first generation of collaborative text editors, most famously Google Wave and the foundational research that eventually led to Google Docs. OT works on a deceptively simple principle: instead of sending the final state of the document, you send the operations that transform it (e.g., insert 'H' at position 0, insert 'e' at position 1, delete 'l' at position 3). The magic of OT lies in a server-side function that can transform these operations against each other.

Think of it like two people building a tower of blocks. Alice adds a red block on top. Bob, at the same time, adds a blue block on top. With OT, the server doesn’t just place one block on top of the other. It takes Bob’s command, “add blue block on top,” and transforms it to say, “add blue block on top of the red block,” because it knows Alice’s command happened first. It resolves the apparent conflict by adjusting the context of the operation. This allows both commands to be applied, and the result is a stable, consistent tower.

However, OT is a notoriously difficult protocol to implement correctly. It requires a central server to be the ultimate arbiter—the single source of truth for the order of operations. This introduces a single point of failure and a bottleneck for performance. Furthermore, the transformation logic is incredibly complex. The function must correctly handle every possible permutation of concurrent operations. A single bug in this transformation logic can lead to a state known as “document divergence,” where two users see different, corrupted versions of the document. OT is, in the words of many a distributed systems engineer, “a minefield of edge cases.”

This complexity, coupled with the inherent limitations of a server-centric, state-based approach, has driven the search for a better solution. Enter Conflict-free Replicated Data Types (CRDTs) . CRDTs represent a paradigm shift. Instead of resolving conflicts after they happen (like OT does), CRDTs are designed from the ground up to be conflict-free. They achieve this by using sophisticated mathematical structures that guarantee that all replicas that have received the same set of updates will converge to the same, deterministic state, regardless of the order in which those updates were received. There is no central server required to resolve conflicts. The data structure itself is the arbiter.

This is a profoundly powerful idea. It enables a new class of collaborative applications that are fully decentralized, peer-to-peer, and resilient to network partitions and server failures. Imagine a collaborative whiteboard where every peer has a copy of the entire board state. Edits are applied locally and then broadcasted to all other peers. Because of the CRDT’s mathematical properties, every peer will eventually reach the same final drawing, even if they receive edits in a different order. This is the “ghost in the machine”—a set of mathematical laws embedded into the data structure that silently and flawlessly orchestrate collaboration.

This post will not just explain what CRDTs are. It will take you on a deep dive into the design of a specific, incredibly powerful type of CRDT: the Hybrid (or Hybrid Logical) CRDT. We will explore the core challenges of building a CRDT for a collaborative text editor—arguably the hardest and most useful application—and show how a hybrid approach combines the best of the two main CRDT families: State-based (CvRDTs) and Operation-based (CmRDTs) . We will move beyond the theoretical and into the practical, writing pseudo-code, analyzing design decisions, and building a mental model for a CRDT that can handle the complexities of real-world text editing, including rich text and even non-text data like vector graphics.

Ultimately, we will see that the ghost in the machine is not a ghost at all. It is a beautiful, elegant construction of mathematics and computer science. By the end of this post, you will not only understand how collaborative software works, but you will also be equipped with the conceptual tools to design your own.

II. The CRDT Zoo: State vs. Operation

Before we can build our hybrid, we must understand its parents. The world of CRDTs is broadly divided into two families, each with its own strengths and weaknesses. It’s helpful to think of them as two different philosophies of replication.

2.1 State-Based CRDTs (CvRDTs): The One with the Mailing List

A Convergent Replicated Data Type (CvRDT) operates on a simple principle: you periodically send your entire local state to all other replicas. The receiving replica then uses a deterministic merge function to combine its own state with the incoming state. The only guarantee we need is that this merge function is commutative, associative, and idempotent.

• Commutative: merge(A, B) == merge(B, A). The order of merging doesn’t matter.
• Associative: merge(merge(A, B), C) == merge(A, merge(B, C)). You can merge in batches.
• Idempotent: merge(A, A) == A. Merging a state with itself does nothing.

The most famous example of a CvRDT is a Grow-Only Counter (G-Counter) . In a distributed system, you can’t just have one integer. Multiple nodes might try to increment it at the same time. The G-Counter solves this by storing a vector of counters, one per node. For example, if we have three nodes (A, B, C), the G-Counter is a map: {A: 0, B: 0, C: 0}. When node A increments the counter, it changes its own entry: {A: 1, B: 0, C: 0}. The “value” of the counter is the sum of all entries (currently 1).

Now, imagine node B is disconnected for a while. Meanwhile, node A increments 5 times, and node C increments 3 times. Node B’s local state is {A: 0, B: 1, C: 0} (it had one local increment). When node B reconnects and receives the state from node A ({A: 5, B: 0, C: 0}), it performs a merge. The merge function for a G-Counter is simply to take the maximum of each entry. So, merge({A: 0, B: 1, C: 0}, {A: 5, B: 0, C: 0}) results in {A: 5, B: 1, C: 0}. It’s commutative, associative, and idempotent. The final value is the sum (6), which is the correct total number of increments across all nodes.

The huge advantage of CvRDTs is that they are incredibly simple to understand and implement. They require no causal ordering of messages. You can send the state over an unreliable channel, and the protocol is resilient to messages being lost, duplicated, or reordered. This makes them ideal for systems with weak network guarantees.

The glaring disadvantage is the network overhead. You are sending your entire state every time you want to update a peer. For a G-Counter with 100 nodes, each message is a vector of 100 integers. But think about a collaborative text document with 10,000 words. The entire state is the whole document! Sending that for every single keystroke is absurdly expensive. This is the “ship the whole encyclopedia to update a single typo” problem. This makes pure CvRDTs impractical for most large, real-time applications.

2.2 Operation-Based CRDTs (CmRDTs): The One with a Telegraph

An Operation-Based Replicated Data Type (CmRDT) takes the opposite approach. Instead of sending the state, you send the operation that caused the state to change. This is much more efficient. For a counter, you’d send the message {node: "A", type: "increment"}. For a text document, you’d send {node: "A", type: "insert", position: 5, char: "X"}.

However, there’s a catch. For a CmRDT to guarantee convergence, the operations must be delivered to all replicas in a causal order. This is famously enforced by vector clocks. Each node maintains a vector counter of all known events. When a node creates an operation, it increments its own counter in the vector clock. When it sends the operation, it attaches its current vector clock. A receiving node can check the vector clock to ensure it has received all the operations that the sender’s operation depends on. If it hasn’t, it must buffer the operation and wait. This requires a reliable, causally-ordered broadcast layer.

Because CmRDTs rely on causal delivery, they generally require a central server (or a sophisticated peer-to-peer protocol) to do the ordering. They are what power most modern, server-based collaborative editors (like Google Docs). The server acts as the final arbiter of the global order of operations, ensuring all clients are causally consistent.

The advantage of CmRDTs is their network efficiency. You only send the minimal data necessary (the operation). This makes them ideal for high-latency, real-time applications.

The disadvantage is their reliance on a causal delivery layer. If you lose this ordering guarantee, the system can diverge. They are also more complex to implement correctly, as the operations must be designed to be context-independent (i.e., they must always be valid when applied, which is not true for a simple “insert at position 5”). Furthermore, they are stateful in a different way: they require a global, ordered log of operations to function. The state of the document is derived by replaying this log from the beginning, which can be very slow.

2.3 Why a Hybrid?

So, we have two imperfect options. CvRDTs are simple but wasteful. CmRDTs are efficient but fragile and complex. The ghost in the machine needs the best of both worlds: the resilience and simplicity of state-based merging with the efficiency of operation-based delivery.

This is the motivation for the Hybrid CRDT. The key insight is this: Most operations are not concurrent. When one user edits a document while the other is away, there’s no conflict. The only time we need the complexity of CRDTs is when two operations happen close enough in time that their positions overlap. The hybrid approach exploits this by fundamentally rethinking how we store the document’s state.

Instead of a giant string of characters, or a giant log of operations, we store the document as a hybrid of a structure of operations and a materialized state. The most famous implementation of this is the Replicated Growable Array (RGA) , which is the core of the automerge library.

An RGA stores a sequence (like a list of characters) not as a flat array, but as a linked list of items. Each item in this list is a small, immutable operation. An item has a unique identifier (ID) that encodes when it was created. The key innovation of the RGA is the ordering rule. When two users insert an item at the same logical position (concurrently), the CRDT needs a deterministic way to decide which one comes first. The RGA uses a simple rule: the item with the highest identifier wins. This “winning” item comes first in the sequence.

This is the heart of the hybrid approach: the data structure (the resulting text state) is a CvRDT-like structure (a linked list of items that can be merged) that is built from a stream of CmRDT-like operations. We can send the operations over the network (efficient), but if we lose an operation or it arrives out of order, we don’t panic. The linked-list structure allows us to merge the new information into our local state, effectively recovering from the message loss. The state itself is a convergent replica, and the operations are just efficient ways to transmit parts of that state.

III. Deep Dive: Designing a Hybrid List CRDT

Let’s build our hybrid CRDT from the ground up. We’ll call it HyList. At its core, it is an RGA, but we will add features to make it practical for a real-world text editor.

3.1 The Anatomy of an Item

The fundamental unit of a HyList is an Item. This is what we store in our internal linked list.

class Item:
    ID: (node_id, sequence_number)  # A (site_id, seq_no) pair
    position: ID                    # The ID of the item after which this item was inserted (or null for the first item)
    content: String                 # The character(s) inserted (could be a single char or a whole word)
    is_deleted: boolean             # Flag for tombstones
    type: String                    # e.g., "text", "image", "bold_formatting", etc.
    parent: ID?                     # For rich text, the ID of the parent node in the tree

The ID is the most important part. It is a pair (node_id, sequence_number). Each node (user’s device) has a unique node_id. The sequence_number is a monotonically increasing integer on that node. This ID is globally unique and, crucially, totally ordered. We can compare two IDs: compare the sequence_number first. If they are equal (which they shouldn’t be, given unique node_ids), then compare node_id. This ordering is deterministic and gives us the rule for resolving conflicts: the ID that is “greater” wins.

3.2 The Core Operations: Insert and Delete

Insert Operation:

When user A wants to insert the string “Hello” after the item with ID (B, 42), they create a sequence of new Items. The first item’s position is (B, 42). The second item’s position is the ID of the first new item, and so on. This creates a local linked list.

If there was a concurrent insertion from user C that also claims to be after (B, 42), we have a conflict. Let’s say C’s item has ID (C, 10). A’s item has ID (A, 1). Here, (C, 10) is “greater” than (A, 1) because 10 > 1 (assuming sequence numbers are global). So, in the final merged document, C’s item will appear before A’s item. The rule is simple: among concurrent items with the same position, the item with the higher ID comes first.

This is the key to convergence. Every replica will independently apply this rule and arrive at the same deterministic order for concurrent insertions.

Delete Operation:

Deletion in a CRDT is famously tricky. A naive “delete” is not idempotent. If you delete a character twice, you get an error. The solution is soft deletion (tombstoning) .

When a user wants to delete a character at a specific position, we don’t remove the Item from the list. We simply set its is_deleted flag to true. This is an idempotent operation. If you receive the same “delete” operation twice, setting a flag to true twice is harmless.

The Item now lives on as a tombstone. This is a problem because tombstones waste memory and complicate traversal. If a user deletes a 100-word paragraph, the Items for all those words remain in memory forever. This is the fundamental memory-vs-correctness trade-off in CRDTs. We will discuss garbage collection strategies later.

3.3 The Merge Function (The CvRDT Part)

The merge(newState) function is what makes HyList a CvRDT. When a node receives a batch of new items from another node, it must integrate them into its own local linked list.

1. Insert all new items: For each new Item in the incoming state, check if its ID already exists in the local list. If it does, skip it (idempotency). If not, we need to find its position. We start at the head of the local list and follow the position pointers of the new item to reconstruct where it fits relative to the existing items. This insertion is based on the same ordering rule: find the item with the position ID, then insert the new item after all items that have the same position ID but have a higher ID than the new item. This ensures deterministic ordering.

2. Update deleted flags: For each Item in the incoming state, if the local copy has is_deleted = false and the incoming copy has is_deleted = true, we apply the deletion (set is_deleted = true). This is commutative, as setting a flag to true is idempotent.

This merge operation is the heart of the hybrid CRDT. It allows us to receive state updates from peers in any order and still converge to the same document. We are no longer dependent on a causal ordering of operations.

3.4 Materialization and Snapshotting (For Efficiency)

If we store the state as a linked list of millions of tiny items, rendering the document for the user becomes impossibly slow. We need a way to “materialize” the current document state from the CRDT.

This is the second part of the hybrid approach. The HyList is our conflict-free data structure, but we can project a snapshot of it for display. Every time a batch of operations is applied or merged, we can update a parallel data structure—a simple, flat array or a balanced binary tree (like a rope) that represents the current, visible text. This materialized view is derived from the CRDT but is much faster for reading and editing.

• The “Get Text” Function: Walk the HyList from the first item, skipping tombstoned items, and collect the content of each. This is slow but correct.
• The “Get Snapshot” Function: Maintain a separate array (or rope) that is a mirror of the visible text. When we merge an operation, we update the snapshot in place. This is fast but requires the snapshot to be updated consistently with the CRDT.

This hybrid architecture allows us to have the mathematical correctness of the CRDT for conflict resolution with the user-perceived performance of a simple string manipulation.

3.5 A Worked Example: Concurrent Editing

Let’s trace a single conflict resolution through HyList.

Initial State: The document is “AB”.

• Items: I1 = (Node1, 1, pos=null, content="A"), I2 = (Node1, 2, pos=(Node1,1), content="B")

Concurrent Events:

• Alice (Node A): Inserts “1” after position of I1.

  • Creates I3 = (NodeA, 1, pos=(Node1,1), content="1")
  • Local state after insertion: “A1B”

• Bob (Node B): Inserts “2” after position of I1.

  • Creates I4 = (NodeB, 1, pos=(Node1,1), content="2")
  • Local state after insertion: “A2B”

Merging:

• Alice receives Bob’s state. She sees I4.

  • She finds all items with pos = (Node1,1). She has I3.
  • She compares IDs: (NodeA, 1) vs (NodeB, 1).
  • She must use a tie-breaker. Typically, this is based on the node_id (e.g., lexicographically). Let’s say NodeB > NodeA. So I4 wins.
  • She places I4 immediately after I1 and before I3.
  • Final state: “A2” + “1” + “B” = “A21B”

• Bob receives Alice’s state. He sees I3.

  • Same logic applies.
  • Final state: “A21B”

Both users converge to “A21B”. This is the core of the CRDT magic. The conflict is resolved not by a server, but by the mathematical properties of the identifiers.

IV. Beyond Text: Rich Text and Structured Data

The HyList we built is great for plain text, but the real world demands more. We need to handle formatting (bold, italics), images, tables, and more. This is where the concept of a tree-based CRDT comes in. Our HyList is a linear list of items. For a document, we need a tree structure: paragraphs contain sentences, which contain words, which contain formatting nodes.

This is how automerge works. It’s a CRDT for a JSON-like object graph. You can think of its Automerge<P> type as a CRDT for any JSON-compatible data structure (maps, lists, text, booleans, numbers). It uses a sophisticated structure called a Sequence-Tree (SeqTree) to represent complex documents.

In our HyList, we added a parent: ID? field. This links an item to its parent node in the document tree. For example:

• Item for a paragraph: (Node1, 1, type="paragraph", pos=null, is_deleted=false)
• Item for a bold run: (Node1, 2, type="bold", pos=(Node1, 1), is_deleted=false)
• Item for the text “Hello”: (Node1, 3, type="text", pos=(Node1, 2), parent=(Node1, 2), is_deleted=false)

Now, the ordering rule is more complex. We first order by the position pointer (which moves up through the tree), and then we need to order by the parent as well. This creates a hierarchical ordering. The merge function for this is the Replicated Growable Array (RGA) algorithm applied to a tree structure.

This is the foundation for a full-featured collaborative editor. You can now have concurrent edits to the formatting of a piece of text (e.g., one user bolds a word while another italicizes it) and the merge function will produce a deterministic result (e.g., bold-italic, as defined by the tie-breaking rule).

V. Performance, Scale, and the Ghost in the Machine

We’ve built a powerful hybrid CRDT. But what about performance and scaling? A naive implementation that stores every keystroke as a linked list node will crash on a 100-page document.

5.1 Garbage Collection: Killing the Tombstones

The biggest performance killer is tombstoning. We must eventually remove tombstones. However, we cannot just delete them, because another peer might not have seen the “delete” operation and could still need that item to correctly apply its own edits.

The key is to know when it’s safe to delete a tombstone. This requires a global knowledge of the system state.

• Central Server Approach: The server can act as a coordinator. Each client reports its current sequence_number for every known node. The server can compute the minimum of all these sequence numbers. Any Item with a sequence_number less than this minimum is guaranteed to have been seen by every replica. Therefore, any delete operation that an old peer might have seen is already known. We can safely garbage-collect tombstones.
• Peer-to-Peer Approach: This is harder. There is no single source of truth. You can use a gossip protocol to share “I have seen up to this sequence number” information. Once you have confirmation from all peers, you can garbage-collect. This is a complex distributed consensus problem.

5.2 Compression and Delta States

Sending the entire linked list of millions of items over the network is not feasible. Our hybrid approach offers a solution: delta states.

A delta state is the set of all items that have changed since the last snapshot. Instead of sending the whole list, you send only the new items (inserts and deletes). This is almost as efficient as operation-based CRDTs! The receiver applies this delta to its current state using the merge function.

The sender can compute a delta by tracking the IDs of all items that have been added or deleted locally since the last time it synchronized. This turns the CvRDT into a practical, bandwidth-friendly system. This is the core of the automerge protocol: you send the operations (deltas) and rely on the state-based merge for correctness.

5.3 The Enduring Strength: No Central Server

The true power of this hybrid CRDT is the ability to work without a central server for correctness. While a server might be convenient for discovery, authentication, or garbage collection, the CRDT itself does not require one. This unlocks incredible possibilities:

• Peer-to-Peer Collaboration: Users can edit a document while completely disconnected from the internet. When they reconnect, their edits are automatically merged via the CRDT.
• Offline-First Applications: The whole document lives on the user’s device. They are always working on their local HyList. Edits are synced in the background.
• Federated Systems: You are not locked into Google’s servers. You can host your own collaboration server, or use a distributed, decentralized protocol like Hypercore or IPFS to replicate the CRDT state.

This resilience is the ghost in the machine. It’s a system that embraces the unreliable nature of the network and still produces consistent results. It’s a system that is, in a very real sense, its own source of truth.

VI. Conclusion: The Unnoticed Symphony

The next time you and a colleague edit a Google Doc without a hitch, take a moment to appreciate the symphony of algorithms playing out under the hood. For decades, Operational Transformation has been the main conductor, but it is a fragile one, reliant on a central server to keep the orchestra in time.

The CRDT revolution offers a different vision. The hybrid CRDT, like the Replicated Growable Array, is a beautiful, decentralized workaround for one of the fundamental problems of distributed computing. It is a ghost in the machine, but a ghost we can understand and engineer.

By combining the simplicity of state-based merging with the efficiency of operation-based delivery, we have a data structure that is both mathematically sound and practically efficient. It allows us to build collaborative applications that are more resilient, more decentralized, and more empowering. The ghost is not magic; it is mathematics. And now, with the conceptual tools we’ve built, you are equipped to summon it yourself.

The future of software is collaborative, and the future of collaboration is written in CRDTs. So, go forth and design the ghosts. Build the next great peer-to-peer whiteboard, the perfect offline-first writing app, or the decentralized Wikipedia. The structure is waiting.