Conflict-Free Replicated Data Type

Versions: Scala 2.12.3, Akka Distributed Data 2.5.11

Pessimistic replication requires a synchronous communication between the main node writing the data and the replicas. However in some cases the optimistic replication can be more efficient and still guarantee the same final result. One of solutions from this category are conflict-free replicated data types.

This post focuses on the Conflict-free Replicated Data Types (CRDT), implemented among others in Redis and Riak. However, the article begins with the explanation of the difference between pessimistic and optimistic replications and why we can use the CRDTs in the latter one. The next part shows this data structure more in details by listing some of popular types (counters, registers and set). The last section shows them in some learning tests written with the help of Akka's Distributed Data library.

Conflict-free replicated data type and optimistic replication

In distributed systems the replication is one of possible sources of the data inconsistencies. When a network partition occurs one or more cluster nodes become unreachable. Thus, during this time they don't receive any updates and the data they store can diverge from the data stored on reachable nodes. Even though the system is globally available, its whole state becomes inconsistent.One of strategies helping to deal with this kind of issues is pessimistic replication.It means that the given state change is confirmed only when all required replicas acknowledge the write of modified data. However as you can imagine, it has a big impact on the latency since the operation is not considered successful as long as there are some of nodes not acknowledging it.

Another approach to deal with the replication issues is the optimistic replication. Here the replication happens in asynchronous manner, i.e. the main writer doesn't need to wait all replicas before confirming the operation. The inconsistencies are quite naturally "allowed" and, if they exist, they're resolved later by the merge operation. An example of such situation can be a boolean flag defined as true when one specific event happened at least once in the past. Thus, when in some replicas this flag is false and in the others true, the conflict can be easily resolved by putting the false flags to true since once happened event can't be discarded.

One of techniques supporting the optimistic replication are Conflict-free Replicated Data Types. As you can deduce from the name, it's a data structure that can be safely (without conflicts) replicated across different nodes in the cluster. The safety is guaranteed by the fact that all conflicts can be mathematically merged or resolved. One of properties guaranteeing it is the commutativity. It means the order-insensitive arguments of the operations, i.e. f(a, b) = f(b, a). We'll see that more in details in the next section where specific data structures are covered.

Conflict-free Replicated Data Types examples

Two different approaches define the CRDTs. The first one is state-based and it creates Convergent Replicated Data-Types (CvRDT). It represents the situations where the whole changed object is sent to the replicas. In the execution flow, the first step consists on updating the local state. After that the new object is sent to the remaining replicas that merge their local state with the one coming from the remote call.

The second approach is operation-based and it creates Commutative Replicated Data-Types (CmRDT). The name comes from the method used to propagate the updates. Instead of sending the whole new object this approach sends the operation constructing it. The replicas receiving this message execute the operation and create by that an updated object. However as you can imagine, because of network issues, the operations can arrive to different replicas in different order. For instance the replica#1 can receive 2 sample operations in order (op1, op2) while the replica#2 in reverse order. Because of that this approach can be applied only to the commutative updates.

In more fine-grained level we can distinguish the following data types: