Weekly System Design Challenges

Key decisions:

1. ID Generation: Base62 encoding of a distributed auto-increment ID (Snowflake) or MD5 hash (first 43 bits → base62). Auto-increment avoids collisions.
2. Storage: NoSQL (DynamoDB/Cassandra) for key-value lookups — partition key = short URL, value = long URL + metadata + TTL.
3. Caching: Redis cache for hot URLs (80/20 rule — 20% of URLs get 80% of traffic). Cache ~20% of daily redirects.
4. Architecture: Write path → ID generator → DB; Read path → Cache → DB → 301/302 Redirect.
5. Analytics: Async — write click events to Kafka → aggregate in Flink/Spark → store counts.

Scale math:

• Writes: 100M/day = 1,157/sec
• Reads: 1B/day = 11,574/sec
• Storage: 100M * 500 bytes = 50GB/day → 18TB over 1 year

Trade-offs: 301 (permanent redirect, better for SEO, no analytics) vs 302 (temporary, enables click tracking).

Key decisions:

1. Algorithm: Token bucket per user/endpoint — allows bursts while enforcing average rate. Each bucket has tokens (current count) and last_refill_timestamp.
2. Storage: Redis — atomic INCR + EXPIRE for fixed window, or Lua script for sliding window log. Redis handles ~100K ops/sec per node.
3. Architecture: Rate limiter as middleware/sidecar. Check Redis → allow/deny → forward to upstream.
4. Distributed sync: Redis is the single source of truth. Use Redis Cluster for sharding across users.
5. Rules engine: Store rules in a config service (e.g., {endpoint: "/login", limit: 5, window: 60s}). Cache rules locally.

Failure handling:

• Redis down → fail open (allow requests) with local in-memory fallback
• Race conditions → Redis Lua scripts (atomic read-check-increment)

Headers returned: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After

Key decisions:

1. Architecture: Event-driven pipeline — API → Validation → Priority Queue → Channel Router → Vendor Adapters (APNs, FCM, Twilio, SendGrid).
2. Queuing: Kafka with priority topics (critical, high, normal, low). Critical topic gets more consumer partitions.
3. Preference service: User preferences in Redis (fast lookup). Check before sending: channel enabled? quiet hours? rate limit OK?
4. Delivery tracking: Each notification gets a UUID. Track state machine: CREATED → QUEUED → SENT → DELIVERED / FAILED. Store in Cassandra.
5. Retry: Exponential backoff with max 3 retries. DLQ for permanently failed messages.
6. Deduplication: Idempotency key (hash of user_id + template_id + params + time_window) in Redis with 1-hour TTL.

Scale math:

• 10B/day = 115K/sec average, 500K/sec peak
• Kafka handles this easily with 100+ partitions per topic
• Device token store: 1B devices * 200 bytes = 200GB (fits in sharded DB)

Key decisions:

1. Connection layer: WebSocket gateway servers (each handling ~500K connections). Session registry in Redis maps user_id → gateway_server_id.
2. Message flow: Sender → Gateway → Message Service → lookup recipient gateway → push to recipient. If offline → store in message queue (Cassandra).
3. Storage: Messages in Cassandra (partition key = conversation_id, clustering key = timestamp). Hot messages cached in Redis.
4. Ordering: Per-conversation monotonic sequence number (atomic counter in Redis or DB sequence).
5. Group messaging: Fan-out on write for small groups (< 256). Each member gets a copy in their inbox. Avoids read-time fan-out latency.
6. Read receipts: Lightweight status updates piggybacked on the WebSocket connection. Batch receipt updates to reduce writes.
7. Media: Upload to S3/CDN → send URL as message payload. Thumbnail generated async.

Offline delivery: When user connects → pull all pending messages from their inbox (Cassandra partition scan by user_id + undelivered flag).

Key decisions:

1. Hybrid fan-out: Fan-out on write for normal users (< 10K followers) — push post ID to each follower's feed cache. Fan-out on read for celebrities — pull their posts at read time and merge.
2. Feed cache: Redis sorted set per user (score = timestamp or ranking score). Store only post IDs (not full content). Limit to last 1000 items.
3. Ranking: Lightweight ML model scores posts at fan-out time (features: recency, engagement, relationship strength). Re-rank at read time with latest signals.
4. Feed generation: Read from feed cache (Redis) → hydrate post IDs from Post Service → apply final ranking → return page.
5. Pagination: Cursor-based (last seen post_id + timestamp) — not offset-based. Guarantees no duplicates.
6. Post storage: Posts in sharded MySQL/PostgreSQL (partition by user_id). Hot posts cached in Redis.

Scale math:

• Fan-out: User with 200 followers → 200 Redis writes per post. Celebrity with 100M followers → DON'T fan out, pull at read time.
• Feed cache: 500M users * 1000 post IDs * 8 bytes = 4TB Redis cluster

Key decisions:

1. Upload pipeline: Client → Upload Service (resumable, chunked uploads via tus protocol) → Object Storage (S3) → Transcode Queue.
2. Transcoding: DAG-based pipeline (split video into segments → transcode each segment in parallel → merge). Use FFmpeg on spot instances. Generate HLS manifest (.m3u8) with multiple quality levels.
3. Storage tiering: Hot videos (< 30 days, popular) on SSD-backed CDN origin. Cold videos (long tail) on cheaper storage (S3 Glacier) with on-demand warming.
4. Streaming: HLS/DASH adaptive bitrate. CDN serves segments. Client measures bandwidth → requests appropriate quality segment. Manifest lists all available bitrates.
5. CDN strategy: Multi-tier CDN (edge → regional → origin). Cache popular videos at edge. Use consistent hashing for cache key distribution.
6. Recommendations: Collaborative filtering + content-based. Pre-compute for popular videos, compute in real-time for long-tail using embedding similarity.

Scale math:

• Upload: 500 hours/min * 60 min * 3GB avg = 90TB/hour of raw uploads
• Storage: 1B videos * 5 renditions * 2GB avg = 10EB (exabytes) — need tiered storage
• Bandwidth: 500M views/day * 500MB avg = 250PB/day egress

Key decisions:

1. Location service: Drivers send GPS coordinates every 3 seconds. Store in Redis with geospatial index (GEOADD, GEORADIUS). Shard by city/region.
2. Matching engine: When rider requests → query nearby available drivers (within expanding radius) → rank by ETA → send request to top-K drivers → first accept wins.
3. Spatial indexing: Geohash-based grid (precision level 6 = ~1.2km cells). Store driver locations in cells. "Nearby" = same cell + 8 adjacent cells.
4. Surge pricing: Supply/demand ratio per geohash cell. Calculate in real-time: surge_multiplier = demand_count / (supply_count * baseline_ratio). Smooth with moving average.
5. Trip tracking: Active trip → location updates published to Kafka → consumed by Trip Service → stored in time-series DB → pushed to rider via WebSocket.
6. ETA: Pre-computed road graph (OSRM/Valhalla) + real-time traffic data. ML model adjusts for historical patterns.

Scale math:

• Location writes: 5M drivers / 3s = 1.7M writes/sec to Redis (sharded across cities)
• Matching: 10M rides/day = 115 matches/sec (bursty — peak 10x during rush hour)
• Geospatial queries: Redis GEORADIUS handles 100K+ queries/sec per shard

Key decisions:

1. Partitioning: Consistent hashing with virtual nodes (150+ vnodes per physical node). Ensures even distribution and minimal rebalancing on node add/remove.
2. Replication: Each key replicated to N=3 nodes (primary + 2 replicas on the hash ring). Writes go to primary → async replicate to followers. Configurable consistency (W=1 for speed, W=2 for durability).
3. Data structures: In-memory hash table per node. Sub-structures (lists, sets, sorted sets) stored as optimized C data structures. Memory-mapped for persistence snapshots.
4. Eviction: LRU approximation (sample 5 random keys, evict the least recently used among them). More memory-efficient than true LRU (no linked list overhead).
5. Failure detection: Gossip protocol — each node pings random peers every 1s. If no response after 3 attempts, mark as suspected. If majority agree, mark as dead → promote replica.
6. Hot keys: Client-side caching with server-assisted invalidation (tracking which clients cached which keys). Or: replicate hot keys to all nodes.
7. Cache stampede prevention: Probabilistic early expiration (recompute before TTL expires based on current_time + random() * beta * compute_time > expiry). Or: single-flight/lock per key.

Client routing: Smart client (knows the hash ring topology) routes directly to the correct node. Gossip protocol keeps clients updated on topology changes.

Scale math:

• 10M ops/sec / 10 nodes = 1M ops/sec per node (achievable with in-memory store)
• 100TB / 10 nodes = 10TB per node (need large-memory machines or SSD-backed with memory caching)