Design a URL shortener

In 2 minutes

I would start by confirming the scale: tens of millions of links a month and about a hundred redirects per create, so the design is read-heavy. A client hits a load balancer that splits creates from redirects, so each side scales on its own. On create, an API instance takes a number from a block handed out by a small ID allocator, encodes it in base 62 to seven characters, scrambles it so the order is hidden, and stores code to long URL in a sharded key-value store with a unique key. Seven characters give 3.5 trillion codes, far more than the 3 billion links we expect. On a visit, the redirect service checks a cache first, falls back to the store on a miss, and answers with a 302, so every click is counted and edits and expiry work. Clicks go to a queue and are counted off the hot path. For safety I would check destinations against a blocklist, rate-limit creates, and make sure disabling a link also clears the cache. The main trade-off is 302 versus 301: 302 costs load but keeps analytics honest.

The question

Clarifying questions

• Can people pick their own alias, or are codes always generated? A chosen alias needs a uniqueness check on a string the user controls, which a plain counter does not give you.
• Do links expire, and can the owner delete one? Expiry adds a time field and a cleanup job, and a delete has to reach every cache that holds the link.
• Do we need click counts, and how fresh must they be? Counting every click pushes you towards a redirect the browser cannot cache, plus a separate event pipeline.
• Roughly how many links are created and followed each month? The read-to-write ratio decides whether the redirect path needs its own cache and its own servers.
• Should the same long URL always get the same short code? Deduplication adds a lookup to every create. Most products skip it and allow several codes per URL.

Requirements

Functional

• Create a short link for a long URL, with an optional custom alias.
• Redirect anyone who opens a short link to the long URL.
• Let the owner set an expiry date and delete a link.
• Show the owner a click count for each link.

Non-functional

• Redirect latency: p99 under 50 ms inside one region.
• Redirect availability of 99.99%, which is about 52 minutes of downtime a year.
• Create latency: p99 under 300 ms. Creates can be slower than redirects.
• Durability: no acknowledged link is ever lost.
• Codes are at most 7 characters and are never reused while a link is live.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real service.
• 50 million new links a month, and 100 redirects for every link created.
• Each stored link takes about 500 bytes: code, long URL, owner, dates and flags.
• Links are kept for 5 years, and the hottest 10 million links get most of the clicks.

The arithmetic:

• Creates per second: 50M a month ÷ (30 days × 86,400 s = 2.6M s) ≈ 19 → ≈ 20/s on average, about 200/s at a 10x peak
• Redirects per second: 100 × 20/s → ≈ 2,000/s on average, about 20,000/s at a 10x peak
• Links stored in 5 years: 50M × 12 months × 5 years → 3 billion links
• Storage: 3 billion × 500 bytes = 1,500 GB → ≈ 1.5 TB, which fits on a few shards
• Code length: 62^7 = 3.5 trillion codes, against 3 billion links → 7 characters is enough, and the space stays almost empty
• Hot cache: 10M links × 500 bytes → ≈ 5 GB, one cache node holds it

High-level design

A client sends every request to a load balancer. The balancer splits the traffic in two on the path: creates go to the Link API, and short-link visits go to the Redirect service. The two are separate so that a flood of redirects can never starve the create path, and each can scale on its own.

On a create, the Link API asks the ID allocator for a number. The allocator hands each API instance a block of numbers at a time, so most creates do not call it at all. The API writes the base-62 form of that number to the Link store, which maps a code to a long URL.

On a visit, the Redirect service looks in the Link cache first, because a small set of links gets most of the clicks. On a miss it reads the Link store and fills the cache for next time. It then answers with a redirect to the long URL.

How a request flows

Create a short link

1. The client sends the long URL, and an optional alias, to the load balancer.
2. The load balancer routes the create request to any Link API instance.
3. The API takes the next number from its block. Only when the block runs out does it ask the allocator for another.
4. The API writes the base-62 code and the long URL to the link store. A unique key on the code catches any clash.
5. The API returns the new short link to the load balancer.
6. The client receives the short link and can share it.

Follow a short link

1. A browser requests the short link, and the load balancer receives it.
2. The load balancer routes the visit to a Redirect service instance.
3. The service looks the code up in the cache. Hot codes are answered here in under a millisecond.
4. On a miss it reads the link store, then writes the answer into the cache for the next visit.
5. The service answers with a 302 redirect and the long URL in the Location header.
6. The load balancer passes the redirect back, and the browser jumps to the long URL.

Deep dive: generating short codes

A code is a number written in base 62: ten digits, 26 lowercase letters and 26 uppercase letters. Seven characters give 62^7, about 3.5 trillion codes. That is more than a thousand times the 3 billion links in our estimate, so seven is plenty.

There are two common ways to get a unique number.

1. A counter. Keep one global counter. Each create takes the next value and encodes it. Codes never collide, but one counter is a bottleneck and a single point of failure.
2. Hash and check. Hash the long URL plus a salt, keep the first seven base-62 characters and insert. If the code is taken, change the salt and retry. No coordination is needed, but every create reads before it writes, and clashes become more common as the table fills.

A counter scales if you hand out numbers in blocks. A small ID allocator holds the global counter in a strongly consistent store. Each API instance asks for a block, say 1,000 numbers, then serves creates from memory until the block is used up. Only one create in a thousand touches the allocator. If an instance crashes it loses the unused part of its block. That wastes a few numbers and nothing else, which is cheap when you have trillions.

A plain counter makes codes that run in order, so anyone can walk them and read every link. If that matters, scramble the number before encoding it. Multiplying by a large number that shares no factor with the code space, then taking the remainder, is a one-to-one mapping. Uniqueness is kept and the output looks random. This hides the order. It is not secrecy, so never put private data behind a short link.

In an interview, lead with blocks and say what they cost: a small extra service. Then name hashing as the simpler option and say what it costs: a read before every write.

Deep dive: the read path, and 301 versus 302

A redirect is one key lookup: a code goes in, a long URL comes out. Put a cache in front of the link store, keyed by code. Our estimate says the 10 million hottest links fit in about 5 GB. Use cache-aside. Look in the cache, on a miss read the store and write the answer back with a TTL, and evict the least recently used entries when memory fills.

Click traffic is skewed. A few links draw most of the visits, so a small cache gives a high hit rate. Cache the answer 'not found' for a few seconds too. Otherwise a scanner guessing random codes sends every guess to the database.

301 or 302? Both send the browser to the long URL. A 301 means moved permanently, and browsers and proxies may cache it. After the first visit, that browser can go straight to the long URL without calling you again. That saves load, but it hides repeat clicks, so your counts are too low. It also means you cannot edit or delete the link for anyone who already cached it. A 302 is not cached by default, so every click reaches your servers.

Pick 302 when you count clicks or allow edits and expiry. Pick 301 when load matters more and links never change. Most products that show analytics use 302.

Counting must not slow the redirect. Send the response first, then publish a click event (code, time, referrer) to a queue and let a separate worker add them up. If the queue is down, buffer a little or drop the event. Losing one click is better than failing a redirect.

Deep dive: custom aliases, expiry and abuse

Custom aliases share the code space with generated codes, so a clash is possible. A user asks for 'summer' and the counter later produces the same string. Put a unique constraint on the code column. A generated code that hits it simply takes the next number. An alias that hits it returns an error saying it is taken. Better still, give aliases a shape that generated codes never have, such as a hyphen or at least 8 characters, so the two can never meet.

Expiry is a column holding the end time. The redirect service checks it on every read and answers 410 Gone once it has passed. The cache TTL must never outlive the expiry, so set it to the smaller of the two. A background job deletes expired rows in batches, so reads never wait on cleanup. Do not reuse an expired code while any cache might still hold it.

Abuse is the real risk, because a short link hides its destination. Phishing and malware are the usual cases.

• Check each long URL on create against a blocklist and a reputation service.
• Rate-limit creates per account and per IP address, and require sign-in for aliases and bulk creation.
• Keep a fast way to disable a code. Disabling must delete the cache entry as well as set a flag in the store, or the link keeps working until its TTL runs out.
• Re-check popular links on a schedule, because a harmless page can turn bad after the link is made.

Trade-offs

• Short code generation: A counter handed out in ID blocks, then scrambled over Hash the long URL and retry on a clash. There are no collisions to handle and a create is one fast write. The cost is a small extra service and a scrambling step to hide the order.
• Redirect status: 302 (temporary) over 301 (permanent). Every click reaches our servers, so counts are right and edits and expiry work. The cost is more load, because the browser cannot cache the answer.
• Cache write policy: Cache-aside with LRU eviction over Write every new link to the cache on create. Only links that are really clicked use memory. The cost is that the first visit to a new link is always a miss.
• Storage layout: A key-value store, or a sharded table, keyed by code over One relational database with joins. Every lookup is by code, so sharding by code is simple and scales. The cost is that listing a user's links needs a second index.

Common follow-up questions

How would you stop one long URL from getting many codes?
Keep a second index from a hash of the long URL to its code, and check it on create. This costs an extra read on every create and a second index to store. It also clashes with per-user analytics and expiry, since two owners may want separate links. Most services skip it on purpose.

What happens if the ID allocator goes down?
Each API instance keeps serving creates from the block it already holds, so a short outage is invisible. Run the allocator on a replicated, strongly consistent store so that it recovers fast. A larger block size buys more time, at the price of wasting more numbers when an instance crashes.

How do you handle one link that suddenly goes viral?
That link becomes a hot key. Keep a very small in-process cache on each redirect instance with a TTL of a few seconds, so most visits never reach the shared cache. If you use 301 for such links, the browsers and a CDN absorb the load as well.

How do you scale the link store?
Shard by a hash of the code, so lookups go to one shard and creates spread evenly. Add replicas for reads and for failover. Because the data is only a few terabytes, you add shards slowly, and consistent hashing keeps the data movement small when you do.