Delta state-based CRDTs in Javascript.
$ npm install delta-crdts constCRDTs=require('delta-crdts')consttype='rga'// or any of the other supported CRDT typesconstType=CRDT(type)To create a replica you need pass in a unique node id.
constreplica=Type('node id')constdeltas=[]deltas.push(replica.push('some value'))deltas.push(replica.insertAt(0,'some other value'))constreplica2=Type('node id 2')deltas.forEach((delta)=>replica2.apply(delta))replica2.value()// ['some value', 'some other value']constreplica3=Type('node id 3')replica3.apply(replica2.state())You can do concurrent edits on both replicas:
// create 2 replicasconstreplicas=[Type('id1'),Type('id2')]// create concurrent deltasconstdeltas=[[],[]]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:
constZero={initial: ()=>0,join: (s1,s2)=>0,value: (state)=>state,mutators: {doSomething(id,state,arg1)=>{// example mutator, returning a deltareturn0}}}CRDT.define('zero',Zero)// now you can use itconstreplica=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: <someinitialvalue>, ... }){// ...}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:
constORMap=CRDT('ormap')constm=ORMap('id1')constdelta=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
consttype=CRDT.type(typeName)Each type has a series of static methods may need to use:
Returns the initial state for the type. Example:
constGCounter=CRDT.type('gcounter')constinitial=GCounter.initial()Returns the view value of a given state.
Joins two states (or deltas) and returns the result.
constGCounter=CRDT.type('gcounter')conststate=GCounter.join(delta1,delta)constvalue=GCounter.value(state)constGCounter=CRDT('gcounter')deltas=[]deltas.push(replica1.inc())deltas.push(replica1.inc())deltas.push(replica1.inc())constbigDelta=deltas.reduce(GCounter.join,GCounter.initial())replica2.apply(bigDelta)MIT
