# System Design: [Key-value store name]

> Reference design for a distributed key-value store that can also run as a
> cache. It covers partitioning with consistent hashing and virtual nodes,
> replication, quorum reads and writes, consistency models and conflict
> resolution (vector clocks versus last-write-wins), hinted handoff,
> anti-entropy with Merkle trees, gossip membership and failure detection,
> an LSM-tree storage engine with compaction, eviction policies for cache
> mode and hot-key handling. The concepts follow the Amazon Dynamo paper
> (DeCandia et al., SOSP 2007) and its open-source descendants. It follows
> the structure of the System Design Document template and is pre-filled
> with a worked design to adapt. Values marked *Example* are assumptions.
> Replace every `[bracketed]` value and every row marked *Example*.

<!--
Guidance: How to use this template
- Decide first what a stale or conflicting read costs the business. That
  answer picks the quorum settings (7.3) and the conflict strategy (7.4);
  everything else follows.
- Size from section 3 with your own item sizes and request mix. Replica
  operations, not client operations, load the nodes.
- If you only need a cache, read 7.9 and 7.10 first: many sections become
  optional when data can be recomputed.
- Test node loss, zone loss and network partition before launch; quorum
  maths on paper is not evidence.
-->

## Document control

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

| Field | Value |
|---|---|
| Document ID | [SDD-KV-001] |
| System / feature | [Distributed key-value store] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Author(s) | [@author] |
| Reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal] |
| Operating modes | [Durable store / Cache / Both] |
| Related | [Capacity estimation worksheet CAP-EST-nnn], [Database design], [ADR: conflict resolution] |

### 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 |
| Main client team | [@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:* Default quorum changed from R=1, W=1 to R=2, W=2 after stale-read incident analysis |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* Added cache mode with LFU eviction |
| 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:* Session, cart and user-preference data live in a single
relational primary that reaches 80% CPU at peak. Most access is by primary
key, values are opaque blobs, and the business prefers accepting a write
during a zone failure over rejecting it. Teams also run four separate cache
clusters with different eviction settings and no shared operations.]

### 1.2 Proposed solution

[*Example:* A leaderless, replicated key-value store. Keys are placed on a
consistent-hash ring with virtual nodes; each key is stored on three nodes
in three zones. Any node can coordinate a request; reads and writes succeed
when two of three replicas answer. Concurrent updates are detected with
version vectors and returned to the client for merging, or resolved by
last-write-wins for keyspaces that opt in. Temporary failures are covered by
hinted handoff, permanent divergence by Merkle-tree anti-entropy, and
membership by gossip with a phi accrual failure detector. Each node stores
data in an LSM-tree engine. The same software runs as a cache with one
replica, TTLs and LFU eviction.]

### 1.3 Decisions requested from reviewers

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Leaderless quorums or leader per partition? | Leaderless with N=3, R=2, W=2 | 7.3, 10 |
| Q-02 | *Example:* Conflict resolution default? | Version vectors with client merge; LWW opt-in per keyspace | 7.4 |
| Q-03 | *Example:* Strict or sloppy quorum? | Sloppy quorum with hinted handoff | 7.5 |
| Q-04 | *Example:* Compaction strategy? | Leveled for read-heavy keyspaces, size-tiered for write-heavy | 7.8 |
| [Q-nn] | [Question] | [Option] | [Section] |

## 2. Requirements

<!-- Guidance: Functional requirements describe behaviour; non-functional requirements describe qualities with numbers. Mark what is out of scope so nobody designs for it. -->

### 2.1 Functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* `get`, `put` and `delete` by key; values up to 1 MB | Must |
| FR-02 | *Example:* Per-request consistency level (ONE, QUORUM, ALL) | Must |
| FR-03 | *Example:* Return all concurrent versions with a context for merge | Must |
| FR-04 | *Example:* Optional TTL per key | Must |
| FR-05 | *Example:* Conditional put on version (compare-and-set within a replica set) | Should |
| FR-06 | *Example:* Cache mode with eviction and no durability guarantee | Should |
| FR-07 | *Example:* Range scans over keys | Won't (hash partitioning) |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Read latency | *Example:* p99 at or below 10 ms at QUORUM within a region | Client timing |
| NFR-02 | Write latency | *Example:* p99 at or below 15 ms at QUORUM | Client timing |
| NFR-03 | Write availability | *Example:* Writes accepted during loss of one zone | Zone failure game day |
| NFR-04 | Durability | *Example:* No acknowledged QUORUM write lost with one zone lost | Fault injection with verification |
| NFR-05 | Convergence | *Example:* Replicas converge within 1 h after a partition heals | Anti-entropy metrics |
| NFR-06 | Elasticity | *Example:* Add a node without downtime; rebalance under 4 h | Expansion test |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 2.3 Out of scope

- [*Example:* multi-key transactions and secondary indexes]
- [*Example:* cross-region synchronous replication (regions replicate asynchronously)]
- [*Example:* SQL or query language]
- [Item deferred, with the release that will take it]

## 3. Capacity estimation

<!-- Guidance: Back-of-the-envelope numbers decide the shape of the design. Show inputs, formulas and results; round generously and say which way you rounded. The method is in the Capacity estimation worksheet (`architecture/back-of-envelope-estimation`). -->

### 3.1 Assumptions

| Input | Symbol | Value | Source |
|---|---|---|---|
| Items stored | $K$ | *Example:* 2 billion | Migration inventory |
| Bytes per item on disk (key, value, metadata) | $s$ | *Example:* 1 200 B | Sample of production rows |
| Replication factor | $N$ | *Example:* 3 | 7.2 |
| Space amplification of the engine | $a$ | *Example:* 1.3 | Benchmark with leveled compaction |
| Usable disk per node at target fill (2 TB at 50%) | $d$ | *Example:* 1 TB | Hardware standard |
| Peak client reads per second | $Q_{r}$ | *Example:* 300 000 | Current database metrics x growth |
| Peak client writes per second | $Q_{w}$ | *Example:* 60 000 | Current database metrics x growth |
| Read quorum, write quorum | $R$, $W$ | *Example:* 2, 2 | 7.3 |
| Replica operations per node at saturation | $c$ | *Example:* 120 000/s | Benchmark on target instance |

### 3.2 Storage and node count

$$
S = K \times s \times N \times a = 2 \times 10^{9} \times 1\,200 \ \text{B} \times 3 \times 1.3 = 9.36 \ \text{TB}
$$

$$
n_{disk} = \left\lceil \frac{9.36}{1} \right\rceil = 10 \ \text{nodes}
$$

The cluster is set to 12 nodes (four per zone) so that each zone holds one
full copy of the data and storage has room for one year of growth.

### 3.3 Replica operations

A coordinator sends each read to $R$ replicas and each write to all $N$
replicas (waiting for $W$ acknowledgements):

$$
O = Q_{r} \times R + Q_{w} \times N = 300\,000 \times 2 + 60\,000 \times 3 = 780\,000 \ \text{replica ops/s}
$$

$$
\text{per node} = \frac{780\,000}{12} = 65\,000 \ (54\% \text{ of } c), \qquad
\text{one node lost} = \frac{780\,000}{11} \approx 70\,900 \ (59\%)
$$

With a whole zone lost (eight nodes left) the load is 97 500 per node, 81%
of saturation: the cluster survives but runs hot, so zone loss is a
declared degraded mode that pauses compaction-heavy maintenance (9.1).

### 3.4 Network

$$
B_{w} = 60\,000 \times 1\,200 \ \text{B} \times 3 = 216 \ \text{MB/s}, \qquad
B_{r} = 300\,000 \times 1\,200 \ \text{B} = 360 \ \text{MB/s}
$$

Reads fetch the full value from one replica and a digest from the other, so
read bandwidth is close to one copy per read. About 576 MB/s across 12 nodes
is under 50 MB/s per node, far below a 10 Gbit/s link.

### 3.5 Summary

| Quantity | Estimate | Design consequence |
|---|---|---|
| Data on disk | 9.36 TB with 3 replicas | 12 nodes of 2 TB, four per zone |
| Replica operations | 780 000/s at peak | 54% per node normally, 81% with a zone lost |
| Network | about 576 MB/s cluster-wide | Not a constraint |
| Ring tokens | 12 nodes x 256 virtual nodes = 3 072 | About 651 000 keys per token range |

## 4. API design

<!-- Guidance: Define the contract first: operations, request and response shapes, errors, idempotency and versioning. Make the consistency level and the version context explicit in the API so clients cannot ignore them. -->

### 4.1 Operations

| Operation | Parameters | Returns | Notes |
|---|---|---|---|
| `get` | key, consistency (ONE, QUORUM, ALL) | One or more versions, each with value and context | More than one version means a conflict to merge |
| `put` | key, value, context, consistency, ttl | New context | Context from the last `get` makes the write a descendant |
| `delete` | key, context, consistency | New context | Writes a tombstone kept for the grace period |
| `cas` | key, expected context, value | Success or current versions | Only within one replica set; runs a consensus round (for example Paxos) among the replicas, so it is slower than `put` |
| `batch_get` | up to 100 keys | Map of results | Fan-out across coordinators |

### 4.2 Request and response examples

The service exposes gRPC; the JSON below shows the same shape for
readability:

```json
{"op": "get", "keyspace": "carts", "key": "user:48213", "consistency": "QUORUM"}
```

```json
{"versions": [{"value": "eyJpdGVtcyI6WzEyLDQ0XX0=", "context": "vv:A=4,B=2"}, {"value": "eyJpdGVtcyI6WzEyLDQ1XX0=", "context": "vv:A=3,C=1"}], "conflict": true}
```

The client merges the two carts, then writes with a context that dominates
both versions:

```json
{"op": "put", "keyspace": "carts", "key": "user:48213", "value": "eyJpdGVtcyI6WzEyLDQ0LDQ1XX0=", "context": "vv:A=4,B=2,C=1", "consistency": "QUORUM"}
```

### 4.3 Errors

| Error | Meaning | Client action |
|---|---|---|
| `UNAVAILABLE_QUORUM` | Fewer than R or W replicas answered in time | Retry with backoff, or lower consistency if the keyspace allows |
| `TIMEOUT` | Coordinator timed out; write may or may not be applied | Retry with the same context; a duplicate can surface as a sibling with the same value, which the next merge collapses |
| `VALUE_TOO_LARGE` | Value above the configured limit | Store large objects elsewhere and keep a pointer |
| `CAS_FAILED` | Expected context is not current | Read, merge, retry |

## 5. Data model

<!-- Guidance: Show what is stored per key and what cluster metadata exists. The storage layout is the engine's; this section is about the logical model clients and operators see. -->

### 5.1 Entities

Each stored record carries its version vector; ring metadata is small and
gossiped to every node.

```mermaid
erDiagram
  KEYSPACE {
    string name PK
    int replication_factor
    string conflict_mode
    string compaction
    string mode
  }
  RECORD {
    string keyspace PK
    bytes key PK
    bytes value
    string version_vector
    bigint expires_at
    bool tombstone
  }
  NODE {
    string node_id PK
    string zone
    string status
    int generation
  }
  TOKEN {
    bigint token PK
    string node_id FK
  }
  HINT {
    string target_node FK
    bytes key
    bytes mutation
    bigint created_at
  }
  KEYSPACE ||--o{ RECORD : contains
  NODE ||--o{ TOKEN : owns
  NODE ||--o{ HINT : "holds for others"
```

### 5.2 Keyspace settings

| Keyspace | Mode | N | Default R / W | Conflict mode | Compaction | TTL |
|---|---|---|---|---|---|---|
| `carts` *(Example)* | Durable | 3 | 2 / 2 | Version vectors, client merge | Leveled | 30 days |
| `sessions` *(Example)* | Durable | 3 | 1 / 2 | Last-write-wins | Size-tiered | 24 h |
| `prefs` *(Example)* | Durable | 3 | 2 / 2 | Last-write-wins | Leveled | None |
| `page-cache` *(Example)* | Cache | 1 | 1 / 1 | Not applicable | In-memory only | 10 min |

## 6. High-level design

<!-- Guidance: One diagram that shows every component on the request paths and where state lives. Name components by responsibility. -->

```mermaid
flowchart LR
  app([Client library]) --> coord[Any node as coordinator]
  subgraph ring["Hash ring, 12 nodes in 3 zones"]
    coord --> r1[(Replica 1, zone a)]
    coord --> r2[(Replica 2, zone b)]
    coord --> r3[(Replica 3, zone c)]
    r1 <--> gossip((Gossip))
    r2 <--> gossip
    r3 <--> gossip
  end
  r1 --> eng[LSM engine: WAL, memtable, SSTables]
  coord -->|replica down| hint[(Hint store on fallback node)]
  ae[Anti-entropy: Merkle tree compare] --> r1
  ae --> r2
  ae --> r3
  ops[Admin API and metrics] --> coord
```

| Component | Responsibility | Scales by |
|---|---|---|
| Client library | Key hashing, choose coordinator (token-aware), retries, merge callback | With clients |
| Coordinator | Find replicas, send requests, wait for quorum, read repair | Every node can coordinate |
| Storage engine | Durable local storage with WAL, memtable and SSTables | Per node disk |
| Gossip and failure detector | Membership, token ownership, liveness | Every node |
| Hint store | Writes held for an unreachable replica | Per node, bounded |
| Anti-entropy | Detect and repair divergence between replicas | Background, throttled |

## 7. Detailed design

<!-- Guidance: Go deep on the parts that are new, risky or contested. Show the sequence of calls and the failure behaviour of each step. -->

### 7.1 Partitioning: consistent hashing with virtual nodes

Keys are hashed (for example with a 64-bit Murmur3 or xxHash) onto a ring.
Each node owns many points on the ring, called virtual nodes or tokens; a
key belongs to the first token clockwise from its hash. With plain
consistent hashing, adding or removing a node moves only the keys of the
ranges next to it, about $1/n$ of the data.

Virtual nodes fix two problems of one-token-per-node rings: uneven range
sizes and the fact that a joining or leaving node exchanges data with only
two neighbours. With 256 tokens per node, a new node takes small ranges from
every existing node, so rebalancing is spread across the cluster. Fewer
tokens per node reduce metadata and repair overhead; more tokens reduce
imbalance. Measure the load spread on your key distribution and record the
choice.

### 7.2 Replication

The preference list for a key is the next $N$ distinct physical nodes
clockwise from the key's position, skipping tokens of nodes already chosen
and placing at most one replica per zone. With $N = 3$ and three zones, each
zone holds one copy of every key, so losing a zone leaves two copies.

### 7.3 Quorum reads and writes

A write succeeds when $W$ replicas acknowledge it; a read returns when $R$
replicas answer. If the read set and write set must overlap in at least one
replica:

$$
R + W > N
$$

With $N = 3$, $R = 2$, $W = 2$ gives $2 + 2 = 4 > 3$. Writes stay available
with up to $N - W = 1$ replica down; reads with up to $N - R = 1$ down.

| Setting (N=3) | Overlap | Read latency | Write latency | Tolerates for reads / writes | Use for |
|---|---|---|---|---|---|
| R=1, W=3 | Yes | Lowest | Highest | 2 / 0 failures | Read-mostly config data |
| R=2, W=2 | Yes | Medium | Medium | 1 / 1 | Default |
| R=3, W=1 | Yes | Highest | Lowest | 0 / 2 | Rare; one acknowledged copy risks loss |
| R=1, W=1 | No | Lowest | Lowest | 2 / 2 | Data where stale reads are harmless |

Overlap is not linearizability. Concurrent writes can still conflict, a
write that failed to reach $W$ may remain on some replicas and be read
later, and sloppy quorums (7.5) let writes land on nodes outside the
preference list. Use `cas` (4.1) or a separate consensus-based store when an
operation needs a single serial order.

**Read repair:** when the coordinator sees replicas with older versions in a
read, it writes the newest version back to them after answering the client.

### 7.4 Consistency models and conflict resolution

The default model is eventual consistency. When R+W>N holds and no
sloppy-quorum fallback is in play, a read observes the latest acknowledged
write; during failures and hinted handoff it may not, so clients must not
assume read-your-writes.

**Version vectors.** Each version carries a list of (node, counter) pairs.
A coordinator increments its own counter on each write. Version X descends
from Y if every counter in X is at least the one in Y; otherwise they are
concurrent and both are kept.

| Step | Event | Version vector | Relationship |
|---|---|---|---|
| 1 *(Example)* | Node A writes cart v1 | A=1 | Initial |
| 2 *(Example)* | Node A writes v2 using context of v1 | A=2 | Descends from v1, v1 discarded |
| 3 *(Example)* | During a partition, node B writes v3 from v2 | A=2, B=1 | Descends from v2 |
| 4 *(Example)* | Node C writes v4 from v2 | A=2, C=1 | Concurrent with v3 |
| 5 *(Example)* | Client reads v3 and v4, merges, writes via node A | A=3, B=1, C=1 | Descends from both |

Vectors grow with the number of coordinators; prune entries older than a
threshold (for example keep the ten most recent) and accept that pruning can
occasionally surface a false conflict.

**Last-write-wins (LWW).** Each write carries a timestamp and the highest
wins. It needs no client merge, but clock skew silently drops writes: a
node whose clock runs 200 ms fast wins against a real later write. Use LWW
only where losing a concurrent update is acceptable (sessions, preferences),
use hybrid logical clocks to limit skew effects, and monitor clock offset.

**Alternatives:** conflict-free replicated data types (counters, sets,
registers) merge automatically and suit carts and counters; they constrain
the value format.

### 7.5 Sloppy quorum and hinted handoff

When a replica in the preference list is unreachable, the coordinator sends
the write to the next healthy node on the ring with a hint naming the
intended owner. The fallback node stores the hint and replays it when gossip
reports the owner alive again.

```mermaid
sequenceDiagram
  participant C as Coordinator
  participant A as Replica A
  participant B as Replica B (down)
  participant D as Fallback D
  C->>A: put k (vv A=3)
  C->>B: put k
  Note over B: no answer within 50 ms
  C->>D: put k with hint for B
  A-->>C: ack
  D-->>C: ack (hinted)
  C-->>C: W=2 reached
  Note over D,B: later, gossip marks B alive
  D->>B: replay hinted write
  B-->>D: ack, hint deleted
```

Hints are capped per target (for example 3 hours of writes); beyond that the
hint is dropped and anti-entropy repairs the replica. A hinted write counts
toward $W$ for availability, which is exactly why sloppy quorums weaken the
overlap guarantee in 7.3.

### 7.6 Anti-entropy with Merkle trees

Each replica keeps a Merkle tree per token range: leaves are hashes of
small key ranges, inner nodes hash their children. Two replicas compare
roots; if they differ, they descend only into differing subtrees and stream
the keys under differing leaves. With about 651 000 keys per token range and
$2^{15} = 32\,768$ leaves, each leaf covers about 20 keys, so a repair moves
little more than the divergent data.

Run repair on every range within the tombstone grace period (7.8);
otherwise a replica that missed a delete can resurrect the deleted value.

### 7.7 Membership, gossip and failure detection

- **Gossip:** every second each node exchanges its view (node, generation,
  heartbeat version, status, tokens) with one to three random peers. State
  spreads to all nodes in a number of rounds that grows with the logarithm
  of cluster size.
- **Seeds:** a small list of seed nodes bootstraps new members and prevents
  logical partitions of the gossip graph.
- **Failure detection:** a phi accrual detector turns inter-arrival times of
  heartbeats into a suspicion level $\phi$; a node is marked down for
  routing when $\phi$ exceeds a threshold (*Example:* 8). Marking down is
  local and reversible; removing a node from the ring is an explicit
  operator action, so a flapping network never triggers mass data movement.

### 7.8 Storage engine: LSM tree and compaction

Writes go to a write-ahead log (fsync policy per keyspace) and an in-memory
memtable. Full memtables flush to immutable sorted files (SSTables) with a
Bloom filter and a sparse index. Reads check the memtable, then SSTables
from newest to oldest, skipping files whose Bloom filter excludes the key.
Deletes write tombstones that remain for a grace period (*Example:* 10 days)
before compaction can drop them.

| Strategy | How it merges | Write amplification | Read amplification | Space amplification | Use for |
|---|---|---|---|---|---|
| Size-tiered | Merge files of similar size | Low | Higher (more files per key) | High during merges (up to 2x temporarily) | Write-heavy, TTL data |
| Leveled | Keep levels of non-overlapping files, each about 10x larger | Higher | Low (about one file per level) | Low (about 1.1x) | Read-heavy, updates |
| Time-window | Group files by write time; drop whole windows on expiry | Low | Low for recent data | Low | Time series with TTL |

Throttle compaction so it never takes more than a set share of disk
bandwidth at peak, and alert when pending compaction bytes keep growing.

### 7.9 Cache mode and eviction policies

In cache mode a keyspace runs with $N = 1$ (or 2 for hot data), no WAL, an
in-memory engine and mandatory TTLs. When memory reaches the limit, the
eviction policy picks victims:

| Policy | Evicts | Strength | Weakness |
|---|---|---|---|
| LRU | Least recently used | Simple, good for recency-driven access | A single scan flushes the hot set |
| LFU (with decay) | Least frequently used | Keeps stable hot keys | Slow to adapt without decay |
| TinyLFU-style admission plus LRU | Admits a new key only if it is likely more popular than the victim | Scan resistant, high hit ratio | More complex, sketch memory |
| TTL-first | Keys closest to expiry | Predictable | Ignores popularity |
| Random | Any key | Cheapest | Lower hit ratio |

*Example:* the page cache holds a hot set of 240 GB on six nodes with 48 GB
usable each (288 GB, 83% full), LFU with decay, TTL 10 minutes. Cache
misses fall through to the owning service, which must survive a cold cache;
see 9.1.

### 7.10 Hot keys

Detect hot keys with a per-node top-k sketch (count-min sketch plus heap)
exported every 10 s. Mitigate in order:

1. Client-side near cache with a short TTL (1 to 5 s) for read-hot keys.
2. Read from any replica (R=1) for keyspaces that accept staleness, which
   spreads a hot key over three nodes.
3. Split write-hot counters into $m$ sub-keys (`key#0` to `key#m-1`) and sum
   on read.
4. Request coalescing at the coordinator so concurrent misses on the same
   key cause one storage read.

## 8. Scalability and performance

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

| Concern | Approach | Limit before redesign |
|---|---|---|
| Throughput | Add nodes; tokens rebalance across the cluster | *Example:* load per node above 60% at peak |
| Storage | Add nodes; leveled compaction keeps space amplification low | Disk fill above 50% |
| Large values | Limit 1 MB; larger objects go to object storage | Values above 100 KB hurt tail latency |
| Hot keys | 7.10 | One key above a single node's capacity even after splitting |
| Wide fan-out batches | Token-aware batching per replica set | Batches above 100 keys |

Latency budget for a QUORUM read (target p99 10 ms):

| Step | Budget |
|---|---|
| Client to coordinator (token-aware, same zone) | 0.5 ms |
| Coordinator to second-fastest replica, cross-zone round trip | 2 ms |
| Storage read (memtable or one to two SSTables, block cache) | 3 ms |
| Merge versions, build response | 0.2 ms |
| Headroom (compaction, garbage collection, queueing) | 4.3 ms |

## 9. Reliability, security and operations

<!-- Guidance: Name the failure modes, the threats and the signals operators watch. Each mitigation should be testable. -->

### 9.1 Failure modes

| Failure | Impact | Detection | Mitigation |
|---|---|---|---|
| One node down | Writes go to fallbacks with hints | Gossip, $\phi$ above threshold | Hinted handoff; repair after hint window |
| One zone down | Two replicas remain; load 81% per node | Zone health | Declared degraded mode; pause repair and major compaction |
| Network partition | Both sides accept writes at sloppy quorum | Gossip views disagree | Version vectors surface conflicts; merge on read |
| Disk failure | Node loses data | Disk errors | Replace node, stream from replicas, run repair |
| Clock skew | LWW keyspaces drop writes | Clock offset metric above 50 ms | NTP or PTP monitoring; vector-clock keyspaces unaffected |
| Cold cache after restart | Backend overload | Hit ratio drop | Warm from snapshot; rate-limit misses to the backend |
| [Failure] | [Impact] | [Signal] | [Mitigation] |

### 9.2 Security

| Threat | Control |
|---|---|
| Unauthenticated access | mTLS between clients and nodes and between nodes; per-keyspace credentials |
| Data exposure at rest | Disk encryption; keys in a key management service |
| Rogue node joining the ring | Node certificates checked before gossip admission |
| Noisy tenant | Per-keyspace request quotas and size limits |
| [Threat] | [Control] |

### 9.3 Observability

| Signal | Metric or log | Alert threshold |
|---|---|---|
| Latency | p99 get and put per keyspace | Above NFR-01 or NFR-02 for 10 min |
| Quorum failures | `UNAVAILABLE_QUORUM` rate | Above 0.01% for 5 min |
| Hints pending | Bytes per target node | Growing for more than 1 h |
| Repair progress | Ranges repaired within grace period | Any range older than grace period minus 2 days |
| Compaction | Pending compaction bytes | Growing for more than 6 h |
| Conflicts | Versions returned per get | Sudden rise (partition or client bug) |

### 9.4 Cost estimate

| Item | Unit cost | Quantity | Monthly cost |
|---|---|---|---|
| Storage nodes | [USD per node-month] | *Example:* 12 | [USD] |
| Cache nodes | [USD per node-month] | *Example:* 6 | [USD] |
| Cross-zone traffic | [USD per GB] | Replication and reads across zones | [USD] |
| Backups (snapshots to object storage) | [USD per TB-month] | 9.36 TB | [USD] |
| **Total** | | | **[USD]** |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why you chose one. Reviewers will propose the alternatives anyway; answer them here. -->

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Replication model | Leader per partition (Raft); leaderless quorums | Leaderless | Writes available during zone loss without election | No single serial order; conflicts possible |
| Partitioning | Range; hash with vnodes | Hash with vnodes | Even spread, simple rebalancing | No range scans |
| Conflict resolution | LWW; version vectors; CRDTs | Version vectors default, LWW opt-in | No silent loss where it matters | Client merge code |
| Quorum type | Strict; sloppy | Sloppy with hints | Higher write availability | Weaker overlap during failures |
| Engine | B-tree; LSM tree | LSM tree | High write throughput, compression | Compaction overhead, read amplification |
| Build or buy | Managed service; open-source; build | [Choice] | [Reason] | [Cost] |
| [Decision] | [Options] | [Chosen] | [Why] | [Cost] |

## 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 | Cluster of 12 nodes, `prefs` keyspace in shadow writes | Fault injection suite passes (node, zone, partition) | YYYY-MM-DD |
| M2 | `sessions` keyspace live | p99 targets met for 14 days | YYYY-MM-DD |
| M3 | `carts` keyspace with client merge | Conflict merge tested with recorded partitions | YYYY-MM-DD |
| M4 | Cache mode replaces team cache clusters | Hit ratio at or above previous clusters | YYYY-MM-DD |

### 11.2 Rollout and rollback

[*Example:* Dual-write from the relational database to the new store, compare
reads in shadow mode, then switch reads per keyspace behind a flag. Rollback
switches reads back; dual writes continue until the keyspace has run 30 days
without discrepancy.]

### 11.3 Risks

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Client teams ignore conflicts and drop versions | Medium | High | Library forces a merge callback; tests in client CI | [@name] |
| R-02 | *Example:* Repair falls behind, deleted data resurrects | Medium | High | Repair scheduler with alerts before the grace period ends | [@name] |
| R-03 | *Example:* Zone loss pushes nodes above saturation | Low | High | Capacity review at 50% growth; add a node per zone | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

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

### 12.1 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Do any keyspaces need cross-region active-active writes? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* Is a CRDT library acceptable for carts instead of client merge? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.2 Glossary

| Term | Meaning |
|---|---|
| Consistent hashing | Placement where adding or removing a node moves only nearby key ranges |
| Virtual node (token) | One of many ring positions owned by a physical node |
| Preference list | The N nodes responsible for a key |
| Quorum | Minimum number of replicas that must answer (R for reads, W for writes) |
| Sloppy quorum | Quorum counted on the first healthy nodes, not only the preference list |
| Hinted handoff | Holding a write for an unreachable replica and replaying it later |
| Version vector | Per-node counters attached to a value to detect concurrent updates |
| Merkle tree | Tree of hashes used to find differing key ranges cheaply |
| Tombstone | Marker recording a delete until all replicas have seen it |
| [Term] | [Meaning] |

### 12.3 References

| Reference | Use |
|---|---|
| G. DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007 | Ring, preference lists, sloppy quorum, hinted handoff, vector clocks, Merkle-tree anti-entropy, gossip |
| D. Karger et al., "Consistent Hashing and Random Trees", STOC 1997 | Consistent hashing |
| P. O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996 | Storage engine in 7.8 |
| N. Hayashibara et al., "The phi Accrual Failure Detector", SRDS 2004 | Failure detection in 7.7 |
| Database design (`architecture/database-design`) | Data modelling for the services that use the store |
| Capacity estimation worksheet (`architecture/back-of-envelope-estimation`) | Method for section 3 |

## Standard and licence note

Based on the published Dynamo paper (DeCandia et al., 2007) and the other
papers listed in 12.3, used as concept sources only, and on common industry
practice for distributed key-value stores. This is a reference design to
adapt, with illustrative numbers. Original text written for this collection;
no text from the cited papers is reproduced. Check the documentation of the
store you build on for its current behaviour and defaults. Template
licence: MIT.