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
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 | responsePros:
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)
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 | clientBest 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
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
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.
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:
Remove timestamps older than window
Check if count within limit
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
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
domain: messaging
descriptors:
- key: message_type
value: marketing
rate_limit:
unit: day
requests_per_unit: 5Rate 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.
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:
No. users = 1 million
Max requests per user = 1 RPS
Max timestamps stored = 60
Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
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 = 40Design 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
W (write acks needed) + R (read replicas needed) > NR = 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:
{
"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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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 --- coordinatorSimple 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
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):
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
sequenceDiagram
participant client
participant tinyUrlService
participant resourceService
client ->> tinyUrlService: shorten(url)
tinyUrlService -->> client: tinyUrl
client ->> tinyUrlService: tinyUrl
tinyUrlService -->> client: 302 redirect, location
client ->> resourceService: locationRedirect 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:
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
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
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
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| BDesign 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.
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:
Priority queue: manages URL importance
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
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
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:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ 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
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 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
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
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/dayVideo 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
1 million transactions/day
= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
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
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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 ratioStep 2: High-Level Design
File Organization:
/uploads
/user_id
/file_id
/fileUpload 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
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
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
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 | responsePros:
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)
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 | clientBest 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
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
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.
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:
Remove timestamps older than window
Check if count within limit
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
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
domain: messaging
descriptors:
- key: message_type
value: marketing
rate_limit:
unit: day
requests_per_unit: 5Rate 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.
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:
No. users = 1 million
Max requests per user = 1 RPS
Max timestamps stored = 60
Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
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 = 40Design 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
W (write acks needed) + R (read replicas needed) > NR = 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:
{
"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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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 --- coordinatorSimple 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
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):
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
sequenceDiagram
participant client
participant tinyUrlService
participant resourceService
client ->> tinyUrlService: shorten(url)
tinyUrlService -->> client: tinyUrl
client ->> tinyUrlService: tinyUrl
tinyUrlService -->> client: 302 redirect, location
client ->> resourceService: locationRedirect 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:
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
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
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
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| BDesign 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.
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:
Priority queue: manages URL importance
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
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
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:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ 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
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 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
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
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/dayVideo 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
1 million transactions/day
= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
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
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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 ratioStep 2: High-Level Design
File Organization:
/uploads
/user_id
/file_id
/fileUpload 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
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
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
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
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 | responsePros:
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)
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 | clientBest 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
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)
No title
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
No title
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 Strategies
Cache Aside
Rendering diagram...
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
Cache Aside
Rendering diagram...
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
Rendering diagram...
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-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)
Rendering diagram...
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
Rendering diagram...
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
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
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
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.
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
Power of Two
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
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
Latency Numbers Every Programmer Should Know
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
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
Availability Numbers
High availability is continuous operation measured as percentage. Cloud providers set SLAs at 99.9% or above.
99%
3.65 days
99.99%
52.60 minutes
99.999%
5.26 minutes
99.9999%
31.56 seconds
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)
No title
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
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)
No title
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
No title
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:
Remove timestamps older than window
Check if count within limit
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
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
domain: messaging
descriptors:
- key: message_type
value: marketing
rate_limit:
unit: day
requests_per_unit: 5Rate 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.
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:
No. users = 1 million
Max requests per user = 1 RPS
Max timestamps stored = 60
Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
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 = 40Understanding 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:
Remove timestamps older than window
Check if count within limit
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
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:
Remove timestamps older than window
Check if count within limit
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
Rendering diagram...
Client sends request to middleware
Rate limiter fetches counter from Redis
If limit reached, reject
Otherwise, forward and increment counter
Rendering diagram...
Rate Limiting Rules
1domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 51domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 5Rate 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.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"Sorted sets provide atomicity; no two operations overlap.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"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:
1No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 401No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MB1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 40Design 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.
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
W (write acks needed) + R (read replicas needed) > NR = 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:
{
"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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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 --- coordinatorSimple 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
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
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
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
1W (write acks needed) + R (read replicas needed) > NR = 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).
Quorum Consensus
1W (write acks needed) + R (read replicas needed) > NR = 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)
1W (write acks needed) + R (read replicas needed) > NConsistency 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:
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
Rendering diagram...
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
Rendering diagram...
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
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
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):
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 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¹⁵
UUID vs ULID
Cannot use due to size (128 bits vs required 64 bits):
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
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
Rendering diagram...
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:
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
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
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
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
No title
Rendering diagram...
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
No title
Rendering diagram...
Rendering diagram...
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:
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
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
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
Short URL Character Combinations
With 62 characters:
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.
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
Hashing vs Base62 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)
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
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
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
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
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
Rendering diagram...
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
Domain queue: manages politeness
Rendering diagram...
Freshness
Periodically recrawl to keep content fresh.
Strategies:
Prioritize frequently updated pages
Prioritize important pages
Update frequency: Check HTTP headers for last-modified date.
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)
Design a Notification System
Problem Understanding
10 million mobile push notifications
1 million SMS messages
5 million emails
High-Level Design
Rendering diagram...
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
Problem Understanding
10 million mobile push notifications
1 million SMS messages
5 million emails
High-Level Design
Rendering diagram...
Rendering diagram...
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.
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.
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
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
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:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ Receiver
Group Chat:
One queue per user in group
Online Indicator
Use short polling (heartbeat every 5s) to presence service. Mark offline after timeout.
Problem Understanding
1:1 and group chat
50 million DAU
Max group: 100 users
Online indicator
Text only
Max text: 1 million characters
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
Use ULID/Snowflake IDs for sortability.
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
Message Flow
One-on-One:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ Receiver
Group Chat:
One queue per user in group
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
1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
Return top K results
Sharding: Use first 3 characters for hash-based sharding.
Problem Understanding
Match query prefix only
Sort by historical frequency
No spell check
English, lowercase alphanumeric
10 million DAU
Back of the Envelope Calculation
1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GB1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
Return top K results
Sharding: Use first 3 characters for hash-based sharding.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
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
15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/dayVideo 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
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
15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/day15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/dayVideo Transcoding Pipeline
No title
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
No title
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
11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
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
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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
11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPS11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
Rendering diagram...
Rendering diagram...
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.
/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.
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
Add to ledger
Deep Dive: PSP Integration
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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
150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratioStep 2: High-Level Design
No title
File Organization:
/uploads
/user_id
/file_id
/fileUpload 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
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
150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratio150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratioStep 2: High-Level Design
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload 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.
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload Types:
Simple: small files
Resumable: large files
Storage: AWS S3 (scalable, reliable, low-latency, cross-region replication)
1/uploads
2 /user_id
3 /file_id
4 /fileWhy Metadata DB?
File metadata (name, size, type, owner)
File revisions
Sharing information
Faster retrieval than object storage
Easier search queries
Frequent updates
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
High Consistency Requirements
Metadata updated atomically (ACID)
File upload eventually consistent
Use relational database for metadata
Storage Optimization
De-duplicate blocks via hashing
Revision limits
Move old files to cold storage
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
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
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
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
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 | responsePros:
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)
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 | clientBest 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
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)
No title
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
No title
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 Strategies
Cache Aside
Rendering diagram...
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
Cache Aside
Rendering diagram...
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
Rendering diagram...
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-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)
Rendering diagram...
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
Rendering diagram...
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
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
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
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.
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
Power of Two
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
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
Latency Numbers Every Programmer Should Know
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
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
Availability Numbers
High availability is continuous operation measured as percentage. Cloud providers set SLAs at 99.9% or above.
99%
3.65 days
99.99%
52.60 minutes
99.999%
5.26 minutes
99.9999%
31.56 seconds
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)
No title
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
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)
No title
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
No title
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:
Remove timestamps older than window
Check if count within limit
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
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
domain: messaging
descriptors:
- key: message_type
value: marketing
rate_limit:
unit: day
requests_per_unit: 5Rate 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.
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:
No. users = 1 million
Max requests per user = 1 RPS
Max timestamps stored = 60
Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
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 = 40Understanding 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:
Remove timestamps older than window
Check if count within limit
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
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:
Remove timestamps older than window
Check if count within limit
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
Rendering diagram...
Client sends request to middleware
Rate limiter fetches counter from Redis
If limit reached, reject
Otherwise, forward and increment counter
Rendering diagram...
Rate Limiting Rules
1domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 51domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 5Rate 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.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"Sorted sets provide atomicity; no two operations overlap.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"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:
1No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 401No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MB1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 40Design 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.
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
W (write acks needed) + R (read replicas needed) > NR = 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:
{
"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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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 --- coordinatorSimple 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
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
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
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
1W (write acks needed) + R (read replicas needed) > NR = 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).
Quorum Consensus
1W (write acks needed) + R (read replicas needed) > NR = 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)
1W (write acks needed) + R (read replicas needed) > NConsistency 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:
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
Rendering diagram...
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
Rendering diagram...
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
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
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):
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 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¹⁵
UUID vs ULID
Cannot use due to size (128 bits vs required 64 bits):
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
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
Rendering diagram...
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:
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
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
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
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
No title
Rendering diagram...
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
No title
Rendering diagram...
Rendering diagram...
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:
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
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
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
Short URL Character Combinations
With 62 characters:
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.
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
Hashing vs Base62 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)
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
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
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
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
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
Rendering diagram...
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
Domain queue: manages politeness
Rendering diagram...
Freshness
Periodically recrawl to keep content fresh.
Strategies:
Prioritize frequently updated pages
Prioritize important pages
Update frequency: Check HTTP headers for last-modified date.
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)
Design a Notification System
Problem Understanding
10 million mobile push notifications
1 million SMS messages
5 million emails
High-Level Design
Rendering diagram...
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
Problem Understanding
10 million mobile push notifications
1 million SMS messages
5 million emails
High-Level Design
Rendering diagram...
Rendering diagram...
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.
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.
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
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
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:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ Receiver
Group Chat:
One queue per user in group
Online Indicator
Use short polling (heartbeat every 5s) to presence service. Mark offline after timeout.
Problem Understanding
1:1 and group chat
50 million DAU
Max group: 100 users
Online indicator
Text only
Max text: 1 million characters
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:
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
Group Message Table:
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
Use ULID/Snowflake IDs for sortability.
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
Message Flow
One-on-One:
Sender → Chat Server 1
→ Message Queue
→ Chat Server 2
→ Receiver
Group Chat:
One queue per user in group
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
1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
Return top K results
Sharding: Use first 3 characters for hash-based sharding.
Problem Understanding
Match query prefix only
Sort by historical frequency
No spell check
English, lowercase alphanumeric
10 million DAU
Back of the Envelope Calculation
1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GB1DAU = 10 million
2Avg queries/user/day = 10
3Query length = 20 bytes
4Queries/day = 10 × 10M × 20 = 2 billion
5Queries/sec = 2B ÷ 86,400 ≈ 23,148 QPS
6Peak QPS = 2 × 23,148 ≈ 46,296 QPS
7Daily writes = 20% × 2B = 400 million
8Daily data = 400M × 20 bytes ÷ 1024 ≈ 8 GBTrie Data Structure
No title
Prefix Trie: Efficient for prefix-based searches.
Optimization: Cache frequent queries at each node.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
Return top K results
Sharding: Use first 3 characters for hash-based sharding.
Constructing Prefix Trie
Process:
Collect queries in analytics log
Aggregate by week
Workers build trie from aggregated data
Update trie database/cache
Querying Trie
User types query
API checks trie cache
On miss, query trie database
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
15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/dayVideo 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
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
15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/day15M DAU × 30 min/day = 150M total viewing minutes/day
25 videos/user/day, 10% upload = 5M × 10% = 500K uploads/day
3Average video: 300 MB
4Storage/day = 500K × 300 MB = 150 TB
5CDN cost = 5M × 5 videos × 300 MB × $0.02/GB ≈ $150K/dayVideo Transcoding Pipeline
No title
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
No title
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
11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
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
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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
11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPS11 million transactions/day
2= 1M ÷ 86,400 ≈ 11.57 TPS ≈ 10 TPSHigh-Level Design
Rendering diagram...
Rendering diagram...
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.
/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.
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
Add to ledger
Deep Dive: PSP Integration
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
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
150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratioStep 2: High-Level Design
No title
File Organization:
/uploads
/user_id
/file_id
/fileUpload 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
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
150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratio150M users, 10M DAU
210 GB per user free space: 50M × 10GB = 500M GB = 5×10^8 GB
32 file uploads/day, 500 KB average
4Uploads/sec = 10M × 2 ÷ 86,400 ≈ 240 UPS
51:1 read/write ratioStep 2: High-Level Design
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload 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.
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload Types:
Simple: small files
Resumable: large files
Storage: AWS S3 (scalable, reliable, low-latency, cross-region replication)
1/uploads
2 /user_id
3 /file_id
4 /fileWhy Metadata DB?
File metadata (name, size, type, owner)
File revisions
Sharing information
Faster retrieval than object storage
Easier search queries
Frequent updates
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
High Consistency Requirements
Metadata updated atomically (ACID)
File upload eventually consistent
Use relational database for metadata
Storage Optimization
De-duplicate blocks via hashing
Revision limits
Move old files to cold storage
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
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
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)
No title
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
No title
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 Strategies
Cache Aside
Rendering diagram...
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
Cache Aside
Rendering diagram...
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
Rendering diagram...
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-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)
Rendering diagram...
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
Rendering diagram...
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
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
Power of Two
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
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
Latency Numbers Every Programmer Should Know
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
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
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
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
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:
Remove timestamps older than window
Check if count within limit
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
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:
Remove timestamps older than window
Check if count within limit
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
Rendering diagram...
Client sends request to middleware
Rate limiter fetches counter from Redis
If limit reached, reject
Otherwise, forward and increment counter
Rendering diagram...
Rate Limiting Rules
1domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 51domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 5Rate 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.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"Sorted sets provide atomicity; no two operations overlap.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"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:
1No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 401No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MB1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 40Understanding 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
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
1W (write acks needed) + R (read replicas needed) > NR = 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).
Quorum Consensus
1W (write acks needed) + R (read replicas needed) > NR = 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)
1W (write acks needed) + R (read replicas needed) > NConsistency 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:
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
Rendering diagram...
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
Rendering diagram...
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
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
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
High-Level Design
No title
Rendering diagram...
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
No title
Rendering diagram...
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:
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
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
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
Short URL Character Combinations
With 62 characters:
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.
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
Hashing vs Base62 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)
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
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
Hashing vs Base62 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)
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)
URL Shortening Process
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
Freshness
Periodically recrawl to keep content fresh.
Strategies:
Prioritize frequently updated pages
Prioritize important pages
Update frequency: Check HTTP headers for last-modified date.
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)
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
No title
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
Rendering diagram...
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.
/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.
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
Add to ledger
Deep Dive: PSP Integration
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
Consistency Guarantees
Use idempotent keys
Always reconcile (never trust external systems)
ACID databases with sync replication
Step 2: High-Level Design
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload 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.
1/uploads
2 /user_id
3 /file_id
4 /fileBlock 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
High Consistency Requirements
Metadata updated atomically (ACID)
File upload eventually consistent
Use relational database for metadata
Storage Optimization
De-duplicate blocks via hashing
Revision limits
Move old files to cold storage
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)
No title
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
No title
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 Strategies
Cache Aside
Rendering diagram...
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
Cache Aside
Rendering diagram...
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
Rendering diagram...
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-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)
Rendering diagram...
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
Rendering diagram...
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
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
Power of Two
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
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
Latency Numbers Every Programmer Should Know
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
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
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
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
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:
Remove timestamps older than window
Check if count within limit
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
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:
Remove timestamps older than window
Check if count within limit
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
Rendering diagram...
Client sends request to middleware
Rate limiter fetches counter from Redis
If limit reached, reject
Otherwise, forward and increment counter
Rendering diagram...
Rate Limiting Rules
1domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 51domain: messaging
2descriptors:
3 - key: message_type
4 value: marketing
5 rate_limit:
6 unit: day
7 requests_per_unit: 5Rate 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.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"Sorted sets provide atomicity; no two operations overlap.
1function rateLimiter(user_id, current_timestamp, limit, interval):
2 redis_key = "rate_limit:" + user_id
3
4 # Remove outdated requests
5 Redis.ZREMRANGEBYSCORE(redis_key, 0, current_timestamp - interval)
6
7 # Add current request
8 Redis.ZADD(redis_key, current_timestamp, current_timestamp)
9
10 # Fetch all requests in window
11 request_count = Redis.ZRANGE(redis_key, 0, -1)
12
13 # Check limit
14 if request_count > limit:
15 return 429, "Too Many Requests"
16
17 return 200, "Request Accepted"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:
1No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MBCPU requirements:
1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 401No. users = 1 million
2Max requests per user = 1 RPS
3Max timestamps stored = 60
4Total memory = 1M × 60 × 8 bytes = 480 MB1Operations/second = 1M users × 1 RPS = 1M ops/sec
2Ops needed = 4 operations per request (log N) = 4M ops/sec
3Redis: 100K ops/sec per core
4Cores needed = 40Understanding 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
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
1W (write acks needed) + R (read replicas needed) > NR = 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).
Quorum Consensus
1W (write acks needed) + R (read replicas needed) > NR = 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)
1W (write acks needed) + R (read replicas needed) > NConsistency 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:
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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
1{
2 "A": [
3 ["node_a", 1],
4 ["node_b", 2]
5 ]
6}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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
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:
Node detects change
Each interval, select random node and share information
Receiving node merges info and may share back
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
Rendering diagram...
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
Rendering diagram...
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
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
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
High-Level Design
No title
Rendering diagram...
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
No title
Rendering diagram...
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:
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
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
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
Short URL Character Combinations
With 62 characters:
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.
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
Hashing vs Base62 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)
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
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
Hashing vs Base62 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)
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)
URL Shortening Process
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
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.
Rendering diagram...
Two-queue system:
Priority queue: manages URL importance
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.
Freshness
Periodically recrawl to keep content fresh.
Strategies:
Prioritize frequently updated pages
Prioritize important pages
Update frequency: Check HTTP headers for last-modified date.
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)
message_id (PK)
UUID
sender_id
UUID
receiver_id
UUID
content
TEXT
created_at
TIMESTAMP
channel_id (PK)
UUID
message_id (CK)
UUID
sender_id
UUID
content
TEXT
created_at
TIMESTAMP
No title
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
Rendering diagram...
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.
/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.
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
Money transfers from buyer to platform (Pay-in)
When order satisfied, money transfers to seller (Pay-out)
Status: pending → completed → failed → success
Only mark checkout successful when all payments successful
Add to ledger
Deep Dive: PSP Integration
Checkout page calls payment API
PSP generates payment token
Payment service stores token
Initiates hosted payment page with token
User completes payment on PSP
PSP redirects to completion page
PSP sends webhook with payment status
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
Consistency Guarantees
Use idempotent keys
Always reconcile (never trust external systems)
ACID databases with sync replication
Step 2: High-Level Design
No title
File Organization:
1/uploads
2 /user_id
3 /file_id
4 /fileUpload 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.
1/uploads
2 /user_id
3 /file_id
4 /fileBlock 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
High Consistency Requirements
Metadata updated atomically (ACID)
File upload eventually consistent
Use relational database for metadata
Storage Optimization
De-duplicate blocks via hashing
Revision limits
Move old files to cold storage
Hashing vs Base62 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)
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)
URL Shortening Process
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...
Hashing vs Base62 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)
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)
URL Shortening Process
Rendering diagram...
Use distributed ID generator
Base 64 encode ID to short URL
Store in database
Rendering diagram...