Ordering and Causality

How distributed systems decide what happened before what: the happens-before relation, Lamport and vector clocks, causal consistency, and total order broadcast.

Overview

Many bugs in distributed systems are ordering bugs: a reply shown before its question, an update applied before the record exists, two nodes that apply the same writes in different orders and end up with different data. This chapter explains which orders matter and the tools that produce them.

Why order matters: cause and effect

Some events depend on others. A reply depends on the question it answers; an update depends on the row it changes. If a replica applies the effect before the cause, users see something impossible.

Many other events are independent of each other. If Alice and Bob each post in unrelated threads at about the same time, it does not matter which one a replica shows first. Such events are concurrent: neither could have known about the other. Concurrent does not mean simultaneous; it only means no information flowed between them.

The happens-before relation

Leslie Lamport defined the happens-before relation in his 1978 paper 'Time, Clocks, and the Ordering of Events in a Distributed System'. Event a happens before event b if b could have been influenced by a.

Same process — a comes before b in one process's own sequence
Message — a sends a message and b receives it
Transitive — a happens before c and c happens before b
Otherwise — a and b are concurrent

This gives a partial order: some pairs are ordered, and concurrent pairs are not. A consistency model that respects it is causal consistency.

Lamport timestamps

A Lamport timestamp is a counter on every node. The rules in Lamport's paper amount to this: add one before each local event or send; put the counter on every message; on receive, set the counter above both the local value and the received value. Ties are broken by node ID, so every event gets a unique pair.

The guarantee runs one way only. If a happens before b, a's timestamp is smaller. But a smaller timestamp does not prove a happened before b: the two may be concurrent. The total order Lamport timestamps give is consistent with cause and effect, but it is decided only after the fact.

Order every event, consistent with happens-before — Tell whether two events were concurrent
Do it with one integer per node and message — Let a node decide now that it is first, such as 'this username is mine', because a smaller stamp may still arrive

Vector clocks

To detect concurrency, a vector clock keeps one counter per node. Each node increases its own entry on each event and, on receive, takes the element-wise maximum. Colin Fidge and Friedemann Mattern described the idea independently in 1988. Compare two vectors entry by entry: if one is less than or equal everywhere, it happened before the other; if each is bigger somewhere, they are concurrent.

The cost is size: one entry per node that has written, carried on every value or message. Dynamo-style databases use a related structure, the version vector, to keep both of two concurrent writes instead of dropping one.

Causal consistency

Causal consistency means every process sees causally related operations in the same order; concurrent operations may appear in different orders on different nodes. Jepsen notes an important property: it can stay available during a network partition, as long as each client keeps talking to the same server. The stronger models cannot.

Eventual consistency — Nothing, until replicas converge — Yes
Causal consistency — Cause before effect — Yes, if clients stick to one server
Linearizability — Everything, in real time — No

For many apps, causal order is exactly what users notice: replies after questions, comments after posts, permissions changed before the new content is shared. It costs less than linearizability because concurrent writes need no coordination.

Total order broadcast

Sometimes every node must apply every operation in the same order, concurrent or not. A replicated database needs this so replicas end up identical. The tool is total order broadcast, also called atomic broadcast: every message reaches every node, and all nodes deliver messages in the same order.

ZooKeeper's Zab protocol promises that if one server delivers message a before b, all servers do; the leader commits a proposal once a quorum has acknowledged it, and zxids give every change a place in one order. Raft does the same with a replicated log: no two servers ever apply different commands at the same log position.

Total order broadcast is equivalent to consensus: Chandra and Toueg showed in 1996 that, in an asynchronous system where nodes can crash, each can be built from the other. You can also build linearizable operations on it, as long as reads go through the log too. To claim a username, append 'claim alice by node 7' to the log, then read the log up to your own entry. If the first claim for 'alice' is yours, you have it; every node agrees, because every node sees the same order. That is exactly the decision Lamport timestamps could not make.

Ordering in practice

One database leader — Total order of all writes — One node's throughput
Kafka partition — Total order within the partition; same key, same partition — No order across partitions
Raft or Zab log — Total order, agreed by a majority — Every write waits for a majority
Vector clocks — Causal order; flags concurrent writes — Grows with the number of writers
Lamport timestamps — A total order consistent with causality — Known only after the fact

Kafka's documentation says events with the same key go to the same partition, and a consumer reads a partition in the order it was written. So partitioning by an entity ID, such as an order ID, keeps each entity's events in order while letting different entities scale out.

What you will be able to do

Define happens-before and concurrency, and spot an ordering anomaly.
Run Lamport and vector clocks by hand and say what each can and cannot tell you.
Explain why causal consistency survives partitions and linearizability does not.
Explain total order broadcast and how it gives uniqueness and replicated state.

Key concepts

Happens-before: Event a happens before b if b could have been influenced by a: same process in order, a message from a to b, or a chain of these.
Concurrent events: Two events where neither happens before the other. No information flowed between them; it says nothing about wall-clock time.
Lamport timestamp: A per-node counter carried on messages. If a happens before b, a has the smaller stamp; the reverse does not hold.
Vector clock: One counter per node. Comparing two vectors tells you whether events are ordered or concurrent.
Causal consistency: Everyone sees causally related operations in the same order; concurrent ones may differ. Can stay available during a partition.
Total order broadcast: Every message reaches every node, and all nodes deliver messages in the same order. Equivalent to consensus.
Replicated log: The ordered list of commands that Raft or Zab agrees on; applying it in order keeps replicas identical.

When to use it

Designing comment threads, chat or feeds where replies must follow their parents
Keeping replicas identical by applying writes in one agreed order
Choosing a Kafka partition key so events for one entity stay in order
Detecting concurrent writes instead of silently dropping one

Interview questions

What is the difference between Lamport timestamps and vector clocks?
Why can causal consistency stay available when linearizability cannot?
What is total order broadcast, and why is it equivalent to consensus?
How do you keep events for one order in sequence in Kafka?
How would you enforce unique usernames with total order broadcast?