Version Vectors
Simple, fast utilities for manipulating version vectors and vector clocks. (Same data structure, different semantic purpose.)
Algorithms are static functions, so they can operate on existing POJOs rather than creating additional allocations.
Features
- Typescript. Written in Typescript, distributed as regular Javascript; includes Typescript declarations.
- 100% unit test coverage. And a large variety of corner-case tests.
Usage
Use through npm, or get the source from Github.
Types and functions:
/**
* A native data type that can be used as the "timestamp" field in a version-vector.
*
* There are good use-cases both for numeric counters (simple, more compact) or strings (e.g. https://www.npmjs.com/package/@asmartbear/logical-time).
* The utilities below work on both.
*/
export declare type Timestamp = string | number;
/**
* Dot: a single Replica ID / Timestamp pair.
*/
export declare type Dot<C extends Timestamp> = [string, C];
/**
* Version-vector: A map of replica IDs to counter, which can be a string or integer -- something native and ordered
*/
export declare type VV<C extends Timestamp> = Record<string, C>;
/**
* The result of comparing two version vectors; the answers are non-linear!
*/
export declare enum CompareResult {
EQUAL = 0,
LEFT_DOMINATES = 1,
RIGHT_DOMINATES = 2,
CONFLICTED = 3
}
/**
* Returns a string representation of the version vector.
*/
export declare function toString<C extends Timestamp>(v: VV<C>): string;
/**
* Returns true only if the given version vector is empty, having no dots.
*/
export declare function isEmpty<C extends Timestamp>(v: VV<C>): boolean;
/**
* Makes a copy of a vector.
*/
export declare function clone<C extends Timestamp>(v: VV<C>): VV<C>;
/**
* Adds a replica/timestamp pair to a vector if it doesn't exist, or updates _only if newer_ if it already exists.
* If you have a `Dot` object, you can invoke like `accumulateDot(v, ...dot)`.
*
* @param v version vector to update
* @return the same object `v`
*/
export declare function accumulateDot<C extends Timestamp>(v: VV<C>, replicaId: string, timestamp: C): VV<C>;
/**
* Sets one vector to the union of the two vectors: All elements, and the largest values of each.
*
* @param v version vector to update
* @param u version vector to accumulate into v
* @return the same object `v`
*/
export declare function accumulateUnion<C extends Timestamp>(v: VV<C>, u: VV<C>): VV<C>;
/**
* For all elements from the second vector that individually dominate the first, remove
* those elements from the first.
*
* @param v version vector to update
* @param u version vector to remove out of v
* @return the same object `v`
*/
export declare function accumulateSubtract<C extends Timestamp>(v: VV<C>, u: VV<C>): VV<C>;
/**
* Sets one vector to the intersection of the two vectors: Only the shared elements, and the minimum timestamp of each.
*
* @param v version vector to update
* @param u version vector to accumulate into v
* @return the same object `v`
*/
export declare function accumulateIntersection<C extends Timestamp>(v: VV<C>, u: VV<C>): VV<C>;
/**
* Compares two vectors. Finds equalty, dominance, or conflict.
*
* @param v the "left" version vector to compare
* @param u the "right" version vector to compare
* @return one of four possible results; see enum
*/
export declare function compare<C extends Timestamp>(v: VV<C>, u: VV<C>): CompareResult;
/**
* Compares a vector with a dot. Finds equalty, dominance, or conflict.
*
* @param v the "left" version vector to compare
* @param u the "right" version vector to compare
* @return one of four possible results; see enum
*/
export declare function compareDot<C extends Timestamp>(v: VV<C>, dot: Dot<C>): CompareResult;
/**
* True if the version vector dominates the dot, which means strict domination or equal.
* Equivalent to when `compareDot()` is `LEFT_DOMINATES` or `EQUAL`, but is more efficient.
*/
export declare function dominatesDot<C extends Timestamp>(v: VV<C>, dot: Dot<C>): boolean;
/**
* Compares two dots as timestamps, first based on time, then tie-breaking by replica ID.
*
* @returns `-1`, `0`, or `1` depending on whether a < b, a == b, or a > b respectively
*/
export declare function compareDotTimestamps<C extends Timestamp>(a: Dot<C>, b: Dot<C>): 1 | 0 | -1;
/**
* Returns the largest dot (replica/timestamp pair) in the vector, ordered by time.
*/
export declare function largestDot<C extends Timestamp>(v: VV<C>): Dot<C>;