This repository implements and tests several state-based conflict free replicated data types (CRDTs).
The repository contains three directories:
core
including basic data types that are used in implementing CRDTs,statebased
containing the implementation of state based CRDTs, andtest
including test suites for both basic data types and state based CRDTs.
The statebased folder also provides the development guide of using implemented CRDTs. For source code examples of using CRDTs look at the test folder.
We use Google Test for testing.
Script setup.sh
from the root folder of this repository installs Google Test.
sudo ./setup.sh
Run test.sh
from the root folder of this repository to test the entire implementation.
This script compiles the repository, places the compiled files in the folder install
, and
creates and executes a binary file crdts_test
that runs test cases. Run the following to test the repository:
./test.sh
The repository implements a last writer wins register, an optimized observed removed set, and a add wins observed removed map.
A LWWRegister is a variant of a register, i.e., a memory cell that stores a value [1]. A LWWRegister exposes the following operations:
value
that queries the most recent value of the local LWWRegister object,assign
that assigns a given value to the local LWWRegister object, andmerge
that "merges" a LWWRegister received at a downstream replica with the local LWWRegister object.
An optimized observed removed set (ORSet) [2] is a variant of set, that is, a collection of unique elements.
A set exposes the following operations:
add
that add an element to to the local ORSet object,remove
that removes an element from the local ORSet object,contains
that queries the existence of a given element in the local ORSet object, andmerge
that merges an ORSet received at a downstream replica with the local ORSet object.
Map implements a convergent key value store. A map exposes the following operations,
get
that returns a value associated to a given key,contains
that checks the existence of a given key,put
that takes a key and value and add them to the map,remove
that deletes a given key and its associated value, andmerge
that merges a map received at a downstream replica with the local object.
[1] Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011, October). Conflict-free replicated data types. In Symposium on Self-Stabilizing Systems (pp. 386-400). Springer, Berlin, Heidelberg.
[2] Bieniusa A, Zawirski M, Preguiça N, Shapiro M, Baquero C, Balegas V, Duarte S. (2012). An optimized conflict-free replicated set arXiv preprint arXiv:1210.3368.