Understanding Conflict-Free Replicated Data Types

Conflict-free Replicated Data Types (CRDTs) are a class of data structures that enable seamless collaboration and data synchronization in distributed systems, allowing for collaborative updates without conflict. CRDTs are designed to achieve eventual consistency across multiple replicas of data, ensuring that even when updates occur independently, all replicas converge to the same state without requiring complex conflict resolution mechanisms.

In this blog post, we'll delve into what CRDTs are, explore their uses and types, understand how they work, and learn how to implement them, with a focus on JavaScript and the powerful Yjs library.

Use Cases of CRDTs

CRDTs are particularly useful in scenarios where real-time collaboration and offline support are crucial:

1. Collaborative Text Editors: Google Docs, Notion, and Etherpad use CRDT-like structures for real-time editing.
2. Collaborative Design Tools: Figma, a popular web-based design tool, uses CRDTs to enable real-time collaboration on design projects. Multiple designers can work on the same file simultaneously, with changes syncing seamlessly across all users.
3. Distributed Databases: RxDB and Riak use CRDTs for conflict-free replication.
4. Multiplayer Games: For maintaining consistent game state across players.

Types of CRDTs

There are two main types of CRDTs:

1. State-based CRDTs: These replicate the entire state of the data structure. Merging is done by comparing and reconciling the states of different replicas.
2. Operation-based CRDTs: These replicate the operations performed on the data structure. Merging is done by applying operations from different replicas in a commutative manner.

How CRDTs Work

CRDTs (Conflict-free Replicated Data Types) operate on principles that ensure eventual consistency across all replicas of the data, even when updates are made concurrently or when network partitions occur. Let's delve deeper into the mechanics:

Key Properties

1. Commutativity: This property ensures that the order of operations doesn't affect the final result. For example, in a counter CRDT, incrementing by 2 and then by 3 yields the same result as incrementing by 3 and then by 2.
2. Associativity: This means that the grouping of operations doesn't matter. Using the counter example again, (1 + 2) + 3 is the same as 1 + (2 + 3).
3. Idempotence: Applying the same operation multiple times has the same effect as applying it once. This is crucial for handling duplicate messages in distributed systems.

Conflict Resolution

CRDTs resolve conflicts automatically by design:

• For state-based CRDTs (CvRDTs), this is achieved through a merge function that combines the states of two replicas. This merge function must be commutative, associative, and idempotent.
• For operation-based CRDTs (CmRDTs), operations are designed to be commutative, ensuring that applying them in any order leads to the same final state.

Logical Clocks

Many CRDT implementations use logical clocks (such as version vectors or dotted version vectors) to track the causal history of operations. This helps in determining the order of concurrent operations and in identifying which updates a replica has already seen.

Using CRDTs in JavaScript with Yjs

Implementing CRDTs from scratch can be complex. However, there are libraries available that simplify the process. For JavaScript, one of the most popular CRDT libraries is Yjs. It is a high-performance CRDT implementation that supports various data types. Let's create a simple todo list application using Yjs, simulating multiple users working on the same document in memory.

Here's an example of how to implement a shared todo list using Yjs:

Let's use the created ydocs :

In this example, we create two Yjs documents (ydoc1 and ydoc2) to simulate two users working on the same todo list. Each document has its own shared map for the todos.

We define functions to add, update, and delete todos, as well as a syncDocs function to manually synchronize the state between the two documents. This simulates what would happen in a networked environment where updates are exchanged between clients.

Conclusion

CRDTs provide a powerful solution for building collaborative, distributed applications that can work seamlessly online and offline. While the underlying concepts can be complex, libraries like Yjs make it easier for developers to leverage the power of CRDTs in their applications. As distributed systems become more prevalent, understanding and utilizing CRDTs will become an increasingly valuable skill for developers.

Useful Links

1. Yjs
2. CRDT
3. Tiptap - A collaborative text editor