uhlc-rs

A Unique Hybrid Logical Clock for Rust.

This library is an implementation of an Hybrid Logical Clock (HLC) associated to a unique identifier. Thus, it is able to generate timestamps that are unique across a distributed system, without the need of a centralized time source.

Usage

Add this to your Cargo.toml:

[dependencies]
uhlc = "0.2"

Then in your code:

use uhlc::*;

// create an HLC with a generated UUID and relying on SystemTime::now()
let hlc = HLC::default();

// generate a timestamp
let ts = hlc.new_timestamp();

// update the HLC with a timestamp incoming from another HLC
if ! hlc.update_with_timestamp(&other_ts).is_ok() {
    println!(r#"The incoming timestamp would make this HLC
             to drift too much. You should refuse it!"#);
}

What is an HLC ?

A Hybrid Logical Clock combines a Physical Clock with a Logical Clock. It generates monotonic timestamps that are close to the pysical time, but with a counter part in the last bits that allow to preserve the "happen before" relationship.

You can find more detailled explanations in:

• This blog: http://sergeiturukin.com/2017/06/26/hybrid-logical-clocks.html
• The original paper: https://cse.buffalo.edu/tech-reports/2014-04.pdf

Why "Unique" ?

In this implementation, each HLC instance is associated with an identifier that must be unique accross the system (by default a UUIDv4). Each generated timestamp, in addition of the hybrid time, contains the identifier of the HLC that generated it, and it therefore unique across the system.

Such property allows the ordering all timestamped events in a distributed system, without the need of a centralized time source or decision.

Note that this ordering preserve the "happen before" relationship only when events can be correlated. I.e.:

• if 2 events have the same source, no problem since they will be timestamped by the same HLC that will generate 2 ordered timestamps.

• if an entity receives an event with a timestamp t1, it must update its HLC with t1. Thus, all consecutive generated timestamps will be greater than t1.

• if 2 events have different sources that have not exchanged timestamped events before, as the physical clocks on each source might not be synchronized, it may happen that the HLCs generate timestamps that don't reflect the real physical ordering. But in most cases this doesn't really matter since there is no a real correlation between those events (one is not a consequence of the other).

Implementation details

The uhlc::HLC struct is created with 2 parameters:

• a unique identifier (as a uhlc::ID)
• a physical clock function (as a fn () -> NTP64)

The uhlc::HLC::default() operation generate an UUIDv4 as identifier and uses std::time::SystemTime::now() as physical clock. But the uhlc::HLC::with_clock(id, clock) operation allows you to provide your own unique id and physical clock.

A uhlc::HLC::NTP64 time is 64-bits unsigned integer as specified in RFC-5909. The first 32-bits part is the number of second since the EPOCH of the physical clock, and the second 32-bits part is the fraction of second. In case its generated by an HLC, the last few bits of the second part are replaced by the HLC logical counter. The size of this counter currently hard-coded to 4 bits in uhlc::CSIZE.

To avoid a "too fast clock" to make an HLC drift too much in the future, the uhlc::HLC::update_with_timestamp(timestamp) operation will return an error if the incoming timestamp exceeds the current physical time more than a delta (currently hard-coded to 100ms). In such case, it could be wise to refuse or drop the incoming event, since it might not be correctly ordered with further events.

Usages

uhlc is currently used in Eclipse zenoh.