Reference

A short reference for the Go library and the multivergence command. The full versions are in the repository: the API and every command, the exact rules for weights, constraints and deadlines, and the file format.

The Pieces

  • Trunk. The state that is real now. Its name is trunk.
  • Branch. A copy-on-write fork of the trunk or of another branch. Writes to it stay in it. A branch that changes 3 keys of a 10,000-key trunk costs about 4 KB.
  • Weight. How likely a branch is, next to the others. Its probability is its weight over the total weight of the live branches.
  • Constraint. A condition on one key, such as fare/flight <= 400 or hold exists. When it stops holding, the branch dies.
  • Deadline. When a branch stops mattering. It dies at the first change made at or after it, and reads show it expired from that moment.
  • Observe. Applies evidence: facts written to the trunk and every live branch, then constraints, then likelihoods multiplied in, then the weights renormalised, then an optional prune.
  • Promote. Makes a live branch’s state the trunk, drops every branch, and starts the next generation. It’s one record in the file.
  • Stale. A branch forked before a direct write to the trunk. Promote refuses it, since promoting would lose that write.

How Observe Works

One call, in this order, all or nothing:

  1. Branches past their deadline die.
  2. Each fact is written to the trunk and every live branch.
  3. Each live branch is checked against its constraints; a broken one kills it.
  4. Each live branch’s weight is multiplied by its likelihood: its own, or Rest, or 1 if no likelihoods were given. Zero rules a branch out.
  5. The survivors are renormalised to add up to 1.
  6. If a prune threshold is set, branches below it die, except the most likely one, and the rest renormalise again.

The engine never decides how likely anything is. The caller supplies likelihoods, and the engine applies them the same way every time, so the same calls give the same weights to the last bit.

Commands

multivergence [-f file] [-json] <command> [arguments]

The store is the file given by -f, or $MULTIVERGENCE_FILE, or multivergence.mv in the current directory.

Command Does
get [-b branch] key print a value
keys [-b branch] [-values] [prefix] list keys in order
set [-b branch] key value write a value (- reads stdin)
del [-b branch] key delete a key
fork name [-from branch] [-weight w] fork the trunk or a live branch
weight name w set a weight
constrain name 'key op value'... add constraints: == != < <= > >=, or key exists, key absent
expire name -in 15m or -at TIME or -clear set or clear a deadline
observe [-fact k=v]... [-unset k]... [-l name=x]... [-rest x] [-prune p] apply evidence
sweep record branches past their deadline
discard name kill a branch
promote name make a branch the trunk
branches [-live] list this generation’s branches
best the most likely live branch
history [-n count] recent events
version the version

With -json, each command prints one JSON value, and a failure prints {"error": "...", "kind": "..."}.

Exit codes: 0 done, 1 error, 2 bad usage, 3 key missing (get) or no live branch (best), and 4 when the change was made and the branch died of it.

Go

s := multivergence.New(nil)                       // in memory
s, err := multivergence.Open("trip.mv", nil)       // a file, with a writer lock
r, err := multivergence.OpenReadOnly("trip.mv", nil) // no lock

s.Set(branch, key, value)       s.Get(branch, key)       s.Delete(branch, key)
s.Fork(name, from, weight)      s.Weight(name, w)        s.Discard(name)
s.Constrain(name, multivergence.AtMost("fare", 400), multivergence.Present("hold"))
s.Expire(name, at)              s.ExpireIn(name, 15*time.Minute)
out, err := s.Observe(multivergence.Evidence{Facts: ..., Likelihoods: ..., Rest: ..., PruneBelow: ...})
s.Promote(name)                 s.Branches()             s.Best()

out.Killed lists the branches that died and why, out.Live the survivors with their probabilities, and out.Settled() the one left, if only one is. A write that breaks a constraint returns a *KilledError: the write was kept and the branch died.

The File

An append-only log. Every change is one checksummed record, written and synced before the call returns. A crash can only cut short the last record, and opening the file drops it. The log is compacted into one snapshot from time to time, written to a new file and renamed into place, with the nodes that branches share written once. One process writes at a time, through a lock file; readers take no lock.

Limits in Version 0.1

  • Promote takes one branch and drops the rest. There’s no merging.
  • A branch is data. Real-world actions taken by a branch aren’t undone when it dies.
  • One machine: one writer per file at a time, no replication.
  • Each change copies the table of branches, so a write takes about 4 µs with 10 live branches and about 70 µs with 1,000.