Using CRDT to Resolve Conflicted Operations
In the conversation I had with some software engineers, I realized that the concept of CRDT (Conflict-free Replicated Data Type) is not well known. I want to raise the awareness of the ubiquitousness of out-of-order, duplicated operations/data in distributed systems and give a very simple introduction on how CRDT can resolve those conflicts.
The problem we are facing in designing distributed systems that support both reads and writes is straightforward, but also critical. As we accepts data/operation, we cannot assume the data arriving to the system is properly ordered and without duplication. For example, an ordering system, which is responsible for sending reliable notifications about order and shipment level events, can be built on top of AWS SNS/SQS and both systems do not guarantee the order of the messages and only guarantee the messages will be delivered at last once. When building a data storage system that persists customers’ orders, we need to resolve the conflicts such as a cancellation message can write before the ordering message. In a broader sense, as long as at least one of upstream data pipelines do not guarantee the order of the events, undesired behavior will happen. In reality, out-of-order/duplicated messages are very common. Hosts and network failures can lead to retries; a cluster without consensus distributed algorithms can send messages without consulting each other.
Conflict-free Replicated Data Type (CRDT) is a set of data structures that can be replicated across network and can guarantee the data to be consistent and correct eventually. Those data structure do not make assumptions on how the data are replicated, or the order of the data it arrives. Details of those data structures and the mathematical prove of their correctness can be found in these two papers:
- https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf
- https://hal.inria.fr/hal-00932836/file/CRDTs_SSS-2011.pdf
Here I gave two examples on how CRDT can be used.
Example 1: Using key-value database to store most-recent data
Imagine we want to build a system that allows users to stores their data and the system should vend the most recent data eventually. Eventually here means that if users submit two operations set (key_1, value_1) at t1 and set (key_1, value_2) at t2, where t2 > t1, no matter what order and duplicates they send to our system, the system should vend (key_1, value_2) after certain reasonable amount of time.
For simplicity, let’s assume that users cannot delete the key. If we simply store key-value pair in the table, this won’t work because if (key_1, value_2) is written to the table before (key_1, value_1), (key_1, value_1) will be stored in the table forever.
What CRDT proposes, is to use additional field to resolve the conflicts. Many systems simply use system clock or physical timestamp to denote the order of the operations/data. Timestamp can be either supplied from the clients or automatically generated within the system. But CRDT does not make assumption on what types of timestamp we use: it can be physical time, can be logic clock, etc.
What if we want to support deletion as well? In this case, we cannot simply delete the item from the database. Imagine users submit two operations set (key_1, value_1) at t1 and delete key_1 at t2, where t2 > t1. If deletion operation arrives before set operation, the (key_1, value_1) will be stored in the database forever!
The solution proposed in CRDT is to retain the deletion records and mark it with a special deletion flag, commonly known as tombstone flag. A record with tombstone flag is typically not visible to clients, but used internally to make sure we don’t overwrite a deleted record. For example, when receiving the deletion operation, instead of deleting the data, we update the record to (key_value, value_1, tombstoned, timestamp_2), so that when we receive the set (key_1, value_1, timestamp_1) operation after deletion operation, if timestamp_1 < timestamp_2, the set operation will be ignored by the system.
Example 2: Adding and deleting items in a set
Imagine we want to build a feature that allows users to add and remove individual items to and remove a set. For example, the set could contains a list of customer IDs who are eligible for a promotion. If we allow users to perform those operation concurrently and want to resolve those conflicted writes to this set, special cares are needed.
To explain this further, if the existing set contains three items {value_1, value_2, value_3}, and there are two users want to apply delta updates to this set concurrently. User A tries to delete value_3 and user B wants to add the same item back. If we cannot resolve the order of the operation, we will get divergent results which could be ether {value_1, value_2, value_3} or {value_1, value_2}.
There are two ways to solve this problem. We can use the same approach used in the previous example: instead of storing only key-value pair in the set, we can store additional information in each item (e.g. event time) to help us resolve the conflicts.
But what if you cannot add additional information to the item because this will introduce non-backward-compatible changes, or simply because the limitation of the system? CRDT proposes that you can actually maintain two sets: one for addition, one for deletion, each of which stores item and additional information to resolve the conflict. Whenever users request the data, we merge both addition and deletion sets by resolving the conflict data (e.g. comparing the event time of the same item from both sets).
