A golang package implementing a number of CRDT primitives
NOTE This has been extracted from Pith and doesn't even have a Makefile yet.
- Achieving Convergence, Causality-Preservation, and Intention-Preservation in Real-Time Cooperative Editing Systems, Sun et. al. 1998
- A Comprehensive Study of Convergent and Commutative Replicated Data Types, Shapiro et. al. 2011
- Strong Eventual Consistency and Conflict-free Replicated Data Types, video by Marc Shapiro
- CRDT Notes, by pfrazee. These summarise stuff from the other references.
- The bluffers guide to CRDTs in Riak
- Key-CRDT Stores, design and implementation of SwiftCloud, a Key-CRDT store that extends a Key-Value store by incorporating CRDTs in the system’s data-mode
- Overview of 'A comprehensive study of Convergent and Commutative Replicated Data Types', from [https://blog.acolyer.org](The Morning Paper)
- Overview of 'Delta State Replicated Data Types', from [https://blog.acolyer.org](The Morning Paper)
- Eventually Consistent Data Structures, from strangeloop12 by Sean Cribbs
- Dotted Version Vector Sets
- https://blog.acolyer.org/2016/04/25/delta-state-replicated-data-types/
- https://arxiv.org/pdf/1603.01529.pdf
A Grow-Only counter. It can increment, but not decrement. the merge operation takes the maximum value from every replica. It cannot represent negative values.
Operations:
- Incr() Increment the counter by 1
- IncrBy(N) Increment the counter by N
A Positive-Negative counter can both increase and decrease. The merge operation will cause the counter to converge to the correct final value. This counter can represent negative numbers
Operations:
- Incr() Increment the counter by 1
- IncrBy(N) Increment the counter by N
- Decr() Decrement the counter by 1
- DecrBy(N) Decrement the counter by N
A Grow-Only set can add values, but not remove them. Once an element is in the set it's there for good.
Operations:
- Add(VALUE) Add VALUE to the set
- Contains(VALUE) Indicates whether VALUE is in the set
- Cardinality() int Returns the set element count
- Values() []string Returns the elements in the set as an array of strings
A Two-Phase set consists of two G-Sets; one to track additions and another for removals.
Operations:
- Add(VALUE) Add VALUE to the set
- Remove(VALUE) Remove VALUE from the set
- Contains(VALUE) Indicates whether VALUE is in the set
- Cardinality() int Returns the set element count
- Values() []string Returns the elements in the set as an array of strings
Removed values can never be re-added to a 2P-Set. For example:
set := rapport.CreateTwoPhaseSet()
set.Add("Foo")
set.Contains("Foo") // true
set.Remove("Foo")
set.Contains("Foo") // false
set.Add("Foo")
set.Contains("Foo") // still falseA Last-Write-Wins element set keeps track of additions and removals, and the relative order of both by using timestamps attached to each value. Each timestamp must be unique and the ordering can be unstable if there's too much disagreement between each replicas clock.
Operations:
- Add(VALUE) Add VALUE to the set
- Remove(VALUE) Remove VALUE from the set
- Contains(VALUE) Indicates whether VALUE is in the set
- Cardinality() int Returns the set element count
- Values() []string Returns the elements in the set as an array of strings
Like the LWW-e-Set, a Observed-Removed set tracks additions and removals. Rather than using a timestamp the OR-set tracks the set of added and removed values, or rather unique ids that stand in for values. A value is in the set if a value if the deleted set does not contain all the unique ids for value that are in the added set.
Operations:
- Add(VALUE) Add VALUE to the set
- Remove(VALUE) Remove VALUE from the set
- Contains(VALUE) Indicates whether VALUE is in the set
- Cardinality() int Returns the set element count
- Values() []string Returns the elements in the set as an array of strings
A Add-Wins set, aka an OR-Set Without Tombstones, was first implemented in Riak (afaik). It's the first of the listed sets that is generally useful. It has less overhead and produces less garbage than a OR-Set.
- Add(VALUE) Add VALUE to the set
- Remove(VALUE) Remove VALUE from the set
- Contains(VALUE) Indicates whether VALUE is in the set
- Cardinality() int Returns the set element count
- Values() []string Returns the elements in the set as an array of strings
https://syncfree.lip6.fr/index.php/2-uncategorised/53-big-sets
If you imagine a dictionary of key/value pairs then a register is the slot that the key names and that the value goes into.
Last-Writer-Wins Register uses a timestamp to decide which replica values are newest during merge operations.
Note that timestamp might actually be a logical time of some sort. If it isn't a logical time then it will suffer from the usual problems of time in a distributed system.
https://hal.archives-ouvertes.fr/inria-00432368/document
http://hal.univ-nantes.fr/file/index/docid/921633/filename/fp025-nedelec.pdf
https://github.com/nkohari/kseq/blob/master/README.md
A Add-Wins Map