High-Level Design (HLD) | Interview Prep

HLD Interview Framework

HLD Interview Framework — Always Follow This

Clarify (5 min) — Functional requirements (what features?), Non-functional (scale, latency, consistency, availability)
Estimate (3 min) — DAU, RPS, Storage, Bandwidth
High-Level Design (5 min) — Draw major components: clients, LBs, services, DBs, caches, queues
API Design (3 min) — Endpoints, request/response schema
Deep Dive (15 min) — Critical components, bottlenecks, tradeoffs
Wrap Up (3 min) — Failure modes, monitoring, future scaling

Back-of-Envelope Estimation

Back-of-Envelope Estimation Cheat Sheet

Must Know

Powers of 2 & Data Sizes

Unit	Value
1 KB	10³ bytes = 1,000 bytes
1 MB	10⁶ bytes
1 GB	10⁹ bytes
1 TB	10¹² bytes
1 PB	10¹⁵ bytes
1 char / 1 UUID	1 B / 36 B
1 image (compressed)	~300 KB
1 video min (720p)	~50 MB

Latency Numbers Every Engineer Knows

Operation	Latency
L1 cache read	0.5 ns
RAM access	100 ns
SSD random read	100 µs
HDD seek	10 ms
Redis GET (same DC)	~0.5 ms
DB query (indexed)	~1-5 ms
Cross-DC round trip	~150 ms
1 GB network transfer	~10 ms (10Gbps)

Quick Estimation Formulas

RPS from DAU: DAU × avg_requests_per_day / 86,400 (seconds/day)
Peak RPS: avg_RPS × 2–3× (typical peak-to-average ratio)
Storage per year: write_RPS × record_size × 86,400 × 365
Bandwidth: peak_RPS × avg_response_size (bytes/s → MB/s)
Rule of thumb: 1M DAU → ~12 RPS avg for a simple app; 100M DAU → 1,200 RPS avg

Architecture Styles

Architecture Styles: Monolith → SOA → Microservices → Serverless → Event-Driven

Architecture

Style	Description	Best For	Avoid When
Monolith	All modules in one deployable unit	Early-stage, small team, <100K DAU	Different components need independent scaling
SOA	Services communicate via ESB/SOAP	Enterprise with legacy integration	Greenfield cloud-native projects
Microservices	Small autonomous services, REST/gRPC	Large teams, independent scaling, different tech stacks	Small teams (operational overhead kills velocity)
Serverless (FaaS)	Functions triggered by events, no server management	Irregular traffic, event processing, glue code	Long-running jobs, latency-critical (cold starts)
Event-Driven	Services communicate via events (Kafka)	Async workflows, decoupling producers from consumers	When immediate consistency is required

Evolutionary Path: Monolith (Day 1) Identify bounded contexts (user service, order service, payment) Modular Monolith (extract modules with clear interfaces) When specific module hits scaling limits Microservices (extract high-scale components first: search, recommendations) For unpredictable spiky traffic Serverless (image resizing, scheduled jobs, webhooks)

Storage Systems

Storage Systems — Object, Block, File Storage

Infrastructure

Type	How	Access	Use Cases	Examples
Object Storage	Flat namespace of objects (key=path, value=blob)	HTTP (GET/PUT), eventual consistency	Images, videos, backups, static assets, data lake	S3, GCS, Azure Blob
Block Storage	Raw blocks, like virtual disk; OS mounts as filesystem	Low-latency I/O (iSCSI, NVMe)	Database volumes, VMs, boot disks	AWS EBS, Azure Disk
File Storage (NFS)	Hierarchical filesystem, shared across instances	NFS/SMB mount	Shared config, CMS assets, ML training data	AWS EFS, Azure Files
In-Memory	RAM-based, volatile (or durable with persistence)	Sub-millisecond	Cache, sessions, leaderboards, queues	Redis, Memcached
Columnar Store	Store data column-by-column (efficient for analytics)	SQL	OLAP, data warehouse, aggregation queries	Snowflake, BigQuery, Redshift

Rule of Thumb

User uploads → Object Storage (S3). Database needs disk → Block Storage (EBS). Shared files between instances → File Storage (EFS). Analytics at scale → Columnar Store (BigQuery/Snowflake).

Message Queues & Event Streaming

Message Queues & Event Streaming — Deep Dive

Critical

Kafka Architecture — Producer → Topics → Consumer Groups

Producer AOrder Service

Producer BPayment Service

Producer CUser Service

→ write →

Topic: orders3 partitions

Topic: payments3 partitions

Topic: events6 partitions

→ read →

Consumer Group AEmail Workers

Consumer Group BAnalytics Workers

Consumer Group CFulfillment Workers

Each producer appends to partition (hash key)

Retained on disk (days/weeks)

Each group reads independently (own offset)

	Kafka	RabbitMQ	AWS SQS	AWS SNS
Model	Pub/Sub + Log (pull)	AMQP queue (push)	Queue (pull)	Topic fan-out (push)
Retention	Days/weeks (log-based)	Until consumed	14 days max	N/A (fire-and-forget)
Ordering	Per partition	Per queue	FIFO queue option	No
Throughput	Millions/sec	50K–100K/sec	Managed, high	Managed
Consumer groups	Yes (replay, multiple)	Competing consumers	No (one consumer)	Multiple subscriptions
Best For	Event streaming, audit log, real-time pipelines	Task queues, RPC	Decoupling AWS services	Fan-out notifications

Message Delivery Semantics

At-most-once: fire-and-forget. May lose messages. Best for logging/metrics where loss is OK.
At-least-once: retry until ack. May duplicate. Consumer must be idempotent. Kafka default.
Exactly-once: hardest to achieve. Kafka Transactions + idempotent producer. Use for financial events.

When to Use a Message Queue in HLD

Decouple services: Order service publishes, Inventory/Email/Notification consume independently
Absorb traffic spikes: Queue acts as buffer; downstream processes at sustainable rate
Async workflows: Video transcoding, report generation, email sending don't block API response
Event sourcing: Kafka as immutable ordered event log
Fan-out: One event triggers multiple downstream consumers in parallel

Data Processing

Data Processing — Batch vs Stream vs Lambda Architecture

Data Engineering

Model	Latency	Throughput	Complexity	Tools	Use Case
Batch Processing	Hours	Very High	Low	Spark, Hadoop MapReduce	Daily reports, ML training, ETL
Stream Processing	Seconds–ms	High	Medium	Kafka Streams, Flink, Spark Streaming	Real-time dashboards, fraud detection, alerting
Micro-batch	Minutes	High	Low-Med	Spark Structured Streaming	Near-real-time analytics (acceptable delay)

Lambda Architecture

Batch Layer: Processes all historical data (S3 → Spark → data warehouse). Accurate but slow.
Speed Layer: Processes real-time stream (Kafka → Flink). Low latency but approximate.
Serving Layer: Merges batch + speed layer results for queries.
Kappa Architecture (simpler): Only stream processing layer; reprocess history by replaying Kafka. Eliminates batch/speed duplication. Preferred modern approach.

Data Pipeline (typical modern stack): Raw events Kafka (stream) Flink / Spark Streaming (real-time transform, aggregate) Redis (for live dashboards) ClickHouse / Druid (for OLAP queries) S3 Data Lake (raw + transformed) dbt + Snowflake (daily batch aggregations for BI) Looker / Tableau (dashboards)

Content Delivery Network

Content Delivery Network (CDN) — Full Architecture

Performance

CDN — Tiered Cache Hierarchy

User (Mumbai)

→ DNS Anycast →

Edge PoPMumbai <10ms

MISS ↓

Regional CacheSingapore

MISS ↓

Origin Shieldsingle ingress to origin

MISS ↓

Customer OriginApp Server / S3

Cache HIT at Edgesub-10ms

Cache HIT at Region~30ms

Origin Request~200ms

CDN Hierarchy: User (Mumbai) DNS Anycast IP routes to nearest PoP Edge Node (Mumbai PoP, <10ms away) Cache HIT return immediately (sub-10ms) Cache MISS request to Regional Cache (Singapore) Cache MISS request to Origin (US) Response cached at Origin CDN Response cached at Regional Edge User CDN PoP (Point of Presence): SSD Cache + Nginx/Varnish + TLS termination + Anycast routing Pull CDN: Edge pulls from origin on cache miss, caches result (Cloudflare) Push CDN: You push content to CDN upfront (Akamai, good for known assets) Cache-Control Headers: Cache-Control: public, max-age=86400, s-maxage=604800 Surrogate-Control: max-age=2592000 (CDN-specific override) Vary: Accept-Encoding (cache separate version per encoding)

What Goes on CDN vs Origin

CDN (cache at edge)	Origin only (don't cache)
Static: JS, CSS, images, videos	User-specific API responses
Public API responses (product listings)	Cart, checkout, payment
ML model weights, binaries	Session-dependent pages
HLS/DASH video segments	Real-time data (stock prices)

Cache Invalidation Strategies

Versioned URLs: /bundle.v2.3.0.js (no invalidation needed — new URL = new cache entry). TTL: set short TTL (5min) for semi-static content. Purge API: POST /purge {urls} to Cloudflare/Fastly on deploy. Surrogate keys (cache tags): tag multiple URLs, purge by tag.

Distributed Consensus

Distributed Consensus — Raft & Paxos

Advanced

Why Consensus Matters in HLD

Multiple nodes must agree on a single value (leader election, config, who owns a lock)
Used by: etcd (Kubernetes config), Zookeeper (Kafka broker election), CockroachDB, Consul

Raft Consensus (Leader-based, easier to understand than Paxos): Roles: Leader | Follower | Candidate 1. Leader Election: All nodes start as Followers with random election timeout (150-300ms) If no heartbeat received, node becomes Candidate RequestVote to all peers; majority wins leader for this term 2. Log Replication: Client writes to Leader Leader appends to own log, sends AppendEntries to all followers When majority (quorum) ack, commit entry, apply to state machine Leader sends commit in next heartbeat to followers 3. Safety: a node only votes for candidate with at least as up-to-date log Quorum = floor(N/2) + 1 3 nodes: quorum = 2 (tolerates 1 failure) 5 nodes: quorum = 3 (tolerates 2 failures)

In Interviews

You rarely need to implement Raft. Know: it's used for leader election and replicated state machine. etcd/Zookeeper use it. Quorum = N/2+1. It tolerates at most (N-1)/2 failures. Split-brain prevention: partitioned minority cannot elect a leader.

Observability

Observability: Metrics, Logs, Traces (The Three Pillars)

Operations

Pillar	What it captures	Tools	Use for
Metrics	Aggregated numeric data over time (RPS, latency p99, error rate, CPU)	Prometheus + Grafana, DataDog, CloudWatch	Alerting, capacity planning, SLA monitoring
Logs	Discrete events with context (request logs, error stack traces)	ELK Stack, Loki, Splunk, Fluentd	Debugging, audit trail, root cause analysis
Traces	End-to-end request path across microservices with span timings	Jaeger, Zipkin, AWS X-Ray, OpenTelemetry	Find bottleneck services, latency breakdown

SLI / SLO / SLA

SLI (Service Level Indicator): Measured metric — e.g., p99 latency = 120ms, error rate = 0.1%
SLO (Service Level Objective): Target — e.g., p99 < 200ms, availability > 99.9% ("three nines")
SLA (Service Level Agreement): Contractual commitment with penalty — "99.9% uptime or credit"
Error Budget: 99.9% SLO = 0.1% error budget = 43.8 min/month of allowed downtime

KEY Alerts Every System Needs

Error rate > 1% for 5 min — page on-call
p99 latency > 2× baseline for 5 min — alert
Queue depth growing (Kafka consumer lag) — scale up consumers
DB connection pool saturation — add read replicas
Cache hit rate drops below 90% — investigate cold start or eviction

Service Mesh & Service Discovery

Microservices

Service Discovery — How Microservices Find Each Other

Client-side discovery: Service A queries registry (Consul/Eureka) directly and load-balances itself. More control but coupling to registry library.
Server-side discovery: Client calls LB (ELB, NGINX), LB queries registry. Simpler clients, extra hop.
DNS-based (Kubernetes): Each service gets a stable DNS name (order-service.default.svc.cluster.local). kube-dns resolves to ClusterIP. Most common modern approach.

Service Mesh (Istio / Linkerd): Each pod gets a sidecar proxy (Envoy) All traffic goes: Service A Envoy (sidecar) network Envoy (sidecar) Service B Control Plane provides: mTLS between all services (zero-trust security) Traffic policies (retries, timeouts, circuit breaker) without code changes Observability (auto-traces, metrics per service pair) Canary deployments (route 5% traffic to v2 via traffic weights) When to use Service Mesh: Large microservice fleet (>20 services) where cross-cutting concerns (security, observability, traffic management) become unmanageable per-service.

Geospatial Systems

Geospatial Systems — Geohashing & Quadtrees

Location

Geohash: Encodes (lat, lng) to a string: (37.7749, -122.4194) "9q8yy" Nearby locations share common prefix: "9q8yy" neighbors share "9q8y" Precision: 6 chars ≈ 1.2km×0.6km, 8 chars ≈ 38m×19m Stored as indexed VARCHAR in DB range query = prefix LIKE '9q8y%' Edge case: points near geohash boundary are geographically close but have different prefixes. Solution: also check 8 neighboring cells. Quadtree: Divide 2D space into 4 quadrants recursively until each cell has ≤ N points (e.g., 100 drivers per cell) Dynamic: densely populated areas get more subdivisions (NYC vs rural) Used by: Google Maps for rendering, Uber for driver partitioning S2 (Google): Divides sphere into hierarchical cells at 30 levels Level 12 ≈ city block, Level 30 ≈ 1cm² All cells same shape (low distortion) Used by: Google Maps, Foursquare, Uber

Nearby Search Query Patterns

Redis GEORADIUS: GEORADIUS drivers 37.77 -122.41 5 km → O(N+log M). Best for real-time moving objects (Uber drivers).
PostGIS: SELECT * FROM restaurants WHERE ST_DWithin(location, ST_MakePoint(-122.41, 37.77), 5000). Best for persistent geo data with complex queries.
Elasticsearch geo_distance: Full-text + location combined query. Good for POI search ("coffee near me").

Collaborative Editing

Operational Transformation & CRDTs (Collaborative Editing)

Real-time Collab

The Problem: Concurrent Edits

User A inserts "X" at position 5. User B simultaneously deletes char at position 3.
After A's op reaches B and B's op reaches A — both must converge to same document.

Operational Transformation (OT) — Google Docs approach: Each op: {type: insert|delete, position, char, clientId, revision} Server acts as central authority (serializes all concurrent ops): Op from User A @ revision 5 Op from User B @ revision 5 (concurrent) Server receives both, transforms B's op against A's op: transform(opB, opA) adjust position to account for A's insert Server applies both, sends transformed ops to all clients Properties: CONVERGENCE (all clients reach same state) + INTENTION PRESERVATION CRDTs (Conflict-free Replicated Data Types) — newer approach (Figma, Notion): Data structure designed so concurrent ops always merge deterministically No central server needed for conflict resolution (peer-to-peer possible) Text CRDT (e.g., RGA, YATA): each character has unique ID + tombstone for delete Insert: new char gets ID = (clientId, lamportClock), positioned relative to neighbors Merge: union of character sets sorted by unique IDs = deterministic order Pros: works offline, peer-to-peer, simpler server Cons: higher memory (tombstones accumulate), harder to implement Used by: Figma (vector graphics), Automerge, Yjs libraries

Interview Answer

For Google Docs / collaborative editor: use OT with a central server (industry-proven, Google uses it). Server serializes all ops and transforms them against each other. Clients maintain shadow copy + local revision counter. For truly distributed / offline-first: CRDTs (Figma approach). Trade-off: CRDTs have higher memory overhead.

Search Architecture

Search Architecture — Inverted Index & Elasticsearch Internals

Search

Inverted Index (core of full-text search): Documents: Doc1: "the quick brown fox" Doc2: "the lazy brown dog" Doc3: "quick brown dog" Inverted Index: "brown" → [Doc1(pos:3), Doc2(pos:3), Doc3(pos:2)] "quick" → [Doc1(pos:2), Doc3(pos:1)] "fox" → [Doc1(pos:4)] Query "quick brown": intersect posting lists for "quick" AND "brown" Result: Doc1, Doc3 (sorted by TF-IDF or BM25 relevance score) Elasticsearch Architecture: Index = collection of shards (distributed across nodes) Primary shard: handles writes, routes to replica shards Replica shard: handles reads, provides failover Write path: Client Primary shard (write + WAL to translog) Replica shards (parallel replication) Refresh (default 1s): flush to in-memory segment (searchable!) Flush (30min or size): commit segment to disk, clear translog Read path: Query broadcast to all shards (scatter-gather) Each shard returns local top-K hits Coordinating node merges, re-ranks, returns global top-K

Relevance Scoring — BM25

TF (Term Frequency): how often term appears in document (more = more relevant)
IDF (Inverse Document Frequency): how rare the term is across all docs (rare = more distinctive)
BM25: improved TF-IDF, saturates TF (very high TF doesn't dominate) — Elasticsearch default since v5
Vector Search (ANN): embed text to dense vector (BERT/OpenAI), find nearest neighbors by cosine similarity. Used for semantic search. Tools: FAISS, Elasticsearch knn, Pinecone.

Idempotency & Exactly-Once

Idempotency & Exactly-Once Semantics

Reliability

Why Idempotency Matters

Networks fail. Client retries. Server may have processed request before failure — duplicate operation risk.
Idempotent operation: applying it multiple times = same result as applying once.
GET, PUT, DELETE are naturally idempotent. POST (create) is NOT.

Idempotency Key Pattern: Client generates unique key: X-Idempotency-Key: uuid-v4 Server: SET idempotency:{key} processing EX 86400 (Redis, NX) If NX fails (key exists): request already processed, return cached response On success: store result in Redis with TTL On failure: delete key so client can retry Useful for: POST /payments, POST /orders, email sending, SMS Database-level Idempotency: INSERT INTO orders (idempotency_key, ...) ON CONFLICT (idempotency_key) DO NOTHING -- or return existing row Kafka Idempotent Producer: enable.idempotence=true Producer gets PID, sequence per partition Broker deduplicates messages within session (exactly-once within producer lifetime) For cross-session: Kafka Transactions (atomic multi-partition writes)

Capacity Planning

Capacity Planning & Horizontal Scaling Checklist

HLD Process

When to Introduce Each Component

Scale Milestone	Introduce
<1K RPS	Single server, managed DB (RDS), no cache needed
1K–10K RPS	Read replicas, Redis cache, CDN for static assets
10K–100K RPS	Horizontal stateless app servers, LB, DB connection pooling (PgBouncer)
100K–1M RPS	DB sharding or NoSQL, Kafka for async, microservices for hot paths
>1M RPS	Multi-region, global LB (Anycast), custom distributed storage

Stateless Service Design (Required for Horizontal Scaling)

No session stored in memory → store in Redis
No uploaded files stored locally → stream to S3
No sticky state in app server → any instance can serve any request
Config from environment or config service (not baked into binary)
Health check endpoint (/health) for load balancer probing
Graceful shutdown: drain in-flight requests before terminating on scale-down

HLD System Design Interview Questions

Big Infrastructure Questions

These are the most common HLD questions at top-tier companies (Google, Meta, Amazon, Uber). Each requires a full 45-min design. Know the key components, trade-offs, and deep-dive areas for each.

HLD-1

Design Google Docs (Collaborative Document Editor)

▶

Requirements: Multiple users edit same document simultaneously in real-time. Changes visible to all within <100ms. Support text, formatting, comments, version history, offline editing, cursor presence.

Scale: 1B documents, 100M DAU, up to 100 concurrent editors per doc. 99.99% availability.

Core Challenge: Conflict resolution when concurrent edits happen. How do two users editing position 5 simultaneously converge to the same document?

Google Docs — Real-time Collaborative Architecture

User ABrowser (OT)

User BBrowser (OT)

User CBrowser (OT)

↓ WebSocket (persistent connection)

Load Balancerconsistent hash on docId

↓ sticky session per document

Doc Server Aowns Doc #1234

Doc Server Bowns Doc #5678

↓

RedisdocId → server routing

Kafkaop-log topic

↓

CassandraOp Log (append-only)

S3Snapshots every 1000 ops

MySQLMetadata + ACL

Architecture: Client (Browser / Mobile) Local Document State (shadow copy + pending ops queue) WebSocket connection to Doc Server (sticky session via consistent hash on docId) Doc Server (one per active document session): Receives op from User A: {type:insert, pos:5, char:'X', rev:42, clientId:'A'} Transforms op against any concurrent ops received (OT algorithm) Appends to document Op Log (ordered) Broadcasts transformed op to all connected clients Persists to Op Storage Storage: Op Log: Cassandra (append-only, docId + revision as PK, fast writes) Document Snapshots: S3 (full doc state every 1000 ops for fast load) Metadata: MySQL (doc title, owner, ACL, created_at, last_modified) Redis: active session routing (docId → server instance mapping) Real-time Sync (OT): Server serializes all ops (single authority) Client sends: op + base_revision Server transforms op against all ops since base_revision Committed op broadcast with new revision number to all clients Client algorithm: Applied locally immediately (optimistic): instant feedback Receive server ack: adjust revision counter Receive other user's op: transform against local pending ops

Cursor Presence & Awareness

Each user's cursor position = op with {type: cursor, pos, userId, color}
Broadcast via same WebSocket channel but not persisted (ephemeral)
Throttled: send cursor updates max every 50ms (debounce)
Display: other cursors rendered as colored carets with username label

Offline Editing & Sync

Client stores pending ops in IndexedDB while offline
On reconnect: send all buffered ops with last-known revision
Server replays and transforms against ops committed while offline
CRDTs (alternative): Automerge/Yjs — no server-side transformation needed, peer-to-peer merge

Key Design Decisions

OT with central server: battle-tested, Google's actual approach
Cassandra for op log: append-only + high write throughput
Snapshot every N ops: fast doc load without replaying all ops
WebSocket per doc server: low latency, stateful connection
Consistent hashing on docId: all clients of same doc → same server

Deep Dive Questions

How to handle server crash during active session? (Redis TTL + reconnect)
How to load a 500-page doc quickly? (latest snapshot + delta ops)
Permission check on every op? (token in WebSocket handshake, server enforces)
Comments vs inline edits: separate op types, thread anchored to character range

HLD-2

Design Google Maps (Navigation & Geo Service)

▶

Requirements: Search POIs, get directions (car/walk/transit), real-time traffic overlay, ETA, turn-by-turn navigation, map tile rendering, live traffic contribution from users.

Scale: 1B+ users, 25M+ updates/day from users. Map data = petabytes. 99.99% uptime for navigation.

Google Maps — System Architecture

User App

→

API Gateway

→

Routing EngineContraction Hierarchies

Tile ServiceQuadtree zoom/x/y.png

POI SearchElasticsearch geo

MAP TILES

GCS Tileszoom/x/y.png

→

CDN99%+ tile HIT rate

→

Client renders

REAL-TIME TRAFFIC

Driver probesGPS every 3s

→

Kafkalocation topic

→

Flinkavg speed per segment

→

Redisedge weights for routing

System Components: 1. Map Tile Service: World map pre-rendered into tiles at 21 zoom levels Tile naming: zoom/x/y.png (quadtree coordinates) Stored on Object Storage (GCS) served via CDN globally Vector tiles (modern): send vector data, render client-side (better scaling, dark mode) Tile generation pipeline: OSM data + satellite imagery Mapnik/custom renderer → tiles 2. Routing Engine: Road network = weighted directed graph Nodes: intersections Edges: road segments with weights (distance, speed_limit, traffic) Algorithm: Bidirectional Dijkstra (15x faster than one-directional) For Google-scale: Contraction Hierarchies (CH) precompute shortcuts Preprocess offline: add shortcut edges bypassing less important nodes Query: expand upward from src AND downward from dst meeting in middle Result: routes in <1ms even for continent-scale 3. Real-time Traffic: Driver location probes → Kafka (every 3s while driving, anonymized) Traffic aggregation service: compute avg speed per road segment (15s windows) Traffic overlay: Flink stream processor updates segment weights in Redis Routing engine reads current edge weights from Redis for ETA 4. ETA Prediction: Historical + real-time traffic + ML model (time of day, day of week, weather) Continually recalculate during navigation if user deviates or traffic changes 5. Search (POI): "Coffee near me" → Elasticsearch geo_distance query + ranking by ratings/distance Named search "Eiffel Tower" → Knowledge Graph (entity resolution) → coordinates Geocoding (address → lat/lng): Nominatim / in-house model Reverse geocoding (lat/lng → address): R-tree spatial index

Key Decisions

Contraction Hierarchies: routing on 10M+ node graph in <1ms
Quadtree tiles + CDN: 99%+ tile requests served from edge cache
Kafka for traffic probes: ingests 100M+ updates/day without loss
Vector tiles: client rendering, reduced data transfer, theme support
Segment-level traffic: granular road speed, not just major highways

Deep Dive Questions

Alternative routes: k-shortest paths, re-weight edges with diversity penalty
Offline maps: pre-download region tiles + routing graph, sync on WiFi
Tunnel/GPS loss: dead reckoning (speed + heading extrapolation) + map snapping
Map updates: OSM community + satellite ML detection → daily tile re-renders

HLD-3

Design Google Drive / Dropbox (File Sync & Storage)

▶

Requirements: Upload/download files, sync across devices, versioning, sharing (link + ACL), deduplication, conflict resolution when same file edited on two devices offline.

Scale: 500M users, 50M DAU, avg 2GB per user = 1 exabyte total. 10M uploads/day.

Google Drive — File Sync Architecture

UPLOAD (Delta Sync)

Clientchunk file into 4MB blocks

→ check missing blocks →

Block Service

→ upload missing only →

S3content-addressed by SHA256

SYNC (Cross-device)

Metadata Service

→

MySQLfile hierarchy + ACL

→

Kafkachange notifications

→

All DevicesSSE / WebSocket push

blocks tablesha256, s3_path, ref_count

files tablefile_id, block_list (sha256s)

Redishot metadata cache

Upload Flow: 1. Client chunks file into 4MB blocks (content-addressed: SHA256 of block) 2. Client checks: which blocks already exist? POST /api/check_blocks [sha256_list] 3. Server: SELECT sha256 FROM blocks WHERE sha256 IN (...) return existing 4. Client uploads ONLY missing blocks (delta sync — huge bandwidth savings) PUT /upload/block/{sha256} direct to S3 via pre-signed URL (bypass app servers) 5. Client: POST /api/commit_file {filename, block_list: [sha256s], parent_version} 6. Server: INSERT file record + version in MySQL, notify other devices via SSE/WebSocket Block Storage (Deduplication): blocks table: {sha256 (PK), s3_path, size, ref_count} files table: {file_id, user_id, version_id, block_list (JSON array of sha256s)} Two users upload same file? Both reference same blocks (storage saved!) Garbage collection: decrement ref_count on delete; S3 deletion when ref_count=0 Sync Protocol: Client maintains local delta log (what changed since last sync) Server sends: GET /changes?since=cursor (long-poll or WebSocket) On change: server publishes event Kafka notifications-{userId} SSE/WebSocket push Conflict Resolution: Two devices edit file while offline, reconnect with divergent versions Strategy: keep BOTH files: "report.docx" + "report.docx (conflict copy, Device A, 2024-01-15)" User resolves manually (same as Dropbox behavior)

Key Decisions

Content-addressed blocks: dedup + only upload changed chunks (delta)
Pre-signed S3 URLs: offload large uploads directly to S3, not app servers
MySQL for metadata: ACID needed for file hierarchy + permissions
Chunked upload: resume interrupted uploads (only re-upload missing chunks)

Deep Dive Questions

Large file upload (10GB): multipart S3 upload, 5min pre-signed URL expiry
Version history: store block_list per version, rollback = re-commit old block_list
Shared folder sync: all members receive change notifications
Client-side encryption: encrypt before upload; server stores ciphertext only

HLD-4

Design Netflix / Video Streaming Platform

▶

Requirements: Stream video on-demand (200M+ subscribers), personalized recommendations, search, content upload pipeline for studios, global CDN delivery, adaptive bitrate.

Scale: 200M subscribers, 100M+ concurrent streams at peak, 15% of global internet traffic.

Netflix — Content Pipeline & Playback Architecture

CONTENT UPLOAD PIPELINE

Studio UploadRaw 4K master

→

S3raw-content

→

Kafkacontent-uploaded

→

GPU TranscoderFFmpeg fleet

↓ outputs: 240p / 720p / 1080p / 4K HLS segments (.ts + .m3u8)

CDN OriginS3 bucket

→ pre-cache →

Edge PoPsOpen Connect in ISPs

PLAYBACK FLOW

User App

GET manifest →

Manifest APIreturns .m3u8 URL

→ fetch segments →

CDN EdgeISP PoP <10ms

RECOMMENDATIONS

Spark BatchALS model

→

Cassandratop-N per user

+

Kafka / Flinkreal-time affinity

Content Upload Pipeline (Studio → Users): Studio uploads raw 4K master → S3 (raw-content bucket) S3 event → Kafka "content-uploaded" topic Transcoding Fleet (GPU instances — EC2 P4d): Input: raw.mp4 FFmpeg transcodes to: 240p/360p/480p/720p/1080p/4K Codec: H.264 (compatibility) + HEVC/H.265 (60% smaller, for 4K) Output: HLS/DASH segments (.ts files, ~6s each) + .m3u8 manifests Upload segments → CDN Origin Playback (Client → CDN): Client: GET /api/manifest/{contentId} → returns .m3u8 with CDN URLs CDN edge (Open Connect Appliance — Netflix's own CDN in ISP PoPs) Edge cache: 99%+ of popular content served directly from ISP network! Adaptive Bitrate (ABR): client monitors download speed If bandwidth drops: switch from 1080p manifest to 720p, seamless mid-stream Recommendation Engine: Offline: Spark batch jobs on viewing history → ALS matrix factorization Near-real-time: Kafka stream → Flink updates user affinity scores Serving: pre-computed top-N in Cassandra Resilience (Netflix Chaos Engineering): Circuit breakers between all microservices (Resilience4j) Chaos Monkey: randomly kills production instances (tests resilience) Multi-region active-active: US-East, US-West, EU, Asia

Key Decisions

Open Connect (own CDN in ISPs): eliminates 95%+ of transit costs
HLS/DASH + ABR: smooth experience across all network conditions
Cassandra for viewing history: write-heavy time-series, global multi-DC
Chaos engineering: force resilience by breaking prod intentionally

Deep Dive Questions

Cold start for new content: pre-load segments to edges before release
DRM: Widevine (Google) / PlayReady (Microsoft) segment encryption
Bandwidth estimation: 200M users × avg 5 Mbps = 1 Pbps capacity needed
Search: Elasticsearch with ML-reranked results based on user profile

HLD-5

Design a Web Crawler (like Google Search Indexer)

▶

Requirements: Crawl 1B+ web pages, extract links, store content, respect robots.txt, avoid duplicate content, refresh stale pages, handle dynamic JS pages.

Scale: 1B pages, avg 100KB/page = 100TB content. Re-crawl top pages every 24h, others weekly. 10K pages/sec sustained.

Web Crawler — Pipeline Architecture

URL FrontierRedis ZSet (priority)

→ dequeue →

Crawl Workersstateless, N=100

→ fetch page →

HTTP Fetchrespect robots.txt

↓

Kafkapages-crawled topic

Kafkalinks-found topic

↓

HTML Parserextract text + links

→

Bloom Filter1B URLs, 1GB RAM

→ not seen →

URL Frontieradd to priority queue

S3raw HTML content

Elasticsearchindexed text

URL Frontier (Priority Queue): Stores URLs to crawl, prioritized by: - PageRank estimate (important pages crawled more often) - Freshness score (last modified headers, update frequency) - Domain politeness (max 1 req/sec per domain) Implementation: Kafka topics per domain + Redis sorted set for priority Crawl Workers (stateless, horizontally scalable): Dequeue URL from Frontier DNS resolve (local cache + upstream) Fetch page (HTTP GET with User-Agent: Googlebot, respect robots.txt) Dynamic pages: headless Chrome (Puppeteer) for JS rendering Extract: all href links + raw HTML content Publish to Kafka: "pages-crawled" + "links-found" topics Content Processing: HTML Parser → extract text, metadata, canonical URL Dedup Service: SHA256(normalized_content) → Bloom Filter → URL Set check Duplicate? Skip. New? Store in S3, index in Elasticsearch URL Deduplication: Bloom filter (1B URLs, 1% FP rate, ~1.2GB RAM) — fast pre-check URL Set (DynamoDB) — authoritative dedup store Refresh Strategy: High-priority (news): re-crawl every 1h Normal pages: adaptive based on historical change rate 404 pages: exponential backoff (1d, 4d, 16d), eventually discard

Key Decisions

Kafka per-domain topics: natural domain-rate-limiting
Bloom filter: O(1) dedup check for 1B URLs in 1GB RAM
Headless Chrome pool: handle JS-heavy SPAs (React, Vue apps)
Adaptive refresh: crawl budget allocated by page importance

Deep Dive Questions

Spider traps: infinite URLs → URL length limit + depth limit
DNS cache poisoning: validate IPs against known-malicious list
Politeness: per-domain rate limit, respect crawl-delay, identify as bot
Distributed URL frontier: shard by domain hash

HLD-6

Design a Payment System (like Stripe / PayPal)

▶

Requirements: Accept card payments, process transactions, handle refunds, prevent double-charges, financial reconciliation, fraud detection. ACID non-negotiable.

Non-Functional: Exactly-once payment processing. 99.999% availability. PCI-DSS compliance. Sub-3s payment confirmation.

Payment System — Critical Transaction Path

Client

POST /payments →

API GatewayTLS + Auth

→

Payment Serviceidempotency key check

↓

Redisidempotency cache (NX)

Fraud DetectionML risk score <200ms

↓ approved

PSPStripe / Adyen

→ ACID →

Ledger (MySQL)double-entry bookkeeping

↓ async

KafkaPaymentCompleted

→

Order Service

Email Service

Analytics

Payment Flow (Critical Path): 1. Client: POST /payments {amount, currency, payment_method_token, idempotency_key} 2. Payment Service: Check idempotency key (Redis NX) — if exists, return cached result 3. Fraud Detection Service (async check within 200ms): ML model: card velocity, geo anomaly, device fingerprint → risk score >0.8 risk: decline. 0.5-0.8: 3DS challenge. <0.5: proceed 4. PSP call: POST to Stripe/Adyen API — Tokenized card (PAN never stored — PCI-DSS scope reduction) 5. On PSP response: SUCCESS: INSERT INTO ledger (txn_id, amount, status='completed') — ACID TIMEOUT: async reconciliation job checks PSP status endpoint 6. Return payment result to client 7. Async: emit PaymentCompleted event → Kafka → Order Service, Email, Analytics Ledger (Double-Entry Bookkeeping): Every financial event creates TWO entries (debit + credit): DEBIT: customer wallet $-50 CREDIT: merchant wallet $+50 Sum of all ledger entries must always = 0 (invariant checked hourly) Append-only: never UPDATE ledger rows — only INSERT corrections Reconciliation: Nightly job: compare our ledger against PSP settlement report Mismatches: auto-refund and alert on-call

Key Decisions

Double-entry ledger: financial correctness, easy auditing
Idempotency at every layer: client → service → PSP
Tokenization: PAN never stored (PCI-DSS compliance)
Async fraud detection: 200ms budget, non-blocking on payment path

Deep Dive Questions

PSP timeout: store as "pending", cron job polls PSP status async
Currency conversion: lock exchange rate at payment time
Chargebacks: reverse ledger entries, hold merchant funds in escrow during dispute
Rate limiting: max 5 payment attempts/hour per card to prevent card testing

HLD-7

Design Instagram / Photo Sharing

▶

Requirements: Upload photos/videos, follow users, home feed, explore/search, stories (24h TTL), likes, comments, DMs, notifications. 1B+ users, 100M photos/day.

Instagram — Hybrid Fan-out Feed Architecture

PHOTO UPLOAD

User

→ pre-signed URL →

S3original

→

Kafkaphoto-uploaded

→

Image ProcessorWebP + resize

→

CDN3 resolutions

FAN-OUT ON WRITE (regular users <10K followers)

Fan-out Worker

ZADD feed:{followerId} →

Redis ZSetper-user pre-built feed

FAN-OUT ON READ (celebrities >10K followers)

Feed Service

→ merge at query time →

Celebrity Timelinefetch top N directly

FEED READ

User

→

Feed Service

→

Redis ZSetregular posts

+

Celebrity pullmerge + sort

Photo Upload: Client → Upload Service (pre-signed S3 URL) → S3 (original) S3 event → Image Processing Worker (Kafka): Resize to: thumbnail (150px), feed (640px), HD (1080px) Convert to WebP (30% smaller than JPEG) Store all variants in S3, URLs in MySQL Feed Architecture (Hybrid Fan-out): Follower count < 10K (regular users): Fan-out on write Post created → FanoutWorker → ZADD feed:{followerId} timestamp postId Feed stored in Redis Sorted Set per user Celebrity (>10K followers): Fan-out on read At read time: fetch latest N posts from celebrity's timeline directly Merge with user's pre-built feed Stories: Upload same as photos, but TTL = created_at + 86400s Redis Sorted Set: stories:{userId} (score = expiry_time) Background job: ZREMRANGEBYSCORE remove expired stories Likes Counter: Redis INCR likes:{postId} (in-memory, fast) Async flush to PostgreSQL every 60s (batch update)

Key Decisions

Hybrid fan-out: pre-built Redis feed for regular users, lazy pull for celebrities
WebP + multiple resolutions: 30% bandwidth reduction, fast load
CDN for all media: images served from edge (global low latency)
Cassandra for DMs: write-heavy, time-ordered messages per conversation

Deep Dive Questions

Perceptual hash dedup: same photo re-uploaded → point to same S3 object
Feed with follow/unfollow: update fan-out set membership atomically
Reels (short video): same as YouTube but max 90s, same HLS pipeline
Explore feed: collaborative filtering + ML ranking

HLD-8

Design a Distributed Task Scheduler (like Airflow / Temporal)

▶

Requirements: Schedule tasks (one-time + cron), assign to workers, retry on failure, handle worker crashes, task dependencies (DAGs), exactly-once execution, monitor task status, priority queues.

Scale: 100M tasks/day, 10K concurrent workers, tasks must run within 1s of scheduled time.

Distributed Task Scheduler — Architecture

SchedulerLeader (etcd election)

→ INSERT due tasks →

MySQLtask_queue (durable)

→ populate →

Redis ZSetscore = run_at timestamp

↓ poll every 100ms

Dispatcher

→ ZRANGEBYSCORE + Lua claim →

Worker Pool10K workers

→ heartbeat →

Redisworker:{id} TTL 30s

↓ on completion

MySQLUPDATE status = done

→ check DAG deps →

Downstream Tasksre-enqueue if ready

DLQfailed after N retries

Scheduler (Leader-elected via Zookeeper/etcd): Cron expressions → parse next N execution times (pre-compute 5min ahead) INSERT INTO task_queue (task_id, run_at, status='pending', priority) Task Queue: Tier 1: Redis Sorted Set (score = run_at timestamp) ZRANGEBYSCORE task_queue -inf NOW LIMIT 0 100 → due tasks ZREM + atomically claim via Lua script (prevent double-dispatch) Tier 2: MySQL (durable, source of truth — Redis populated from here on startup) Dispatcher: Polls Redis every 100ms for due tasks Assigns to available worker via consistent hashing (task_type → worker pool) Worker heartbeats via Redis key (worker:{id} EX 30s) On heartbeat miss: task reassigned (at-least-once delivery) Workers (stateless pool): Execute task logic (must be idempotent!) On failure: retry with exponential backoff (max_retries configurable) Poison pills (always-failing): move to DLQ after max_retries DAG Dependencies: task_dependencies table: {task_id, depends_on_task_id} After task completes: check if downstream tasks now have all dependencies met If yes: INSERT downstream tasks into task_queue

Key Decisions

Redis sorted set: O(log N) scheduling, ~10ms dispatch latency
MySQL as durable backup: recover all pending tasks on Redis restart
Leader election via etcd: prevents double-scheduling
DLQ: poisonous tasks isolated, don't block healthy tasks

Deep Dive Questions

Time zone handling: store all times in UTC, convert at display layer
At-most-once (financial jobs): 2PC between scheduler DB and task execution record
Worker autoscaling: monitor queue depth, scale workers up/down via K8s HPA
Cascading failures: rate limit task retries, circuit break task_type if too many failures

HLD-9

Design Amazon E-Commerce (Product, Cart, Orders, Inventory)

▶

Requirements: Product catalog, search, cart, checkout, order management, inventory, pricing, recommendations. 300M active users, 1M orders/day, Black Friday 10× peak.

E-Commerce — Service Decomposition & Checkout Saga

SERVICE LAYER

Catalog ServiceMySQL + ES + Redis

Cart ServiceRedis only

Order ServiceMySQL ACID

Inventory ServiceMySQL + opt lock

Pricing ServiceRules + Redis TTL

CHECKOUT SAGA (distributed transaction)

1. ValidateCart items

→

2. ReserveInventory

→

3. ChargePayment

→

4. ConfirmOrder

→

5. KafkaOrderConfirmed

On failure at any step → compensating transactions run in reverse

Service Decomposition: Product Catalog → MySQL + Elasticsearch (search) + Redis (hot products) Cart Service → Redis (session-like, ephemeral, fast reads/writes) Order Service → MySQL (ACID for order lifecycle) Inventory → MySQL (ACID for stock counts, optimistic lock for reserve) Pricing Service → Rules engine + dynamic pricing + Redis cache (TTL 5min) Checkout Flow (Saga Pattern): 1. Inventory Service: RESERVE stock (decrement available_count) If conflict: return "out of stock", rollback 2. Payment Service: charge card (idempotency key = orderId) If payment fails: compensate → Inventory RELEASE reservation 3. Order Service: CREATE order record with status='confirmed' 4. Kafka: OrderConfirmed → Fulfillment, Email, Analytics Flash Sale Architecture (10K req/sec for 1 item): Pre-allocate tokens in Redis (1 token = 1 item reservation right) User claims token first: RPOP flash_tokens:{productId} Got token: proceed to checkout with guaranteed inventory Prevents overselling + reduces DB load during spike

Key Decisions

Saga (Choreography): services react to events independently
Redis for cart: sub-millisecond reads, no ACID needed
Optimistic locking for inventory: high-concurrency without DB blocking
Flash sale tokens in Redis: decouple spike from DB writes

Deep Dive Questions

Cart persistence: sync Redis cart to DB on checkout (prevent loss on expiry)
Price consistency: lock price at checkout (not cart-add)
Returns: saga compensation chain → refund payment + restore inventory
Multi-warehouse: nearest warehouse with stock for fastest delivery ETA

HLD-10

Design a Global CDN / Content Delivery Network

▶

Requirements: Serve static + dynamic content globally with <50ms latency. Cache 90%+ requests at edge. Handle 10 Tbps peak traffic. DDoS protection. 99.999% uptime.

1. DNS + Anycast Routing: Customer's domain CNAME → cdn.example.com Anycast: same IP announced from all PoPs User's DNS query auto-routes to geographically nearest PoP 2. Edge PoP (Point of Presence): Physical servers in 200+ cities co-located in major ISPs/IXPs Local SSD cache: hot content on 100TB NVMe per PoP Nginx/Varnish cache + Envoy LB + TLS termination On cache miss: fetch from Regional Mid-tier cache or Origin Shield 3. Tiered Cache Architecture: Edge (city) → Regional Mid-tier (continent) → Origin Shield → Customer Origin Mid-tier collapses cache misses: 1000 edge misses → 1 request to origin 4. Cache Invalidation: Surrogate keys (cache tags): tag content by type (product:{id}) Purge by tag: invalidate all product:{12345} URLs across all PoPs CDN propagates purge via gossip protocol (<1s global propagation) 5. DDoS Mitigation: Volumetric (L3/L4): BGP blackhole + traffic scrubbing centers Application (L7): rate limiting per IP, WAF rules (block SQLi, bad bots) Anycast absorbs UDP floods: traffic spread across all PoPs

Key Decisions

Anycast: automatic failover + DDoS absorption across 200+ PoPs
Tiered caching: collapse origin requests by 100-1000×
Private backbone: 30-50ms faster than public internet
Surrogate keys: surgical cache invalidation without full purge

Deep Dive Questions

Video delivery: range request / byte-range caching per segment
Geo-blocking: edge checks IP geolocation against blocklist
Hot object stampede: request coalescing (only 1 origin request per uncached URL)
HTTPS everywhere: HSTS preloading, OCSP stapling at edge for fast TLS

HLD-11

Design a Metrics & Monitoring System (like Prometheus + Grafana)

▶

Requirements: Collect metrics from thousands of services, store time-series data, query for dashboards, trigger alerts. Scale to 1M+ metrics, 1-second granularity, 90-day retention.

Metrics & Monitoring System — Architecture

COLLECTION

Services/metrics endpoint

→ scrape (pull) →

Prometheuspull every 15s

+

Lambda / FaaS/metrics push

→

StatsD Agentpush model

↓

Kafkametrics-raw topic

→

Flinkrollups: 1s→1min→5min

→

TSDBPrometheus / InfluxDB

→

S3 / Thanoslong-term 90 days

PromQL Queryrate(), histogram_quantile()

→

Redis Cache30s TTL

→

Grafanadashboards

+

AlertmanagerPagerDuty / Slack

Collection: Pull model (Prometheus): scrape /metrics endpoint of each service every 15s Push model (StatsD, CloudWatch Agent): service pushes to aggregation agent Better for serverless/ephemeral functions Ingestion Pipeline (1M metrics/sec): Services → Kafka (metrics-raw topic, partitioned by service_name) Stream processor (Flink): aggregate raw points → 1-min rollups → 5-min rollups Write to TSDB (Time-Series DB) Storage: Data shape: (metric_name, labels, timestamp, value) Compression: Gorilla encoding (Facebook): 1.37 bytes/data point (vs 16 bytes raw) store delta-of-deltas for timestamps + XOR compression for values Options: Prometheus TSDB, InfluxDB, Thanos/Cortex (Prometheus at scale + S3) Query Layer: PromQL: rate(http_requests_total{status="500"}[5m]) → 5-min error rate Pre-computed rollups: 1s → 1min → 5min → 1hr aggregates for fast dashboards Cache query results in Redis (30s TTL) Alerting: Alertmanager: evaluate alert rules every 15s against recent metrics Alert: http_error_rate > 0.01 for 5m → fire PagerDuty/Slack Deduplication + flapping suppression (pending state buffer)

Key Decisions

Kafka buffer: handles ingest spikes without dropping metrics
Pre-aggregated rollups: fast dashboard queries without scanning raw data
Gorilla compression: 12× storage reduction for time-series
S3 long-term via Thanos: cheap historical data

Deep Dive Questions

High cardinality labels (userId as label): cardinality explosion — use logs instead
Cross-DC aggregation: Thanos sidecar merges metrics across regions globally
Anomaly detection: seasonal decomposition + z-score alerting (ML-based)
Retention tiers: 15s/7 days, 1min/30 days, 1hr/1 year