Grove.HybridLogicalClock (Grove v0.1.1)

View Source

A Hybrid Logical Clock (HLC) combining physical and logical time.

HLCs provide timestamps that:

  1. Are always monotonically increasing
  2. Stay close to physical wall-clock time
  3. Handle clock drift between nodes
  4. Are totally ordered (with node ID as tiebreaker)

Structure

  • time: Physical time in milliseconds
  • counter: Logical counter for events at same millisecond
  • node: Node identifier for tiebreaking

Advantages over Lamport Clocks

  • Timestamps correlate with real time (useful for debugging)
  • Bounded divergence from wall clock
  • Better semantics for Last-Write-Wins registers

Example

iex> hlc = Grove.HybridLogicalClock.new(:node_a)
iex> hlc = Grove.HybridLogicalClock.tick(hlc)
iex> hlc.time > 0
true

References

Based on "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" by Kulkarni et al.

Summary

Types

node_id()
t()

Functions

after?(hlc1, hlc2)

Returns true if hlc1 happened after hlc2.

before?(hlc1, hlc2)

Returns true if hlc1 happened before hlc2.

compare(hlc1, hlc2)

Compares two HLCs for ordering.

from_tuple(arg)

Creates an HLC from a tuple.

merge(hlc1, hlc2)

Merges two HLCs, returning the one that happened later.

new(node)

Creates a new HLC for the given node.

tick(hlc)

Records a local event, advancing the clock.

to_tuple(hybrid_logical_clock)

Returns the timestamp as a comparable tuple.

update(local, hybrid_logical_clock)

Updates the local clock upon receiving a remote timestamp.

Types

node_id()

@type node_id() :: term()

t()

@type t() :: %Grove.HybridLogicalClock{
  counter: non_neg_integer(),
  node: node_id(),
  time: non_neg_integer()
}

Functions

after?(hlc1, hlc2)

@spec after?(t(), t()) :: boolean()

Returns true if hlc1 happened after hlc2.

before?(hlc1, hlc2)

@spec before?(t(), t()) :: boolean()

Returns true if hlc1 happened before hlc2.

compare(hlc1, hlc2)

@spec compare(t(), t()) :: :before | :after | :equal

Compares two HLCs for ordering.

Returns:

  • :before if hlc1 < hlc2
  • :after if hlc1 > hlc2
  • :equal if they are identical

from_tuple(arg)

@spec from_tuple({non_neg_integer(), non_neg_integer(), node_id()}) :: t()

Creates an HLC from a tuple.

merge(hlc1, hlc2)

@spec merge(t(), t()) :: t()

Merges two HLCs, returning the one that happened later.

new(node)

@spec new(node_id()) :: t()

Creates a new HLC for the given node.

tick(hlc)

@spec tick(t()) :: t()

Records a local event, advancing the clock.

If physical time has advanced, reset counter. Otherwise increment counter.

to_tuple(hybrid_logical_clock)

@spec to_tuple(t()) :: {non_neg_integer(), non_neg_integer(), node_id()}

Returns the timestamp as a comparable tuple.

Useful for sorting or storing.

update(local, hybrid_logical_clock)

@spec update(t(), t()) :: t()

Updates the local clock upon receiving a remote timestamp.

Takes the maximum of local time, remote time, and physical time. Adjusts the counter appropriately.