System Design Casebook

Round trip time (RTT)

Time for a packet to reach the other side and come back. Distance sets the floor: light in fiber covers about 200 km per millisecond.

DNS

Turns a name like example.com into an IP address. Answers are cached by browsers, operating systems and resolvers for the record’s TTL.

TCP handshake

SYN, SYN-ACK, ACK: one round trip before any data can flow.

TLS handshake

Agrees on keys to encrypt the connection: two round trips with TLS 1.2, one with TLS 1.3.

Time to first byte (TTFB)

From starting the request until the first byte of the response arrives. Setup, one round trip and server work all count.

Connection reuse

Keeping a connection open (keep-alive, pooling) so later requests skip DNS and both handshakes.

How a name becomes an address

Latency

Time for one operation, measured end to end. Usually reported in milliseconds.

Throughput

Work completed per unit of time: requests per second, messages per second, MB per second.

Bandwidth

The maximum rate a link can carry. Throughput is what you actually get through it.

Percentile

p99 = 250 ms means 99% of requests finished within 250 ms and 1 in 100 took longer. p50 is the median.

Tail latency

The slow end of the distribution, p99 and beyond. It grows in importance as one user action fans out into many calls.

Mean

The average. A few very slow requests drag it far above what a typical user sees, so it describes nobody.

Availability

Uptime as a share of total time, such as 99.9%. Measured over a window, often 30 days.

MTBF

Mean time between failures: how long things usually run before breaking.

MTTR

Mean time to recovery: how long it takes to get back up once broken.

Single point of failure

A component whose failure stops the whole system.

Redundancy

Extra copies of a component so one can fail without an outage.

SLI, SLO, SLA

What you measure, the target you set for it, and the contract you sign with customers.

Formula  availability = MTBF ÷ (MTBF + MTTR)
Example  fails once a month (720 h), 1 h to recover   → 720 ÷ 721 = 99.86%
Faster   same failures, recover in 6 minutes          → 720 ÷ 720.1 = 99.99%

Recovering faster buys nines as surely as failing less often, and it is usually cheaper: good alerts, quick rollbacks and automatic failover.

Arrival rate (λ)

How many requests arrive per second.

Service time (S)

How long one request takes when nothing else is waiting.

Utilization (ρ)

The share of time a resource is busy: arrival rate × service time, for one server.

Little’s law

Requests in the system = arrival rate × time each one spends there. L = λ × W, true for any stable system.

Saturation

Work arrives faster than it can be served; queues and latency grow without limit.

Headroom

Spare capacity kept free for spikes and failures, often 30 to 40% at peak.

Transaction

A group of reads and writes that succeed or fail as one unit.

ACID

Atomic (all or nothing), consistent (rules hold), isolated (as if one at a time), durable (survives crashes).

Index

A sorted structure, usually a B-tree, that finds rows without scanning the table. Speeds reads, slows writes.

OLTP and OLAP

Many small transactional reads and writes, versus large analytical scans over history.

Schema

The declared structure of the data. Enforced on write in relational databases, interpreted on read in many NoSQL stores.

Write-ahead log

Changes are appended to a log before being applied, so a crash can be replayed. Replication and change data capture read the same log.

Synchronous

The caller waits for the answer. Simple, but the caller is only as fast and available as whatever it calls.

Asynchronous

The caller hands off work, often through a queue, and moves on. Decouples the two sides at the cost of eventual results.

Pull and push

Pull: the client asks for news. Push: the server sends it when it happens.

Webhook

An HTTP callback: you give a service a URL and it calls you when an event happens.

RPC

Calling a function on another machine as if it were local, as gRPC does with typed contracts.

Fan-out

One request or event that triggers many downstream calls or messages.

Bit and byte

A byte is 8 bits. Network speeds are quoted in bits (Mbps), file sizes in bytes (MB), so divide by 8.

KB and KiB

KB is 1,000 bytes; KiB is 1,024. For estimates the 2.4% difference does not matter; for disk sizes it adds up.

Throughput in practice

Protocol overhead and congestion usually leave 70 to 90% of the link rate for your data.

1. 1

   Clarify requirements

   Agree on users, features, scale and what matters most. Leave with 3 to 5 functional and 3 to 5 non-functional requirements written down.

   “Read heavy or write heavy? Is a few seconds of staleness acceptable?”

2. 2

   Estimate

   QPS, peak QPS, storage and bandwidth, rounded hard. You want the order of magnitude that decides the design, not precision.

   “35K reads per second is more than one database should take, so we need a cache.”

3. 3

   High level design

   API, data model, and one diagram of the request path. Get the interviewer to agree before you add detail.

   “That’s the happy path end to end. Which part should we go deeper on?”

4. 4

   Deep dive

   Two or three hard parts: the hot path, the data that grows, the failure that hurts. Show options, pick one, and say what it costs.

   “Push fan-out breaks for celebrities, so I’d switch them to pull.”

5. 5

   Wrap up

   Recap, name the bottlenecks, what you would monitor, and what changes at 10× traffic.

   “At 10× the fan-out workers go first. I’d alert on queue lag.”

Mistakes that cost the most

• Drawing boxes before the requirements are agreed.
• Naming a product instead of the property you need. Say “a durable, ordered, replayable log” first, then “Kafka”.
• Presenting one option. Interviewers want the alternative you rejected and why.
• Ignoring failure. For every box, know what happens when it dies or a call to it times out.
• Designing for planet scale when the numbers say 50 requests per second.

1 day

86,400 s ≈ 10⁵ s

1 month

≈ 2.6M s

1M requests / day

≈ 12 per second

Peak traffic

≈ 2 to 3× average

KB, MB, GB, TB, PB

10³, 10⁶, 10⁹, 10¹², 10¹⁵ B

ID, timestamp

8 B each

What to take from it

• Avoid chatty calls. One round trip inside a data center (about 0.5 ms) costs as much as 5,000 memory reads. Batch requests and fetch in bulk.
• Keep hot data in memory. That is the whole case for caches like Redis.
• Read sequentially. Reading 1 MB in sequence from SSD is cheaper than 4 random 4 KB reads combined. Log structured storage (Kafka, LSM trees) exploits this.
• Put data near users. Crossing an ocean costs about 150 ms per round trip, which is why CDNs and multi-region deployments exist.
• Compress before sending. Compressing 1 KB takes microseconds; sending it across a WAN takes milliseconds.

Tip: the left and right arrow keys step through the diagram while the buttons have focus.

Caches exist at every layer: the browser, the CDN, the API gateway, an application cache such as Redis or Memcached, and the database’s own buffer pool. In interviews “add a cache” usually means an application cache, and the follow up is always the same: how does data get in, and how does stale data get out?

PACELC adds the everyday case: even with no partition, waiting for replicas to confirm (consistency) costs latency. Most tuning happens here, not during rare partitions.

Consistency models, strongest to weakest

Where it runs

Put the limiter in the API gateway or as middleware, keyed by user ID, API key or IP. Counters live in Redis so every gateway node sees the same numbers; wrap check and decrement in a Lua script (or use INCR with EXPIRE) so two nodes cannot both spend the last token. Rejected calls get 429 Too Many Requests with a Retry-After header, and well behaved clients back off exponentially.

Spot the families: booking, payments and ride matching are all contention problems; feeds, chat and notifications are fan-out problems; autocomplete, crawlers and nearby search are indexing problems.

Estimates

New URLs    100M per month ÷ 2.6M s        ≈ 40 writes/s
Redirects   100 reads per write             ≈ 4,000 reads/s, peak ≈ 8,000
Total URLs  100M × 12 months × 10 years     = 12B
Storage     12B × 500 B                     ≈ 6 TB
Code space  62⁶ ≈ 56.8B, 62⁷ ≈ 3.5T         → 7 characters gives plenty of headroom

Numbers used in these calculations

The point of these numbers is that modern machines are huge. Rules like “split the database at 100 GB” are long outdated, and sharding before the numbers demand it is a common interview mistake. At 500 GB, a URL shortener fits comfortably on one Postgres server; replicate it for availability, and shard only when throughput or size truly requires it.

POST /api/v1/urls
{ "longUrl": "https://example.com/a/long/path",
  "alias": null, "expiresAt": null }
→ 201 { "shortUrl": "https://sho.rt/zn9edcu" }

GET /zn9edcu
→ 302 Found
  Location: https://example.com/a/long/path

urls
  code        CHAR(7)    PRIMARY KEY
  long_url    TEXT
  owner_id    BIGINT
  created_at  TIMESTAMP
  expires_at  TIMESTAMP  NULL

Deep dive: generating the short code

Deep dive: 301 or 302

A 301 Moved Permanently is cached by the browser, so repeat visits never reach you. Less load, but you lose click analytics and cannot change or expire the link for that visitor. A 302 Found sends every click through your servers: more load, complete analytics. Most commercial shorteners use 302 because analytics is the product.

Deep dive: scaling reads

Redirects outnumber writes 100 to 1, and clicks concentrate on recent and viral links. Cache code → long URL in Redis with LRU eviction. If the hottest 20% of a month’s links take most of the clicks, that is 20M × 500 B = 10 GB, which fits in one Redis node. Add read replicas behind the cache, and for extreme traffic answer redirects at the CDN edge.

Estimates

Feed reads  300M DAU × 10 opens ÷ 86,400 s     ≈ 35,000 reads/s
New posts   300M DAU × 2 posts ÷ 86,400 s      ≈ 7,000 posts/s
Fan-out     7,000 posts/s × 200 followers      ≈ 1.4M feed inserts/s if we push
Feed cache  300M users × 500 post IDs × 8 B    ≈ 1.2 TB of IDs in memory

POST /v1/posts
{ "text": "...", "mediaIds": ["m_81"] }

GET /v1/feed?limit=20&cursor=1783229482342
→ 200 { "posts": [...],
        "nextCursor": "1783228190031" }

posts    post_id PK, author_id, text,
         media_ids, created_at
follows  follower_id, followee_id
feeds    user_id → [post_id, ...]
         Redis list, capped at ~500

Deep dive: push or pull

Hybrid is the standard answer: push for ordinary accounts, and for accounts above a threshold (say 100K followers) skip fan-out. At read time the feed service merges the precomputed feed with fresh posts from the few celebrities the reader follows. Skip fan-out to users inactive for 30 days too, and build their feed by pull when they come back.

Deep dive: pagination and ranking

Paginate with a cursor (the last post ID seen), never with OFFSET. New posts arriving at the top shift every offset, so page two by offset repeats items; a cursor stays stable. Ranked feeds fetch a few hundred candidates, score them by affinity, recency and engagement, and cache the ranked page for a few minutes.

Estimates

Messages     50M DAU × 40 per day ÷ 86,400 s    ≈ 23,000 messages/s
Storage      2B messages/day × 100 B            ≈ 200 GB/day, ≈ 73 TB/year
Connections  10M concurrent ÷ 100K per server   ≈ 100 chat servers

How clients stay connected

Use WebSockets for messages only. Login, profiles, group management and media uploads stay on ordinary stateless HTTP services behind a load balancer.

Deep dive: ordering with Snowflake IDs

Client clocks drift, so ordering comes from IDs the server assigns. A Snowflake ID packs a timestamp into the high bits, so sorting by ID sorts by time, and each generator can mint thousands of IDs per millisecond with no coordination.

Deep dive: storage, presence, groups

Estimates

Daily volume  10M push + 1M SMS + 5M email       = 16M per day, ≈ 185/s
Campaign peak 10M pushes in 10 minutes           ≈ 17,000/s
Log storage   16M × 500 B × 365 days             ≈ 2.9 TB per year

POST /v1/notifications
{ "eventId": "evt_8812", "userId": 42,
  "template": "payment_succeeded",
  "params": { "amount": "€50" },
  "channels": ["push", "email"],
  "priority": "high" }
→ 202 Accepted { "notificationId": "ntf_19a" }

devices        user_id, token, platform
preferences    user_id, category, channel,
               enabled, quiet_hours
notifications  id PK, event_id UNIQUE,
               user_id, channel, status,
               sent_at, opened_at

Deep dive: delivery you can trust

• Persist first. Write the notification row, then enqueue it. If a worker crashes, a sweeper finds rows stuck in PENDING and re-enqueues them.
• Deduplicate by event ID. The unique constraint on event_id means a service that publishes the same event twice still produces one notification.
• One queue per channel, with priority lanes. Login codes and payment alerts never wait behind a ten million user marketing campaign.
• Retry with exponential backoff and jitter, within each provider’s rate limits. After a fixed number of attempts, move the message to a dead letter queue and alert.
• Close the loop. Providers report delivery through callbacks; the app reports opens. Both update the status row.

Deep dive: not annoying people

Check preferences at send time, not when the message is queued, because a user may opt out in between. Cap marketing messages per user per day, hold non-urgent messages during quiet hours in the user’s own time zone, and bundle bursts into digests: “12 people liked your post” instead of twelve pings.

Estimates

Requests     10M DAU × 10 searches × 20 keystrokes = 2B per day, ≈ 23,000/s
Peak         ≈ 2×                                   ≈ 50,000/s
Prefix index ≈ 1B prefixes × 5 IDs × 8 B         ≈ 40 GB plus keys, so shard it

GET /v1/suggest?q=tw&lang=en
→ 200 Cache-Control: max-age=3600
  { "suggestions": ["twitter", "twitch",
    "twilight", "twins", "tweetdeck"] }

prefix  top 5 completions, precomputed
t       twitter, twitch, tiktok, target, translate
tw      twitter, twitch, twilight, twins, tweetdeck
twi     twitch, twilight, twins, twitter, twine

Storing the top five at every node is what makes serving fast: a lookup walks down as many nodes as the prefix has characters and returns the stored list, with no need to search the subtree below.

Deep dive: where suggestions live

Deep dive: the data pipeline

Search logs flow into a stream. A batch job counts queries over the last few weeks with older counts weighted less; a streaming job counts the last hour to catch trending terms. The scores are merged, a builder produces a new trie, writes it to object storage, and serving nodes load it and swap it in atomically. Reads never wait for writes.

Deep dive: cutting the load

• Debounce in the client: send only after a short pause in typing.
• Cache responses in the browser, and at the CDN for short prefixes, which are the hottest and identical for everyone.
• Shard by prefix range using a shard map balanced by traffic, because far more queries start with “s” than with “x”.

Estimates

Fetch rate  1B pages ÷ 2.6M s per month         ≈ 385 pages/s, peak ≈ 800
Storage     1B × 500 KB                         = 500 TB per month, ≈ 30 PB in 5 years
URL seen    10B URLs in a Bloom filter at 1%    ≈ 12 GB of memory

Deep dive: the URL frontier

Deep dive: never twice

Estimates

Searches    100M DAU × 5 searches ÷ 86,400 s     ≈ 5,800 QPS, peak ≈ 15,000
Businesses  200M × 1 KB                           ≈ 200 GB
Geo index   200M × (6 B geohash + 8 B ID)         ≈ 3 GB, fits in memory

Why a plain index fails

SELECT id FROM business
WHERE lat BETWEEN 48.853 AND 48.863
  AND lng BETWEEN 2.284 AND 2.305;

An index on latitude returns a thin strip around the whole planet, and one on longitude returns another. The database has to intersect two huge sets. What we need is a way to map two dimensions to one so that points close on the map stay close in the index.

Geohash does this. Split the world in half by longitude and write 1 if the point is in the upper half, 0 if lower. Then split by latitude, then longitude again, alternating. Every 5 bits become one base32 character, and each extra character makes the cell 32 times smaller. Nearby points usually share a prefix, so “everything in this cell” becomes a prefix lookup.

The boundary problem

Two cafés across a street can sit in different cells with no shared prefix. So never search only the user’s cell: query the cell and its eight neighbors, compute exact distances for the candidates, drop those outside the radius and sort. If too few results come back, drop one character of precision and search again.

Estimates

Normal day  1M tickets per day                  ≈ 12 per second
Big on-sale 2M fans for 50,000 seats            = 40 fans per seat
Seat map    2M fans refreshing every 5 s         = 400,000 reads/s, so cache and push

events    event_id, venue_id, on_sale_at
seats     event_id, seat_id, section, price,
          status FREE | HELD | SOLD,
          held_by, hold_expires_at, version
bookings  booking_id, user_id, event_id,
          seat_ids, payment_id, status

UPDATE seats
SET status = 'HELD', held_by = :user,
    hold_expires_at = now() + interval '10 min'
WHERE event_id = :event AND seat_id = :seat
  AND (status = 'FREE' OR
      (status = 'HELD' AND hold_expires_at < now()));
/* 1 row changed: you hold it.
   0 rows: someone else does. */

Deep dive: preventing double booking

Deep dive: surviving the on-sale

• Virtual waiting room. Fans get a place in line and a signed admission token; the booking service only accepts requests with a valid token and admits at the rate it can serve.
• Seat map from cache, changes pushed. Serve the map from a cache refreshed every second or two and push seat changes over server-sent events. The hold step is authoritative, so a slightly stale map is harmless.
• Split the hot event. One event cannot be sharded by event ID; partition its seats by section instead.

Estimates

Location    1M drivers online × 1 update per 4 s = 250,000 writes/s
Ingest      250,000 × 100 B                       ≈ 25 MB/s
Ride asks   10M rides per day                     ≈ 115/s, peak ≈ 600/s

PUT  /v1/drivers/me/location
     { lat, lng, heading, ts }
POST /v1/rides { pickup, dropoff }
→ 202 { rideId }
WS   /v1/rides/{id}/stream
→ driver position, ETA

AVAILABLE → OFFERED → ON_TRIP → AVAILABLE
               │
               └ timeout or decline → AVAILABLE

/* every transition is a compare and set */
UPDATE drivers SET status = 'OFFERED'
WHERE id = :d AND status = 'AVAILABLE';

Deep dive: where locations live

Location history still matters for fares, safety and analytics, so updates are also written to a stream such as Kafka and stored in bulk, never row by row.

Deep dive: matching

Matching asks the index for available drivers in the rider’s cell and its neighbors, then ranks them by estimated time of arrival from a routing engine on the road graph, not by straight-line distance: the closest car by air may be across a river. The best candidate gets an offer with a timeout of 10 to 15 seconds; on timeout or decline, the next candidate gets it. The compare and set on driver status guarantees no driver is offered two rides at once.

Deep dive: live tracking

During a trip, the driver app keeps sending locations; the location service publishes them on a channel for that trip, and the rider’s WebSocket receives them. Updates every few seconds are enough, because the client animates smoothly between points.

Estimates (assumptions)

Uploads  1M videos per day × 300 MB          = 300 TB per day of originals
Views    1B views per day × 100 MB            = 100 PB per day
Egress   100 PB ÷ 86,400 s                    ≈ 1.2 TB/s, about 9 Tbps
Verdict  bandwidth dwarfs everything, so the CDN is the core of the design

API

POST /v1/uploads                    → { uploadId, chunkUrls[] }
PUT  {chunkUrl}                     8 MB chunk, resumable
POST /v1/uploads/{id}/complete
GET  /v1/videos/{id}/master.m3u8    → list of renditions

Deep dive: the transcoding pipeline

Bitrates vary a lot with content and encoder; treat these as orders of magnitude.

Deep dive: adaptive bitrate streaming

Each rendition is cut into segments of a few seconds and listed in a manifest (HLS or DASH). The player downloads segments one at a time, measures throughput and how much video is buffered, and picks the quality of the next segment accordingly. That is why video drops to a blurrier picture instead of freezing when the train enters a tunnel.

Deep dive: spending to save

Newer codecs such as VP9 and AV1 need noticeably less bandwidth for the same quality but cost far more to encode. Spend that compute on popular videos, where every saved byte is multiplied by millions of views; keep the long tail on cheaper encodes. Push popular videos to edge caches ahead of demand; Netflix goes further and places its own cache servers inside internet providers’ networks.

Estimates

Commits   500M file changes per day          ≈ 5,800 commits/s
Storage   100M users × 5 GB                  = 500 PB before deduplication
Upload    a typical edit changes one 4 MB block, not the whole file

POST /v1/blocks/check { hashes: [...] }
→ which hashes the server is missing
PUT  /v1/blocks/{hash}       one 4 MB block
POST /v1/files/commit
{ path, baseVersion, blockHashes: [...] }
GET  /v1/changes?cursor=c_9812   long poll

files     file_id, namespace_id, path,
          latest_version
versions  file_id, version, block_hashes[],
          size, device_id, created_at
blocks    hash PK, storage_key, ref_count
journal   namespace_id, seq, file_id, version

Deep dive: blocks and deduplication

Split each file into blocks of about 4 MB and name every block by its SHA-256 hash. Before uploading, the client asks which hashes the server already has and sends only the missing ones. The same block stored by a million users is kept once. Fixed size blocks have one weakness: inserting a byte near the start shifts every boundary. Content defined chunking places boundaries with a rolling hash, so they move with the content and an insert changes only one or two blocks.

Deep dive: the commit protocol

1. Upload missing blocks to object storage.
2. Commit the new version with its block list and the baseVersion it was edited from.
3. The server accepts only if baseVersion is still the latest, appends to the folder’s journal and bumps latest_version, all in one transaction.
4. If another device committed first, the commit is rejected and the client saves its edit as a conflicted copy instead of overwriting.

Metadata lives in a relational database sharded by namespace (a user’s root or a shared folder), so each folder’s journal is on one shard and strictly ordered. Devices remember their position in the journal as a cursor and long poll for anything newer.

Estimates (assumptions)

Peak load  1M open documents × 2 editors × 1 op/s ≈ 2M operations/s
Servers    ≈ 10,000 active documents per server    ≈ 100+ collaboration servers
Op log     ≈ 50B ops per day × 100 B                ≈ 5 TB per day before compaction

documents   doc_id, title, owner,
            snapshot_version
snapshots   doc_id, version, content
operations  doc_id, version, author,
            op, created_at
            append only, version + 1 each

{ "doc": "d_71", "baseVersion": 4182,
  "op": { "insert": "X", "at": 1 },
  "clientOpId": "c9-0012" }
→ { "ack": "c9-0012", "version": 4183 }

Deep dive: OT or CRDT

Deep dive: one document, one server

Transformation needs a single ordering point, so every editor of a document must reach the same collaboration server. Route by doc_id with consistent hashing and a lookup service. That server holds the document in memory, assigns each operation the next version, appends it to the log, and broadcasts it. A client sends each operation with the version it was based on; if the server has moved on, it transforms the operation before applying it.

Cursors and selections are presence data: broadcast a few times per second, never persisted.

Partitioning and replication use exactly the ring from IV.3: pick a key there to see its three replicas.

Deep dive: conflicts and vector clocks

With W below N, two clients can update the same key on different replicas at once. A vector clock is a list of [server, counter] pairs attached to each version. If one version’s counters are all greater or equal, it descends from the other and wins. If neither dominates, the writes were concurrent and the system keeps both for the client to merge.

Deep dive: failures

Estimates

Payments  1M per day ÷ 86,400 s     ≈ 12 per second
Peak      Black Friday, 10×         ≈ 120 per second
Verdict   one database handles this; spend the design effort on correctness

The flow

1. Checkout sends a payment request with an idempotency key, for example the order ID. The payment service stores the order as NOT_STARTED.
2. The executor calls the PSP. Card details never touch our servers: the PSP’s hosted page or SDK turns them into a token.
3. The PSP answers, or calls our webhook later, and the order moves to SUCCESS or FAILED.
4. On success, the wallet balance and ledger entries are written in one transaction, or through the outbox pattern if they live in different services.
5. Nightly, reconciliation matches the PSP settlement file line by line against the ledger and flags every mismatch.

Deep dive: the double entry ledger

Every transaction debits and credits the same total, so the sum of all entries is always zero. Entries are append only: a refund is a new pair of entries, never an edit. If the books ever fail to balance, you can trace exactly which transaction broke them.

Deep dive: retries and distributed steps

• Retry with exponential backoff and jitter: about 1, 2, 4, 8 seconds, each randomized so thousands of clients do not retry in lockstep. Then stop and alert.
• Check before retrying an unknown outcome: query the PSP for the payment’s status using the same key.
• Outbox pattern: write the state change and the event to publish in the same database transaction; a relay publishes the event afterwards. No “saved but never announced” gaps.
• Saga for multi-step flows: each step has a compensating action (a refund undoes a charge) instead of a distributed lock.
• Store money as integers in minor units (cents) with a currency code. Floating point cannot represent 0.10 exactly.