versidag

Concurrent version history based on a Merkle-DAG.

version + dag = versidag

Motivation

In distributed systems, the replicas' clocks aren't reliable to get the total order of versions. This is specially true in p2p networks where the difference in clocks may be exacerbated. There are ways to get a partial order of versions by preserving causality, such as by using Lamport timestamps, Vector clocks and DAGs to name a few.

This module leverages Merkle-DAGs to preserve causality (happen-before) and a tie-breaker to determine the order of concurrent versions. The DAG will converge amongst replicas because:

• The nodes on Merkle-DAGs are labeled based on their contents, meaning that whenever a merge occurs, they converge to the same label (cid).
• The tie-breaker is deterministic among replicas, meaning that the total order of versions will be the same among replicas.
• The merge operation guarantees that non-concurrent heads are removed.

Installation

$ npm install versidag

Usage

import createVersidag from 'versidag';

const myVersidag = createVersidag({
    tieBreaker: (node1, node2) => /* */,
    readNode: (cid) => /* */,
    writeNode: (node) => /* */,
});

const myVersidagA = await myVersidag.add('Hi', 1);
const myVersidagB = await myVersidagA.add('Hello', 2);
const myVersidagC = await myVersidagA.add('Hi World', 3);
const myVersidagD = await myVersidagB.merge(myVersidagC.headCids, 'Hello World');

const versions = await myVersidagD.resolve();
// [
//   { version: 'Hello World' },
//   { version: 'Hi World', meta: 3 }
//   { version: 'Hello', meta: 2 }
//   { version: 'Hi', meta: 1 }
// ]

API

createVersidag([headCids], config)

Creates a versidag instance with the specified heads.

If no headCids are supplied it means that it will be headless. The config is an object that has the following shape:

{
  // Writes a node, returning its content id
  // This function may return a promise
  writeNode: (node, config) => <nodeCid>,
  // The maximum concurrent writeNode calls, defaults to Infinity
  writeConcurrency: 10,
  // Maximum amount of time to wait for a writeNode to complete, defaults to null
  writeTimeout: 10000,
  // Reads a node by its content id
  // This function may return a promise
  readNode: (cid, config) => <node>,
  // The maximum concurrent writeNode calls, defaults to Infinity
  readConcurrency: 10,
  // Maximum amount of time to wait for a writeNode to complete, defaults to null
  readTimeout: 10000,
  // A tie-breaker that compares concurrent nodes, where the node's shape is { version, meta }
  // This is a comparator function that must return -1, 1 or 0
  tieBreaker: (node1, node2) => <number>,
}

The writeNode, readNode and tieBreaker are mandatory.

Important considerations:

• The return value of writeNode must be based on the node contents, meaning that it should produce that same result for the same node, across replicas. This is often called a content id or cid.
• The return value of tieBreaker must be consistent, that is, for the same arguments it should return exactly the same result, across replicas. In essence, it should be the same pure function in all replicas.
• The readNode and writeNode must take into consideration their respective timeout configurations in case they perform async I/O. In simpler cases, you might use p-timeout which plays nicely with promises created with p-cancelable.

Example:

import hashObj from 'hash-obj';

const nodesMap = new Map();

// Example of a in-memory versidag where the tie-breaker is a simple meta comparison
const versidag = createVersidag({
  writeNode: (node) => {
    // The hash-obj module returns an hash of the object
    const cid = hashObj(node)

    nodesMap.set(cid, node);

    return cid;
  },
  readNode: (cid) => nodesMap.get(cid),
  tieBreaker: (node1, node2) => node1.meta - node2.meta
});

.headCids

A getter for the underlying DAG heads content ids.

.config

A getter for the underlying config.

.add(version, meta)

Adds a new version with the supplied meta, creating a DAG node pointing to the current heads.

Returns a promise that resolves to a new versidag pointing to the new head.

Example:

import createVersidag from 'versidag';

const myVersidag = createVersidag({ /* config */ });
const myVersidagA = await myVersidag.add('Hi', 1);

.union(headCids)

Concatenates the current heads with the supplied headCids.

Any duplicate heads are removed and the final heads will be sorted lexically.
Returns a new versidag pointing to the concatenated heads.

Note that no new DAG node will be written.

Example:

import createVersidag from 'versidag';

const myVersidag = createVersidag({ /* config */ });
const myVersidagA = await myVersidag.add('Hi', 1);
const myVersidagB = await myVersidagA.add('Hello', 2);
const myVersidagC = await myVersidagA.add('Hi World', 3);

const myVersidagD = await myVersidagB.union(myVersidagC.headCids);
// myVersidagD heads are ['B', 'C']

.merge(headCids, [version])

Creates a DAG node pointing to the union of the current heads with the supplied headCids, optionally pointing to a version.

Any duplicate heads are removed and the final heads will be sorted lexically.
Moreover, any non-concurrent heads will be removed so that the result is deterministic among replicas.

Returns a new versidag pointing to the concatenated heads.

In case you specify a version, it's important that it is consistent across all replicas. This means that the replicas must converge to the same version. The way the convergence happens is out of the scope of this module, but one possible solution is to use CRDTs.

Example:

import createVersidag from 'versidag';

const myVersidag = createVersidag({ /* config */ });
const myVersidagA = await myVersidag.add('Hi', 1);
const myVersidagB = await myVersidagA.add('Hello', 2);
const myVersidagC = await myVersidagA.add('Hi World', 3);

const myVersidagD = await myVersidagB.merge(myVersidagC.headCids);

// myVersidagD has a single head that is merge node pointing B and C

.resolve([options])

Resolves the versions by traversing the DAG.

Available options:

• limit: The maximum number of versions to retrieve, defaults to Infinity.
• fromCids: Start the traversal from these heads instead of the current ones, used for pagination.

Returns an object containing the versions. If limit was specified, the object also contains the nextCids that may be used for the next iteration.

If you just need a few versions, you should specify a limit. This ensures that the traversal will stop as soon as we get that amount of versions.

Example:

import createVersidag from 'versidag';

const myVersidag = createVersidag({ /* config */ });
const myVersidagA = await myVersidag.add('Hi', 1);
const myVersidagB = await myVersidagA.add('Hello', 2);
const myVersidagC = await myVersidagA.add('Hi World', 3);
const myVersidagD = await myVersidagB.merge(myVersidagC.headCids, 'Hello World');

const result1 = await versidag.resolve();
// {
//   versions:[
//     { version: 'Hello world' },
//     { version: 'Hi World', meta: 3 }
//     { version: 'Hello', meta: 2 }
//     { version: 'Hi', meta: 1 }
//   ],
//   nextCids: [],
// }

// With pagination
const result1 = await versidag.resolve({ limit: 2 });
// {
//   versions:[
//     { version: 'Hello world' },
//     { version: 'Hi World', meta: 3 }
//   ],
//   nextCids: ['B', 'A'],
// }

const result2 = versidag.resolve({ limit: 2, fromCids: result1.nextCids });
// {
//   versions:[
//     { version: 'Hello', meta: 2 },
//     { version: 'Hi', meta: 1 }
//   ],
//   nextCids: [],
// }

Tests

$ npm test
$ npm test -- --watch  # during development

License

Released under the MIT License.