brazier/store/hlc

Hybrid logical clock (Kulkarni, Demirbas et al., “Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases”, 2014), used to order writes to a replicated store.

A timestamp is the wall clock in milliseconds, a logical counter that orders events within the same millisecond (or while the wall clock lags a timestamp already seen), and the writing node’s name. Timestamps compare by wall time, then logical counter, then node name, so every two timestamps from different nodes are ordered the same way on every node.

The clock never goes backwards: tick (a local write) and observe (a remote write merged here) both return a timestamp strictly greater than every timestamp this node has produced or seen, even if the wall clock stepped back.

Types

Timestamp

</>

One hybrid logical clock reading.

pub type Timestamp {
  Timestamp(wall_ms: Int, logical: Int, node: String)
}

Constructors

Timestamp(wall_ms: Int, logical: Int, node: String)

Values

compare

</>

pub fn compare(a: Timestamp, b: Timestamp) -> order.Order

Total order: wall time, then logical counter, then node name.

drift_ms

</>

pub fn drift_ms(remote: Timestamp, now_ms: Int) -> Int

How far remote is ahead of the wall clock, in milliseconds (0 if it is not ahead). The replica logs a warning above its drift threshold.

max

</>

pub fn max(a: Timestamp, b: Timestamp) -> Timestamp

The later of two timestamps.

observe

</>

pub fn observe(
  last: Timestamp,
  remote: Timestamp,
  now_ms: Int,
) -> Timestamp

The clock after merging a remote timestamp: greater than both last and remote. Keeps this node’s name.

tick

</>

pub fn tick(last: Timestamp, now_ms: Int) -> Timestamp

The timestamp of a local event (a write on this node). last is the clock’s current value, now_ms the wall clock.

to_string

</>

pub fn to_string(ts: Timestamp) -> String

wall_ms.logical@node, for logs.

zero

</>

pub fn zero(node: String) -> Timestamp

The clock of a node that has not produced or seen any timestamp yet.