Creating a collaborative app using CRDTs
Creating a collaborative application such as Google Docs, Miro or Figma that lets multiple users work together online is a difficult task. Creating a collaborative app using the same methods one does in single user applications won’t work.
Why you ask. Because you have to ensure consistency, handle crappy internet connections, support offline editing, transfer changes in real-time.
Fortunately, research has been devoted to solving some of these issues. Conflict-Free Replicated data type (CRDT) is is a collection of data types that can be used in a collaborative application, in order ensure consistency. In this post I will show a set of the problems that CRDTs solves, and how it can be applied to editing documents, sets, registers, counters, graphs, which can be used in many different use cases.
The term replica describes a copy of data a single user or server have. Replicas will merge state created with each other, and after a merge, the replicas will have the same state. CRDTs uses a consistency model called strong eventual consistency. The Wikipedia description of eventual consistency is:
Eventual consistency is a consistency model used in distributed computing to achieve high availability that informally guarantees that, if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value.
Strong eventual consistency, emphasis some mathematical properties which guarantee consistency.
There exist two different types of CRDTs, one is state-based were the state is sent between replicas and merged, and the other is operation-based were individual operations are sent to other replicas.
Naive set implementation.
In the naive set implementation, we have two different replicas that are editing some type of data that can be represented as a set. Starting from the top, the blue replica starts by adding the element a, then it removes a, and finally, it receives the add operation of element a. In the end, the blue replica has the state consisting of element a. The yellow replica starts by receiving the add operation, so it adds a, next it adds a again (nothing changes) and finally the removal of the element arrives, which makes the yellow replica end up with nothing in the end. The problem here is that both replicas have received the same operations, yet they diverge into different states, so this implementation does not work. Later I will show how this can be solved.
Naive counter implementation.
An operation-based counter will work since addition is commutative and associative, given that each change is delivered exactly once.
State-based counters are not idempotent, therefore they will not converge, for example. If you merge multiple times the value will increase, therefore this will not work. Merging 1 with 2 using the max function, will equal 2, although 3 is the correct answer. By using the properties of the vector clock we can achieve a counter that works.
Naive sequence implementation
An issue regarding sequences is displayed in the above figure, here both replicas start with the sequence “abc”. The blue replica inserts the letter “e” at index 2, then it receives a delete operation at index 1, and ends up with “aec”. The yellow replica starts with a delete operation, followed by the insert of the letter “e” at index 2, and ends up with “ace”. The issue here is that the replicas diverge, as the yellow replica applied the delete operation which altered the indexes, thus inserting “e” in the wrong index.
Before we look at how CRDTs work, I will explain some mathematical properties behind it.
Commutative: a*b=b*a
Associative: (a*b)*c = a*(b*c)
Idempotent: (a*a) = a* = binary operation, example: max, union, or
Commutative and associative properties ensure operation/changes can be made out of order. While the idempotent function ensures that a merge a state with itself is equivalent. The three properties (associative, commutative, and idempotent) in listing 2.1 form a join-semilattice, see figure 2.1 and figure 2.2. A join-semilattice is a partially ordered set which for every subset has a join, a least upper bound(LUB). For any two given elements there exists a single LUB. All elements are ordered according to a binary relation. In a CRDT the merge function uses the join-semilattice, meaning for any given set of elements, there exists one LUB, which will move the two elements towards the same state. The max function and the union function follows these three properties. For instance the max function:
Commutative: max(a,b) = max(b,a)
Associative: max(max(x,y),z) = max(x,max(y,z))
Idempotent: max(x,x) = x
This is demonstrated in the join-semilattice in the following figure. In the join-semilattice, any two elements will have a LUB, that brings both elements into the next state after a merge has been done.
Let’s look at an example of LUB. Two elements are highlighted which are merging with each other, the result is the LUB highlighted in green, the state in which both replicas will end up in. The merge function is simply the pairwise max of two vectors.
Another example:
If you merge the same element with itself, the LUB will be the same element, following the idempotent property.
Let’s take a final example is were you merge an element with one that’s above itself, the LUB will be the above element.
The union operation can also be applied, for instance
Commutative: (a ∪ b)= (b ∪ a)
Associative: (a ∪ b) ∪ c) = (a ∪ (b ∪ c))
Idempotent: (a ∪ a) = a
Where the corresponding the join-semi lattice looks like this. The previous examples work here too.
State-based CRDTs uses all three properties. The operation based CRDT uses the first two properties and relies on exactly once-delivery of each operation. The operation based approach can emulate the state-based approach, you can read more about this in the original paper as I don’t think it’s necessary in order to grasp these concepts.
Counters
A counter is the easiest CRDT and will help you understand more complex CRDTs down the line. An operation based counter, however, is commutative and associative, therefore by sending a value to another replica will merge.
A state-based counter as stated previously does not follow the properties behind a CRDT, unless it is implemented using the properties behind a vector clock, where each replica has a designated position in the vector were it can increment the counter. The merge function will then use the pairwise max of two vectors, as explained in the join-semilattice previously.
The sequence diagram above demonstrates how it works. Both replicas have a designated position in the distributed counter, were the replica can apply increments to this specific position, then it simply sends it to the other replica which will merge it. To get the current state of the counter, you sum up each element and end up with the final value. In order to have decrements, another vector can be used for decrements. You can read more about this in the articles I recommend at the bottom of the page.
Sets
There exist a few different CRDT Sets. The Grow only set is where you can add an element once, since elements in a set are unique, adding it again results in the same state, as it is idempotent. In order to handle removal of elements we can use the 2P-Set, were each element can be added or removed once, and once it is removed, it can not re-added again. This works by using two sets, one for adding elements and another for removing elements. The elements that are in the final set are the elements that are in the add-set, but not in the remove-set, as shown by the lookup function below.
The bellow sequence diagram demonstrates how the 2P-Set works.
2P-Set
A constraint with the 2P-Set is that it can re-add something which was removed, but with the OR-Set each element is tagged with a unique id so that an element can be added after a removal. In the below example both users add element “a” but internally they are tagged with a unique id.
OR-Set
Sequences
In order to deal with document or sequences, each element in the sequence must have a global index, such that it can be inserted at the index at multiple replicas, even if the insert is applied in different orders. In order to work properly, elements are never removed, only tagged with a tombstone saying that the element is removed, and as such not displayed to the user.
Another issue is were both replicas insert a character at the same index simultaneously, then the tiebreaker consists of looking at the ID of the replicas, and using this number to suggest were to do the insert. In the diagram below “ins(3,c,1)” is an insert operation were “c” is inserted at index 3, by the replica 1. Since both replicas are inserting a character at index 3, the tiebreaker is the ID of the replica, since 1 is lower than 2, “c” will be inserted before “d” in the example below.
Hopefully, by now some of the CRDT concepts have been introduced to you, but they are a bit difficult to grasp, therefore I have suggested further reading below.
Further reading:
https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf
https://hal.archives-ouvertes.fr/hal-00921633/document
https://medium.com/@amberovsky/crdt-conflict-free-replicated-data-types-b4bfc8459d26
https://medium.com/@istanbul_techie/a-look-at-conflict-free-replicated-data-types-crdt-221a5f629e7e
https://conclave-team.github.io/conclave-site/
http://digitalfreepen.com/2017/10/06/simple-real-time-collaborative-text-editor.html
