System Design

Scalability
• Vertical scaling: more CPU/RAM on one server
• Horizontal scaling: more servers, requires stateless design
• Load balancing: distribute traffic (Round Robin, Least Connections, Consistent Hashing)

Availability & Reliability
• Availability = uptime / (uptime + downtime). "Five 9s" = 99.999%
• Redundancy: no single point of failure
• Failover: automatic switchover to backup
• Replication: data copies across nodes

CAP Theorem In a distributed system, you can guarantee only 2 of 3:
• Consistency: every read gets the latest write
• Availability: every request gets a response
• Partition Tolerance: system works despite network splits

Latency vs Throughput
• Latency: time for one request (ms)
• Throughput: requests per second (RPS)
• Optimize for the bottleneck, not the best-case

DNS Domain → IP resolution. TTL caching at multiple levels.

CDN (Content Delivery Network) Serve static assets from edge locations close to users. Cloudflare, Fastly, CloudFront.

Load Balancer Distribute traffic. L4 (TCP/UDP) vs L7 (HTTP/HTTPS). Can terminate SSL.

API Gateway Single entry point for microservices. Auth, rate limiting, routing, logging.

Message Queues Async decoupling. Kafka (high throughput), RabbitMQ (flexible routing), SQS (managed).

Caching
• Client-side (browser cache), CDN, Application cache (Redis, Memcached), Database query cache
• Cache eviction: LRU, LFU, TTL-based
• Cache invalidation strategies: write-through, write-back, write-around

Databases
• Relational (RDBMS): ACID, normalized, SQL. PostgreSQL, MySQL.
• NoSQL: flexible schema. Document (MongoDB), Key-Value (Redis, DynamoDB), Column (Cassandra), Graph (Neo4j).
• Sharding: horizontal partitioning across database nodes
• Read replicas: offload read traffic from primary

Microservices Small, independently deployable services with single responsibilities. Communicate via REST or messaging.

Event-Driven Architecture Services publish/subscribe to events. Loose coupling, high scalability.

CQRS (Command Query Responsibility Segregation) Separate read and write models. Write side emits events, read side builds optimized projections.

Event Sourcing Store state changes as an append-only event log. Replay to reconstruct state.

Circuit Breaker Prevent cascading failures. Open (reject) → Half-Open (probe) → Closed (allow).

Saga Pattern Distributed transactions across services. Choreography (events) vs Orchestration (central coordinator).

Rate Limiting Protect APIs from abuse. Token bucket, Leaky bucket, Fixed/Sliding window.

Step 1 Clarify Requirements (5 min)
• Functional: what features does the system need?
• Non-functional: scale (users/data), latency targets, availability SLA

Step 2 Capacity Estimation (5 min)
• Daily Active Users → requests/sec
• Storage needs (data size × users × days)
• Bandwidth (read/write ratios)

Step 3 High-Level Design (10 min)
• Draw major components: clients → CDN → load balancer → app servers → DB/cache
• Identify data flow end-to-end

Step 4 Deep Dive (15 min)
• Pick 23 interesting components to detail
• DB schema, API design, caching strategy, replication

Step 5 Identify & Resolve Bottlenecks (5 min)
• Single points of failure?
• How does it scale 10×? 100×?
• Monitoring and alerting strategy

Requirements
• Shorten long URLs to short codes (bit.ly style)
• 100M URLs/day written, 10B reads/day (100:1 read:write)
• Links never expire (or optional TTL)
• Custom slugs support

Capacity Estimation `` Writes: 100M/day = ~1,160/s Reads: 10B/day = ~116,000/s Storage: 100M × 500 bytes = ~50GB/day → ~18TB/year ``

Core Algorithm Base62 Encoding ```python import hashlib, string

CHARS = string.ascii_letters + string.digits # 62 chars

def encode(num: int, length=7) -> str: result = [] while num: result.append(CHARS[num % 62]) num //= 62 return ''.join(reversed(result)).zfill(length)

# Option A: Counter-based (simple, sequential IDs) # ID 12345 → encode(12345) → "3d7"

# Option B: Hash-based (non-sequential, distributed) def shorten(long_url: str) -> str: hash_val = int(hashlib.md5(long_url.encode()).hexdigest(), 16) return encode(hash_val % (62**7)) ```

Architecture ``` Client → Load Balancer → App Servers ↓ ↓ Write Path Read Path (MySQL) (Redis Cache → MySQL)

Write: generate short code, store {short → long}, return short URL Read: look up in Redis first (cache hit ~90%), fallback to MySQL

Cache strategy: write-through on insert, TTL = 24h for hot URLs ```

Database Schema ``sql CREATE TABLE urls ( id BIGINT PRIMARY KEY AUTO_INCREMENT, short_code CHAR(7) NOT NULL UNIQUE, long_url TEXT NOT NULL, user_id BIGINT, created_at TIMESTAMP DEFAULT NOW(), expires_at TIMESTAMP, clicks BIGINT DEFAULT 0 ); CREATE INDEX idx_short ON urls(short_code); ``