Design a URL shortening service similar to TinyURL or Bitly. The service accepts a long URL and returns a much shorter alias; when anyone visits the short alias, the service redirects them to the original long URL. Walk through both the **high-level architecture** and the **low-level design**, and be ready to justify your key-generation strategy and storage choices. ### Constraints & Assumptions - Read-heavy workload: assume roughly a **100:1 read:write ratio** (redirects vastly outnumber creations). - Scale assumption: about **500M new short URLs per month** (~200 writes/sec average); at 100:1 that is ~20,000 redirects/sec average, with peaks several times higher. - Short codes should be as short as practical (target ~7 characters) drawn from `[a-zA-Z0-9]` (base-62). - A short link, once created, must keep resolving to the same long URL for its lifetime. - Links may have an optional expiration; assume a long default TTL (e.g., a few years) unless the user sets one. - Redirects must be low-latency (target p99 < ~100 ms) and highly available — a redirect should essentially never return a 5xx. - Optional features to consider but not over-build: custom/vanity aliases and per-link click analytics. ### Clarifying Questions to Ask - What is the expected scale (new URLs per day, total stored) and the read:write ratio? - Do short links expire, and if so who controls the TTL? - Do we need custom/vanity aliases, and must generated codes be hard to guess (security/enumeration concern)? - What is the allowed character set and maximum length for a short code? - Do we need click analytics (counts, geo, referrer) on the redirect path? - What are the availability, latency, and consistency targets? ### Part 1 — High-Level Design Lay out the functional and non-functional requirements, do a back-of-the-envelope capacity estimation, define the public API, and sketch the high-level architecture — explicitly separating the **write (create)** path from the **read (redirect)** path. ```hint Where to start Split functional requirements (shorten, redirect, optional custom alias, optional expiry/analytics) from non-functional ones (low-latency reads, high availability, ~100:1 read-heavy). Derive storage size and QPS from the write rate, then multiply for reads. ``` ```hint Read path The redirect is the hot path. Put a cache (e.g., Redis) in front of the datastore and consider a CDN/edge layer, since a hot link can be read millions of times. Most of your traffic should never touch the database. ``` #### Clarifying Questions for this Part - Should redirects use **301 (permanent)** — browser/CDN-cacheable, cheaper, but you lose per-click analytics — or **302 (temporary)** so every click reaches your servers and can be counted? #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2 — Low-Level Design Design the short-code generation and the data model. Compare key-generation strategies, handle collisions and custom aliases, choose a storage engine with justification, and sketch the core classes/interfaces. ```hint Key generation Compare three approaches: (1) hash the long URL (MD5/SHA), base-62 encode, and truncate; (2) a global auto-increment counter encoded in base-62; (3) a pre-generated Key Generation Service (KGS) that hands out unused codes. Weigh collisions, predictability/enumeration, and coordination cost. ``` ```hint Sizing the code With a 62-character alphabet, how many characters do you need for your scale? The space is $62^n$ — work out the smallest $n$ that comfortably exceeds the total URLs you expect to store. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - How do you guarantee two concurrent creates never issue the same code? (KGS, DB unique constraint + retry, counter ranges per server.) - At this scale, how do you expire and garbage-collect old or expired links? - How would you add per-link click analytics without adding latency to the redirect path? - As the datastore outgrows one node, how do you shard/partition it, and how does that interact with your key scheme?