News for hackers. Stuff that matters.

dangduc

Re:Roshi: a CRDT system for timestamped events on Wednesday May 14, 2014 @04:37AM (#7742766)
I'm trying to understand CRDTs, and Roshi provides an implementation of how CRDTs can be put to use in real-world applications. I've assess the documentation on Roshi and would like assent or clarification if I'm wrong.

After glossing over the readme of github.com/soundcloud/roshi I came away with the impression that Roshi's LWW-element-set implementation does not strictly adhere to the qualities of a CRDT, mainly that operations must be commutative.

Roshi documents two uses-cases:

If first we apply an add operation to the set, then apply a remove operation with the same tuple, the resulting set will ignore the remove operation: A(a,1) R() + remove(a,1) = A(a,1) R()

If we apply the remove operation, then next the add operation, the resulting set will ignore the add operation: A() R(a,1) + add(a,1) = A() R(a,1)

This means the resulting state of the set depends on the order of operations, which violates the commutative property of CRDTs.

As a consequence, if we assume this CRDT is replicated on each redis node in a Roshi cluster, then there is a case (admittedly rare and short-lived) where a Roshi cluster cannot be eventually consistent:

Given no more future operations on a set with key K, if, node 1 contains a key K with set A(a,1) R(), and node 2 contains a key K with set A() R(a,1), then the system cannot be eventually consistent.

Roshi seems to have implemented a weak form of CRDT, which under rare and short-lived situations impedes eventual consistent. But given the operational realities, this is totally acceptable.