Probability for System Design
You do not need a math degree to design reliable systems, but you do need enough probability to answer questions like: "How likely is a UUID collision in our database?" or "How many samples do we need before our cache is warm?" or "What is the false positive rate of our Bloom filter?" This page covers the probability concepts that show up repeatedly in system design interviews and real engineering decisions.
Probability is the language of everything that goes wrong sometimes: a disk that dies once every few years, a request that is slow one time in a hundred, an alert that fires when nothing is broken, two random IDs that happen to match. Systems at scale turn "sometimes" into "every day". A failure with a one-in-a-million chance per request happens about 86 times a day at 1,000 requests per second. Being able to put a number on "sometimes" is what lets you decide whether to add a replica, a retry, a check, or nothing at all.
Every concept below follows the same shape: intuition first, then the formula, then a worked numeric example, then where it shows up in real systems. The Python snippets are self-contained and runnable; the outputs printed in comments come from actually running them.
flowchart TD
F["Foundations: sample spaces, conditional probability, Bayes"] --> I["Independence and correlated failures"]
I --> RV["Random variables, expectation, variance"]
RV --> D["Distributions: Bernoulli to Pareto"]
D --> C["Collisions and coverage: birthday, coupon collector"]
RV --> B["Tail bounds: union, Markov, Chebyshev, Chernoff"]
D --> R["Reliability: nines, quorums, fan-out tail latency"]
C --> S["Sketches: reservoir sampling, Bloom filters"]
R --> MC["Monte Carlo when the algebra gets hard"]
B --> MC
Foundations: Sample Spaces and Events
Intuition
Before you can say "the probability of X", you need to be precise about what could happen. The sample space is the set of all possible outcomes of an experiment. An event is a subset of outcomes you care about. A probability assigns each event a number between 0 and 1 such that the whole sample space has probability 1 and disjoint events add up.
Most engineering mistakes in probability are sample-space mistakes: treating outcomes as equally likely when they are not, or forgetting some.
The Rules
For events and :
The complement rule is the single most useful trick in engineering probability. "At least one of things fails" is hard to count directly; "none of them fail" is easy. So:
Worked Example
You deploy to 3 servers. Each deploy independently fails with probability 0.02. What is the chance at least one fails?
Counting directly means adding 7 cases. With the complement:
About 5.9%, nearly three times the single-server rate. For small , ; that approximation breaks down as approaches 1, which is where fan-out gets painful.
Engineering Application
For a rollout the sample space is every combination of healthy and unhealthy hosts; for a hash scheme, every assignment of keys to buckets. Writing it down is how you catch the assumption that every shard is equally likely to be hit when 5% of keys get 50% of traffic.
Conditional Probability and Bayes' Theorem
Intuition
Conditional probability answers: given that I already know happened, how likely is ? Knowing shrinks the sample space to only those outcomes where is true, and we re-measure inside that smaller world.
Bayes' theorem lets you flip a conditional around. You usually know (how often does the alert fire when the database really is down?), but you want (the alert fired, is the database really down?).
The denominator is the law of total probability: the evidence can happen either because the hypothesis is true or because it is false, and we add both routes.
The Base-Rate Fallacy: Why Your Alerts Are Mostly Wrong
Here is the most important applied Bayes example for an on-call engineer.
You have an anomaly detector checking a service every 5 minutes. Real incidents are rare: one 5-minute window in 1,000 contains a real problem, so . The detector is good:
- Sensitivity (true positive rate): when there is an incident, it fires 99% of the time. .
- False positive rate: when everything is fine, it fires only 2% of the time. .
The alert fires. What is the probability there is actually an incident?
Under 5%. Nineteen out of twenty pages are false alarms, even though the detector is "99% accurate". The reason is the base rate: healthy windows outnumber incident windows 999 to 1, so even a small false-positive rate applied to that huge pool swamps the true positives.
Counting makes it concrete. There are 288 five-minute windows in a day. Per day you expect true alerts and false ones. Your on-call engineer is woken up about six times a day and is right to ignore most of them, which is exactly how real incidents get ignored too.
flowchart TD
W["100,000 five-minute windows"] --> INC["100 real incidents"]
W --> OK["99,900 healthy windows"]
INC --> TP["99 alerts (true positives)"]
INC --> FN["1 missed (false negative)"]
OK --> FP["1,998 alerts (false positives)"]
OK --> TN["97,902 quiet (true negatives)"]
TP --> R["Of 2,097 alerts, only 99 are real: 4.7%"]
FP --> R
What actually helps:
| Change | New | Why |
|---|---|---|
| Baseline (prior 0.1%, FPR 2%) | 4.7% | Base rate dominates |
| Cut FPR to 0.1% | 49.8% | False positives were the problem, not sensitivity |
| Raise sensitivity to 100% | 4.7% | Barely moves: you were already catching incidents |
| Alert only when 2 independent signals agree | 71.0% | Second signal updates the 4.7% prior again |
| Higher base rate (flaky service, prior 1%) | 33.3% | Same detector, more real incidents |
The two-signal row applies Bayes twice: the 4.7% posterior becomes the prior for the second, independent check. That is why good alerting uses user-facing symptoms (error rate, SLO burn) with confirmation windows rather than single noisy causes. Sensitivity barely matters; the false-positive rate on the huge healthy population is what you must drive down.
def posterior(prior: float, tpr: float, fpr: float) -> float:
"""P(incident | alert) via Bayes' theorem."""
evidence = tpr * prior + fpr * (1 - prior)
return tpr * prior / evidence
p1 = posterior(prior=0.001, tpr=0.99, fpr=0.02)
print(f"one alert: {p1:.1%}")
print(f"FPR cut to 0.1%: {posterior(0.001, 0.99, 0.001):.1%}")
print(f"two independent alerts: {posterior(p1, 0.99, 0.02):.1%}")
# one alert: 4.7%
# FPR cut to 0.1%: 49.8%
# two independent alerts: 71.0%
The same math, everywhere
Fraud detection, intrusion alerts and flaky-test detection all hunt for rare things. Always ask: how many false positives does the healthy majority generate?
Independence, and Why "Independent" Failures Aren't
Intuition
Two events are independent if knowing one tells you nothing about the other:
Independence is what lets you multiply. It is also the assumption that is most often silently false in real systems.
The Replica Calculation Everyone Does
Each of 3 replicas is down 1% of the time. If failures are independent, the chance all three are down at once is:
One in a million: six nines of "at least one replica is up". It looks wonderful.
Why It Is Wrong
Replicas share a rack, a switch, a zone, a kernel version, a config push, a certificate expiry, and the same bug triggered by the same poison request. When the shared thing fails, they fail together.
A standard way to model this is the common-cause (or "beta-factor") model: with probability some shared cause takes out every replica at once; otherwise replicas fail independently.
Worked Example
Same 3 replicas at , but add a shared cause (a bad config push, an AZ outage) that is active 0.1% of the time, :
That is 1,000 times worse than the independent estimate, dominated entirely by . More replicas in the same failure domain do nothing; only reducing helps: separate racks, zones and regions, and staggered deploys.
flowchart LR
subgraph AZ1["Same zone: correlated"]
A1["Replica 1"]
A2["Replica 2"]
A3["Replica 3"]
end
PWR["Shared power, switch, config push"] --> A1
PWR --> A2
PWR --> A3
subgraph SPREAD["Spread across zones: closer to independent"]
B1["Replica 1 in zone a"]
B2["Replica 2 in zone b"]
B3["Replica 3 in zone c"]
end
Engineering Application
- Placement: Cassandra's
NetworkTopologyStrategy, Kubernetes topology spread constraints and HDFS rack awareness exist to shrink . - Deploys: canaries and staged rollouts stop one bad push from hitting every replica.
- Disks: same-batch drives tend to fail close together, and RAID rebuilds stress the survivors exactly when you need them.
- Retries: overload failures are correlated with the next attempt failing, so independent retry math is optimistic.
Correlation is the default
Treat independence as a claim that must be justified by separate failure domains, not as a default. When a design review says "three replicas, so 10^-6", ask: what single event takes out all three?
Random Variables, Expectation and Variance
Intuition
A random variable is a number attached to each outcome: the latency of a request, the number of failed disks this month, the number of keys that land in bucket 7. Its expectation is the long-run average: weight each value by its probability and add. Its variance measures how far values typically stray from that average.
The standard deviation is in the same units as , which makes it the easier one to reason about.
Worked Example
A cache lookup takes 1 ms on a hit (probability 0.9) and 50 ms on a miss (probability 0.1).
The mean is 5.9 ms, a number no single request ever takes. The standard deviation is 2.5 times the mean. This is the first hint of why averages are a poor summary of latency, a theme the A/B testing page picks up with percentiles.
Linearity of Expectation: The Most Useful Trick
This holds whether or not the are independent. That makes it astonishingly powerful: break a complicated count into a sum of 0/1 indicator variables, compute each one's expectation (which is just a probability), and add.
Trick 1: Expected Number of Hash Collisions
Hash keys uniformly into buckets. How many colliding pairs do you expect?
There are pairs. For each pair, let if they collide. . By linearity:
Worked: 1 million keys with a 32-bit hash ():
You expect about 116 colliding pairs. If your code uses a 32-bit hash as a unique key (a common shortcut for deduplication or "fingerprints"), you will silently merge about 116 pairs of distinct records. Notice how simple that was compared with computing the probability of at least one collision, which we do properly in the birthday section.
Trick 2: Expected Empty Buckets
Throw keys into buckets. Each bucket is empty with probability . By linearity, about 36.8% of buckets are empty, and therefore the other 63.2% hold all the keys. This is why a hash table at load factor 1 has long chains in some buckets, and why random load balancing leaves some servers idle while others queue.
Variance of Sums
Variance is not linear in general:
For independent variables the covariance is zero, so the sum of copies has mean but standard deviation only : relative noise shrinks like . That is why big services see smoother traffic than small ones, and why correlated users (everyone opening the app at a cup final) break the rule. Correlation does not change the mean of a retry storm, only how bunched up it is.
Distributions an Engineer Meets
A distribution is a recipe for how probability is spread over values. You do not need dozens. Six or seven cover nearly every systems question.
flowchart TD
BER["Bernoulli: one trial succeeds or fails"] --> BIN["Binomial: successes in n trials"]
BER --> GEO["Geometric: trials until first success"]
BIN -->|"n large, p small"| POI["Poisson: count of rare events"]
POI -->|"time between events"| EXP["Exponential: inter-arrival time"]
BIN -->|"n large"| NORM["Normal: sums of many small effects"]
NORM -->|"multiply instead of add"| LOGN["Log-normal: latency, file sizes"]
LOGN --> HEAVY["Heavy tails: Pareto, power laws"]
Bernoulli and Binomial: Counting Failures
Intuition. A Bernoulli trial is one coin flip: success with probability . The binomial counts successes (or failures) in independent flips.
Worked example. A cluster has 1,000 disks; each fails in a given month with probability 0.01. Expected failures: . Standard deviation: . The chance of 20 or more failures in one month is about 0.33%, and of 30 or more about (computed exactly below).
Engineering application. Spare-capacity planning ("how many spare disks should be on the shelf?"), replica placement ("what is the chance 2 of my 3 replicas are on failed disks?"), and quorum survival all start here.
from scipy import stats
n, p = 1000, 0.01
X = stats.binom(n, p)
print(f"mean={X.mean():.1f} sd={X.std():.2f}")
print(f"P(X >= 20) = {X.sf(19):.4f}")
print(f"P(X >= 30) = {X.sf(29):.2e}")
# keep enough spares to cover the 99.9th percentile month
print(f"spares for 99.9% of months: {int(X.ppf(0.999))}")
# mean=10.0 sd=3.15
# P(X >= 20) = 0.0033
# P(X >= 30) = 2.06e-07
# spares for 99.9% of months: 21
Geometric: Retries Until Success
Intuition. Keep trying until something works. If each attempt succeeds with probability independently, the number of attempts is geometric.
Worked example. A flaky downstream call succeeds 90% of the time. Expected attempts: . Probability you need more than 3 attempts: . So "retry up to 3 times" turns a 10% failure rate into a 0.1% failure rate, if failures are independent.
Now flip it around and look at load. With at most 3 attempts and per-attempt failure rate , the expected attempts per request are :
| Per-attempt failure | Expected attempts (max 3) | Load on downstream |
|---|---|---|
| 0.1 (mostly healthy) | 1.11 | +11% |
| 0.5 (struggling) | 1.75 | +75% |
| 0.9 (overloaded) | 2.71 | +171% |
The retry policy nearly triples the load on a service at exactly the moment it is overloaded, and overload failures are correlated (the next attempt is likely to fail too), so the independent-retry benefit evaporates while the cost remains. This is the arithmetic behind retry budgets, exponential backoff with jitter and circuit breakers; see Timeouts, Retries and Backoff and Circuit Breaker.
Retry amplification compounds across layers
If three layers each retry 3 times, a failing leaf can see up to attempts per user request. Retry at one layer (usually the one closest to the user that can make the call idempotent), and give every other layer zero retries or a shared budget.
Poisson: Arrivals
Intuition. Many users acting independently, each rarely sending a request, produce a total count per second that is Poisson. It is the binomial in the limit of many trials with a tiny per-trial probability, with held fixed.
Mean equals variance, so the standard deviation is . At 1,000 requests per second the typical per-second wobble is only about .
Worked example. A queue consumer sees on average 5 jobs per second. Probability of a second with 10 or more jobs: about 3.2%. Probability of a completely idle second: . If the consumer can only handle 9 per second, about 3% of seconds will build a backlog even though the average load is only 56% of capacity. That is the first glimpse of why queues form at utilizations well below 100%; Queueing Theory takes it the rest of the way.
Engineering application. Poisson is the default model for request arrivals, page faults, cosmic-ray bit flips, and independent hardware failures across a fleet. It is wrong whenever arrivals are correlated: retries, cron jobs firing on the minute, push notifications sent to everyone at once, and diurnal traffic (the rate itself changes over the day).
Expected Value for Capacity Planning
The Concept
Expected value E[X] is the long-run average outcome. For capacity planning, you need both the expected value and the variance — a system that handles the average but not the peaks will fail.
Application: Request Rate Planning
Correction (2026-11-09)
The original version of this snippet computed lam ** k * math.exp(-lam) / math.factorial(k) directly. At lam = 1000 that overflows (OverflowError: int too large to convert to float) before it returns anything. The version below computes the same Poisson probability in log space, so it runs and prints the value the comment always claimed.
# Poisson process — models random arrivals (web requests)
import math
def poisson_probability(lam: float, k: int) -> float:
"""P(X = k) where X ~ Poisson(lambda), computed in log space to avoid overflow."""
return math.exp(k * math.log(lam) - lam - math.lgamma(k + 1))
def poisson_capacity(avg_rps: float, target_percentile: float = 0.999) -> int:
"""Find the request rate we should provision for."""
cumulative = 0
for k in range(int(avg_rps * 3)):
cumulative += poisson_probability(avg_rps, k)
if cumulative >= target_percentile:
return k
return int(avg_rps * 3)
avg_rps = 1000
p99_9 = poisson_capacity(avg_rps, 0.999)
print(f"Average: {avg_rps} RPS → Provision for: {p99_9} RPS (p99.9)")
# Average: 1000 RPS → Provision for: 1099 RPS (p99.9)
That 10% headroom is per-second Poisson noise only. Daily peaks are commonly 2–5 times the average, and retry or batch bursts exceed Poisson by far. Add Poisson headroom on top of a measured peak, never instead of it.
Application: Queue Wait Times (Little's Law)
Little's Law relates the average number of items in a system to the arrival rate and average time in the system:
L = λ × W
Where:
L = average number of items in the system
λ = average arrival rate
W = average time an item spends in the system
graph LR
ARR["Arrivals<br/>λ = 100 req/sec"] --> SYS["System<br/>L = 50 requests<br/>in-flight"]
SYS --> DEP["Departures"]
SYS --- LIT["Little's Law:<br/>L = λ × W<br/>50 = 100 × 0.5s<br/>Average wait = 500ms"]
style SYS fill:#d97706,color:#fff
Interview Application
If an interviewer says "We have 100 requests per second and each takes 500ms to process," apply Little's Law: you have 50 concurrent requests on average. You need enough worker threads/processes/pods to handle 50 concurrent requests — plus headroom for variance.
Little's Law holds for any arrival and service distribution in a stable system. Why latency explodes near 100% utilization is covered on Queueing Theory.
Exponential: Time Between Events, and Memorylessness
Intuition. If arrivals are Poisson with rate , the gap between consecutive arrivals is exponential with the same rate.
Its defining property is memorylessness:
Having waited already tells you nothing about how much longer you will wait. An exponential light bulb that has burned for 1,000 hours is as good as new.
Worked example. At 1,000 requests per second the mean gap is 1 ms. The chance of a gap longer than 1 ms is ; longer than 5 ms is . Arrivals are clumpy: lots of short gaps and occasional long ones, even though the rate is perfectly steady.
Engineering application. Constant-rate random failures (the flat middle of the hardware "bathtub curve") are exponential, which is what makes MTBF a meaningful single number; infant mortality and wear-out are not memoryless. Real latency tails are worse than memoryless (a request already at 2 seconds is probably stuck), which argues for timeouts plus hedged requests over very long timeouts. In simulations, generate Poisson arrivals by summing random.expovariate(rate) gaps.
Normal: Sums of Many Small Effects
Intuition. Add up many independent, modest-sized random effects and the result is approximately normal, the bell curve, regardless of what each piece looked like. That is the central limit theorem, covered properly on the A/B testing page.
The rule to memorise: about 68.3% of values lie within of the mean, 95.4% within , 99.7% within . The 99th percentile is .
Worked example. 10 million independent users, each averaging 20 requests a day with standard deviation 30, produce a daily total that is approximately normal with mean and standard deviation : under 0.05% relative noise. Bigger day-to-day swings are real changes, not chance.
Engineering application. Aggregate traffic and sample means in experiments. Not latency, which is skewed right with a long tail; "mean plus 3 sigma" badly underestimates it.
Heavy Tails: Pareto and Log-Normal
Intuition. In a heavy-tailed distribution, extreme values are not just possible but common enough to dominate totals. A few huge files take most of the disk; a few slow requests dominate the tail; a few hot keys get most of the traffic; a few customers generate most of the load.
Log-normal. If is normal, is log-normal. It arises from multiplying many independent factors (each stage of a request slows it by some random percentage). Latencies and file sizes are often roughly log-normal in the body.
Pareto (power law). The tail decays polynomially instead of exponentially:
As drops toward 1, the mean blows up: with , the mean is 1.5 at , 2 at , 3 at and 11 at . For the variance is infinite, so sample averages never settle down. The famous "80/20 rule" corresponds to : the top 20% of items hold 80% of the total.
Worked example (log-normal latency). Suppose service latency is log-normal with median 20 ms and (in log space).
| Statistic | Value |
|---|---|
| Median (p50) | 20 ms |
| Mean | ms |
| p99 | ms |
| p99.9 | ms |
The mean is 65% above the median, and p99 is ten times the median. A dashboard showing "average 33 ms" describes neither the typical request (20 ms) nor the bad ones (200+ ms).
Engineering application.
- Latency: report percentiles, and merge histograms rather than averaging percentiles across hosts.
- Storage: a few files dominate bytes while many small ones dominate inode count; design for both.
- Sharding: Zipf-distributed key popularity produces hot partitions; see Math Patterns in System Design.
- Capacity: one giant customer import can exceed a month of normal traffic, so last week's mean predicts poorly.
Birthday Paradox
The Concept
The birthday paradox states that in a group of just 23 people, there is a greater than 50% chance that two people share a birthday. This is counterintuitive because there are 365 possible birthdays, but collisions happen far sooner than you expect.
The intuition: what grows is not the number of people but the number of pairs. 23 people form pairs, and each pair has a 1-in-365 chance to match. You are not asking "does anyone share my birthday" (that needs about 253 people) but "does any pair match".
The general formula for collision probability with n items and d possible values:
P(collision) ≈ 1 - e^(-n² / 2d)
For a 50% collision probability:
n ≈ 1.177 × √d
Where the Formula Comes From
The probability that all items are distinct is a product: the second avoids the first, the third avoids the first two, and so on.
using for small . So
Setting the probability to gives . The small-probability form is the expected number of colliding pairs from the linearity section, and is the one to use for "is this safe?" questions.
Application: Hash Collisions
If you are using a hash function with b bits, the number of items before a 50% collision probability is approximately 2^(b/2).
Correction (2026-11-09)
The 128-bit row previously said "~18 quintillion", which is without the 1.177 factor, and it labelled the row "UUID v4" although UUID v4 has only 122 random bits (6 bits are fixed version and variant). The table now gives the full-128-bit figure, about , and a separate UUID v4 row, about , which matches the "about 2 quintillion" order of magnitude in the tip below. The other rows already include the 1.177 factor and are unchanged.
| Hash Size | Possible Values | 50% Collision At | Use Case |
|---|---|---|---|
| 32-bit | 4.3 × 10^9 | ~77,000 items | Small internal lookup |
| 64-bit | 1.8 × 10^19 | ~5 billion items | Session IDs (borderline) |
| 122-bit (UUID v4 random bits) | 5.3 × 10^36 | ~2.7 quintillion (2.7 × 10^18) | Database primary keys |
| 128-bit (fully random) | 3.4 × 10^38 | ~22 quintillion (2.2 × 10^19) | Random 128-bit tokens |
| 256-bit (SHA-256) | 1.2 × 10^77 | ~4 × 10^38 | Cryptographic use |
Correction (2026-11-09)
1 - math.exp(-x) for rounds to exactly 0 in double precision, so the original snippet printed 0.00e+00, not the 9.4e-20 in its comment. Using -math.expm1(-x), which computes accurately for tiny , fixes it. The comment's value was right; the code was not.
import math
def birthday_collision_prob(n: int, d: int) -> float:
"""Probability of at least one collision among n items with d possible values."""
# expm1 keeps precision when the probability is tiny; 1 - exp(-x) rounds to 0.0
return -math.expm1(-n * (n - 1) / (2 * d))
# UUID v4 has 122 random bits
uuid_space = 2**122
n_uuids = 1_000_000_000 # 1 billion UUIDs
prob = birthday_collision_prob(n_uuids, uuid_space)
print(f"P(collision with {n_uuids:,} UUIDs): {prob:.2e}")
# P(collision with 1,000,000,000 UUIDs): 9.40e-20
# Essentially zero — UUIDs are safe at scale
System Design Interview Pattern
When an interviewer asks "Will we have collisions with this ID scheme?", use the birthday paradox formula. If the hash space is 2^b bits, you need roughly 2^(b/2) items before collisions become likely. For 128-bit UUIDs, that is 2^61 — about 2 quintillion — so you are safe.
(The 2^61 in the tip is , the UUID v4 figure; the 1.177 factor takes it to the 2.7 quintillion in the table.)
The UUID Math, Properly
How many random UUID v4s can you generate before the collision probability reaches one in a billion? Invert :
About 103 trillion UUIDs. Real-world UUID collisions come from bad randomness (cloned VM RNG state, seeded PRNGs), not the birthday bound; use the OS CSPRNG and the math holds.
- UUID v7 (RFC 9562) puts a 48-bit millisecond timestamp first and keeps up to 74 random bits, so collisions can only happen within one millisecond: a million IDs in the same millisecond gives . Safe, and time-sorted, which B-tree indexes like.
- Truncated hashes lose this fast: 8 hex characters of a SHA-256 is 32 bits, 50% collision risk at about 77,000 items.
The Short-URL Math
A URL shortener with 7-character base-62 codes (a–z, A–Z, 0–9) has possible codes. That sounds like plenty for a service storing a billion links. The birthday bound disagrees:
With randomly generated codes, you reach a coin-flip chance of some collision after only 2.2 million links, and a 1% chance after about 266,000. By 100 million links you expect about colliding pairs.
The fix is not a bigger alphabet. It is to check for collisions and retry, which is cheap because the relevant number for a new insert is different: the chance that one new random code hits one of the existing codes is . At a billion stored links that is per insert, so the expected number of retries per insert is negligible.
| Scheme | Space | 50% birthday point | Per-insert collision at 1B stored |
|---|---|---|---|
| 6 chars base-62 | ~281,000 | 1.8% | |
| 7 chars base-62 | ~2.2 million | 0.028% | |
| 8 chars base-62 | ~17 million | 0.00046% | |
| Counter + base-62 encode | none | never | 0% (but guessable) |
Alternatives that avoid collisions entirely: a global counter (or ranges of counters handed to each server) encoded in base 62, possibly passed through a reversible permutation so codes are not sequential. See Hash Tables for collision handling inside data structures.
Application: Sharding and Load Balancing
The birthday paradox also explains hot spots. If you randomly assign n requests to k servers:
Correction (2026-11-09)
The original comment said the formula gives "~10,960 — the hottest server gets ~10% more than average". Running the code gives about 10,303: roughly 3% above the average of 10,000. The formula is the standard "balls into bins" estimate for the heavily loaded case . Strictly this is a concentration result rather than the birthday paradox itself, but it is the same "randomness clumps" intuition.
def expected_max_load(n: int, k: int) -> float:
"""Approximate max load on any server when n items are distributed to k buckets."""
import math
# For large n, max load ≈ n/k + sqrt(2 * n/k * ln(k))
avg = n / k
return avg + math.sqrt(2 * avg * math.log(k))
# 1M requests, 100 servers
print(f"Expected max load: {expected_max_load(1_000_000, 100):.0f}")
# ~10,303 — the hottest server gets ~3% more than average
Imbalance grows as load per server shrinks: 10,000 requests on 100 servers gives a max of about 130 (30% hot), and 100 requests on 100 servers leaves 37% of servers empty. For few, large jobs use "power of two choices" (pick two random servers, use the less loaded), which cuts the maximum from about to about . See Load Balancing Algorithms.
Coupon Collector Problem
The Concept
If there are n distinct coupons and you collect them randomly (with replacement), on average you need n × H(n) draws to collect all of them, where H(n) is the harmonic number ≈ ln(n) + 0.577.
E[draws] = n × (1/1 + 1/2 + 1/3 + ... + 1/n) ≈ n × ln(n) + 0.577n
Why. This is linearity of expectation again. Split the process into phases: phase starts when you have distinct coupons. Each draw is new with probability , so the phase length is geometric with mean . Add the phases:
The first coupons come almost free; the last one alone takes draws on average. The tail is also wide: the standard deviation is about , so for the full collection takes draws.
graph LR
subgraph "Coupon Collector"
CC1["n = 10<br/>E ≈ 29 draws"] --> CC2["n = 100<br/>E ≈ 519 draws"]
CC2 --> CC3["n = 1000<br/>E ≈ 7,485 draws"]
CC3 --> CC4["n = 10000<br/>E ≈ 97,876 draws"]
end
Application: Cache Warming
If your cache has n distinct keys accessed uniformly at random, the coupon collector tells you how many requests you need before the cache is fully warm (all keys loaded).
Correction (2026-11-09)
The third call below was meant to show 95% coverage, but it omitted the coverage argument and silently reused the 99% default, so it printed the same 46,051 as the line above. It now passes coverage=0.95, which gives 29,957: reaching 95% costs about 35% fewer requests than reaching 99%.
import math
def cache_warming_requests(n_keys: int, coverage: float = 0.99) -> int:
"""Estimate requests needed to cover `coverage` fraction of `n_keys` distinct cache keys."""
# For partial coverage: E[requests for k out of n] ≈ n * ln(n / (n-k))
k = int(n_keys * coverage)
return int(n_keys * math.log(n_keys / (n_keys - k)))
print(f"100 keys, 99% coverage: {cache_warming_requests(100):,} requests")
# 460 requests
print(f"10,000 keys, 99% coverage: {cache_warming_requests(10000):,} requests")
# 46,051 requests
print(f"10,000 keys, 95% coverage: {cache_warming_requests(10000, coverage=0.95):,} requests")
# 29,957 requests — 95% is much cheaper
System Design Application
When discussing cache warming strategies, reference the coupon collector: "With 10,000 cache keys, we need roughly 50,000 random requests to reach 99% coverage. For faster warming, we should pre-populate the cache using a scan of the database rather than relying on random traffic."
With real Zipf-like traffic the hot keys load within a few hundred requests, so hit ratio recovers far faster than coverage; the coupon collector is the pessimistic bound. See Cache Warming.
Application: Sampling Coverage
If you are sampling events from a stream to discover distinct event types, the coupon collector gives you the expected number of samples before you see all types.
The same count answers "how many random probes before every backend is health-checked". Gossip beats it, rounds, because informed nodes spread the rumour too; see Gossip Protocols.
Tail Bounds: Union, Markov, Chebyshev, Chernoff
Often you do not know the exact distribution, or computing it is painful, but you need a guarantee: "the probability of something bad is at most X". Tail bounds give you that, trading tightness for generality. Think of them as a ladder: the more you know about the variable, the tighter the bound you can claim.
flowchart LR
U["Union bound: needs only individual probabilities"] --> M["Markov: needs only the mean, X nonnegative"]
M --> CH["Chebyshev: needs mean and variance"]
CH --> CF["Chernoff: needs a sum of independent pieces"]
CF --> EX["Exact distribution: tightest"]
The Union Bound
Intuition. The probability that any of several bad things happens is at most the sum of their individual probabilities. Overlaps only make the true number smaller.
No independence needed. Worked: a request touches 20 services, each with a 0.05% error rate. Whatever the correlations, . If you need under 0.5%, the per-service budget is . This is exactly how SLO error budgets are divided among dependencies, and how Bonferroni corrects for multiple comparisons on the A/B testing page.
Markov's Inequality
Intuition. A nonnegative variable cannot be far above its mean very often, or the mean would be bigger.
Worked: with mean latency 50 ms, at most of requests take 500 ms or more, for any distribution. Its use is sanity checks: "mean 50 ms and 20% over 500 ms" cannot both be true.
Chebyshev's Inequality
Intuition. If you also know the variance, values more than standard deviations from the mean are rare, whatever the shape.
At most 25% of values lie beyond and 11% beyond , for any distribution (a normal has 4.6% and 0.27%). Applied to a sample mean, whose variance is , it gives the weak law of large numbers: .
Chernoff Bounds
Intuition. When is a sum of many independent small pieces, deviations from the mean are exponentially unlikely, far less likely than Markov or Chebyshev can show. For a sum of independent 0/1 variables with mean :
A simpler, looser form for is .
Worked: comparing the ladder. Disks again: 1,000 disks, 1% monthly failure, , . How likely are 30 or more failures?
| Method | Bound on |
|---|---|
| Markov | |
| Chebyshev () | |
| Chernoff () | |
| Exact binomial |
Each rung buys orders of magnitude.
Engineering application. Chernoff is why random load balancing, hash sharding and sampling estimates concentrate tightly around their means: they are sums of many independent coin flips. It is also why that guarantee fails when keys are not independent; one tenant with a billion keys is one giant coin, not a billion small ones.
Reliability Math
Series vs Parallel Availability
Intuition. If a request needs every component, any single failure breaks it, and availability multiplies down. If a request needs any one of several redundant components, all must fail together, and unavailability multiplies down.
flowchart LR
subgraph SERIES["Series: all required"]
LB["LB 99.99%"] --> APP["App 99.9%"] --> DB["DB 99.95%"]
end
subgraph PARALLEL["Parallel: any one suffices"]
R1["Replica 99.9%"]
R2["Replica 99.9%"]
end
Worked example. A request goes through a load balancer (99.99%), an app tier (99.9%), and a database (99.95%):
About 99.84%, worse than the weakest component. Now replace the single database with two independent replicas at 99.95% each: the database tier becomes and the whole path rises to about 99.89%, now limited by the app tier.
A chain is weaker than its weakest link ( components at 99.9% give roughly ); redundancy moves the bottleneck; and parallel math assumes independence and instant failover, whose detector is itself a series component.
Nines and Downtime Budgets
| Availability | Downtime per year | Per 30-day month | Per week |
|---|---|---|---|
| 99% ("two nines") | 3.65 days | 7.2 hours | 1.7 hours |
| 99.9% | 8.77 hours | 43.2 minutes | 10.1 minutes |
| 99.95% | 4.38 hours | 21.6 minutes | 5.0 minutes |
| 99.99% | 52.6 minutes | 4.3 minutes | 1.0 minute |
| 99.999% | 5.26 minutes | 26 seconds | 6 seconds |
Every extra nine cuts the budget tenfold. At five nines you cannot afford a human to be paged and log in: recovery must be automatic. The system design math page turns these budgets into error budgets and deploy policies.
MTBF and MTTR
Intuition. A component alternates between working (on average MTBF, mean time between failures) and being repaired (on average MTTR, mean time to repair). The fraction of time it is up is
Worked example. MTBF of 1,000 hours and MTTR of 1 hour gives . Cut MTTR to 10 minutes and availability becomes , without making the component any more reliable. Halving MTTR is worth the same as doubling MTBF, and MTTR is usually far cheaper to improve: faster detection, automated failover, one-click rollback, smaller blast radius.
In redundant systems MTTR is also the window of vulnerability in which a second failure is fatal: a mirrored pair's mean time to total failure is roughly , so halving MTTR doubles it.
k-of-n Quorum Survival
Intuition. A consensus group of nodes stays available while at least a majority, , are up. The number of up nodes is binomial, so survival is a binomial tail:
Worked example. Each node is up with :
| Cluster | Needs | Tolerates | Unavailability | |
|---|---|---|---|---|
| 1 node | 1 of 1 | 0 failures | 0.99 | |
| 3 nodes | 2 of 3 | 1 failure | 0.999702 | |
| 5 nodes | 3 of 5 | 2 failures | 0.99999015 | |
| 7 nodes | 4 of 7 | 3 failures | 0.99999966 | |
| 3 nodes, any 1 (read-anywhere) | 1 of 3 | 2 failures | 0.999999 |
For 3 nodes the calculation is . Each step from 3 to 5 to 7 buys roughly 30 times lower unavailability, at the cost of more replicas to write to and slower consensus (a write waits for the -th fastest ack). Note also that a 4-node cluster needs 3 of 4 and tolerates only one failure, the same as 3 nodes, while having more nodes that can fail: even sizes buy nothing for majority quorums. The trade-offs between , and are on Quorums and Leaderless Replication.
from math import comb
def quorum_availability(n: int, k: int, a: float) -> float:
"""P(at least k of n independent nodes are up), each up with probability a."""
return sum(comb(n, i) * a**i * (1 - a)**(n - i) for i in range(k, n + 1))
for n in (3, 4, 5, 7):
k = n // 2 + 1
avail = quorum_availability(n, k, 0.99)
print(f"n={n} needs {k}: availability={avail:.8f} unavailable={1 - avail:.1e}")
# n=3 needs 2: availability=0.99970200 unavailable=3.0e-04
# n=4 needs 3: availability=0.99940797 unavailable=5.9e-04
# n=5 needs 3: availability=0.99999015 unavailable=9.9e-06
# n=7 needs 4: availability=0.99999966 unavailable=3.4e-07
The 4-node cluster is actually less available than the 3-node one. And all of these assume independent node failures: put all 5 nodes in one zone and the correlated-failure term from the independence section dominates every row.
Tail Latency at Fan-Out
Intuition. A request that fans out to backends in parallel and waits for all of them is as slow as the slowest one. Even if each backend is slow only rarely, with enough backends somebody is slow almost every time.
If each backend independently exceeds some latency threshold with probability :
Worked example. Each leaf has a p99 of 100 ms, so of calls exceed 100 ms.
| Fan-out | , leaf | With leaf |
|---|---|---|
| 1 | 1.0% | 0.1% |
| 10 | 9.6% | 1.0% |
| 50 | 39.5% | 4.9% |
| 100 | 63.4% | 9.5% |
| 200 | 86.6% | 18.1% |
At a fan-out of 100, 63% of user requests see the leaf's p99 latency. The leaf's 99th percentile has become the user's median. Turning it around: to keep the user-facing p99 at 100 ms with fan-out 100, each leaf needs , so the leaf's p99.99 must be under 100 ms.
This is the argument of Dean and Barroso's "The Tail at Scale" (Communications of the ACM, 2013). Remedies: hedged requests (after the leaf's p95, send a second copy and take the first answer; about 5% extra load, and both copies are slow only with probability ), partial results (search can skip a shard; a bank balance cannot), smaller fan-out, and fixing the causes of the leaf's tail (GC pauses, compaction, noisy neighbours).
sequenceDiagram
participant U as User request
participant A as Aggregator
participant L1 as Leaf 1
participant L2 as Leaf 2
participant L3 as Leaf 100
U->>A: query
A->>L1: sub-query
A->>L2: sub-query
A->>L3: sub-query
L1-->>A: 12 ms
L2-->>A: 15 ms
Note over A,L3: Leaf 100 hits a GC pause
L3-->>A: 140 ms
A-->>U: answer after 140 ms, the slowest leaf
Reservoir Sampling
The Concept
Reservoir sampling selects k items uniformly at random from a stream of unknown length n, using only O(k) memory.
Algorithm R (Vitter, 1985):
- Fill the reservoir with the first
kitems. - For each subsequent item at position
i(starting fromk+1):- Generate a random integer
jfrom1toi. - If
j <= k, replace reservoir[j] with the current item.
- Generate a random integer
Note (2026-11-09)
The example call at the bottom read from a file called huge_log.txt, which does not exist when you run the snippet. It is kept as a comment, and a runnable check on a generated stream has been added beneath it.
import random
def reservoir_sample(stream, k: int) -> list:
"""Select k items uniformly at random from a stream of unknown length."""
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
# Sample 100 items from a billion-row file — O(100) memory
# with open('huge_log.txt') as f:
# sample = reservoir_sample(f, 100)
# Runnable check: every item of a 10-item stream should be kept ~30% of the time (k/n = 3/10)
random.seed(7)
counts = [0] * 10
for _ in range(100_000):
for item in reservoir_sample(range(10), 3):
counts[item] += 1
print([round(c / 100_000, 3) for c in counts])
# [0.3, 0.298, 0.299, 0.303, 0.3, 0.3, 0.296, 0.305, 0.299, 0.301]
graph TD
S["Stream: item 1, item 2, ..., item n"]
R["Reservoir: size k"]
S -->|"First k items"| R
S -->|"Item i (i > k):<br/>P(keep) = k/i"| D{"Random j in [1..i]"}
D -->|"j ≤ k: replace"| R
D -->|"j > k: discard"| DISCARD["Discarded"]
style R fill:#059669,color:#fff
Why It Works
For any item at position i, the probability it ends up in the reservoir is exactly k/n:
- First k items: Initially included with probability 1. Must survive all subsequent replacement attempts. The probability of surviving is
k/(k+1) × (k+1)/(k+2) × ... × (n-1)/n = k/n. - Item at position i > k: Probability of being selected is
k/i. Must survive replacements from itemsi+1throughn. Combined probability isk/n.
In symbols, for an item at position : it is selected with probability , and each later item evicts it with probability , so
The product telescopes. This is the kind of argument interviewers want to see: a claim, then a product that collapses.
Application: Streaming Analytics
// Real-time: keep a random sample of recent errors
class ErrorSampler {
#reservoir = [];
#count = 0;
#maxSamples;
constructor(maxSamples = 100) {
this.#maxSamples = maxSamples;
}
add(error) {
this.#count++;
if (this.#reservoir.length < this.#maxSamples) {
this.#reservoir.push(error);
} else {
const j = Math.floor(Math.random() * this.#count);
if (j < this.#maxSamples) {
this.#reservoir[j] = error;
}
}
}
getSample() { return [...this.#reservoir]; }
}
For "a sample of the last hour", reset the reservoir per window; for weighted sampling, keep the top items by key (Efraimidis–Spirakis).
Bloom Filter False Positive Probability
The Concept
A Bloom filter is a space-efficient probabilistic data set membership test. It can tell you "definitely not in the set" or "probably in the set." It uses m bits and k hash functions.
graph LR
subgraph "Bloom Filter (m = 16 bits)"
B0["0"] --- B1["0"] --- B2["1"] --- B3["0"]
B3 --- B4["0"] --- B5["1"] --- B6["0"] --- B7["1"]
B7 --- B8["0"] --- B9["0"] --- B10["1"] --- B11["0"]
B11 --- B12["0"] --- B13["1"] --- B14["0"] --- B15["0"]
end
ADD["add('hello')"] -->|"h1('hello') = 2<br/>h2('hello') = 5<br/>h3('hello') = 10"| B2 & B5 & B10
style B2 fill:#059669,color:#fff
style B5 fill:#059669,color:#fff
style B10 fill:#059669,color:#fff
The Math
After inserting n items with k hash functions into m bits:
Probability a specific bit is still 0:
P(bit = 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)
False positive probability (all k bits are 1 for a non-member):
P(false positive) = (1 - e^(-kn/m))^k
Optimal number of hash functions:
k_optimal = (m/n) × ln(2) ≈ 0.693 × (m/n)
Bits per element for target false positive rate p:
m/n = -1.44 × log₂(p)
The derivation is a chain of the tools above. Each of the hash writes misses a given bit with probability ; treating them as independent, the bit stays 0 with probability (the same step as the birthday bound). A non-member is a false positive when all of its bits are 1. At the optimal , exactly half the bits are set, which is the intuition behind : a half-full filter carries the most information per bit.
| Target FP Rate | Bits Per Element | Hash Functions |
|---|---|---|
| 10% | 4.8 bits | 3 |
| 1% | 9.6 bits | 7 |
| 0.1% | 14.4 bits | 10 |
| 0.01% | 19.2 bits | 13 |
Correction (2026-11-09)
The output comment previously said bits: 958505838 and actual_fp_rate: 0.0098. Running the code gives 958,505,837 bits and 0.0101: the code truncates the optimal down to 6, which lands slightly above the 1% target. Rounding to 7 gives about 0.0100. The table's 7 for 1% is right.
import math
def bloom_filter_params(n: int, fp_rate: float) -> dict:
"""Calculate optimal Bloom filter parameters."""
m = int(-n * math.log(fp_rate) / (math.log(2) ** 2))
k = int((m / n) * math.log(2))
actual_fp = (1 - math.exp(-k * n / m)) ** k
return {
"bits": m,
"bytes": m // 8,
"megabytes": m / (8 * 1024 * 1024),
"hash_functions": k,
"actual_fp_rate": actual_fp,
}
# 100 million items, 1% false positive rate
params = bloom_filter_params(100_000_000, 0.01)
print(params)
# {'bits': 958505837, 'bytes': 119813229, 'megabytes': 114.26...,
# 'hash_functions': 6, 'actual_fp_rate': 0.01014...}
# ~114 MB to test membership in 100M items with 1% FP rate
System Design: When to Use Bloom Filters
- Database queries: Check if a key exists before hitting disk (used by Cassandra, LevelDB, RocksDB)
- Web crawling: Track visited URLs without storing all of them
- Spam filtering: Quick check if an email address is in a block list
- CDN: Check if content is in cache before forwarding to origin
Two traps: the false-positive rate climbs steeply past the designed , and the base-rate fallacy applies (if most lookups are for absent keys, most "maybe present" answers are wrong). See Bloom Filters.
Monte Carlo Estimation
The Concept
Monte Carlo methods use random sampling to estimate quantities that are difficult to compute analytically. The accuracy improves with more samples at a rate of 1/√n.
The recipe: simulate one random scenario, run it many times, average. The simulation can include what the algebra cannot: correlated failures, timeouts, real latency histograms.
Application: Estimating Pi
import random
def estimate_pi(n_samples: int) -> float:
"""Estimate pi using Monte Carlo: ratio of points in a quarter circle to a square."""
inside = 0
for _ in range(n_samples):
x, y = random.random(), random.random()
if x * x + y * y <= 1:
inside += 1
return 4 * inside / n_samples
# Accuracy improves with sqrt(n)
for n in [1000, 10000, 100000, 1000000]:
pi_est = estimate_pi(n)
error = abs(pi_est - 3.14159265) / 3.14159265 * 100
print(f"n={n:>10,}: π ≈ {pi_est:.6f} error: {error:.3f}%")
Application: System Capacity Estimation
When exact analysis is intractable (complex queueing systems, failure cascades), Monte Carlo simulation gives you answers.
Correction (2026-11-09)
The parallel case's comment claimed the simulation prints "~99.9999999%". It cannot: the true unavailability is , so 100,000 trials almost never see a single all-down sample and the output is 100.00000000%. The exact value comes from the formula, not the simulation. This is a general Monte Carlo limit: to estimate a probability you need well over trials, so rare events need the analytic answer or importance sampling.
import random
def simulate_availability(
component_availability: list[float],
architecture: str, # 'series' or 'parallel'
n_simulations: int = 100_000
) -> float:
"""Monte Carlo estimation of system availability."""
up_count = 0
for _ in range(n_simulations):
components_up = [
random.random() < avail
for avail in component_availability
]
if architecture == 'series':
system_up = all(components_up) # All must be up
else: # parallel
system_up = any(components_up) # At least one must be up
if system_up:
up_count += 1
return up_count / n_simulations
# 3 services in series (all must be up), each 99.9% available
series_avail = simulate_availability([0.999, 0.999, 0.999], 'series')
print(f"Series availability: {series_avail:.4%}")
# ~99.70% — each additional service multiplies failure probability
# 3 replicas in parallel (at least one must be up), each 99.9% available
parallel_avail = simulate_availability([0.999, 0.999, 0.999], 'parallel')
print(f"Parallel availability: {parallel_avail:.8%}")
# Prints 100.00000000% — the true value, 1 - 0.001**3 = 99.9999999%, is too rare to sample
Application: Quorum Survival With Correlated Failures
Here is where simulation earns its keep. The analytic quorum table assumed independent nodes. Add a shared zone outage and the formula gets messy; the simulation stays a few lines.
import random
def quorum_up(n_nodes: int, node_avail: float, zone_of: list[int],
zone_outage_p: float, rng: random.Random) -> bool:
"""One scenario: zones fail first, then nodes fail independently."""
zones_down = {z for z in set(zone_of) if rng.random() < zone_outage_p}
up = sum(1 for i in range(n_nodes)
if zone_of[i] not in zones_down and rng.random() < node_avail)
return up >= n_nodes // 2 + 1
def estimate(zone_of: list[int], trials: int = 1_000_000, seed: int = 42) -> float:
rng = random.Random(seed)
ups = sum(quorum_up(len(zone_of), 0.99, zone_of, 0.002, rng) for _ in range(trials))
return 1 - ups / trials
print(f"5 nodes, 1 zone: unavailability = {estimate([0, 0, 0, 0, 0]):.1e}")
print(f"5 nodes, 3 zones: unavailability = {estimate([0, 0, 1, 1, 2]):.1e}")
print(f"5 nodes, 5 zones: unavailability = {estimate([0, 1, 2, 3, 4]):.1e}")
# 5 nodes, 1 zone: unavailability = 1.9e-03
# 5 nodes, 3 zones: unavailability = 1.5e-04
# 5 nodes, 5 zones: unavailability = 2.2e-05
With each zone out 0.2% of the time, five nodes in one zone are about as unavailable as the zone itself, roughly : 200 times worse than the independent . A 2-2-1 spread survives any single zone outage, but losing a 2-node zone leaves no spare, so it lands at about . One node per zone gets close to the independent figure. (Rare-event estimates at a million trials are noisy; expect a few tens of percent of wobble between seeds.)
Confidence in Monte Carlo Results
The standard error of a Monte Carlo estimate with n samples:
SE = σ / √n
| Samples | Relative Error (for proportion ~0.5) |
|---|---|
| 1,000 | ~1.6% |
| 10,000 | ~0.5% |
| 100,000 | ~0.16% |
| 1,000,000 | ~0.05% |
(For a proportion , , so the table's values are , in absolute percentage points. For a rare event the relative error is , which is why the parallel-availability simulation above needs far more than trials to say anything.)
Diminishing Returns
Going from 1,000 to 10,000 samples (10x more work) only reduces error by ~3x. Going from 100,000 to 1,000,000 (10x more work) reduces error by ~3x again. Budget your simulation time accordingly.
Cheat Sheet: Quick Formulas
| Concept | Formula | Engineering Use |
|---|---|---|
| Birthday paradox (50% collision) | n ≈ 1.18 × √d | Hash collision estimation |
| Coupon collector (full coverage) | E ≈ n × ln(n) | Cache warming, sampling |
| Reservoir sampling | Keep with P = k/i for item i | Stream sampling |
| Bloom filter FP rate | (1 - e^(-kn/m))^k | Set membership testing |
| Little's Law | L = λ × W | Queue/capacity sizing |
| Poisson P(X=k) | λ^k × e^(-λ) / k! | Request rate modeling |
| Monte Carlo error | SE = σ / √n | Simulation accuracy |
| Bayes | P(H given E) = P(E given H)P(H) / P(E) | Alert precision, base rates |
| Complement | P(≥1) = 1 - P(none) | Any "at least one" question |
| Expected collisions | n(n-1) / 2d | Fingerprints, short IDs |
| Geometric retries | E = 1/p, P(N>k) = (1-p)^k | Retry limits and load |
| Exponential gap | P(T>t) = e^(-λt) | Inter-arrival, random failures |
| Union bound | P(any) ≤ Σ P(each) | Splitting error budgets |
| Markov | P(X ≥ a) ≤ E[X]/a | Sanity checks |
| Chebyshev | P(|X-μ| ≥ kσ) ≤ 1/k² | Distribution-free spread |
| Series / parallel | ΠA / 1 - Π(1-A) | Availability of a path |
| MTBF / MTTR | A = MTBF / (MTBF + MTTR) | Repair time vs reliability |
| Fan-out tail | 1 - (1-p)^n | Tail at scale |
Interview Questions
1. Your anomaly detector is "99% accurate" and fires. Should the on-call engineer assume an incident?
Answer. Not without the base rate. With sensitivity 99%, false-positive rate 2% and incidents in 0.1% of windows, Bayes gives . Most alerts are false. To fix it, reduce the false-positive rate (alert on user-facing symptoms with a duration condition), or require two independent signals, which lifts the posterior to about 71%. Raising sensitivity barely helps.
2. Three replicas, each down 1% of the time. What is the availability?
Answer. If independent, . But the honest answer is "it depends on correlation". With a shared cause active 0.1% of the time (same rack, same deploy), all-down probability is about , so availability is about 99.9%, a thousand times worse. Spread replicas across failure domains and stagger deploys; adding replicas inside one domain does not help.
3. How many random 7-character base-62 short codes can you generate before a collision is likely, and what do you do about it?
Answer. The space is . The birthday bound gives 50% collision probability at million codes, far below the capacity. So you must check-and-retry on insert (with a unique index). That is cheap: at a billion stored codes, a new code collides with probability . Alternatively use a counter encoded in base 62, permuted if codes must not be guessable.
4. A service fans out to 100 shards, each with p99 = 50 ms. What is the user-facing latency profile?
Answer. , so the shard p99 becomes roughly the user's median. For a user-facing p99 of 50 ms you need each shard's p99.99 under 50 ms (). Mitigations: hedged requests after the p95, partial results, smaller fan-out, and attacking the shard's tail causes (GC, compaction, noisy neighbours).
5. A downstream fails 50% of the time under overload, and your client retries up to 3 times. What happens?
Answer. Expected attempts per request are : 75% more load on a service that is already overloaded, and with multiple retrying layers it multiplies ( attempts worst case for three layers). Overload failures are correlated, so retries rarely succeed. Use retry budgets (for example, retries at most 10% of requests), exponential backoff with jitter, circuit breakers, and retry at only one layer.
6. Explain why a 3-node consensus cluster is better than 4 nodes, and quantify 3 versus 5.
Answer. Majority quorum: 3 nodes need 2 (tolerate 1 failure), 4 nodes need 3 (still tolerate only 1) but have more nodes that can fail, so 4 nodes are slightly less available (unavailability versus at 99% per node). Five nodes need 3 and tolerate 2: unavailability , about 30 times better than 3 nodes, at the cost of more write traffic and a slower -th ack.
7. MTBF is 2,000 hours and MTTR is 4 hours. The team proposes doubling MTBF with better hardware. Is there a cheaper option?
Answer. . Doubling MTBF gives . Halving MTTR to 2 hours gives , the same improvement. MTTR is usually cheaper to cut (automated detection and failover, faster rollback). In a replicated system, shorter MTTR also shrinks the window in which a second failure is fatal, multiplying the benefit.
8. Mean latency is 40 ms. Your manager says 15% of requests take over 400 ms. Possible?
Answer. No. Latency is nonnegative, so Markov's inequality gives . Either the mean or the 15% is wrong (perhaps they come from different time windows or different endpoints). Markov is a cheap consistency check on dashboards.
Related Pages
- Statistics for A/B Testing — Hypothesis testing and experimentation
- Math Patterns in System Design — Estimation, availability budgets, cache and sharding math
- Hash Tables — Hash function collision handling
- Sorting & Searching — Algorithmic complexity
- Queueing Theory — Little's Law, utilization and latency
- Quorums and Leaderless Replication — N, W, R trade-offs
- Bloom Filters — Sizing and variants
- Timeouts, Retries and Backoff — Retry amplification in practice
- System Design Interviews — Where these concepts get applied