@asmartbear/logical-time NPM

Logical Time & Time-Ordered GUIDs

A JavaScript implementation of the WP Engine Logical Time algorithm. Also generates time-ordered globally-unique IDs (LT-GUID).

Logical Time (LT) is an enhancement of Lamport Timestamps in these ways:

LTs monotonically increase, even if the physical clock has low resolution (e.g. ticks once per second) or if it is misbehaved (e.g. moves slowly or backwards), as is common in containerized environments.
LTs can coordiante between two processes P and Q, such that all timestamps generated by Q after that moment are strictly larger than all timestamps generated by P prior to that moment.
If the underlying system clock is tightly synchronized with other systems, then LTs are a very good approximation for "real time." If not, they still retain all of their properties. Thus, it is possible to create algorithms (like Last-Write Wins) which are always correct and predictable, and get more accurate automatically as the underlying system becomes more accurate.

LTs are not unique, and in fact there are common use-cases where two systems will independently generate the same LT. However, very often the use-case for LTs includes them being globally-unique, therefore this library also includes the ability to generate globally-unique IDs (GUIDs), which are prefixed with LT, and therefore their primary sort-order is by LT.

Uses:

Last-Write Wins: Determining who should win in "Last-Write Wins" algorithms. If one system definitely know about the other (i.e. "causal link"), it will have the larger LT. If it is ambiguous, LT is still a great way to break ties because it is a best-effort at "real, universal" time.
Vector Clocks: Rather than a simple "counter," LTs provide the same mathematical requirements (i.e. a monotonically increasing value), but with the added semantics of time and causal relations. Therefore, it is valid to compare "counters" between different elements in the vector, rather than treating them as opaque. This is useful for auditing as well and for multi-write conflict resolution. Without this factor, conflict-resolution often results in something like "whichever system ID is greater," but this results in system P always winning, even if system Q provably changed the value after P in real time.
Appending to distributed arrays: Together with a tag for uniqueness, LTs can be used as keys for appending to a distributed array. Items are always ordered properly relative to each system in isolation, yet sort together with other systems as precisely in "real time" as the underlying systems allow, but also enforce the rule that if P was synchronized with Q at time T, then all array entries by P after time T will come after all entries by Q before time T.

Features:

Fast: Generates LTs at 12,000,000/sec on MacBook Pro; results are plain JavaScript strings that are compared using < and ==.
Compact: The representation is space-compact.
Testable: The concept of "system clock" is pluggable, making it easy to write unit tests under arbitrary time-assumptions.
Typescript: Written in Typescript, but distributed as regular Javascript, and includes Typescript declarations

Usage

Use through npm, or get the source from Github.

Generates LT strings. The strings are normal, compact JavaScript strings which compare in the usual way, so "earlier" or "equal" relations are just the usual JavaScript operators like < and =.

import { LT } from '@asmartbear/logical-time';

// Object that provides the system time. Several implementations...
const pt = new LT.PhysicalTimeOS();        // gets system time, every invocation
const pt = new LT.PhysicalTimeOSTimer();   // 4x faster than the above, but must
                                            // remember to call pt.stopUpdating().
const pt = new LT.PhysicalTimeMock();       // manual control; good for testing

// This object maintains the state needed to generate LT strings.  Typically
// a singleton in an application; unit tests can use multiple for testing
// any combination of states and race conditions.
const lt = new LT.LogicalTimeManager(pt);

// Generate LTs
console.log(lt.generateLT());  // -> bVD-aC
console.log(lt.generateLT());  // -> bVD-aD   (time identical, so just counter updated)
console.log(lt.generateLT());  // -> bVE-aC   (time updated, so counter was reset)

// Synchronize with another LT.
const otherLT = getFromAnotherSystem();     // just a string
lt.synchronizeLT(otherLT);        // `lt` is updated only if needed

To create LT-GUIDs, you can supply a globally-unique string when creating the LogicalTimeManager(), or you can leave it blank to generate one for you, as in the example above. Or use the getUniqueSystemIdentifier() helper function to generate one:

import { LT } from '@asmartbear/logical-time';

// Generate a globally unique ID.  If you want this to be stable across runs, store it
// somewhere, like browser-local storage or a configuration system.
const unique = LT.getUniqueSystemIdentifier();      // -> tDQtVEgbxg

// Create the LogicalTimeManager and pass in the unique ID.
const pt = new LT.PhysicalTimeOS();
const lt = new LT.LogicalTimeManager(pt, unique);
console.log(lt.generateLT());  // -> hDCbxNyDD-BBBD-tDQtVEgbxg
console.log(lt.generateLT());  // -> hDCbxNyDG-BBBB-tDQtVEgbxg