1. Introduction to System Design

System design is the process of defining the architecture, components, modules, interfaces, and data for a system to satisfy specified requirements. In the context of software engineering, it involves making high-level decisions about how to build scalable, reliable, and maintainable systems.

Why System Design Matters

The Journey Ahead

This guide takes you through a comprehensive exploration of system design, from fundamental concepts to complex real-world implementations. Each section builds upon previous knowledge, creating a complete understanding of how modern distributed systems work.

Learning Approach

Throughout this guide, we’ll use:

• Visual diagrams (in Mermaid format) to illustrate architectures
• Real-world examples from companies like Netflix, Uber, and Twitter
• Code examples in Python to demonstrate concepts
• Trade-off analyses to understand decision-making
• Practical exercises to reinforce learning

2. System Design Fundamentals

2.1 Scalability

Scalability is the ability of a system to handle increased load by adding resources. There are two primary approaches:

Vertical Scaling (Scale Up)

Adding more power to existing machines (CPU, RAM, disk).

Advantages:

• Simple implementation
• No code changes required
• Maintains data consistency easily

Disadvantages:

• Hardware limits (you can’t add infinite resources)
• Single point of failure
• Expensive at high end
• Requires downtime for upgrades

Horizontal Scaling (Scale Out)

Adding more machines to distribute the load.

Advantages:

• No theoretical limit to scaling
• Better fault tolerance
• More cost-effective
• Can use commodity hardware

Disadvantages:

• Application complexity increases
• Data consistency challenges
• Network overhead
• Requires load balancing

2.2 Performance vs Scalability

These concepts are often confused but are distinctly different:

• Performance Problem: System is slow for a single user

  • Solution: Optimize algorithms, add indexes, use caching

• Scalability Problem: System performs well for one user but degrades under load

  • Solution: Add servers, implement load balancing, distribute data

2.3 Latency vs Throughput

Latency: Time to perform a single operation

• Measured in milliseconds (ms)
• Example: Database query takes 50ms

Throughput: Number of operations per time unit

• Measured in requests per second (RPS) or queries per second (QPS)
• Example: System handles 10,000 requests/second

Important Insight: Low latency doesn’t always mean high throughput!

2.4 Key Latency Numbers Every Engineer Should Know

2.5 Availability

Availability is the percentage of time a system is operational and accessible.

Availability Calculation:

Availability = (Total Time - Downtime) / Total Time × 100%

Standard Availability Tiers (The Nines):

Achieving High Availability:

1. Eliminate Single Points of Failure (SPOF)

   • Redundant components
   • Failover mechanisms
   • Multi-region deployment

2. Implement Health Checks

   • Monitor service health
   • Automatic failure detection
   • Quick recovery mechanisms

3. Use Load Balancers

   • Distribute traffic
   • Route around failures
   • Prevent server overload

3. Back-of-the-Envelope Estimation

Being able to quickly estimate system requirements is crucial for system design. This section covers the estimation techniques used in interviews and real-world planning.

3.1 Power of Two

Understand data volume units:

3.2 Common Performance Numbers

• QPS (Queries Per Second) for web server: 1000 - 5000
• Database connections pool size: 50 - 100 per instance
• Average web page size: 1-2 MB
• Video streaming bitrate: 1-5 Mbps for 1080p
• Mobile app API call: 5-10 calls per user session

3.3 Example Estimation: Twitter-Like System

Calculations:

DAU = 300M × 50% = 150M

Tweets per day = 150M × 2 = 300M
Tweets per second (average) = 300M / 86400 ≈ 3,500 tweets/second
Peak QPS = 3,500 × 2 = 7,000 tweets/second (assuming 2x peak factor)

Average tweet size:
- Tweet text: 280 chars × 2 bytes = 560 bytes
- Metadata (ID, timestamp, user_id, etc.): 200 bytes
- Total per tweet: ~800 bytes ≈ 1 KB

Media tweets (10%):
- Image average: 500 KB
- Total per media tweet: 500 KB + 1 KB ≈ 500 KB

Daily storage:
- Text tweets: 270M × 1 KB = 270 GB
- Media tweets: 30M × 500 KB = 15 TB
- Total per day = 15.27 TB

5-year storage:
15.27 TB/day × 365 days × 5 years ≈ 27.9 PB

Ingress (upload):
15.27 TB/day ÷ 86,400 seconds ≈ 177 MB/second

Egress (assume each tweet viewed 10 times):
177 MB/s × 10 = 1.77 GB/second

20% of tweets generate 80% of traffic
Daily cache: 15.27 TB × 0.2 = 3 TB

4. The System Design Interview Framework

A systematic approach to solving any system design problem.

4.1 The 4-Step Framework

4.2 Key Principles

Start Simple, Then Iterate

• Begin with a basic design
• Add complexity incrementally
• Justify each addition

Focus on What Matters

• Prioritize based on requirements
• Don’t over-engineer
• Keep the user experience in mind

Think About Trade-offs

• No perfect solution exists
• Discuss pros and cons
• Choose based on requirements

Use Real Numbers

• Apply back-of-the-envelope calculations
• Validate your assumptions
• Show quantitative reasoning

5. Networking and Communication

5.1 The OSI Model and TCP/IP

5.2 HTTP and HTTPS

HTTP (Hypertext Transfer Protocol) is the foundation of data communication on the web.

Common HTTP Methods:

HTTP Status Codes:

1xx: Informational
  100 Continue
  101 Switching Protocols

2xx: Success
  200 OK
  201 Created
  202 Accepted
  204 No Content

3xx: Redirection
  301 Moved Permanently
  302 Found (Temporary Redirect)
  304 Not Modified
  307 Temporary Redirect
  308 Permanent Redirect

4xx: Client Errors
  400 Bad Request
  401 Unauthorized
  403 Forbidden
  404 Not Found
  409 Conflict
  429 Too Many Requests

5xx: Server Errors
  500 Internal Server Error
  502 Bad Gateway
  503 Service Unavailable
  504 Gateway Timeout

HTTPS = HTTP + SSL/TLS

HTTPS adds encryption and authentication through SSL/TLS:

5.3 REST vs GraphQL vs gRPC vs WebSockets

REST (Representational State Transfer)

Characteristics:

• Resource-based (nouns in URLs)
• Stateless
• Uses standard HTTP methods
• Returns JSON or XML

Example:

GET /api/users/123
GET /api/users/123/posts
POST /api/users/123/posts
PUT /api/users/123
DELETE /api/users/123

Pros:

• Simple and widely understood
• Cacheable
• Good tooling support

Cons:

• Over-fetching or under-fetching data
• Multiple round trips for related data
• Versioning can be challenging

GraphQL

Characteristics:

• Client specifies exactly what data it needs
• Single endpoint
• Strongly typed schema
• Real-time updates via subscriptions

Example:

query {
  user(id: "123") {
    name
    email
    posts(limit: 10) {
      title
      createdAt
    }
  }
}

Pros:

• No over-fetching/under-fetching
• Single request for complex data
• Self-documenting API

Cons:

• More complex backend
• Caching is harder
• Potential for expensive queries

gRPC (Google Remote Procedure Call)

Characteristics:

• Uses Protocol Buffers (binary format)
• HTTP/2 based
• Strongly typed
• Bi-directional streaming

Example (protobuf):

service UserService {
  rpc GetUser (UserRequest) returns (UserResponse);
  rpc ListUsers (ListUsersRequest) returns (stream UserResponse);
}

message UserRequest {
  string user_id = 1;
}

message UserResponse {
  string user_id = 1;
  string name = 2;
  string email = 3;
}

Pros:

• Very fast (binary protocol)
• Streaming support
• Strong typing

Cons:

• Not browser-friendly
• Less human-readable
• Steeper learning curve

WebSockets

Characteristics:

• Full-duplex communication
• Persistent connection
• Real-time bidirectional data flow

Use cases:

• Chat applications
• Live feeds
• Real-time gaming
• Collaborative editing

5.4 API Authentication

1. Basic Authentication

Authorization: Basic base64(username:password)

• Simple but insecure (credentials in every request)
• Use only over HTTPS

2. API Keys

X-API-Key: your-api-key-here

• Simple to implement
• Good for server-to-server
• Hard to revoke individual keys

3. OAuth 2.0

Most common flows:

Authorization Code Flow (for web apps):

4. JWT (JSON Web Tokens)

Structure: header.payload.signature

// Header
{
  "alg": "HS256",
  "typ": "JWT"
}

// Payload
{
  "sub": "user123",
  "name": "John Doe",
  "iat": 1516239022,
  "exp": 1516242622
}

// Signature
HMACSHA256(
  base64UrlEncode(header) + "." +
  base64UrlEncode(payload),
  secret
)

Pros:

• Stateless (no server-side session storage)
• Portable across domains
• Contains user information

Cons:

• Can’t revoke before expiration
• Token size can be large
• Vulnerable if secret is exposed

6. Load Balancing

Load balancers distribute incoming traffic across multiple servers, improving availability and preventing any single server from becoming a bottleneck.

6.1 Why Load Balancers?

Benefits:

• High Availability: If one server fails, traffic routes to healthy servers
• Scalability: Add more servers to handle increased load
• Performance: Distribute load evenly
• Flexibility: Perform maintenance without downtime

6.2 Load Balancer Architecture

6.3 Load Balancing Algorithms

1. Round Robin

• Distributes requests sequentially
• Simple and fair distribution
• Doesn’t account for server load or capacity

class RoundRobinLoadBalancer:
    def __init__(self, servers):
        self.servers = servers
        self.current = 0

    def get_server(self):
        server = self.servers[self.current]
        self.current = (self.current + 1) % len(self.servers)
        return server

2. Weighted Round Robin

• Assigns weight to each server based on capacity
• Servers with higher capacity get more requests

class WeightedRoundRobinLoadBalancer:
    def __init__(self, servers_with_weights):
        # servers_with_weights = [('server1', 5), ('server2', 3), ('server3', 2)]
        self.servers = []
        for server, weight in servers_with_weights:
            self.servers.extend([server] * weight)
        self.current = 0

    def get_server(self):
        server = self.servers[self.current]
        self.current = (self.current + 1) % len(self.servers)
        return server

3. Least Connections

• Routes to server with fewest active connections
• Good for long-lived connections

class LeastConnectionsLoadBalancer:
    def __init__(self, servers):
        self.connections = {server: 0 for server in servers}

    def get_server(self):
        return min(self.connections, key=self.connections.get)

    def on_connection_established(self, server):
        self.connections[server] += 1

    def on_connection_closed(self, server):
        self.connections[server] -= 1

4. Least Response Time

• Routes to server with lowest average response time
• Dynamically adapts to server performance

5. IP Hash

• Uses client IP to determine server
• Ensures same client always routes to same server
• Good for session persistence

import hashlib

class IPHashLoadBalancer:
    def __init__(self, servers):
        self.servers = servers

    def get_server(self, client_ip):
        hash_value = int(hashlib.md5(client_ip.encode()).hexdigest(), 16)
        server_index = hash_value % len(self.servers)
        return self.servers[server_index]

6. Random

• Randomly selects server
• Simple and works well with many servers

6.4 Load Balancer Layers

Layer 4 (Transport Layer) Load Balancing

• Operates at TCP/UDP level
• Routes based on IP and port
• Fast (no packet inspection)
• Cannot make routing decisions based on content

Layer 7 (Application Layer) Load Balancing

• Operates at HTTP level
• Can route based on URL, headers, cookies
• More intelligent routing
• Slower (needs to inspect packets)
• Can do SSL termination

6.5 Health Checks

Load balancers need to know which servers are healthy:

import time
import requests

class HealthChecker:
    def __init__(self, servers, check_interval=10):
        self.servers = servers
        self.healthy_servers = set(servers)
        self.check_interval = check_interval

    def check_health(self, server):
        try:
            response = requests.get(f"{server}/health", timeout=2)
            return response.status_code == 200
        except:
            return False

    def monitor(self):
        while True:
            for server in self.servers:
                if self.check_health(server):
                    self.healthy_servers.add(server)
                else:
                    self.healthy_servers.discard(server)
            time.sleep(self.check_interval)

    def get_healthy_servers(self):
        return list(self.healthy_servers)

6.6 Session Persistence (Sticky Sessions)

Challenge: With load balancing, subsequent requests from the same user might go to different servers.

Solutions:

1. Sticky Sessions at Load Balancer

• Load balancer remembers which server served a client
• Routes all requests from that client to same server
• Problem: If server dies, session is lost

2. Shared Session Storage

• Store sessions in Redis/Memcached
• Any server can serve any request
• More scalable and fault-tolerant

3. Client-Side Sessions (JWT)

• Session data stored in token on client
• Stateless servers
• Token passed with each request

7. Caching Strategies

7.1 What to Cache?

7.2 Cache Levels

1. Client-Side Caching

• Browser cache
• LocalStorage / SessionStorage
• Service Workers

2. CDN Caching

• Caches static assets close to users
• Reduces origin server load

3. Application-Level Caching

• In-memory caches (Redis, Memcached)
• Application server cache

4. Database Caching

• Query result cache
• Buffer pool cache

7.3 Caching Patterns

1. Cache-Aside (Lazy Loading)

Most common pattern:

def get_user(user_id):
    # Try cache first
    user = cache.get(f"user:{user_id}")

    if user is None:
        # Cache miss - load from database
        user = database.query(f"SELECT * FROM users WHERE id = {user_id}")

        # Store in cache for next time
        cache.set(f"user:{user_id}", user, ttl=3600)

    return user

Flow:

1. Application checks cache
2. If data exists (cache hit), return it
3. If data doesn’t exist (cache miss):
   • Load from database
   • Write to cache
   • Return data

Pros:

• Only requested data is cached
• Cache failure doesn’t break application

Cons:

• Initial request is slow (cache miss)
• Stale data possible if cache doesn’t expire

2. Read-Through Cache

Cache sits between application and database:

class ReadThroughCache:
    def __init__(self, cache, database):
        self.cache = cache
        self.database = database

    def get(self, key):
        # Cache handles database lookup automatically
        return self.cache.get(key, loader=lambda: self.database.get(key))

Flow:

1. Application requests data from cache
2. Cache checks if data exists
3. If not, cache loads from database automatically
4. Cache returns data

Pros:

• Cleaner application code
• Consistent caching logic

Cons:

• Cache becomes critical dependency
• Potential bottleneck

3. Write-Through Cache

Data written to cache and database simultaneously:

def update_user(user_id, data):
    # Write to both cache and database
    cache.set(f"user:{user_id}", data)
    database.update(f"UPDATE users SET ... WHERE id = {user_id}")

Pros:

• Cache always consistent with database
• No stale data

Cons:

• Slower writes (two operations)
• Cache may contain rarely-read data

4. Write-Behind (Write-Back) Cache

Data written to cache immediately, database updated asynchronously:

def update_user(user_id, data):
    # Write to cache immediately
    cache.set(f"user:{user_id}", data)

    # Queue database write for later
    write_queue.push({
        'operation': 'update',
        'table': 'users',
        'id': user_id,
        'data': data
    })

Pros:

• Very fast writes
• Can batch database writes

Cons:

• Risk of data loss if cache fails
• More complex to implement
• Eventual consistency

5. Refresh-Ahead

Proactively refresh cache before expiration:

import time
import threading

def refresh_ahead_cache(key, ttl, refresh_threshold=0.8):
    data = cache.get(key)

    if data is None:
        # Cache miss - load and cache
        data = load_from_database(key)
        cache.set(key, data, ttl=ttl)
    else:
        # Check if approaching expiration
        remaining_ttl = cache.ttl(key)
        if remaining_ttl < (ttl * refresh_threshold):
            # Asynchronously refresh
            threading.Thread(
                target=lambda: cache.set(key, load_from_database(key), ttl=ttl)
            ).start()

    return data

7.4 Cache Eviction Policies

When cache is full, which data should be removed?

1. LRU (Least Recently Used)

• Evicts least recently accessed items
• Most commonly used
• Good for general-purpose caching

2. LFU (Least Frequently Used)

• Evicts items accessed least often
• Good for data with varying access patterns

3. FIFO (First In First Out)

• Evicts oldest items first
• Simple but not always optimal

4. TTL (Time To Live)

• Items expire after fixed time
• Good for time-sensitive data

Implementation of LRU Cache:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return None
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            # Update and move to end
            self.cache.move_to_end(key)
        self.cache[key] = value

        if len(self.cache) > self.capacity:
            # Remove least recently used (first item)
            self.cache.popitem(last=False)

# Usage
cache = LRUCache(capacity=3)
cache.put("user:1", {"name": "Alice"})
cache.put("user:2", {"name": "Bob"})
cache.put("user:3", {"name": "Charlie"})
cache.put("user:4", {"name": "David"})  # Evicts user:1

7.5 Cache Considerations

1. Cache Expiration (TTL)

Set appropriate TTL based on data characteristics:

# Fast-changing data
cache.set("stock_price:AAPL", price, ttl=60)  # 1 minute

# Slow-changing data
cache.set("user_profile:123", profile, ttl=3600)  # 1 hour

# Rarely changing data
cache.set("product_category", categories, ttl=86400)  # 24 hours

2. Cache Stampede Prevention

Problem: When cached item expires, multiple requests simultaneously hit database.

Solution: Use locks or probabilistic early expiration:

import threading
import random

lock_dict = {}

def get_with_stampede_protection(key, ttl, load_function):
    data = cache.get(key)

    if data is None:
        # Get or create lock for this key
        if key not in lock_dict:
            lock_dict[key] = threading.Lock()

        lock = lock_dict[key]

        # Only one thread loads data
        with lock:
            # Double-check cache (another thread may have loaded it)
            data = cache.get(key)
            if data is None:
                data = load_function()
                cache.set(key, data, ttl=ttl)

    # Probabilistic early refresh
    remaining_ttl = cache.ttl(key)
    if remaining_ttl < ttl * 0.2:  # Last 20% of TTL
        if random.random() < 0.1:  # 10% chance
            threading.Thread(
                target=lambda: cache.set(key, load_function(), ttl=ttl)
            ).start()

    return data

3. Cache Warming

Pre-populate cache with frequently accessed data:

def warm_cache():
    """Run during application startup"""
    # Load popular users
    popular_users = database.query("SELECT * FROM users ORDER BY popularity DESC LIMIT 1000")
    for user in popular_users:
        cache.set(f"user:{user.id}", user, ttl=3600)

    # Load popular products
    popular_products = database.query("SELECT * FROM products ORDER BY sales DESC LIMIT 5000")
    for product in popular_products:
        cache.set(f"product:{product.id}", product, ttl=7200)

4. Distributed Caching

For high availability and scalability:

7.6 Redis vs Memcached

8. Content Delivery Networks (CDN)

CDNs are geographically distributed networks of servers that deliver content to users based on their location.

8.1 How CDN Works

CDN Request Flow:

8.2 Benefits of CDN

1. Reduced Latency

   • Content served from nearest location
   • Fewer network hops

2. Reduced Origin Load

   • CDN handles most traffic
   • Origin serves only cache misses

3. Better Availability

   • Multiple edge servers provide redundancy
   • Can serve stale content if origin is down

4. DDoS Protection

   • Distributed architecture absorbs attacks
   • Traffic filtered at edge

5. Cost Savings

   • Reduced bandwidth from origin
   • Lower infrastructure costs

8.3 What to Put on CDN?

Static Assets (Best for CDN):

• Images
• CSS files
• JavaScript files
• Fonts
• Videos
• PDFs and downloadable files

Dynamic Content (Possible with advanced CDNs):

• API responses with caching headers
• Personalized content (with edge computing)
• HTML pages

8.4 CDN Considerations

1. Cache Invalidation

Challenge: How to update cached content?

Solutions:

a. Time-Based (TTL)

Cache-Control: max-age=86400  # Cache for 24 hours

b. Versioned URLs

/static/app.js?v=1.2.3
/static/app.1.2.3.js
/static/app.abc123hash.js

c. Cache Purge API

import requests

def purge_cdn_cache(url):
    # Cloudflare example
    response = requests.post(
        'https://api.cloudflare.com/client/v4/zones/{zone_id}/purge_cache',
        headers={'Authorization': 'Bearer {api_token}'},
        json={'files': [url]}
    )
    return response.json()

2. Cache-Control Headers

# Don't cache
Cache-Control: no-store

# Cache but revalidate
Cache-Control: no-cache

# Cache for 1 hour
Cache-Control: max-age=3600

# Cache for 1 hour, revalidate after expiry
Cache-Control: max-age=3600, must-revalidate

# Private (browser only, not CDN)
Cache-Control: private, max-age=3600

# Public (can be cached by CDN)
Cache-Control: public, max-age=86400

# Immutable (never changes)
Cache-Control: public, max-age=31536000, immutable

3. CDN Push vs Pull

Pull CDN (Most Common):

• CDN fetches content from origin on first request
• Origin remains source of truth
• Lazy loading

Push CDN:

• You upload content directly to CDN
• No origin server needed
• Manual or automated uploads

9. Database Systems

9.1 SQL vs NoSQL

9.2 When to Use SQL?

Use SQL (Relational Databases) When:

1. Data is structured and relationships are important

   • E-commerce (orders, customers, products)
   • Financial systems (accounts, transactions)
   • CRM systems

2. ACID compliance is required

   • Banking and financial applications
   • Inventory management
   • Any system where data consistency is critical

3. Complex queries needed

   • Reporting and analytics
   • Joins across multiple tables
   • Aggregations and complex filtering

4. Data integrity constraints

   • Foreign keys
   • Unique constraints
   • Check constraints

Example Schema (E-commerce):

CREATE TABLE users (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    email VARCHAR(255) UNIQUE NOT NULL,
    name VARCHAR(255) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE products (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(255) NOT NULL,
    price DECIMAL(10, 2) NOT NULL,
    stock INT NOT NULL,
    category_id BIGINT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    FOREIGN KEY (category_id) REFERENCES categories(id)
);

CREATE TABLE orders (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    user_id BIGINT NOT NULL,
    total_amount DECIMAL(10, 2) NOT NULL,
    status ENUM('pending', 'paid', 'shipped', 'delivered') DEFAULT 'pending',
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    FOREIGN KEY (user_id) REFERENCES users(id)
);

CREATE TABLE order_items (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    order_id BIGINT NOT NULL,
    product_id BIGINT NOT NULL,
    quantity INT NOT NULL,
    price DECIMAL(10, 2) NOT NULL,
    FOREIGN KEY (order_id) REFERENCES orders(id),
    FOREIGN KEY (product_id) REFERENCES products(id)
);

9.3 When to Use NoSQL?

Use NoSQL When:

1. Massive scale required

   • Billions of rows
   • Petabytes of data
   • Millions of operations per second

2. Schema flexibility needed

   • Rapidly evolving data models
   • Each record has different fields
   • Semi-structured or unstructured data

3. High availability over consistency

   • Social media feeds
   • Real-time analytics
   • IoT data

4. Denormalized data is acceptable

   • Data duplication is okay
   • Joins are rare

NoSQL Types:

1. Key-Value Stores (Redis, DynamoDB)

Simplest NoSQL model:

# Redis example
cache.set("user:123", json.dumps({
    "name": "John Doe",
    "email": "john@example.com"
}))

user = json.loads(cache.get("user:123"))

Use cases:

• Session storage
• Caching
• Real-time analytics
• Shopping carts

2. Document Databases (MongoDB, CouchDB)

Store JSON-like documents:

// MongoDB example
{
    "_id": ObjectId("507f1f77bcf86cd799439011"),
    "name": "John Doe",
    "email": "john@example.com",
    "addresses": [
        {
            "type": "home",
            "street": "123 Main St",
            "city": "San Francisco",
            "zip": "94102"
        },
        {
            "type": "work",
            "street": "456 Market St",
            "city": "San Francisco",
            "zip": "94103"
        }
    ],
    "orders": [
        {"order_id": "ORD001", "total": 99.99},
        {"order_id": "ORD002", "total": 149.99}
    ]
}

Use cases:

• Content management
• User profiles
• Product catalogs
• Real-time analytics

3. Column-Family Stores (Cassandra, HBase)

Optimized for write-heavy workloads:

Row Key: user_123
  Column Family: profile
    name: "John Doe"
    email: "john@example.com"

  Column Family: activity
    2024-01-15:10:30:00: "login"
    2024-01-15:10:31:22: "viewed_product_456"
    2024-01-15:10:35:45: "added_to_cart_456"

Use cases:

• Time-series data
• Event logging
• IoT sensor data
• Message systems

4. Graph Databases (Neo4j, Amazon Neptune)

Optimized for relationships:

// Neo4j example
(John:Person {name: "John Doe"})
-[:FRIENDS_WITH]->(Jane:Person {name: "Jane Smith"})
-[:WORKS_AT]->(Company:Company {name: "Acme Corp"})
<-[:WORKS_AT]-(Bob:Person {name: "Bob Johnson"})
-[:LIKES]->(Product:Product {name: "Widget"})

Use cases:

• Social networks
• Recommendation engines
• Fraud detection
• Knowledge graphs

9.4 Database Performance Optimization

1. Indexing

Indexes speed up queries but slow down writes:

-- Create index
CREATE INDEX idx_users_email ON users(email);
CREATE INDEX idx_products_category ON products(category_id);

-- Composite index
CREATE INDEX idx_orders_user_status ON orders(user_id, status);

-- Full-text index
CREATE FULLTEXT INDEX idx_products_search ON products(name, description);

Types of Indexes:

• B-Tree Index (default): Good for equality and range queries
• Hash Index: Only for equality comparisons
• Full-Text Index: For text search
• Spatial Index: For geographic data

Index Best Practices:

• Index columns used in WHERE, JOIN, ORDER BY
• Don’t over-index (slows writes)
• Use composite indexes for multi-column queries
• Monitor index usage and remove unused indexes

2. Query Optimization

-- Bad: SELECT *
SELECT * FROM users WHERE email = 'john@example.com';

-- Good: Select only needed columns
SELECT id, name, email FROM users WHERE email = 'john@example.com';

-- Use EXPLAIN to analyze queries
EXPLAIN SELECT * FROM orders
WHERE user_id = 123 AND status = 'pending';

-- Avoid N+1 queries
-- Bad: Query in loop
for user_id in user_ids:
    orders = db.query(f"SELECT * FROM orders WHERE user_id = {user_id}")

-- Good: Single query
orders = db.query(f"SELECT * FROM orders WHERE user_id IN ({','.join(user_ids)})")

3. Connection Pooling

import psycopg2
from psycopg2 import pool

# Create connection pool
connection_pool = pool.SimpleConnectionPool(
    minconn=5,
    maxconn=20,
    host="localhost",
    database="mydb",
    user="user",
    password="password"
)

def execute_query(query):
    conn = connection_pool.getconn()
    try:
        cursor = conn.cursor()
        cursor.execute(query)
        result = cursor.fetchall()
        return result
    finally:
        connection_pool.putconn(conn)

10. Database Sharding and Partitioning

When a single database can’t handle the load, we need to split data across multiple databases.

10.1 Vertical vs Horizontal Partitioning

Vertical Partitioning (Splitting by columns)

Original Table:
users: id, name, email, address, bio, profile_pic

Split into:
users_basic: id, name, email
users_extended: id, address, bio, profile_pic

Use when:

• Different columns accessed with different frequencies
• Some columns are rarely used
• Reduce I/O for common queries

Horizontal Partitioning/Sharding (Splitting by rows)

users table split by region:
users_us: All US users
users_eu: All EU users
users_asia: All ASIA users

10.2 Sharding Strategies

1. Range-Based Sharding

Split data based on ranges:

def get_shard_by_range(user_id):
    if user_id < 1000000:
        return "shard_1"
    elif user_id < 2000000:
        return "shard_2"
    elif user_id < 3000000:
        return "shard_3"
    else:
        return "shard_4"

Pros:

• Simple to implement
• Easy to add new ranges

Cons:

• Uneven distribution (hot shards)
• Difficult to rebalance

2. Hash-Based Sharding

Use hash function to determine shard:

import hashlib

def get_shard_by_hash(user_id, num_shards):
    hash_value = int(hashlib.md5(str(user_id).encode()).hexdigest(), 16)
    shard_id = hash_value % num_shards
    return f"shard_{shard_id}"

Pros:

• Even distribution
• Automatic balancing

Cons:

• Adding shards requires rehashing
• Range queries difficult

3. Geographic Sharding

Split by location:

def get_shard_by_geo(user_location):
    if user_location in ['US', 'CA', 'MX']:
        return "shard_americas"
    elif user_location in ['GB', 'FR', 'DE']:
        return "shard_europe"
    elif user_location in ['CN', 'JP', 'IN']:
        return "shard_asia"
    else:
        return "shard_global"

Pros:

• Low latency (data close to users)
• Regulatory compliance (data residency)

Cons:

• Uneven distribution
• Cross-shard queries complex

4. Directory-Based Sharding

Maintain lookup table:

# Shard directory
shard_directory = {
    "user:1": "shard_1",
    "user:2": "shard_1",
    "user:3": "shard_2",
    "user:4": "shard_3",
}

def get_shard_by_directory(user_id):
    return shard_directory.get(f"user:{user_id}", "shard_default")

Pros:

• Maximum flexibility
• Easy to migrate data between shards

Cons:

• Directory is single point of failure
• Additional lookup required

10.3 Challenges with Sharding

1. Cross-Shard Joins

Problem: Can’t join tables across different databases.

Solution: Denormalize data or handle joins at application level:

def get_user_with_orders(user_id):
    # Get shard for user
    user_shard = get_shard(user_id)
    user = user_shard.query(f"SELECT * FROM users WHERE id = {user_id}")

    # Orders might be on different shard
    order_shard = get_shard_for_orders(user_id)
    orders = order_shard.query(f"SELECT * FROM orders WHERE user_id = {user_id}")

    # Combine in application
    user['orders'] = orders
    return user

2. Distributed Transactions

Problem: Transaction spanning multiple shards.

Solution: Two-Phase Commit (2PC) or avoid distributed transactions:

def transfer_money(from_user_id, to_user_id, amount):
    from_shard = get_shard(from_user_id)
    to_shard = get_shard(to_user_id)

    if from_shard == to_shard:
        # Same shard - normal transaction
        with from_shard.transaction():
            from_shard.execute(f"UPDATE accounts SET balance = balance - {amount} WHERE user_id = {from_user_id}")
            to_shard.execute(f"UPDATE accounts SET balance = balance + {amount} WHERE user_id = {to_user_id}")
    else:
        # Different shards - use 2PC or saga pattern
        # (More complex - see distributed transactions section)
        pass

3. Rebalancing

Problem: Adding/removing shards requires data migration.

Solution: Consistent hashing or careful planning:

def rebalance_shards(old_shards, new_shards):
    # Calculate which data needs to move
    for key in get_all_keys():
        old_shard = hash(key) % old_shards
        new_shard = hash(key) % new_shards

        if old_shard != new_shard:
            # Migrate data
            data = get_data_from_shard(old_shard, key)
            write_data_to_shard(new_shard, key, data)
            delete_data_from_shard(old_shard, key)

10.4 Sharding Architecture

This is Part 1 of the comprehensive guide. The document will continue with remaining sections covering Database Replication, Distributed Systems, Design Patterns, Real-World System Designs (Twitter, Google Maps, Key-Value Store, etc.), Case Studies, and extensive references.

Would you like me to continue with the next sections?

11. Database Replication

Database replication is the process of copying data from one database to another to ensure redundancy, improve availability, and enhance read performance.

11.1 Master-Slave Replication

The most common replication pattern:

How it works:

1. All write operations go to the master database
2. Master propagates changes to slave databases
3. Read operations are distributed across slave databases
4. Improves read performance through load distribution

Advantages:

• Better read performance (distribute reads across multiple servers)
• Data backup (slaves serve as backups)
• Analytics without impacting production (run reports on slaves)
• High availability (promote slave if master fails)

Disadvantages:

• Replication lag (slaves might be slightly behind master)
• Single point of failure for writes (only one master)
• Complexity in failover scenarios

11.2 Master-Master Replication

Both databases accept writes and sync with each other:

Advantages:

• No single point of failure for writes
• Better write performance (distribute writes)
• Lower latency for geographically distributed systems

Disadvantages:

• Complex conflict resolution
• Potential for inconsistency
• More difficult to manage

Conflict Resolution Strategies:

# Last Write Wins (LWW)
def resolve_conflict_lww(value1, value2):
    """
    Choose the value with the latest timestamp
    """
    if value1.timestamp > value2.timestamp:
        return value1
    return value2

# Version Vector
class VersionVector:
    def __init__(self):
        self.vector = {}
    
    def increment(self, node_id):
        self.vector[node_id] = self.vector.get(node_id, 0) + 1
    
    def merge(self, other):
        """Merge two version vectors"""
        for node_id, version in other.vector.items():
            self.vector[node_id] = max(
                self.vector.get(node_id, 0),
                version
            )
    
    def compare(self, other):
        """
        Returns:
        - 'before' if self < other
        - 'after' if self > other
        - 'concurrent' if conflicting
        """
        self_greater = False
        other_greater = False
        
        all_nodes = set(self.vector.keys()) | set(other.vector.keys())
        
        for node in all_nodes:
            self_ver = self.vector.get(node, 0)
            other_ver = other.vector.get(node, 0)
            
            if self_ver > other_ver:
                self_greater = True
            elif other_ver > self_ver:
                other_greater = True
        
        if self_greater and not other_greater:
            return 'after'
        elif other_greater and not self_greater:
            return 'before'
        else:
            return 'concurrent'

11.3 Replication Methods

Synchronous Replication:

• Master waits for slave acknowledgment before confirming write
• Strong consistency
• Higher latency
• Used when data consistency is critical

def synchronous_write(data):
    # Write to master
    master.write(data)
    
    # Wait for all slaves to acknowledge
    for slave in slaves:
        slave.write(data)
        slave.acknowledge()
    
    return "Write successful"

Asynchronous Replication:

• Master confirms write immediately
• Slaves updated eventually
• Lower latency
• Risk of data loss if master fails

def asynchronous_write(data):
    # Write to master
    master.write(data)
    
    # Queue replication (don't wait)
    for slave in slaves:
        replication_queue.enqueue({
            'slave': slave,
            'data': data
        })
    
    return "Write successful"

Semi-Synchronous Replication:

• Master waits for at least one slave
• Balance between consistency and performance

12. Distributed Systems Concepts

12.1 What is a Distributed System?

Characteristics:

• Multiple autonomous computers: Independent nodes with their own CPU, memory, and storage
• Connected through a network: Communication via TCP/IP, message queues, or RPC
• Coordinate actions through message passing: No shared memory between nodes
• No shared memory: Each node has isolated memory space
• Failures are partial: Some components can fail while others continue working

12.2 Fallacies of Distributed Computing

13. CAP Theorem and Consistency Models

13.1 CAP Theorem

In Reality:

• Network partitions will happen (P is mandatory)
• Must choose between C and A during partition
• When partition heals, system needs reconciliation strategy

CP Systems (Consistency + Partition Tolerance):

• Wait for partition to heal
• Return errors during partition
• Example: Banking systems, MongoDB (with majority write concern)

AP Systems (Availability + Partition Tolerance):

• Always accept reads/writes
• Resolve conflicts later
• Example: Social media feeds, DNS, Cassandra

13.2 Consistency Models

Strong Consistency:

• After a write, all reads see that value
• Highest consistency guarantee
• Higher latency

def strong_consistency_read():
    # Read from master or wait for replication
    return master.read()

Eventual Consistency:

• If no new updates, eventually all reads return same value
• Lower latency
• Used in AP systems

def eventual_consistency_read():
    # Read from any replica
    # Might return stale data
    return random.choice(replicas).read()

Read-Your-Writes Consistency:

• Users see their own writes immediately
• Others might see stale data

session_writes = {}

def write(user_id, data):
    master.write(data)
    session_writes[user_id] = time.now()

def read(user_id):
    if user_id in session_writes:
        # Read from master for this user
        return master.read()
    else:
        # Can read from replica for others
        return replica.read()

Monotonic Reads:

• If user reads value A, subsequent reads won’t return older values

user_last_read_time = {}

def monotonic_read(user_id):
    last_time = user_last_read_time.get(user_id, 0)
    
    # Only read from replicas caught up to last_time
    valid_replicas = [
        r for r in replicas 
        if r.last_sync_time >= last_time
    ]
    
    result = random.choice(valid_replicas).read()
    user_last_read_time[user_id] = time.now()
    return result

Causal Consistency:

• Related operations are seen in correct order
• Independent operations can be seen in any order

13.3 BASE Properties

Alternative to ACID for distributed systems:

• Basically Available: System appears to work most of the time
• Soft state: State may change without input (due to eventual consistency)
• Eventual consistency: System becomes consistent over time

14. Message Queues and Event-Driven Architecture

14.1 Why Message Queues?

14.2 Message Queue Patterns

1. Point-to-Point (Queue)

Each message consumed by exactly one consumer:

class MessageQueue:
    def __init__(self):
        self.queue = []
        self.lock = threading.Lock()
    
    def send(self, message):
        with self.lock:
            self.queue.append(message)
    
    def receive(self):
        with self.lock:
            if self.queue:
                return self.queue.pop(0)
            return None

# Usage
queue = MessageQueue()

# Producer
queue.send({"order_id": 123, "action": "process"})

# Consumer
message = queue.receive()
if message:
    process_order(message)

2. Publish-Subscribe (Topic)

Each message consumed by all subscribers:

class PubSubTopic:
    def __init__(self):
        self.subscribers = []
        self.messages = []
    
    def subscribe(self, subscriber):
        self.subscribers.append(subscriber)
    
    def publish(self, message):
        for subscriber in self.subscribers:
            subscriber.receive(message)

# Usage
topic = PubSubTopic()

# Subscribers
email_service = EmailService()
sms_service = SMSService()
push_service = PushService()

topic.subscribe(email_service)
topic.subscribe(sms_service)
topic.subscribe(push_service)

# Publisher
topic.publish({"event": "order_placed", "user_id": 123})
# All three services receive the message

14.3 Popular Message Queue Systems

RabbitMQ:

• Feature-rich
• Complex routing
• Good for traditional message queueing

Apache Kafka:

• High throughput
• Log-based
• Great for event streaming
• Stores messages for replay

Amazon SQS:

• Fully managed
• Simple to use
• Good for AWS ecosystem

Redis Pub/Sub:

• Very fast (in-memory)
• Simple pub/sub
• No message persistence

14.4 Event-Driven Architecture Example

# Event Bus
class EventBus:
    def __init__(self):
        self.handlers = {}
    
    def subscribe(self, event_type, handler):
        if event_type not in self.handlers:
            self.handlers[event_type] = []
        self.handlers[event_type].append(handler)
    
    def publish(self, event):
        event_type = event.get('type')
        if event_type in self.handlers:
            for handler in self.handlers[event_type]:
                try:
                    handler(event)
                except Exception as e:
                    print(f"Handler error: {e}")

# Services
def send_confirmation_email(event):
    user_id = event['user_id']
    order_id = event['order_id']
    print(f"Sending email to user {user_id} for order {order_id}")

def update_inventory(event):
    items = event['items']
    print(f"Updating inventory for {items}")

def send_notification(event):
    user_id = event['user_id']
    print(f"Sending push notification to user {user_id}")

# Setup
event_bus = EventBus()
event_bus.subscribe('order_placed', send_confirmation_email)
event_bus.subscribe('order_placed', update_inventory)
event_bus.subscribe('order_placed', send_notification)

# Trigger event
event_bus.publish({
    'type': 'order_placed',
    'order_id': 12345,
    'user_id': 789,
    'items': ['item1', 'item2']
})