coordination-store

How it is built

Architecture overview

A coordination store is a small, strongly consistent key-value database that a fleet of other services uses to agree on facts: who is the leader, which nodes are alive, what the current configuration is, who holds a lock. It holds little data (metadata, measured in megabytes to a few gigabytes), but every read and write has to be right, because the services above it make decisions from the answer. The one idea that makes it work is a replicated log under a state machine: a small odd number of servers (three or five) run a consensus protocol (Raft in etcd and Consul, Zab in ZooKeeper, Paxos in Chubby) that puts every write into one agreed order, and each server applies that order to the same in-memory and on-disk key space. On top sits what makes it a coordination primitive rather than just a database: versioned keys, a watch that streams changes, and leases (TTL-bound ownership) so that dead clients lose their locks and ephemeral registrations automatically.

Clients do not use the store as a general database. They use it to build locks, leader election, barriers, service registries and configuration distribution, and Kubernetes uses it as the backing store for all cluster state (source: Kubernetes docs, etcd operations).

Parts:

• Consensus — orders all writes across the replicas, elects a leader — Raft, Multi-Paxos, Exponential backoff with jitter for election timeouts
• Log and storage — durable log of commands plus the key space — Write-ahead log, Group commit, fsync and direct I/O, B+ tree, CRC32C checksums
• Versioned key space — every write gets a revision, old versions are readable until compacted — MVCC, Optimistic concurrency control
• Snapshots and compaction — bound the log and the history — State machine snapshots, Copy-on-write fork, copy-on-write-snapshots (no page yet)
• Read path — serves reads without breaking linearizability — linearizable-reads (no page yet)
• Watch and leases — change streams and expiring ownership — Watch notifications, Message sequence numbers, Leases, Fencing tokens, grpc-protocol (no page yet)
• Failure detection — decides which members and clients are gone — Health checking, Phi accrual failure detector, SWIM gossip

 clients ──gRPC──► any member ──forward──► LEADER ──append──► WAL (fsync, batched)
   ▲  ▲                                      │  replicate entries
   │  └── watch stream (revision R+1…) ◄─┐   ├──► follower ─► WAL ─► ack
   │                                      │   └──► follower ─► WAL ─► ack
   └── reply after commit ◄── apply ◄─ majority acked
                               │
                               ▼
              state machine: key space + revisions (B+ tree) ─► snapshot + compaction
              lease table: TTL timers, expiry deletes attached keys

How the parts fit together

Consensus

Every write is a command proposed to the leader, appended to its log, copied to followers and committed once a majority has it on disk. Raft fixes the roles (leader, follower, candidate), terms, and the log-matching rule in a form built to be implementable; Multi-Paxos is the older equivalent that Chubby and Spanner are built on, with a stable leader that skips the first phase. Viewstamped Replication is a third relative (no page yet). ZooKeeper uses its own atomic broadcast protocol, Zab, with the same leader-and-majority shape (source: Hunt et al. 2010).

The cluster size is the main design choice: with n = 2f + 1 members the group survives f failures, so 3 members tolerate one and 5 tolerate two; an even size adds a failure without adding tolerance. Bigger groups make every commit wait for more acknowledgements without adding capacity: replication buys availability, not throughput. Election timeouts are randomised (Exponential backoff with jitter is the same idea) so two followers do not time out together and split the vote.

Log and storage

The commit latency is the disk's fsync latency, plus a round trip to the nearest follower. Entries are appended to a Write-ahead log and made durable with an fsync before the member acknowledges (fsync and direct I/O covers what the call really guarantees). Because that fsync dominates, concurrent proposals are batched: one fsync covers many entries (Group commit). Each log record carries a checksum (CRC32C checksums) so a torn tail after a crash is detected and cut rather than replayed.

The applied state lives in a key space. etcd keeps it in an embedded B+-tree database, bbolt, plus an in-memory index from key to revisions. A B+ tree is the right structure for a read-heavy, ordered, range-scanned key space of modest size; a write-heavy store would prefer an LSM tree, and the alternative is explicit in the graph. ZooKeeper instead keeps an in-memory image of the state, with transaction logs and snapshots on disk, which is why it values small data and fast reads (source: ZooKeeper docs, overview).

Versioned key space

MVCC is what lets a coordination store offer more than "latest value". Every write gets a global, monotonically increasing revision, and a key remembers the revisions at which it changed. That gives you three things: a consistent snapshot at one revision for a multi-key read, compare-and-swap on a key's version (Optimistic concurrency control: read, then write "only if the version is still N"), and a point to resume a watch from. etcd exposes this as transactions with compare, then, else branches (source: etcd docs, API guarantees). The cost is that history grows until it is compacted, and etcd's database does not shrink until it is defragmented (source: etcd docs, maintenance).

Snapshots and compaction

An unbounded log cannot be replayed on restart or sent to a lagging follower. State machine snapshots save the key space as of log index i so the log prefix can be deleted; a new or far-behind follower loads the snapshot, then replays the suffix. The snapshot must be taken without freezing writes: either copy-on-write pages in the storage engine (copy-on-write-snapshots, no page yet) or a process fork that shares memory pages with the parent until they change (Copy-on-write fork), the way some in-memory stores snapshot. Log compaction and MVCC history compaction are two separate things and both must run.

Read path

By default a read must be linearizable: it must see every write that finished before it started. The naive way sends reads through the log like writes, which is correct but slow. The faster way, linearizable-reads (no page yet), has the leader confirm it is still the leader (a quorum round trip) or hold a time-bounded leader lease, then answer from its applied state, with no log write. etcd also offers a "serializable" read that any member answers from local state, fast but possibly stale (source: etcd docs, API guarantees). ZooKeeper made the opposite default: reads are served by the member the client is connected to, which may lag, and a sync call forces catch-up (source: ZooKeeper docs, programmer's guide). Choose per call: leader election and locking need the linearizable read; a dashboard does not.

Watch and leases

A watch is how clients avoid polling. The client reads at revision R, then asks to watch from R + 1, and receives an ordered stream of changes with no gap and no duplicate, including a resume point after a reconnect (Message sequence numbers is the general mechanism). etcd guarantees that a watch never drops events within the available history window, and that all changes from one operation arrive in one response (source: etcd docs, API guarantees). ZooKeeper's watches are one-time triggers and the client must re-read and re-set the watch, so it can miss intermediate changes (source: ZooKeeper docs, programmer's guide). The streams run over a multiplexed RPC channel, grpc-protocol (no page yet) in etcd.

A lease is a lock that expires on its own: the client creates a lease with a TTL, attaches keys to it, and refreshes it with keep-alives; if the client dies, the lease expires and the keys vanish. ZooKeeper reaches the same effect with sessions and ephemeral nodes. This is what makes service registration and leader election self-cleaning. Expiry is based on time, so a client that merely pauses (a long garbage-collection stop, a frozen VM) can believe it still holds a lock the store has already given away. The cure is a fencing token: each lock grant carries a number (the key's revision works) that the protected resource checks, rejecting any write with an older token than it has seen.

Failure detection

Two kinds of liveness are tracked. Client liveness is lease or session expiry: simple, fixed timeout. Member liveness inside the consensus group is heartbeats from the leader, and the missed-heartbeat timeout triggers an election. Fixed timeouts are brittle under variable latency; an adaptive detector such as the Phi accrual failure detector scales suspicion to the observed heartbeat distribution, and gossip (SWIM gossip) spreads membership without a central list, which is how Consul tracks its wider fleet beside its Raft servers. Client-side health checking with hysteresis keeps a registry from flapping.

Data and control flow

A write (for example, put key value):

1. The client sends the request to any member; a follower forwards it to the leader.
2. The leader appends it to its log, batches it with other pending entries, and sends the batch to followers in parallel.
3. Each member writes the entries to its WAL and fsyncs; this is where the time goes. Followers acknowledge.
4. When a majority has the entry, the leader marks it committed and applies it: new revision, update the key space, trigger the watchers of that key.
5. The leader replies to the client; followers apply the same entry when they learn it is committed.

Leader election for an application (lock on a key):

1. Each candidate creates a lease and writes a key such as /election/<lease-id> attached to it, in a transaction that records the key's creation revision.
2. The candidate with the lowest creation revision is the leader. Everyone else watches the key just before theirs (the predecessor only), not the whole prefix, to avoid a thundering herd on every release.
3. The leader keeps its lease alive. If it dies or is partitioned, the lease expires, its key is deleted, and the next candidate's watch fires.
4. The new leader uses its revision as a fencing token on every write to shared resources.

Watch after a disconnect:

1. The client remembers the revision of the last event it processed.
2. It reconnects (to any member, with backoff and jitter so clients do not all come back at the same moment) and asks to watch from that revision plus one.
3. If the revision is still in the history, the member replays the missed events in order. If it has been compacted, the client gets an error and must list the whole prefix again, then start a new watch.

Scaling

What limits a coordination store, in the order you hit it:

1. Write latency is fsync plus one round trip to the nearest majority. Levers: fast, low-latency local SSDs for the WAL, members in one region or nearby zones, group commit; never spread a group over distant regions unless you accept that latency on every write.
2. Write throughput is bound by the leader: one node orders everything. Levers: batch client operations in transactions, reduce write churn (lease keep-alives and frequently updated keys are the usual culprits), and shard by running separate clusters per concern. Adding members does not raise write throughput.
3. Read throughput can scale: serializable reads from followers, or observer members in ZooKeeper, or caching in clients that watch. The price is staleness, which you control per call.
4. Data size: the store is designed for small metadata. etcd has a default storage quota of 2 GiB and suggests 8 GiB as a normal maximum, and a default request size limit of 1.5 MiB (source: etcd docs, system limits). Levers: compact and defragment, store pointers instead of blobs, keep large objects elsewhere.
5. Watchers and connections: each watch costs memory and each event fans out to all watchers. Levers: watch narrow prefixes, share one watch in a client-side cache (the pattern behind informer caches), put a proxy in front.

Failure modes

Real implementations

Choice: pick etcd when you want a linearizable key-value API with revisions, watch-from-revision and leases (typical for Kubernetes-style control planes); ZooKeeper if you already run the Hadoop or Kafka-era stack that expects it; Consul when service discovery with health checks and multi-datacenter features is the main job.

Sources

• D. Ongaro and J. Ousterhout, In Search of an Understandable Consensus Algorithm (Raft), USENIX ATC 2014. paper
• P. Hunt et al., ZooKeeper: Wait-free Coordination for Internet-scale Systems, USENIX ATC 2010. paper
• M. Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI 2006. page
• etcd docs: API guarantees (linearizability, watch guarantees), system limits, maintenance (compaction, defragmentation, space quota alarm).
• Apache ZooKeeper docs: overview, programmer's guide (watches).
• Kubernetes docs: operating etcd clusters.
• Licence texts and descriptions read through the GitHub API.