[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

conflict-free replicated data-types

For those who are interested, I've quickly hacked an implementation of 

This is available in https://github.com/samoht/ocaml-crdt

The idea is to create new datatypes on top of Lamport's vector clocks that you 
can easily use in distributed settings because they are conflict-free 
(reminder: a vector clock is an array of integer, with size = number of actor, 
and where actor $i$ can only increment the cell number $i$: they are used to 
get some distributed timestamp and to be able to order events in a distributed 
run). For instance, you can have a distributed counter, that each actor can 
increment concurrently, and whose global state is the sum of local increments. 
These structures are sent between actors and can be synchronized easily.

What I've implemented:
- a distributed additive counter: it is just a vector clock, and it global 
state is the sum of its components
- a distributed counter: it is 2 distributed additive counters, one for the 
number of incrs, one for the number of decrs, and the global state is the 
difference of global state of these two counters
- a distributed set: you have one distributive counter per elements, and you 
can check whether an element is in a set if the global value of the counter is 
greater than 0
- a distributed map: you have one distributive set to test membership, and one 
normal map to carry the contents <- this is a bit broken currently, I might 
change that later

Currenlty, the only missing bits is a nice way to exchange distributed 
datastructes between actors. I'm using Obj.magic in 
https://github.com/samoht/ocaml-crdt/blob/master/test/main.ml, I would be quite 
happy to find an other nicer solution (but I have none in mind currently).




Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.