CRDTs are data structures that can be replicated across multiple computers in a network. These replicas can be updated independently or concurrently without coordination between the replicas and resolve themselves automatically.
Inconsistencies i.e. conflicts are resolved through a conflict resolution algorithms.
Multi-user editing and collaboration over networks presents a vast array of issues. To illustrate where things can go wrong, even in a simple 2-user environment, let's consider the following examples.
In the simplest case, two users have replicate sets of letters. If each user performs a transaction on their set, those transactions could then be sent to the other user. The transactions can be unionized, and then each user performs the actions from the other user:
Each user ends up with the correct, expected list of letters. This is all well and good, but in the real world things aren't this simple. Consider another slightly more complex example.
Say we have two replicates of a string. In order to keep track of the letters, we assign each of the letters an index. When we remove or insert a letter, we supply the letter and the place to insert or remove it. However, this can cause some issues. In the figure below, one user deletes a letter at position 2, while the other user deletes a letter at position 1 and inserts a letter at 7. When these the users exchange actions, incorrect letters are removed and the string becomes jumbled.
A possible solution to this issue is to transform the operation that a user performs after an edit by a second user. For example if user A deletes the 6th index from the string, user B's operation of adding 's' to the 7th index would be transformed to insert s at position (7-1)
This is a extremely boiled down example of a method called operational transformation, which is a solution for conflict resolution. However, this is a very limited approach. Many iterations have tried and failed at solving issues where more than 2 users are editing a document, or manipulating data, at once. In fact, Google Docs uses OT, however this only works because a central Google Server acts as the arbiter between multiple peers. With OT, a true multi-user editing system is very difficult.
Here enters CRDTs, which attempt to solve concurrency issues through resolution algorithms, allowing for a seamless multi-user editing system.
Generally consistency in distributed systems can be strong or eventual. Strong consistency allows for sequential writes, but is impossible when users are disconnected from each other and aren't available with network partitions. Eventual consistency allows for individual partitions to converge eventually, but these can be complicated algorithms that are hard to test.
CRDTs raise the bar in striving for strong eventual consistency. Once two nodes have seen the same event, they are immediately in the same state.
There are two main approaches when designing a CRDT.
- Operation-based CRDTs - transmit only the operation. The replicas receive the operations and apply them locally.
- State-based CRDTs - Send the whole local state to other replicates. These are easier to implement, but are more costly.
OP-based CRDTs need to follow a set of rules to assure strong eventual consistency.
- All concurrent operations must commute
- ie.
(x*2)-1 !== (x-1)*2but(x-4)-3 === (x-3)-4
- ie.
- Assume that updates are applied exactly once
- Updates must be applied in the order from which they were sent from their origin.
In the example below, two users are sharing simple counter data. What is shared between the users is the actual operation that each user attempts to perform. The action is performed locally, increasing or decreasing the value, and then shared with the second user.
In the second figure, the value is a map and not a number. Concurrency is dealt with in this case by assigning each entry a unique id (in this case Xa or Xb) that that additions and removals can be tracked accurately.
These update the local state, then send the state and merge with other users.
- Allow for retransmissions. The merge function should be idempotent, i.e. no matter how many times you apply a transformation, the end result will always be the same.
- We need a concept of 'going forward', i.e. clocks.
- Updates and merges always go forward and must increase the state in this order.
In the example of a state-based CRDT algorithm below, the entire state, in this case an object containing all actions performed on the a property. Whenever a local transaction occurs, the whole state is passed {a: +3, -5}, for example.
Yjs' CRDT algorithm is best described with a visual example. Assume we have a document with the characters AB already written. One user wants to insert "C" between these characters.
In Yjs, every character is assigned a unique identifier/timestamp, a pair of integers with the first representing the user identifier or the user who performed the operation and the second representing an incrementing clock.
For instance, the C would have the coordinates (0,0) for the user 0 and clock 0.
The C is inserted and now the same user wants to insert a D in between C and B. This character would have the identifier of 0,1. It is the same user 0, but the clock has incremented to 1.
Let's say a different user inserts an E in between A and B, but the timestamp is 0. Here we have a concurrency conflict.
Yjs resolves this by looking at the id. If the clocks are the same, but the ids are different, Yjs compares them and gives preference to the lower user id. The resulting document is therefore ACDEB.
For efficiency, Yjs doesn't store a time stamp for every unique character, but rather stores groups of characters as items. If one user types the string 'ABC', the timestamp would be supplied to the entire string: ABC(0,0). If another user wanted to insert a character 'D' in between this string, the result would be a split item: A(0,0) D(1,1) BC(0,0).
For a deeper dive into Yjs check out this article.
Information for this section was sourced from several videos (1, 2, 3) websites (crdt.tech, wikipedia), and tag1's Yjs Deep Dive.