Utility class for comparing timestamp and data center identifier when implementing last-writer wins.
Implements a 'Observed Remove Set' operation based CRDT, also called a 'OR-Set'.
Implements a 'Observed Remove Set' operation based CRDT, also called a 'OR-Set'. Elements can be added and removed any number of times. Concurrent add wins over remove.
It is not implemented as in the paper A comprehensive study of Convergent and Commutative Replicated Data Types. This is more space efficient and doesn't accumulate garbage for removed elements. It is described in the paper An optimized conflict-free replicated set The implementation is inspired by the Riak DT riak_dt_orswot.
The ORSet has a version vector that is incremented when an element is added to
the set. The DC -> count
pair for that increment is stored against the
element as its "birth dot". Every time the element is re-added to the set,
its "birth dot" is updated to that of the DC -> count
version vector entry
resulting from the add. When an element is removed, we simply drop it, no tombstones.
When an element exists in replica A and not replica B, is it because A added
it and B has not yet seen that, or that B removed it and A has not yet seen that?
In this implementation we compare the dot
of the present element to the version vector
in the Set it is absent from. If the element dot is not "seen" by the Set version vector,
that means the other set has yet to see this add, and the item is in the merged
Set. If the Set version vector dominates the dot, that means the other Set has removed this
element already, and the item is not in the merged Set.
This class is immutable, i.e. "modifying" methods return a new instance.
Representation of a Vector-based clock (counting clock), inspired by Lamport logical clocks.
Representation of a Vector-based clock (counting clock), inspired by Lamport logical clocks.
Reference: 1) Leslie Lamport (1978). "Time, clocks, and the ordering of events in a distributed system". Communications of the ACM 21 (7): 558-565. 2) Friedemann Mattern (1988). "Virtual Time and Global States of Distributed Systems". Workshop on Parallel and Distributed Algorithms: pp. 215-226
Based on akka.cluster.ddata.VersionVector
.
This class is immutable, i.e. "modifying" methods return a new instance.
VersionVector module with helper classes and methods.