crdt

package module
v0.0.0-...-cf7aa53 Latest Latest
Warning

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

 Go to latest Published: May 12, 2024 License: MIT Imports: 3 Imported by: 0

README

crdt

Go Report Card

A go implementation of State-based Conflict-free Replicated Data Types, modeled after the data types outlined in A comprehensive study of Convergent and Commutative Replicated Data Types.

To-Do's

  • Fix 2P2P-Graph removeVertex and Merge

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type GCounter 

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

GCounter is a CRDT counter that can only be incremented.

func NewGCounter 

func NewGCounter(name string, node string) *GCounter

NewGCounter constructs a GCounter based on the parameters provided. The GCounter will be initialized to a value of 0. It is assumed the name of this specific GCounter uniquely identifies this counter throughout the cluster.

func (*GCounter) Increment 

func (counter *GCounter) Increment()

Increment increments this counter by 1.

func (*GCounter) Merge 

func (counter *GCounter) Merge(that *GCounter)

Merge performs an idempotent operation which combines that with counter. The maximum value for each value in values is set to each counter.values. This is an idempotent operation and is a no-op if counter.name != that.name.

func (*GCounter) Value 

func (counter *GCounter) Value() int

Value returns the current value of this counter.

type GSet 

type GSet[T comparable] struct {
	// contains filtered or unexported fields
}

GSet is a CRDT set in which elements can only be added to it. The types of elements (T) must be set on initialization.

func NewGSet 

func NewGSet[T comparable](name string) *GSet[T]

NewGSet constructs a GSet with the associated name. It is assumed the name of this specific GSet uniquely identifies this set throughout the cluster.

func (*GSet[T]) Add 

func (gset *GSet[T]) Add(value T)

Add adds the specified value to the set. Is a no-op if the value has ever previously been added to the set.

func (*GSet[T]) Lookup 

func (gset *GSet[T]) Lookup(value T) (exists bool)

Lookup reports whether the T value exists within the set.

func (*GSet[T]) Merge 

func (gset *GSet[T]) Merge(that *GSet[T])

Merge adds all elements in that.set to gset.set. This is an idempotent operation and is a no-op if gset.name != that.name.

func (*GSet[T]) Size 

func (gset *GSet[T]) Size() int

Size returns number of elements that currently exist within the set.

type LWWESet 

type LWWESet[T comparable] struct {
	// contains filtered or unexported fields
}

LWWESet is a CRDT set in which each element has a timestamp associated with it. A last-writer-wins implementation is used to determine whether an element exists within the set or not. The integer `time.Now().UnixNano()` is used to identify a total ordering of updates and is assumed to be universal across all replicas of this LWWESet. The types of elements (T) must be set on initialization.

func NewLWWESet 

func NewLWWESet[T comparable](name string) *LWWESet[T]

NewLLWESet constructs an empty LWWESet with the associated name. It is assumed the name of this specific LWWESet uniquely identifies this set throughout the cluster.

func (*LWWESet[T]) Add 

func (lwweSet *LWWESet[T]) Add(value T)

Add adds the specified value to the set (i.e., its timestamp in the addSet gets updated to now).

func (*LWWESet[T]) Lookup 

func (lwweSet *LWWESet[T]) Lookup(value T) bool

Lookup reports whether the T value exists within the set. An element exists within the set if its timestamp in the addSet is greater than its timestamp in the removeSet.

func (*LWWESet[T]) Merge 

func (lwweSet *LWWESet[T]) Merge(that *LWWESet[T])

Merge adds all elements in that.addSet and that.removeSet to lwweSet.addSet and llweSet.removeSet respectively, accounting for colissions by storing the most recent of the two timestamps. This is an idempotent operation and is a no-op if lwweSet.name != that.name.

func (*LWWESet[T]) Remove 

func (lwweSet *LWWESet[T]) Remove(value T)

Remove removes the specified value from the set (i.e., its timestamp in the removeSet gets updated to now). This is a no-op if the value has never been added to the set previously.

func (*LWWESet[T]) Size 

func (lwweSet *LWWESet[T]) Size() int

Size returns the number of elements currently within the set.

type LWWRegister 

type LWWRegister[T any] struct {
	// contains filtered or unexported fields
}

LWWRegister is a CRDT register that holds the most recent value that was assigned to it. The integer `time.Now().UnixNano()` is used to identify a total ordering of assignments and is assumed to be universal across all replicas of this LWWRegister.

func NewLWWRegister 

func NewLWWRegister[T any](name string, value T) *LWWRegister[T]

NewLWWRegister constructs a LWWRegister with an initial value of value. The name of the register is assumed to be unique across the cluster this register exists in.

func (*LWWRegister[T]) Assign 

func (reg *LWWRegister[T]) Assign(value T)

Assign sets the value of this register to the parameter and updates the timestamp to `time.Now().UnixNano()`.

func (*LWWRegister[T]) Merge 

func (reg *LWWRegister[T]) Merge(that *LWWRegister[T])

Merge will assign the value and timetamp in that to reg if and only if reg.name == that.name AND reg.timestamp < that.timestamp. This is an idempotent operation.

func (*LWWRegister[T]) Value 

func (reg *LWWRegister[T]) Value() T

Value returns the current value stored in the register.

type MVRegister 

type MVRegister[T any] struct {
	// contains filtered or unexported fields
}

MVRegister is a CRDT register that holds a registerValue for each node that exists within the cluster. TODO the values of each register here could be a LWWRegister to avoid duplicating logic.

func NewMVRegister 

func NewMVRegister[T any](name string, node string, initialValue T) *MVRegister[T]

NewMVRegister constructs a MVRegister with a value for this node set to initialValue. It is assumed the name of this specific MVRegister uniquely identifies this register throughout the cluster.

func (*MVRegister[T]) Assign 

func (reg *MVRegister[T]) Assign(value T)

Assign sets the value in the parameter to the value of the register for this node.

func (*MVRegister[T]) Merge 

func (reg *MVRegister[T]) Merge(that *MVRegister[T])

Merge sets the value of each node's register using a last-writer-wins implementation. This is an idempotent operation and is a no-op if reg.name != that.name.

func (*MVRegister[T]) Value 

func (reg *MVRegister[T]) Value() map[string]T

Value returns a map of node -> value for each node in the cluster.

type ORSet 

type ORSet[T comparable] struct {
	// contains filtered or unexported fields
}

ORSet is a CRDT set in which specific elements that are added to the set are given a unique ID that must be removed explicitly for an element to be perceived as not being in the set. The types of elements (T) must be set on initialization.

func NewORSet 

func NewORSet[T comparable](name string) *ORSet[T]

NewORSet constructs an empty ORSet with the associated name. It is assumed the name of this specific ORSet uniquely identifies this set throughout the cluster.

func (*ORSet[T]) Add 

func (orset *ORSet[T]) Add(value T)

Add adds the specified value to the set. Functionally, this creates a new unique ID and adds it to this element's List of currently added IDs.

func (*ORSet[T]) Lookup 

func (orset *ORSet[T]) Lookup(value T) bool

Lookup reports whether T value exists within the set.

func (*ORSet[T]) Merge 

func (orset *ORSet[T]) Merge(that *ORSet[T])

Merge performs the following three actions:

  • Add all elements (and their unique IDs) from that.set to orset.set
  • Add all elements (and their unique IDs) from that.tombstone to orset.tombstone
  • Remove all elements from orset.set if all their unique IDs exist within orset.tombstone

This is an idempotent operation and is a no-op if orset.name != that.name.

func (*ORSet[T]) Remove 

func (orset *ORSet[T]) Remove(value T)

Remove removes the specified value from the set. Functionally, this adds all unique IDs for the specified value in orset.set to orset.tombstone and removes them from orset.set.

func (*ORSet[T]) Size 

func (orset *ORSet[T]) Size() int

Size returns the number of elements that currently exist within the set.

type PNCounter 

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

PNCounter is a CRDT counter that can both increase and decrease in value.

func NewPNCounter 

func NewPNCounter(name string, node string) *PNCounter

NewPNCounter constructs a new PNCounter with the associated name and an initial value of 0. It is assumed the name of this specific PNCounter uniquely identifies this counter throughout the cluster.

func (*PNCounter) Decrement 

func (counter *PNCounter) Decrement()

Decrement decreases the value of this counter by 1.

func (*PNCounter) Increment 

func (counter *PNCounter) Increment()

Increment increases the value of this counter by 1.

func (*PNCounter) Merge 

func (counter *PNCounter) Merge(that *PNCounter)

Merge performs an idempotent operation of which each GCounter in counter is merged with its counterpart in that. This is an idempotent operation and is a no-op if counter.name != that.name.

func (*PNCounter) Value 

func (counter *PNCounter) Value() int

Value returns the current value of this counter.

type PNSet 

type PNSet[T comparable] struct {
	// contains filtered or unexported fields
}

PNSet is a CRDT set in which each element can be added/removed from the set. Uses a PNCounter that is assumed to have only one node to abstract additions and removals of elements from the set. Note, it is possible for a no-op add to occur if two nodes remove the same element from the set and are then merged again, making the counter equal to -1. The types of elements (T) must be set on initialization.

func NewPNSet 

func NewPNSet[T comparable](name string) *PNSet[T]

NewPNSet constructs a PNSet with the associated name. It is assumed the name of this specific PNSet uniquely identifies this set throughout the cluster.

func (*PNSet[T]) Add 

func (pnset *PNSet[T]) Add(value T)

Add adds the specified value to the set (i.e., its counter is incremented by 1).

func (*PNSet[T]) Lookup 

func (pnset *PNSet[T]) Lookup(value T) bool

Lookup reports whether the T value exists within the set.

func (*PNSet[T]) Merge 

func (pnset *PNSet[T]) Merge(that *PNSet[T])

Merge adds all elements in that.set to pnset.set that did not exist previously, and merges the counters for each element that exists in both. This is an idempotent operation and is a no-op if pnset.name != that.name.

func (*PNSet[T]) Remove 

func (pnset *PNSet[T]) Remove(value T)

Remove removes the specified value from the set (i.e., its counter is decremented by 1). This is functionally a no-op if value does not exist in the set.

func (*PNSet[T]) Size 

func (pnset *PNSet[T]) Size() int

Size returns the number of elements that currently exist within the set.

type Register 

type Register[T any] interface {
	Get() T
	Set(T)
	Merge(*Register[T])
}

type TwoPhaseGraph 

type TwoPhaseGraph[T comparable] struct {
	// contains filtered or unexported fields
}

TwoPhaseGraph is a CRDT graph in which edges and vertexes can only be added or removed once throughout the lifetime of the graph.

func NewTwoPhaseGraph 

func NewTwoPhaseGraph[T comparable](name string) *TwoPhaseGraph[T]

NewTwoPhaseGraph constructs a TwoPhaseGraph with the provided name. It is assumed the name of this specific TwoPhaseGraph uniquely identifies this register throughout the cluster.

func (*TwoPhaseGraph[T]) AddEdge 

func (graph *TwoPhaseGraph[T]) AddEdge(v1 T, v2 T)

AddEdge will add the edge v1 -> v2 iff:

  • v1 and v2 exist in the graph
  • v1 -> v2 has never been added to the graph before

func (*TwoPhaseGraph[T]) AddVertex 

func (graph *TwoPhaseGraph[T]) AddVertex(vertex T)

AddVertex will add the provided vertex to the graph if it has not been added before.

func (*TwoPhaseGraph[T]) EdgeCount 

func (graph *TwoPhaseGraph[T]) EdgeCount() int

EdgeCount returns the current number of edges that exist within the graph.

func (*TwoPhaseGraph[T]) LookupEdge 

func (graph *TwoPhaseGraph[T]) LookupEdge(v1 T, v2 T) bool

LookupEdge reports whether the provided edge v1 -> v2 currently exists within the graph or not.

func (*TwoPhaseGraph[T]) LookupVertex 

func (graph *TwoPhaseGraph[T]) LookupVertex(vertex T) bool

LookupVertex reports whether the provided vertex currently exists within the graph or not.

func (*TwoPhaseGraph[T]) Merge 

func (graph *TwoPhaseGraph[T]) Merge(that *TwoPhaseGraph[T])

Merge will merge the contents of the TwoPhaseSets vertices and edges from that to this graph. This is an idempotent operation and is a no-op if graph.name != graph.name.

func (*TwoPhaseGraph[T]) RemoveEdge 

func (graph *TwoPhaseGraph[T]) RemoveEdge(v1 T, v2 T)

RemoveEdge removes the provided edge v1 -> v2 from the graph if it currently exists within it.

func (*TwoPhaseGraph[T]) RemoveVertex 

func (graph *TwoPhaseGraph[T]) RemoveVertex(vertex T)

RemoveVertex removes the provided vertex from the graph if it currently exists within it.

func (*TwoPhaseGraph[T]) VertexCount 

func (graph *TwoPhaseGraph[T]) VertexCount() int

VertexCount returns the current number of vertices that exist within the graph.

type TwoPhaseSet 

type TwoPhaseSet[T comparable] struct {
	// contains filtered or unexported fields
}

TwoPhaseSet is a CRDT set in which an element can be added and removed only once in the lifetime of this set. This is executed by having to GSets internally, one that holds elements that have been added, the other elements that have been removed. The types of elements (T) must be set on initialization.

func NewTwoPhaseSet 

func NewTwoPhaseSet[T comparable](name string) *TwoPhaseSet[T]

NewTwoPhaseSet constructs a TwoPhaseSet with the associated name. It is assumed the name of this specific TwoPhaseSet uniquely identifies this set throughout the cluster.

func (*TwoPhaseSet[T]) Add 

func (tpset *TwoPhaseSet[T]) Add(value T)

Add adds the specified value to the set. Is a no-op if the value has ever previously been added to the set.

func (*TwoPhaseSet[T]) Lookup 

func (tpset *TwoPhaseSet[T]) Lookup(value T) bool

Lookup reports whether the T value exists within the set.

func (*TwoPhaseSet[T]) Merge 

func (tpset *TwoPhaseSet[T]) Merge(that *TwoPhaseSet[T])

Merge calls Merge on both GSets within this TwoPhaseSet. This is an idempotent operation and is a no-op if tpset.name != that.name.

func (*TwoPhaseSet[T]) Remove 

func (tpset *TwoPhaseSet[T]) Remove(value T)

Remove adds the specified value to tpset.tombstone if it exists within tpset.gset. This functionally removes it from this TwoPhaseSet forever.

func (*TwoPhaseSet[T]) RemoveIf 

func (tpset *TwoPhaseSet[T]) RemoveIf(fn func(value T) bool)

RemoveIf removes each value from this tpset if fn returns true when applied to each element currently in the set.

func (*TwoPhaseSet[T]) Size 

func (tpset *TwoPhaseSet[T]) Size() int

Size returns the number of elements that currently exist within the set.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.