Design a URL Shortener

The service has two jobs. Given a long URL, it returns a short one such as https://tiny.example/zn9edcu. Given a short URL, it sends the browser to the original address. Everything else, such as custom aliases, expiry, and click analytics, is optional and should be negotiated with the interviewer before you design anything.

Clarify the shape of the traffic early because it drives every later choice. A typical framing is 100 million new URLs per day, a read-to-write ratio of about 10:1, codes made only of digits and letters, and records kept for ten years. Short codes should be as short as possible, must never collide, and must not be deleted or changed once issued, since links will be printed and shared in places you cannot edit.

Writes: 100,000,000 / 86,400 seconds is roughly 1,160 writes per second. With a 10:1 read ratio, redirects run at about 11,600 per second, and peaks may be two or three times higher. Over ten years the system stores 100M × 365 × 10 = 365 billion records.

If an average long URL plus metadata is about 100 bytes, storage is 365 × 10^9 × 100 bytes = 36.5 × 10^12 bytes, or about 36.5 TB. Double-check: 100M rows per day at 100 bytes is 10 GB per day; 10 GB × 3,650 days is 36.5 TB, which agrees. That fits in a sharded relational store or a key-value store; it is not an exotic amount of data. The read rate, not the storage, is what makes caching essential.

Two endpoints are enough. POST /api/v1/data/shorten takes a longUrl and returns the short URL. GET /api/v1/{shortUrl} looks up the code and answers with an HTTP redirect whose Location header holds the long URL.

The status code is a real trade-off. 301 Moved Permanently tells browsers the mapping never changes, so they cache it and later clicks skip your servers entirely. That cuts load and latency but blinds you to repeat clicks. 302 Found is treated as temporary, so every click comes back to the service, which costs more traffic but lets you count clicks, change destinations, and expire links. Choose 301 when cost dominates and 302 when analytics or control matter.

Conceptually the system is one big hash table from short code to long URL. In-memory maps do not survive restarts or scale past one machine, so the real store is a table with columns id, shortURL, and longURL, indexed on both URL columns so lookups in either direction are fast.

The code alphabet is [0-9, a-z, A-Z], which has 62 characters, so a code of length n can represent 62^n values. We need at least 365 billion. 62^6 is about 56.8 billion, which is too small, while 62^7 is about 3.52 trillion, comfortably above the target with roughly ten times headroom. Seven characters is therefore the minimum length that lasts ten years at this write rate.

Option one hashes the long URL with CRC32, MD5, or SHA-1 and keeps the first seven characters. Truncation makes collisions possible, so the service must check the database and, on a clash, append a predefined salt string and hash again until the code is free. Each write may need several reads. A Bloom filter in front of the database can answer 'definitely not used' quickly and cut down the checks. One upside is that the same long URL always hashes the same way, which deduplicates naturally.

Option two takes a globally unique integer from an ID generator (such as a Snowflake-style service) and converts it to base 62. With the alphabet ordered 0-9, then a-z (10–35), then A-Z (36–61), ID 1,000,000 becomes 4c92, because 4 × 62³ + 12 × 62² + 9 × 62 + 2 = 953,312 + 46,128 + 558 + 2 = 1,000,000, and digit 12 maps to c. Collisions cannot happen because IDs are unique, and no lookup is needed before the insert. The costs are that code length grows as IDs grow, and sequential IDs make the next code guessable, which can be a privacy or abuse problem.

Shortening with base 62: the server receives the long URL and first checks whether it is already stored; if so it returns the existing code, avoiding duplicates. Otherwise it fetches a new unique ID, converts it to base 62, and inserts the triple (id, shortURL, longURL). The response contains the short URL.

Redirecting dominates traffic, so it is designed around a cache. A load balancer forwards the GET to any stateless web server. The server looks up the code in a cache such as Redis; on a hit it returns the redirect immediately. On a miss it reads the database, fills the cache, and then redirects. If the code is unknown the user gets a 404. Because the mapping is immutable, cache invalidation is almost free, which is why hit rates can be very high.

The web tier is stateless, so it scales horizontally behind the load balancer. The database tier scales with read replicas for the read-heavy load and with sharding, typically by hash of the short code, once a single primary can no longer absorb the writes. Because each lookup is a point read on a single key, the data also fits naturally in a key-value store.

Real services add protection and insight. A rate limiter on the shorten endpoint keyed by IP or API key stops one client from exhausting the code space or flooding the system with spam links. Analytics such as click counts, referrers, and geography are gathered asynchronously, usually by having the redirect server emit an event to a queue instead of writing counters inline. Keep the redirect path short so the analytics pipeline can fail without breaking links.

Redirects must keep working even when parts of the system fail. Replicate the database, run the cache as a cluster so one node loss only reduces hit rate, and make the ID generator highly available, for example by giving each server a pre-allocated range of IDs so it can keep issuing codes during a coordinator outage. A cache stampede on a viral link is handled by request coalescing or by simply letting the first miss populate the entry.

In the interview, the strongest answers state the 62^7 arithmetic out loud, compare the two code-generation approaches honestly, and explain the 301 versus 302 choice in terms of the business goal rather than reciting definitions.