CRDT: Conflict-free Replicated Data Types

1. Introduction:

  • to work offline
  • to access from different devices
  • several people to modify the same data

2. Strong eventual consistency:

  • Strong consistency (SC): all write operations are done strictly sequentially, read request on any replicas returns the same, last written result. A real-time consensus (with all its following consequences) is required to solve conflicts, allow n/2–1 nodes to be down
  • Eventual consistency (EC): make updates on the local, then propagate updates. Read on some replicas can return obsolete state. Rollback or somehow decide what to do in case of conflicts. That means we still need consensus, but not in the real-time
  • Strong eventual consistency (SEC): EC + replicas have a recipe to solve conflicts automatically. Therefore we do not require a consensus. Allows n-1 nodes to be down.

3. “Likes and hits” problems:

Count google.com hits:

Count a user’s likes:

4. Terminology:

  1. Idempotence
    The result doesn’t change if you apply the same operation several times.
    Example:
    1) GET request
    2) f(x) = x + 0
  2. Commutative property
    f(x, y) = f(y, x)
  3. Partial order
    Reflexivity + Transitivity + Antisymmetry
  4. Semilattice
    Partially ordered set with a least upper bound
  5. Version vector
    A vector with a size of the amount of nodes. Each node increments its vector element in case of some predefined events. During synchronization, these vectors are sent together with the payload and then by examining which node has greater value it can be decided which node has new/obsolete values. Thus it defines a total order.

5. Synchronisation models:

State-based:

  • Data type (or states on replicas) forms a semilattice
  • merge() function produces a least upper bound
  • Replicas form a connected graph
  • Data type: set of natural numbers N
  • Minimal element — negative infinity
  • merge(x, y) = max(x, y)

Operation-based:

  1. Executes generate() method which returns an effector() function to be called on other replicas. In other words, effector() is a closure to modify state on other replicas.
  2. Applies effector() to the local state.
  3. Propagates effector() to all other replicas
  • Reliable transmission protocol
  • If effector() is delivered in causal order then concurrent effector() have to commute OR
  • If effector() is delivered without respecting causal order then all effecter() have to commute
  • effector() has to be idempotent if it can be delivered more than once.

Delta-based:

Pure operation-based:

Typical usages:

  • If in your system updates must be propagated immediately the state-based synchronization is the bad choice because it costs more to the whole state. Delta-based would be the better choice, however, in this particular case the difference with state-based won’t be that much.
  • In case when you need to synchronize a replica after a failure — state-based / delta-based is the right choice. If you have to use the op-based, then there are options:
    1) Reply all missed changes since the failure
    2) Take a full copy of one of the replicas and apply all missed operations
  • As it has been mentioned earlier, op-based synchronization requires effector() to be delivered only once to each replica. This requirement can be loosened by requiring effector() to be idempotent. In practice, it is much easier to implement the former than the latter.

The relation between Op-based and State-based:

Now it’s time to talk about CRDT!

6. CRDT: Counter

6.1 Op-based counter:

6.2 State-based counter:

  • Hits/likes counter (sic!)
  • Amount of logged in users in a p2p network (Skype)

7. CRDT: Register

7.1 LWW-Register

  • Columns in cassandra
  • NFS — a whole file or a part of it

7.2 Multi-Value Register, MV-Register:

  • Amazon shopping basket. It has a well-known bug when an item re-appears in the basket after deletion. The reason is that MV-Register doesn’t behave like a set even though it stores a set of values (see below). Amazon indeed doesn’t treat that as a bug — it actually increases sales.
  • Riak. In the more general case we let the application to decide which values are the actual one (please note — we are not talking about conflicts!)

8. CRDT: Set

Naive implementation

8.1 Grow-Only Set, G-Set:

8.2 2P-Set:

8.3 LWW-element Set:

8.4 PN-Set:

8.5 Observe-Remove Set, OR-Set, Add-Win Set:

8.6 Remove-win Set:

9. CRDT: Graph

  1. removeVertex() has priority, all incident edges are removed
  2. addEdge() has priority, all removed vertices are re-added
  3. Delay removeVertex() execution till all concurrent removeVertex() are executed.

10. CRDT: Map

10.1 Map of literals:

  • How to deal with concurrent put() operations? We can do by analogy with counters and use LWW or MV semantics
  • How to deal with concurrent put()/rmv() operations? We can do by analogy with sets and use put-wins or rmv-wins or last-put-wins semantics.

10.2 Map of CRDTs:

11. CRDT: List

12. Riak

  • Counter: PN-Counter
  • Set: OR-Set
  • Map: Update-wins Map of CRDTs
  • (Boolean) Flag: OR-Set with no more than 1 element
  • Register: tuples of (value, timestamp)

13. Usages of CRDT

14. References

--

--

--

https://www.linkedin.com/in/amberovsky/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Fault Tolerance in Kubernetes Clusters

3 Python Packages to Hide Passwords and Secrets From Your Code

Important topics, which need to be gear up in order to passed google cloud architect certification

Everything I Want to Do Is Racist

Get Spotify Lyrics Right On Your Terminal !

Convert an EML File to PNG in Java

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Anton Zagorskii

Anton Zagorskii

https://www.linkedin.com/in/amberovsky/

More from Medium

WWH of Traditional File Formats to Modern File formats with modern file Storages — DELL/EMC ECS…

Using Sun Models to Capture Analytical User Requirements | Crimson Macaw

Introduction to Data Lineage, Data Governance and Data Dictionary Use Cases and Application

The Why, What And How Of Composable Data And Analytics