CRDTs - Conflict-Free Replicated Data Types for OCaml

A CRDT (or Conflict-Free Replicated Data Type) is a data type designed to satisfy the Strong Eventual Consistency model.

In other words, given a set of replicas of the same data type, and a number of operations independently applied to any replica, all replicas will eventually reach the same state, no matter the order of the operations.

These properties make CRDTs extremely useful for distributed KV stores and collaborative applications, among others.

Further Reading:

• Conflict-free replicated data types
• A comprehensive study of Convergent and Commutative Replicated Data Types

Datatypes

Included data types are:

• IntVector : An Integer Vector.

• GCounter : A grow-only counter.

• PNCounter : A counter implementing both increment and decrement operations.

• GSet : A grow-only set.

• USet : A set supporting both add and remove operations. ¹

• ORSet : A set supporting both add and remove operations.

Unless stated otherwise, all implementations come in mutable (Crdt.Mutable) and immutable (Crdt.Immutable) flavours.

Please note that the current implementations are designed only for educational purposes. Don't use them for any serious work.

1: Removed elements can never be added again. Use an ORSet if you want to be able to add removed elements again. Read the reasoning in the documentation.

Installing

Using opam:

opam install crdt-ml

Or you can install from source:

make && make install

To try the library in a repl, open an ocaml toplevel and require it:

# #use "topfind";;
# #require "crdt";;

To link it, compile your files using ocamlbuild:

ocamlbuild -use-ocamlfind -pkgs crdt <your-file>

Run the tests:

make test

The tests depend on iTeML. You can install it with opam install qtest.

You can also choose to use just a certain part of the library. To do so, link or load the submodule you want:

• crdt_mutable - Mutable implementations.
• crdt_immutable - Immutable implementations.

Usage

For a simple increment / decrement counter:

open Crdt.Mutable.PNCounter

let a = make () and
    b = make ()

incr a
incr a

query a
- : int = 2

decr b
merge a b

query a
- : int = 1

Using an USet:

module StrSet = Crdt.Mutable.USet.Make (String)

open StrSet

let s1 = make () and
    s2 = make ()

add "I" s1
add "Love" s1

add "Pancakes" s2
add "Yeah!" s1

merge s1 s2
merge s2 s1

value s1
- : bytes list = ["I"; "Love"; "Pancakes"; "Yeah!"]

remove "Yeah!" s2
merge s1 s2

value s1
- : bytes list = ["I"; "Love"; "Pancakes"]

value s2
- : bytes list = ["I"; "Love"; "Pancakes"]

Documentation

Check out the online documentation for more. The documentation and the API reference are automatically generated by ocamldoc from the interfaces.

You can generate your own local documentation running make doc.

License

GPLv3. Check the License.