Skip to content

system.md

Latest commit

 

History

History
289 lines (191 loc) · 24.9 KB

system.md

File metadata and controls

289 lines (191 loc) · 24.9 KB
Raw

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

Real-time delivery to clients

Transport Direction Note
Short polling client pulls simple, wasteful, latency = interval
Long polling client pulls, server holds works everywhere, one request per message
SSE server → client plain HTTP, auto-reconnect with Last-Event-ID, text only
WebSocket both ways stateful connections — needs a connection registry to find the server holding a user
  • 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

Pattern Write path Read path Trade-off
Cache-aside app writes DB, invalidates cache miss → read DB, fill cache most common; stale until TTL/invalidation
Read-through — cache loads from DB on miss cache owns the loading logic
Write-through write cache + DB together cache always warm slower writes; the two writes aren't atomic, so a crash or race can still diverge them
Write-behind write cache, flush DB async fast writes risk of data loss before flush

Eviction and stampedes

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

B-tree vs LSM-tree

B-tree (PostgreSQL, MySQL) LSM-tree (RocksDB, Cassandra)
Writes in-place page updates, random I/O append to an in-memory memtable → flush immutable sorted files (SSTables)
Reads one tree walk, predictable may check several files; bloom filters skip most
Background work page splits, vacuum compaction
Fits read-heavy, range scans write-heavy

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

Algorithm Behavior Note
Token bucket tokens refill at a fixed rate allows bursts up to bucket size; most common
Leaky bucket requests drain at a constant rate smooth output, no bursts
Fixed window counter count per time window simple; up to 2× limit at window boundary
Sliding window log/counter exact or blended count accurate; counter variant is cheap

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.
Tier What runs in the standby region RTO / RPO
Backup and restore nothing; restore from backups hours / hours
Pilot light replicated data, compute off tens of minutes / minutes
Warm standby a scaled-down copy minutes / seconds
Active-active full capacity everywhere ~zero / ~zero with sync replication
  • 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

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.