merge

type Clock ¶

type Clock struct {
	Wall    int64  `json:"wall"`
	Logical uint32 `json:"logical"`
	Actor   string `json:"actor"`
}

Clock is a hybrid logical clock stamp (Kulkarni et al., 2014): wall time in milliseconds, a logical counter for events within one millisecond, and the actor as the final tiebreak. Total order, so two replicas always agree on which write wins.

func (c Clock) IsZero() bool

func (c Clock) Less(o Clock) bool

type Conflict ¶

type Conflict struct {
	Path   string
	Winner Op
	Loser  Op
}

Conflict is a write that landed on a leaf another actor had changed since the writer last saw it. The state is the same whichever order the writes arrived in (that is the CRDT); the conflict is a note for the people, so neither value is silently lost. Winner is what the leaf now holds; Loser is the write that did not take.

type HLC ¶

type HLC struct {
	Actor string
	// contains filtered or unexported fields
}

HLC issues clocks for one actor. Now never returns a clock lower than one it has seen (Observe), so a replica that received a newer write stamps its next write after it, whatever its wall clock says.

func (h *HLC) Now(ms int64) Clock

func (h *HLC) Observe(c Clock)

type Keyer ¶

type Keyer func(listPath string, elem map[string]any) (key string, ok bool)

Keyer says whether a list at listPath is keyed and, for one element, which key names it. Return ok=false for a list that is not keyed (it is then stored as one leaf, last writer wins on the whole list).

type Op ¶

type Op struct {
	Path   string `json:"path"`
	Value  any    `json:"value,omitempty"`
	Delete bool   `json:"delete,omitempty"`
	Clock  Clock  `json:"clock"`
	Base   Clock  `json:"base"`
	// Text, when set, is a character edit to a text leaf rather than a
	// write of the whole value; Value and Delete are then ignored.
	Text *TextOp `json:"text,omitempty"`
}

Op is one write to one leaf: set Value at Path, or delete it. Base is the clock of the value the writer saw there, so a concurrent overwrite can be noticed (see Conflict); zero when the writer saw nothing.

func Decompose(doc map[string]any, clock Clock, keys Keyer) []Op

type State ¶

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

State is the replicated map. The zero value is empty and usable.

func New() *State

func (s *State) Apply(op Op) (applied bool, conflict *Conflict)

func (s *State) ClockAt(path string) (Clock, bool)

func (s *State) Clone() *State

func (s *State) Document() map[string]any

func (s *State) Merge(o *State)

func (s *State) Ops() []Op

func (s *State) TextEdit(path, want string, h *HLC) []Op

type Text ¶

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

Text is a replicated sequence of characters: the Replicated Growable Array (Roh, Jeon, Kim, Lee, "Replicated abstract data types: Building blocks for collaborative applications", 2011). Every character has a unique id (the clock that inserted it) and names the character it was typed after; a deleted character stays as a tombstone so a concurrent insert after it still has its anchor. Two people typing in the same sentence at once both keep what they typed, in a deterministic order, on every replica.

A text leaf in a State holds one of these instead of a scalar. The field is still one leaf: a plain Set on it (from a client that does not speak text ops, or an import) replaces the whole text with a new one seeded from the string, under the usual last-writer rule, and text ops from then on edit that one.

func NewText() *Text

func TextFrom(s string, clock Clock) *Text

func (t *Text) Apply(op TextOp) bool

func (t *Text) Clone() *Text

func (t *Text) Edit(want string, next func() Clock) []TextOp

func (t *Text) Merge(o *Text)

func (t *Text) Ops() []TextOp

func (t *Text) String() string

type TextOp ¶

type TextOp struct {
	Insert bool  `json:"insert,omitempty"`
	ID     Clock `json:"id"`
	After  Clock `json:"after,omitempty"`
	R      rune  `json:"r,omitempty"`
}

TextOp is one edit to a text leaf: insert rune R with id ID after the character After (zero Clock means at the start), or delete the character ID.

func (t TextOp) Less(c Clock) bool