CRDT

aka Conflict Free Replication Data Type is data structure that can be replicated on multiple network where each replica could be updated independently and concurrently without coordination between replica and theoretically can be resolve inconsistencies that might comes up.

There are 2 types of CRDTs

• State-based CRDTs State-based CRDTs also called convergent replicated data types, or CvRDTs. This CRDT types send their full local state to other replicas where the states are merged by a function which must be Commutative, Associative and Idempotent.

• Operation-based CRDTs Operation-based CRDTs propagate state by transmitting only the update operation. The replica, receive the update and apply them locally. the operations are Commutative

Known CRDT’s

• G-Counter (Grow-only Counter)
• PN Counter (Positive Negative Counter)
• G-Set (Grow-only Set)
• 2P-Set (Two-phase set)
• LWW-Element-Set (Last-Write-Wins-Element-Set)
  • LWW-Element-Set consist of add set and remove set with timestamp on each element
  • Elements are added to and LWW-Element-Set by inserting element into the add set with a timestamp
  • Elements are removed from LWW-Element-Set by being added into the remove set with a timestamp
  • An element is a member of the LWW-Element-Set if it’s in the add set but not in the remove set
  • Or in the remove set but with the earlier timestamp than the latest timestamp in the add set.
• OR-Set (Observed-Remove Set)
• Sequence CRDTs

Know implementation of CRDT’s

• Redis is in-memory databases, uses CRDT’s for implementing globally distributed databases
• Apple implements CRDT’s on the Notes app