grokking-system-design-interview

# Grokking System Design Interview Skill > Skill by [ara.so](https://ara.so) — Design Skills collection. This skill provides expertise in using the Grokking System Design repository, a pattern-based approach to system design interviews. Learn reusable building blocks (caching, sharding, replication, consistency models) and apply them to any design question. ## What This Project Does Grokking System Design is a free, open companion to the original course that teaches: - **Pattern-based methodology**: Learn 24 reusable building blocks instead of memorizing answers - **Interview framework**: A repeatable 7-step structure for any question - **40+ question walkthroughs**: From TinyURL to ChatGPT, organized by difficulty - **Company-specific guides**: How 58 companies run their system design rounds - **Distributed systems deep dives**: Case studies of Dynamo, Cassandra, Kafka, etc. ## Installation This is a knowledge repository, not code you install. Clone it for offline reference: ```bash git clone https://github.com/design-gurus/grokking-system-design.git cd grokking-system-design ``` Or browse online at: https://github.com/design-gurus/grokking-system-design ## Repository Structure ``` grokking-system-design/ ├── patterns/ # 24 reusable building blocks ├── questions/ # 40+ system design walkthroughs ├── companies/ # 58 company-specific interview guides ├── cheat-sheets/ # Quick reference sheets ├── roadmaps/ # 1-week, 2-week, 6-week study plans ├── deep-dives/ # Distributed systems case studies └── glossary.md # System design vocabulary ``` ## The 7-Step Interview Framework Every system design question should follow this structure: ### 1. Clarify Requirements (3-5 minutes) **Functional requirements** (what the system does): ``` Example for "Design Instagram": - Users can upload photos - Users can follow other users - Users see a feed of photos from people they follow - Users can like and comment on photos ``` **Non-functional requirements** (how the system performs): ``` - Scale: 500M users, 100M daily active users - Availability: 99.99% uptime - Latency: Feed loads in < 200ms - Consistency: Eventual consistency is acceptable ``` ### 2. Estimate Scale (5 minutes) ``` Traffic estimate: - 100M DAU - Each user views 50 photos/day = 5B photo views/day - 5B / 86400 seconds ≈ 58K requests/second - Peak traffic (3x average) = 174K RPS Storage estimate: - 2M new photos/day - Average photo size: 2MB - Daily storage: 2M × 2MB = 4TB/day - 5-year storage: 4TB × 365 × 5 ≈ 7.3PB Bandwidth estimate: - Incoming: 4TB/day = 46MB/s - Outgoing (views): 5B × 2MB / 86400 = 115GB/s ``` ### 3. Define the API (5 minutes) ```python # REST API example for Instagram # Upload photo POST /api/v1/photos Content-Type: multipart/form-data Body: { photo: file, caption: string, location: string } Response: { photo_id: string, url: string } # Get user feed GET /api/v1/feed?user_id={id}&cursor={cursor}&limit=20 Response: { photos: [...], next_cursor: string } # Follow user POST /api/v1/users/{user_id}/follow Body: { follower_id: string } Response: { success: boolean } # Like photo POST /api/v1/photos/{photo_id}/like Body: { user_id: string } Response: { success: boolean, like_count: number } ``` ### 4. Design the Data Model (5 minutes) ```sql -- SQL schema example for Instagram CREATE TABLE users ( user_id BIGINT PRIMARY KEY, username VARCHAR(50) UNIQUE NOT NULL, email VARCHAR(255) UNIQUE NOT NULL, created_at TIMESTAMP DEFAULT NOW(), INDEX idx_username (username) ); CREATE TABLE photos ( photo_id BIGINT PRIMARY KEY, user_id BIGINT NOT NULL, photo_url VARCHAR(500) NOT NULL, caption TEXT, location VARCHAR(255), created_at TIMESTAMP DEFAULT NOW(), FOREIGN KEY (user_id) REFERENCES users(user_id), INDEX idx_user_created (user_id, created_at) ); CREATE TABLE follows ( follower_id BIGINT NOT NULL, followee_id BIGINT NOT NULL, created_at TIMESTAMP DEFAULT NOW(), PRIMARY KEY (follower_id, followee_id), INDEX idx_follower (follower_id), INDEX idx_followee (followee_id) ); CREATE TABLE likes ( photo_id BIGINT NOT NULL, user_id BIGINT NOT NULL, created_at TIMESTAMP DEFAULT NOW(), PRIMARY KEY (photo_id, user_id), INDEX idx_photo (photo_id) ); ``` For NoSQL (DynamoDB): ```json // Users table { "PK": "USER#12345", "SK": "METADATA", "username": "johndoe", "email": "john@example.com", "created_at": "2024-01-01T00:00:00Z" } // Photos table { "PK": "USER#12345", "SK": "PHOTO#67890", "photo_id": "67890", "photo_url": "https://cdn.example.com/photos/67890.jpg", "caption": "Beautiful sunset", "created_at": "2024-01-15T18:30:00Z" } // Follows table (adjacency list) { "PK": "USER#12345", "SK": "FOLLOWS#USER#99999", "created_at": "2024-01-10T12:00:00Z" } ``` ### 5. High-Level Architecture (10 minutes) ``` ┌─────────────┐ │ Clients │ (Web, iOS, Android) └──────┬──────┘ │ ▼ ┌─────────────┐ │ CDN │ (CloudFront, Cloudflare) └──────┬──────┘ │ ▼ ┌─────────────┐ │Load Balancer│ (ELB, HAProxy, NGINX) └──────┬──────┘ │ ▼ ┌──────────────────────────────┐ │ API Gateway / BFF │ └──────┬───────────────────────┘ │ ├─────────┬─────────┬─────────┐ ▼ ▼ ▼ ▼ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ User │ │ Photo │ │ Feed │ │ Social │ │Service │ │Service │ │Service │ │Service │ └───┬────┘ └───┬────┘ └───┬────┘ └───┬────┘ │ │ │ │ ├──────────┼──────────┼──────────┤ ▼ ▼ ▼ ▼ ┌───────────────────────────────────────┐ │ Message Queue (Kafka) │ └───────────────────────────────────────┘ │ │ │ │ ├──────────┼──────────┼──────────┤ ▼ ▼ ▼ ▼ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ Cache │ │ SQL DB │ │ NoSQL │ │ Object │ │(Redis) │ │(Postgres)│ │(Cassandra)││Storage│ └────────┘ └────────┘ └────────┘ │ (S3) │ └────────┘ ``` ### 6. Deep Dive (15 minutes) Pick 1-2 components and go deep. Example: **Feed generation** ```python # Feed generation service - approach 1: Fan-out on write class FeedService: def __init__(self, cache, db, queue): self.cache = cache # Redis self.db = db # PostgreSQL self.queue = queue # Kafka def publish_photo(self, user_id, photo_id): """ When user posts a photo, push to all followers' feeds (Fan-out on write) """ # Get all followers followers = self.db.query( "SELECT follower_id FROM follows WHERE followee_id = %s", (user_id,) ) # Push to each follower's feed cache for follower in followers: feed_key = f"feed:{follower['follower_id']}" self.cache.zadd( feed_key, {photo_id: time.time()}, # Score = timestamp nx=True # Only if not exists ) # Keep only latest 1000 items self.cache.zremrangebyrank(feed_key, 0, -1001) # Publish event for async processing self.queue.publish('photo.published', { 'user_id': user_id, 'photo_id': photo_id, 'timestamp': time.time() }) def get_feed(self, user_id, cursor=None, limit=20): """ Retrieve user's feed from cache """ feed_key = f"feed:{user_id}" # Get from Redis sorted set (sorted by timestamp) if cursor: photo_ids = self.cache.zrevrangebyscore( feed_key, max=cursor, min='-inf', start=0, num=limit ) else: photo_ids = self.cache.zrevrange( feed_key, start=0, end=limit-1 ) if not photo_ids: # Cache miss - generate from DB (fan-out on read) return self._generate_feed_from_db(user_id, limit) # Batch fetch photo metadata photos = self._batch_get_photos(photo_ids) return { 'photos': photos, 'next_cursor': photos[-1]['timestamp'] if photos else None } def _generate_feed_from_db(self, user_id, limit): """ Fallback: Generate feed from database (Fan-out on read for cache misses) """ photos = self.db.query(""" SELECT p.photo_id, p.user_id, p.photo_url, p.caption, p.created_at FROM photos p JOIN follows f ON p.user_id = f.followee_id WHERE f.follower_id = %s ORDER BY p.created_at DESC LIMIT %s """, (user_id, limit)) # Warm up cache feed_key = f"feed:{user_id}" for photo in photos: self.cache.zadd( feed_key, {photo['photo_id']: photo['created_at'].timestamp()} ) return {'photos': photos, 'next_cursor': photos[-1]['created_at'] if photos else None} ``` **Trade-offs:** | Approach | Pros | Cons | Use When | |----------|------|------|----------| | Fan-out on write | Fast reads, pre-computed | Slow writes, storage overhead | Most users have few followers | | Fan-out on read | Fast writes, less storage | Slow reads, more DB load | Users have many followers (celebrities) | | Hybrid | Best of both | Complex implementation | Production systems | ### 7. Bottlenecks & Trade-offs (5 minutes) ``` Bottleneck: Database writes (photo uploads) Solutions: 1. Shard database by user_id (consistent hashing) 2. Use write-ahead log (WAL) for durability 3. Batch writes with message queue 4. Use object storage (S3) for photos, DB only for metadata Bottleneck: Feed generation for celebrity users (millions of followers) Solutions: 1. Hybrid approach: fan-out on read for users with > 100K followers 2. Limit fan-out, deliver celebrity posts on demand 3. Use real-time stream processing (Kafka + Flink) Bottleneck: Hot partition (single shard receives too much traffic) Solutions: 1. Re-shard using different hash function 2. Add secondary indexes 3. Cache popular content (80/20 rule) Trade-off: Consistency vs Availability (CAP theorem) - Strong consistency: Users always see latest data, but system may be unavailable during network partition - Eventual consistency: System is always available, but users may see stale data temporarily - Choice: Eventual consistency for social features (likes, follows), strong consistency for payments ``` ## Core Patterns Reference ### 1. Caching ```python # Redis caching pattern with TTL and cache-aside strategy import redis import json from typing import Optional class CacheService: def __init__(self, redis_url: str): self.redis = redis.from_url(redis_url) def get(self, key: str) -> Optional[dict]: """Get from cache, return None if miss""" value = self.redis.get(key) return json.loads(value) if value else None def set(self, key: str, value: dict, ttl: int = 3600): """Set with TTL (default 1 hour)""" self.redis.setex(key, ttl, json.dumps(value)) def delete(self, key: str): """Invalidate cache entry""" self.redis.delete(key) def get_or_compute(self, key: str, compute_fn, ttl: int = 3600): """Cache-aside pattern: get from cache or compute and store""" cached = self.get(key) if cached is not None: return cached # Cache miss - compute and store value = compute_fn() self.set(key, value, ttl) return value # Usage cache = CacheService(redis_url="redis://localhost:6379/0") def get_user_profile(user_id: str): return cache.get_or_compute( key=f"user:{user_id}", compute_fn=lambda: db.fetch_user(user_id), ttl=1800 # 30 minutes ) ``` **Cache eviction policies:** - LRU (Least Recently Used) - default, good for general use - LFU (Least Frequently Used) - good for access patterns with hot keys - TTL (Time To Live) - expire after fixed time ### 2. Load Balancing ```nginx # NGINX load balancer configuration upstream api_servers { # Load balancing method least_conn; # Route to server with fewest connections # Alternative: ip_hash (sticky sessions), round_robin (default) server api1.example.com:8080 weight=3 max_fails=3 fail_timeout=30s; server api2.example.com:8080 weight=2 max_fails=3 fail_timeout=30s; server api3.example.com:8080 weight=1 backup; # Backup server # Health checks check interval=3000 rise=2 fall=3 timeout=1000; } server { listen 80; server_name api.example.com; location / { proxy_pass http://api_servers; proxy_set_header Host $host; proxy_set_header X-Real-IP $remote_addr; proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; # Timeouts proxy_connect_timeout 5s; proxy_send_timeout 10s; proxy_read_timeout 10s; # Retries proxy_next_upstream error timeout http_500 http_502 http_503; } } ``` ### 3. Sharding / Partitioning ```python # Consistent hashing for data partitioning import hashlib from bisect import bisect_right from typing import List, Dict class ConsistentHash: def __init__(self, nodes: List[str], virtual_nodes: int = 150): """ nodes: List of server addresses virtual_nodes: Number of virtual nodes per physical node """ self.virtual_nodes = virtual_nodes self.ring: Dict[int, str] = {} self.sorted_keys: List[int] = [] for node in nodes: self.add_node(node) def _hash(self, key: str) -> int: """Hash function (MD5)"""