Convergent Replicated Data Types

By kellabyte  //  Distributed Systems  //  2 Comments

Chris Patterson mentioned CRDT’s on Twitter this morning which reminded me that I haven’t blogged or provided any resource links on them in the past even though I’ve been reading about them for over a year. So here goes!

CRDT’s help build things like distributed sets, lists, counters and maps.

Justin Sheehy has a great quote describing what CRDT’s are:

CRDTs can provide values that appear similar to simple, well-known data types (like integers, sets, and maps) but with an internal structure that makes it safe to update them without any coordination between writers and without any loss of information in the face of concurrency.

The “C” in CRDT can stand for three different things. “convergent” if the underlying implementation is state-based, “commutative” if the underlying implementation is op-based, “conflict-free” if you wish to describe both/either at once without referring to the specifics of your internal choices.

The original paper about CRDT’s can be found here

I highly recommend watching the excellent talk from Sean Cribbs called Eventually Consistent Data Structures that covers what CRDT’s are and what they are for.

  • John Hamilton

    I really need to pore over your blog more. I get information overload on Twitter and often miss gems like this. Thanks for taking the time to write, Kelly. I’m always impressed by your seemingly endless supply of energy.

  • Pingback: Scalable Eventually Consistent Counters « kellabyte