# Building Blocks of Scalable Systems

The core components used to assemble distributed systems. Each block solves a specific problem; knowing when and why to introduce each one is the foundation of system design.

## DNS (Domain Name System)

### What It Does

Translates human-readable domain names (example.com) into IP addresses (93.184.216.34). It is the first step in every web request.

### Key Concepts

- **A record:** Maps domain to IPv4 address
- **AAAA record:** Maps domain to IPv6 address
- **CNAME record:** Maps domain to another domain (aliasing)
- **NS record:** Delegates a subdomain to a nameserver
- **TTL (Time to Live):** How long DNS resolvers cache the result

### Design Implications

- DNS-based load balancing: return different IPs for the same domain (round-robin DNS)
- GeoDNS: return different IPs based on the client's geographic location
- Low TTL enables faster failover but increases DNS query load
- DNS propagation delay (minutes to hours) affects failover speed

---

## CDN (Content Delivery Network)

### What It Does

Caches static and semi-static content at edge servers geographically close to users. Reduces latency and offloads origin servers.

### Types

| Type | What It Caches | Best For |
|------|---------------|----------|
| **Push CDN** | Content is uploaded proactively by origin | Small, rarely changing content (assets, firmware) |
| **Pull CDN** | Content is fetched from origin on first request, then cached | Large, frequently accessed content (images, videos, CSS/JS) |

### What to Put on a CDN

- Static assets: CSS, JavaScript, fonts, images, videos
- Semi-static content: user profile images, product images
- Pre-rendered pages: landing pages, marketing content
- API responses (with appropriate Cache-Control headers)

### What NOT to Put on a CDN

- Personalized content (user-specific data)
- Real-time data (stock prices, live scores)
- Content that changes every request

### Cache Invalidation

- **TTL-based:** Set expiration time; simple but content can be stale until TTL expires
- **Versioned URLs:** `style.v2.css` or `style.css?v=abc123`; instant invalidation, cache-friendly
- **Purge API:** Explicitly invalidate specific URLs; fast but requires operational tooling

---

## Load Balancers

### What They Do

Distribute incoming network traffic across multiple servers to ensure no single server is overwhelmed.

### L4 vs L7 Load Balancing

| Feature | L4 (Transport Layer) | L7 (Application Layer) |
|---------|---------------------|----------------------|
| **Operates on** | TCP/UDP packets | HTTP/HTTPS requests |
| **Speed** | Faster (less processing) | Slower (inspects content) |
| **Routing decisions** | IP address, port | URL path, headers, cookies, body |
| **SSL termination** | No (pass-through) | Yes (can decrypt and re-encrypt) |
| **Use cases** | High-throughput TCP services | Web apps, API routing, A/B testing |

### Load Balancing Algorithms

| Algorithm | How It Works | Best For |
|-----------|-------------|----------|
| **Round robin** | Rotate through servers sequentially | Homogeneous servers, even request complexity |
| **Weighted round robin** | Rotate with weights per server | Servers with different capacities |
| **Least connections** | Route to server with fewest active connections | Varying request durations |
| **IP hash** | Hash client IP to pick server | Session stickiness without cookies |
| **Consistent hashing** | Minimal redistribution when servers change | Cache servers, stateful routing |

### Health Checks

- **Active health checks:** Load balancer periodically pings each server (HTTP GET /health)
- **Passive health checks:** Monitor real traffic for errors (5xx responses, timeouts)
- **Unhealthy threshold:** Remove server after N consecutive failures
- **Recovery threshold:** Re-add server after M consecutive successes

---

## Reverse Proxy

### What It Does

Sits in front of web servers and forwards client requests. Provides a single entry point while hiding backend complexity.

### Benefits

- **Security:** Hides backend server IPs, terminates SSL, filters malicious requests
- **Caching:** Caches responses to reduce backend load
- **Compression:** Compresses responses before sending to clients
- **Rate limiting:** Controls request rate per client
- **SSL termination:** Handles HTTPS, backends communicate over HTTP internally

### Common Tools

- Nginx (most popular, also serves as load balancer)
- HAProxy (high-performance TCP/HTTP proxy)
- Envoy (modern, designed for microservices and service mesh)
- Traefik (auto-discovery, container-native)

---

## Caching

### Cache Layers

Caching can exist at every layer of the stack:

| Layer | What Is Cached | Tools | Latency |
|-------|---------------|-------|---------|
| **Client** | HTML, CSS, JS, images | Browser cache, local storage | ~0 ms |
| **CDN** | Static assets, pre-rendered pages | CloudFront, Cloudflare, Akamai | 5-50 ms |
| **Web server** | Full page responses | Nginx cache, Varnish | 1-5 ms |
| **Application** | Computed results, DB query results | Redis, Memcached | 1-5 ms |
| **Database** | Query plans, buffer pool | Built-in query cache | Varies |

### Cache Strategies

| Strategy | How It Works | Pros | Cons | Best For |
|----------|-------------|------|------|----------|
| **Cache-aside** | App checks cache; on miss, reads DB, writes to cache | Simple, app controls | Cache miss = two calls, possible stale data | General purpose, read-heavy |
| **Read-through** | Cache checks DB on miss automatically | Simpler app code | Cache library dependency | Read-heavy, standard lookups |
| **Write-through** | Write goes to cache AND DB synchronously | Cache always consistent | Write latency increased | Data that must be fresh |
| **Write-behind** | Write goes to cache; cache writes to DB asynchronously | Fast writes | Data loss risk if cache fails | High write throughput |
| **Refresh-ahead** | Cache proactively refreshes before TTL expires | Reduces cache miss latency | Wasted refreshes for unpopular keys | Frequently accessed hot data |

### Cache Invalidation Approaches

| Approach | How It Works | Tradeoff |
|----------|-------------|----------|
| **TTL (Time to Live)** | Entry expires after a set time | Simple but data can be stale |
| **Event-driven invalidation** | Write to DB triggers cache delete | Fresh data but coupling between writer and cache |
| **Version-based** | Cache key includes version number | Clean but requires version tracking |
| **Write-invalidate** | On write, delete the cache entry (next read re-populates) | Simple, avoids stale reads |
| **Write-update** | On write, update the cache entry with new value | Faster reads but more complex writes |

### Cache Eviction Policies

- **LRU (Least Recently Used):** Evict the entry not accessed for the longest time (most common)
- **LFU (Least Frequently Used):** Evict the entry accessed the fewest times
- **FIFO (First In, First Out):** Evict the oldest entry
- **Random:** Evict a random entry (surprisingly effective)

### Common Caching Problems

| Problem | Description | Solution |
|---------|------------|----------|
| **Cache stampede** | Many threads simultaneously miss cache and hit DB | Locking (only one thread fetches), request coalescing |
| **Hot key** | One key gets massive traffic | Replicate hot keys across multiple cache nodes |
| **Cache penetration** | Queries for non-existent data always miss | Cache null results with short TTL, use Bloom filter |
| **Cache warming** | Cold cache after restart causes DB overload | Pre-load popular keys at startup |

---

## Message Queues

### What They Do

Decouple producers (senders) from consumers (processors) by placing an intermediary buffer between them. Producers write messages to the queue; consumers read and process them independently.

### Why Use Them

- **Decoupling:** Producer and consumer don't need to know about each other
- **Buffering:** Absorb traffic spikes without dropping requests
- **Async processing:** Return response to user immediately, process in background
- **Retry and dead-letter:** Failed messages can be retried or moved to a dead-letter queue
- **Fan-out:** One message can be consumed by multiple subscribers

### Queue vs Pub/Sub

| Feature | Queue (Point-to-Point) | Pub/Sub (Broadcast) |
|---------|----------------------|---------------------|
| **Consumers** | One consumer per message | All subscribers get every message |
| **Use case** | Task processing, job queues | Event notification, real-time feeds |
| **Examples** | SQS, RabbitMQ (queue mode) | SNS, Kafka (topics), Redis Pub/Sub |

### Common Tools

| Tool | Model | Strengths |
|------|-------|-----------|
| **Apache Kafka** | Distributed log, pub/sub | High throughput, message replay, ordering within partitions |
| **RabbitMQ** | AMQP broker, queue + pub/sub | Flexible routing, mature, good for complex workflows |
| **Amazon SQS** | Managed queue | Zero ops, scales automatically, at-least-once delivery |
| **Redis Streams** | In-memory stream | Very fast, consumer groups, simpler than Kafka |

### Message Delivery Guarantees

| Guarantee | Meaning | Tradeoff |
|-----------|---------|----------|
| **At-most-once** | Message delivered 0 or 1 times | Fast but messages can be lost |
| **At-least-once** | Message delivered 1 or more times | Reliable but consumers must handle duplicates |
| **Exactly-once** | Message delivered exactly 1 time | Ideal but expensive (requires idempotency or transactions) |

---

## Consistent Hashing

### The Problem

Simple hash-based partitioning (key % N) breaks badly when N changes: almost all keys need to be remapped.

### How Consistent Hashing Works

1. Imagine a circular ring of hash values (0 to 2^32 - 1)
2. Each server is hashed to a point on the ring
3. Each key is hashed to a point on the ring
4. A key is assigned to the first server encountered clockwise from its position

### Why It Works

- When a server is added, only the keys between the new server and its predecessor need to move (~1/N of all keys)
- When a server is removed, only its keys need to be reassigned to the next server
- This is dramatically better than simple hashing where ~all keys move

### Virtual Nodes

Problem: with few servers, distribution can be very uneven.
Solution: map each physical server to multiple virtual nodes on the ring.

- Server A might be at positions 10, 90, 170, 250 on the ring
- Server B might be at positions 50, 130, 210, 290
- More virtual nodes = more even distribution (typically 100-200 per server)

### Applications

| Use Case | Why Consistent Hashing |
|----------|----------------------|
| **Distributed cache (Memcached, Redis cluster)** | Add/remove nodes without invalidating most cached data |
| **Database sharding** | Rebalance with minimal data movement |
| **CDN routing** | Route requests to nearest/appropriate edge server |
| **Load balancing** | Sticky sessions without storing session maps |

---

## Putting It All Together

A typical web-scale architecture layers these blocks:

```
Client -> DNS -> CDN (static) -> Load Balancer (L7)
  -> Web Servers -> Application Servers
    -> Cache (Redis) -> Database (Primary + Replicas)
    -> Message Queue -> Worker Servers
```

**Design principle:** Start simple. Add each building block only when you hit the specific problem it solves:
1. Single server handles everything
2. Separate database from application server
3. Add load balancer and multiple app servers
4. Add cache for read-heavy paths
5. Add CDN for static assets
6. Add message queue for async processing
7. Add database replicas for read scaling
8. Shard database for write scaling
9. Add multiple datacenters for geographic distribution

# Common System Designs

Brief overviews of frequently encountered system designs. Each section covers the core requirements, key components, design decisions, and critical tradeoffs. Use these as starting templates that you adapt to specific requirements.

---

## URL Shortener

### Requirements
- Given a long URL, generate a short unique URL
- Given a short URL, redirect to the original URL
- Optional: custom short URLs, expiration, analytics

### Key Components
- **API service:** Accepts long URL, returns short URL; accepts short URL, returns redirect
- **ID generator:** Creates unique short codes (base62-encoded auto-increment or hash)
- **Key-value store:** Maps short code to long URL (Redis, DynamoDB, or Cassandra)
- **Analytics service:** Logs redirects for click tracking (async via message queue)

### Design Decisions

| Decision | Options | Recommendation |
|----------|---------|----------------|
| **ID generation** | Auto-increment + base62, hash (MD5/SHA), pre-generated IDs | Auto-increment + base62 for simplicity; pre-generated ranges for distributed |
| **Redirect type** | 301 (permanent) vs 302 (temporary) | 302 if you need analytics (browser doesn't cache); 301 for maximum performance |
| **Storage** | SQL vs NoSQL | NoSQL key-value (simple lookup, massive scale) |
| **Read optimization** | Cache layer | Cache-aside with Redis; short URLs follow power-law (few URLs get most traffic) |

### Scale Calculations (100M DAU)
- Write QPS: ~116 (10M new URLs/day)
- Read QPS: ~5,800 (500M redirects/day), peak ~29K
- Storage: ~1.1 TB/year (300 bytes per record, 10M/day, 10-year retention)

---

## Rate Limiter

### Requirements
- Limit the number of requests a client can send in a time window
- Return 429 (Too Many Requests) when limit exceeded
- Must be low-latency (add minimal overhead to each request)

### Key Components
- **Rate limiter middleware:** Checks request against limits before routing to backend
- **Counter store:** Redis for atomic increment and TTL-based expiration
- **Configuration service:** Defines rules (100 requests/minute per API key)

### Algorithms

| Algorithm | How It Works | Pros | Cons |
|-----------|-------------|------|------|
| **Token bucket** | Bucket holds tokens; each request consumes one; bucket refills at fixed rate | Smooth, allows bursts up to bucket size | Requires per-client state |
| **Leaky bucket** | Requests enter a queue; processed at fixed rate | Very smooth output | Doesn't handle bursts well |
| **Fixed window** | Count requests in fixed time windows (e.g., each minute) | Simple | Spike at window boundary (2x burst) |
| **Sliding window log** | Store timestamp of each request; count within sliding window | Accurate | Memory-intensive (stores every timestamp) |
| **Sliding window counter** | Weighted combination of current and previous window | Good accuracy, low memory | Approximate (but close enough) |

### Design Decisions

| Decision | Options | Recommendation |
|----------|---------|----------------|
| **Where to rate-limit** | Client-side, API gateway, middleware, server-side | API gateway or middleware (centralized, before business logic) |
| **Counter storage** | Local memory, Redis, database | Redis (atomic operations, TTL, shared across servers) |
| **Distributed coordination** | Single Redis, Redis Cluster, local + sync | Redis Cluster for high availability |
| **Rate limit headers** | X-RateLimit-Remaining, X-RateLimit-Limit, Retry-After | Include all three; Retry-After is most important |

### Handling Exceeded Limits
- Return HTTP 429 with `Retry-After` header
- Optionally queue excess requests instead of rejecting
- Log rate-limited requests for monitoring (detect abuse patterns)

---

## Notification System

### Requirements
- Send push notifications, SMS, and email
- Support millions of users with different preferences
- Handle retry for failed deliveries

### Key Components
- **Notification service:** API to receive notification requests
- **User preference store:** Which channels each user has enabled
- **Template service:** Render notification content from templates
- **Delivery workers:** Per-channel workers (push, SMS, email)
- **Message queues:** One queue per channel for decoupling and retry
- **Delivery log:** Track sent, delivered, read status

### Design Decisions
- **Decouple with queues:** Separate queue per channel allows independent scaling and retry
- **Retry with exponential backoff:** Failed deliveries retry with increasing delay (1s, 2s, 4s, 8s...)
- **Rate limiting per user:** Prevent notification fatigue (max N notifications per hour)
- **Priority levels:** Urgent (password reset) vs normal (marketing) vs low (weekly digest)
- **Deduplication:** Idempotency key prevents sending the same notification twice

---

## News Feed (Social Feed)

### Requirements
- Users follow other users
- When a user posts, followers see the post in their feed
- Feed is ordered by recency (or ranked by algorithm)

### Key Components
- **Post service:** Stores posts
- **Follow graph:** Stores who follows whom
- **Feed generation service:** Assembles personalized feeds
- **Feed cache:** Pre-computed feeds per user (Redis sorted sets)
- **Notification service:** Alerts followers of new posts

### The Core Tradeoff: Fanout Strategy

| Strategy | How It Works | Pros | Cons |
|----------|-------------|------|------|
| **Fanout-on-write (push)** | When user posts, write to every follower's feed cache | Fast reads (feed is pre-built) | Slow writes for celebrities, wastes storage for inactive users |
| **Fanout-on-read (pull)** | When user reads feed, fetch posts from all followed accounts | Fast writes, no wasted storage | Slow reads (must merge N sources), high read-time computation |
| **Hybrid** | Push for normal users, pull for celebrities | Balanced | More complex code |

### Hybrid Design (Recommended)
- Users with < 10K followers: fanout-on-write (pre-push to follower feeds)
- Users with > 10K followers: fanout-on-read (merge at read time)
- Feed cache: Redis sorted set per user, scored by timestamp, capped at ~1,000 entries
- Celebrity posts: fetch at read time and merge into the cached feed

---

## Chat System

### Requirements
- 1:1 and group messaging
- Real-time delivery (< 1 second latency)
- Message persistence and history
- Online/offline status (presence)

### Key Components
- **Connection service:** Manages WebSocket connections (stateful)
- **Message service:** Stores and retrieves messages
- **Presence service:** Tracks online/offline status
- **Notification service:** Push notifications for offline users
- **Group service:** Manages group membership and routing

### Design Decisions

| Decision | Options | Recommendation |
|----------|---------|----------------|
| **Protocol** | HTTP polling, long polling, WebSocket, SSE | WebSocket for bidirectional real-time |
| **Message storage** | SQL, NoSQL, wide-column | Wide-column (Cassandra/HBase) for write-heavy, time-series access |
| **Message ordering** | Timestamp, sequence number, hybrid | Monotonic ID per conversation (timestamp + sequence) |
| **Presence** | Heartbeat, connection-based | Heartbeat every 30s; mark offline after 3 missed beats |
| **Group message routing** | Fan-out to members, pull on read | Fan-out via message queue for groups up to ~500 members |

### Message Flow (1:1)
1. Sender sends message via WebSocket to connection service
2. Connection service publishes to message queue
3. Message service persists to database
4. If recipient is online: deliver via their WebSocket connection
5. If recipient is offline: send push notification, store for later delivery

---

## Search Autocomplete

### Requirements
- As user types, suggest top completions
- Latency under 100ms
- Suggestions ranked by frequency/relevance

### Key Components
- **Trie (prefix tree):** Data structure optimized for prefix matching
- **Aggregation service:** Collects search queries and computes frequencies
- **Cache layer:** Top-k results for popular prefixes (Redis)
- **Data collection service:** Logs queries for frequency analysis

### Design Decisions
- **Trie structure:** Each node stores a character; leaf or internal nodes store top-k completions
- **Pre-computation:** Compute top-k for each prefix offline (daily/hourly job), store in trie
- **Caching:** Cache results for popular prefixes (top 20% of prefixes serve 80% of queries)
- **Sharding:** Shard trie by first character or first two characters
- **Update frequency:** Rebuild trie hourly or daily from query logs (real-time updates are rarely needed)

---

## Web Crawler

### Requirements
- Crawl billions of web pages
- Respect robots.txt and rate limits
- Handle duplicates, broken links, and dynamic content

### Key Components
- **URL frontier:** Priority queue of URLs to crawl (BFS order)
- **Fetcher:** Downloads page content (HTTP client with timeout and retry)
- **DNS resolver:** Cached DNS lookups to avoid repeated resolution
- **Content parser:** Extracts links, text, and metadata from HTML
- **Deduplication:** Content hash (MD5/SHA) to detect duplicate pages
- **URL filter:** Removes unwanted URLs (file types, domains, robots.txt exclusions)
- **Storage:** Blob store for raw content, database for metadata and links

### Design Decisions
- **Politeness:** One connection per domain at a time; respect `Crawl-delay` in robots.txt
- **Priority:** Rank URLs by PageRank, freshness, or domain importance
- **Deduplication:** URL dedup (seen this URL?) + content dedup (seen this content at another URL?)
- **Trap avoidance:** Detect infinite loops (calendar pages, query parameter variations), set max URL depth
- **Recrawl:** Schedule recrawl based on page change frequency (detect via Last-Modified, ETag)

---

## Unique ID Generator

### Requirements
- Generate globally unique IDs at high throughput
- IDs should be roughly sortable by time
- 64-bit (fits in a long integer)

### Approaches

| Approach | Format | Pros | Cons |
|----------|--------|------|------|
| **UUID** | 128-bit random | Simple, no coordination | 128-bit (too large), not sortable |
| **Auto-increment (single DB)** | Sequential integer | Simple, sortable | Single point of failure, doesn't scale |
| **Auto-increment (multi DB)** | Even/odd or ranges per DB | Scales writes | Gaps in sequence, coordination for ranges |
| **Snowflake** | 64-bit: timestamp + datacenter + machine + sequence | Time-sortable, distributed, 64-bit | Clock sync dependency |
| **ULID** | 128-bit: timestamp + random | Sortable, simple | 128-bit |

### Snowflake ID Structure (Recommended for Most Systems)

```
| 1 bit unused | 41 bits timestamp | 5 bits datacenter | 5 bits machine | 12 bits sequence |
```

- **41-bit timestamp:** Milliseconds since custom epoch; ~69 years of IDs
- **5-bit datacenter ID:** Up to 32 datacenters
- **5-bit machine ID:** Up to 32 machines per datacenter
- **12-bit sequence:** Up to 4,096 IDs per millisecond per machine
- **Total capacity:** 4,096 x 32 x 32 = ~4 million IDs/second system-wide

### Design Decisions
- **Clock sync:** Use NTP; if clock goes backward, wait or reject (never generate duplicate)
- **Custom epoch:** Start from your launch date, not Unix epoch (maximizes timestamp range)
- **Machine ID assignment:** Use ZooKeeper, etcd, or config to assign unique machine IDs
- **Sequence overflow:** If 4,096 exhausted in one millisecond, wait for next millisecond

---

## Design Pattern Summary

| System | Key Pattern | Key Tradeoff |
|--------|------------|-------------|
| URL shortener | Base62 encoding + key-value store | 301 vs 302 redirect |
| Rate limiter | Token bucket + Redis counters | Accuracy vs memory |
| Notification | Per-channel queues + retry | Reliability vs latency |
| News feed | Hybrid fanout (push + pull) | Write amplification vs read latency |
| Chat | WebSocket + message queue | Connection statefulness vs scalability |
| Autocomplete | Trie + top-k precomputation | Freshness vs latency |
| Web crawler | BFS frontier + politeness | Crawl speed vs politeness |
| ID generator | Snowflake (time + machine + sequence) | Coordination vs simplicity |

# Database Design and Scaling

How to choose, design, and scale databases for distributed systems. The database is usually the first bottleneck -- understanding scaling strategies lets you plan growth deliberately.

## SQL vs NoSQL Decision Framework

### When to Choose SQL (Relational)

Choose relational databases (PostgreSQL, MySQL, Oracle) when:

- **ACID transactions** are required (financial data, inventory, bookings)
- **Complex joins** across multiple tables are common
- **Schema is well-defined** and unlikely to change dramatically
- **Data integrity** via foreign keys and constraints is critical
- **Reporting and ad-hoc queries** are needed (SQL is incredibly expressive)

### When to Choose NoSQL

Choose NoSQL when the access pattern matches a specific NoSQL model:

| NoSQL Type | Best For | Examples | When to Use |
|-----------|----------|---------|-------------|
| **Key-Value** | Simple lookups by key | Redis, DynamoDB, Riak | Session storage, caching, user preferences |
| **Document** | Flexible schema, nested data | MongoDB, CouchDB, Firestore | Product catalogs, content management, user profiles |
| **Wide-Column** | High write throughput, time-series | Cassandra, HBase, ScyllaDB | IoT data, event logs, messaging history |
| **Graph** | Highly connected data | Neo4j, Amazon Neptune, JanusGraph | Social networks, recommendation engines, fraud detection |

### The Decision Checklist

| Question | If Yes: SQL | If Yes: NoSQL |
|----------|-------------|---------------|
| Need ACID transactions? | SQL | |
| Need complex joins? | SQL | |
| Schema is stable? | SQL | |
| Schema evolves rapidly? | | Document DB |
| Need horizontal write scaling? | | Wide-column or Key-value |
| Access pattern is simple key lookup? | | Key-value |
| Data is highly connected (graph)? | | Graph DB |
| Need full-text search? | | Consider Elasticsearch alongside primary DB |

**Important:** Many real systems use multiple databases (polyglot persistence). A social app might use PostgreSQL for user accounts, Redis for sessions, Cassandra for the activity feed, and Elasticsearch for search.

---

## Vertical Scaling (Scale Up)

### What It Means

Make a single server more powerful: more CPU, more RAM, faster disks, more network bandwidth.

### Advantages

- Simple -- no code changes required
- No distributed systems complexity
- Strong consistency is easy (single node)
- No need for sharding logic

### Limitations

- Hard ceiling -- you can't buy an infinitely powerful machine
- Single point of failure -- one server, one failure domain
- Cost increases non-linearly -- a 2x more powerful server costs more than 2x the price
- Downtime during upgrade -- usually requires restart

### When to Use

- Early-stage products where simplicity matters more than scale
- When vertical limits haven't been reached (modern servers can handle significant load)
- When strong consistency requirements make horizontal scaling very difficult

**Rule of thumb:** Start vertical. A single PostgreSQL server with 64 cores and 256 GB RAM handles more than most applications need. Move to horizontal when you actually hit the limits.

---

## Replication

### Leader-Follower (Master-Slave)

The most common replication pattern:

```
Writes -> Leader (Primary)
Reads  -> Leader or Followers (Replicas)
```

**How it works:**
1. All writes go to the leader
2. Leader writes to its write-ahead log (WAL)
3. Followers replicate the WAL and apply changes
4. Reads can go to any node (leader or follower)

**Advantages:**
- Scales reads horizontally (add more followers)
- Provides redundancy (promote a follower if leader fails)
- Simple mental model

**Challenges:**

| Challenge | Description | Mitigation |
|-----------|------------|------------|
| **Replication lag** | Followers may be seconds behind leader | Read-your-writes: route user's reads to leader after they write |
| **Failover complexity** | Promoting a follower requires coordination | Automated failover with consensus (e.g., Patroni for PostgreSQL) |
| **Write bottleneck** | All writes still go to one node | See sharding section below |

### Multi-Leader (Master-Master)

Multiple nodes accept writes:

```
Region A writes -> Leader A -> replicates to -> Leader B
Region B writes -> Leader B -> replicates to -> Leader A
```

**When to use:**
- Multi-region deployments where each region needs local writes
- Offline-capable applications (each device is a "leader")

**The hard problem: write conflicts.** When two leaders modify the same row:

| Strategy | How It Works | Tradeoff |
|----------|-------------|----------|
| **Last-write-wins (LWW)** | Timestamp-based, latest wins | Simple but can lose data |
| **Application-level merge** | App defines custom merge logic | Correct but complex |
| **CRDTs** | Conflict-free data structures | Automatic merge but limited data types |
| **Conflict avoidance** | Route same data to same leader | Simple but limits flexibility |

### Leaderless Replication

All nodes are equal; reads and writes go to multiple nodes:

- Write to W nodes, read from R nodes
- If W + R > N (total nodes), reads are guaranteed to see latest write
- Used by Cassandra and DynamoDB

**Advantages:** No single point of failure, high availability
**Disadvantages:** Complex consistency model, conflict resolution needed

---

## Sharding (Horizontal Partitioning)

### What It Means

Split data across multiple database servers (shards), each holding a subset of the data. Each shard is a fully independent database.

### When to Shard

Shard only when you have exhausted simpler options:
1. Vertical scaling (bigger server)
2. Read replicas (for read-heavy workloads)
3. Caching (for hot data)
4. Query optimization (indexes, query rewriting)
5. **Then** shard (for write-heavy workloads or data too large for one server)

### Sharding Strategies

#### Hash-Based Sharding

```
shard_number = hash(shard_key) % number_of_shards
```

| Pros | Cons |
|------|------|
| Even data distribution | Adding/removing shards requires data redistribution |
| Simple implementation | Range queries across shards are difficult |
| No hotspots (if hash is good) | Re-sharding is expensive |

**Mitigation for redistribution:** Use consistent hashing instead of simple modulo.

#### Range-Based Sharding

```
Shard 1: user_id 1 - 1,000,000
Shard 2: user_id 1,000,001 - 2,000,000
```

| Pros | Cons |
|------|------|
| Efficient range queries | Uneven distribution (hotspots) |
| Natural data locality | New data may overwhelm one shard |
| Simple to understand | Requires manual range management |

**Best for:** Time-series data (shard by month), geographic data (shard by region).

#### Directory-Based Sharding

A lookup service maps each key to its shard:

```
Lookup table:
  user_123 -> shard_3
  user_456 -> shard_1
```

| Pros | Cons |
|------|------|
| Flexible, any key-to-shard mapping | Lookup service is a single point of failure |
| Easy rebalancing | Extra network hop for every query |
| Can handle hotspots by moving individual keys | Directory itself needs to be highly available |

### Choosing a Shard Key

The shard key determines everything about your sharding strategy. Choose carefully:

| Criteria | Why It Matters |
|----------|---------------|
| **High cardinality** | More distinct values = more even distribution |
| **Even distribution** | Avoid hotspots where one shard gets disproportionate traffic |
| **Query patterns** | Most queries should hit a single shard (avoid scatter-gather) |
| **Growth stability** | Key shouldn't cause imbalance as data grows |

**Common shard keys:**
- `user_id` -- good for user-centric applications (each user's data on one shard)
- `tenant_id` -- good for multi-tenant SaaS (each tenant isolated)
- `geo_region` -- good for location-based services
- `created_at` -- good for time-series (but recent shard gets all writes)

### The Celebrity/Hotspot Problem

Even with good hash-based sharding, a single popular entity can overwhelm one shard.

**Example:** A celebrity with 100 million followers. Any action on their account generates massive read/write traffic on the shard that holds their data.

**Solutions:**
1. **Dedicated shard:** Move the hot entity to its own shard
2. **Secondary partition:** Split the hot entity's data further (e.g., partition followers into sub-groups)
3. **Caching:** Put a cache in front of the hot shard
4. **Application-level routing:** Detect hot keys and handle them differently

### Cross-Shard Operations

The biggest challenge with sharding: operations that span multiple shards.

| Operation | Challenge | Solution |
|-----------|----------|----------|
| **Joins** | Can't join across shards efficiently | Denormalize, or join at application level |
| **Aggregations** | Must scatter query to all shards and gather results | Pre-compute aggregates, use a separate analytics DB |
| **Transactions** | Distributed transactions are slow and complex | Design for single-shard transactions, use sagas for cross-shard |
| **Unique constraints** | Can't enforce uniqueness across shards | Use a global sequence service, or accept probabilistic uniqueness |

---

## Denormalization

### What It Means

Duplicate data across tables or documents to avoid expensive joins at read time.

### When to Denormalize

| Indicator | Example |
|-----------|---------|
| Read-heavy workload (100:1 read:write ratio) | News feed, product catalog |
| Joins are too slow | Dashboard aggregating data from 5+ tables |
| Data changes infrequently | User profile data embedded in every post |
| Scale requires sharding (joins across shards are impractical) | Any sharded system |

### Denormalization Patterns

| Pattern | How It Works | Example |
|---------|-------------|---------|
| **Embed related data** | Store related data in same row/document | Store author name in each post (not just author_id) |
| **Materialized view** | Pre-compute and store query results | Nightly job that joins orders + products into a summary table |
| **Counter cache** | Store computed counts alongside parent | `posts_count` column on user table, incremented on new post |
| **Summary table** | Aggregate data into a summary | Daily revenue summary table updated by background job |

### Tradeoffs

| Benefit | Cost |
|---------|------|
| Faster reads (no joins) | Slower writes (update multiple places) |
| Simpler queries | Data inconsistency risk |
| Works with sharding | More storage used |
| Reduced database load | Application must maintain consistency |

---

## Database Selection Guide

Quick reference for choosing the right database:

| Requirement | Recommended | Examples |
|-------------|------------|---------|
| General-purpose web app | Relational | PostgreSQL, MySQL |
| Simple key-value lookups at massive scale | Key-value | Redis, DynamoDB |
| Flexible schema, document-oriented | Document | MongoDB, Firestore |
| High write throughput, time-series | Wide-column | Cassandra, ScyllaDB |
| Graph relationships | Graph | Neo4j, Neptune |
| Full-text search | Search engine | Elasticsearch, OpenSearch |
| Analytics and OLAP | Columnar | ClickHouse, BigQuery, Redshift |
| Caching layer | In-memory | Redis, Memcached |
| Message/event storage | Distributed log | Apache Kafka |

**Remember:** Most systems use 2-3 databases for different access patterns. This is polyglot persistence and it is normal at scale.

# Back-of-the-Envelope Estimation

Essential numbers, formulas, and worked examples for estimating system capacity. The goal is order of magnitude, not precision -- being within 10x is success; being within 2x is excellent.

## Powers of Two

Every engineer should know these instantly:

| Power | Exact Value | Approximate |
|-------|-------------|-------------|
| 2^10 | 1,024 | 1 thousand (1 KB) |
| 2^20 | 1,048,576 | 1 million (1 MB) |
| 2^30 | 1,073,741,824 | 1 billion (1 GB) |
| 2^40 | 1,099,511,627,776 | 1 trillion (1 TB) |
| 2^50 | ~1.13 x 10^15 | 1 quadrillion (1 PB) |

**Quick conversions:**
- 1 KB = 10^3 bytes
- 1 MB = 10^6 bytes
- 1 GB = 10^9 bytes
- 1 TB = 10^12 bytes
- 1 PB = 10^15 bytes

**Useful round numbers:**
- 1 million seconds = ~11.5 days
- 1 billion seconds = ~31.7 years
- 86,400 seconds in a day (~10^5)
- 2.5 million seconds in a month (~2.5 x 10^6)
- 31.5 million seconds in a year (~3 x 10^7)

---

## Latency Numbers Every Programmer Should Know

These numbers, originally compiled by Jeff Dean, define the performance landscape:

| Operation | Latency | Notes |
|-----------|---------|-------|
| L1 cache reference | 0.5 ns | |
| Branch mispredict | 5 ns | |
| L2 cache reference | 7 ns | |
| Mutex lock/unlock | 25 ns | |
| Main memory reference | 100 ns | |
| Compress 1 KB with Snappy | 3 us | |
| Send 1 KB over 1 Gbps network | 10 us | |
| Read 4 KB randomly from SSD | 150 us | |
| Read 1 MB sequentially from memory | 250 us | |
| Round trip within same datacenter | 500 us | |
| Read 1 MB sequentially from SSD | 1 ms | |
| HDD disk seek | 10 ms | |
| Read 1 MB sequentially from HDD | 20 ms | |
| Send packet CA -> Netherlands -> CA | 150 ms | |

### Key Takeaways

1. **Memory is fast, disk is slow.** Memory access (~100 ns) is 100,000x faster than disk seek (~10 ms).
2. **SSD is much faster than HDD.** SSD random read (~150 us) is ~67x faster than HDD seek (~10 ms).
3. **Sequential reads are fast everywhere.** Sequential 1 MB from memory (250 us) vs SSD (1 ms) vs HDD (20 ms).
4. **Network within a datacenter is fast.** Round trip ~0.5 ms. Cross-continent is ~150 ms (300x slower).
5. **Compression is cheap.** Compressing 1 KB takes ~3 us -- almost always worth doing for network transfer.

### Design Implications

| Latency Requirement | Design Strategy |
|--------------------|-----------------|
| < 1 ms | Must be in memory (cache, in-process) |
| < 10 ms | Can hit SSD or local cache |
| < 100 ms | Can hit database (with indexes) or remote cache |
| < 500 ms | Can make 1-2 network calls within datacenter |
| < 1 second | Can make multiple datacenter calls or one cross-region call |
| > 1 second | Must be async, show loading state to user |

---

## Availability Nines

| Availability | Downtime/Year | Downtime/Month | Downtime/Week |
|-------------|---------------|----------------|---------------|
| 99% (two nines) | 3.65 days | 7.31 hours | 1.68 hours |
| 99.9% (three nines) | 8.77 hours | 43.83 minutes | 10.08 minutes |
| 99.95% | 4.38 hours | 21.92 minutes | 5.04 minutes |
| 99.99% (four nines) | 52.60 minutes | 4.38 minutes | 1.01 minutes |
| 99.999% (five nines) | 5.26 minutes | 26.30 seconds | 6.05 seconds |

### SLA Composition

When services depend on each other, availabilities multiply:

- Service A: 99.9%, Service B: 99.9%
- Combined (A depends on B): 99.9% x 99.9% = 99.8%

This means:
- A chain of 3 services at 99.9% each = 99.7% combined
- A chain of 5 services at 99.9% each = 99.5% combined

**Implication:** To achieve 99.99% end-to-end, each component must be significantly better than 99.99% individually, or you need redundancy (parallel paths) to improve overall availability.

**Parallel redundancy:**
- Two instances of a service, each at 99%: 1 - (0.01 x 0.01) = 99.99%
- Both must fail simultaneously for the system to be unavailable

---

## QPS Estimation

### Formula

```
Average QPS = DAU x average_actions_per_user / 86,400
Peak QPS    = Average QPS x peak_factor (typically 2-5x)
```

### Worked Examples

**Twitter-like service:**
- DAU: 300 million
- Tweets per user per day: 2 (average)
- Tweet reads per user per day: 100
- Write QPS: 300M x 2 / 86,400 = ~7,000 QPS
- Peak write QPS: 7,000 x 3 = ~21,000 QPS
- Read QPS: 300M x 100 / 86,400 = ~350,000 QPS
- Peak read QPS: 350,000 x 3 = ~1,050,000 QPS
- Read:write ratio = 50:1

**URL shortener:**
- DAU: 100 million
- URLs created per user per day: 0.1 (most users only read)
- URL redirects per user per day: 5
- Write QPS: 100M x 0.1 / 86,400 = ~116 QPS
- Read QPS: 100M x 5 / 86,400 = ~5,800 QPS
- Peak read QPS: 5,800 x 5 = ~29,000 QPS

**Chat application:**
- DAU: 50 million
- Messages per user per day: 40
- Message QPS: 50M x 40 / 86,400 = ~23,000 QPS
- Peak QPS: 23,000 x 5 = ~115,000 QPS

---

## Storage Estimation

### Formula

```
Daily storage  = records_per_day x average_record_size
Yearly storage = daily_storage x 365
Total storage  = yearly_storage x retention_years
```

### Worked Examples

**Twitter-like service (5-year retention):**
- Tweets per day: 300M users x 2 tweets = 600M tweets
- Average tweet size: tweet_id (8 bytes) + user_id (8 bytes) + text (280 chars = 280 bytes) + timestamp (8 bytes) + metadata (100 bytes) = ~400 bytes
- Daily storage: 600M x 400 bytes = 240 GB/day
- Yearly storage: 240 GB x 365 = ~88 TB/year
- 5-year storage: 88 TB x 5 = ~440 TB
- With media (images, videos): multiply by 10-50x

**URL shortener (10-year retention):**
- New URLs per day: 100M x 0.1 = 10M URLs
- Average record size: short_code (7 bytes) + original_url (200 bytes) + metadata (50 bytes) = ~257 bytes, round to 300 bytes
- Daily storage: 10M x 300 bytes = 3 GB/day
- Yearly storage: 3 GB x 365 = ~1.1 TB/year
- 10-year storage: 1.1 TB x 10 = ~11 TB

**Chat application (indefinite retention):**
- Messages per day: 50M users x 40 messages = 2 billion messages
- Average message size: 200 bytes (text) + 100 bytes (metadata) = 300 bytes
- Daily storage: 2B x 300 bytes = 600 GB/day
- Yearly storage: 600 GB x 365 = ~219 TB/year

---

## Bandwidth Estimation

### Formula

```
Incoming bandwidth = write_QPS x average_request_size
Outgoing bandwidth = read_QPS x average_response_size
```

### Worked Examples

**URL shortener:**
- Write: 116 QPS x 300 bytes = ~35 KB/s (negligible)
- Read: 5,800 QPS x 500 bytes (redirect response) = ~2.9 MB/s
- Peak read: 29,000 QPS x 500 bytes = ~14.5 MB/s

**Image hosting service:**
- Upload: 100 QPS x 2 MB = 200 MB/s incoming
- Download: 10,000 QPS x 500 KB (average image) = 5 GB/s outgoing
- This immediately tells you: CDN is mandatory

---

## Server Count Estimation

### Rule of Thumb

- A single web server handles ~1,000-10,000 QPS (depends on workload complexity)
- A single database server handles ~5,000-10,000 QPS for simple queries
- A single cache server (Redis) handles ~100,000 QPS for simple GET/SET
- A single message queue node handles ~10,000-100,000 messages/second

### Formula

```
Server count = Peak QPS / QPS per server
Add redundancy factor (typically 2-3x for fault tolerance)
```

### Worked Example

**URL shortener:**
- Peak read QPS: 29,000
- QPS per web server: ~5,000 (lightweight redirect)
- Minimum web servers: 29,000 / 5,000 = ~6
- With redundancy: 6 x 2 = 12 web servers
- Cache QPS: 29,000 (cache all reads)
- Redis nodes: 29,000 / 100,000 = 1 (with a replica for failover)

---

## Estimation Quick Reference

| What to Estimate | Formula | Typical Inputs |
|-----------------|---------|----------------|
| Average QPS | DAU x actions / 86,400 | DAU, actions per user |
| Peak QPS | Avg QPS x 2-5 | Traffic pattern |
| Daily storage | Records/day x record size | Record count, schema |
| Yearly storage | Daily x 365 | Daily storage |
| Bandwidth | QPS x response size | QPS, payload size |
| Server count | Peak QPS / capacity per server x 2 | Peak QPS |
| Cache size | Working set x record size | Hot records, record size |

---

## Common Estimation Mistakes

| Mistake | Why It Matters | Fix |
|---------|---------------|-----|
| Forgetting peak vs average | Average is fine, but peak causes outages | Always multiply by 2-5x for peak |
| Ignoring media storage | Text is tiny; images and video dominate | Account for media separately |
| Precise calculation | 3,472 QPS is false precision | Round to 3,500 or "about 3K-4K" |
| Forgetting replication | Storage and bandwidth multiply with replicas | Multiply by replication factor (typically 3x) |
| Ignoring metadata | Indexes, logs, and overhead add up | Add 30-50% overhead to raw data size |
| Using current numbers only | Systems grow | Apply expected growth rate (typically 2-3x/year) |

# The Four-Step System Design Process

A structured framework for approaching any system design problem. Each step has a clear purpose, time allocation, and set of deliverables.

## Overview

```
Step 1: Understand the Problem & Establish Design Scope  (~5-10 min)
Step 2: Propose High-Level Design & Get Buy-In           (~15-20 min)
Step 3: Design Deep Dive                                  (~15-20 min)
Step 4: Wrap Up                                           (~5 min)
```

Total: ~45-60 minutes for a complete design session. Adjust proportionally for shorter or longer sessions.

---

## Step 1: Understand the Problem & Establish Design Scope

### Purpose

Ensure you and your audience agree on what the system needs to do, how big it needs to be, and what constraints apply. Ambiguity here cascades into wasted effort later.

### What to Do

**Ask clarifying questions.** Never assume. The difference between a system that serves 1,000 users and one that serves 100 million users is fundamental, not incremental.

### Functional Requirements

Define what the system does:

- What are the core features?
- Who are the users? (end users, internal services, third-party integrations)
- What are the key use cases? Walk through the most important user flows.
- What are the inputs and outputs?
- Are there any features explicitly out of scope?

**Example questions for a URL shortener:**
- Can users create custom short URLs or only auto-generated ones?
- Do short URLs expire?
- Do we need analytics (click count, referrer, geo)?
- Do we need to support URL deletion or editing?

### Non-Functional Requirements

Define how the system behaves:

| Requirement | Questions to Ask |
|-------------|-----------------|
| **Scale** | How many DAU? How many requests per day? Peak vs average? |
| **Latency** | What is the acceptable response time? P50, P95, P99? |
| **Availability** | What SLA? 99.9%? 99.99%? |
| **Consistency** | Strong consistency required or eventual consistency acceptable? |
| **Durability** | Can we lose data? What is the acceptable RPO? |
| **Security** | Authentication? Authorization? Encryption at rest/in transit? |

### Back-of-the-Envelope Estimates

Establish order-of-magnitude numbers:

- **QPS:** DAU x actions-per-user / 86,400
- **Peak QPS:** Average QPS x 2-5 (depends on traffic pattern)
- **Storage:** Records-per-day x record-size x retention-period
- **Bandwidth:** QPS x average-response-size

### Deliverables from Step 1

- Written list of functional requirements (3-5 bullet points)
- Written list of non-functional requirements (scale, latency, availability)
- Back-of-the-envelope estimates (QPS, storage, bandwidth)
- Explicit out-of-scope items

### Common Mistakes in Step 1

| Mistake | Consequence | Fix |
|---------|------------|-----|
| Skipping clarification | Solving the wrong problem | Ask at least 5 clarifying questions |
| Assuming scale | Over-engineering or under-engineering | Get explicit DAU and QPS numbers |
| Ignoring non-functional requirements | System works but is too slow/unreliable | Always ask about latency, availability, consistency |
| Spending too long | Not enough time for design | Timebox to 10 minutes maximum |

---

## Step 2: Propose High-Level Design & Get Buy-In

### Purpose

Create a blueprint that shows the major components, their responsibilities, and how data flows between them. This is the "skeleton" that Step 3 will flesh out.

### What to Do

**Draw a diagram.** Include:

1. **Clients:** Web, mobile, API consumers
2. **API Gateway / Load Balancer:** Entry point for requests
3. **Application Services:** The business logic layer, broken into services if appropriate
4. **Data Stores:** Databases, caches, blob storage, search indices
5. **Supporting Infrastructure:** Message queues, CDN, notification services
6. **Data Flow Arrows:** Show the direction and nature of communication (sync HTTP, async queue, etc.)

### API Design

Define the key API endpoints:

```
POST /api/v1/urls        # Create short URL
GET  /api/v1/urls/{id}   # Redirect to original URL
GET  /api/v1/urls/{id}/stats  # Get analytics
```

For each endpoint, specify:
- HTTP method and path
- Request parameters / body
- Response format
- Error codes

### Data Model

Define the core entities and their relationships:

```
URL:
  id: bigint (primary key)
  short_code: varchar(7) (unique index)
  original_url: text
  user_id: bigint (foreign key)
  created_at: timestamp
  expires_at: timestamp (nullable)
  click_count: bigint (default 0)
```

Choose the storage technology:
- Relational (PostgreSQL, MySQL) for structured data with complex queries
- Key-value (Redis, DynamoDB) for simple lookups at massive scale
- Document (MongoDB) for flexible schema
- Wide-column (Cassandra, HBase) for high write throughput with time-series data

### Get Buy-In

Before diving deeper:
- "Does this high-level approach make sense?"
- "Are there any major concerns with this direction?"
- "Should we focus the deep dive on [component A] or [component B]?"

### Deliverables from Step 2

- High-level architecture diagram with labeled components and data flow arrows
- API contract for the core endpoints
- Data model for the primary entities
- Storage technology choice with brief justification
- Agreement on which components deserve a deep dive

---

## Step 3: Design Deep Dive

### Purpose

Take the 2-3 most critical or complex components from the high-level design and design them in detail. This is where you demonstrate depth of knowledge.

### Choosing What to Deep Dive

Pick components that are:
- **Hardest to scale:** The database, the real-time messaging layer, the search index
- **Most critical for correctness:** The payment processor, the consistency model, the rate limiter
- **Most novel or unique:** Whatever makes this system different from a textbook example

### How to Deep Dive

For each component:

**1. State the specific challenge**
"The news feed service needs to assemble a personalized feed from thousands of followed accounts within 200ms."

**2. Explore design options**
Present at least two approaches with tradeoffs:

| Approach | Pros | Cons |
|----------|------|------|
| Fanout-on-write | Fast read, pre-computed | Expensive for celebrity accounts, wastes storage |
| Fanout-on-read | Cheap writes, fresh data | Slow reads, high read-time computation |
| Hybrid | Balanced for most cases | More complex, two code paths |

**3. Choose and justify**
"We choose the hybrid approach because 99% of accounts have < 10K followers (fanout-on-write is cheap), and the 1% celebrity accounts use fanout-on-read to avoid write amplification."

**4. Detail the implementation**
- Data structures and algorithms
- Database schema additions
- Caching strategy
- Error handling and edge cases

### Deep Dive Examples

**URL shortener -- ID generation deep dive:**
- Option A: Auto-increment ID + base62 encoding (simple, sequential, single-point bottleneck)
- Option B: Pre-generated ID ranges per server (distributed, no coordination, slight complexity)
- Option C: Hash of original URL (deterministic, possible collisions, needs collision handling)
- Choice: Option B for scalability with Option C as a fallback for deduplication

**Chat system -- message delivery deep dive:**
- WebSocket connection management at scale
- Message ordering guarantees (per-conversation monotonic IDs)
- Offline message storage and delivery on reconnect
- Read receipts and presence (heartbeat-based, eventual consistency acceptable)

### Deliverables from Step 3

- Detailed design of 2-3 critical components
- Tradeoff analysis for each design decision
- Data structures, schemas, or algorithms where relevant
- Edge case handling

---

## Step 4: Wrap Up

### Purpose

Summarize the design, acknowledge its limitations, and suggest future improvements. This demonstrates maturity and self-awareness.

### What to Cover

**1. Summary of the design**
One-paragraph overview of how the system works end-to-end.

**2. Tradeoffs acknowledged**
- "We chose eventual consistency for the news feed, which means a post may take 1-2 seconds to appear in all followers' feeds."
- "Sharding by user_id means cross-user queries (e.g., trending topics) require scatter-gather."

**3. Bottlenecks identified**
- "The database write path will be the first bottleneck at 50K QPS."
- "Hot users with millions of followers will stress the fanout service."

**4. Future improvements**
- "Add a CDN for frequently accessed short URLs."
- "Implement rate limiting per API key to prevent abuse."
- "Add a circuit breaker for downstream service calls."

**5. Error handling and edge cases**
- What happens when the database is down?
- What happens when the cache is full?
- How do we handle duplicate requests?
- How do we handle schema migrations?

### Deliverables from Step 4

- One-paragraph design summary
- List of acknowledged tradeoffs
- Identified bottlenecks and scaling triggers
- Suggested future improvements

---

## Tips for Each Step

### General Tips

- **Think out loud.** The process is as important as the result.
- **Use numbers.** "A lot of traffic" is vague; "50K QPS" is actionable.
- **Draw diagrams.** Visual communication is clearer than verbal descriptions.
- **Name your tradeoffs.** Every decision has a cost; acknowledging it shows depth.

### Step 1 Tips

- Ask open-ended questions first, then narrow down
- Write down assumptions explicitly -- don't keep them in your head
- If given incomplete information, state your assumption and move on

### Step 2 Tips

- Start with the simplest design that could work, then add complexity
- Label every arrow in the diagram (HTTP, gRPC, async message, etc.)
- Don't design microservices for a system that could be a monolith

### Step 3 Tips

- Go deep on 2-3 things rather than shallow on everything
- Compare at least two approaches before choosing
- Address failure modes: what happens when this component goes down?

### Step 4 Tips

- Be honest about what you didn't cover
- Propose monitoring and alerting for the bottlenecks you identified
- Mention operational concerns: deployment, data migration, feature flags

# Reliability and Operations

A system is only as good as its ability to stay up, recover from failures, and be observed. This reference covers the operational practices that turn a design diagram into a production system.


## Table of Contents
1. [Health Checks](#health-checks)
2. [Monitoring and Alerting](#monitoring-and-alerting)
3. [Logging](#logging)
4. [Deployment Strategies](#deployment-strategies)
5. [Disaster Recovery](#disaster-recovery)
6. [Data Center Redundancy](#data-center-redundancy)
7. [Autoscaling](#autoscaling)
8. [Operational Readiness Checklist](#operational-readiness-checklist)

---

## Health Checks

### Liveness vs Readiness

Two fundamentally different questions:

| Check | Question | What Happens on Failure |
|-------|----------|------------------------|
| **Liveness** | Is the process alive and not deadlocked? | Restart the process |
| **Readiness** | Can this instance serve traffic right now? | Remove from load balancer (but don't restart) |

### Implementation

**Liveness probe (`/healthz` or `/livez`):**
```
Returns 200 if:
  - Process is running
  - Main thread is responsive
  - No deadlock detected

Returns 503 if:
  - Event loop is blocked
  - Process is in an unrecoverable state
```

**Readiness probe (`/readyz` or `/ready`):**
```
Returns 200 if:
  - Database connection is active
  - Cache connection is active
  - Required downstream services are reachable
  - Startup initialization is complete

Returns 503 if:
  - Any critical dependency is unreachable
  - Still warming up (loading cache, running migrations)
```

### Best Practices

- Liveness checks should be simple and fast (< 100ms) -- don't check external dependencies
- Readiness checks should verify all critical dependencies
- Set appropriate thresholds: don't restart on a single failure (3 consecutive failures is typical)
- Include version and build info in health check response for debugging
- Separate health check endpoints for different concerns (database, cache, queue)

### Kubernetes Configuration

```yaml
livenessProbe:
  httpGet:
    path: /healthz
    port: 8080
  initialDelaySeconds: 15
  periodSeconds: 10
  failureThreshold: 3

readinessProbe:
  httpGet:
    path: /readyz
    port: 8080
  initialDelaySeconds: 5
  periodSeconds: 5
  failureThreshold: 2
```

---

## Monitoring and Alerting

### The Three Pillars of Observability

| Pillar | What It Captures | Tools | Use Case |
|--------|-----------------|-------|----------|
| **Metrics** | Numeric measurements over time | Prometheus, Datadog, CloudWatch | Dashboards, alerting, trend analysis |
| **Logs** | Discrete events with context | ELK (Elasticsearch, Logstash, Kibana), CloudWatch Logs, Splunk | Debugging, audit trails, error investigation |
| **Traces** | Request journey across services | Jaeger, Zipkin, AWS X-Ray, Datadog APM | Latency analysis, dependency mapping, bottleneck identification |

### Key Metrics to Track

#### The Four Golden Signals (Google SRE)

| Signal | What It Measures | Example Metric |
|--------|-----------------|----------------|
| **Latency** | Time to serve a request | P50, P95, P99 response time |
| **Traffic** | Demand on the system | Requests per second (QPS) |
| **Errors** | Rate of failed requests | 5xx error rate, timeout rate |
| **Saturation** | How full the system is | CPU utilization, memory usage, queue depth |

#### The RED Method (for request-driven services)

- **Rate:** Requests per second
- **Errors:** Errors per second
- **Duration:** Distribution of request latency

#### The USE Method (for resources)

- **Utilization:** Percentage of resource in use (CPU at 80%)
- **Saturation:** Work queued because resource is busy (run queue length)
- **Errors:** Error events on the resource (disk I/O errors)

### Alerting Best Practices

| Practice | Why | Example |
|----------|-----|---------|
| **Alert on symptoms, not causes** | Users care about latency, not CPU | Alert on "P99 latency > 500ms" not "CPU > 80%" |
| **Severity levels** | Not everything is a page | Critical (page on-call), Warning (ticket), Info (log) |
| **Include runbook link** | Responder needs context | Alert message includes link to troubleshooting steps |
| **Avoid alert fatigue** | Too many alerts = ignored alerts | Review and prune alerts quarterly; every alert must be actionable |
| **Set appropriate thresholds** | Too sensitive = noise; too lenient = missed issues | Use percentile-based thresholds (P99 > X) rather than averages |

### Dashboard Design

Every service should have a standard dashboard with:

1. **Request rate** (QPS) -- is traffic normal?
2. **Error rate** (4xx, 5xx) -- are requests failing?
3. **Latency** (P50, P95, P99) -- are requests slow?
4. **Saturation** (CPU, memory, disk, connections) -- are resources exhausted?
5. **Dependencies** (downstream error rate, latency) -- are dependencies healthy?

---

## Logging

### Log Levels

| Level | When to Use | Example |
|-------|------------|---------|
| **ERROR** | Something failed and needs attention | Database connection lost, payment processing failed |
| **WARN** | Something unexpected but handled | Retry succeeded, deprecated API called |
| **INFO** | Normal operational events | Request processed, user logged in, deployment started |
| **DEBUG** | Detailed diagnostic information | SQL queries, request/response bodies, cache hits/misses |

### Structured Logging

Always use structured (JSON) logging, not plain text:

**Bad:**
```
2024-01-15 10:23:45 ERROR Failed to process order 12345 for user 678
```

**Good:**
```json
{
  "timestamp": "2024-01-15T10:23:45Z",
  "level": "ERROR",
  "message": "Failed to process order",
  "order_id": "12345",
  "user_id": "678",
  "error": "payment_declined",
  "trace_id": "abc-123-def",
  "service": "order-service",
  "duration_ms": 2340
}
```

### Best Practices

- Include a correlation/trace ID in every log entry (links logs across services)
- Never log sensitive data (passwords, tokens, full credit card numbers, PII)
- Log at request boundaries (request received, response sent, downstream calls)
- Set appropriate retention (7 days for DEBUG, 30 days for INFO, 90+ days for ERROR)
- Use log aggregation (ELK, CloudWatch, Splunk) -- never rely on SSH-ing into servers

---

## Deployment Strategies

### Rolling Deployment

**How it works:** Replace instances one at a time. At any point, some instances run the old version and some run the new version.

| Pros | Cons |
|------|------|
| Zero downtime | Two versions running simultaneously (must be backward-compatible) |
| Simple to implement | Slow rollout for large fleets |
| Easy rollback (stop rolling, roll backward) | Mixed-version issues during deployment |

**Best for:** Stateless services, backward-compatible changes.

### Blue-Green Deployment

**How it works:** Run two identical environments (blue and green). Deploy new version to green. Switch traffic from blue to green. Keep blue as instant rollback.

| Pros | Cons |
|------|------|
| Instant rollback (switch back to blue) | Double the infrastructure cost |
| No mixed versions | Database schema changes are tricky (both versions need to work) |
| Full testing of green before switch | Requires sophisticated load balancer or DNS switching |

**Best for:** Critical services where instant rollback is essential.

### Canary Deployment

**How it works:** Route a small percentage of traffic (1-5%) to the new version. Compare metrics (latency, error rate) between old and new. Gradually increase traffic if metrics are healthy.

| Pros | Cons |
|------|------|
| Low risk (small blast radius) | More complex infrastructure |
| Real production testing | Requires good monitoring to detect issues |
| Data-driven promotion decisions | Two versions running simultaneously |

**Canary progression:**
1. Deploy to 1-2% of traffic
2. Wait 10-30 minutes, compare metrics
3. If healthy: increase to 10%, wait, compare
4. If healthy: increase to 50%, wait, compare
5. If healthy: promote to 100%
6. At any step: if metrics degrade, rollback to 0%

**Best for:** Large-scale services where you want data-driven confidence.

### Feature Flags

**How it works:** Deploy code with features behind flags. Enable features independently of deployment.

| Pros | Cons |
|------|------|
| Decouple deployment from release | Flag management complexity |
| Per-user or per-segment rollout | Dead flags accumulate (tech debt) |
| Instant disable without deployment | Testing combinatorial complexity |

**Best combined with:** Canary deployment. Deploy the code, then canary the feature flag.

---

## Disaster Recovery

### RPO and RTO

Two metrics define your disaster recovery requirements:

| Metric | Question | Example |
|--------|----------|---------|
| **RPO (Recovery Point Objective)** | How much data can you afford to lose? | RPO = 1 hour means you need at least hourly backups |
| **RTO (Recovery Time Objective)** | How long can you be down? | RTO = 15 minutes means automated failover is required |

### Disaster Recovery Strategies

| Strategy | RPO | RTO | Cost | How It Works |
|----------|-----|-----|------|-------------|
| **Backup and restore** | Hours | Hours | Low | Periodic backups to S3; restore on failure |
| **Pilot light** | Minutes | Minutes-hours | Medium | Minimal replica running; scale up on failure |
| **Warm standby** | Seconds-minutes | Minutes | High | Scaled-down replica always running; scale up on failure |
| **Multi-site active-active** | Near-zero | Near-zero | Very high | Full copy in each region; both serve traffic |

### Backup Best Practices

- **3-2-1 rule:** 3 copies, 2 different media types, 1 offsite
- **Test restores regularly** -- an untested backup is not a backup
- **Automate backup verification** -- checksum validation, test restore to staging
- **Encrypt backups** -- at rest and in transit
- **Define retention** -- daily for 7 days, weekly for 4 weeks, monthly for 12 months

---

## Data Center Redundancy

### Active-Passive

```
Primary DC: Serves all traffic
Secondary DC: Hot standby, receives replicated data
Failover: DNS or load balancer switches to secondary
```

| Pros | Cons |
|------|------|
| Simpler (one write path) | Wasted capacity in passive DC |
| No conflict resolution needed | Failover takes time (DNS TTL, warmup) |
| Clear data authority | Secondary may have replication lag |

### Active-Active

```
DC-A: Serves region A traffic, replicates to DC-B
DC-B: Serves region B traffic, replicates to DC-A
```

| Pros | Cons |
|------|------|
| Full utilization of both DCs | Write conflicts between DCs |
| Lower latency (users hit nearest DC) | Complex data synchronization |
| No failover needed (traffic redirects) | Must handle split-brain scenarios |

### Key Challenges

| Challenge | Solution |
|-----------|---------|
| **Data synchronization** | Async replication with conflict resolution (LWW, CRDTs) |
| **Session management** | Centralized session store (Redis) or stateless sessions (JWT) |
| **Cache consistency** | Accept eventual consistency or use distributed cache |
| **Traffic routing** | GeoDNS routes users to nearest DC; health-check-based failover |

---

## Autoscaling

### What to Scale On

| Metric | When to Use | Example |
|--------|------------|---------|
| **CPU utilization** | Compute-bound workloads | Scale up when CPU > 70% for 5 minutes |
| **Memory utilization** | Memory-bound workloads | Scale up when memory > 80% |
| **Request rate** | Traffic-driven scaling | Scale up when QPS > 1000 per instance |
| **Queue depth** | Worker-based processing | Scale up when queue > 10,000 messages |
| **Custom metrics** | Business-specific | Scale up when active WebSocket connections > 5,000 per instance |

### Scaling Configuration

| Parameter | Recommendation | Why |
|-----------|---------------|-----|
| **Min instances** | At least 2 (for redundancy) | Survives single instance failure |
| **Max instances** | Set a cap (cost protection) | Prevents runaway scaling from bugs or attacks |
| **Scale-up threshold** | 70% utilization | Leave headroom for traffic spikes during scale-up |
| **Scale-down threshold** | 30% utilization | Avoid flapping (scaling up and down repeatedly) |
| **Cooldown period** | 5-10 minutes | Prevents rapid oscillation |

### Scaling Strategies

| Strategy | How It Works | Best For |
|----------|-------------|----------|
| **Reactive** | Scale based on current metrics | Unpredictable traffic |
| **Scheduled** | Pre-scale for known patterns | Predictable peaks (morning rush, end-of-day batch) |
| **Predictive** | ML-based prediction of future load | Gradual ramps with some predictability |

### Common Autoscaling Mistakes

| Mistake | Consequence | Fix |
|---------|------------|-----|
| No max limit | Runaway costs or resource exhaustion | Always set max instances |
| Scaling on average, not percentile | Miss tail latency issues | Scale on P95/P99 latency or queue depth |
| Too aggressive cooldown | Flapping (scale up, scale down, repeat) | Set cooldown to 5-10 minutes |
| Scaling only the web tier | Database becomes bottleneck | Scale all tiers (web, cache, database connections) |
| No load testing | Unknown scaling behavior | Load test to find breaking points before production |

---

## Operational Readiness Checklist

Before going to production, verify:

| Category | Check |
|----------|-------|
| **Health** | Liveness and readiness probes configured |
| **Monitoring** | Dashboard with four golden signals |
| **Alerting** | Critical alerts with runbooks |
| **Logging** | Structured logs with trace IDs |
| **Deployment** | Rollback plan tested |
| **Scaling** | Autoscaling configured with min/max |
| **Backup** | Backup schedule defined, restore tested |
| **DR** | RPO/RTO defined, failover tested |
| **Security** | Secrets in vault, TLS everywhere, access controlled |
| **Documentation** | Architecture diagram, runbooks, on-call rotation |