Delta state-based CRDTs in Javascript.
$ npm install delta-crdts
const CRDTs = require('delta-crdts')
const type = 'rga' // or any of the other supported CRDT types const Type = CRDT(type)
To create a replica you need pass in a unique node id.
const replica = Type('node id')
const deltas = [] deltas.push(replica.push('some value')) deltas.push(replica.insertAt(0, 'some other value'))
const replica2 = Type('node id 2')
deltas.forEach((delta) => replica2.apply(delta))
replica2.value() // ['some value', 'some other value']
const replica3 = Type('node id 3') replica3.apply(replica2.state())
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())
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')
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.
The following types are built-in:
(* means that the type is causal and can be embedded in an ORMap)
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Increment-only Counter | gcounter |
.inc() |
int |
| PN-Counter | pncounter |
.inc(),.dec() |
int |
| Lex-Counter | lexcounter |
.inc(),.dec() |
int |
| Causal Counter * | ccounter |
.inc(),.dec() |
int |
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Enable-Wins Flag * | ewflag |
.enable(), .disable() |
Boolean |
| Disable-Wins Flag * | dwflag |
.enable(), .disable() |
Boolean |
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Grow-Only Set | gset |
.add(element) |
Set |
| Two-Phase Set | 2pset |
.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 Set | rwlwwset |
.add(element), .remove(element) |
Set |
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Replicable Growable Array | rga |
.push(element), .insertAt(pos, element), .removeAt(pos), updateAt(pos, element), insertAllAt(pos, elements) |
Array |
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Last-Write-Wins Register | lwwreg |
.write(value) |
Value |
| Multi-Value Register * | mvreg |
.write(value) |
Set of concurrent values |
| Name | Identifier | Mutators | Value Type |
|---|---|---|---|
| Observed-Remove Map * | ormap |
.remove(key), applySub(key, crdt_name, mutator_name, ...args) |
Object |
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:
- AWORSet
- CCounter
- DWFlag
- EWFlag
- MVReg
- ORMap
- RWORSet
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.
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:
Returns the initial state for the type. Example:
const GCounter = CRDT.type('gcounter') const initial = GCounter.initial()
Returns the view value of a given state.
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)
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)
MIT