crdt

Documentation

Overview

Package crdt implements the operation-based observed-removed set (ORSet) structure upon that the CmRDT parts of pluto are built. Please note that for correct operation and results we expect the broadcast communication to all other replicas to be reliable and causally-ordered as provided by pluto's package comm.

The operation-based ORSet implementation of this package is a practical derivation from its specification by Shapiro, Preguiça, Baquero and Zawirski, available under: https://hal.inria.fr/inria-00555588/document

Index

• type ORSet
  • func InitORSet() *ORSet
  • func InitORSetFromFile(fileName string) (*ORSet, error)
  • func InitORSetWithFile(fileName string) (*ORSet, error)
  • func (s *ORSet) Add(e string, send sendFunc) error
  • func (s *ORSet) AddEffect(e string, tag string, needsLocking bool, needsWriteBack bool) error
  • func (s *ORSet) GetAllValues() []string
  • func (s *ORSet) Lookup(e string, needsLocking bool) bool
  • func (s *ORSet) Remove(e string, send sendFunc) error
  • func (s *ORSet) RemoveEffect(rSet map[string]string, needsLocking bool, needsWriteBack bool) error
  • func (s *ORSet) WriteORSetToFile(needsLocking bool) error

Types

type ORSet

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

ORSet conforms to the specification of an observed- removed set defined by Shapiro, Preguiça, Baquero, and Zawirski. It consists of unique IDs and data items.

func InitORSet

func InitORSet() *ORSet

InitORSet returns an empty initialized new observed-removed set.

func InitORSetFromFile

func InitORSetFromFile(fileName string) (*ORSet, error)

InitORSetFromFile parses an ORSet found in the supplied file and returns it, initialized with elements saved in file.

func InitORSetWithFile

func InitORSetWithFile(fileName string) (*ORSet, error)

InitORSetWithFile takes in a file name and initializes a new ORSet with opened file handler to that name as designated log file.

func (*ORSet) Add

func (s *ORSet) Add(e string, send sendFunc) error

Add is a helper function only to be executed at the source node of an update. It executes the prepare and effect update parts of an add operation. Afterwards, the update instruction is send downstream to all other replicas via the send function which takes care of the reliable causally-ordered broadcast.

func (*ORSet) AddEffect

func (s *ORSet) AddEffect(e string, tag string, needsLocking bool, needsWriteBack bool) error

AddEffect is the effect part of an update add operation defined by the specification. It is executed by all replicas of the data set including the source node. It inserts given element and tag into the set representation.

func (*ORSet) GetAllValues

func (s *ORSet) GetAllValues() []string

GetAllValues returns all distinct values of a supplied ORSet.

func (*ORSet) Lookup

func (s *ORSet) Lookup(e string, needsLocking bool) bool

Lookup cycles through elements in ORSet and returns true if element e is present and false otherwise.

func (*ORSet) Remove

func (s *ORSet) Remove(e string, send sendFunc) error

Remove is a helper function only to be executed by the source node of an update remove operation. It first handles the prepare part by checking the deletion precondition and creating a remove set and afterwards executes the effect part locally and sends out the remove message to all other replicas.

func (*ORSet) RemoveEffect

func (s *ORSet) RemoveEffect(rSet map[string]string, needsLocking bool, needsWriteBack bool) error

RemoveEffect is the effect part of an update remove operation defined by the specification. It is executed by all replicas of the data set including the source node. It removes supplied set of tags from the ORSet's set.

func (*ORSet) WriteORSetToFile

func (s *ORSet) WriteORSetToFile(needsLocking bool) error

WriteORSetToFile saves an active ORSet onto stable storage at location from initialization. This allows for a CRDT ORSet to be made persistent and later be resumed from prior state.