- Notifications
You must be signed in to change notification settings - Fork0
Concurrent version history based on a Merkle-DAG
License
ipfs-shipyard/js-versidag
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Concurrent version history based on a Merkle-DAG.
version + dag = versidag
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 usingLamport timestamps,Vector clocks andDAGs to name a few.
This module leveragesMerkle-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.
- Themerge operation guarantees that non-concurrent heads are removed.
$ npm install versidag
importcreateVersidagfrom'versidag';constmyVersidag=createVersidag({tieBreaker:(node1,node2)=>/* */,readNode:(cid)=>/* */,writeNode:(node)=>/* */,});constmyVersidagA=awaitmyVersidag.add('Hi',1);constmyVersidagB=awaitmyVersidagA.add('Hello',2);constmyVersidagC=awaitmyVersidagA.add('Hi World',3);constmyVersidagD=awaitmyVersidagB.merge(myVersidagC.headCids,'Hello World');constversions=awaitmyVersidagD.resolve();// [// { version: 'Hello World' },// { version: 'Hi World', meta: 3 }// { version: 'Hello', meta: 2 }// { version: 'Hi', meta: 1 }// ]
Creates a versidag instance with the specified heads.
If noheadCids are supplied it means that it will be headless.Theconfig is an object that has the following shape:
{// Writes a node, returning its content id// This function may return a promisewriteNode:(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>,}
ThewriteNode,readNode andtieBreaker are mandatory.
Important considerations:
- The return value of
writeNodemust be based on thenodecontents, meaning that it should produce thatsame result for the samenode, across replicas. This is often called a content id orcid. - The return value of
tieBreakermust beconsistent, that is, for the same arguments it should return exactly the same result, across replicas. In essence, it should be the samepure function in all replicas. - The
readNodeandwriteNodemust take into consideration their respective timeout configurations in case they perform async I/O. In simpler cases, you might usep-timeout which plays nicely with promises created withp-cancelable.
Example:
importhashObjfrom'hash-obj';constnodesMap=newMap();// Example of a in-memory versidag where the tie-breaker is a simple meta comparisonconstversidag=createVersidag({writeNode:(node)=>{// The hash-obj module returns an hash of the objectconstcid=hashObj(node)nodesMap.set(cid,node);returncid;},readNode:(cid)=>nodesMap.get(cid),tieBreaker:(node1,node2)=>node1.meta-node2.meta});
A getter for the underlying DAG heads content ids.
A getter for the underlying config.
Adds a newversion with the suppliedmeta, creating a DAG node pointing to the current heads.
Returns a promise that resolves to a new versidag pointing to the new head.
Example:
importcreateVersidagfrom'versidag';constmyVersidag=createVersidag({/* config */});constmyVersidagA=awaitmyVersidag.add('Hi',1);
Concatenates the current heads with the suppliedheadCids.
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:
importcreateVersidagfrom'versidag';constmyVersidag=createVersidag({/* config */});constmyVersidagA=awaitmyVersidag.add('Hi',1);constmyVersidagB=awaitmyVersidagA.add('Hello',2);constmyVersidagC=awaitmyVersidagA.add('Hi World',3);constmyVersidagD=awaitmyVersidagB.union(myVersidagC.headCids);// myVersidagD heads are ['B', 'C']
Creates a DAG node pointing to the union of the current heads with the suppliedheadCids, optionally pointing to aversion.
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 aversion, 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 useCRDTs.
Example:
importcreateVersidagfrom'versidag';constmyVersidag=createVersidag({/* config */});constmyVersidagA=awaitmyVersidag.add('Hi',1);constmyVersidagB=awaitmyVersidagA.add('Hello',2);constmyVersidagC=awaitmyVersidagA.add('Hi World',3);constmyVersidagD=awaitmyVersidagB.merge(myVersidagC.headCids);// myVersidagD has a single head that is merge node pointing B and C
Resolves the versions by traversing the DAG.
Available options:
limit: The maximum number of versions to retrieve, defaults toInfinity.fromCids: Start the traversal from these heads instead of the current ones, used for pagination.
Returns an object containing theversions. Iflimit was specified, the object also contains thenextCids that may be used for the next iteration.
If you just need a few versions, you should specify alimit. This ensures that the traversal will stop as soon as we get that amount of versions.
Example:
importcreateVersidagfrom'versidag';constmyVersidag=createVersidag({/* config */});constmyVersidagA=awaitmyVersidag.add('Hi',1);constmyVersidagB=awaitmyVersidagA.add('Hello',2);constmyVersidagC=awaitmyVersidagA.add('Hi World',3);constmyVersidagD=awaitmyVersidagB.merge(myVersidagC.headCids,'Hello World');constresult1=awaitversidag.resolve();// {// versions:[// { version: 'Hello world' },// { version: 'Hi World', meta: 3 }// { version: 'Hello', meta: 2 }// { version: 'Hi', meta: 1 }// ],// nextCids: [],// }// With paginationconstresult1=awaitversidag.resolve({limit:2});// {// versions:[// { version: 'Hello world' },// { version: 'Hi World', meta: 3 }// ],// nextCids: ['B', 'A'],// }constresult2=versidag.resolve({limit:2,fromCids:result1.nextCids});// {// versions:[// { version: 'Hello', meta: 2 },// { version: 'Hi', meta: 1 }// ],// nextCids: [],// }
$ npmtest$ npmtest -- --watch# during development
Released under theMIT License.
About
Concurrent version history based on a Merkle-DAG
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.
Contributors2
Uh oh!
There was an error while loading.Please reload this page.