vectorclock

A simple implementation of vector clocks in Javascript.

vectorclock

A simple implementation of vector clocks in Javascript.

Vector clocks are represented as plain old objects with a "clock" key (which is a hash). For example: { clock: { a: 1, b: 2 } }.

Recommended reading:

  • increment(clock, nodeId): increment a vector clock at "nodeId"
  • merge(a, b): given two vector clocks, returns a new vector clock with all values greater than those of the merged clocks
  • compare(a, b) / ascSort(a, b): compare two vector clocks, returns -1 for a < b and 1 for a > b; 0 for concurrent and identical values. Can be used to sort an array of objects by their "clock" key via [].sort(VClock.ascSort)
  • descSort(a, b): sorts in descending order (N, ... 3, 2, 1)
  • isConcurrent(a, b): if A and B are equal, or if they occurred concurrently.
  • isIdentical(a, b): if every value in both vector clocks is equal.

Here is one way to implement read repair by detecting which clocks are concurrent, and if necessary, returning multiple values:

var responses = [ { clock: ... }, { clock: ... }];
// sort the responses by the vector clocks
responses.sort(VClock.descSort);
// then compare them to the topmost
// (in sequential order, the greatest) item
var repaired = [ responses.shift() ];
responses.forEach(function(item, index) {
  // if they are concurrent with that item, then there is a conflict
  // that we cannot resolve, so we need to return the item.
  if(VClock.isConcurrent(item, repaired[0]) &&
    !VClock.isIdentical(item, repaired[0])) {
    repaired.push(item);
  }
});