CRDTs: Distributed Semilattices

I've recently returned from the Strange Loop conference in St. Louis. One of the talks that really piqued my interest was one by Peter Bourgon (@peterbourgon) on CRDTs.

In Abstract Algebra a CRDT is formally known as a Semilattice. As a Semilattice a CRDT must obey the following laws.

  • Associativity: x ∧ (y ∧ z) = (x ∧ y) ∧ z
  • Commutativity: x ∧ y = y ∧ x
  • Idempotency: x ∧ x = x

This means that given two or more CRDTs you can merge them in any any order with any precedence any amount of times and the results will always consistently converge to the same thing. This is a very useful trick to manage consistency in distributed systems.

There is a somewhat cannonical paper on CRDTs called A comprehensive study of Convergent and Commutative Replicated Data Types. This paper contains the the definitions of the two main families of CRDTs (CvRDT vs CmRDT) along with the specifications for numerous CRDT counters, registers and sets.

A CvRDT is what the paper calls a Convergent Replicated Data Type. A CvRDT is described as a state based CRDT that has a join/merge operation that must receive another CRDT as input to produce the convergent result. While a CmRDT is what the paper refers to as a Commutative Replicated Data Type and is an operation based CRDT that receives commutative operations on a channel such that regardless of the order the operations are played in the CmRDT will converge to the result of another one with the same operation set.

CvRDT are the simpler of these two variants, thus you'll notice that in the CRDT paper the majority of the specifications described are CvRDT implementations.

The CRDTs specified in the paper are as follows:

  • Counters
    • G-Counter
    • PN-Counter
  • Registers
    • LWW-Register
    • MV-Register
  • Sets
    • G-Set
    • 2P-Set
    • LWW-Element-Set
    • PN-Set
    • OR-Set

What follows is a small subset of the CRDTs defined in the paper.

Counters

CRDT counters provide you with a convergent way to do distributed counters. These are useful for high volume large scale distributed counters that should eventually converge to the correct value. A good use case would be in real time analytics or distributed gaming.

G-Counter

The G-Counter is a state based grow only counter. This means the only operations you're allowed to perform on a G-Counter are #increment() and #merge()

In scala it would look roughly as follows:

final case class GCounter(n: Long) {  
  def inc = GCounter(n + 1)
  def merge(other: GCounter) = GCounter(n max other.n)
  def toLong = n
}

PN-Counter

The PN-Counter is a state based counter that supports convergent increment and decrement. It accomplishes this by storing two G-Counters. One G-Counter P is used to track the number of increments while the other G-Counter N is used to track the number of decrements. The current value of a PN-Counter is P - N and the merge operation for two PN-Counters is PNCounter(a.p max b.p, a.n max b.n).

In scala it would look roughly as follows:

final case class PNCounter(p: GCounter, n: GCounter) {  
  def inc = PNCounter(p.inc, n)
  def dec = PNCounter(p, n.inc)
  def merge(other: PNCounter) = {
    PNCounter(p.merge(other), n.merge(other))
  }
  def toLong = p.toLong - n.toLong
}

Sets

Sets are a CRDT primitive for representing convergent collections. They can be used to represent follower graphs, group membership and even convergent ordered log events.

G-Set

A G-Set is a state based grow only set. You can only ever add new members to a G-Set and merge them with other G-Sets.

In scala it would look roughly as follows:

final case class GSet[A](s: Set[A]) {  
  def insert(item: A) = Gset(s + item)
  def merge(other: GSet[A]) = GSet(s ++ other.s)
  def toSet = s
}

2P-Set

A 2P-Set (two phase set), is a state based set that supports the insertion of elements and the once only removal of elements. Once an element is removed from a 2P-Set it can never be added back to the set in a convergent manner. This is achieved by internally maintaining two G-Sets. A G-Set A to track all the set additions and a G-Set R to track all the set removals. An element is considered to be in the set if it is present in the A set and not present in the R set. The merge operation is the result of merging the internal G-Sets of the CRDTs.

In scala this would look roughly as follows:

final case class TwoPhaseSet[A](a: GSet[A], r: GSet[A]) {  
  def insert(item: A) = copy(a = a.insert(item))
  def remove(item: A) = copy(r = r.insert(item))
  def merge(other: TwoPhaseSet[A]) = {
    TwoPhaseSet(a.merge(other.a), r.merge(other.r))
  }
  def toSet = a.toSet.diff(r.toSet)
}

Conclusion

CRDTs are a great way to have convergent consistency in distributed systems. If you want to see more of them more fully implemented in Scala i've implemented a good amount of them in a repository called Convergence.