Clocks in distributed systems

Ordering events in a system where every machine keeps its own time

Terry Pratchett’s Thief of Time

This article is a part of a long series on distributed systems fundamentals:

• Introduction to distributed systems

• Scaling

• Latency

• CAP theorem

• Consensus protocols

I found my old collection of Terry Pratchett books last week. I used to buy them for a couple of euros each in high school, and through fantastical satire, they were my first encounter with many real-world problems and ideas.

“Thief of Time” was my favorite.

It’s about inter-dimensional beings who find the world too messy, so they try to stop time to put everything in order once and for all. At 17 years old, I didn’t know how messy time can be, and I didn’t understand the antagonists’ obsession with it.

Now at 32, after working in tech for a decade, I do wish I could stop time.

Clocks

Any article, book, or paper on distributed systems starts with three pieces of information:

1. The system works concurrently on multiple nodes

2. They communicate over an unreliable network

3. There’s no shared clock

I found this last one confusing at first.

In the real world, time flows in one direction. This happens, then that happens. Two things can’t happen at the same time, and they can’t happen out of order.

But in a distributed system, every service is its own universe with its own time.

Services may live on different machines, and their clocks can drift from one another. Any attempt to perfectly synchronize them would be futile because they communicate over a network that takes an arbitrary time to deliver messages.

This wouldn’t matter if we were running a monolith on a single EC2 instance, but at scale, one machine is rarely enough to serve a whole product. The moment we add more machines to our system, we add more clocks, and any attempt to order events based on physical time would not work.

Why?

Clocks lie

You’ve got two people editing the same document.

One person makes an edit, it goes to service A, and gets written. After that, the other person makes an edit, and it goes to service B. However, service B’s clock is running behind, so the system thinks this is an old edit and doesn’t accept it.

In the real world, these events happened one after another.

But the clocks can make them feel out of order.

If we rely on clocks, the one that’s running the fastest always wins, and there are numerous edge cases like this one.

We don’t need time to create order

Time matters because it tells us what happened after what.

We don’t necessarily care about the exact millisecond something happened, but how it fits into the sequence of events and actions. Leslie Lamport, whom I’ve already written about in the previous article, concluded that we need logical clocks, not physical ones

We can use a counter that shows how events relate to one another.

A counter can track the version of each entry, so if the clocks drift or the network distorts the order of messages, we still know if we’re receiving an old entry version or the latest one.

• If the entry’s counter is at version 6, and we receive a smaller number, we know this is an old request.

• If we receive a higher version, we accept it because it moves the entry forward.

At this point, we know that distributed systems are an endless exercise in edge case handling, and while this helps us catch some problems, it doesn’t work out of the box for all of them.

Concurrent requests

Imagine that we accept a clock that bumps an entry to version 6, but then we get another request that wants to update it to the same version.

Clocks alone cannot solve this.

They help us figure out sequencing, but some requests can still happen concurrently. Two people may attempt to update the same entity at roughly the same time, without their clients having the chance to sync the data.

How we solve this problem is a business decision.

• We can say that the latest write wins. But this means that one client may lose their entry without notice.

• We can decline and ask them to reload the data and make a new update.

• We can decline the request, tell the client there’s a conflict, and ask them to merge both changes.

To cover more complex merge and sequencing scenarios, we can use more complex logical clocks - vector clocks or Cockroach DB’s hybrid logical clocks.

Vector clocks store the exact chain of versions that led to the latest update, so if the business requires you to merge conflicting versions, you can do that. If you recognize that two update requests share a common history, the unlucky client whose request came in second can merge them the same way they resolve a git conflict.

Clocks live with the data

One misconception I had when I first read about clocks was where they live.

If every replica needs to keep its own logical clock as an in-memory state, they’d need to be synchronized, which introduces the network again, and that wouldn’t work. And it wouldn’t be just one because you most probably work with many entries, so you’d need to keep all of them. Do this enough times, and you’ve reinvented a distributed database.

So every entry keeps its own logical clock that lives in storage.

It can be a version column, for example. When we update an entry, we first check whether we’re updating it against the current or a higher version. If not, we use one of the policies we outlined above.

This is where all the “there’s a new version of this file“ messages come from.

I even got this error on Substack as I’m writing this: