# IDs, clocks & consensus

> Generate unique IDs without a single counter, order events without trusting wall clocks, elect one leader safely with leases and fencing tokens, and know what consensus systems like etcd give you.

System Design roadmap · Communication & reliability · 21 min read · https://levelcode.org/roadmaps/system-design/coordination

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](https://levelcode.org/concepts/unique-ids).

| Scheme | Size | Sortable by time | Coordination | Notes |
|---|---|---|---|---|
| Database sequence | 64 bits | Yes | The database | Leaks volume ("order 1043"); one writer |
| UUIDv4 | 128 bits | No | None | Random, so inserts scatter across a B-tree index |
| UUIDv7 | 128 bits | Yes (ms) | None | Timestamp prefix + randomness; standardised in RFC 9562 |
| Snowflake-style | 64 bits | Yes (ms) | A unique worker ID per node | Compact, fast, needs worker IDs assigned |
| Ticket server / ID ranges | 64 bits | Roughly | Occasional fetch of a block | Each node reserves 1,000 IDs at a time |

**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:

```text
| 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
```

```go
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](https://levelcode.org/concepts/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](https://levelcode.org/concepts/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](https://levelcode.org/concepts/leases-and-fencing-tokens).

```sequence
title: A fencing token stops a paused leader
participants: Node A, Lock service, Node B, Storage
Lock service --> Node A: lease granted, token 33
Node A -> Node A: long GC pause
> A's lease expires while it's paused.
Lock service --> Node B: lease granted, token 34
Node B -> Storage: write (token 34)
Storage --> Node B: OK, highest token = 34
Node A -> Storage: write (token 33)
Storage --> Node A: rejected: token 33 < 34
```

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](https://levelcode.org/concepts/consensus-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.

> [!IMPORTANT]
> Don't implement consensus yourself. Correct implementations took years of testing to get right. Use etcd, ZooKeeper or Consul — or a database built on Raft — for **small, critical, strongly consistent** data: leader leases, configuration, service discovery, shard maps. Never use them as a general-purpose database.

## 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](https://levelcode.org/concepts/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.

**Solution**

**Elect a leader with a lease.** Each replica tries to acquire a lease named `billing-scheduler` from a consensus-backed store — a Kubernetes `Lease` via client-go's leader election, or an etcd election — with a 15-second lease renewed every 5 seconds. Only the holder runs the hourly schedule. If it crashes or loses contact, the lease expires and another replica takes over within about 15 seconds.

**Fence the work.** A lease alone can't stop a paused ex-leader from waking up and generating invoices. Use the lease's fencing token (the etcd revision, or a counter incremented on every acquisition) and make the database enforce it. Record each run in a `billing_runs(period, fence)` table, and claim a run with `INSERT INTO billing_runs (period, fence) VALUES ($1, $2) ON CONFLICT (period) DO UPDATE SET fence = EXCLUDED.fence WHERE billing_runs.fence < EXCLUDED.fence` — a stale leader's lower token claims nothing. Check the token again in the transaction that writes each batch of invoices (`SELECT fence FROM billing_runs WHERE period = $1 FOR UPDATE` must still equal your token), so a leader that lost its lease halfway through a run stops writing.

**Make the work itself idempotent.** Even with fencing, design invoice generation so a repeat is harmless: a unique constraint on `(customer_id, billing_period)` in the invoices table, so a second attempt to create the same invoice fails and is skipped. This also covers the case where the leader crashes halfway through a run and the next leader starts again.

**Result:** the lease makes it rare for two replicas to run the job; fencing makes a stale leader's writes ineffective; and the unique constraint guarantees exactly one invoice per customer per period no matter what.

## 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.

## Quiz

1. Why do time-ordered IDs such as UUIDv7 usually insert faster into a B-tree primary key than random UUIDv4?

   A. They are shorter
   B. New values land at the right edge of the index instead of on random pages, so fewer pages must be read, split and cached
   C. B-trees can't store random values
   D. They don't need an index at all

   **Answer: B.** Random keys scatter inserts across the whole index, forcing it to stay in memory and causing page splits everywhere. Monotonic keys behave like a sequence and touch only the most recent pages.

2. A node holding a 10-second lease pauses for 20 seconds during garbage collection, then writes. What prevents this write from corrupting data?

   A. Checking the lease immediately before the write
   B. A fencing token: storage rejects writes carrying a token lower than one it has already seen
   C. Using a longer lease of 30 seconds
   D. NTP clock synchronisation

   **Answer: B.** The pause can occur between any check and the write, and any lease length can be exceeded by a long enough pause. A monotonically increasing token checked by the storage is what makes the stale holder's write fail.

3. How many node failures can a 5-node Raft cluster tolerate while still committing writes?

   A. 1
   B. 2
   C. 3
   D. 4

   **Answer: B.** Commits need a majority: 3 of 5. With 2 nodes down, 3 remain and can still form a majority. A 4-node cluster also tolerates only 1 failure, which is why clusters have odd sizes.

4. Two servers record events with wall-clock timestamps. Why can't you trust timestamp order across them?

   A. Timestamps are stored in different time zones
   B. Wall clocks on different machines differ and can jump when NTP corrects them, so a later event can carry an earlier timestamp
   C. Timestamps only have second precision
   D. Databases reorder rows by timestamp automatically

   **Answer: B.** Clock skew of a few milliseconds — or a step correction — is enough to invert the order of close events. Logical clocks, or a single sequencer, give an order you can rely on.