Operation-based variant of CRDTs is based on idea, that instead of replicating the state (or its delta), we replicate the operations, and let the corresponding replica build eventually consistent state from operations only. A standardized API for such data types consist of several members:
initial: empty instance of CRDT object.query: returns a value out of the CRDT object.atSource: which returns a serializable operation. I.e. for a givenCounterCRDT, itsatSourcefunction could return operations likeinc(replicaId, delta)ordec(replicaId, delta).downstreamwhich is used to consume operations incoming from both local and remote sources to produce new state of the CRDT object.
This variant introduces some complexity on the replication protocol itself, as it needs to satisfy at least reliable causal broadcast properties. In many practical implementations this means, that we need to perform two kinds of I/O - not only network, but also disk persistence in order to achieve reliable delivery - before applying downstream function over incoming operations, produced by atSource.
Since at some point we need to broadcast operations to other replicas, usually living on different machines, it means, that we need some form I/O. A problem with I/O is that it's usually orders of magnitude slower than operations performed locally. Most production systems are reducing that cost by applying batching of messages.
For operation-based CRDTs it means that before calling downstream over incoming operation, we are supposed to already preserve that operation - it's an implicit requirement of providing exactly once delivery required by CmRDT replication protocol - which means involving I/O.
This creates a following opportunity: could we conflate operations awaiting in the buffer, before performing I/O on it?
Example: Imagine operation-based Counter implementation, which exposes two operations inc(replicaId, delta) and dec(replicaId, delta). Now, we are serving operations incoming with high frequency - at a rate high enough, to require us to start buffering operations before performing I/O. Our buffer could look like this:
inc(A,1) -> inc(B,4) -> dec(A,3) -> inc(A,1)
We could conflate those operations into a single equivalent in form of dec(A,1) -> inc(B,4), and send it over I/O instead. Moreover, we could even apply that replacement in a downstream operation and still end up with correct state. To do that, we need 2 things:
- A conflate operation:
op * op -> opdefined for CRDT's operations, that we want to conflate. - A buffer, that will allow us to perform fast lookups for buffered operations corresponding to the same object (or data type, as we potentially could conflate across multiple objects of the same type).
The funny part starts with 2nd point, as I still need to evaluate this one somehow so see if the whole idea has sense.