Key-Value Stores and Distributed Caches

At 09:17, Atlas loses one of six cache cells. Cache CPU falls. Network traffic on the five survivors rises by 20%, which they can absorb. The database is the component that fails.

Before the loss, Atlas serves 240,000 cache reads per second at a modeled 96.5% hit rate. The database therefore receives about 8,400 read misses per second. Traffic is even across cells, so the lost cell had served 40,000 reads per second; 38,600 of them had been hits. Those keys are absent from their new owners immediately after remapping:

steady backend misses = 240,000 reads/s × (1 - 0.965)
                      = 8,400 requests/s

displaced hits = (240,000 reads/s / 6 cells) × 0.965
               = 38,600 requests/s

unmitigated backend demand = 8,400 + 38,600
                           = 47,000 requests/s

The backend’s safe envelope is 18,000 requests per second. The cache tier has spare operations capacity, yet the backend surge transfers 2.61 times safe load into a slower dependency. Hit rate did not predict this. Average requests per second did not predict it. The decisive quantities were which keys disappeared, how expensive their misses were, and how quickly protection activated.

That incident supplies the central rule for both key-value stores and distributed caches: design for key popularity and miss cost, not average operations per second; a small hot set often determines the architecture.

Start with the key contract

A key-value interface appears simple because it places much of the design burden inside the key. Before selecting memory, disks, replicas, or routing, write the operation contract.

Atlas’s product-summary cache uses:

key:      product-summary:{market}:{product-id}:{representation-version}
value:    rendered summary plus authoritative version and generated-at time
reads:    240,000/s steady; 390,000/s launch peak
writes:   8,000/s invalidation or replacement
deletes:  900/s product/market withdrawal
value:    p50 420 B; p95 1.8 KiB; p99 9.6 KiB; max 64 KiB
skew:     hottest key 18,000 reads/s; top 0.2% keys carry 61% of reads
freshness: 30 s normally; withdrawal must not be served after authority version
miss cost: p50 34 ms; p99 210 ms; 3.8 backend operations per fill

The key encodes market and representation version because those facts change identity. It does not encode every source-table version: that would turn each update into a new unreachable key population and leave retention to luck. A key needs a canonical binary or textual encoding, length limit, namespace ownership, hashing rule, collision policy, and version migration plan. Ambiguous concatenation such as 12:34 without field boundaries invites collisions. User-controlled unbounded prefixes invite memory and cardinality attacks.

Classify each operation separately:

• GET may accept a bounded-stale value if it carries an authority version and the caller’s correctness rule permits it.
• PUT if version = v is a conditional mutation, not an ordinary overwrite.
• DELETE may need a tombstone so an old replica or fill cannot resurrect withdrawn state.
• INCREMENT creates a write-hot authority and may require the invariant treatment of transactional systems.
• MGET over one partition is a different operation from a scatter across 40 partitions.

“Eventually consistent” is not an operation contract. State monotonic-read, read-your-write, conditional-write, conflict, deletion, and failure behavior per key class. A cache copy must not quietly become the authority for withdrawal, payment, inventory, or access control.

Memory-resident and storage-backed designs fail differently

An in-memory hash table can provide a short point-access path: route, locate a bucket, compare the key, return the value. Its costs include hash computation, pointer or bucket traversal, allocator behavior, metadata, synchronization, replication, network, and memory capacity. A restart or cell loss removes its working set unless persistence or another replica restores it.

A storage-backed key-value engine can accept a larger working set and durable state. A common log-structured shape acknowledges writes to an append path, records recent state in memory, writes immutable sorted runs, consults indexes and filters for reads, and compacts older versions. It exchanges random in-place writes for sequential write and background merge work. Read amplification, write amplification, space amplification, cache residency, and compaction debt become part of the request contract.

These are not simply “fast” and “slow” choices:

Hash tables optimize equality lookup but do not make values free to store. Log-structured layouts improve write shape but do not make compaction free. Ordered indexes support scans but add bytes and update work. Select the local data structure from the actual operation mix, value distribution, durability, scan need, and recovery path.

For storage-backed systems, expose compaction debt: bytes pending, levels/runs touched per read, obsolete/tombstone bytes, write stalls, background I/O, temporary space, and foreground latency by compaction state. A steady write rate below device bandwidth can still be unsustainable when each logical byte is rewritten several times. A manual “catch-up compaction” during an incident can consume the same I/O needed by reads and replica repair.

Partition maps move keys, not popularity

Hash partitioning maps a key into a token, slot, or bucket and assigns that range to an owner. Consistent-hashing families reduce remapping when owners change; virtual nodes or many logical partitions can make placement more granular and let heterogeneous nodes own different shares. They do not guarantee balanced demand. Uniform hash space can place one 18,000-read/s key on a single owner.

Record three distributions:

1. bytes per partition and replica;
2. operations and service demand per partition; and
3. hottest keys and tenants within each partition.

A partition with 3% of bytes can consume 40% of CPU. A balanced request count can hide large-value serialization and network skew. A virtual-node move that balances bytes can make operations worse. Placement needs resource-weighted evidence, failure-domain constraints, and a movement budget.

Atlas’s clients cache a versioned partition map. On each request they compute the partition, select an eligible replica, and include the map epoch. A server that no longer owns the key redirects or rejects with its newer epoch. The client refreshes topology under a single-flight guard and retries only within its deadline and attempt budget. Without those rules, thousands of clients can refresh simultaneously, stale clients can hammer the old owner, and redirection chains can become a control-plane outage.

Three routing shapes are viable:

Partition-aware clients remove a proxy hop and distribute routing work. They increase client-library compatibility, connection count, map convergence, and rollout risk.

Routing proxies centralize topology, authentication, admission, and observability. They add a hop, queue, capacity tier, and failure domain. A proxy fleet must itself partition or bound work.

Any-node coordination lets a server forward to the current owner. It simplifies clients but spends server-to-server bandwidth and can hide stale topology behind extra hops.

Reject a design review that says only “use consistent hashing.” Ask who owns the map, how epochs advance, how clients discover change, what happens during a partial move, how connections drain, and which request budget pays for redirection.

Replication defines two paths and one authority

A key request path is not just client → node. A write may cross coordinator selection, version validation, log or memory mutation, replica transfer, acknowledgment, and visibility. A read may select one replica, read several and reconcile, or require an authority/version threshold.

For each key class, state:

• replica count and failure-domain placement;
• write authority and conflict rule;
• acknowledgment boundary;
• read selection and required version;
• repair and tombstone propagation;
• behavior when the partition is split; and
• when a failed owner is fenced from returning.

Quorum-like R, W, and N labels are incomplete without failure detection, sloppy placement, clock/version representation, read repair, concurrent-write reconciliation, and membership epoch. Replication can trade latency, availability, durability, and staleness, but it does not make two conflicting writers one authority.

For a cache, replicas may be disposable performance copies. For a key-value authority, replicas participate in the durability and consistency promise. Do not use the cache-loss playbook—drop and refill—on the only authoritative copy of a value.

Hot keys need a mechanism matched to their operation

Atlas’s hottest summary receives 18,000 reads per second. One owner has a measured safe envelope of 12,000 reads per second for this value-size and connection population, so modeled utilization is 1.5 before retries or failure.

Several mitigations solve different problems:

Three perfectly balanced read replicas give an optimistic 36,000-read/s envelope and 0.5 utilization for the hot key. That is not a guarantee: client imbalance, replica lag, shared partition demand, failover, and connection limits reduce usable capacity. If the key is a counter requiring ordered writes, read replication does not relieve the mutation owner. If it is a large generated representation, pushing a versioned value to edge caches may remove more work than adding central replicas.

Do not salt a business key reflexively. Salting a read-only value duplicates state and complicates invalidation. Salting a counter either requires aggregation or weakens one authority. First identify whether the constrained work is lookup CPU, serialization bytes, network, write coordination, fill cost, or caller fan-out.

TTL, expiry, tombstones, and cleanup are separate decisions

A time to live is a retention or freshness control, not proof that a value is correct. Atlas gives ordinary summaries a 30-second TTL to bound staleness and memory residence, with randomized spread to avoid synchronized expiry. Withdrawal uses an authority-version check and tombstone because serving a withdrawn product for 30 seconds is not allowed.

Expiry can be implemented lazily on access, actively by background sampling or timing structures, or during storage compaction. Each shape leaves different expired-but-resident bytes and consumes different CPU/I/O. A burst of identical TTLs can create an expiry storm: many keys disappear together, fills synchronize, backend work rises, and newly filled values evict other useful data.

Tombstones prevent resurrection when deletes race with replicas, repair, delayed writes, or immutable storage runs. They consume memory and storage until every relevant old version is unreachable. Garbage-collecting tombstones too early can restore deleted data; retaining them forever can make compaction and reads expensive. The deletion contract needs a version, propagation horizon, repair horizon, backup/replay behavior, and proof for safe removal.

Background cleanup is production work. Track expired bytes waiting, tombstone age, scan/compaction CPU and I/O, foreground interference, and whether cleanup falls behind during overload. A system that meets foreground latency by accumulating unbounded cleanup debt has borrowed from recovery.

Eviction chooses the next backend request

Eviction and admission are different. Admission decides whether a candidate enters the cache. Eviction chooses what leaves when capacity is constrained. Admitting a one-hit scan can evict a compact hot set even if the eviction policy is nominally recency- or frequency-aware.

Choose policy from reuse-distance and miss-cost evidence:

• recency is useful when recent access predicts near-future reuse;
• frequency helps preserve repeatedly hot items but adapts slowly without aging;
• size-aware policy avoids letting a few large values consume disproportionate space;
• cost-aware policy may retain expensive-to-recompute values even at lower frequency;
• explicit non-admission protects the established working set from scans and uncacheable objects.

Eviction storms have a feedback loop: memory pressure evicts useful keys, misses allocate fill buffers, fills increase memory and backend load, latency extends in-flight object lifetimes, and more keys are evicted. Guard on eviction rate, miss-cost-weighted demand, allocation failures, fragmentation, and backend reserve—not only percentage memory used.

Fragmentation means free bytes are not necessarily usable for the next allocation class. Slab or size-class allocators trade allocation speed and predictability for internal slack. External fragmentation, per-item metadata, hash buckets, pointers, TTL tables, client buffers, replication buffers, snapshots, forks, compaction, and operating-system reserve all sit outside “sum of values.” Measure resident set and allocator-class occupancy against logical payload.

Account for every resident byte

Atlas models 20 million items per cell with a 36-byte average key, 720-byte average value, and 96 bytes of per-item/index metadata. The model applies a 1.12 allocator multiplier, keeps two resident copies, reserves transient space equal to 8% of replicated resident bytes, and targets 80% occupancy:

logical keys + values                     = 14.08 GiB
metadata                                  =  1.79 GiB
one resident copy after allocator factor  = 17.77 GiB
two resident copies                       = 35.55 GiB
transient buffers                         =  2.84 GiB
used before headroom                      = 38.39 GiB
required physical at 80% occupancy        = 47.99 GiB
margin in a 64 GiB cell allocation        = 16.01 GiB

These are modeled averages, not a purchase order. Averages understate a heavy value-size tail and allocator boundaries. Validate with item-size histograms, metadata samples, allocator statistics, process RSS, copy/snapshot peaks, replication backlog, and a cold-to-warm load test. Repeat during rebalancing and failure because transient copies can be largest then.

Capacity must pass three gates at once:

bytes: resident working set + copies + metadata + transient + headroom
operations: reads + writes + deletes + expiry + repair + replication
miss work: miss rate × backend service demand, by key/cost class

Network bytes, serialization CPU, connections, storage I/O, and compaction may add more gates. “The cluster holds the dataset” is insufficient if one hot partition exceeds CPU or a cell loss overwhelms the backend.

Multi-key operations expose the partition boundary

A single-key interface offers predictable ownership because one key maps to one partition. Multi-key operations preserve that property only when all keys are co-located or the system supplies a cross-partition transaction/coordination protocol.

Co-location techniques—hash tags, compound partition keys, aggregates—can make a known group atomic or efficient. They can also create a giant partition, couple unrelated lifecycles, and block independent scaling. Scatter/gather adds fan-out, partial results, retry ambiguity, and tail amplification. A client-side sequence of GET, modify, PUT is not atomic merely because each call is fast.

Classify a multi-key need as one of four jobs:

1. independent parallel reads with declared partial behavior;
2. co-located atomic mutation under one owner;
3. cross-owner invariant requiring transaction or serialized authority; or
4. derived aggregation that can be asynchronous and reconciled.

Reject the key-value archetype as the primary design when secondary queries, broad scans, joins, or cross-key invariants dominate. An explicit index or transactional/analytical system may be the honest center, even if it stores some fields as values.

Rebalancing is a foreground traffic event

Adding capacity changes placement before it creates warm capacity. A rebalance reads existing values, transfers bytes, writes new copies, updates ownership, invalidates client topology, warms indexes/caches, and eventually deletes old copies. It competes with foreground CPU, network, storage, replication, expiry, and backend fills.

Cache loss is the abrupt version of that transition: ownership moves before useful values are resident, so the backend becomes an involuntary warm-up source unless guarded controls intervene.

Use versioned phases:

1. add empty capacity without authority;
2. copy a bounded partition range with checksums/version evidence;
3. tail or reconcile concurrent changes;
4. make the destination eligible for shadow reads;
5. advance ownership epoch and route a canary share;
6. drain old ownership after stale-client and retry horizons; and
7. delete old copies only after rollback no longer needs them.

Warm-up must be demand-aware. Sequentially loading the whole keyspace may evict the actual hot set and saturate the backend. Options include restoring a recent working-set snapshot, shadowing bounded production reads, prioritizing hot keys from access logs, peer-copying values, or admitting on demand behind coalescing. Each has privacy, staleness, and backend-cost implications.

For a cache, a new node can look healthy while empty. For storage-backed state, a new replica can have all bytes yet lack a warm block cache or completed compaction. Readiness needs workload evidence, not process liveness.

The Atlas cell-loss playbook

Atlas’s unmitigated 47,000 backend requests per second cannot be “autoscaled away” safely: backend scaling is slower than the surge, and additional database concurrency can increase queueing or contention. The playbook protects correctness first and backend reserve second.

Detect and classify. Confirm the ownership epoch, lost ranges, hit/miss populations, backend demand by key class, survivor utilization, and whether the event is cell loss, stale topology, split authority, or an eviction storm. Do not remap around a network partition until old owners are fenced.

Freeze amplification. Disable automatic client retries beyond one topology refresh. Coalesce one fill per key and bound waiters by deadline. Stop speculative warmers, scans, and low-value prefetch. Apply per-key, tenant, and backend-cost admission.

Use correctness-scoped degradation. Atlas can serve last-known summaries for 65% of displaced-hit traffic because those representations exclude withdrawals and carry an authority version. Withdrawal-sensitive, access-control, inventory, and price-commit paths bypass stale data.

Protect the backend. After stale-safe serving, 35% of displaced hits remain: 13,510 fills per second. The model assumes coalescing removes 70% of those duplicate fills, leaving 4,053 added requests per second. With the steady 8,400 misses:

guarded backend demand = 8,400 + 4,053
                       = 12,453 requests/s

backend utilization against safe envelope = 12,453 / 18,000
                                          ≈ 0.692

The arithmetic proves only that these assumed reductions fit the envelope. It does not prove they will occur. Atlas measures the eligible stale fraction, distinct fills per key, coalescing fan-in, backend request demand, and dropped/deferred work continuously. If the guard fails, it rejects optional representations before stealing correctness-critical capacity.

Restore deliberately. Recreate ownership with a new epoch, warm the highest miss-cost keys under a token budget, canary traffic, and watch backend reserve. Do not reconnect the old cell until fencing proves it cannot serve stale authority. Reconcile cache contents only where values are safe copies; rebuild from authority otherwise.

Exit by evidence. End emergency mode after topology convergence, hot-set residency, backend reserve, survivor headroom, eviction stability, and retry normalization hold for a defined window. Record lost keys, surge shape, stale decisions, dropped work, and recovery time.

The same playbook distinguishes named failure modes:

• Thundering herd: many callers fill the same absent/expired key; signatures are high same-key concurrency and duplicate backend calls.
• Split brain: two owners accept conflicting mutation authority; signatures are overlapping epochs, divergent versions, and reconciliation conflict.
• Stale topology: clients target moved owners; signatures are redirects, refresh storms, extra hops, and old-epoch requests.
• Eviction storm: memory pressure repeatedly removes useful keys; signatures are rising evictions, falling reuse, allocation/transient growth, and backend feedback.

Validate the design in the states that matter

Steady benchmarks are necessary but insufficient. Run campaigns that preserve key and value distributions:

• cold start, warm steady state, and working-set turnover;
• hottest-key and hottest-partition load;
• one-cell loss with real client topology-refresh behavior;
• replica loss, delayed replication, and fenced rejoin;
• synchronized and jittered TTL populations;
• scan/admission pollution and allocator-class pressure;
• rebalance with foreground traffic and rollback;
• compaction/cleanup debt and temporary-space pressure; and
• backend slowdown while cache misses and retries are bounded.

Join client attempt/epoch, partition/key class, server queue/service, hit outcome, value bytes, replica version, eviction/expiry reason, fill identity, and backend trace. Hash or bucket raw keys for privacy and bounded telemetry; retain a controlled hot-key diagnostic path. System-wide hit rate without miss-cost and key-popularity populations can hide the incident you need to predict.

The executable model at examples/performance-engineering-system-design-handbook/part-05/key-value-cache/ reproduces the loss and memory arithmetic. Replace its constants with measured distributions and run sensitivity ranges before using it for capacity.

Applied design and failure exercise

Cache-tier design. Given Atlas’s workload card, choose the key and representation version, authoritative source, TTL/jitter, withdrawal behavior, admission and eviction policy, partition count, replica placement, routing shape, hot-key treatment, per-cell memory, backend reserve, and warm-up method. State which reads may use stale-safe service and which must bypass it. Reject at least one plausible alternative because of a concrete consistency or failure-transfer limit.

Loss estimate. Recompute the playbook for eight cells, a 97.2% hit rate, 320,000 reads per second, a 24,000-request/s backend envelope, and only 40% stale-safe eligibility. Measure or assume a coalescing reduction, label it, and determine the maximum reduction required to remain below 80% of backend capacity. Then state the metric that would falsify the assumption within the first ten seconds.

Storage-backed variant. The same keys become authoritative and must survive a regional restart. Add acknowledgment, tombstone retention, compaction, replica repair, and recovery objectives. Identify which cache playbook actions are now unsafe. Estimate background byte demand and temporary space rather than carrying over the memory-only design.

Durable rules for bounded key access

1. Define key identity, operation mix, value distribution, consistency, and miss cost before choosing a product.
2. Separate disposable cache copies from authoritative key-value state.
3. Treat hashes and virtual nodes as placement tools; measure demand and bytes independently.
4. Version topology, bound refresh, and fence former owners.
5. Match hot-key mitigation to read, write, fill, serialization, or network work.
6. Make replica acknowledgment, read visibility, conflict, and repair explicit.
7. Treat TTL, expiry, invalidation, tombstones, and cleanup as different mechanisms.
8. Pair eviction with admission, and protect the working set from scans and transient allocations.
9. Account for keys, values, metadata, allocator slack, copies, buffers, and headroom.
10. Keep multi-key invariants within one owner or pay explicitly for coordination.
11. Admit rebalancing, warm-up, compaction, and repair as production workloads.
12. Capacity-test bytes, operations, hot partitions, and failure-transferred miss work together.

A key-value system makes bounded access possible by narrowing identity and routing. The next archetype changes the unit from a key request to an unbounded event flow. There, partition keys still determine locality, but lag age, event time, checkpoint state, shuffle, and replay decide whether the result arrives correctly and on time.

Evidence and transfer limits

• Karger et al.’s consistent hashing paper establishes a placement technique that limits remapping under membership change. It does not prove balanced popularity, zero movement, or a complete production membership protocol.
• Amazon’s Dynamo paper and publication record documents a highly available key-value design using partitioning, replication, versioning, and application-assisted reconciliation. Its workload and 2007 implementation choices are evidence for mechanisms, not a default consistency prescription.
• The current Redis Cluster specification gives a concrete slot, redirection, migration, and client-topology contract. Atlas is not Redis, and other systems use different membership, routing, transaction, and failover semantics.
• Redis’s current key eviction documentation distinguishes memory limits and several eviction policies and notes replication/persistence buffers outside dataset accounting. Its policy names and sampling behavior are implementation-specific.
• Redis’s current EXPIRE documentation distinguishes active/passive expiry and describes persistence/replication behavior. Do not generalize its clock or deletion mechanism to another engine.
• Memcached’s performance and memory documentation explains its slab-page/chunk accounting. Atlas’s 1.12 allocator multiplier is modeled teaching input, not a Memcached measurement.
• RocksDB’s official compaction documentation shows how LSM compaction style changes read, write, and space behavior. Storage engines differ; verify the active version, options, device, workload, and recovery state.
• The deterministic fixture at examples/performance-engineering-system-design-handbook/part-05/key-value-cache/ verifies the chapter’s 8,400 steady misses/s, 38,600 displaced hits/s, 47,000 unmitigated requests/s, 12,453 guarded requests/s, hot-key bounds, and memory accounting. It assumes uniform cell traffic, fixed hit rate and item averages, immediate redistribution, independent reduction factors, constant capacity, and no latency feedback. Production decisions require distributions, failure drills, and observed guard effectiveness.