README
¶
CRDT 
This is an implementation of Convergent and Commutative Replicated Data Types in Go.
The following state-based counters and sets have currently been implemented.
Counters
G-Counter
A grow-only counter (G-Counter) can only increase in one direction. The increment operation increases the value of current replica by 1. The merge operation combines values from distinct replicas by taking the maximum of each replica.
gcounter := crdt.NewGCounter()
// We can increase the counter monotonically by 1.
gcounter.Inc()
// Twice.
gcounter.Inc()
// Or we can pass in an arbitrary delta to apply as an increment.
gcounter.IncVal(2)
// Should print '4' as the result.
fmt.Println(gcounter.Count())
PN-Counter
A positive-negative counter (PN-Counter) is a CRDT that can both increase or
decrease and converge correctly in the light of commutative
operations. Both .Inc() and .Dec() operations are allowed and thus
negative values are possible as a result.
pncounter := crdt.NewPNCounter()
// We can increase the counter by 1.
pncounter.Inc()
// Or more.
pncounter.Inc(100)
// And similarly decrease its value by 1.
pncounter.Dec()
// Or more.
pncounter.DecVal(100)
// End result should equal '0' here.
fmt.Println(pncounter.Count())
Sets
G-Set
A grow-only (G-Set) set to which element/s can be added to. Removing element from the set is not possible.
obj := "dummy-object"
gset := crdt.NewGSet()
gset.Add(obj)
// Should always print 'true' as `obj` exists in the g-set.
fmt.Println(gset.Contains(obj))
2P-Set
Two-phase set (2P-Set) allows both additions and removals to the set. Internally it comprises of two G-Sets, one to keep track of additions and the other for removals.
obj := "dummy-object"
ppset := crdt.NewTwoPhaseSet()
ppset.Add(obj)
// Remove the object that we just added to the set, emptying it.
ppset.Remove(obj)
// Should return 'false' as the obj doesn't exist within the set.
fmt.Println(ppset.Contains(obj))
LWW-e-Set
Last-write-wins element set (LWW-e-Set) keeps track of element additions and removals but with respect to the timestamp that is attached to each element. Timestamps should be unique and have ordering properties.
obj := "dummy-object"
lwwset := crdt.NewLWWSet()
// Here, we remove the object first before we add it in. For a
// 2P-set the object would be deemed absent from the set. But for
// a LWW-set the object should be present because `.Add()` follows
// `.Remove()`.
lwwset.Remove(obj); lwwset.Add(obj)
// This should print 'true' because of the above.
fmt.Println(lwwset.Contains(obj))
OR-Set
An OR-Set (Observed-Removed-Set) allows deletion and addition of elements similar to LWW-e-Set, but does not surface only the most recent one. Additions are uniquely tracked via tags and an element is considered member of the set if the deleted set consists of all the tags present within additions.
// object 1 == object 2
obj1, obj2 := "dummy-object", "dummy-object"
orset := crdt.NewORSet()
orset.Add(obj1); orset.Add(obj2)
// Removing any one of the above two objects should remove both
// because they contain the same value.
orset.Remove(obj1)
// Should return 'false'.
fmt.Println(orset.Contains(obj2))
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var (
ErrNoSuchBias = errors.New("no such bias found")
)
Functions ¶
This section is empty.
Types ¶
type GCounter ¶
type GCounter struct {
// contains filtered or unexported fields
}
GCounter represent a G-counter in CRDT, which is a state-based grow-only counter that only supports increments.
func NewGCounter ¶
func NewGCounter() *GCounter
NewGCounter returns a *GCounter by pre-assigning a unique identity to it.
func (*GCounter) Count ¶
Count returns the total count of this counter across all the present replicas.
func (*GCounter) Inc ¶
func (g *GCounter) Inc()
Inc increments the GCounter by the value of 1 everytime it is called.
func (*GCounter) IncVal ¶
IncVal allows passing in an arbitrary delta to increment the current value of counter by. Only positive values are accepted. If a negative value is provided the implementation will panic.
func (GCounter) MarshalJSON ¶
MarshalJSON implements Marshaller on GCounter via a `jsonGCounter`
func (*GCounter) Merge ¶
Merge combines the counter values across multiple replicas. The property of idempotency is preserved here across multiple merges as when no state is changed across any replicas, the result should be exactly the same everytime.
func (*GCounter) UnmarshalJSON ¶
UnmarshalJSON implements unmarshaller on GCounter via a `jsonGCounter`
type GSet ¶
type GSet struct {
// contains filtered or unexported fields
}
Gset is a grow-only set.
func (*GSet) Add ¶
func (g *GSet) Add(elem interface{})
Add lets you add an element to grow-only set.
func (*GSet) Contains ¶
Contains returns true if an element exists within the set or false otherwise.
func (*GSet) Elems ¶
func (g *GSet) Elems() []interface{}
Elems returns all the elements present in the set.
func (*GSet) MarshalJSON ¶
MarshalJSON will be used to generate a serialized output of a given GSet.
type LWWSet ¶
type LWWSet struct {
// contains filtered or unexported fields
}
func NewLWWSetWithBias ¶
func (*LWWSet) MarshalJSON ¶
type PNCounter ¶
type PNCounter struct {
// contains filtered or unexported fields
}
PNCounter represents a state-based PN-Counter. It is implemented as sets of two G-Counters, one that tracks increments while the other decrements.
func NewPNCounter ¶
func NewPNCounter() *PNCounter
NewPNCounter returns a new *PNCounter with both its G-Counters initialized.
func (*PNCounter) Count ¶
Count returns the current value of the counter. It subtracts the value of negative G-Counter from the positive grow-only counter and returns the result. Because this counter can grow in either direction, negative integers as results are possible.
func (*PNCounter) Dec ¶
func (pn *PNCounter) Dec()
Dec monotonically decrements the current value of the PN-Counter by one.
func (*PNCounter) DecVal ¶
DecVal adds a decrement to the current value of PN-Counter by the value of delta decr. Similar to IncVal, the value of decr cannot be less than 0.
func (*PNCounter) Inc ¶
func (pn *PNCounter) Inc()
Inc monotonically increments the current value of the PN-Counter by one.
type TwoPhaseSet ¶
type TwoPhaseSet struct {
// contains filtered or unexported fields
}
TwoPhaseSet supports both addition and removal of elements to set.
func NewTwoPhaseSet ¶
func NewTwoPhaseSet() *TwoPhaseSet
NewTwoPhaseSet returns a new instance of TwoPhaseSet.
func (*TwoPhaseSet) Add ¶
func (t *TwoPhaseSet) Add(elem interface{})
Add inserts element into the TwoPhaseSet.
func (*TwoPhaseSet) Contains ¶
func (t *TwoPhaseSet) Contains(elem interface{}) bool
Contains returns true if the set contains the element. The set is said to contain the element if it is present in the add-set and not in the remove-set.
func (*TwoPhaseSet) MarshalJSON ¶
func (t *TwoPhaseSet) MarshalJSON() ([]byte, error)
MarshalJSON serializes TwoPhaseSet into an JSON array.
func (*TwoPhaseSet) Remove ¶
func (t *TwoPhaseSet) Remove(elem interface{})
Remove deletes the element from the set.
Source Files