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 compared with the others. On a single machine its clock is enough, but in a cluster every node has its own and none of them fully agrees with the rest. TeselaDB settles that order with hybrid logical clocks (HLC), with no central clock to ask on every write and no atomic clocks in the data centres.

Why an order is needed

Picture two writes to the same order that reach different nodes a few milliseconds apart. If each node stamps them with its physical clock and one of those clocks runs ahead, the write that happened later can carry the smaller timestamp, and a read that looks at versions by timestamp will return an order that no longer exists. The database needs an order that respects causality. Hybrid clocks give it with no extra coordination. Each timestamp stays close to the physical clock, so it can be read as a time of day. Even so, it never goes back on what a node has already seen.

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. Two timestamps are compared first by their milliseconds and, when those are equal, by the counter, so within a single millisecond a node can stamp many versions without two of them matching. With 4 bytes, the counter takes more than four billion different values in every millisecond.

How a node's clock moves

Each node moves its timestamp forward with its physical clock, and when it receives a message carrying a timestamp greater than its own it adopts it and keeps counting from there. An example with numbers. Node A stamps a write at 10:00:00.500 and sends it to node B, whose clock reads 10:00:00.480 because it runs 20 ms behind. B stamps nothing below what it has received. Its next timestamp is 10:00:00.500 with the counter at 1, and from there it goes on with its own clock as soon as that clock reaches the same time. If an event on one node causes another on a different node, the second one always carries the greater timestamp, even when the second node's clock runs late.

The uncertainty window

The problem comes with writes that have not talked to each other. The clocks of two nodes can differ by up to 250 ms, because each one stays within 125 ms of the cluster median. Suppose a read with timestamp t finds a version written on another node at t + 100 ms. By the timestamps, that version is later. But the other node's clock may have been ahead, and the write may have finished before the read started, with no way to know it from inside the cluster. That is why any version the read finds within the 250 ms after its timestamp makes it restart with a greater timestamp so that it sees it. The same goes for a pending write of a transaction and for a commit the read learns about on its way.

When the restart goes unnoticed

If the read is the first statement of a transaction or a read on its own, the node restarts it by itself, and your application only sees that the query took a little longer. If the version shows up in a later statement, the transaction has already read data at the old timestamp and cannot change it halfway. It then fails with WriteConflict and the TransientTransactionError label. MongoDB drivers retry it on their own, just as they retry a transaction that clashes with another in MongoDB, so code that already handles those errors stays the same.

Reads with no uncertainty

The window only exists when the read timestamp comes from the clock of the node that serves the read. A read at a historical timestamp has none, because nobody assigns that timestamp at the moment. That happens when the client passes atClusterTime and when it reads from a follower without afterClusterTime, and in those two cases the read never restarts for uncertainty, however close a write is to its timestamp.

The wait on commit

The other half of the deal is missing. When a transaction commits, its commit timestamp comes from the clock of the node that coordinates it, which may run ahead of the others. Before answering the client, that node waits until its wall clock reaches the commit timestamp. Thanks to that wait, any transaction that starts after the answer either sees it directly or finds it inside its window and restarts to see it. The rule is checked with a TLA+ model, together with the one for the window.

When a clock drifts

The window and the wait rest on no clock drifting more than 125 ms from the median. Group 0 computes each node's deviation from the median of the voters' clocks, and a node that goes over it hands over its leaderships and takes none until it is back within the margin. If a node's clock runs 400 ms ahead, for example, it stops leading ranges until it is corrected. That is why every machine of the cluster needs NTP. Without it, this happens to a node often.

What you see from your application

Reads never return a result that contradicts the real order of the writes, even when the clocks of your machines do not agree. In exchange, some reads restart and take a little longer. Each node publishes the uncertainty restarts in its metrics, next to transaction commits and aborts by reason. With them you know how many reads pay that cost, and if the figure jumps, the first thing worth checking is clock synchronisation. The Hybrid clocks and Consistency and isolation pages of the documentation tell the same rules with fewer examples.