Walkthrough 1 — Design a URL Shortener (TinyURL)

# Design a URL Shortener (TinyURL) ## The brief Build a URL shortener like TinyURL or Bit.ly. User submits a long URL; gets a short URL back. Visiting short URL redirects to long URL. ## Step 1: Clarify requirements In an interview, ask: - Read:write ratio? (Typically 100:1 — many more redirects than creations.) - Custom slugs allowed? (Vanity URLs.) - Expiration? (Auto-delete after N days?) - Analytics? (Click count, geo, referrer.) - Auth? (Anyone can shorten, or only logged-in users?) Assume for this design: - 100M new URLs/month. - 100:1 read:write ratio. - 7-char short URL. - No expiration. - Basic click count analytics. ## Step 2: Capacity estimation 100M URLs/month × 12 months × 5 years = 6B URLs total in 5 years. Storage per URL: ~500 bytes (long URL + short slug + metadata) → 3TB total. Throughput: - Writes: 100M / (30 × 86400) = ~40 writes/sec average. Peak: 200/sec. - Reads: 40 × 100 = 4000 reads/sec average. Peak: 20000/sec. Bandwidth: redirects are tiny (HTTP 301 with new URL); not a concern. ## Step 3: High-level design ``` [Client] ↓ [Load Balancer] ↓ [Web Service (stateless, many instances)] ↓ ↓ [Cache (Redis)] [Database] ↓ (cache miss) ↓ [Database lookup] ``` ## Step 4: Short URL generation Two main approaches: ### Approach A: Hash-based Hash the long URL (MD5/SHA), take first 7 chars (base62). Pros: deterministic; same long URL → same short URL. Cons: collisions need handling (rare with 7 chars × 62 alphabet = 3.5T possibilities, but still). ### Approach B: Counter-based Auto-increment ID → encode to base62 → 7-char string. ```python def encode(n): chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" result = "" while n > 0: result = chars[n % 62] + result n //= 62 return result.zfill(7) ``` ID 1 → "0000001"; ID 62 → "0000010"; etc. Pros: no collisions; sequential. Cons: predictable (people can iterate URLs). Mitigate with random offset. ### Distributed counter Single counter = bottleneck. Options: - **Ranges**: each web server reserves a batch of IDs (e.g., 1000) and serves from it; refresh from DB when exhausted. - **Snowflake-style**: timestamp + datacenter_id + worker_id + sequence. - **UUID**: simpler but longer (16 chars base62, not 7). For 7-char short URLs, range-based counter is most common. ## Step 5: Database Schema: ```sql CREATE TABLE urls ( short_code VARCHAR(7) PRIMARY KEY, long_url TEXT NOT NULL, created_at TIMESTAMP DEFAULT NOW(), click_count BIGINT DEFAULT 0, user_id BIGINT NULL ); CREATE INDEX idx_user_id ON urls(user_id); ``` For 6B rows: sharded relational DB OR NoSQL. - **Postgres sharded by hash(short_code)**: works. - **DynamoDB**: scales horizontally; perfect for KV access pattern. - **Cassandra**: also fits. Choose by team familiarity; DynamoDB is the cleanest fit for the access pattern. ## Step 6: Cache Redis caches `short_code → long_url`: - 4000 reads/sec average; 80% hit rate → 800 DB reads/sec (manageable). - TTL: a day or week; popular URLs stay cached. - LRU eviction. Working set: top 10% of URLs likely account for 90% of traffic. 600M URLs × 500 bytes / 10 = 30GB cache. Doable with Redis Cluster. ## Step 7: Redirect flow ``` GET /aB3xY9z → Web service → Cache.get("aB3xY9z") → hit: return 301 → Cache miss: DB.get("aB3xY9z") → Cache.set("aB3xY9z", long_url, ttl=86400) → Return 301 to long_url → Async: increment click_count (write to queue, batch update) ``` 301 (Permanent Redirect) preferred over 302 (Temporary) for SEO and caching by browsers. ## Step 8: Analytics (click counts) Naive: increment counter on every redirect → write-heavy bottleneck. Better: - Web service writes click event to Kafka. - Worker batches and updates DB every minute or hour. - Or use a separate analytics DB (ClickHouse). For real-time click counts: Redis counter that periodically syncs to DB. ## Step 9: Custom slugs User picks "my-cool-link" instead of auto-generated. - Check uniqueness: `SELECT 1 FROM urls WHERE short_code = ?`. - If unique, insert with that code. - Length constraint: 3-20 chars. ## Step 10: Scaling Bottlenecks as traffic grows: - **DB writes**: sharding + async batched analytics. - **Cache misses**: tune TTL; bigger cache cluster. - **Hot keys**: a viral URL gets 10K req/sec on one cache key. Solutions: replicate the hot key across multiple cache nodes; CDN cache the redirect response. ## Common follow-up questions - **What if a URL is malicious?** Blacklist; integrate with Google SafeBrowsing. - **Expiration?** Add `expires_at` column; periodic cleanup job. - **Authorization on custom slugs?** Reserve some keywords; rate-limit creations per user. - **A/B testing on URLs?** Add `variant` field; redirect based on coin flip. ## Self-rubric - [ ] Clarified requirements (read:write ratio, custom slugs, etc.) - [ ] Estimated capacity (storage, QPS) - [ ] Designed sho