crdt

package module
Version: v0.0.0-...-68acdd7 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 28, 2016 License: MIT Imports: 5 Imported by: 0

README

CRDT Build Status Coverage Status GoDoc Report card

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

View Source
var (
	ErrNoSuchBias = errors.New("no such bias found")
)

Functions

This section is empty.

Types

type BiasType

type BiasType string
const (
	BiasAdd    BiasType = "a"
	BiasRemove BiasType = "r"
)

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

func (g *GCounter) Count() (total int)

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

func (g *GCounter) IncVal(incr int)

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) Merge

func (g *GCounter) Merge(c *GCounter)

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.

type GSet

type GSet struct {
	// contains filtered or unexported fields
}

Gset is a grow-only set.

func NewGSet

func NewGSet() *GSet

NewGSet returns an instance of GSet.

func (*GSet) Add

func (g *GSet) Add(elem interface{})

Add lets you add an element to grow-only set.

func (*GSet) Contains

func (g *GSet) Contains(elem interface{}) bool

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) Len

func (g *GSet) Len() int

Len returns the no. of elements present within GSet.

func (*GSet) MarshalJSON

func (g *GSet) MarshalJSON() ([]byte, error)

MarshalJSON will be used to generate a serialized output of a given GSet.

type LWWSet

type LWWSet struct {
	// contains filtered or unexported fields
}

func NewLWWSet

func NewLWWSet() (*LWWSet, error)

func NewLWWSetWithBias

func NewLWWSetWithBias(bias BiasType) (*LWWSet, error)

func (*LWWSet) Add

func (s *LWWSet) Add(value interface{})

func (*LWWSet) Contains

func (s *LWWSet) Contains(value interface{}) bool

func (*LWWSet) MarshalJSON

func (s *LWWSet) MarshalJSON() ([]byte, error)

func (*LWWSet) Merge

func (s *LWWSet) Merge(r *LWWSet)

func (*LWWSet) Remove

func (s *LWWSet) Remove(value interface{})

type ORSet

type ORSet struct {
	// contains filtered or unexported fields
}

func NewORSet

func NewORSet() *ORSet

func (*ORSet) Add

func (o *ORSet) Add(value interface{})

func (*ORSet) Contains

func (o *ORSet) Contains(value interface{}) bool

func (*ORSet) Merge

func (o *ORSet) Merge(r *ORSet)

func (*ORSet) Remove

func (o *ORSet) Remove(value interface{})

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

func (pn *PNCounter) Count() int

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

func (pn *PNCounter) DecVal(decr int)

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.

func (*PNCounter) IncVal

func (pn *PNCounter) IncVal(incr int)

IncVal increments the current value of the PN-Counter by the delta incr that is provided. The value of delta has to be >= 0. If the value of delta is < 0, then this implementation panics.

func (*PNCounter) Merge

func (pn *PNCounter) Merge(pnpn *PNCounter)

Merge combines both the PN-Counters and saves the result in the invoking counter. Respective G-Counters are merged i.e. +ve with +ve and -ve with -ve, but not computation is actually performed.

type Set

type Set interface {
	Add(interface{})
	Contains(interface{}) bool
}

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL