grokking-system-design-interview

name	grokking-system-design-interview
description	Pattern-based system design interview preparation framework with reusable building blocks, question walkthroughs, and company-specific interview guides
triggers	["help me prepare for a system design interview","show me system design patterns","design a scalable system","explain distributed system concepts","practice system design questions","what are common system design building blocks","how to approach system design interviews","show me cache and load balancing patterns"]

Grokking System Design Interview Skill

Skill by 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:

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)

# 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 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):

// Users table
{
  "PK": "USER#12345",
  "SK": "METADATA",
  "username": "johndoe",
  "email": "[e-mail]",
  "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"
   

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

# 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()
        })
    
     ():
        
        feed_key = 
        
        
         cursor:
            photo_ids = .cache.zrevrangebyscore(
                feed_key,
                =cursor,
                =,
                start=,
                num=limit
            )
        :
            photo_ids = .cache.zrevrange(
                feed_key,
                start=,
                end=limit-
            )
        
          photo_ids:
            
             ._generate_feed_from_db(user_id, limit)
        
        
        photos = ._batch_get_photos(photo_ids)
        
         {
            : photos,
            : photos[-][]  photos  
        }
    
     ():
        
        photos = .db.query(, (user_id, limit))
        
        
        feed_key = 
         photo  photos:
            .cache.zadd(
                feed_key,
                {photo[]: photo[].timestamp()}
            )
        
         {: photos, : photos[-][]  photos  }

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

# 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)
         cached   :
             cached
        
        
        value = compute_fn()
        .(key, value, ttl)
         value


cache = CacheService(redis_url=)

 ():
     cache.get_or_compute(
        key=,
        compute_fn=: db.fetch_user(user_id),
        ttl=  
    )

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 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

# 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)"""
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_node(self, node: str):
        """Add a node with virtual replicas"""
        for i in range(self.virtual_nodes):
            virtual_key = f":"
            hash_val = ._(virtual_key)
            .ring[hash_val] = node
            .sorted_keys.append(hash_val)
        
        .sorted_keys.sort()
    
     ():
        
         i  (.virtual_nodes):
            virtual_key = 
            hash_val = ._(virtual_key)
             .ring[hash_val]
            .sorted_keys.remove(hash_val)
    
     () -> :
        
          .ring:
             
        
        hash_val = ._(key)
        
        
        idx = bisect_right(.sorted_keys, hash_val)
         idx == (.sorted_keys):
            idx = 
        
         .ring[.sorted_keys[idx]]


nodes = [, , ]
ch = ConsistentHash(nodes)


user_id = 
shard = ch.get_node(user_id)
()


ch.add_node()

4. Rate Limiting

# Token bucket rate limiter

import time
from threading import Lock

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        """
        capacity: Maximum tokens in bucket
        refill_rate: Tokens added per second
        """
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = time.time()
        self.lock = Lock()
    
    def _refill(self):
        """Add tokens based on time elapsed"""
        now = time.time()
        elapsed = now - self.last_refill
        tokens_to_add = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill = now
    
    def consume(self, tokens: int = 1) -> bool:
        """
        Try to consume tokens. Returns True if allowed, False if rate limited.
        """
        with self.lock:
            self._refill()
            
            if self.tokens >= tokens:
                self.tokens -= tokens
                 
             


 :
     ():
        .redis = redis_client
        .key_prefix = key_prefix
    
     () -> :
        
        key = 
        now = time.time()
        window_start = now - window
        
        pipe = .redis.pipeline()
        
        
        pipe.zremrangebyscore(key, , window_start)
        
        
        pipe.zcard(key)
        
        
        pipe.zadd(key, {now: now})
        
        
        pipe.expire(key, window)
        
        results = pipe.execute()
        request_count = results[]
        
         request_count < limit


limiter = TokenBucket(capacity=, refill_rate=)  

 limiter.consume():
    
    handle_request()
:
    
     {: }, 

5. Message Queue Pattern

# Kafka producer/consumer pattern

from kafka import KafkaProducer, KafkaConsumer
import json

class EventPublisher:
    def __init__(self, bootstrap_servers: list):
        self.producer = KafkaProducer(
            bootstrap_servers=bootstrap_servers,
            value_serializer=lambda v: json.dumps(v).encode('utf-8'),
            acks='all',  # Wait for all replicas
            retries=3,
            max_in_flight_requests_per_connection=1  # Preserve order
        )
    
    def publish(self, topic: str, event: dict, key: str = None):
        """Publish event to Kafka topic"""
        future = self.producer.send(
            topic,
            key=key.encode('utf-8') if key else None,
            value=event
        )
        # Optionally wait for confirmation
        # result = future.get(timeout=10)
        return future
    
    def close(self):
        self.producer.flush()
        self.producer.close()

class EventConsumer:
    def __init__(self, bootstrap_servers: , group_id: , topics: ):
        .consumer = KafkaConsumer(
            *topics,
            bootstrap_servers=bootstrap_servers,
            group_id=group_id,
            value_deserializer= m: json.loads(m.decode()),
            auto_offset_reset=,  
            enable_auto_commit=  
        )
    
     ():
        
        :
             message  .consumer:
                :
                    handler(message.value)
                    
                    .consumer.commit()
                 Exception  e:
                    ()
                    
        :
            .consumer.close()


publisher = EventPublisher([, ])
publisher.publish(
    topic=,
    event={
        : ,
        : ,
        : time.time()
    },
    key=  
)


 ():
    user_id = event[]
    
    send_email(event[], )
    
    analytics.track(, user_id)

consumer = EventConsumer(
    bootstrap_servers=[, ],
    group_id=,
    topics=[]
)
consumer.consume(handle_signup)

Common Question Patterns

URL Shortener (Basic)

Approach:

1. Generate unique short code (base62 encoding of auto-increment ID or hash)
2. Store mapping in key-value store (Redis + persistent DB)
3. Handle collisions with retry or pre-generated pool
4. Implement redirect (302 temporary or 301 permanent)

import hashlib
import base64

class URLShortener:
    BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    def __init__(self, db, cache):
        self.db = db
        self.cache = cache
    
    def shorten(self, long_url: str, custom_alias: str = None) -> str:
        """Create short URL"""
        # Check if URL already shortened
        existing = self.db.query(
            "SELECT short_code FROM urls WHERE long_url = %s",
            (long_url,)
        )
        if existing:
            return existing['short_code']
        
        if custom_alias:
            short_code = custom_alias
            # Check availability
            if self.db.query("SELECT 1 FROM urls WHERE short_code = %s", (short_code,)):
                raise ValueError("Alias already taken")
        else:
            # Generate short code from auto-increment ID
            url_id = self.db.insert("INSERT INTO urls (long_url) VALUES (%s)", (long_url,))
            short_code = self._encode_base62(url_id)
        
        # Store mapping
        self.db.execute(
            "UPDATE urls SET short_code = %s WHERE id = %s",
            (short_code, url_id)
        )
        
        
        .cache.(, long_url, ttl=)
        
         short_code
    
     () -> :
        
        
        cached = .cache.get()
         cached:
             cached
        
        
        result = .db.query(
            ,
            (short_code,)
        )
        
          result:
             ValueError()
        
        long_url = result[]
        
        
        .cache.(, long_url, ttl=)
        
        
        ._track_click(short_code)
        
         long_url
    
     () -> :
        
         num == :
             .BASE62[]
        
        encoded = []
         num > :
            encoded.append(.BASE62[num % ])
            num //= 
        
         .join((encoded))
    
     ():
        
        
        .queue.publish(, {
            : short_code,
            : time.time()
        })

News Feed / Timeline (Advanced)

See detailed example in "Deep Dive" section above.

Key decisions:

• Fan-out on write vs read vs hybrid
• How to handle celebrity users (millions of followers)
• Cache strategy (Redis sorted sets)
• Pagination (cursor-based vs offset)

Real-time Chat (Advanced)

Architecture:

• WebSocket connections for real-time delivery
• Message queue for reliability (Kafka)
• Presence service (Redis pub/sub)
• Message history (Cassandra or MongoDB)

# WebSocket chat server with Socket.IO

from socketio import AsyncServer, ASGIApp
from aiohttp import web
import asyncio

sio = AsyncServer(async_mode='aiohttp', cors_allowed_origins='*')
app = web.Application()
sio.attach(app)

# In-memory store (use Redis in production)
connections = {}  # user_id -> set of socket IDs
rooms = {}        # room_id -> set of user_ids

@sio.event
async def connect(sid, environ):
    """Client connected"""
    print(f"Client {sid} connected")

@sio.event
async def authenticate(sid, data):
    """Authenticate user and join their rooms"""
    user_id = data['user_id']
    token = data['token']
    
    # Verify token (omitted)
    if not verify_token(token):
        await sio.disconnect(sid)
        return
    
    # Track connection
    if user_id not in connections:
        connections[user_id] = set()
    connections[user_id].add(sid)
    
    # Join user's chat rooms
    user_rooms = db.get_user_rooms(user_id)
    for room_id in user_rooms:
        await sio.enter_room(sid, room_id)
        if room_id not  rooms:
            rooms[room_id] = ()
        rooms[room_id].add(user_id)
    
    
     sio.emit(, {: user_id}, skip_sid=sid)


  ():
    
    room_id = data[]
    user_id = data[]
    content = data[]
    
    
    message_id =  db.save_message({
        : room_id,
        : user_id,
        : content,
        : time.time()
    })
    
    
     queue.publish(, {