Operation-based and state-based CRDTs v5
Operation-based CRDT types (CmCRDT)
The implementation of operation-based types is trivial because the operation isn't transferred explicitly but computed from the old and new row received from the remote node.
Currently, these operation-based CRDTs are implemented:
crdt_delta_counter—bigintcounter (increments/decrements).crdt_delta_sum—numericsum (increments/decrements).
These types leverage existing data types with a little bit of code to compute the delta. For example, crdt_delta_counter is a domain on a bigint.
This approach is possible only for types for which the method for computing the delta is known, but the result is simple and cheap (both in terms of space and CPU) and has a couple of added benefits. For example, it can leverage operators/syntax for the underlying data type.
The main disadvantage is that you can't reset this value reliably in an asynchronous and concurrent environment.
Note
Implementing more complicated operation-based types by creating custom data types is possible, storing the state and the last operation. (Every change is decoded and transferred, so multiple operations aren't needed.) But at that point, the main benefits (simplicity, reuse of existing data types) are lost and no advantage is gained compared to state-based types except for the space requirements. (A per-node state isn't needed.) For example, there's still no ability to reset.
State-based CRDT types (CvCRDT)
State-based types require a more complex internal state and so can't use the regular data types directly the way operation-based types do.
Currently, four state-based CRDTs are implemented:
crdt_gcounter—bigintcounter (increment-only).crdt_gsum—numericsum/counter (increment-only).crdt_pncounter—bigintcounter (increments/decrements).crdt_pnsum—numericsum/counter (increments/decrements).
The internal state typically includes per-node information, increasing the on-disk size but allowing added benefits. The need to implement custom data types implies more code (in/out functions and operators).
The advantages are:
- The ability to reliably reset the values.
- A somewhat self-healing nature in the presence of lost changes, which doesn't happen in a cluster that operates properly.
- The ability to receive changes from other than source nodes.
Consider, for example, that a value is modified on node A, and the change gets replicated to B but not C due to network issue between A and C. If B modifies the value and this change gets replicated to C, it includes even the original change from A. With operation-based CRDTs, node C doesn't receive the change until the A-C network connection starts working again.
The main disadvantages of CvCRDTs are higher costs in terms of disk space and CPU usage. A bit of information for each node is needed, including nodes that were already removed from the cluster. The complex nature of the state (serialized into varlena types) means increased CPU use.