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.
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.