HLClock

v0.1.2

HLClock v0.1.2 HLClock View Source

Hybrid Logical Clock

Provides globally-unique, monotonic timestamps. Timestamps are bounded by the clock synchronization constraint, max_drift.

Implementation assumes that timestamps are (at a minimum) regularly sent; a clock at rest will eventually be unable to generate timestamps due to assumed bounds on the logical clock relative to physical time.

In order to account for physical time drift within the system, timestamps should regularly be exchanged between nodes. Generate a timestamp at one node via HLClock.send_timestamp/1; at the other node, call HLClock.recv_timestamp/2 with the received timestamp from the first node.

Inspired by https://www.cse.buffalo.edu/tech-reports/2014-04.pdf

Link to this section Summary

Functions

before?(t1, t2)

Determines if the clock’s timestamp “happened before” a different timestamp

max_drift()

Configurable clock synchronization parameter, ε. Defaults to 300 seconds

now()

Functionally equivalent to using send_timestamp. This generates a timestamp for local causality tracking

recv_timestamp(remote)

Given the current timestamp for this node and a provided remote timestamp, perform the merge of both logical time and logical counters. Returns the new current timestamp for the local node

send_timestamp()

Generate a single HLC Timestamp for sending to other nodes or local causality tracking

start_link(opts \\ [])

Starts and links the supervision tree

to_datetime(timestamp)

Create a millisecond granularity DateTime struct representing the logical time portion of the Timestamp

to_os_time(timestamp)

Return the logical, monotonic time portion. Unlike System.monotonic_time, if timestamps are regularly exchanged with other nodes and/or clients, this monotonic timestamp will represent a cluster wide monotonic value

Link to this section Functions

Link to this function before?(t1, t2) View Source

Determines if the clock’s timestamp “happened before” a different timestamp

Link to this function max_drift() View Source

Configurable clock synchronization parameter, ε. Defaults to 300 seconds

Link to this function now() View Source

Functionally equivalent to using send_timestamp. This generates a timestamp for local causality tracking.

Link to this function recv_timestamp(remote) View Source

Given the current timestamp for this node and a provided remote timestamp, perform the merge of both logical time and logical counters. Returns the new current timestamp for the local node

Link to this function send_timestamp() View Source

Generate a single HLC Timestamp for sending to other nodes or local causality tracking

Link to this function start_link(opts \\ []) View Source

Starts and links the supervision tree.

Link to this function to_datetime(timestamp) View Source

Create a millisecond granularity DateTime struct representing the logical time portion of the Timestamp.

Given that this representation loses the logical counter and node information, it should be used as a reference only. Including the counter in the DateTime struct would create absurd but still ordered timestamps.

Example 

iex> {:ok, t0} = Timestamp.new(1410652800000, 0, 0)
{:ok, %HLClock.Timestamp{counter: 0, node_id: 0, time: 1410652800000}}
iex> encoded = Timestamp.encode(t0)
<<1, 72, 113, 117, 132, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>
iex> << time_and_counter :: size(64), _ :: size(64) >> = encoded
iex> DateTime.from_unix(time_and_counter, :microsecond)
{:ok, #DateTime<4899-07-30 06:31:40.800000Z>}
Link to this function to_os_time(timestamp) View Source

Return the logical, monotonic time portion. Unlike System.monotonic_time, if timestamps are regularly exchanged with other nodes and/or clients, this monotonic timestamp will represent a cluster wide monotonic value.