learning CRDT notes

what is CRDT:

CRDT

CRDT stands for Conflict-free replicated Data Type, its a way to ensure concurrent data update between clients. They guaranteed convergence eventually as long as concurrent updates are commutative.

This is a topic in distributed systems.

CRDT address the problem of concurrency in distributed system. However it has limitations, such as the lack of consensus. It only address part of the problem since a lot of update operation is not communicative.

Types of CRDT:

  • CvRDTs - Convergent replicated Data Types
  • CmRDTs - Commutative replicated Data Types

State based replication

Replica received update from client, and then sometime later it sends its full state to other replica.

Replica receiving other's full state will merge their current state with the incoming state.

Every replication occasional does the above actions, hence every update eventually reach every replica in the system.

IF:

  • set of value of the state form semi-lattice(a partially ordered set with a join/least upper bound operation)
  • updates are increasing
  • merge function computes the least upper bound THEN replica guaranteed to converge at the same value.

IF:

  • if set of all possible states if semi-lattice THEN Merge operation has to be idempotent, associative, and commutative
Idempotent - operation on a element will produce the same result.

IF:

  • Replica satisfy above points

THEN:

  • Replica is CvRDTs.

img of CvRDTs

Operation based replication

Don't send whole state broadcast update operations to all systems, expect each replica to replay them.

This may cause replica to received update operation in different order, so they have to be communicative.

img of CmRDTs

Resource followed

  • https://www.farley.ai/posts/causal
  • https://medium.com/@istanbul_techie/a-look-at-conflict-free-replicated-data-types-crdt-221a5f629e7e
  • https://en.wikipedia.org/wiki/Semilattice
  • https://www.youtube.com/watch?v=3UkC3sXLqhQ
  • https://www.youtube.com/watch?v=LCFf2DBTVmo
  • https://www.youtube.com/watch?v=KbyVjwmzlpk
  • https://www.youtube.com/watch?v=XJQqDDTNvJA