# System Design: [Coordination service name]

> Reference design for a distributed lock and coordination service: a small,
> strongly consistent, replicated store that other systems use for leader
> election, locks with leases, fencing tokens, configuration, membership and
> change notification. It covers consensus with Raft (or Multi-Paxos),
> sessions and keep-alives, failover grace periods, watches, read scalability
> and the ways teams misuse such a service. Concepts draw on the Chubby lock
> service (Burrows, OSDI 2006), the Raft paper (Ongaro and Ousterhout, USENIX
> ATC 2014), ZooKeeper (Hunt et al., USENIX ATC 2010) and the etcd v3.6 API
> documentation; the text and the worked design are original. It follows the
> structure of the System Design Document template. Replace every
> `[bracketed]` value and every row marked *Example*.

<!--
Guidance: How to use this template
- Be explicit that this service is for coordination, not for data: small
  values, low write rates, many readers. Write the usage policy (7.5) before
  onboarding the first team.
- Decide what a lock protects and how the protected resource checks fencing
  tokens (7.3). A lock without fencing is advisory at best.
- Size sessions and watches, not bytes; keep-alives and notification fan-out
  are what overload coordination services (section 3).
- Rehearse leader failover with real clients and measure whether any session
  expired.
-->

## Document control

<!-- Guidance: A design is a proposal until it is approved; record who decided and when. -->

| Field | Value |
|---|---|
| Document ID | [SDD-COORD-001] |
| System / feature | [Coordination service for leader election, locks and configuration] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner | [@owner] |
| Author(s) | [@author] |
| Reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal; tier-0 dependency] |
| Consistency model | [*Example:* Linearizable writes and reads by default; serializable reads opt-in] |
| Related | Distributed Key-Value Store System Design (`system-design/design-distributed-kv-store`), Job Scheduler System Design (`system-design/design-job-scheduler`), Message Queue System Design (`system-design/design-message-queue`) |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Tech lead | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Staff / principal engineer | [@name] | [Decision] | YYYY-MM-DD |
| SRE / operations | [@name] | [Decision] | YYYY-MM-DD |
| Security | [@name] | [Decision] | YYYY-MM-DD |
| Platform consumers' representative | [@name] | [Decision] | YYYY-MM-DD |

## Revision history

<!-- Guidance: Note what changed in the design, not the wording. -->

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft for design review |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Added fencing tokens after a split-brain write in the scheduler |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* Added proxy tier to absorb keep-alives and watch fan-out |
| 1.0 | YYYY-MM-DD | [@name] | *Example:* Approved |

## Contents

<!-- Guidance: Keep aligned with the headings. -->

1. [Overview](#1-overview)
2. [Requirements](#2-requirements)
3. [Capacity estimation](#3-capacity-estimation)
4. [API design](#4-api-design)
5. [Data model](#5-data-model)
6. [High-level design](#6-high-level-design)
7. [Detailed design](#7-detailed-design)
8. [Scalability and performance](#8-scalability-and-performance)
9. [Reliability, security and operations](#9-reliability-security-and-operations)
10. [Trade-offs and alternatives](#10-trade-offs-and-alternatives)
11. [Delivery plan and risks](#11-delivery-plan-and-risks)
12. [Appendices](#12-appendices)

## 1. Overview

<!-- Guidance: One page that a busy reviewer can read alone: problem, proposed solution in a paragraph, and the decisions that need their attention. -->

### 1.1 Problem statement

[*Example:* Teams implement leader election with database row locks,
cache-based locks with TTLs, and hand-written heartbeats. Last quarter two
scheduler instances both believed they were leader after a long garbage
collection pause and ran the same billing job twice. Configuration is pushed
by redeploying, and service discovery lags by minutes.]

### 1.2 Proposed solution

[*Example:* A coordination service runs as cells of five replicas across
three zones, replicated with Raft. It exposes a small hierarchical key-value
store with revisions, sessions held alive by keep-alives, locks and
elections built on sessions, and watches that stream changes from a given
revision. Every lock acquisition returns a fencing token (the lock key's
revision) that protected resources must check. A stateless proxy tier
absorbs keep-alives and fans out watch notifications. Values are capped at
*Example* 64 KB and the service is explicitly not a general data store.]

### 1.3 Decisions requested from reviewers

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Which consensus protocol? | Raft, using a mature open-source implementation | 7.1 |
| Q-02 | *Example:* How are reads made linearizable without a log write? | Leader confirms leadership with a quorum before serving (read index) | 7.1 |
| Q-03 | *Example:* What protects resources from a stale lock holder? | Fencing tokens checked by the resource | 7.3 |
| Q-04 | *Example:* Session TTL and keep-alive interval? | 30 s TTL, keep-alive every 10 s, grace period across leader failover | 7.2 |
| Q-05 | *Example:* Cell size? | 5 voting replicas in 3 zones | 3.6, 9.1 |
| [Q-nn] | [Question] | [Option] | [Section] |

### 1.4 45-minute interview path

<!-- Guidance: Use this order when presenting the design in an interview or a short review; the same document then serves both. -->

| Minutes | Cover | Output on the whiteboard |
|---|---|---|
| 0 to 5 | What clients need: leader election, locks, config, discovery; consistency expectation | Core requirements FR-01 to FR-06 |
| 5 to 10 | Sessions, keep-alives, writes, reads, watches | Keep-alives dominate; one leader takes all writes |
| 10 to 18 | Cell, proxies, clients diagram | Section 6 diagram |
| 18 to 33 | Deep dive: consensus and linearizable reads (7.1) and locks with fencing tokens (7.3); if the interviewer asks about scale, use watches and read scaling (7.4) | Raft roles, fencing sequence |
| 33 to 40 | Session failover and misuse pitfalls | Grace period, usage policy |
| 40 to 45 | Trade-offs and 10x | Table in section 10 |

## 2. Requirements

<!-- Guidance: Split core requirements from below-the-line items. State the consistency guarantee per operation, not just for the service. -->

### 2.1 Core functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* Store small keys and values with a global revision on every change | Must |
| FR-02 | *Example:* Atomic compare-and-set transactions on one or more keys | Must |
| FR-03 | *Example:* Sessions with TTL kept alive by clients; ephemeral keys deleted when the session ends | Must |
| FR-04 | *Example:* Exclusive locks and leader election returning a fencing token | Must |
| FR-05 | *Example:* Watches on a key or prefix from a given revision, with no missed events | Must |
| FR-06 | *Example:* Linearizable reads by default | Must |
| FR-07 | *Example:* Shared (reader) locks | Should |
| FR-08 | *Example:* Serializable (possibly stale) reads for discovery and config | Should |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Availability | *Example:* 99.99% per cell; tolerate loss of one zone | Synthetic lock acquire every 10 s |
| NFR-02 | Write latency | *Example:* p99 below 25 ms within a region | Server and client histograms |
| NFR-03 | Failover | *Example:* New leader within 5 s; no healthy client session expires during failover | Failover drill |
| NFR-04 | Safety | *Example:* Never two holders of an exclusive lock whose fencing tokens are both accepted by the resource | Fault-injection tests with partitions and process pauses |
| NFR-05 | Watch delivery | *Example:* p99 below 1 s from commit to notification for 100 000 watchers | Probe keys |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 2.3 Below the line (out of scope)

- [*Example:* Storing application data, queues or large blobs (see `system-design/design-distributed-kv-store` and `system-design/design-message-queue`)]
- [*Example:* Fine-grained locks held for milliseconds per request]
- [*Example:* Cross-region linearizability within one cell; each region runs its own cell, with one global cell for rare global decisions]
- [*Example:* Rate limiting and counters at request rates]
- [Item deferred, with the release that will take it]

## 3. Capacity estimation

<!-- Guidance: Show inputs, formulas and results, and end every estimate with the design consequence it forces. -->

### 3.1 Assumptions

| Input | Symbol | Value | Source |
|---|---|---|---|
| Client sessions per cell | $S$ | *Example:* 100 000 | Service instances x processes |
| Keep-alive interval | $t_k$ | *Example:* 10 s (TTL 30 s) | 7.2 |
| Writes per second (locks, elections, config, registrations) | $W$ | *Example:* 2 000 | Onboarding survey |
| Reads per second | $Q$ | *Example:* 50 000 | Onboarding survey |
| Watches per session | $w$ | *Example:* 5 | Client library defaults |
| Keys and average value size | $K$, $v$ | *Example:* 1 million, 1 KB | Onboarding survey |
| Log fsync latency on target disks | $f$ | *Example:* 2 ms | Benchmark |
| Notifications sent per second per server | $n$ | *Example:* 20 000 | Benchmark |

### 3.2 Keep-alives

$$
KA = \frac{S}{t_k} = \frac{100\,000}{10\ \text{s}} = 10\,000\ \text{keep-alives/s}
$$

Keep-alives refresh leases, and lease refreshes are handled by the leader.
Consequence: keep-alives alone are five times the write rate, so a proxy
tier terminates client sessions and refreshes them upstream in batches; the
cell sees one stream per proxy instead of one per client.

### 3.3 Writes

Every write is appended to the replicated log and fsynced by a quorum. One
fsync per write would cap throughput near $1 / f = 500$ writes/s per
replica; group commit batches entries:

$$
\text{entries per batch} = \frac{W \times f}{1} = 2\,000 \times 0.002 = 4
$$

Consequence: batching makes 2 000 writes/s easy, but all writes go through
one leader, so adding replicas does not add write capacity (it adds
latency). Write growth is handled by more cells partitioned by tenant, not
bigger cells.

### 3.4 Reads and watches

Reads at 50 000/s are 25 times the write rate. Consequence: reads must be
served by followers and proxies, using read-index confirmation for
linearizable reads and local state for serializable ones (7.1, 7.4).

Watches: $S \times w = 500\,000$ watches; at about 200 B each that is about
100 MB of memory, which is small. Fan-out is the risk: a change to a key
watched by all 100 000 sessions creates 100 000 notifications, which take
one server $100\,000 / 20\,000 = 5$ s to send. Consequence: watches register
at proxies, so the cell sends one notification per proxy and proxies fan out
in parallel; clients add jitter before re-reading so the change does not
create a read herd.

### 3.5 Data size and snapshots

$K \times v = 10^{6} \times 1$ KB $= 1$ GB, kept in memory with the log on
SSD. Consequence: cap the keyspace at *Example* 2 GB; a new or lagging replica
installs a snapshot of that size in about 20 s at 100 MB/s, which keeps
replacement of a failed replica quick. Enforce value size limits and per-tenant
quotas to hold the cap.

### 3.6 Cell size

A cell of $2F + 1$ voting replicas tolerates $F$ failures. Five replicas
across three zones (2 + 2 + 1) survive the loss of any one zone or of any two
replicas. Three voters in three zones also survive a zone loss, but only one
replica failure. Consequence: five voters, not three, so that one replica can
be down for a planned upgrade while another fails unexpectedly.

### 3.7 Summary

| Quantity | Estimate | Design consequence |
|---|---|---|
| Keep-alives | 10 000/s | Proxy tier aggregates sessions |
| Writes | 2 000/s | Group commit; scale by more cells, not bigger cells |
| Reads | 50 000/s | Follower reads with read index; proxy caches |
| Watch fan-out | 100 000 per hot key change, 5 s from one server | Proxies fan out; client jitter |
| Data | ~1 GB in memory | Keyspace cap 2 GB; value size limit |
| Cell | 5 voters in 3 zones | Survives a zone loss |

## 4. API design

<!-- Guidance: Keep the API small. Every call must state its consistency, and every lock call must return a fencing token. -->

### 4.1 Operations

| Operation | Consistency | Notes |
|---|---|---|
| `Session.Create(ttl)` | Linearizable | Returns session ID; server may adjust TTL |
| `Session.KeepAlive(id)` (stream) | Leader | Returns remaining TTL |
| `KV.Get(key, serializable = false)` | Linearizable by default | Returns value, `create_revision`, `mod_revision` |
| `KV.Range(prefix, at_revision?)` | Linearizable or at a past revision | Bounded page size |
| `KV.Txn(compares, then, else)` | Linearizable | Compares on value, version or revisions |
| `Lock.Acquire(name, session, timeout)` | Linearizable | Returns fencing token |
| `Lock.Release(name, token)` | Linearizable | Idempotent |
| `Election.Campaign(name, session, value)` | Linearizable | Blocks until leader; returns token |
| `Election.Observe(name)` (stream) | Watch semantics | Current leader and changes |
| `Watch(key or prefix, from_revision)` (stream) | Ordered, resumable | Fails with `compacted` if the revision is too old |

### 4.2 Lock acquisition as a transaction

A lock is a key created only if it does not exist, attached to the caller's
session so it disappears if the session ends:

```text
Txn(
  compare: create_revision("locks/billing-run") == 0
  then:    put("locks/billing-run", owner="sched-7", session=S123)
  else:    get("locks/billing-run")
)
-> succeeded: token = header.revision (for example 482113)
-> failed:    watch "locks/billing-run" for delete, then retry
```

For fair queuing, each waiter instead creates `locks/billing-run/{session}`
and the holder is the key with the lowest `create_revision`; each waiter
watches only the key just before it, so a release wakes one waiter, not all.

### 4.3 Protected resource check

The resource, not the lock service, enforces exclusion. It stores the highest
token it has accepted per protected object and rejects anything lower:

```text
WriteJobResult(job_id, result, fencing_token = 482113)
  if fencing_token < last_seen_token[job_id]: reject (stale holder)
  else: last_seen_token[job_id] = fencing_token; apply
```

### 4.4 Errors

| Error | Meaning | Client action |
|---|---|---|
| `session_expired` | Session TTL passed without keep-alive | Stop work guarded by its locks; create a new session |
| `not_leader` | Request reached a follower that cannot serve it | Retry via proxy |
| `compacted` | Watch revision older than retained history | Re-read current state, then watch from its revision |
| `quota_exceeded` | Tenant key count or size limit | Reduce usage; request quota |
| `value_too_large` | Above size limit | Store data elsewhere, keep a pointer |

## 5. Data model

<!-- Guidance: Show the replicated state and the access-pattern table: each query, the key or index that serves it, and why the key layout was chosen. -->

### 5.1 Replicated state

All state is one replicated state machine per cell, built from the Raft log:

```mermaid
erDiagram
  TENANT ||--o{ KEY : owns
  SESSION ||--o{ KEY : "attaches (ephemeral)"
  KEY ||--o{ KEY_REVISION : "history kept until compaction"
  SESSION ||--o{ WATCH : registers
  TENANT {
    string tenant_id PK
    int key_quota
    int byte_quota
  }
  SESSION {
    bigint session_id PK
    int ttl_s
    datetime expires_at
  }
  KEY {
    string path PK
    bigint create_revision
    bigint mod_revision
    int version
    bigint session_id
    bytes value
  }
  KEY_REVISION {
    string path PK
    bigint revision PK
    string op
  }
  WATCH {
    bigint watch_id PK
    string path_or_prefix
    bigint from_revision
  }
```

The cell keeps a single 64-bit revision counter that increases with every
committed change; it orders all changes and serves as the fencing token
source. Watches live in proxy and server memory, not in the replicated state.

### 5.2 Storage choices

| Data | Store | Why |
|---|---|---|
| Raft log | Append-only files on local SSD, fsynced | Durability of every committed entry |
| State machine | In-memory index plus an embedded B-tree or LSM file with multi-version keys | Fast reads; reads at past revisions until compaction |
| Snapshots | Local files, copied to object storage for disaster recovery | Replica catch-up and restore |
| Session and lease expiry | Leader memory, rebuilt from state on election | Leader alone expires sessions; followers do not |

### 5.3 Access patterns

| Access pattern | Served by | Key layout and rationale |
|---|---|---|
| Who is leader of `scheduler`? | Lowest `create_revision` under `elections/scheduler/` | Per-candidate keys avoid herds; order by revision is total |
| Acquire lock `billing-run` | Txn on `locks/billing-run` | One key per lock; attached to session |
| Read all config for a service | Range `config/{service}/` | Prefix per service keeps reads to one range |
| List live instances | Range `members/{service}/` of ephemeral keys | Session expiry removes dead instances |
| Follow config changes | Watch prefix `config/{service}/` from the read revision | Read then watch from that revision: nothing missed |
| Tenant usage | Counters per top-level prefix `{tenant}/` | Quotas enforced at write time |

## 6. High-level design

<!-- Guidance: One diagram with clients, proxies, the cell and its replicas, and where the leader sits. -->

```mermaid
flowchart LR
  subgraph clients["Clients"]
    a[Scheduler instances]
    b[Service instances]
    c[Config readers]
  end
  subgraph proxies["Proxy tier (stateless)"]
    p1[Proxy 1]
    p2[Proxy 2]
    p3[Proxy n]
  end
  subgraph cell["Coordination cell (5 voters, 3 zones)"]
    l[(Leader, zone A)]
    f1[(Follower, zone A)]
    f2[(Follower, zone B)]
    f3[(Follower, zone B)]
    f4[(Follower, zone C)]
    l <-->|Raft log replication| f1
    l <--> f2
    l <--> f3
    l <--> f4
  end
  a --> p1
  b --> p2
  c --> p3
  p1 -->|writes, keep-alives| l
  p2 -->|linearizable reads via read index| f2
  p3 -->|watches| f4
  l --> snap[(Snapshot backups)]
```

| Component | Responsibility | Scales by |
|---|---|---|
| Client library | Sessions, keep-alive, lock and election recipes, fencing tokens, watch resume | With clients |
| Proxy tier | Terminate sessions, batch keep-alives, cache reads, share watches | Proxy instances |
| Leader | Order all writes, expire sessions, confirm leadership for reads | One per cell |
| Followers | Replicate log, serve reads with read index, serve watches | Up to 5 voters; non-voting replicas for reads |
| Snapshot backup | Disaster recovery | Object storage |

## 7. Detailed design

<!-- Guidance: Go deep on two to four hard problems. For each, list the options, the choice and the reason, and show the failure behaviour. -->

### 7.1 Deep dive: consensus and linearizable reads

| Option | How it works | Strength | Weakness |
|---|---|---|---|
| A. Primary-backup with external failure detector | One primary, backups copy; an external system picks a new primary | Simple data path | Needs another consensus system to decide failover; split-brain risk |
| B. Multi-Paxos | Replicas agree on each log slot; a stable leader optimises the common case | Proven; flexible | Many variants; hard to implement and reason about |
| C. Raft | Strong leader, randomized election timeouts, log matching, joint consensus for membership | Designed for understandability; many mature implementations | Leader is a throughput bottleneck |
| D. Atomic broadcast as in ZooKeeper (ZAB) | Leader broadcasts ordered updates; recovery protocol on leader change | Proven at scale | Tied to one implementation family |

**Choice:** C, using a mature implementation rather than writing one.
**Reason:** the team must operate and debug the protocol during incidents;
Raft's structure (leader election, log replication, safety) is easier to
reason about, and its membership-change procedure supports replacing replicas
without downtime.

Linearizable reads have three options:

| Read option | How | Cost | Risk |
|---|---|---|---|
| Through the log | Append a read entry and wait for commit | One quorum write per read | Slow, expensive |
| Read index | Leader records commit index, confirms it is still leader with a quorum heartbeat, then the replica serves once it has applied up to that index | One round of heartbeats, batched across reads | None beyond normal Raft assumptions |
| Leader lease | Leader serves reads alone while its lease (based on election timeout) has not expired | No network round | Depends on bounded clock drift; unsafe if clocks jump |

**Choice:** read index by default, leader lease off. **Reason:** the extended
Raft paper describes confirming leadership with a majority before answering a
read and notes that relying on a lease makes safety depend on timing; for a
lock service, safety wins over a fraction of a millisecond. A new leader
commits a no-op entry at the start of its term before serving reads, so it
knows which entries are committed.

### 7.2 Deep dive: sessions, keep-alives and failover

Sessions tie ephemeral keys and locks to a live client. A session ends when no
keep-alive arrives before its TTL; then its ephemeral keys and locks are
deleted in one committed transaction, so watchers see a consistent change.

| Parameter | *Example* value | Reasoning |
|---|---|---|
| Session TTL | 30 s | Longer than leader failover plus network blips |
| Keep-alive interval | 10 s | Three chances before expiry |
| Election timeout | 1 to 2 s randomized | Cross-zone round trips; Raft paper suggests 150 to 300 ms for LAN-scale clusters |
| Client grace period | 45 s of retrying after losing contact | Survive failover; resume only if the cell confirms the session still exists |

During leader failover no keep-alive is acknowledged. Two measures keep
healthy sessions alive:

1. A new leader does not expire any session until it has given every session
   at least one full TTL from its election (session expiry is extended on
   leadership change).
2. The client library, on losing contact, enters a "jeopardy" state: it tells
   the application that its locks may be at risk, pauses work that needs them,
   and keeps trying other replicas for the grace period. If contact returns
   and the cell confirms the session is still alive, work resumes; if the
   session expired or the grace period ends, the application treats its
   locks as lost.

The application must also stop acting on a lock when its own process paused
(garbage collection, VM migration). Timeouts on the client cannot detect that
reliably, which is why fencing tokens (7.3) exist.

### 7.3 Deep dive: locks, leader election and fencing tokens

A lock gives mutual exclusion **in the coordination service**, not at the
resource. A holder can be paused after it last checked its session, wake up
after the session expired and another client took the lock, and still send a
write.

```mermaid
sequenceDiagram
  participant A as Client A
  participant B as Client B
  participant C as Coordination cell
  participant R as Protected resource
  A->>C: acquire lock
  C-->>A: granted, token 33
  Note over A: long pause, session expires
  C->>C: delete lock (session expired)
  B->>C: acquire lock
  C-->>B: granted, token 34
  B->>R: write with token 34
  R-->>B: ok, remember 34
  A->>R: write with token 33 (stale)
  R-->>A: rejected, 33 below 34
```

| Option | How it works | Protects against paused holder? |
|---|---|---|
| A. TTL lock in a cache | Set-if-absent with expiry | No; also unsafe on cache failover |
| B. Coordination-service lock only | Session-bound key | No; only the service knows who holds it |
| C. Lock-delay | After a holder's session expires, the lock cannot be taken for a short period | Reduces risk; does not remove it |
| D. Fencing token checked by the resource | Token = lock key's revision; resource rejects lower tokens | Yes, if every write path checks it |

**Choice:** D for every lock that guards a side effect, with C as an extra
margin for resources that cannot check tokens yet. **Reason:** only the
resource can reject a stale write after the fact. Teams that cannot add a
token check must design the work to be idempotent instead.

Leader election uses the same recipe: each candidate creates an ephemeral key
under `elections/{name}/`; the lowest `create_revision` leads and its
revision is the leader epoch, used as the fencing token for everything the
leader writes. Followers watch only their predecessor.

### 7.4 Deep dive: watches, caching and read scalability

| Option | How it works | Strength | Weakness |
|---|---|---|---|
| A. Polling | Clients re-read every few seconds | Simple | Load grows with clients; staleness equals interval |
| B. One-shot watches | Notification once; client re-reads and re-registers | Simple server | Changes between notification and re-register must be detected by version check |
| C. Revision-based streaming watches | Stream every change after a given revision; resumable after disconnect | Nothing missed; ordered | History must be retained until compaction |
| D. Client cache with server invalidation | Server invalidates cached entries before a write completes | Very low read load | Write waits for invalidations; complex |

**Choice:** C, served by followers and proxies, plus small proxy caches for
serializable reads. **Reason:** read-then-watch-from-revision gives clients a
gap-free view; proxies merge identical watches so the cell sees one per proxy.
Keep history for *Example* 1 hour; a watcher that falls further behind gets
`compacted` and must re-read.

Read scaling ladder, in order:

1. Serializable reads from any follower for discovery and config that
   tolerate staleness.
2. Read-index linearizable reads on followers.
3. Proxy caches kept current by watches.
4. Non-voting replicas (learners) that replicate the log and serve reads
   without slowing commits.
5. More cells, partitioned by tenant.

### 7.5 Misuse pitfalls and usage policy

| Pitfall | Why it hurts | Policy |
|---|---|---|
| Using the service as a database | Large values and high write rates slow every tenant's elections | Value cap 64 KB; per-tenant quotas; reviews for any write rate above 50/s |
| Fine-grained locks per request | Write rate explodes; latency on every request | Coarse locks held for minutes or hours; per-request coordination elsewhere |
| Lock without fencing | Paused holder corrupts the resource | Fencing token or idempotent work required |
| Everyone watches one key and re-reads at once | Notification and read herd | Proxies; jitter; watch predecessor only in queues |
| Short session TTLs "for faster failover" | Sessions expire during routine leader changes | TTL at least 3x keep-alive and above failover time |
| Treating a cell as global | Cross-region latency on every write | One cell per region; a global cell only for rare decisions |
| Assuming the service is always up | Hard dependency in every request path | Cache last known config; leaders keep working through short outages only when fenced |

### 7.6 How real systems do it

> **How real systems do it (paraphrased, not copied).** Burrows describes
> Google's Chubby in "The Chubby Lock Service for Loosely-Coupled Distributed
> Systems" (OSDI 2006). Chubby is aimed at coarse-grained locking and small
> files, with cells of typically five replicas that use Paxos to elect a
> master holding a master lease. Clients keep sessions alive with keep-alives;
> when a client loses contact, its library signals jeopardy and waits through a
> grace period (45 s by default in the paper) so sessions survive master
> failover. Lock holders can obtain a sequencer that servers check before
> acting, with a lock-delay as a weaker fallback for servers that do not check.
> Clients cache data and the master invalidates caches before changes complete;
> proxies can absorb keep-alives and reads. Separately, Ongaro and Ousterhout's
> "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014)
> defines Raft, decomposing consensus into leader election, log replication
> and safety; its extended version covers linearizable read handling. This
> template reuses the ideas, not the text or figures.

## 8. Scalability and performance

<!-- Guidance: Show how the design meets the numbers in section 3 and where it breaks first. -->

| Concern | Approach | Limit before redesign |
|---|---|---|
| Writes | Group commit; small values | Leader disk and CPU; *Example:* about 10 000 small writes/s per cell |
| Keep-alives | Proxy aggregation | Proxy count and session churn on proxy restarts |
| Reads | Read index on followers, proxies, learners | Heartbeat batching on the leader |
| Watches | Proxy sharing, jitter | Notification fan-out per server |
| Data size | Quotas, 2 GB cap | Snapshot install time for new replicas |
| Tenants | Separate cells per tenant group | Operational cost per cell |

Write latency budget (NFR-02, *Example*): client to proxy 0.5 ms, proxy to
leader 0.5 ms, leader append and parallel replication to the fastest two
followers across zones 2 ms plus fsync 2 ms, apply 0.2 ms, response path 1 ms;
about 6 ms typical, with headroom for cross-zone variance up to the 25 ms p99.

## 9. Reliability, security and operations

<!-- Guidance: Name the failure modes, the threats and the signals operators watch. Each failure needs detection, blast radius, mitigation and a recovery time objective. -->

### 9.1 Failure-mode table

| Component | Failure | Detection | Blast radius | Mitigation | RTO |
|---|---|---|---|---|---|
| Leader | Crash | Followers miss heartbeats | Writes and linearizable reads pause | Raft election; sessions extended on new leader | *Example:* under 5 s |
| One zone | Outage | Replica health | Up to two of five voters | Remaining three keep quorum | No interruption beyond election |
| Two zones | Outage | Quorum lost | Whole cell read-only or down | Clients run on cached config; documented manual recovery from snapshot | *Example:* 1 h manual |
| Disk | Slow fsync | Commit latency | All writes | Dedicated SSD; alert; replace replica | *Example:* 30 min |
| Proxy | Crash | Health checks | Its sessions must reconnect | Clients reconnect to another proxy within the grace period | *Example:* 10 s |
| Client | Long pause | Session expiry | Its locks move to another client | Fencing tokens reject its late writes | Immediate |
| Tenant | Abusive write rate | Per-tenant metrics | Every tenant's latency | Quotas and rate limits per tenant | *Example:* 1 min |
| [Component] | [Failure] | [Signal] | [Scope] | [Mitigation] | [Time] |

### 9.2 Security

| Threat | Control |
|---|---|
| Unauthorised lock or config change | mTLS for clients and peers; role-based access per prefix |
| Peer impersonation | Peer certificates pinned to cell membership |
| Secrets stored as config values | Prohibited by policy; secret manager instead; scanner on writes |
| Snapshot theft | Encrypted backups with restricted access |
| Denial of service by one tenant | Quotas, request limits, separate cells for critical tenants |
| [Threat] | [Control] |

### 9.3 Observability

| Signal | Metric | Alert threshold |
|---|---|---|
| Leadership | Leader changes per hour | *Example:* more than 3 |
| Commit latency | p99 proposal to commit | Above 25 ms for 5 min |
| Follower lag | Applied index behind leader | Above 1 000 entries |
| Sessions | Expirations per minute | Spike above baseline x 5 |
| Watches | Notification delay | Above 1 s at p99 |
| Size | Keyspace bytes vs cap | Above 70% |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why one was chosen. Include what changes at ten times and a tenth of the load. -->

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Consensus | Primary-backup; Multi-Paxos; Raft; ZAB-like | Raft | Understandable, mature implementations | Leader-bound writes |
| Linearizable reads | Via log; read index; leader lease | Read index | Safe without clock assumptions | One heartbeat round per read batch |
| Lock safety | Lock only; lock-delay; fencing | Fencing (+ lock-delay fallback) | Only the resource can reject stale writes | Every resource must check tokens |
| Notifications | Polling; one-shot; streaming from revision | Streaming from revision | Gap-free and resumable | History retention |
| Build or adopt | Write own; adopt etcd, ZooKeeper or Consul; managed | [Choice] | [Reason] | [Cost] |
| At 10x load | 1 million sessions, 20 000 writes/s | Partition by tenant into several cells; more proxies; learners for reads | One leader cannot take 10x writes | More cells to run and to place tenants on |
| At 0.1x load | 10 000 sessions, 200 writes/s | One 3-voter cell may suffice if one zone loss is the only target; no proxy tier | Lower cost | Cannot tolerate a second failure while one replica is down for maintenance |

## 11. Delivery plan and risks

<!-- Guidance: How the design reaches production safely, and what could stop it. -->

### 11.1 Milestones

| Milestone | Scope | Exit criterion | Target date |
|---|---|---|---|
| M1 | Cell, client library with sessions, locks and fencing tokens | Safety test suite passes with partitions and pauses | YYYY-MM-DD |
| M2 | Scheduler and job runner migrate (`system-design/design-job-scheduler`) | No duplicate runs in 30 days | YYYY-MM-DD |
| M3 | Proxy tier, watches, config and discovery | 100 000 sessions in load test; NFR-05 met | YYYY-MM-DD |
| M4 | Second cell, tenant placement, quotas | Failover drill per cell passes | YYYY-MM-DD |

### 11.2 Rollout and rollback

[*Example:* Each consumer migrates behind a flag that selects the old or new
election mechanism; both run in observe-only mode for a week and must agree
on the leader. Rollback flips the flag; the old mechanism stays deployed until
the migration is complete for 30 days.]

### 11.3 Risks

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Teams skip fencing token checks | High | High | Library makes token mandatory; review checklist | [@name] |
| R-02 | *Example:* Service becomes a dumping ground for data | Medium | High | Quotas, value cap, usage policy (7.5) | [@name] |
| R-03 | *Example:* Hot watch key overloads proxies | Medium | Medium | Jitter, watch sharing, load test | [@name] |
| R-04 | *Example:* Quorum loss in a regional disaster | Low | High | Cached config in clients; restore runbook | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

<!-- Guidance: Supporting detail, glossary, open questions and references. -->

### 12.1 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Which existing resources can check fencing tokens, and which need idempotency instead? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* Do we need a global cell, or can all decisions be regional? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.2 Glossary

| Term | Meaning |
|---|---|
| Cell | One replicated group of servers that forms a quorum |
| Session | Client's liveness lease, renewed by keep-alives |
| Ephemeral key | Key deleted automatically when its session ends |
| Fencing token | Monotonic number from the lock grant that resources compare to reject stale holders |
| Read index | Commit index the leader confirms with a quorum before a linearizable read is served |
| Jeopardy | Client state after losing contact, before the session is declared lost |
| Learner | Non-voting replica that receives the log and serves reads |
| Compaction | Removal of old revisions from history |
| [Term] | [Meaning] |

### 12.3 Related templates

- Distributed Key-Value Store System Design (`system-design/design-distributed-kv-store`): for data that does not belong here.
- Job Scheduler System Design (`system-design/design-job-scheduler`): main consumer of leader election and fencing.
- Message Queue System Design (`system-design/design-message-queue`): controller election and partition metadata.
- Stream Processing Engine System Design (`system-design/design-stream-processing-engine`): coordinator leader and checkpoint pointer.
- Distributed Cache System Design (`system-design/design-distributed-cache`): slot map storage.

### 12.4 References

| Reference | Use |
|---|---|
| Burrows M., "The Chubby Lock Service for Loosely-Coupled Distributed Systems", OSDI '06, 2006 | Coarse locks, sessions, grace period, sequencers, lock-delay, proxies (7.2, 7.3, 7.6) |
| Ongaro D., Ousterhout J., "In Search of an Understandable Consensus Algorithm", USENIX ATC '14, 2014, and its extended version | Raft, election timeouts, read-only handling (7.1, 7.6) |
| Hunt P. et al., "ZooKeeper: Wait-free Coordination for Internet-scale Systems", USENIX ATC '10, 2010 | Watches and coordination recipes (7.4) |
| etcd v3.6 documentation, API guarantees and API reference | Revisions, leases, watches from a revision, transactions (4, 5, 7.4) |
| Kleppmann M., "How to do distributed locking", 8 February 2016 | Fencing token argument (7.3) |

## Standard and licence note

Based on the publicly described designs and documentation cited in 12.4
(Chubby, Raft, ZooKeeper, etcd v3.6); no standard governs coordination
services. This is a reference design to adapt, with illustrative numbers
marked *Example*. Original text written for this collection; sources were used
as inspiration only and no text, figures or diagrams were copied. Check the
current documentation of any implementation you adopt, because API details
change between releases. Template licence: MIT.