Conflict-free replicated data types are data structures that can be replicated over multiple computers in a network, where replicas can be updated independently and concurrently without coordination between the replicas.
Code in this repository implements stl-like set, map and multi-value register as a header only library. The stl interface was chosen as a standard, yet the code definitely does not met all stl requirements for the containers. Merging algorithm is based on the article "An Optimized Conflict-free Replicated Set".
This algorithm was chosen for its elegance and optimization - the crdt structure keeps minimal amount of metadata and can shrink during erase operations. The algorithm also looked super simple to implement yet that turned into quite an interesting excercise.
In a nutshell, CRDT type needs to hold additional metadata related to operations that mutate the data structure so it can resolve the conflicts later when state between replicas is synchronzied. The algorithm is able to drop metadata that was observed by other replicas and is no longer required to resolve the conflicts or the metadata thats effects are no longer observable because of other operations.
Any operation on CRDT data type is done through 'merging' of CRDT types.
Lets say we want to add an element E to the set S: we create an empty set D (delta) and add element E there. We merge set S with D. S now contains E. This allows us to distribute the delta D to other replicas that will perform the same merge operation. We can distribute it now or later, but the modifications comming from single replica needs to be ordered. This approach allows for buffering the changes naturally, we simply do all modifications to D and when we are done, we just merge (again, does not matter if we merge localy or on remote replicas) with latest version of D. So if ten elements are added, five of them deleted, final version that will be distributed will contain just the remaining five elements. If we add millions of elements and delete them all, we will distribute just the 'deletion', not the addition, as the effect of the deletion hides the effect of the addition. The erasure works similarily: we create empty set D, perform erasure of E, merge with S. S now does not have the element E.
Algorithm for conflict-free merging and base implementation for stl-like containers is in crdtr::detail::dot_kernel. This allows types that have different implementations to be merged together. The dot_kernel class uses tags to select concrete representation for convenience. Currently, set and map operations are implemented as merges with stack-based temporary crdt types and different implementations exist for performance testing:
- crdt::detail::dot_kernel_metadata_stl - implemented using std::set and std::map
- crdt::detail::dot_kernel_metadata_btree - implemented using btree::set and btree::map
- crdt::detail::dot_kernel_metadata_flat - implemented using boost's flat_set and flat_map.
The general idea is that it should be possible to merge in-memory crdt type with on-disk crdt type efficiently and using the same algorithm, without imposing restrictions on size of the data. Or it should be possible to have classes with local metadata and merge them into classes with shared metadata to lower memory requirements.
- crdt::set - stl-like set
- crdt::map - stl-like map
- crdt::value_mv - multi-value register
It is hard to give any numbers right now as there are some unexplained and significant differences between msvc/clang compilers and windows/linux systems, yet fastest crdt implementation seems to be the one based on btree and the performance of random insertion into crdt::set with btree is roughly 6x slower than random insertion into the std::set (with stock memory allocators). btree is consistently 2x faster than stl implementation. Implementation using flat data structures is comparable to btree, yet suffers for large N.
Here they are.
Thank you, interested reader.
As the structures are recursive and the combination of CRDT structures is again a CRDT structure, graphs emerge naturally, or one can imagine json documents, all having the deterministic merging ability on all their fields, perhaps defined by user-selected merge strategy (observed remove, last write wins, etc), mapped from the persistent storage.