# Operation conflation of Commutative Replicated Data Types

## Intro to Commutative Replicated Data Types

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 given `Counter` CRDT, its `atSource` function could return operations like `inc(replicaId, delta)` or `dec(replicaId, delta)`.
- `downstream` which 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`.

## An opportunity

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:

1. A conflate operation: `op * op -> op` defined for CRDT's operations, that we want to conflate.
2. 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.