hlc-gen

Lock-free Hybrid Logical Clock (HLC) timestamp generator.

Implements the Hybrid Logical Clock (HLC) machinery outlined in Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases paper.

Features

• Lock-free implementation of the HLC algorithm.
• High throughput, easy to use with minimal API (timestamp generation for local and send events + generator adjusting on receive events).

Motivation

The idea is to have a generator producing timestamp-based IDs that are:

• unique and monotonic
• based on timestamp, thus allowing the correct ordering of events ("happened before" relationship preserved)
• operate on a sub-millisecond level (produced timestamps are in nanoseconds)
• are generated in a lock-free manner

Implementation Details

The generated HLC timestamp has two components (see HlcTimestamp):

#[derive(Hash, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub struct HlcTimestamp {
    /// Wall-clock time.
    ///
    /// Timestamp in nanoseconds since the Unix epoch.
    pt: i64,

    /// The logical clock value.
    ///
    /// Captures causality for events that occur at the same wall-clock time.
    lc: u64,
}

Basically, you have two counters, one for the wall-clock time and another for the logical clock. The logical clock is used to resolve the "happened before" relationship between events that occur at the same, that is when granularity of the wall-clock time is not small enough to distinguish between events.

Sample Use Case

Since HLC timestamps are based on the wall-clock time, they are quite useful in algorithms that require ordering of events, or that need to determine how far apart two events are in time.

For example, HLC timestamps can be used to implement page replacement algorithms, where page accesses are marked with HLC timestamps. This allows the algorithm to determine which pages are good candidates for eviction based on their access patterns: remove the least recently accessed page, but making sure that it has been added more than 5 minute ago (based on Jim Gray's 5 minute rule idea ).

Usage

use hlc_gen::{HlcGenerator, HlcTimestamp, UtcTimestamp};

// Create a new HLC generator.
let g = HlcGenerator::default();

// Generate a new HLC timestamp for local or send event.
let ts: HlcTimestamp = g.next_timestamp()
                        .expect("Failed to generate timestamp");

// When message comes from another node, we can update
// the generator to preserve the causality relationship.
let another_ts = HlcTimestamp::from_parts(1234567890, 1234567890);
g.update(&ts)
 .expect("Incoming message has timestamp that is drifted too far");

// Newly generated timestamp will "happen after" both
// the previous local and incoming remote timestamps.
let ts: Option<HlcTimestamp> = g.next_timestamp();