The distinction between the past, present and future is only a stubbornly persistent illusion. — Albert Einstein
Have you ever seen a reply show up above the message it was answering on your text app? You ask someone out for lunch, and their "sure, 1 pm works" appears first.
Or consider this: your account has a balance of 500. You get paid 10,000, and a few seconds later you pay an 8,000 bill. The deposit is handled by one server and the bill payment by another. If the second server thinks the payment came first, it sees a balance of 500 and declines it, even though in real life the deposit came first.
These two cases, at core, are just machine(s) disagreeing about which message came first.
Distributed systems live up to their name (duh). There are a lot of machines running at the same time, and there's no single clock they can all trust. Each machine keeps its own time. The number one question you should ask while setting up or working with a distributed system is: how do these machines communicate? Or, more precisely, in what order did things happen? It all comes down to how we resolve and perceive time.
So, distributed systems have no shared clock. Every machine keeps its own, they disagree, and messages take an unpredictable time to arrive.
A question that sounds trivial, "which of these two events happened first?", has no obvious answer.
I'll make an attempt to answer it through each clock in this blog.
Quick terminology
A few words I'll keep using, so we're on the same page:
- Node: one machine in the system. A server, a database replica, whatever. For simplicity, I'll just say node everywhere.
- Event: something that happens on a node. Classify "events" into three types, and every story in this blog is built from them. A local event is something that happens on the node by itself, like writing a file. A send is the node sending a message to another node. A receive is a message arriving.
- Message: how nodes talk to each other. Messages take some unpredictable amount of time to arrive.
- Timestamp: a label we stick on an event so we can order it later. Every clock in this blog is just a different way of making that label.
- Cause and effect: This is important. if event A could have influenced event B (A is a send and B is its receive, or A simply came earlier on the same node), then A is the cause and B is the effect. Any clock worth using should never put an effect before its cause.
- Unrelated: two events with no chain of messages connecting them, so neither could have influenced the other. You'll also see this called "concurrent".
To explore all clocks fairly, we'll run the same small story through each one. There are three nodes (0/1/2)
Node 0 does something locally and sends a message to node 1.
Node 1 receives it and sends a message to node 2.
Meanwhile, node 2 does something entirely on its own before receiving.
Each clock reads this same story, fixes the line the previous clock got wrong, and introduces a new weakness that motivates the next.
All of this lives in SaaT, SaaT (Saat, Turkish for "Time") is an exhaustive set of distributed systems clocks and causal ordering algorithms implemented from scratch in Go. It has one folder per clock (sometimes two), and every folder tells this exact story.
1. Physical clocks
The obvious approach that would come to your mind is to simply compare the time on each node. Enter the physical clock.
yep, the time we're used to seeing on our watches and on our phones.
If your watch says 12:00:01 when you do X, and mine says 12:00:02 when I do Y, you'd say X happened first. That is all "ordering by physical time" means: compare the two readings.
The blog should have been done and dusted here, but its not. mainly due to how the clocks run in the first place. These clocks run off a quartz crystal that vibrates at a nearly fixed frequency, and a counter that turns those vibrations into a time of day like 12:00:01.250. Each machine has its own crystal that keeps its own reading. A timestamp is just that reading, and the best practice is to store it in UTC so there's no timezone conversion needed.
And these crystals aren't identical. Ordinary hardware drifts by roughly 10 to 100 parts per million, which at 50 ppm is about 4 seconds a day. Temperature, load and age all change the rate. So the time keeps on "drifting". This drift is called skew. Let's understand it with an example:
- How wrong node 1's clock is: 50 ms slow
- How long the message takes to travel: 20 ms
consider our three node story:
1. At true time 12:00:00.100, node 0 sends the message. Its clock is correct, so it stamps .100.
2. The message travels for 20 ms and arrives at true time 12:00:00.120.
3. Node 1's clock is 50 ms slow, so when it looks at its watch it sees .070, and stamps the receive .070.
So the send is stamped .100 and the receive .070. This makes it look like "effect" happen before its "cause".
The useful rule is that ordering breaks whenever the clock error is bigger than the gap between the events. Here the error is 50 ms and the message took 20 ms, so it breaks. If node 1 were only 10 ms slow, it would show .110, which is after .100, and everything would look fine by luck. In fast systems, events are often only a few milliseconds apart, so this happens all the time.
SaaT's 01-physical replays our three-node story with a slightly wrong clock to simulate exactly this on each node.
Fixing the skew:
The fix is simple -- ask someone who has the right time. That's literally what NTP (Network Time Protocol) does.
But who has the right time you ask?
GPS satellites.
Each satellite carries atomic clocks (very accurate clocks) and keeps broadcasting the time, like a radio station. They don't talk back, just relay.
Some organisations (Google, Cloudflare, maybe even your uni) plug a GPS receiver or an atomic clock into a server, which is really just an antenna listening to that broadcast. That server's clock is nearly perfect, and it runs NTP software, so anyone on the internet can ask it for the time.
These servers are arranged in layers, called strata. Stratum 0 is the actual GPS or atomic clock, stratum 1 servers are wired directly to one, stratum 2 servers ask stratum 1, and so on. Your laptop usually sits a few layers down, and every layer adds a tiny bit of error. In the background, your OS quietly asks a few of these servers every few minutes to every few hours.
PS: in SaaT (realNTP), we ask an NTP server of the skew our local machine (laptop has).
Simple enough: your machine asks, the server replies. The hard part is that the reply takes time to travel back, so by the time you read it, it's already a little old. How do we deal with that?
NTP tries to solve this by noting 4 different timestamps:
- t0: when I sent the request (my clock)
- t1: when the server received it (server's clock)
- t2: when the server sent the reply (server's clock)
- t3: when I received the reply (my clock)
Consider this case -- my clock is 100 ms slow, the server's is correct, and each trip takes 20 ms. Let's assume the truetime when I send is 12:00:00.000.
- t0 = 11:59:59.900 (my slow clock)
- t1 = 12:00:00.020 (the server)
- t2 = 12:00:00.020 (it replies instantly)
- t3 = 11:59:59.940 (my slow clock, at true time .040)
Now look at each trip, as the clocks see it:
- The trip there looks like 120 ms (t1 − t0). It really took 20 ms, plus my 100 ms error.
- The trip back looks like −80 ms (t3 − t2). It really took 20 ms, minus my 100 ms error. A negative trip: according to my slow clock, the reply arrived before the server even sent it. That's the giveaway that my clock is behind.
Flip the sign on the second one (that's the t2 − t3 in the formula below, which is +80) and add them: 120 + 80 = 200. The 20 ms of travel time cancels out, my 100 ms error gets counted twice, and halving it gives me 100 ms. I'm 100 ms slow, so I move my clock forward by 100 ms.
That's the whole formula:
offset = ((t1 − t0) + (t2 − t3)) / 2
The first bracket is the trip there, the second is the trip back with its sign flipped. Add them up, halve it, and what's left is the error. A positive offset means the server is ahead of us.
where NTP falls short:
There's a catch, and it's the key weakness. The averaging only works if the trip there and the trip back took equal time. If the way there took 20 ms and the way back took 60 ms, the answer is wrong by half the difference, and we have no way to determine if it happened.
That is why NTP gives you an estimate, never a promise.
We try to solve this though. If the error is small, the OS slews, basically meaning that it runs the clock a tiny bit faster or slower until it catches up, so time never jumps.
If the error is big (classic ntpd uses 128 ms), it steps: it just changes the time instantly. Steps cause trouble, as you'll see below.
There are other methods to sync as well. NTP is the popular one, but we'll see these being used here and there and these are worth mentioning:
- Cristian's algorithm is the simplest version. Ask one trusted server for the time, then set your clock to its answer plus half the round trip, since the reply was already that old. It's like phoning a friend who has a correct watch: they say "it's 3:00," the call took 2 seconds, so you set 3:00:01. NTP is this idea made smarter.
- Berkeley algorithm is for when nobody has the right time. A leader asks everyone for their reading, averages them, and tells each machine how much to adjust. Say the leader reads 10:00:00, machine A reads 10:00:03 and machine B reads 09:59:57. The average is 10:00:00, so A is told "go back 3 seconds" and B is told "go forward 3 seconds." It sends adjustments rather than a time, because a time would be stale by the time it arrived. The group agrees with itself, though not necessarily with the real world.
- PTP (Precision Time Protocol) is NTP's idea with better stopwatches. NTP's timestamps are taken by software, which gets delayed by the operating system. PTP has the network card stamp the packet in hardware at the exact moment it leaves or arrives. That cuts the error from milliseconds to microseconds. Finance, telecom and big datacenters use it.
- GPS and atomic clocks directly. An atomic clock keeps time by counting the vibrations of atoms, which is so stable it would take millions of years to be a second off. GPS is basically atomic clocks delivered by radio. If you put a receiver in your own datacenter, you skip the internet entirely. Google does this, and it's the starting point for TrueTime later.
| Method | Who talks to whom | Rough accuracy |
|---|---|---|
| NTP | your machine asks servers over the internet | a few milliseconds, or under 1 ms on a good LAN |
| Cristian | your machine asks one server | similar to one NTP exchange |
| Berkeley | a leader polls the group and averages | the group agrees internally |
| PTP | machines sync with hardware timestamps | microseconds or better |
| GPS or atomic clock | direct reference clock in the building | well under a microsecond |
Our fixes cause problems too
Disadvantages:
- No node can see true time, only its own clock.
- NTP adds a second problem: it can step a clock backward, so a single machine can stamp a later event with an earlier time. event happening before cause.
- Even after syncing, your clock is off by an unknown amount, and nothing tells you how much.
- all this catching up has to deal with leap seconds, which are very real. (Not to be confused with leap years, which are just calendar housekeeping, the extra Feb 29. Those don't bother clocks.)
That last one deserves a closer look, because leap seconds are probably the strangest way a clock can break. The Earth's spin is slightly irregular and slowing down, while atomic clocks tick perfectly, so the two slowly drift apart. Every now and then a standards body announces an extra second at the end of June or December: 23:59:59, then 23:59:60, then 00:00:00. There have been 27 since 1972, the last one at the end of 2016.
For computers it's a headache, because Unix time pretends every day has exactly 86,400 seconds and has no way to show :60. The clock usually repeats a second, which means time goes backward. That has taken real systems down; Cloudflare's DNS outage on 1 January 2017 is a well-known example. The fix is smearing: instead of adding one whole second at once, stretch the final hours (Google and AWS use 24 hours) so that every second is a hair longer, about 11.6 microseconds. Nothing ever jumps.
Put all of this together (drift, steps, an unknown error, leap seconds) and the picture is pretty clear: in a distributed system, physical timestamps can't be trusted to order events that happened close together. A physical clock is fine for measuring how long something took on one machine, but it's not fine for comparing events between two machines.
The conclusion: let's stop asking "what time is it?" and ask the question we actually care about, "what could have influenced what?" To answer that, let's try dropping time from the equation entirely. Enter Lamport clocks.
2. Lamport clocks
Mr. Lamport, in 1978 wrote a paper called Time, Clocks, and the Ordering of Events in a Distributed System, and the idea is to throw time away entirely and rather focus on keeping a counter for events.
What each node carries
Each node carries one number -- a counter that starts at 0. No time.
This counter roughly describes how many events have happened on this node, as far as it knows. Each node also has an ID.
So a single timestamp looks like
counter + nodeID
comparison and working:
During comparison, we compare the counters first. If they're equal, compare the node IDs.
How Mr. Lamport thought of using this combination of a counter and a node ID is rather interesting. The counter does the real work: it goes up with every event, and on a receive it jumps past whatever the sender had, so an effect always ends up with a bigger number than its cause. The node ID is only a tie-breaker. Two different nodes can easily land on the same counter, and we want every pair of events to have a definite order, so we settle ties by node ID. It's arbitrary, but everyone agrees on it.
Here's the origin story, which Lamport tells himself on his page for the paper. It started with a note by Paul Johnson and Bob Thomas about keeping duplicate databases in sync using message timestamps. Lamport, who had a solid grasp of special relativity (where different observers can disagree about which of two events happened first), saw what their algorithm was really doing: using timestamps to get a total ordering of events that agrees with causality. Their version didn't quite get it right, and it could produce anomalies that violated causality, so he wrote a short note correcting it. The paper grew out of that.
The trick in the paper is to define "happened before" without any physical clock, using three rules: events on the same node are ordered, a send happens before its receive, and if A happened before B and B before C, then A happened before C. Two events with no such chain between them are concurrent (our "unrelated"). From there, a logical clock only has to satisfy one condition: if A happened before B, A's number must be smaller than B's. That's exactly what the counter rules give us, and the node ID is added at the very end, only to turn this partial order into a total one.
How it runs
Three rules:
- Local event: counter = counter + 1.
- Send: counter = counter + 1, then attach the counter to the message.
- Receive: counter = max(own counter, counter in the message) + 1.
for our 3 node simulation, lamport clocks would look something like
Every counter starts at 0, and each row below is one event, in the order they happen:
| Step | Node | What happens | Counter | Message carries |
|---|---|---|---|---|
| 1 | 0 | local event | 0 → 1 | |
| 2 | 0 | sends to node 1 | 1 → 2 | 2 |
| 3 | 1 | receives from node 0 | max(0, 2) + 1 = 3 | |
| 4 | 1 | sends to node 2 | 3 → 4 | 4 |
| 5 | 2 | local event (on its own, nobody told it anything) | 0 → 1 | |
| 6 | 2 | receives from node 1 | max(1, 4) + 1 = 5 |
final state: node 0 = 2 node 1 = 4 node 2 = 5
The two receives (steps 3 and 6) are the interesting ones: in both, the node's counter jumps up to catch up with the number the message carried.
In our simulation, there are two different kinds of receives:
- catch-up case: The first is the catch-up case, where the message is ahead of you. Node 1 was at 0 and the message said 2, so it jumps to 3. Your counter takes the sender's knowledge onboard.
- already-ahead case: : you're ahead of the message. Suppose node 2 had done nine local events (counter 9) before the message stamped 4 arrived. max(9, 4) + 1 = 10. The message teaches you nothing new, and the receive just counts as another event.
either way the
+ 1makes the receive bigger than the send.
SaaT's 02-lamport is a single file that runs this exact story:
If event A could have caused event B, then A's number is smaller than B's. Or, put differently, a receive is always stamped above its send. That fixes the problem physical clocks had, where the receive got a smaller timestamp than the send, and no clock skew can break it, because there's no physical time involved at all.
Where it breaks
It only works one way. If A happened before B, then L(A) < L(B). But if L(A) < L(B), we cannot conclude that A really caused B. They might be unrelated as well.
Look at node 0's send, which got 2, and node 2's local event, which got 1. Lamport says node 2's event came first, but the two have nothing to do with each other. (unrelated)
So we have a clear problem to solve: we also need a way of figuring out which events are unrelated and which are not. Enter vector clocks.
3. Vector clocks
Take it this way: vector clocks are just Lamport clocks that can say "unrelated".
A single counter can't say "unrelated" because it squeezes everything a node knows into one number. A vector clock stops this squeezing. It keeps one counter per node, so with three nodes you'd have something like [node 0 counter, node 1 counter, node 2 counter].
Slot 0 means "how many events on node 0 do I know about", slot 1 is the same for node 1, and so on. (I count nodes from 0 because that's how the code indexes them.) A node's own slot counts its own events, and the other slots are what it has heard about the others.
How it runs
Everyone starts at [0,0,0].
- Local event: add 1 to your own slot only. Node 0:
[0,0,0]→[1,0,0]. - Send: add 1 to your own slot, and attach the whole array. Node 0:
[1,0,0]→[2,0,0], and the message carries[2,0,0]. - Receive: first merge (take the bigger number in each slot), then add 1 to your own slot.
Just like Lamport, the receive comes in different forms depending on who's ahead. The recipe is always the same: for each slot, keep the bigger number (that's the merge), then add 1 to your own slot. Here are three receives, slot by slot:
1) Message ahead everywhere (node 1 receives from node 0)
slot 0 slot 1 slot 2
mine 0 0 0
message 2 0 0
keep bigger 2 0 0 ← the merge
add 1 to own slot (slot 1) → [2, 1, 0]
2) Mixed (node 2 receives from node 1)
slot 0 slot 1 slot 2
mine 0 0 3
message 2 2 0
keep bigger 2 2 3 ← the merge
add 1 to own slot (slot 2) → [2, 2, 4]
3) I'm ahead everywhere (node 1 receives from node 0)
slot 0 slot 1 slot 2
mine 5 4 1
message 2 1 0
keep bigger 5 4 1 ← the merge
add 1 to own slot (slot 1) → [5, 5, 1]
What each case is telling you:
- Message ahead everywhere: the message knows more than I do in every slot, so I take all of it in.
- Mixed (the interesting one): neither side knows everything.
- slots 0 and 1: the message is ahead, so I learn about events I hadn't heard of
- slot 2: I'm ahead (three of my own events the message knows nothing about), so I keep mine
- after the merge I know everything both of us knew, and my receive counts as one more event of mine: 3 → 4
- I'm ahead everywhere: the message teaches me nothing, so the merge changes nothing. The receive is just one more event: 4 → 5.
Now our story, start to finish:
node 0: local [1,0,0] send [2,0,0]
node 1: receive [2,1,0] send [2,2,0]
node 2: local [0,0,1] receive [2,2,2]
comparison:
To compare two events, put their arrays side by side:
- If one is smaller or equal in every slot, it happened first.
- If each is bigger somewhere, they're unrelated. Each knows something the other has never heard of, so neither could have caused the other.
| Event A | Event B | Verdict | Why |
|---|---|---|---|
[2,0,0] |
[2,1,0] |
A before B | B is bigger in slot 1 and equal elsewhere, so B knows everything A knew, plus more |
[2,0,0] |
[0,0,1] |
unrelated | A is ahead in slot 0, B is ahead in slot 2 |
[1,0,0] |
[0,0,1] |
unrelated | two nodes each did something, with no message between them |
Node 2's local event [0,0,1] against node 0's send [2,0,0] is the exact pair Lamport got wrong. The vector says "unrelated", which is the truth.
So vector clocks let us tell which events are unrelated, which wasn't possible with Lamport clocks, and now the guarantee runs both ways: A caused B if and only if A's vector is smaller than B's.
Where it breaks
Three weaknesses:
- Size. One slot per node. For 3 nodes that's nothing. For 1,000 nodes, each message carries 1,000 numbers. In databases the vector is often per piece of data, with one slot per copy (commonly 3), so it's cheaper than it sounds.
- The node count is fixed up front. If a fourth node joins, every existing array is the wrong length.
- It doesnt tell time.
[3,1,2]can't answer "what happened in the last hour?"
Real systems stretched the vector clock in several directions to fix specific problems. Here's each variant in a nutshell, and all of them have a folder in SaaT.
The vector family
Version vectors (clock.go): a vector clock labels events, a version vector labels copies of a piece of data on different nodes. Two replicas compare vectors to see whether one copy is simply newer or whether both were edited independently, which is a real conflict that gets detected instead of silently overwritten. It's what Amazon's Dynamo used for its shopping cart, and Riak followed.
Dotted version vectors (clock.go): a plain version vector can't tell apart two writes that go through the same node, so it either silently drops one or hoards false siblings. A dot tags each value with the exact write that made it, so only genuinely concurrent writes survive. Riak made this its default logical clock from 2.0 onward.
Interval tree clocks (clock.go): every vector so far needs a fixed list of nodes. Here a node owns a piece of an identity interval, splits it when it forks off a helper, and takes it back when the helper leaves, so the clock grows and shrinks with the system and nobody has to hand out IDs. It comes from a 2008 paper.
Matrix clocks (clock.go): a vector tells a node what it knows, a matrix also keeps a guess of what every other node knows, one row per node. The payoff is knowing when everyone has seen an event, so old log entries can be safely thrown away, which is the classic use in replicated logs. The cost is N×N numbers per node.
What's still missing
Look at the whole family together. They can all say "unrelated", but none can say "roughly when", and they all grow with the number of nodes. For debugging, expiry times and "show me the last hour", we want something that looks like time and stays small.
That's the problem with vector clocks. They solve the "unrelated" problem, but they still don't give us time, and they cost memory as the cluster grows.
Enter hybrid clocks.
4. Hybrid logical clocks (HLC)
Enter HLC. HLC lives up to its name, i.e. hybrid. It's simple really. Contains a physical clock for "when", and a small counter for working out causality. You get the best of both (right? more on that later).
What each node carries
Two numbers: (latest time seen, counter).
The latest time seen is not the same thing as your computer's clock. The computer's clock is the physical time right now.
The latest time seen is the highest time this node has ever used or heard
Most of the time the two are the same. They differ when a message arrives from a node whose clock is faster than yours: now the highest time you've heard about is ahead of your own clock, and the node holds on to it until its own clock catches up. For example, say a node's own clock reads 980, and a message stamped 1010 arrives:
my physical clock latest time seen
start 980 980 ← same
message stamped 1010 arrives 980 1010 ← latest is ahead of my clock
10 ms later 990 1010 ← still holding on to 1010
20 ms later 1000 1010 ← still holding on
30 ms later 1010 1010 ← my clock caught up, same again
How it runs
Local event or send: take the bigger of (my latest time seen, my physical clock right now). If my latest time seen didn't change, add 1 to the counter. If it moved forward, reset the counter to 0.
Receive: take the biggest of three things: my latest time seen, the message's latest time seen, and my physical clock right now. The counter then depends on who won that max:
- only the message tied for the win → message's counter + 1
- only my own latest tied → my counter + 1
- both tied → the bigger of the two counters + 1
- my physical clock won alone → reset to 0
run our simulation on the three nodes for HLC:
Physical clocks in the story: node 0 reads 1000 then 1010, node 1 (slow) reads 980 then 990, node 2 reads 1005 then 1065.
node 0 local: physical 1000 → latest 1000, moved forward → (1000, 0)
node 0 send: physical 1010 → latest 1010, moved forward → (1010, 0)
node 1 receive: message (1010,0), physical 980
max(0, 1010, 980) = 1010, only the message won → (1010, 1)
node 1 send: physical 990, but latest is 1010, so max = 1010 → (1010, 2)
(the time can't move, so the counter counts)
node 2 local: physical 1005 → (1005, 0)
node 2 receive: message (1010,2), physical 1065
max(1005, 1010, 1065) = 1065, the physical clock
won alone, reset the counter → (1065, 0)
Three scenarios show up here:
- Catch-up case (node 1's receive). The message was ahead of the physical clock, so node 1 borrows the message's time. Its slow clock (980) is ignored for now. Node 1 is now "living in 1010" until its own clock reaches it.
- Counting case (node 1's send). The clock hasn't advanced past what's been seen, so the counter ticks. This is Lamport behaviour living inside HLC.
- Healthy case (node 2's receive). The physical clock is simply the newest, so HLC behaves like a normal clock, and the counter resets.
There's one more flavor, a tie. If we're at (1010, 3), a message arrives with (1010, 5), and my physical clock reads 1000, the latest time is 1010 from both sides, so the counter is max(3, 5) + 1 = 6.
we also built a real version of this in SaaT, the physical part is the actual time.Now() and you can give one node a deliberately wrong clock, then watch the HLC drift away from its physical clock and come back.
What we solve through HLC is
- Causality is kept: the receive
(1010,1)is bigger than the send(1010,0), despite node 1's slow clock. - The numbers still look like times, so "last hour" queries and expiry times work.
- It stays two numbers, no matter how many nodes there are.
This is the reason CockroachDB and MongoDB use HLC (and why the downsides below don't hurt them much).
Because a lot of what they do with time is about recent time. Nobody minds if "a minute ago" is off by a few milliseconds. What they can't live with is an effect stamped before its cause, and that is exactly what HLC rules out.
A footnote on hybrid vector clocks: if you want "unrelated" detection and time-like numbers, put an HLC pair in every slot of a vector. You genuinely get both, and you pay the vector's size cost again. SaaT has this one too.
Where it breaks
- HLC can't say "unrelated". It is lamport-shaped (this can be solved though, see the hybrid vector footnote above)
- It never tells you how wrong its time might be. HLC absorbs clock error, it doesn't measure it.
There's no error bar. To make that promise, we first have to know how wrong our clocks might be. Enter google's TrueTime.
5. TrueTime
When I was first reading about all of these clocks in order, I felt they were eerily similar to the atomic models, in the way one solved another, and some solved other problems. And the final model(quantum) was based on "uncertainty". The same progression plays out here.
Truetime was developed by Google, TrueTime is a globally distributed clock. It's the core mechanism that allows Google's Spanner to order distributed transactions globally without a single central server.
each node carries an interval, an earliest and a latest
So now "it's not just 1000", but "it's between 998 and 1002". The machine can state the error bar honestly because it knows when it last checked with its GPS or atomic reference, and it knows the worst a crystal can drift since then. Right after a check the interval is narrow, and it widens slowly until the next check. In Google's Spanner the interval is roughly 1 to 7 ms wide.
How it runs
To commit a transaction:
- Ask for the interval, for example
[998, 1002]. - Take the latest end as the transaction's timestamp: 1002.
- Wait until even the earliest end of the clock's interval has passed 1002. This is commit wait. With an error bar of ±2, true time has to reach about 1004, so it waits about 4 ms.
- Only then commit.
Comparison:
Once the wait is over, true time has definitely passed 1002 on every machine. So any transaction that starts after this, anywhere in the world, gets an interval that sits entirely past 1002, and with it a bigger timestamp. Timestamp order now matches real-world order.
You can also compare two events by their intervals:
[998, 1002] vs [1010, 1014] → no overlap, the first is definitely earlier
[998, 1002] vs [1000, 1004] → overlap, can't say, so wait
SaaT also has a real-time version of this: the interval is built from the round-trip times of real NTP servers, and the commit wait actually sleeps.
We're solving External consistency. : If one transaction finishes before another starts in real time, the first one's timestamp is smaller
Where it breaks
- Capital: It costs two things -- special hardware (with GPS receivers and atomic clocks in every datacenter), and waiting, since every commit waits about twice the error bar.
Ending note:
I compared this to the atomic models earlier, where each model fixes the one before it. That only goes so far. Atomic models got replaced, but none of these clocks replace the others.
Each one gives something up to get something else, so you pick the one whose costs you can live with.
| Clock | What it gives you | What it costs |
|---|---|---|
| Physical | simple, human-readable | skew, drift, can jump backward |
| Lamport | cause before effect, one number | can't say "unrelated", not real time |
| Vector family | can say "unrelated" | grows with nodes, not real time |
| HLC | cause before effect, looks like time, two numbers | can't say "unrelated", no error bar |
| TrueTime | real-time order guaranteed | special hardware, commit wait |
And where you've probably already met them:
| Clock | Famous for |
|---|---|
| Physical + NTP | every machine you own. PTP in finance and telecom |
| Lamport | the idea everything else builds on |
| Vector clocks, version vectors | Amazon's Dynamo, Riak |
| Dotted version vectors | Riak |
| Matrix clocks | log garbage collection in replicated systems |
| HLC | CockroachDB, MongoDB |
| TrueTime | Google Spanner |
I was in my fourth semester, sitting in my web development class next to @LowKeyDevs, when I first read about distributed clocks in DDIA by Martin Kleppmann, and i was completely immersed.
I think that was the best part of the entire book, and something that stuck with me. We finally made SaaT, and took the time to sum it all up with this blog, starting from a physical clock that lies about causality and ending with a physical clock that is honest about how wrong it might be.
Comments
Join the discussionNo comments yet. Be the first to comment.
