Whose clock is right? Putting events in order

Many designs have to put events in order. A chat app must show a reply after the question. A log search must show what happened first. A system that keeps only the newest value must know which write is newer. The interviewer asks: "How do you order the messages?"

A weak answer says "sort by timestamp". A strong answer says that each server has its own clock, so two timestamps from two servers cannot be compared safely. Then it gives a fix and its cost: a counter for each conversation, or a logical clock.

At SDE-1 level you should know that clocks differ. At SDE-2 level you should give a fix with a number. At SDE-3 level you should explain what each fix cannot do.

Think of two shops on one street. Each has a wall clock and writes the time on every receipt. One clock is 5 minutes fast. A customer buys in shop A, walks to shop B and buys there, one minute after that. The receipt from shop B shows an earlier time than the receipt from shop A. If you sort the receipts by time, the order is wrong.

Why clocks differ

Every computer has its own clock. It is not perfect: it runs a little fast or a little slow. This is clock drift. Clock skew is the difference between the clocks of two computers at the same moment.

Computers reduce skew by asking a time server over the network, using the Network Time Protocol (NTP). Each answer leaves a small error. The NTP standard says that clients on a fast local network are typically within a few hundred microseconds. It says NTP version 4 is precise within a few tens of milliseconds when the checks are up to 36 hours apart. If the time service stops, the error grows. In a Quick Round on this course, two servers were 20 minutes ahead and 2 minutes behind.

A clock can also jump backwards, when it is corrected or when a leap second is added. A leap second is one extra second that the world adds to the clock now and then. Cloudflare reported that the leap second of 1 January 2017 made a program measure a negative time, and some of its DNS queries failed.

So a computer has two kinds of clock:

• The wall clock shows the date and time. It can jump forwards or backwards. Use it to show a time to a person.
• The monotonic clock only moves forward. Its value means nothing by itself. Subtract two readings to measure how long something took. Use it to measure how long a call takes, and for time limits.

What goes wrong with timestamps

The skews in this lesson are large, as when a time service fails. With a healthy time service the skew is smaller, but events a few milliseconds apart can still swap.

A timestamp from one server can order two events correctly only when the real gap between the events is larger than the skew. In a chat, a reply often comes within a second or less. Skew of a few hundred milliseconds is enough to put a reply first.

The time-ordered IDs of lesson 23 (Snowflake, ULID, UUID version 7) have the same weakness. Their time part comes from the clock of the server that made the ID.

Expiry checks also depend on the clock. A login token that is valid for 15 minutes is checked by the server's own clock. A server that is 20 minutes ahead sees every new token as expired. A server that is 2 minutes behind may see a new token as "not valid yet" for 2 minutes. This happens when the token holds a "not valid before" time. Servers often allow a leeway of 30 to 60 seconds, but a leeway cannot hide a skew of minutes.

Fix 1: a sequence number for each key

Do not ask which message came first in the whole world. Ask only for the order inside one conversation. Give each conversation a counter. Each new message takes the next number: 41, 42, 43. Sort by that number.

The counter must go up in one atomic step (lesson 22), for example:

UPDATE conversations SET last_seq = last_seq + 1
WHERE id = 77 RETURNING last_seq;

This gives an exact order inside one conversation, with no clock. A reader can also find a missing message: after 41 comes 43, so 42 is missing. The costs:

• One place, the row of the conversation, hands out the numbers. In lesson 22, a row that is held for 2 ms takes at most 500 updates per second.
• There is no order between two conversations. That is usually fine.
• A cancelled transaction leaves a gap in the numbers (lesson 23).

Fix 2: logical clocks

Sometimes no single place can give the numbers, because several servers accept events. Then use a logical clock: a counter that does not measure time. It only measures order.

First, a precise meaning. Event A happened before event B if one of these holds:

1. A and B are on the same server, and A came first.
2. A is the sending of a message, and B is the receiving of that message.
3. A chain of the two rules connects them.

If neither happened before the other, the two events are concurrent: neither could have influenced the other.

The Lamport clock. Each server keeps a counter, which starts at 0.

1. Before each event on the server, add 1 to the counter. Sending a message is an event.
2. Every message carries the counter of its sender.
3. When a server receives a message, it sets its counter to the larger of its own counter and the message counter, and adds 1.

If A happened before B, the counter of A is smaller than the counter of B. Sort events by counter. If two counters are equal, put the lower server name first. Every server gets the same order, and no effect comes before its cause. Leslie Lamport described this in 1978. The limit: a smaller counter does not prove that the event happened first. Two concurrent events get counters in some order, and you cannot see that they are concurrent.

The vector clock. Each server keeps a list with one counter for every server. On an event, a server adds 1 to its own entry. A message carries the whole list. On receiving, the server takes the larger value for each entry, and then adds 1 to its own entry. Compare two lists entry by entry. If every entry of A is smaller than or equal to the entry of B, and one is smaller, A happened before B. If neither list is below the other, the events are concurrent. The cost is size: one number for each server.

A chat app with three servers: A, B and C.

Assumptions (made up to teach with, not real measurements):

• A is 200 ms ahead and B is 100 ms behind. The skew is 200 - (-100) = 300 ms.
• A busy group chat gets 8 messages per second.
• An update on one row takes 2 ms (lesson 22).

Step 1: timestamps. At real time T, Asha's question goes through A. It gets the time T + 200 ms. At real time T + 150 ms, Ravi's reply goes through B. It gets the time T + 150 - 100 = T + 50 ms. The reply has the smaller timestamp, so sorting by time shows the reply first. This answers the predict box.

The real gap was 150 ms, which is less than the skew of 300 ms. In this group the average gap between messages is 1,000 / 8 = 125 ms, which is also less than 300 ms. So many neighbouring messages that go through different servers can swap places.

Step 2: a sequence number for each conversation. The conversation 77 has last_seq = 40. Asha's question gets 41 and Ravi's reply gets 42, whichever server took them. One row takes 1,000 ms / 2 ms = 500 messages per second. The busy group needs 8, which is 8 / 500 = 1.6% of that. A group with 2,000 messages per second would need 4 times the limit, so one counter would not be enough.

Step 3: a Lamport clock. All counters start at 0.

1. A saves the question and sends it to B: A's counter becomes 1. The message carries 1.
2. B receives it: max(0, 1) + 1 = 2.
3. B saves the reply and sends it to A: B's counter becomes 3.
4. A receives it: max(1, 3) + 1 = 4.
5. C does an event of its own and sends nothing: C's counter becomes 1.

Sort by counter. If two counters are equal, put the lower server name first. The order is: question (1, A), C's event (1, C), receive (2, B), reply (3, B), receive (4, A). The question is before the reply. But C's event has no link to the question. It is placed there only because its counter is small. The Lamport clock cannot tell us this.

Step 4: a vector clock with the order [A, B, C].

• Question on A: [1, 0, 0].
• B receives it: the larger values are [1, 0, 0], then add 1 to B's entry: [1, 1, 0]. The reply: [1, 2, 0].
• C's event: [0, 0, 1].

Question [1, 0, 0] against reply [1, 2, 0]: every entry is smaller or equal, and one is smaller. The question happened before the reply. Question [1, 0, 0] against C's event [0, 0, 1]: the first entry is larger, the third is smaller. Neither is below the other, so they are concurrent. The cost: with 1,000 servers a list of 8-byte numbers is 1,000 x 8 = 8,000 bytes, against 8 bytes for a Lamport counter.

• Timestamps solve a time that people can read, with no extra work. They cost the wrong order when the real gap is smaller than the skew (150 ms against 300 ms). I would use them for display, and for events that are seconds apart.
• A sequence number for each key solves an exact order inside one conversation. It costs one place that hands out the numbers (500 per second for one row) and no order between keys. I would change to another way when one key needs more than that rate.
• A Lamport clock solves an order that respects cause and effect, with no trust in clocks. It costs a counter in every message, and it cannot show concurrency. I would use a vector clock when I must know whether two events are concurrent. Its cost is a list that grows with the number of servers.
• A time service solves part of the problem. It costs care: watch it, and alert on drift. A small skew remains.

"NTP keeps all the clocks the same, so timestamps give the order." NTP always leaves some error, from a few hundred microseconds to tens of milliseconds. Two messages 150 ms apart can still swap.

"A Snowflake ID or ULID gives the exact order of events." Their time comes from the clock of the server that made them. In the example, the question's ID (made on A) is larger than the reply's ID (made on B 150 ms after it). Lesson 23 says "roughly in order".

"A smaller Lamport counter means the event happened first." It does not. It only means that the event is not after the other one. In Step 3, C's event has counter 1 and the reply has counter 3, yet C's event did not happen before the reply. It had nothing to do with it.

1. What is clock skew? Which clock do you use to measure how long a call took, and why?
2. Server A is 120 ms ahead and server B is 80 ms behind. A question goes through A. A reply goes through B 150 ms after it. (a) What is the skew? (b) Is the order wrong if you sort by timestamp? (c) A Lamport clock on A has counter 6 when it sends a message to B. B's counter is 2. What is B's counter after receiving?
3. Login tokens last 15 minutes. One API server has a clock that is 20 minutes ahead. What do users see, and what do you do?