crdt

Documentation

Overview

Package crdt implements CRDT types and associated changes

The main CRDT types are Dict and Seq which implement map-like and list-like container types.

The Container type can hold any mutable value.

Index

• func BetweenOrd(a, b string, count int) []string
• func LessOrd(a, b string) bool
• func NextOrd(key string) string
• func PrevOrd(key string) string
• type Container
  • func (c Container) Apply(ctx changes.Context, cx changes.Change) changes.Value
  • func (c Container) Clone() Container
  • func (c Container) Delete() (changes.Change, Container)
  • func (c Container) Get() (*Rank, interface{})
  • func (c Container) Set(r *Rank, v interface{}) (changes.Change, Container)
  • func (c Container) Update(inner changes.Change) (changes.Change, Container)
• type Dict
  • func (d Dict) Apply(ctx changes.Context, c changes.Change) changes.Value
  • func (d Dict) Clone() Dict
  • func (d Dict) Delete(key interface{}) (changes.Change, Dict)
  • func (d Dict) Get(key interface{}) (*Rank, interface{})
  • func (d Dict) Set(key, value interface{}) (changes.Change, Dict)
  • func (d Dict) Update(key interface{}, inner changes.Change) (changes.Change, Dict)
• type Rank
  • func NewRank() *Rank
  • func (r *Rank) Less(o *Rank) bool
• type Seq
  • func (s Seq) Apply(ctx changes.Context, c changes.Change) changes.Value
  • func (s Seq) Items() []interface{}
  • func (s Seq) Move(offset, count, distance int) (changes.Change, Seq)
  • func (s Seq) Splice(offset, remove int, replacement []interface{}) (changes.Change, Seq)
  • func (s Seq) Update(idx int, inner changes.Change) (changes.Change, Seq)

Functions

func BetweenOrd

func BetweenOrd(a, b string, count int) []string

BetweenOrd returns keys between the two provided keys.

func LessOrd

func LessOrd(a, b string) bool

LessOrd returns true if a < b

func NextOrd

func NextOrd(key string) string

NextOrd returns the next ordinal.

Less(key, next(key)) is guaranteed to always be true

func PrevOrd

func PrevOrd(key string) string

PrevOrd returns the prev ordinal.

LessOrd(prev(key), key) is guaranteed to always be true

Types

type Container

type Container struct {
	Entries map[*Rank]interface{}
	Undos   map[*Rank]int
	Deleted int
}

Container holds a single CRDT value.

This is implemented as a map of unique rank to values. Every update creates a new entry in this map. Undo of an update causes the undo count for that rank to be incremented (and undo of the undo causes the count to be decremented).

Tho whole container itself can be deleted (with Deleted tracking the count) and undeleted.

func (Container) Apply

func (c Container) Apply(ctx changes.Context, cx changes.Change) changes.Value

Apply implements changes.Value

func (Container) Clone

func (c Container) Clone() Container

Clone duplicates the whole container

func (Container) Delete

func (c Container) Delete() (changes.Change, Container)

Delete deletes the whole container

func (Container) Get

func (c Container) Get() (*Rank, interface{})

Get returns the latest undeleted value or nil if no such value exists.

func (Container) Set

func (c Container) Set(r *Rank, v interface{}) (changes.Change, Container)

Set updates the value using the provided rank. The effective value is given by the largest undeleted rank. Reverting the returned change will simply cause the undo count of the rank to be modified.

func (Container) Update

func (c Container) Update(inner changes.Change) (changes.Change, Container)

Update wraps a change meant for the value within the container.

type Dict

type Dict struct {
	Entries map[interface{}]Container
}

Dict implements a CRDT-style dictionary

func (Dict) Apply

func (d Dict) Apply(ctx changes.Context, c changes.Change) changes.Value

Apply implments changes.Value

func (Dict) Clone

func (d Dict) Clone() Dict

Clone duplicates the whole state

func (Dict) Delete

func (d Dict) Delete(key interface{}) (changes.Change, Dict)

Delete removes the value for the key.

func (Dict) Get

func (d Dict) Get(key interface{}) (*Rank, interface{})

Get returns the current value or nil if there is no value available.

func (Dict) Set

func (d Dict) Set(key, value interface{}) (changes.Change, Dict)

Set creates or updates the value for a key

func (Dict) Update

func (d Dict) Update(key interface{}, inner changes.Change) (changes.Change, Dict)

Update takes a change meant for the value at the provided key and wraps it so that it can applied on the dict

type Rank

type Rank struct {
	Epoch int64
	Nonce [4]int64
}

Rank implements a unique ID that can be used for sorting.

The Epoch field is meant to track the time when the rank was created, so this can be used for garbage collection and such

Use Ord if it is important to generate specific sortable IDs with the ability to confine them between any two such values.

func NewRank

func NewRank() *Rank

NewRank returns a new rank with current Epoch and some random bits to ensure uniqueness

func (*Rank) Less

func (r *Rank) Less(o *Rank) bool

Less returns true iff r < o

type Seq

type Seq struct {
	Values Dict
	Ords   Dict
}

Seq implements a CRDT-style sequence

func (Seq) Apply

func (s Seq) Apply(ctx changes.Context, c changes.Change) changes.Value

Apply implements changes.Value

func (Seq) Items

func (s Seq) Items() []interface{}

Items returns the seq as an array

func (Seq) Move

func (s Seq) Move(offset, count, distance int) (changes.Change, Seq)

Move shifts the sub sequence (offset, offset +count) by distance

func (Seq) Splice

func (s Seq) Splice(offset, remove int, replacement []interface{}) (changes.Change, Seq)

Splice replaces the sub-sequence [offset:offset+remove]

func (Seq) Update

func (s Seq) Update(idx int, inner changes.Change) (changes.Change, Seq)

Update takes a change meant for the value at a specific index and wraps it so that it can applied on the Seq