System Design Building Blocks — The Primitives Toolkit: Estimation Discipline, Stampede, Hot-Shard, Consistent Hashing, Bloom & Quorum (Deep Dive)

Every one of these six primitives is the same underlying mechanism repeated: load or membership concentrates on one point unless something spreads it, and a number only earns its keep once it is compared to a limit and forces a decision. A BOTE estimate that never meets a capacity gate is inert. A cache key that all readers hit at once is a stampede. A shard key that clusters traffic on one node is a hot shard. A naive hash table that reshuffles almost everything on resize is the same clustering problem in disguise, solved by a ring. A Bloom filter and a quorum both trade a small, provable error rate for a large space or availability win. This page gives the derived arithmetic for each — the deep pages already own the full mechanism, this is the connective toolkit and the decision layer that ties them together.

1. Estimation → decision discipline

Back-of-envelope arithmetic is not the deliverable — the decision it forces is. A number that dead-ends (“40,000,000 Mbps”, “2,000,000,000 MB/day”) has been computed but not used. The loop that actually earns interview credit has four steps: compute the figure, sanity-check it against something you already know, compare it to a capacity gate (a load-tested per-node/per-shard ceiling), and decide — name the concrete design change the comparison forces.

Worked trace. A service estimates 345,600,000 requests/day. Average QPS = 345,600,000 ÷ 86,400 s = 4,000. Applying a standard 3× diurnal peak multiplier: peak QPS = 12,000. Sanity-check: that is a plausible peak for a mid-size consumer service, not an outlier — good, keep going. Compare to gate: a single shard was load-tested to hold ≈3,000 QPS before p99 latency degrades. 12,000 > 3,000, so one shard cannot carry peak load. Decide: shards needed = 12,000 ÷ 3,000 = 4 shards minimum (add headroom in a real design — this is the floor, not the target).

2. Cache stampede — the arithmetic and the three fixes

A stampede happens because expiry is a single instant: a hot key served at 50,000 req/s with a 60 s TTL sits fine until the clock hits T, at which point every in-flight reader misses simultaneously and hammers the origin together — a ≈50,000× instantaneous load spike on that one key, often enough to take the DB down, after which the cache can never refill (a cascading outage). The deep Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops page derives the full XFetch probability math; here is the toolkit-level summary of the three standard mitigations:

• Single-flight / request coalescing: the first miss takes a per-key lock, fetches once, and populates; every other concurrent reader blocks on that in-flight fetch and shares its result. The origin sees 1 fetch, not 50,000 — but the whole herd pays the recompute latency together.
• Stale-while-revalidate: serve the stale value immediately (zero latency hit for anyone) and refresh asynchronously in the background, bounding origin load to one refresh per key — at the cost of every reader briefly seeing a stale value.
• TTL jitter / probabilistic early recomputation (XFetch): readers refresh early with a probability that rises as expiry nears, so on average exactly one reader refreshes just before T and the herd never forms — no lock, no guaranteed staleness.

Never let a hot key hard-expire with no coalescing — that combination is the single most common cause of a cache-triggered outage.

3. Cache strategy decision rule — tie the strategy to the workload

Four strategies answer two independent questions: on a read miss, who populates the cache? On a write, when does the cache get updated relative to the source of truth?

A fifth pattern, write-around (write DB, bypass the cache entirely), is the right call when written data is rarely re-read soon — logs, cold archival — so the write doesn't pollute the cache with data nobody will fetch; the cost is a guaranteed miss on the first read after a write.

Worked hit-ratio trade-off. With a 1 ms cache hit and an 8 ms DB round trip (so a miss costs 1 ms lookup + 8 ms DB = 9 ms): at 90% hit rate, mean read latency ≈ 0.9×1 ms + 0.1×9 ms ≈ 1.8 ms, and the DB sees only 10% of read QPS. Drop to 50% hit rate and mean latency rises to ≈ 0.5×1 + 0.5×9 = 5 ms — a ≈2.8× latency increase — and DB load rises 5×. Hit ratio, not raw cache speed, is the number that actually determines DB load and user-visible latency; that's what to defend under review, not the cache engine's per-op microbenchmark.

4. Hot shard — a quantified example and the shard-key rule

Shard users by user_id % 4. If one celebrity account draws 40% of all read traffic, its shard sees ≈ 0.40 + 0.60⁄4 = 0.55 of total load, while the other three shards split the remaining 0.45 ≈ 0.15 each — one node at 55%, three sitting near-idle at 15%. Because the fleet can only be driven as hard as its busiest node allows, the whole fleet's usable capacity is capped at roughly 1 ⁄ (4×0.55) ≈ 45% of what it could handle if load were even across all four shards — more than half the provisioned capacity sits idle.

Shard-key selection rule. Choose a key that is (a) high-cardinality (many distinct values, so no single value dominates) and (b) evenly accessed (no value is disproportionately hot). Never shard on a monotonic key (timestamp, auto-increment id) — every new write lands on the newest shard, a hot spot that moves but never leaves.

Remedies once you have a hot key:

• Hash the key (e.g. md5(user_id)) so sequential and celebrity ids scatter across shards — but a single very hot key still maps to exactly one shard, so this alone does not fix a true hotspot.
• Split the hot key: write to sub-keys user_id:{0..9}, spreading that one key's load 10× across ten physical locations, then scatter-gather on read (query all ten, merge the results).
• Front the hot key with a cache so the shard sees one refresh per TTL rather than the full flood — this is the hot-shard analogue of the stampede fix in §2.

See the deep Data Partitioning — Fan-out Stragglers, Salting Read Cost & Vertical-Split Hazards page for the salting/fan-out cost trade-off in full.

5. Consistent hashing — the remap arithmetic, derived

Plain hash(key) % n ties every key's owner to the divisor n. Scaling 4→5 shards changes that divisor for every key, so ≈ (n−1)⁄n = 4⁄5 = 80% of all keys must physically move — during which the cluster is degraded and every cache is cold (a thundering herd onto the origin at exactly the moment you added capacity to relieve one). Consistent hashing fixes this by placing nodes on a hash ring: a key belongs to the first node reached going clockwise from its hash position. Inserting a new node only steals the arc between it and its predecessor — nobody else's ownership changes.

Keys-move trace (traced worked example). Ring with nodes A(90°), B(180°), C(270°), D(360°/0°), owning the arcs immediately behind them. Insert D’ at 330°, between C and D. Five sample keys: K1(45°)→A, K2(130°)→B, K3(240°)→C — all three unaffected, since none falls in D's shrinking arc. K5(350°) was owned by D and still is, since 350° > 330°. Only K4(300°) — previously owned by D — now falls in the new arc (C, D’] and moves to D’. Going from 4 nodes to 5, exactly 1 of the 5 sample keys moved: ≈ 1⁄5 = 20%, matching the general result that a ring remaps ≈ 1⁄n of the keyspace on a node change — not (n−1)⁄n like modulo.

Virtual nodes — why they exist (the load-variance argument)

With one token per physical node, arc lengths on the ring are random and uneven — the busiest node can end up owning ≈ ln(n)⁄n of the ring, 2–3× the average, i.e. a hot node purely from bad luck in the placement. Give each physical node V virtual nodes (tokens) scattered around the ring instead of one, and the per-node load concentrates around the mean with spread shrinking ≈ 1⁄√V. At V=256 (Cassandra's pre-4.0 default num_tokens; Cassandra 4.0+ ships num_tokens=16 with an improved token-allocation algorithm), the hottest physical node sits within a few percent of the average, and when a node is decommissioned its load is absorbed in parallel by many other nodes rather than dumped on one successor. That variance reduction — not a hand-wave “spreads load more evenly” — is the real reason vnodes exist. Full mechanism, rendezvous-hashing comparison and the SPOF trade-off of directory-based partitioning live on the deep What Is the Difference Between Rendezvous Hashing and Consistent Hashing page.

6. Bloom filter — the derived formula and a concrete sizing

With m bits, n inserted items, and k independent hash functions: after n inserts, P(a given bit is still 0) = (1 − 1⁄m)^kn ≈ e^−kn⁄m. A false positive requires all k queried bits to be set, so:

FP ≈ (1 − e−kn⁄m)k

Minimizing FP over k gives the optimal hash count k = (m⁄n)·ln 2 (which sets roughly half the bits to 1), and at that optimum FP ≈ (1⁄2)^k = 2^{−(m⁄n)ln2}. The practical rule of thumb: ≈ 9.6 bits/item, k=7 → ≈1% FP; ≈ 14.4 bits/item, k=10 → ≈0.1%; every extra ≈4.8 bits/item cuts the false-positive rate roughly 10×.

Worked sizing. 1,000,000 URLs at a 1% false-positive target → m ≈ 9.6 × 1,000,000 = 9.6 million bits ≈ 1.2 MB, with k=7 hash functions — versus tens of megabytes to store the raw strings in a hash set. That 1.2 MB comfortably fits in RAM/L3 cache, which is the whole point: the filter screens out the ≈99% of definitely-absent keys before a costly disk seek or RPC, at the price of occasionally doing one wasted lookup. The full derivation, concurrency caveats, and adversarial false-positive-rate analysis live on the deep Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR page.

7. Quorum — the majority-overlap proof and a partition trace

With N replicas, a write acknowledged by W and a read consulting R: if R + W > N, the read set and the write set must share at least one node (pigeonhole principle — two subsets of an N-element set that are each larger than N⁄2 cannot be disjoint), so every read is guaranteed to see the latest acknowledged write.

The same inequality, using a plain majority (⌊N⁄2⌋+1 for both R and W), is exactly what stops split-brain: any two subsets each larger than N⁄2 must overlap, so two network partitions can never each independently assemble a majority for conflicting decisions.

Partition trace, N=5 split 3|2. The 3-node side reaches quorum (3 ≥ 3) and keeps electing a leader and committing writes. The 2-node side cannot (2 < 3) and correctly refuses to serve — so no two leaders ever exist simultaneously. This is why odd N is preferred: N=5 tolerates 2 failures, but N=4 also needs 3 for a majority and tolerates only 1 failure — the 4th node buys zero extra fault tolerance over N=3. It is also why (R=1, W=N) — write-all, read-one — is fragile in production: a single down replica blocks every write. See the deep Quorum Arithmetic — Why R + W > N page for read-repair, sloppy-quorum, and hinted-handoff on top of this base proof.

Pitfalls

• Estimating without deciding. A page (or an interview answer) that stops at a raw number — “12,000 QPS”, “40,000,000 Mbps” — has computed but not decided anything. Always close the loop: compare to a gate, name the shard/replica/cache-tier count it forces.
• Hard TTL expiry with no coalescing on a hot key. The single most common cache-triggered outage: N concurrent misses become N origin hits at the exact same instant.
• Sharding on a monotonic key (timestamp, auto-increment id). It looks evenly distributed in aggregate but every new write lands on the single newest shard — a hot spot that never leaves.
• Treating hash % n as "good enough" hashing at scale. It works until the first resize, at which point ≈ (n−1)⁄n of keys move at once — precisely when the cluster can least afford a cold-cache thundering herd.
• Sizing a Bloom filter for average n instead of peak n. The FP rate is derived assuming n items are inserted into m bits; overfilling past the design n drives the real false-positive rate far above the target because more bits than planned end up set.
• Assuming R + W > N alone gives full consistency. It guarantees the read and write sets overlap, not that the overlapping replica's value is correctly identified as the latest — you still need versioning/timestamps (or vector clocks) to pick the right value out of an overlapping quorum.

Judgment layer

Cache strategy, by workload: reads must never lag writes and write volume is modest → write-through. Write-heavy and loss-tolerant → write-back. Written data is rarely re-read soon → write-around. Default, cache-outage-safe read path → cache-aside; only reach for read-through to centralize fetch logic in the cache layer itself. Anti-stampede choice follows the same logic as cache strategy: cheap recompute and exactness required → single-flight; brief staleness tolerable and latency is critical → stale-while-revalidate; expensive hot key where neither blocking nor staleness is acceptable → XFetch.

Bloom filter vs named alternatives: choose a Bloom filter when a definite-no is cheap to cache and a rare false-yes only costs one wasted lookup — SSTable/LSM read avoidance (RocksDB, Cassandra, HBase skip a disk seek when the filter says absent), CDN one-hit-wonder filters, dedup pre-checks. Prefer a plain hash set when you need exact membership, must enumerate members, or the set is small enough to fit anyway — a Bloom filter never returns the actual value, only maybe/no. Prefer a counting Bloom filter or a cuckoo filter when you must support deletion — a standard Bloom filter cannot delete, since clearing a bit could corrupt another item's membership; a cuckoo filter additionally gives a lower FP rate at similar space and supports delete, at the cost of a more complex (occasionally-relocating) insert. Do not use a Bloom filter where a false positive is dangerous rather than merely wasteful (e.g. gating a hard security block) or where you need the value back, not just a maybe/no answer.

Takeaways

• An estimate is only as useful as the decision it forces — always run compute → sanity-check → compare-to-gate → decide, and name the concrete design change at the end.
• Stampede and hot-shard are the same failure shape at different scopes (one key vs one node): both are fixed by spreading the load (coalescing/jitter, or splitting/scattering) rather than hoping traffic stays even.
• Consistent hashing's entire value is remapping ≈1/n of keys instead of ≈(n−1)/n on a node change — and vnodes exist to fix the load-variance that a single token per node introduces.
• Bloom filters and quorums both trade a small, precisely derivable error/availability budget (FP rate; the side without a majority) for a large space or availability win — know the formula, not just the name.

Related pages

• Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops (Deep Dive) — the full XFetch probability derivation behind the stampede-fix summary in §2.
• Data Partitioning — Fan-out Stragglers, Salting Read Cost & Vertical-Split Hazards (Deep Dive) — the salting/scatter-gather cost trade-off behind the hot-shard remedies in §4.
• Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive) — concurrency caveats and adversarial false-positive analysis beyond the sizing formula in §6.
• Quorum in Practice — The Two Inequalities, Conflict Resolution, Read-Repair, Partitions & Tail Latency (Deep Dive) — read-repair, sloppy-quorum, and hinted-handoff on top of the R+W>N proof in §7.
• What Is the Difference Between Rendezvous Hashing and Consistent Hashing, and When Should I Use Each — the alternative to vnodes for the same load-variance problem.

Re-authored/Deepened for this guide.