IDs, clocks & consensus

Some problems are easy on one machine and genuinely hard across several: handing out unique IDs, deciding which event happened first, and making sure exactly one node does a job. Each looks like it needs a single authority, and a single authority is a single point of failure. This lesson covers the standard answers — ID schemes, logical clocks, leases with fencing tokens, and consensus — and, just as important, which of them you should build yourself (IDs) and which you should rent (consensus).

#Unique IDs

A single database sequence (bigserial) is simple and perfectly fine until IDs must be generated on many machines, offline, or before the row reaches the database. Then you need a scheme where nodes don't have to talk to each other. See unique ID generation.

Index locality matters. A B-tree index on random UUIDv4 keys inserts each new row on a random page, so the whole index must stay in memory and pages split constantly. Time-ordered IDs (UUIDv7, Snowflake) append to the right edge of the index like a sequence does. For new systems, UUIDv7 is the easiest good default: no coordination, sortable, and supported by most languages and databases.

Snowflake, from Twitter, packs a 64-bit integer:

| 1 bit unused | 41 bits: ms since a custom epoch | 10 bits: worker ID | 12 bits: sequence |
  41 bits of milliseconds ≈ 69 years · 1,024 workers · 4,096 IDs per millisecond per worker

const (
	workerBits = 10
	seqBits    = 12
	maxSeq     = 1<<seqBits - 1
)

var epoch = time.Date(2024, 1, 1, 0, 0, 0, 0, time.UTC)

type Snowflake struct {
	mu       sync.Mutex
	workerID int64 // 0–1023, unique per running process
	lastMs   int64
	seq      int64
}

func (s *Snowflake) Next() (int64, error) {
	s.mu.Lock()
	defer s.mu.Unlock()
	now := time.Since(epoch).Milliseconds()
	switch {
	case now < s.lastMs:
		// The clock went backwards (an NTP step). Never reuse old timestamps.
		return 0, fmt.Errorf("clock moved back %d ms", s.lastMs-now)
	case now == s.lastMs:
		s.seq = (s.seq + 1) & maxSeq
		if s.seq == 0 { // 4,096 IDs this millisecond: wait for the next one
			for now <= s.lastMs {
				now = time.Since(epoch).Milliseconds()
			}
		}
	default:
		s.seq = 0
	}
	s.lastMs = now
	return now<<(workerBits+seqBits) | s.workerID<<seqBits | s.seq, nil
}

The hard part isn't the bit packing; it's guaranteeing no two running processes share a worker ID, for example by leasing IDs from a coordination service or deriving them from a StatefulSet ordinal.

Note also what time-ordered IDs don't promise: that ID order is event order. Two machines' clocks differ by milliseconds, so an ID generated "later" on one machine can be smaller than one generated earlier on another.

#Clocks and ordering

Every machine has two clocks, and mixing them up causes real bugs. See clocks and ordering.

• The wall clock (time.Now() as a date) is synchronised by NTP, usually to within a few milliseconds, but it can jump forwards or backwards when NTP corrects it, and it drifts between corrections.
• The monotonic clock only moves forward and is meaningless across machines. Use it for durations and timeouts. (Go's time.Now() carries both, and time.Since uses the monotonic part.)

So you can't reliably order events from different machines by wall-clock timestamp. "Last write wins by timestamp" can silently keep the older write if its machine's clock ran fast.

Lamport clocks give an order that's consistent with causality without trusting time. Each node keeps a counter: increment it for each local event; attach it to every message; on receiving a message, set your counter to max(local, received) + 1. If event A could have caused B, A's counter is smaller. Ties are broken by node ID, giving every event a total order everyone agrees on.

Lamport clocks can't tell you whether two events were concurrent (neither could have caused the other). Vector clocks can — each node keeps a counter per node — which is how some databases detect conflicting writes. Hybrid logical clocks (used by CockroachDB and others) combine a physical timestamp with a logical counter, so values stay close to real time while still respecting causality. Google Spanner goes further, using GPS and atomic clocks with a known error bound and waiting out that uncertainty before committing.

#Leader election

Many designs need exactly one node to do something: run the scheduler, own a partition, accept writes for a shard. Electing that leader is easy when nothing goes wrong; the difficulty is the moment when two nodes both believe they're it. See leader election.

The standard building block is a lease: a lock with an expiry. A node acquires the lease from a strongly consistent store, does its work while renewing it periodically, and if it stops renewing — because it crashed or got cut off — the lease expires and another node takes over.

In Kubernetes you get this from Lease objects (client-go's leaderelection package); with etcd, from its election API built on leases. Both rely on a store that is itself consensus-backed, which matters for the next section.

#The paused leader and fencing tokens

Leases have a subtle failure. A node holds the lease, then pauses — a long garbage-collection pause, a VM migration, a swapped-out process — for longer than the lease duration. Another node acquires the lease and starts working. The first node wakes up, still believing it holds the lease, and writes. Now two "leaders" write to the same storage. Checking the lease before each write doesn't help: the pause can happen between the check and the write.

The fix is a fencing token: a number that increases every time the lease changes hands. The holder sends its token with every write, and the storage rejects writes carrying a token lower than the highest it has seen. See leases and fencing tokens.

etcd exposes this as each key's revision number; ZooKeeper as zxid or znode versions. With a SQL database as the storage, the check is a conditional update: UPDATE jobs SET … , fence = $token WHERE id = $id AND fence < $token. Locks built only on Redis (such as the Redlock algorithm) provide no fencing token, so use them only where an occasional double execution is harmless.

#Consensus: agreeing on one log

Underneath every safe lease, election and configuration store is a consensus algorithm: a way for a group of nodes to agree on a sequence of values even when some nodes crash or messages are delayed. Raft (etcd, Consul, CockroachDB, TiKV), Paxos (Spanner, Google's Chubby) and ZooKeeper's closely related Zab are the standard ones. See consensus and Raft.

Raft, in outline:

1. Nodes elect a leader for a numbered term. A candidate needs votes from a majority.
2. Clients send writes to the leader, which appends them to its log and replicates them to followers.
3. An entry is committed once a majority has stored it. Committed entries are never lost, because any future leader must win a majority vote, and any majority overlaps the majority that stored the entry.
4. If the leader fails, followers time out, start a new term and elect a new leader — whose log is guaranteed to contain every committed entry.

The majority rule sets the numbers. A cluster of 2f + 1 nodes tolerates f failures: 3 nodes survive 1 failure, 5 survive 2. Four nodes tolerate only one failure, the same as three, while making every write wait for one more acknowledgement — so clusters have odd sizes. And because each write needs a majority round trip, consensus stores handle thousands of writes per second, not millions; spreading a cluster across regions adds the inter-region round trip to every write.

#Gossip: when you don't need agreement

Not everything needs consensus. Cluster membership ("which nodes are alive?") in a large cluster often uses a gossip protocol: every second, each node exchanges what it knows with a few random peers, and information spreads through the cluster in a number of rounds proportional to the logarithm of its size, like a rumour. Cassandra, Consul's member list and many service meshes use gossip for membership and failure detection. It's cheap, scales to thousands of nodes and tolerates failures well — and its information is eventually consistent, which is fine for "who's alive" but not for "who's the leader". See gossip protocols.

#Practice

Six replicas of a billing service each run a scheduler that should, once per hour, generate invoices for customers whose billing period ended. Today every replica runs the job, so customers get six invoices. Design a fix so the job runs once per hour even when replicas crash, are paused, or are partitioned. Explain how you prevent duplicate invoices if two replicas briefly both believe they're the leader.

#Key takeaways

• For IDs without coordination, prefer time-ordered schemes (UUIDv7, Snowflake) for index locality; Snowflake needs unique worker IDs.
• Wall clocks jump and drift: use monotonic time for durations, and never order cross-machine events by timestamp alone.
• Lamport clocks give an order consistent with causality; vector clocks also detect concurrency.
• Leases elect a single leader, but a paused node can outlive its lease; fencing tokens checked by storage make its writes harmless.
• Consensus (Raft, Paxos) commits entries on a majority of 2f + 1 nodes. Rent it from etcd, ZooKeeper or Consul, and keep only small critical data there.
• Gossip spreads eventually consistent membership cheaply; it's not a substitute for consensus.