distributed-computingdistributed-systemcrdt

What is CRDT in Distributed Systems?


I am a newbie in Distributed systems and I am trying to get an insight on the concept of CRDT. I realize that it has three notations :

Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type

Can anyone give an example where we use CRDT in distributed systems? Thanks a lot in advance.


Solution

  • CRDTs are inspired by the work of Marc Shapiro. In distributed computing, a conflict-free replicated data type (abbreviated CRDT) is a type of specially-designed data structure used to achieve strong eventual consistency (SEC) and monotonicity (absence of rollbacks). There are two alternative routes to ensuring SEC: operation-based CRDTs and state-based CRDTs.

    CRDTs on different replicas can diverge from one another but at the end they can be safely merged providing an eventually consistent value. In other words, CRDTs have a merge method that is idempotent, commutative and associative.

    The two alternatives are equivalent, as one can emulate the other, but operation-based CRDTs require additional guarantees from the communication middleware. CRDTs are used to replicate data across multiple computers in a network, executing updates without the need for remote synchronization. This would lead to merge conflicts in systems using conventional eventual consistency technology, but CRDTs are designed such that conflicts are mathematically impossible. Under the constraints of the CAP theorem they provide the strongest consistency guarantees for available/partition-tolerant (AP) settings.

    Some examples where they are used

    Riak is the most popular open source library of CRDT's and is used by Bet365 and League of Legends. Below are some useful links that supports Riak.

    1- Bet365 (Uses Erlang and Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

    2- League of Legends uses the Riak CRDT implementation for its in-game chat system (which handles 7.5 million concurrent users and 11,000 messages per second)

    3- Roshi implemented by SoundCloud that supports a LWW time-stamped Set: -Blog post: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events