Wide layout

Table of contents

System Design Learning Notes - Byte Byte Go

Comprehensive system design notes covering scalability, design patterns, and real-world system implementations

No title

This document contains comprehensive notes on system design principles, architectures, and patterns based on the Byte Byte Go course and system design interviews.

System Design Interview Basics

No title

An interviewee is evaluated based on how they analyze a vague problem and solve it step by step. System design questions are open-ended with many variations and differences, just like in the real world.

Key Concepts

  • The desired outcome is to come up with an architecture that achieves system design goals

  • Discussions could go in different directions depending on the interviewer

  • Some interviewers may choose high-level architecture to cover all aspects

  • Others might focus on one or more specific areas

Scale from Users to Millions

No title

Designing a system that supports millions of users is challenging and requires continuous refinement and endless improvement.

Choosing the Right Database

For most developers, relational databases are the best option as they have proven themselves over 40 years. However, consider non-relational databases if:

  • Your application requires super-low latency

  • Your data is unstructured, or you don't have relational data

  • You only need to serialize and deserialize data (JSON, XML, YAML, etc.)

  • You need to store a massive amount of data

Horizontal vs Vertical Scaling (Web Tier)

When traffic is low, vertical scaling is an option, but it has serious limitations:

  • Hard limit: impossible to add unlimited CPU and memory to a single server

  • No failover and redundancy: single point of failure

Horizontal scaling addresses these by distributing load across multiple servers.

Load Balancer (Web Tier)

Private IPs are used for communication between servers for better security. A load balancer routes traffic efficiently:

  • If a server goes offline, traffic routes to healthy servers

  • As traffic grows, add more servers to the pool automatically

Database Scaling (Data Tier)

Use a master-slave replication model:

  • Master database handles write operations

  • Slave databases handle read operations

  • Read-heavy applications benefit from multiple slaves

Advantages of Database Replication

  • Better performance: writes and updates go to master; reads distributed across slaves

  • Reliability: data preserved across multiple locations

  • High availability: system operates even if a database is offline

Caching

No title

A cache temporarily stores expensive responses or frequently accessed data in memory for faster subsequent requests.

Benefits

  • Better system performance

  • Reduced database workloads

  • Independent cache tier scaling

Read-Through Cache Pattern

Application checks cache first. On cache miss, query database, store in cache, return data.

Caching Strategies

Cache Aside

mermaid
graph LR
    client((Client))
    cache[(Cache)]
    database[(Database)]

    client <-.-> | 1. no data in cache | cache
    client <--> | 2. read from database | database
    client -.-> | 3. write to cache | cache
    client --> | 4. return data | response

Pros:

  • Works best for read-heavy workloads

  • Application can function if cache is down (slower)

  • Cache can differ from database data model

Cons:

  • Cache invalidation required when data changes

  • Or rely on TTL expiration

Read-Through Cache

Sits inline between client and database. Library or cache provider handles fetching logic.

Cons:

  • Data model must match database

  • Inconsistency possible if cache not updated after database change

Write-Through Cache

Application writes to cache, which updates database. Both remain consistent.

Pros:

  • Used for write-heavy workloads

Cons:

  • Higher write latency (wait for database write)

Write-Around Cache

Direct writes to database; only reads cached.

Write-Back Cache

Application writes to cache; cache asynchronously writes to database.

Cons:

  • Data inconsistency possible

  • Data persistence not guaranteed

Considerations When Using Cache

  • When to cache: Data read frequently but modified infrequently

  • Expiration policy: Implement appropriate TTL to balance staleness vs. reload frequency

  • Consistency: Keep data store and cache in sync

  • Mitigating failures: Multiple cache servers across data centers prevent SPOF

  • Eviction policy: LRU (Least Recently Used) most popular; also LFU, FIFO

CDNs (Content Delivery Networks)

mermaid
graph LR
    client((Client))
    cdn[(CDN)]
    origin[(Origin Server)]

    client --> | 1. request | cdn -.-> | 2. if not in cdn request | origin
    origin --> | 3. response | cdn --> | 4. cdn response | client

Best Practices:

  • Implement fallback to origin server if CDN fails

  • Don't cache infrequently accessed data

  • Set correct cache headers (expires, cache-control)

  • Invalidate objects when deleted from origin

  • Use object versioning: https://cdn.example.com/image.jpg?v=1.0

Stateless Architecture

Keep web tier stateless to enable horizontal scaling. Session state stored outside data tier in NoSQL for scalability and performance.

Availability Zones

In multi-data center setup, use geoDNS to route users to closest data center.

Technical Challenges:

  • Traffic redirection: Use geoDNS to direct to nearest data center

  • Data synchronization: Replicate data across data centers

  • Testing and deployment: Test at different locations; automated deployment tools essential

Message Queues

Decouple sender and receiver. Both publisher and subscriber scale independently.

Benefits:

  • Consumer can read messages even when producer unavailable

Logging, Metrics, and Automation

Logging: Monitor error logs per server or aggregate to centralized service

Metrics:

  • Host level: CPU, Memory, disk I/O

  • Aggregated level: database tier, cache tier performance

  • Key business metrics: DAU, retention, revenue

Automation: CI/CD practices, automated build/test/deploy

Database Scaling

Vertical Scaling

Add more CPU, RAM to database server. Limitations: hardware limits, higher costs, SPOF risk.

Horizontal Scaling (Sharding)

Distribute data across multiple servers using sharding key.

Critical Factor: Choose sharding key that evenly distributes data.

Challenges:

  • Resharding: When shard exhausts capacity or uneven distribution

  • Celebrity problem (hotspot key): Excessive access to specific shard

  • Join and de-normalization: Hard to perform joins across shards; use de-normalization

Scaling to Millions of Users

Summary of techniques:

  • Keep web tier stateless

  • Build redundancy at every tier

  • Cache data as much as possible

  • Support multiple data centers

  • Host static assets in CDN

  • Scale data tier by sharding

  • Split tiers into individual services

  • Monitor system and use automation tools

Back of the Envelope Estimations

No title

Understanding scalability basics enables effective estimations.

Power of Two

Power
Approximate Value
Full Name
Short Name

10

1 Thousand

Kilobyte

KB

20

1 Million

Megabyte

MB

30

1 Billion

Gigabyte

GB

40

1 Trillion

Terabyte

TB

50

1 Quadrillion

Petabyte

PB

Key relationships:

  • 1 PB = 10^6 GB = 10^9 MB = 10^12 KB = 10^15 bytes

  • 1000 KB = 1 MB; 1000 MB = 1 GB; 1000 GB = 1 TB; 1000 TB = 1 PB

Latency Numbers Every Programmer Should Know

Operation
Time

L1 cache reference

0.5 ns

Branch mispredict

5 ns

L2 cache reference

7 ns

Mutex lock/unlock

100 ns

Main memory reference

100 ns

Compress 1 KB with Zippy

10 µs

Send 2 KB over 1 Gbps network

20 µs

Read 1 MB sequentially from memory

250 µs

Round trip within same datacenter

500 µs

Disk seek

10 ms

Read 1 MB sequentially from network

10 ms

Read 1 MB sequentially from disk

30 ms

Send packet CA (California) → Netherlands → CA

150 ms

1s = 1000 ms = 1,000,000 µs = 1,000,000,000 ns

Availability Numbers

High availability is continuous operation measured as percentage. Cloud providers set SLAs at 99.9% or above.

Availability %
Downtime per Year

99%

3.65 days

99.99%

52.60 minutes

99.999%

5.26 minutes

99.9999%

31.56 seconds

Twitter Example

Assumptions:

  • 300 million monthly active users

  • 50% use Twitter daily

  • Average 2 tweets per day

  • 10% of tweets contain media

  • Data stored for 5 years

QPS Estimate:

  • Daily Active Users (DAU) = 300M × 50% = 150M

  • Tweets QPS = 150M × 2 ÷ 24 ÷ 3600 ≈ 3,500 QPS

  • Peak QPS = 2 × 3,500 ≈ 7,000 QPS

Storage Requirements:

  • Average tweet: tweet_id (64 bytes) + text (140 bytes) + media (1 MB)

  • Media storage = 150M × 2 × 10% × 1 MB = 30 TB/day

  • 5-year storage = 30 TB × 365 × 5 ≈ 55 PB


System Design Interview Framework

No title

A system design interview simulates real-world problem solving where two co-workers collaborate on an ambiguous problem.

Key Principles

  • The process matters more than the final design

  • Demonstrate design skill, defend choices, respond to feedback

  • Shows ability to collaborate, work under pressure, resolve ambiguity

  • Watch for red flags: over-engineering, narrow-mindedness, stubbornness

Step 1: Understand the Problem and Establish Design Scope (3-10 min)

  • Don't jump to solution immediately

  • Ask clarifying questions

  • Write assumptions on whiteboard

  • Ask about: features, user count, scale timeline, tech stack, existing services

Example Questions:

  • Is this mobile, web, or both?

  • What are the most important features?

  • How many daily active users?

  • What's the traffic volume?

  • Can feed contain images, videos, or just text?

Step 2: Propose High-Level Design and Get Buy-In (10-15 min)

  • Create initial blueprint with key components

  • Use diagrams: clients, APIs, servers, data stores, caches, queues

  • Perform back-of-envelope calculations

  • Review concrete use cases

  • Decide on API endpoints and database schema based on complexity

  • Communicate throughout

Step 3: Design Deep Dive (10-25 min)

  • Work with interviewer to decide which components to detail

  • Focus on: performance bottlenecks, resource estimations, specific features

  • Be attentive to interviewer's preferences (high-level vs. detailed performance)

  • Avoid unnecessary details that don't demonstrate scalability knowledge

  • Stay focused on meaningful components

Step 4: Wrap Up (3-5 min)

  • Identify system bottlenecks and suggest improvements

  • Recap design (especially for long sessions)

  • Discuss error handling, monitoring, metrics, rollout

  • Discuss scale adjustments (1M → 10M users)

  • Propose refinements if time allows

Time Distribution (45-minute interview)

  • Step 1: 3-10 minutes

  • Step 2: 10-15 minutes

  • Step 3: 10-25 minutes

  • Step 4: 3-5 minutes

Dos

  • Always seek clarification

  • Understand requirements

  • Communicate thoughts

  • Suggest multiple approaches; focus on critical components first

  • Work collaboratively

Don'ts

  • Skip typical preparation

  • Dive into solution without clarifying

  • Focus too much on single component early

  • Hesitate to ask for help

  • Consider interview finished until interviewer indicates so

Design a Rate Limiter

Understanding the Problem

Benefits:

  • Prevent DoS attacks via resource starvation

  • Reduce costs for paid third-party services

  • Prevent server overload and handle misbehavior

Design Requirements:

  • Server-side implementation

  • Flexible rules (IP, user ID, etc.)

  • Distributed environment capable

  • Low latency, minimal memory

  • Robust, fault-tolerant

  • Clear feedback on throttling

Implementation Approaches

  • Client-side: Not reliable; clients easily manipulated

  • Server-side: More secure; middleware placement

  • API Gateway: Rate limiting in cloud microservices (also handles SSL, auth)

Rate Limiting Algorithms

Token Bucket Algorithm

Tokens added periodically; each request consumes one token.

Key Parameters:

  • Bucket size: max tokens allowed

  • Refill rate: tokens added per second

Bucket Determination:

  • Different buckets for different endpoints

  • Separate bucket per IP or user

  • Global bucket for system maximum

Pros:

  • Easy to implement

  • Memory efficient

  • Allows traffic bursts

Cons:

  • Parameters need careful tuning

Leaky Bucket Algorithm

Fixed-rate queue; requests processed at constant rate.

Key Parameters:

  • Bucket size: queue capacity

  • Outflow rate: requests processed per second

Pros:

  • Memory efficient

  • Stable outflow rate

Cons:

  • Burst traffic fills queue with old requests

  • Two parameters to tune

Fixed Window Counter Algorithm

Timeline divided into fixed windows; counter per window.

Limitation: Spike at window edges allows more requests than quota.

Pros:

  • Memory efficient

  • Easy to understand

  • Resets at window boundary

Cons:

  • Traffic spike at window edges

Sliding Window Log Algorithm

Maintain log of request timestamps in sliding window.

Process:

  1. Remove timestamps older than window

  2. Check if count within limit

  3. Allow or reject request

Pros:

  • Very accurate; enforces limit in rolling window

Cons:

  • High memory consumption

Sliding Window Counter Algorithm

Similar to fixed window but window slides with time.

Formula: Current window requests + (Previous window requests × overlap %)

Pros:

  • Smooth out traffic spikes

  • Memory efficient

Cons:

  • Approximate rate (assumes even distribution)

  • Only works for not-so-strict lookback windows

High-Level Design

mermaid
graph LR
    request --> rate_limiter((Rate\nLimiter))
    redis[(Redis)] -.-> rate_limiter
    rate_limiter --> forward_req[Forward request]
    rate_limiter --> reject_req[Reject request]
  • Client sends request to middleware

  • Rate limiter fetches counter from Redis

  • If limit reached, reject

  • Otherwise, forward and increment counter

Rate Limiting Rules

yaml
domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

Rate Limited Response Headers

HTTP 429 (Too Many Requests) response with headers:

  • X-Ratelimit-Remaining: remaining requests in window

  • X-Ratelimit-Limit: calls allowed per window

  • X-Ratelimit-Retry-After: seconds until next request allowed

Race Conditions in Distributed Systems

Without proper handling, concurrent rate limiters can increment incorrectly.

Solution: Redis Sorted Sets

Use atomic operations (ZADD, ZREMRANGEBYSCORE) that prevent concurrent interference.

py
function rateLimiter(user_id, current_timestamp, limit, interval):
    redis_key = "rate_limit:" + user_id

    # Remove outdated requests
    Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)

    # Add current request
    Redis.ZADD(redis_key, current_timestamp, current_timestamp)

    # Fetch all requests in window
    request_count = Redis.ZRANGE(redis_key, 0, -1)

    # Check limit
    if request_count > limit:
        return 429, "Too Many Requests"

    return 200, "Request Accepted"

Sorted sets provide atomicity; no two operations overlap.

Monitoring

Ensure:

  • Algorithm is effective

  • Rules are effective

  • Adjust rules if too strict or ineffective for spike traffic

Back of the Envelope Calculations

Memory for Redis storage:

text
No. users = 1 million
Max requests per user = 1 RPS
Max timestamps stored = 60
Total memory = 1M × 60 × 8 bytes = 480 MB

CPU requirements:

text
Operations/second = 1M users × 1 RPS = 1M ops/sec
Ops needed = 4 operations per request (log N) = 4M ops/sec
Redis: 100K ops/sec per core
Cores needed = 40

Design Consistent Hashing

No title

Consistent hashing enables efficient distribution of requests/data across servers for horizontal scaling.

Hash Space and Hash Ring

  • Hash space: range of hash values (typically circle)

  • Use SHA-1: hash value between 0 and 2^160 - 1

  • Each server placed on ring using hash of IP/name

Problems with Traditional Hashing

  • Uniform distribution possible

  • Single shard can become hotspot receiving disproportionate requests

Virtual Nodes (vnodes)

Improve load balancing and fault tolerance:

  • Multiple virtual nodes per physical server (not just one)

  • Better balanced data distribution

  • Improved shard reallocation management

  • Servers with higher capacity get more vnodes

If server has high capacity, it can be represented by more virtual nodes.

Design a Key-Value Store

No title

A key-value database stores unique identifiers as keys with associated values.

Understanding the Problem

Tradeoffs:

  • Read vs. write vs. memory usage

  • Consistency vs. availability

Design Characteristics:

  • Small key-value pairs (< 10 KB)

  • Support big data

  • High availability

  • High scalability

  • Automatic scaling

  • Tunable consistency

  • Low latency

Single Server Key-Value Store

Approach: Store pairs in hash table (in-memory).

Optimizations:

  • Data compression

  • Store frequently used data in memory; rest on disk

Scales up quickly to need for distributed store.

Distributed Key-Value Store (Distributed Hash Table)

No title

Critical: Understand CAP theorem.

CAP Theorem

Impossible to provide more than two of:

  • Consistency: All clients see same data at same time

  • Availability: Any client request gets response (even with some nodes down)

  • Partition Tolerance: System operates despite network disruptions

System Types:

  • CP Stores: Consistent, Partition tolerant (sacrifice availability)

    • Examples: Google Bigtable, Apache HBase

    • If partition down, writes fail until fixed

  • AP Stores: Available, Partition tolerant (sacrifice consistency)

    • Examples: Amazon Dynamo, Apache Cassandra

    • System available but data may be inconsistent

  • CA Stores: NOT PRACTICAL in real-world distributed systems

    • Examples: RDBMS, Google Spanner

    • Network partitions will happen; must tolerate them

Data Replication

Quorum Consensus

text
W (write acks needed) + R (read replicas needed) > N
  • R = 1, W = N: Optimized for fast reads

  • W = 1, R = N: Optimized for fast writes

  • W + R > N: Strong consistency guaranteed (Usually N=3, W=R=2)

Consistency Models

Strong Consistency: Client always sees latest data.

Weak Consistency: Client may see stale data.

Eventual Consistency: Client eventually sees latest data (specific form of weak consistency).

Inconsistency Resolution

Use vector clocks tracking updates:

json
{
	"A": [
		["node_a", 1],
		["node_b", 2]
	]
}

When conflicts occur:

  • Accept value with largest counter

  • "Last write wins" if same vector value (but prone to clock skew)

  • Application-level resolution (Cassandra approach)

  • Merge conflicting versions

  • Manual intervention

Handling Failures

Gossip Protocol

Nodes periodically communicate with random subset of others, sharing system state.

Properties:

  • Random communication periodically

  • Eventual consistency

  • Decentralized (no central authority)

  • Highly fault-tolerant

  • Highly scalable

How it Works:

  1. Node detects change

  2. Each interval, select random node and share information

  3. Receiving node merges info and may share back

  4. Information spreads exponentially

Advantages:

  • Scalable

  • Fault-tolerant

  • Decentralized

  • Simple/efficient

  • Exponential spread

Disadvantages:

  • Only eventual consistency

  • Duplicate information possible

  • Convergence latency

  • Network overhead if gossip too frequent

Merkle Trees (Permanent Failure)

Detect and sync missing data:

  • Divide key space into equal buckets

  • Hash values in each bucket

  • Build tree bottom-up; root hash stored

  • Compare root hash: if same, data matches

  • If different, traverse tree to find differences

  • Transfer missing data after merge conflict resolution

System Diagram

mermaid
graph LR
    client[Client] --> |read, write| coordinator[(Coordinator)]
    coordinator --- node_a[(Node A)] --- node_b[(Node B)]
    node_b --- node_c[(Node C)]
    node_c --- node_d[(Node D)]
    node_d --- node_e[(Node E)]
    node_e --- coordinator
  • Simple APIs: get(key), put(key, value)

  • Coordinator acts as proxy

  • Nodes distributed on ring (consistent hashing)

  • Completely decentralized; auto node addition/removal

  • Data replicated at multiple nodes

  • No SPOF; each node same responsibilities

  • Other node takes coordinator role on failure

Each Node Tasks

  • Replication

  • Failure detection

  • Conflict resolution

  • Storage engine

LSM Trees

Log-Structured Merge Tree optimizes high write throughput.

Structure:

  • Memtable: in-memory buffer for writes

  • WAL (Write-Ahead Log): disk persistence on crash

  • SSTables: Sorted String Tables (immutable)

Process:

  • Writes go to memtable and WAL

  • When full, flush memtable to SSTable

  • SSTables merged via compaction to reduce count

Read optimization:

  • Check memtable first

  • Use Bloom Filter to determine which SSTable has key

  • Read from correct SSTable

Summary

Goal
Technique

Big data storage

Consistent hashing

High availability reads

Data replication, Multi-datacenter

High availability writes

Versioning, vector clocks

Dataset partition

Consistent hashing

Incremental scalability

Consistent hashing

Heterogeneity

Consistent hashing

Tunable consistency

Quorum consensus

Temporary failure handling

Sloppy quorum, hinted handoff

Permanent failure handling

Merkle tree

Datacenter outage

Cross-datacenter replication


Design a Unique ID Generation System

Design Requirements

  • IDs must be unique

  • Numerical values only

  • Fit into 64-bit

  • Ordered by date

  • Generate > 10,000 unique IDs per second

Number Scales

  • Thousand = 10³

  • Lakh = 10⁵

  • Million = 10⁶

  • Billion = 10⁹

  • Trillion = 10¹²

  • Quadrillion = 10¹⁵

Time Units

  • 1 second = 1,000 ms = 1,000,000 µs = 1,000,000,000 ns

UUID vs ULID

Cannot use due to size (128 bits vs required 64 bits):

Feature
UUID
ULID

Size

128 bits (32 hex chars)

128 bits (26 Base32 chars)

Uniqueness

Extremely high

Extremely high

Sortability

Not lexicographically

Sortable by time

Timestamp

Only in UUIDv1

Built-in (48-bit)

Readability

Not human-readable

More compact

Use Case

Random/time-based/custom

Time-based with randomness

Adoption

Standardized, widespread

Newer, growing

Design a URL Shortening Service

Problem Understanding

  • Long URLs to short URLs: google.com/search?q=X → tinyurl.com/abc123

  • 100 million URLs per day

  • As short as possible

  • Character set: [a-zA-Z0-9] (62 characters)

  • Shortened URLs cannot be updated/deleted

Back of the Envelope Calculation

  • 100 million URLs per day writes

  • Write QPS = 100M ÷ 24 ÷ 60 ÷ 60 ≈ 1,157 URLs/sec

  • Read QPS (10:1 ratio) ≈ 11,570 reads/sec

  • 10-year lifecycle: 100M × 365 × 10 = 365 billion URLs

  • Storage: 365 billion × 100 bytes ≈ 36.5 TB

Note: 1 TB = 2^40 bytes = 1,099,511,627,776 bytes

High-Level Design

mermaid
sequenceDiagram
    participant client
    participant tinyUrlService
    participant resourceService

    client ->> tinyUrlService: shorten(url)
    tinyUrlService -->> client: tinyUrl

    client ->> tinyUrlService: tinyUrl
    tinyUrlService -->> client: 302 redirect, location
    client ->> resourceService: location

Redirect Types

Permanent (301):

  • Client caches redirect

  • Subsequent requests go directly to resource

  • Low server load but miss analytics

Temporary (302):

  • Client queries URL service each time

  • High server load but tracks analytics

Design Deep Dive

Short URL Character Combinations

With 62 characters:

Length
Max URLs

1

62

2

3,844

3

238,328

4

14,776,336

5

916,132,832

6

56,800,235,584

7

3.5 trillion

7 characters sufficient for 3.5 trillion URLs.

Hashing vs Base62 Conversion

Aspect
Hash + Collision Resolution
Base 62 Conversion

Short URL length

Fixed

Variable (grows with ID)

Unique ID generator

Not needed

Required

Collision handling

Possible, needs resolution

Not possible

Predictability

Unpredictable

Can predict next short URL (security concern)

Hashing Approach

On hash collision, generate new hash with random salt.

Optimization: Use Bloom Filter to reduce database lookups.

Base 64 Encoding Approach

  • Cannot have unique IDs for same URLs

  • Possible to predict URL existence by incrementing ID

URL Shortening Process

mermaid
graph TD
    longUrl[Long URL] --> inDB{longURL in DB?}
    inDB -- yes --> returnShort[Return existing short URL]
    inDB -- no --> genID[Generate new ID]
    genID --> encode[Convert ID to short URL]
    encode --> save[Save ID, short URL, long URL]
  • Use distributed ID generator

  • Base 64 encode ID to short URL

  • Store in database

Design a Web Crawler

Problem Understanding

  • 1 billion pages per month (search engine indexing)

  • HTML only

  • Consider newly added/edited pages

  • Store HTML for 5 years

  • Ignore duplicate content

Additional Requirements:

  • Scalability: parallelize across billions of pages

  • Robustness: handle bad HTML, unresponsive servers, malicious links

  • Politeness: don't overload websites

  • Extensibility: support new content types with minimal changes

Back of the Envelope Calculation

  • 1 billion pages/month = 1B ÷ 30 ÷ 24 ÷ 60 ÷ 60 ≈ 385.8 pages/sec ≈ 400 pages/sec

  • Peak QPS = 2 × 400 = 800 pages/sec

  • Average page: 500 KB

  • Storage: 1B × 500 KB = 500 TB per month

  • 5-year storage: 500 TB × 12 × 5 = 30 PB

High-Level Design Flow

mermaid
graph TD
    A[Seed URLs] --> B[URL Frontier]
    B --> C[HTML Downloader]
    C --> D[Content Parser]
    D --> F{Content Seen?}
    F -- Yes --> G[Discard]
    F -- No --> H[Link Extractor]
    H --> I[URL Filter]
    I --> J{URL Seen?}
    J -- Yes --> K[Skip]
    J -- No --> L[Add to URL Frontier]
    F --> M[(Content Storage)]
    J --> N[(URL Storage)]
    N -.-> |check status| B

Design Deep Dive

DFS vs BFS

BFS preferred for:

  • Even coverage across domains

  • High-priority page prioritization

  • Rate-limiting implementation

  • Better resource management

URL Frontier

Avoid DDOS by not sending requests to same domain too frequently. Add artificial delay.

mermaid
graph LR
    urlFrontier[URL Frontier] --> queueMapper[Queue Mapper]
    queueMapper --> q1[[wikipedia.com]] --> w1[Worker 1]
    queueMapper --> q2[[google.com]] --> w2[Worker 2]
    queueMapper --> q3[[facebook.com]] --> w3[Worker 3]

Two-queue system:

  1. Priority queue: manages URL importance

  2. Domain queue: manages politeness

Freshness

Periodically recrawl to keep content fresh.

Strategies:

  • Prioritize frequently updated pages

  • Prioritize important pages

Update frequency: Check HTTP headers for last-modified date.

HTML Downloader

Respect robots.txt to avoid crawling disallowed pages.

Performance Optimizations

  • Distributed crawling

  • DNS caching

  • Select datacenter closest to domain

  • Short timeouts for unresponsive servers

Detect and Avoid Problematic URLs

  • Duplicate content detection via hashing

  • Avoid spider traps (infinite loops)

  • Filter data noise (ads, comments)

Server-Side Rendering (SSR)

Many sites use SSR; parsing HTML without SSR misses dynamically generated content.

Design a Notification System

Problem Understanding

  • 10 million mobile push notifications

  • 1 million SMS messages

  • 5 million emails

High-Level Design

mermaid
flowchart LR
    S1[Service 1] --> NS[Notification Servers]
    S2[Service 2] --> NS
    SN[Service N] --> NS

    NS --> Cache[(Cache)]
    Cache --> DB[(DB)]

    NS --> iOSQ[[iOS PN Queue]]
    NS --> AndroidQ[[Android PN Queue]]
    NS --> SMSQ[[SMS Queue]]
    NS --> EmailQ[[Email Queue]]

    iOSQ --> iOSW[iOS Workers]
    AndroidQ --> AndroidW[Android Workers]
    SMSQ --> SMSW[SMS Workers]
    EmailQ --> EmailW[Email Workers]

    iOSW --> APNs[APNs]
    AndroidW --> FCM[FCM]
    SMSW --> SMS[SMS Service]
    EmailW --> Email[Email Service]

Delivery Guarantees

  • At-most-once: May not deliver; never more than once

  • At-least-once: Delivers at least once; might duplicate

  • Exactly-once: Delivered exactly once (theoretical; doesn't account for network failures)

Additional Components

  • Notification templates

  • Frequency capping

  • Opt-out mechanism

  • Retry logic

  • Queued notification monitoring

  • Analytics (delivery/failure/open rates)

Low-Level Details

Exactly-once guarantee implementation:

  • Check eventId in notification log

  • Discard if present

  • Add to log on successful delivery


Design a News Feed System

Problem Understanding

  • Users post stories and view friends' stories

  • Feed in reverse chronological order

  • 5,000 friends max

  • 10 million DAU

  • Images, videos, links supported

Fanout Service (Two Models)

Fanout on Write (Push Model)

Pre-computes feed during write; delivers to friends' caches immediately.

Pros:

  • Real-time feed generation

  • Fast retrieval (pre-computed)

Cons:

  • Hotkey problem for users with many friends

  • Wastes resources on inactive users

Fanout on Read (Pull Model)

Generates feed on-demand when user loads homepage.

Pros:

  • Better for inactive users

  • No hotkey problem

Cons:

  • Slower feed retrieval

Hybrid Approach

Use push for most users; pull for celebrities/power users.

Design a Chat System

Problem Understanding

  • 1:1 and group chat

  • 50 million DAU

  • Max group: 100 users

  • Online indicator

  • Text only

  • Max text: 1 million characters

Long Polling

Server waits for new messages before sending. Client/server terminate on timeout; client reconnects.

Scalability Calculation

  • 10KB memory per connection

  • 50 million DAU: 500 GB memory

  • 10% online: 50 GB memory

Database Selection

Traditional RDBMS not ideal for chat due to long-tail data and random I/O issues.

Cassandra: LSM-based, optimized for high writes ClickHouse: Columnar, optimized for analytics

Data Models

Message Table:

Column
Type

message_id (PK)

UUID

sender_id

UUID

receiver_id

UUID

content

TEXT

created_at

TIMESTAMP

Group Message Table:

Column
Type

channel_id (PK)

UUID

message_id (CK)

UUID

sender_id

UUID

content

TEXT

created_at

TIMESTAMP

Use ULID/Snowflake IDs for sortability.

Message Flow

One-on-One:

  1. Sender → Chat Server 1

  2. → Message Queue

  3. → Chat Server 2

  4. → Receiver

Group Chat:

  • One queue per user in group

Online Indicator

Use short polling (heartbeat every 5s) to presence service. Mark offline after timeout.

Design a Search Autocomplete System

Problem Understanding

  • Match query prefix only

  • Sort by historical frequency

  • No spell check

  • English, lowercase alphanumeric

  • 10 million DAU

Back of the Envelope Calculation

text
DAU = 10 million
Avg queries/user/day = 10
Query length = 20 bytes
Queries/day = 10 × 10M × 20 = 2 billion
Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
Peak QPS = 2 × 23,148 ≈ 46,296 QPS
Daily writes = 20% × 2B = 400 million
Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GB

Trie Data Structure

No title

Prefix Trie: Efficient for prefix-based searches.

Optimization: Cache frequent queries at each node.

Constructing Prefix Trie

Process:

  1. Collect queries in analytics log

  2. Aggregate by week

  3. Workers build trie from aggregated data

  4. Update trie database/cache

Querying Trie

  1. User types query

  2. API checks trie cache

  3. On miss, query trie database

  4. Return top K results

Sharding: Use first 3 characters for hash-based sharding.


Design YouTube

Problem Understanding

  • Upload and watch videos

  • All clients (mobile, web, smart TV)

  • 5 million DAU

  • 30 mins active usage/day

  • International support

  • All audio/video formats

  • Encryption required

  • 1 GB max video size

  • Can leverage cloud tech

Back of the Envelope Calculation

text
5M DAU × 30 min/day = 150M total viewing minutes/day
5 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
Average video: 300 MB
Storage/day = 500K × 300 MB = 150 TB
CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/day

Video Transcoding Pipeline

Why: Raw video large; not all devices support all formats; quality adjustment for bandwidth.

Components:

  • Container (format): MP4, AVI, MKV

  • Codec (compression): H.264, H.265, VP9

Directed Acyclic Graph (DAG) Model

Parallel processing of video inspection, encoding, thumbnail generation, watermarking, audio encoding, then assembly.

Resource Allocation

Resource manager decides:

  • Which worker processes task

  • Task processing priority

  • Worker return to pool after processing

System Optimizations

  • Parallel processing (split long videos)

  • Parallel uploads (chunked with retry)

  • Upload centers closer to users

  • Queuing between pipeline steps

Safety Optimizations

  • Pre-signed URLs (limited, expirable, metadata)

  • E2E encryption

  • DRM solutions

  • Visual watermarks

Cost Optimizations

  • Serve popular content from CDN

  • Regional distribution

  • On-demand encoding for unpopular videos

  • Build custom CDN (like Netflix)

  • Efficient storage management

Design a Payment System

Problem Understanding

  • E-commerce payment backend

  • Credit cards example

  • Third-party PSP (Stripe, PayPal)

  • No stored credit card data

  • Global, single currency

  • 1 million transactions/day

  • Pay-in and pay-out flows

  • Reconciliation required

Back of the Envelope Calculation

text
1 million transactions/day
= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPS

High-Level Design

mermaid
graph LR
    subgraph internal
        payment_service[Payment Service]
        payment_executor[Payment Executor]
    end

    subgraph external
        psp[PSP]
        card_schemes[Card Schemes]
    end

    client --> LB --> payment_service --> payment_executor --> psp --> card_schemes
    payment_service --> ledger[(Ledger)]
    payment_service --> wallet[(Wallet)]

Components

  • Payment Service: Validates payments, compliance checks

  • Payment Executor: Executes sequence of payment operations

  • Card Schemes: VISA/Mastercard processing

  • Ledger: Transaction history

  • Wallet: Current user/seller balance

Payment API Design

/v1/payments

Executes payment event with buyer info, checkout ID, credit card (encrypted/token), and payment orders list.

Store currency amounts as strings, not floats, to avoid precision loss.

/v1/payments?id={payment_order_id}

Returns payment order status.

Data Models

Payment Event Table:

  • checkout_id (PK)

  • buyer_info

  • seller_info

  • credit_card_info

  • status

Payment Order Table:

  • payment_order_id (PK)

  • checkout_id (FK)

  • buyer_account

  • amount (string)

  • currency

  • status

  • ledger_updated_at

  • wallet_updated_at

Payment Flow

  1. Money transfers from buyer to platform (Pay-in)

  2. When order satisfied, money transfers to seller (Pay-out)

  3. Status: pending → completed → failed → success

  4. Only mark checkout successful when all payments successful

  5. Add to ledger

Double Entry Bookkeeping

All transactions must balance: sum of debits and credits = 0.

Hosted Payment Page

Use third-party to handle credit card data compliance burden.

Payout Flow

Similar to pay-in but uses payout provider instead of PSP.

Deep Dive: PSP Integration

  1. Checkout page calls payment API

  2. PSP generates payment token

  3. Payment service stores token

  4. Initiates hosted payment page with token

  5. User completes payment on PSP

  6. PSP redirects to completion page

  7. PSP sends webhook with payment status

  8. Payment service updates database

Reconciliation

Handles webhook failures and extended outages.

Process:

  • PSP sends settlement file nightly

  • Compare with internal records

  • Flag discrepancies: auto-adjust, need human review, or investigate

Payment Delays

  • PSP may mark high-risk for manual verification

  • CRON job monitors pending transactions

  • Updates status from PSP

Idempotency

Prevent duplicate payments via idempotent keys (payment table PK).

Consistency Guarantees

  • Use idempotent keys

  • Always reconcile (never trust external systems)

  • ACID databases with sync replication

Design Google Drive

Step 1: Understanding the Problem

Features:

  • Upload/Download/Sync files

  • All file types supported

  • Mobile and Web

  • Encryption

  • 10 GB max file size

  • 10 million DAU

Clarifying Requirements:

  • Reliable file storage

  • Fast sync speed

  • Bandwidth optimization

  • Scalability

  • High availability

Back of the Envelope Calculation

text
50M users, 10M DAU
10 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
2 file uploads/day, 500 KB average
Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
1:1 read/write ratio

Step 2: High-Level Design

File Organization:

text
/uploads
  /user_id
    /file_id
      /file

Upload Types:

  • Simple: small files

  • Resumable: large files

Storage: AWS S3 (scalable, reliable, low-latency, cross-region replication)

Why Metadata DB?

  • File metadata (name, size, type, owner)

  • File revisions

  • Sharing information

  • Faster retrieval than object storage

  • Easier search queries

  • Frequent updates

Sync Conflicts

First user to finish wins; others' changes discarded. User notified and can merge/keep/discard.

Block Servers

  • Break files into chunks

  • Encrypt separately

  • Store in S3 with unique ID and sequence number

  • Track metadata in database

  • Only changed blocks re-uploaded (delta sync)

Server-side chunking and encryption safer than client-side.

Step 3: Design Deep Dive

LSM Tree Optimization

Efficient chunking and block management.

High Consistency Requirements

  • Metadata updated atomically (ACID)

  • File upload eventually consistent

  • Use relational database for metadata

Metadata Schema

  • User, Device, Workspace, File, FileVersion, Block tables

  • Hierarchical relationships

Upload/Download Flows

Upload notifies changes; download applies changes via pull or notification queue.

Long Polling

Detect file changes during collaborative editing with periodic polling.

Storage Optimization

  • De-duplicate blocks via hashing

  • Revision limits

  • Move old files to cold storage

Failure Recovery

Access files from different region if primary S3 fails.


Additional Key Concepts

Bloom Filters

Probabilistic data structure checking element set membership. Useful for:

  • Avoiding unnecessary lookups

  • Identifying which SSTable contains key

Distributed Systems Patterns

Consistent Hashing: Even load distribution, minimal re-mapping on node changes

Replication: Data across multiple nodes for high availability

Sharding: Horizontal data partitioning

Eventual Consistency: System converges to consistent state over time

Key Design Tradeoffs

  • Consistency vs. Availability: CAP theorem limits

  • Latency vs. Throughput: Cache vs. batch processing

  • Storage vs. Computation: Pre-compute vs. on-demand

  • Complexity vs. Features: Simple reliable design vs. feature-rich