0. Prerequisites — Core Building Blocks Read First If New to These Technologies

A. How to Use This Section

Unlike the twenty problems that follow, this section has no interview prompt and no deep dives tied to a single narrative. It exists purely as a primer — a plain-English explanation of every recurring technology and concept that gets used, often without re-explaining itself, across Problems 1 through 20. Redis alone is named well over a hundred times in this document; if you've never used it, every one of those mentions will read as jargon rather than a design decision you can evaluate.

Read it once, start to finish, before Problem 1, if most of the terms below are unfamiliar. Already comfortable with databases, caching, and message queues? Skim the table of contents above and jump only to the sections covering terms you don't already know — nothing here is required reading to follow the individual problems, which explain why a given tool was chosen in context. This section explains what the tool actually is, underneath that choice.

A note on depth: some of these building blocks (rate limiting algorithms, geospatial indexing) get their own full, dedicated deep dive later in the document (Problem 2 and Problem 5, respectively). Here, you'll get only enough to recognize the term when it's used in passing somewhere else — the full treatment is where it's the actual subject of the problem.

B. Relational vs. NoSQL Databases

A relational (SQL) database — Postgres, MySQL, and similar — stores data in tables made of rows and columns, with a defined schema and a query language (SQL) capable of joining data across tables. Its headline feature is the ACID transaction: a group of operations that either all succeed together or all fail together (Atomicity), leave the database in a valid state either way (Consistency, in the database sense — not to be confused with distributed-systems consistency in L), don't interfere with other concurrent transactions in ways that produce wrong results (Isolation), and survive a crash once committed (Durability). This is exactly what makes a relational database the right tool whenever a design needs a genuine, multi-step atomic operation — Ticketmaster's seat-hold transaction (Problem 8) is the clearest example among the first ten problems, and Payment System's double-entry ledger write (Problem 15) sharpens the same requirement further still: every write must leave two or more balanced rows, or none of them, with no in-between state ever observable.

NoSQL is not one thing — it's an umbrella term for several different data models, each optimized for a different access pattern, at the cost of giving up some of what a relational database offers (usually cross-row transactions, joins, or both):

NoSQL Type	Example Systems	Optimized For	Used (conceptually) In This Document For
Key-Value	Redis, DynamoDB	Extremely fast lookup by a single key; simple structure	Counters (Rate Limiter, P2), session/connection routing tables (Chat System, P4), leader locks (Job Scheduler, P10), the cache's own store (Distributed Cache, P11), the generic per-key store that is the whole problem (Distributed Key-Value Store, P18)
Document	MongoDB	Flexible, nested, semi-structured records without a rigid predefined schema	Generic entity storage where fields vary or evolve over time
Wide-Column	Cassandra, DynamoDB (wide mode)	Very high write throughput, naturally time-ordered data, horizontal scale	Chat message history (P4), job execution history (P10), delivery-attempt logs (Notification System, P12), windowed click-aggregation rollups (Ad Click Aggregation, P16)

The actual decision rule, stripped of vendor branding: reach for a relational database when correctness depends on an atomic, multi-step transaction or a strict uniqueness constraint (Ticketmaster's seat status, URL Shortener's alias uniqueness); reach for a NoSQL store when the access pattern is simple (fetch by key, append in time order) and the priority is raw horizontal write/read scale over transactional guarantees.

C. Replication & Sharding

These two terms sound similar and are frequently confused, but solve opposite problems.

Replication means keeping multiple copies of the same data on different machines. The standard model is leader-follower (also called primary-replica): all writes go to one leader machine, which then propagates the change to one or more follower/replica machines; reads can be served from any replica to spread out read load. The catch is replication lag — a replica's copy is, for some small window of time, slightly behind the leader's — which is exactly why reading from a replica is an eventually-consistent operation, not a strongly-consistent one. Distributed Cache applies this same leader-follower model at shard granularity, explicitly reasoning about that same replication lag (P11). Distributed Key-Value Store (P18) picks this section's other option instead: a symmetric, peer-to-peer model with no leader at all, where every node is a structural equal and any node in a key's preference list can coordinate a request — the explicit alternative to leader-follower this section describes.

Sharding (also called partitioning) means splitting different data across different machines, so that no single machine has to store or serve the entire dataset. Each shard typically also has its own replicas — the two techniques compose, they aren't alternatives to each other.

The one decision that matters most when sharding: choosing the shard key. A shard key should group together data that's almost always accessed together, so a typical request only ever needs to talk to one shard. This document repeatedly picks the shard key to match the natural "ownership boundary" of the data — sharding by event_id (Ticketmaster, P8), by doc_id (Google Docs, P9), by job_id (Job Scheduler, P10), by query prefix (Search Autocomplete, P13), by merchant_id (Payment System, P15), and by partition key chosen deliberately upfront (Distributed Message Queue, P20) are all the same underlying idea, generalized further in the Patterns Playbook (Section 21).

D. Caching & Redis

Caching, generally: keep a copy of data that's expensive to compute or slow to fetch somewhere faster and closer to where it's needed, so most requests never have to pay the original cost. The most common pattern in this document is cache-aside (lazy loading): on a read, check the cache first; on a miss, fetch from the real source of truth (usually a database), then populate the cache before returning — the next request for the same data hits the cache directly. Everything in this section gets its own full, dedicated deep dive later: Distributed Cache (Problem 11) designs exactly this kind of system end-to-end — eviction, replication, and sharding included — the same way Rate Limiter (Problem 2) is the dedicated deep dive for token buckets and sliding windows (N). Search Autocomplete (P13) and Yelp (P17) both layer exactly this cache-aside model in front of a slower origin (trie shards and a search engine, respectively) as one stage of a broader caching hierarchy, explicitly citing Distributed Cache's own cache-aside design as the reference point.

Cache invalidation and TTL: a cached copy can become stale once the underlying data changes. The simplest, most common fix used throughout this document is a TTL (time-to-live) — the cached entry simply expires and is removed automatically after a fixed duration, rather than requiring an explicit "go delete this from every cache" step. TTL shows up constantly: rate-limiter window counters (P2), reservation holds (P8), presence data (P9), and TTL as a first-class, per-entry property of the store itself (Distributed Cache, P11) are all, underneath, "store this, and forget it automatically after N seconds."

What Redis specifically is: Redis is an in-memory data-structure store — meaningfully more than a plain key-value cache, even though "use it as a cache" is its most common role in this document. It supports several native data types beyond a flat string value:

• Strings — the basic case: a single value per key (a cached page, a counter).
• Hashes — a key mapping to multiple field/value pairs, like a compact object.
• Sets and Sorted Sets — sorted sets in particular attach a numeric score to each member and keep them ordered by it, which is what underlies sliding-window-style rate limiting (P2) and leaderboard-shaped problems generally — Real-Time Leaderboard (Problem 19) is the deep dive built entirely around this one data type, sorted sets as the primary structure rather than a supporting cache.
• Lists — ordered sequences, useful as a simple queue.

Why Redis operations are effectively atomic without extra application-level locking: Redis processes commands single-threaded — one command (like INCR, an atomic increment) runs to completion before the next one starts, so two concurrent increments can never interleave and produce a wrong result. For anything more complex than a single built-in command, Redis supports Lua scripting — a small script bundling several operations (e.g., "check the current count, and only increment it if under the limit") that Redis executes as a single atomic unit, the same way a database transaction guarantees all-or-nothing execution. This is exactly what backs the Rate Limiter's atomic check-and-increment (Problem 2) without needing a separate, external lock.

Redis as a distributed lock: the basic building block is a single atomic command — SET key value NX PX ttl — which sets a key only if it doesn't already exist (NX), with an automatic expiry (PX, milliseconds). "Only if it doesn't already exist" is what makes this usable as a lock: whichever process's SET succeeds first holds the lock; everyone else's fails and knows to back off. The TTL is what prevents a crashed lock-holder from blocking everyone else forever. Worth knowing this is a genuinely debated technique, not settled dogma — the more elaborate multi-node version of this idea (often called Redlock) has a well-known public disagreement between Redis's creator and distributed-systems researcher Martin Kleppmann over whether it's actually safe under real-world clock and network conditions. This is exactly why, when a database's own native atomicity (a conditional update, a transaction) is available and sufficient, this document consistently prefers that over reaching for an external lock — Ticketmaster's seat-hold reasoning (Problem 8, Deep Dive M) states this trade-off explicitly.

Redis Pub/Sub: a simple publish/subscribe mechanism — a publisher sends a message on a named channel, and every currently-subscribed client receives it immediately. The critical thing to understand is that it's fire-and-forget and non-durable: if no one is subscribed to a channel at the moment a message is published, that message is simply gone — there's no log to replay later. This makes it a good fit for ephemeral, loss-tolerant data (presence updates, cursor broadcasts — Chat System P4, Google Docs P9) and a bad fit for anything that must never be lost, which is precisely the durability distinction Kafka (G) exists to provide instead.

E. Distributed Locks

The underlying problem: multiple independent processes, on different machines, sometimes need to ensure only one of them is touching a particular shared resource at a time — the distributed-systems equivalent of a single-process mutex, except there's no shared memory to put the lock in.

The core danger of any lock, distributed or not: if the process holding the lock crashes without releasing it, everyone else waits forever unless the lock can expire on its own — this is exactly why every distributed lock discussed in this document is lease-based (has a built-in TTL), never a bare, unexpiring lock.

When to reach for an external lock (Redis-based, as in D) versus a database's own native atomicity: if the entire "check, then act" operation can be expressed as a single atomic database statement (a conditional UPDATE ... WHERE status = 'available', checking the affected-row count) or a single database transaction, that's simpler and has one fewer moving part than introducing a separate lock service — reach for it first. An external distributed lock earns its keep specifically when the protected operation needs to span multiple systems that a single database transaction can't reach — Distributed Cache's cache-refill-coalescing fallback (P11) is the clearest example: a short-lived lock around the refill step, held only by whichever request wins the race, so every other concurrent request waits on that one fetch instead of stampeding the origin.

ZooKeeper and etcd are purpose-built coordination services, offering strongly-consistent, ordered key storage with the ability to "watch" a key for changes — a more robust (and more operationally heavy) foundation for distributed locks and leader election than a single Redis key, used in real production systems at larger scale than a Redis-based lock comfortably handles. Underneath both, a consensus algorithm (ZooKeeper uses ZAB, etcd uses Raft) lets a cluster of machines agree on a single authoritative value even if some of them fail or are unreachable, via a form of majority voting — worth knowing this exists conceptually; the algorithm's internals are out of scope here. Distributed Message Queue's per-partition leader-and-ISR replication and its cluster controller (P20) both lean on exactly this kind of consensus quorum, at partition granularity instead of whole-service granularity.

F. Leader Election

The problem it solves: some responsibilities must be performed by exactly one instance at a time among a fleet of otherwise-identical, redundant instances — not zero (a single point of failure), and not more than one (which, depending on the responsibility, can actively cause harm rather than just waste work).

Lease-based election, the common pattern: every candidate instance repeatedly tries to atomically acquire a shared, TTL'd lock (E) keyed to "the leader role" itself; whichever instance succeeds is the leader until its lease expires, and must periodically renew that lease to remain leader. If the leader crashes and stops renewing, the lease simply expires and a different instance's next attempt succeeds — failover happens automatically, bounded by how long the lease TTL is.

Split-brain, the real risk to be aware of: under unlucky timing — clock skew between machines, or a garbage-collection pause that delays a renewal — two instances can briefly both believe they're the leader. This is a genuinely hard, real distributed-systems problem, not just an interview talking point, which is part of why Job Scheduler's design (Problem 10, Deep Dive M) treats leader election as deserving its own explicit deep dive rather than a one-line mention. The same lease-based mechanism resurfaces for Distributed Cache's shard leadership on resharding (P11) and, at a finer, per-partition grain, for Distributed Message Queue's partition leaders and cluster controller (P20) — a singleton role elected the identical way regardless of how small or large the thing being led is.

G. Message Queues, Kafka & Pub/Sub

Why decouple a producer from a consumer at all: if a service that accepts work (say, "resize this uploaded image") called the actual resizing logic directly and synchronously, a slow or overloaded resizer would make the accepting service slow too, and a burst of uploads would have nowhere to go but straight into an overwhelmed resizer. A queue sits in between: the producer drops work onto the queue and moves on immediately; consumers pull work off at whatever rate they can sustainably handle, buffering the burst.

Traditional message queue model (e.g. SQS, RabbitMQ): a message is delivered to one consumer, and is removed from the queue once that consumer acknowledges having processed it.

Kafka's log-based model is meaningfully different: messages are appended to a durable, ordered log (called a topic), and are not deleted when read — instead, each consumer (or independent group of consumers, a consumer group) tracks its own position (offset) in that log. This means multiple entirely independent downstream systems can each read the full stream of events at their own pace, which is exactly why Kafka (or an equivalent log-based broker) is the right fit whenever one event needs to feed more than one independent downstream consumer — e.g., a "job completed" event feeding both an analytics pipeline and a notification service. A topic is typically split into multiple partitions for parallelism, with a guarantee of ordering only within a partition, not across the whole topic.

At-least-once delivery, and why it matters everywhere else in this document: both traditional queues and Kafka-style logs generally guarantee a message will be delivered at least once, not exactly once — if a consumer crashes after doing the work but before acknowledging it, the same message gets redelivered and processed again. This single fact is the reason idempotency (O) is such a recurring, load-bearing concept throughout this document rather than an edge-case afterthought — queues do not give you exactly-once processing for free, and no design in this document pretends otherwise.

Where this shows up: async fanout (News Feed, P3), the transcoding pipeline (Video Streaming, P7), the trigger queue feeding the worker fleet (Job Scheduler, P10), the delivery-triggering event feeding both a push-provider worker pool and an analytics pipeline (Notification System, P12), the query-log stream feeding the offline batch-aggregation pipeline (Search Autocomplete, P13), the durable queue absorbing extremely-high-volume click events ahead of windowed aggregation (Ad Click Aggregation, P16), the lightweight queue decoupling a leaderboard's synchronous in-memory write from its durable persistence (Real-Time Leaderboard, P19), and Distributed Message Queue (P20), which builds a Kafka-shaped log-based broker from scratch, contrasting it against the traditional delete-on-consume model described here at every step.

H. CDNs & Load Balancers

A CDN (content delivery network) is a set of servers distributed geographically close to end users, caching content (video segments, images, static assets) so a user's request is served from a nearby edge location instead of traveling all the way to a distant origin server. A cache hit at the edge is fast and never touches the origin at all; a cache miss falls through to the origin, gets cached at that edge location, and is fast for the next nearby request. This is the standard delivery mechanism for anything read-heavy and mostly-static — video segments (Video Streaming, P7) are the clearest example in this document. Search Autocomplete's non-personalized base ranking (P13) is a subtler fit for the same reason: the response for a given (prefix, locale) is largely identical across huge numbers of users and changes only as often as the trie rebuilds, so it can sit at the edge with a short TTL and never reach an origin shard at all.

A load balancer distributes incoming requests across a fleet of backend servers, which is what actually makes horizontal scaling of a stateless service possible — without one, a client would need to somehow already know which specific server to talk to. Load balancers operate at different layers of the network stack:

• L4 (transport layer) — routes based on IP address and port alone, without looking at the actual HTTP request; faster and simpler, but "dumber."
• L7 (application layer) — understands HTTP itself, so it can route based on URL path, headers, or cookies, and can also terminate SSL/TLS on behalf of backend servers; more capable, at the cost of more per-request processing.

Load balancers also perform health checks, automatically stopping traffic to a backend instance that's failing to respond correctly — the basic mechanism behind "a crashed server doesn't keep receiving requests."

I. Blob / Object Storage

What it is: a storage system (Amazon S3 is the best-known example) purpose-built for storing large, unstructured binary objects (images, videos, documents) referenced by a simple key — not a traditional hierarchical filesystem, and not a queryable database; just cheap, durable, massively scalable storage for bytes.

Why databases are a poor fit for large binary content directly: storing multi-megabyte blobs inside database rows bloats the database's storage footprint, slows down backups and replication (both of which now have to move all those bytes too), and costs meaningfully more per gigabyte than purpose-built object storage.

The metadata/blob split, a pattern repeated constantly in this document: store a small pointer/metadata row in the database (an object key, size, owner, timestamps) and the actual bytes in the object store — used for News Feed media (P3), Chat System attachments (P4), Web Crawler's fetched pages (P6), Video Streaming's raw and transcoded files (P7), Google Docs's snapshots (P9), Distributed File Storage's content-addressed chunk store (P14, the same split with a twist: the object key is a content hash, which is what turns it into deduplication), Ad Click Aggregation's cold-storage archive of raw click events past the ~30-day dispute window (P16), and Yelp's business photos (P17). This is generalized further as its own named pattern in the Patterns Playbook (Section 21).

Pre-signed URLs: a time-limited, permission-scoped URL that grants a client temporary, direct upload or download access to a specific object in the store — without the application server ever having to proxy the actual bytes through itself. This is what lets Video Streaming's upload pipeline (Problem 7) keep large file transfers off the application tier entirely, and the same mechanism Distributed File Storage (P14) reuses for chunk upload/download, gated by an access check at the metadata layer before a chunk hash or URL is ever handed to a client.

J. Consistent Hashing

The problem it solves: given N servers (or shards) and a huge number of keys, you need a way to assign each key to a server that's (a) roughly balanced across all servers, and (b) doesn't force almost every key to move when a server is added or removed. A naive approach — hash(key) % N — fails badly at (b): changing N from, say, 10 to 11 changes the result of that modulo operation for nearly every key, meaning nearly everything has to be relocated for one server joining or leaving.

How consistent hashing works, conceptually: imagine a fixed circular range of hash values (a "ring") — both servers and keys get mapped onto points on this ring by hashing their identifiers. A key belongs to whichever server's point is the next one clockwise from the key's own point. When a server is added or removed, only the keys between it and its immediate neighbor on the ring need to move — everything else stays exactly where it was.

Virtual nodes: in practice, each physical server is given multiple points on the ring (not just one), which smooths out load distribution — without this, one server could unluckily end up owning a disproportionately large or small arc of the ring purely by hash coincidence.

Where used: rate-limiter shard/owner assignment (P2), Chat System's connection-server routing (P4), Google Docs's document-server assignment (P9), Distributed Cache's primary partitioning mechanism across cache nodes (P11), Distributed File Storage's chunk-store sharding by content hash — an unusually clean case, since hashes are already uniform (P14), and Distributed Key-Value Store's deepest treatment of the ring, extended to decide not just which node owns a key but which N nodes replicate it, including virtual-node load-balance trade-offs (P18) — all instances of "which server owns this piece of data or this responsibility right now," solved the same way.

K. WebSockets & Persistent Connections

Ordinary HTTP is request/response: a client asks, a server answers, the connection (in the simplest mental model) is done. This is a poor fit for anything where the server needs to push data to a client without the client having asked first — a new chat message arriving, another user's edit in a collaborative document.

A WebSocket upgrades a single underlying TCP connection into a persistent, full-duplex channel — either side can send data to the other at any time, for as long as the connection stays open, without the overhead of a new HTTP request per message.

Why this beats polling or long-polling for real-time features: plain polling (the client repeatedly asks "anything new?") wastes requests when nothing has changed and adds latency up to the length of the polling interval; long-polling (the server holds a request open until it has something to send, then the client immediately reopens another one) is a partial workaround that still carries meaningful per-message overhead. A genuinely persistent connection avoids both problems.

The routing problem this creates: a fleet of connection servers ends up holding millions of long-lived connections between them, and a message destined for a specific user has to find whichever specific server currently holds that user's connection. The standard fix — a shared session store (user_id → server_id) plus a pub/sub broker to actually deliver the message to the right server — is used in Chat System (Problem 4) and generalized further in the Patterns Playbook (Section 21).

L. Consistency Models: CAP & PACELC

The CAP theorem states that when a network Partition actually occurs (some machines can't talk to others), a distributed system must choose between Consistency (every read reflects the most recent write, everywhere) and Availability (every request still gets a response, even if it might be a bit stale) — you cannot have both guaranteed simultaneously during a real partition.

Why CAP alone is an incomplete picture: PACELC extends the reasoning to the much more common case — no partition at all. Even then, there's still a trade-off between Latency and Consistency: waiting for a write to be confirmed by every replica before responding is slower but strongly consistent; responding immediately off of a possibly-slightly-stale replica is faster but only eventually consistent.

The three consistency levels that come up repeatedly:

• Strong consistency — every read reflects the latest write, guaranteed. Expensive to maintain across a distributed system; used sparingly and deliberately in this document (Ticketmaster's seat status, P8; a leader lock, P10). Payment System's ledger (P15) goes further still — every LedgerTransaction commits as a single ACID unit, a materially stronger requirement than this framing allows for elsewhere, with no "eventually balances" state ever tolerated.
• Eventual consistency — reads may briefly return stale data, but all replicas converge to the same value given enough time with no new writes. The default posture for most of this document (URL Shortener's redirect path, P1; a document's browse/seat-map display, P8; Ad Click Aggregation's headline dashboard numbers, deliberately treated as approximate and provisional, P16).
• Causal consistency — a middle ground: operations that are causally related (an edit that depends on a prior edit) are seen in the correct relative order, even if unrelated operations aren't ordered relative to each other. Relevant to Google Docs's edit ordering (P9).

The pattern behind nearly every design in this document: pick eventual consistency as the default (it's simpler, cheaper, and more available), and carve out one deliberately narrow "strong-consistency island" specifically where correctness genuinely requires it — never the reverse. This exact shape is named explicitly, and given its own generalized treatment, in the Patterns Playbook (Section 21). Distributed Key-Value Store (P18) is the deepest treatment of this whole trade-off: PACELC stops being a naming exercise and becomes a literal, tunable (N, R, W) quorum a caller picks and defends per request, rather than one fixed system-wide stance.

M. Bloom Filters

What it is: a compact, probabilistic data structure for testing whether an element is a member of a set. It has an unusual, specific guarantee: it can say "definitely not in the set" with certainty, but can only say "probably in the set" — occasionally producing a false positive (claiming something is present when it isn't), never a false negative.

How it works, conceptually: a Bloom filter is a bit array plus several independent hash functions. Adding an element hashes it several ways and sets the corresponding bits. Checking membership hashes the candidate the same ways and checks whether all those bits are already set — if even one isn't, the element is definitely not present; if all are set, it probably is (possibly due to bits set by other elements coincidentally overlapping).

Why a small, tunable false-positive rate is an acceptable trade for a huge space saving: storing billions of full URLs just to check "have we seen this exact URL before" would require enormous memory; a Bloom filter answers the same question using a small fraction of that space. Web Crawler's URL-deduplication problem (Problem 6) is the clear example — a false positive there just means occasionally, harmlessly skipping a URL that hadn't actually been seen yet, a low-cost mistake in exchange for a massive space savings. Ad Click Aggregation (P16) reuses it as a cheap pre-filter sitting in front of an exact click-ID dedup store: a "definitely not seen" answer is trusted outright and skips the expensive exact lookup entirely, while a "probably seen" answer falls through to the real check — the filter's one-directional error means this can never wrongly discard a genuine click. The same problem also introduces HyperLogLog for a different question (estimating how many distinct elements, not testing membership of one) — worth keeping the two probabilistic structures distinct rather than treating them as interchangeable.

N. Rate-Limiting & Geospatial Primers

Both of these get a full, dedicated deep dive later (Rate Limiter is Problem 2 in its entirety; geospatial indexing is central to Ride-Sharing, Problem 5) — this is only enough to recognize the terms when they're referenced in passing elsewhere.

Token bucket: a bucket holds up to N tokens and refills at a fixed rate; each incoming request consumes one token, and a request arriving when the bucket is empty is rejected or delayed. This allows short bursts up to the bucket's capacity while still enforcing a steady average rate over time.

Sliding window counter: counts requests within a continuously-moving time window, rather than a window that abruptly resets — this avoids the "double burst at the boundary" flaw of a naive fixed window, where a client could send a full limit's worth of requests right at the end of one window and another full limit's worth right at the start of the next.

Geohash: encodes a latitude/longitude pair into a short string such that geographically nearby points tend to share string prefixes — this turns "find points near me" into a comparatively simple string-prefix or range query.

Quadtree: a tree structure that recursively divides two-dimensional space into four quadrants, subdividing further only in regions with a high density of points — unlike a geohash's fixed-precision grid cells, a quadtree's cell size adapts to how densely populated a given area actually is.

Where these resurface beyond their home problems: Search Autocomplete (P13) blends a geohash-prefixed branch or a separate geospatial index into its trie for location-aware suggestions, reusing this reasoning rather than inventing a new spatial mechanism; Yelp (P17) re-derives the same geohash/S2/quadtree choice for static points (businesses, which essentially never move) rather than Ride-Sharing's constantly-moving drivers — a sharper version of the judgment, since a geohash can be computed once at write time and stored directly instead of recomputed on every read.

O. Idempotency

What "idempotent" means: performing an operation multiple times has exactly the same effect as performing it once.

Why this matters specifically in distributed systems: networks are unreliable — a client can send a request, have it actually succeed on the server, and then never receive the response (a timeout, a dropped connection). From the client's point of view, this is indistinguishable from the request never having reached the server at all. If the client's only safe option is to retry, and retrying isn't safe, the system is stuck. This is also precisely why literal "exactly-once" execution isn't achievable over a network in the first place — you cannot reliably tell "it happened but the confirmation was lost" apart from "it never happened" — a point made explicitly in Job Scheduler's Deep Dive O (Problem 10).

The actual, achievable substitute: make retries safe. A client attaches a stable, unique idempotency key to a mutating request; the server checks whether it has already processed that exact key and, if so, simply returns the original result instead of repeating the underlying side effect (charging a card a second time, sending a duplicate message).

Where this exact mechanism is reused, under different names, throughout this document: Chat System's client_msg_id (Problem 4), Ticketmaster's payment-confirmation idempotency key (Problem 8), Job Scheduler's per-execution idempotency key (Problem 10), Notification System's client-generated key guarding against duplicate sends (P12), Distributed File Storage's stable operation ID tagging every queued sync entry so an interrupted flush never double-uploads a chunk (P14), Payment System's mandatory Idempotency-Key header — the single non-negotiable mechanism the entire design is built around (P15), Ad Click Aggregation's click_id-based dedup against duplicate at-least-once deliveries (P16), and Distributed Message Queue's own consumer-side idempotent-consumer pattern, paired with its honestly-stated at-least-once guarantee (P20) — six different domains by now, the identical underlying technique.

P. Quick-Reference Glossary

Term	One-Line Definition	Where It Shows Up
Redis	In-memory data-structure store; used as a cache, a counter, a TTL'd lock, and a Pub/Sub channel	Nearly every problem
Kafka	Durable, ordered, append-only log; lets multiple independent consumers each read the full event stream	P3, P7, P10, P12, P16, P20 (P20 builds a Kafka-shaped system from scratch)
CDN	Geographically distributed edge cache for read-heavy, mostly-static content	P1, P3, P7, P13
Load Balancer	Distributes requests across a fleet of stateless backend servers	Every problem, implicitly
Blob / Object Storage	Cheap, durable storage for large binary content, referenced by key (e.g. S3)	P3, P4, P6, P7, P9, P14 (the chunk store itself)
Sharding	Splitting different data across different machines by a key	P2, P8, P9, P10, P11, P13 (by prefix), P15 (by merchant_id), P18, P19, P20 (by partition)
Replication	Keeping copies of the same data on multiple machines for availability/read scale	Implicit in every data store; the central subject of P18's tunable quorum and P20's leader+ISR model
Consistent Hashing	Assigns keys to servers on a ring such that adding/removing a server reshuffles only a small slice of keys	P2, P4, P9, P11 (primary partitioning mechanism), P14 (chunk store), P18 (deepest treatment, incl. virtual-node trade-offs)
Distributed Lock	A TTL'd, cross-machine mutex, typically built on a single atomic conditional write	P2, P8, P10 (conceptually)
Leader Election	Ensures exactly one instance among many actively performs a singleton responsibility	P10, P20 (per-partition leader, re-elected from the ISR on failover)
ZooKeeper / etcd	Purpose-built strongly-consistent coordination services for locks/leader election at scale	Named as an alternative in P8, P10, P20 (partition-leader metadata)
WebSocket	A persistent, full-duplex connection allowing server-initiated push	P4, P9
Bloom Filter	Space-efficient probabilistic set-membership test; false positives possible, false negatives impossible	P6, P16 (dedup pre-filter ahead of the exact idempotency check)
Token Bucket	Rate-limiting algorithm allowing bursts up to a fixed capacity while enforcing an average rate	P2, referenced in P8, P12 (per-user-per-channel throttling), P13 (per-client query throttling)
Sliding Window Counter	Rate-limiting algorithm avoiding fixed-window boundary bursts	P2
Geohash	Encodes lat/lng into a string where nearby locations share prefixes	P5, P17 (static-point index, contrasted against P5's moving-driver index)
Quadtree	Recursively subdivided 2D spatial index, adapting cell size to point density	P5, P17
Idempotency Key	A client-generated unique key making a retried mutating request safe to repeat	P4, P8, P10, P12, P15 (mandatory at the API boundary), P16, P20 (applied by the queue's own consumers)
CAP Theorem	Under a network partition, choose consistency or availability, not both	Conceptual backbone of every consistency-model discussion; made fully explicit and tunable per-request in P18
TTL	Time-to-live; an automatic expiry on a stored value	P2, P8, P9, P11 (first-class cache expiry), P12 (dedup window)
Pre-Signed URL	A time-limited, scoped URL granting direct client access to an object store, bypassing the app server	P7, P14 (chunk upload)
Trie (Prefix Tree)	Tree where each root-to-node path spells out a string prefix, enabling fast prefix lookups and precomputed per-node results	P13 (core data structure, precomputed top-K cached at each node)
HyperLogLog	Probabilistic data structure estimating the count of distinct elements in a set using a small, fixed amount of memory	P16 (unique-click / unique-viewer estimation at high volume)
Watermark	In stream processing, a marker asserting "no more events older than this timestamp will arrive," used to decide when a windowed aggregation can be safely finalized	P16 (handling late-arriving click events)
Vector Clock	A set of per-replica logical counters attached to a write, used to determine whether two versions are causally ordered or genuinely concurrent (conflicting)	P18 (conflict detection between replicas)
Version Vector	The same underlying mechanism as a vector clock, applied per-file/per-device to detect when two edits to the same file are genuinely concurrent rather than one superseding the other	P14 (sync-conflict detection, resolved via a conflicted copy)
Merkle Tree	A tree of hashes where each parent hashes its children; lets two replicas find exactly which data differs by comparing tree hashes top-down, without transferring all the data being compared	P18 (anti-entropy — efficiently finding what a replica is missing)
Hinted Handoff	When the node that should own a write is temporarily unreachable, a different available node accepts the write and hands it off to the rightful owner once it recovers	P18 (keeps writes available during a transient node failure)
Read Repair	Detecting, during a read, that replicas disagree on a key's value, and proactively pushing the latest version to the stale replica(s)	P18 (a second, read-triggered path for replicas to converge, alongside hinted handoff)
Quorum (N/R/W)	Tunable replication knobs: N replicas store each key; a write must be acknowledged by W of them; a read must be confirmed by R of them. W + R > N guarantees every read overlaps the latest write	P18 (exposed directly to the caller, so consistency/availability is chosen per-request rather than fixed system-wide)
Content-Defined Chunking	Splits a file into variable-size chunks based on a rolling hash over the content itself (not fixed-size blocks), so a small edit only changes the chunks actually touched by it	P14 (enables chunk-level dedup and delta sync across a whole chunk store, even across different users' files)
Saga Pattern	A multi-step distributed transaction expressed as a sequence of local steps, each paired with a compensating (undo) action, since no single database transaction can span multiple independent services	P15 (multi-step payment flows spanning the ledger, a payment processor, and notifications)
Double-Entry Ledger	An append-only accounting model where every transaction is recorded as two balanced entries (a debit and a credit), enforced by the storage layer so the ledger can never be observed in an unbalanced state	P15 (the strongest-consistency requirement in this document)
Consumer Group	A set of consumers that split a topic's partitions among themselves, so each partition is actively processed by exactly one group member at a time	P20 (also introduced conceptually in Prerequisites G; P20 is the deep dive on building the mechanism itself)
ISR (In-Sync Replicas)	The subset of a partition's replicas that are fully caught up with the leader; only ISR members are eligible for leader election on failover, bounding how much acknowledged data can be lost	P20 (leader+ISR replication model)