Hybrid logical clock

A distributed clock which preserves logical ordering and which roughly approximates physical time. That is, like a Lamport clock, it allows us to capture causation: if event A happened before event B, the clock value for A will definitely be less than that of B. It doesn’t allow us to say the converse (i.e. that if one clock value is smaller than another, then the former definitely happened before the latter). But a hybrid logical clock makes the converse approximately true by bounding the logical clock value to be quite close to the physical clock value.

The causation property allows these clocks to be used for space-efficient syncing mechanisms when Building local-first apps.

The clock representation has two components: l and c; the former is meant to represent physical time; the latter is used to capture causality when l is ambiguous. l is always maintained at the maximum of local physical time and the latest-known remote event. c is incremented whenever l is ambiguous and reset whenever l changes.

The algorithm:

HLCs can be made to fit into 64 bits by expressing the timestamp as a 32-bit second, a 16-bit fractional second, and using a 16-bit value for c, which should be more than enough. This allows up to 65536 events in the same 15µs interval, or an event every roughly 2ns. That should be enough under most circumstances, though to prevent fingerprinting browsers may round their time representations to the nearest millisecond, in which case this 64-bit representation would allow for one event every 15µs, which might not be enough for a tight loop.

Q. What does “hybrid” refer to in “hybrid logical clock”?
A. It’s approximately a physical clock, too, and its value is partially determined by physical clocks.

Q. How do hybrid logical clocks improve upon physical clocks?
A. By guaranteeing strong (one-way) causal ordering guarantees.

Q. How do hybrid logical clocks improve upon Lamport/logical clocks?
A. They closely approximate physical time, which is often important for program semantics and debugging.

Q. In what way are hybrid logical clocks more efficient than vector clocks?
A. Uses bounded space.

Q. In what way are hybrid logical clocks more convenient than vector clocks?
A. They closely approximate physical time.

Q. In what key way are hybrid logical clocks less powerful than vector clocks?
A. They can’t strictly guarantee that if A’s clock value is less than B, then A happened before B—though they approximate this quite closely.

Q. Why is the strong one-way causal ordering of hybrid logical clocks particularly useful for distributed systems?
A. It allows for consistent global snapshots (i.e. find all events which occurred before X time).

Q. What is the strong guarantee made by hybrid logical clocks?
A. If A happened before B, then A’s clock value is less than B’s clock value.

Q. What is the approximate ordering guarantee made by hybrid logical clocks?
A. The logical value of an event is close to the physical time of the event, so it’s approximately true that if A’s clock value is less than B’s clock value, then A happened before B.

Q. What are the two components of a hybrid logical clock’s value?
A. $l$, approximating physical time; and $c$, a simple counter used to capture causality when $l$ is ambiguous.

Q. How is a hybrid logical clock’s $l$ value updated when sending or receiving messages?
A. It’s updated to the maximum of the constituents and the local physical time.

Q. How is a hybrid logical clock’s $c$ value updated when sending or receiving messages?
A. It’s reset when $l$ is changing and incremented by 1 over the last largest value’s $c$ otherwise.

Q. Why can’t a hybrid logical clock’s $c$ overflow, practically speaking?
A. When physical time advances, $c$ resets. So it only increases continually when one system’s clock is “far behind” another’s.

Q. In what circumstance can a hybrid logical clock’s $c$ overflow?
A. When the local physical time is far behind that of a remote machine.

Q. What problem might you have if you use hybrid logical clock values generated on separate machines as primary keys?
A. The values are not guaranteed to be unique across nodes; monotonicity is only a local guarantee.

References

Kulkarni, S., Demirbas, M., Madeppa, D., & Avva, B. (2014). Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases.