Hybrid clocks without atomic clocks

For a read to see a consistent state of the database, each version of a document needs a timestamp that says in which order it happened. TeselaDB uses hybrid logical clocks (HLC). It needs neither a central clock nor atomic clocks.

What a timestamp carries

HLC timestamp = [ 8 bytes: physical milliseconds ][ 4 bytes: logical counter ]

Each timestamp joins 8 bytes of milliseconds from the physical clock and 4 bytes of a logical counter. Each node moves its timestamp forward with its clock. When it gets a message with a timestamp greater than its own, it takes it, so if one event on a node causes another on a different node, the second event always carries the greater timestamp.

The uncertainty window

The clocks of two nodes can differ by up to 250 ms, because each one stays within 125 ms of the cluster median. A read that finds a version inside that window ahead of its timestamp cannot tell whether it happened before it. In that case it restarts at a later timestamp to see it, so some reads take a little longer. In exchange, reads never return a result that contradicts the real order of the writes.

When a clock drifts

A node whose clock drifts more than 125 ms from the median gives up its leaderships until it is back within the margin. Every machine of the cluster needs NTP. Without it, that happens to a node often. More detail in Hybrid clocks and Consistency and isolation.