delta_crdt v0.5.9 DeltaCrdt
Start and interact with the Delta CRDTs provided by this library.
A CRDT is a conflict-free replicated data-type. That is to say, it is a distributed data structure that automatically resolves conflicts in a way that is consistent across all replicas of the data. In other words, your distributed data is guaranteed to eventually converge globally.
Normal CRDTs (otherwise called “state CRDTs”) require transmission of the entire CRDT state with every change. This clearly doesn’t scale, but there has been exciting research in the last few years into “Delta CRDTs”, CRDTs that only transmit their deltas. This has enabled a whole new scale of applications for CRDTs, and it’s also what this library is based on.
A Delta CRDT is made of two parts. First, the data structure itself, and second, an anti-entropy algorithm, which is responsible for ensuring convergence. DeltaCrdt
implements Algorithm 2 from “Delta State Replicated Data Types – Almeida et al. 2016” which is an anti-entropy algorithm for δ-CRDTs. DeltaCrdt
also implements join decomposition to ensure that deltas aren’t transmitted unnecessarily in the cluster.
While it is certainly interesting to have a look at this paper and spend time grokking it, in theory I’ve done the hard work so that you don’t have to, and this library is the result.
With this library, you can build distributed applications that share some state. Horde.Supervisor
and Horde.Registry
are both built atop DeltaCrdt
, but there are certainly many more possibilities.
Here’s a simple example for illustration:
iex> {:ok, crdt1} = DeltaCrdt.start_link(DeltaCrdt.AWLWWMap, sync_interval: 3)
iex> {:ok, crdt2} = DeltaCrdt.start_link(DeltaCrdt.AWLWWMap, sync_interval: 3)
iex> DeltaCrdt.set_neighbours(crdt1, [crdt2])
iex> DeltaCrdt.set_neighbours(crdt2, [crdt1])
iex> DeltaCrdt.read(crdt1)
%{}
iex> DeltaCrdt.mutate(crdt1, :add, ["CRDT", "is magic!"])
iex> Process.sleep(10) # need to wait for propagation for the doctest
iex> DeltaCrdt.read(crdt2)
%{"CRDT" => "is magic!"}
Link to this section Summary
Functions
Include DeltaCrdt in a supervision tree with {DeltaCrdt, [crdt: DeltaCrdt.AWLWWMap, name: MyCRDTMap]}
Mutate the CRDT synchronously
Mutate the CRDT asynchronously
Read the state of the CRDT
Notify a CRDT of its neighbours
Start a DeltaCrdt and link it to the calling process
Link to this section Types
crdt_option() :: {:on_diffs, ([diff()] -> any())} | {:sync_interval, pos_integer()} | {:max_sync_size, pos_integer() | :infinite} | {:storage_module, DeltaCrdt.Storage.t()}
Link to this section Functions
Include DeltaCrdt in a supervision tree with {DeltaCrdt, [crdt: DeltaCrdt.AWLWWMap, name: MyCRDTMap]}
mutate( crdt :: GenServer.server(), function :: atom(), arguments :: list(), timeout :: timeout() ) :: :ok
Mutate the CRDT synchronously.
For the asynchronous version of this function, see mutate_async/3
.
To see which operations are available, see the documentation for the crdt module that was provided in start_link/3
.
For example, DeltaCrdt.AWLWWMap
has a function add
that takes 4 arguments. The last 2 arguments are supplied by DeltaCrdt internally, so you have to provide only the first two arguments: key
and val
. That would look like this: DeltaCrdt.mutate(crdt, :add, ["CRDT", "is magic!"])
. This pattern is repeated for all mutation functions. Another exaple: to call DeltaCrdt.AWLWWMap.clear
, use DeltaCrdt.mutate(crdt, :clear, [])
.
mutate_async( crdt :: GenServer.server(), function :: atom(), arguments :: list() ) :: :ok
Mutate the CRDT asynchronously.
read(crdt :: GenServer.server(), timeout :: timeout()) :: crdt_state :: term()
Read the state of the CRDT.
set_neighbours(crdt :: GenServer.server(), neighbours :: [GenServer.server()]) :: :ok
Notify a CRDT of its neighbours.
This function allows CRDTs to communicate with each other and sync their states.
Note: this sets up a unidirectional sync, so if you want bidirectional syncing (which is normally desirable), then you must call this function twice (or thrice for 3 nodes, etc):
DeltaCrdt.set_neighbours(c1, [c2, c3])
DeltaCrdt.set_neighbours(c2, [c1, c3])
DeltaCrdt.set_neighbours(c3, [c1, c2])
start_link(crdt_module :: module(), opts :: crdt_options()) :: GenServer.on_start()
Start a DeltaCrdt and link it to the calling process.
There are a number of options you can specify to tweak the behaviour of DeltaCrdt:
:notify
- when the state of the CRDT has changed,msg
will be sent topid
. Varyingmsg
allows a single process to listen for updates from multiple CRDTs.:sync_interval
- the delta CRDT will attempt to sync its local changes with its neighbours at this interval. Default is 50.