System Design¶

Key system design building blocks and trade-offs, grouped by subtopic. For CAP, consistency, replication, and sharding internals, see distributed.md; for API design, idempotency, and outbox, see backend.md; for auth and web security, see security.md.

Interview framework¶

Structure and estimates¶

• Order: requirements (functional + scale, latency, availability, consistency) → estimates → API → data model → high-level design → deep dive on the hardest 1–2 parts → bottlenecks and trade-offs.
• Latencies: RAM read ~100 ns, SSD random read ~100 µs, same-DC round trip ~0.5 ms, cross-continent ~150 ms.
• Downtime per year: 99.9% ≈ 8.8 h, 99.99% ≈ 53 min, 99.999% ≈ 5 min.

Back-of-envelope conversions¶

• 1 day ≈ 86,400 s ≈ 10⁵ s, so 1M requests/day ≈ 12 QPS; assume peak ≈ 2–3× average unless told otherwise.
• 1 KB × 1M items = 1 GB; 1 KB × 1B = 1 TB.
• Ballpark capacity (varies with workload): a well-indexed PostgreSQL box handles 10k+ simple queries/s; Redis ~100k ops/s per core.
• Little's law L = λ × W: requests in flight = throughput × latency — 1,000 RPS × 200 ms = 200 concurrent requests, which sizes thread pools, connection pools, and queues.

Traffic and edge¶

Load balancing¶

• L4 balances by IP/port, fast, no inspection; L7 reads HTTP (path, headers, cookies) for content routing and retries, at higher CPU cost.
• Algorithms: round robin, weighted, least connections (uneven request lengths), IP/consistent hash (same key → same server, good for caches).
• Sticky sessions defeat statelessness and unbalance load — move session state to a shared store instead.

Balancing long-lived connections¶

• HTTP/2 and gRPC multiplex all requests over one long-lived connection, so an L4 balancer pins a client to one backend and new replicas get no traffic.
• Fix with L7 (per-request) balancing, client-side balancing, or a maximum connection age that forces reconnects.
• WebSockets have the same problem after scale-out: rebalance by closing connections gradually.

Proxies and gateways¶

• Reverse proxy (Nginx, Envoy): TLS termination, load balancing, caching in front of servers.
• API gateway: auth, rate limiting, routing, aggregation for north–south traffic; a BFF is one gateway per client type.
• Service mesh (Istio, Linkerd): sidecar proxies (or per-node proxies in Istio ambient mode) handle east–west traffic — mTLS, retries, telemetry without app changes.

Real-time delivery to clients¶

• Push to many clients means stateful servers: plan for reconnect storms after a deploy (jittered reconnects).

CDN and object storage¶

• Pull CDN fetches from origin on first miss; push CDN is pre-uploaded (large, rarely changing files). Invalidate with versioned filenames, not purges.
• Object storage (S3, GCS) holds blobs cheaply and durably; keep only metadata in the database and use pre-signed URLs so transfers bypass app servers.

Caching¶

Strategies¶

Eviction and stampedes¶

• Eviction: LRU (most common), LFU, TTL.
• Cache stampede: many concurrent misses on a hot key hit the DB at once — fix with request coalescing (single-flight), a lock, or probabilistic early refresh.
• Jitter TTLs so keys written together don't expire together.

Cache and database consistency¶

• On write, delete the key rather than updating it, so concurrent writers can't leave an older value in place.
• Cache-aside still races: a slow reader can refill the cache with a value read before the write — bound it with a TTL, a delayed second delete, or leases (Facebook memcache).
• For many writers, invalidate from the database's change stream (CDC) instead of from application code.

Data storage choices¶

SQL vs NoSQL¶

• NoSQL families by access pattern: key-value, document, wide-column (heavy writes, time series), graph; model tables around queries, not entities.
• Pick NoSQL only for a named reason (write volume, schema flexibility, access pattern). Product internals in postgresql.md and redis.md.

B-tree vs LSM-tree¶

• Compaction strategy trades read, write, and space amplification against each other.

Search and analytics stores¶

• An inverted index maps each term to the documents containing it; relevance scoring is usually BM25.
• Elasticsearch/OpenSearch are near-real-time (new docs searchable after a refresh, ~1 s default), and the primary shard count is fixed at index creation — resize by reindexing or split/shrink.
• OLAP stores use column storage, compression, and vectorized scans of few columns over many rows, with star schemas (facts + dimensions).
• Treat search indexes and warehouses as derived stores, fed by CDC from the source of truth.

Scaling ladder¶

• Cheapest first: query/index tuning → caching → read replicas → vertical scaling → split databases by domain → sharding.
• Sharding needs a high-cardinality, evenly spread key; cross-shard joins and transactions become the app's problem.
• Denormalization trades write complexity for read speed; CQRS separates the models entirely (distributed.md).

Asynchronous processing¶

Queue semantics¶

• Queues decouple producers from consumers, absorb spikes, and move slow work off the request path.
• Delivery is at-least-once, so consumers must be idempotent; route repeatedly failing messages to a dead-letter queue.
• Fan-out: pub/sub (SNS, Kafka topics) delivers each event to many subscribers independently.

Queues vs logs¶

• RabbitMQ/SQS (queue): a message is removed once acknowledged — distributes tasks among workers.
• Kafka (log): a durable append-only log; each consumer group tracks its own offset, so many groups can replay the same data.
• Partitioning and ordering: see distributed.md.

Rate limiting¶

Rate-limiting algorithms¶

Distributed rate limiting¶

• Enforce at the gateway, keyed by user, API key, or IP; reject with 429 and Retry-After.
• Share counters in Redis so every server sees one limit; wrap INCR + EXPIRE in MULTI or a Lua script, or a crash between them leaves a counter with no TTL.
• A local per-instance limiter skips the round trip but is only approximate (limit ÷ instances).

Reliability and operations¶

Availability math¶

• Components in series multiply: 99.9% × 99.9% ≈ 99.8%.
• Redundant components in parallel fail only together: 1 − 0.001² ≈ 99.9999%.
• Both formulas assume independent failures; a shared zone or dependency wipes out most of the parallel redundancy gain.

Multi-region and disaster recovery¶

• RPO = acceptable data loss, RTO = acceptable recovery time; together they pick the tier.

• Async cross-region replication means RPO > 0; active-active also needs conflict handling or a home region per record, plus global routing (GeoDNS, anycast).
• A failover that was never rehearsed rarely works: run regular game days.

SLIs, SLOs, error budgets¶

• SLI = what's measured, SLO = internal target, SLA = contractual promise (looser than the SLO).
• The gap to 100% is the error budget — spend it on releases, slow down when it's exhausted.
• Alert on SLO burn rate and user-felt symptoms, not on every cause (CPU at 80%).

Observability¶

• Metrics: numeric time series (Prometheus); golden signals latency, traffic, errors, saturation — RED for services, USE for resources.
• Logs: structured, centralized, tagged with a request ID. Traces: a request's span tree across services (OpenTelemetry).
• Metrics say something is wrong, traces say where, logs say why.
• Percentiles can't be averaged across hosts or time windows: merge the histograms (or sketches), then take p99.
• High-cardinality labels (user ID, request ID) multiply Prometheus time series; keep them in logs and traces.

Architecture¶

Monolith vs microservices¶

• Default to a modular monolith: in-process calls and local transactions, with module boundaries that could later become services.
• Extract a service for a concrete reason (independent scaling, deploy cadence, team ownership); boundaries mirror teams (Conway's law).

Service discovery¶

• Instances register with a registry (Consul, etcd, Eureka) and drop out on failed health checks; clients or a load balancer resolve names to healthy instances.
• Kubernetes does this natively with Service DNS names — see devops.md.

Probabilistic and spatial structures¶

Bloom filter¶

• Set membership in a bit array with k hash functions: "definitely not" or "probably yes" — no false negatives.
• Can't delete (a counting variant can); used to skip disk lookups (LSM trees) and dedupe crawled URLs.

Count-min sketch and HyperLogLog¶

• Count-min sketch estimates per-item frequency in fixed memory — heavy hitters, top-k in a stream.
• HyperLogLog estimates distinct counts in ~12 KB with ~0.8% error (Redis PFADD/PFCOUNT).

Geospatial indexes¶

• Geohash encodes lat/lon as a string: a shared prefix means nearby, but close points can straddle a cell boundary and share none.
• Pick a precision whose cell is at least the search radius, then query the cell and its 8 neighbors.
• A quadtree subdivides dense areas further, adapting to uneven density; Google S2 and Uber H3 use hierarchical cells the same way.

Classic designs: user-facing¶

URL shortener¶

• Read-heavy (~100:1); base62 in 7 characters gives ~3.5 trillion keys.
• Keys from hash + collision check, a counter encoded in base62 (predictable unless shuffled), or a pre-generated key pool.
• 301 is cached by browsers by default (less load, lost clicks); 302 isn't cached without explicit freshness headers, so every click hits you (analytics). Collect analytics asynchronously.

News feed¶

• Fan-out on write: precompute followers' feeds at post time — instant reads, but a celebrity triggers massive write amplification.
• Fan-out on read: merge followees' posts at read time — slower reads, no amplification.
• Hybrid: push for normal accounts, pull for celebrities; store post IDs, hydrate from cache, rank as a separate step.

Chat system¶

• A persistent WebSocket per client; a connection registry (user → server) routes messages via pub/sub.
• A server-assigned per-conversation sequence number orders messages; a client-generated message ID dedupes retries.
• Offline users get a push notification and fetch on reconnect; large groups hit the same fan-out problem as feeds.

Typeahead¶

• A trie (or prefix index) with precomputed top-k suggestions per node, built offline from query logs and cached aggressively.
• Debounce on the client; for semantic matches, query an approximate nearest-neighbor index (HNSW).

Video streaming¶

• Upload to object storage → a transcoding pipeline splits the video into chunks and encodes them in parallel at several resolutions and bitrates.
• Package as HLS or DASH: 2–10 s segments plus a manifest listing the renditions, served from a CDN.
• The player picks a rendition per segment from measured bandwidth and buffer (adaptive bitrate), so quality drops instead of stalling.
• Pre-warm popular titles at the edge; the long tail streams from regional caches or the origin.

Notification system¶

• One API → a queue per channel (push, SMS, email) → workers calling providers (APNs, FCM, Twilio) with retries.
• Dedupe by notification ID, respect user preferences and rate limits, track delivery status per message.

Proximity service¶

• Index places by geohash prefix or quadtree cell; search the cell plus neighbors, then filter by exact distance.
• Static places are read-heavy — cache per cell; moving objects (drivers) report every few seconds into an in-memory index (Redis GEO).

Classic designs: data and infrastructure¶

Web crawler¶

• A URL frontier of per-host queues enforces politeness (one connection per host, robots.txt, crawl delay) and priority.
• Dedupe URLs with a seen-set (Bloom filter at scale) and content with checksums or SimHash.
• Cache DNS; guard against spider traps with URL depth and length limits.

File sync¶

• Split files into chunks (~4 MB) addressed by content hash: upload only changed chunks and dedupe identical ones across users.
• A metadata service stores file → chunk list and versions; other devices get change notifications via long polling or WebSocket.
• Concurrent edits produce a conflicted copy rather than a silent overwrite.

Metrics and click aggregation¶

• Events flow through Kafka into a stream processor that aggregates per key per tumbling window, by event time with watermarks (distributed.md).
• Keep raw events so aggregates can be recomputed after a bug; dedupe by event ID.
• Pre-aggregate hot keys locally before the shuffle.

Distributed job scheduler¶

• Store jobs with next_run_at; workers claim due rows with FOR UPDATE SKIP LOCKED or a lease, so each run has one owner.
• An expired lease hands a dead worker's job to another, so jobs must be idempotent.
• At high volume, partition jobs by ID or bucket them by time (a timing wheel).

Payments and ledgers¶

• A double-entry ledger: every transaction is balanced debits and credits; rows are append-only, corrections are new entries.
• Idempotency keys on every provider call; reconcile against provider reports daily.
• Store amounts as integer minor units with a currency, never floats.

Leaderboard¶

• A Redis sorted set: ZINCRBY updates a score and ZREVRANK returns a user's rank in O(log n); ZRANGE ... REV reads the top k in O(log n + k); internals in redis.md.
• Beyond one node, shard by score range or keep per-shard top-k and merge.

Booking and inventory contention¶

• Overselling comes from check-then-write races: use conditional updates (UPDATE ... SET left = left - 1 WHERE id = ? AND left > 0) or row locks.
• For seat selection, place a temporary hold with a TTL that expires if payment doesn't finish; a waiting room absorbs flash-sale spikes.