Home

Awesome

delta-crdts

Delta state-based CRDTs in Javascript.

Install

$ npm install delta-crdts

Import

const CRDTs = require('delta-crdts')

Instantiate a type

const type = 'rga' // or any of the other supported CRDT types
const Type = CRDT(type)

Create a replica

To create a replica you need pass in a unique node id.

const replica = Type('node id')

Mutate that replica

const deltas = []
deltas.push(replica.push('some value'))
deltas.push(replica.insertAt(0, 'some other value'))

Create a second replica

const replica2 = Type('node id 2')

Apply the deltas

deltas.forEach((delta) => replica2.apply(delta))

Query the value

replica2.value() // ['some value', 'some other value']

Initialize a replica from the entire state

const replica3 = Type('node id 3')
replica3.apply(replica2.state())

Conflict management

You can do concurrent edits on both replicas:

// create 2 replicas
const replicas = [Type('id1'), Type('id2')]

// create concurrent deltas
const deltas = [[], []]

deltas[0].push(replicas[0].push('a'))
deltas[0].push(replicas[0].push('b'))

deltas[1].push(replicas[1].push('c'))
deltas[1].push(replicas[1].push('d'))

deltas[0].forEach((delta) => replicas[1].apply(delta))
deltas[1].forEach((delta) => replicas[0].apply(delta))

assert.deepEqual(replicas[0].value(), replicas[1].value())

Extend

You can extend the types, creating your own CRDT.

Example:

const Zero = {
  initial: () => 0,
  join: (s1, s2) => 0,
  value: (state) => state,
  mutators: {
    doSomething (id, state, arg1) => {
      // example mutator, returning a delta
      return 0
    }
  }
}

CRDT.define('zero', Zero)

// now you can use it

const replica = CRDT('zero')('node id')

Support for incremental value computation

It's possible to allow types to have incremental value computation. If a type supports that, the value is incrementally computed on each delta that is applied.

To add support for incremental value computation to a CRDT, the type definition should support the following function:

Type.incrementalValue = function (beforeState, newState, delta, cache = { value: <some initial value>, ... }) {
  // ...
}

As an example you can get inspiration from the RGA implementation.

Types

The following types are built-in:

(* means that the type is causal and can be embedded in an ORMap)

Counters

NameIdentifierMutatorsValue Type
Increment-only Countergcounter.inc()int
PN-Counterpncounter.inc(),.dec()int
Lex-Counterlexcounter.inc(),.dec()int
Causal Counter *ccounter.inc(),.dec()int

Flags

NameIdentifierMutatorsValue Type
Enable-Wins Flag *ewflag.enable(), .disable()Boolean
Disable-Wins Flag *dwflag.enable(), .disable()Boolean

Sets

NameIdentifierMutatorsValue Type
Grow-Only Setgset.add(element)Set
Two-Phase Set2pset.add(element), .remove(element)Set
Add-Wins-Observed-Remove Set *aworset.add(element), .remove(element)Set
Remove-Wins-Observed-Remove Set *rworset.add(element), .remove(element)Set
Remove-Wins-Last-Write-Wins Setrwlwwset.add(element), .remove(element)Set

Arrays

NameIdentifierMutatorsValue Type
Replicable Growable Arrayrga.push(element), .insertAt(pos, element), .removeAt(pos), updateAt(pos, element), insertAllAt(pos, elements)Array

Registers

NameIdentifierMutatorsValue Type
Last-Write-Wins Registerlwwreg.write(value)Value
Multi-Value Register *mvreg.write(value)Set of concurrent values

Maps

NameIdentifierMutatorsValue Type
Observed-Remove Map *ormap.remove(key), applySub(key, crdt_name, mutator_name, ...args)Object

Embedding CRDTs in ORMaps

OR-Maps support embedding of other causal CRDTs. Example:

const ORMap = CRDT('ormap')
const m = ORMap('id1')
const delta = m.applySub('a', 'mvreg', 'write', 'A')
console.log(m.value()) // => {a: new Set(['A'])}

Of this collection, causal CRDTs are:

Sets, uniqueness and object id

For testing uniqueness in a way that is safe when replicas are distributed, for objects we calculate the hash using the hast-it package.

If you want, you can override it by providing a hashCode attribute in your object.

For all objects where typeof object !== 'object', we use the value itself as comparison.

Static methods

You may get the static definition of a type by doing

const type = CRDT.type(typeName)

Each type has a series of static methods may need to use:

Type.initial()

Returns the initial state for the type. Example:

const GCounter = CRDT.type('gcounter')
const initial = GCounter.initial()

Type.value(state)

Returns the view value of a given state.

Type.join(s1, s2)

Joins two states (or deltas) and returns the result.

const GCounter = CRDT.type('gcounter')

const state = GCounter.join(delta1, delta)

const value = GCounter.value(state)

Example of using static methods:

const GCounter = CRDT('gcounter')

deltas = []
deltas.push(replica1.inc())
deltas.push(replica1.inc())
deltas.push(replica1.inc())

const bigDelta = deltas.reduce(GCounter.join, GCounter.initial())

replica2.apply(bigDelta)

License

MIT