How do you design a high-throughput distributed URL Shortener (TinyURL) at scale?

Designing a URL Shortener (TinyURL/Bitly) is a classic system design interview question that tests end-to-end distributed system fundamentals: encoding, unique key generation, high read-to-write ratios, and cache sizing.\n\n### 1. Requirements & Quantitative Scale\n* Write Volume: 100 million URLs created/month = ~40 writes/sec (bursting to 500 writes/sec).\n* Read Volume: 100:1 read-to-write ratio = 10 billion clicks/month = ~4,000 reads/sec (bursting to 40,000 reads/sec).\n* Storage Calculation: 100M URLs * 500 bytes per record * 12 months * 5 years = 3 Terabytes total.\n\n### 2. Hash Encoding vs. Key Generation Service (KGS)\n* Naive MD5 / SHA-256: Hashing the long URL produces a 128-bit hash. Taking the first 7 characters causes frequent hash collisions when different users shorten the same destination.\n* Optimal Production Solution: Key Generation Service (KGS):\n 1. A standalone offline service pre-generates billions of unique 7-character strings using Base62 ([a-zA-Z0-9] where $62^7 \approx 3.52 \text{ trillion unique URLs}$).\n 2. The pre-generated keys are stored in a database in two states: UNASSIGNED and ASSIGNED.\n 3. Web servers fetch batches of 1,000 keys into memory at a time. When a shorten request arrives, the server instantly assigns an unused key with $O(1)$ latency and zero collision risk.\n\n### 3. Redirection Mechanics: 301 vs. 302 Redirect\n* 301 Moved Permanently: The browser permanently caches the redirect. Subsequent clicks bypass your servers and go directly to the destination. (Saves server bandwidth, but prevents click analytics tracking).\n* 302 Found (Temporary Redirect): The browser sends every subsequent click to your server before redirecting. Required in production to track user geography, referrers, and click timestamps.\n\n### Key Architectural Comparison\n| Component | Architecture Decision | Why Chosen |

| Database | Wide-Column NoSQL (Cassandra / DynamoDB) | 3 TB dataset easily partitioned by 7-char hash key with simple primary key point queries. |\n