Design a URL shortener

  • Lesson 38 of 40
  • 14 min
  • Intermediate
  • 12 steps

You put the whole course together on a real case: a service that turns long URLs into short codes. You start from requirements and numbers, then grow it by fixing one bottleneck at a time.

Redirect time
5 ms
Store lookups
400 req/s
Short codes
scrambled
Links kept
6 TB × 3
people opening linksAPIserversShortenerAPIserversAPIserversAPI serverslinks tableIDsblocksIDsscraperCachecode → URLCachekey-value storeStreamclicksStreamclick countsRequirementscreatelong URL → short codeopenshort code → redirectredirectfast and always availablecreating a linkmay take a bit longerNapkin math200 M links / month≈ 80 writes/s× 50 opens each≈ 4,000 reads/sevening peak × 3≈ 12,000 reads/s5 years: 12 B links≈ 6 TBexample values, 500 bytes per linkThe APIPOST /links { url }→ { code }GET /{code}→ 302 + Locationtablecode PK · long_url · expires_atcode = 7 characters of hash(url)code taken → retryTwo URLs, one codehash("…/annual-report")→ Rk29fQa…hash("…/bread-recipe")→ Rk29fQa…same 7 characterscollisionon every writecheck, vary, retryexample codesblock 4,000,000 – 4,999,999Base 62alphabet0–9 a–z A–Z100→ 1C4,000,000→ gMA862^7≈ 3.5 trillion codesGET /gMA9, /gMAa…code = base62(shuffle(id))Same ids, new order4,000,000 → gMA8the next one is guessable4,000,001 → gMA9and so is the one after4,000,000 shuffled→ Qx7mT2p4,000,001 shuffled→ b0RkW9eexample shuffled codes90% hitsonly the misses: 10%302 FoundTwo kinds of redirect301 permanentthe browser keeps itless load, no counts or changes302 temporaryevery click comes backanalytics and control, more loadpartition = hash(code)3 copies in different zonesclick event, no waitingredirect: ~5 msPOST /links × 3,000/minrate limit · destination check429The finished designCodesshuffled counter, base 62unique with no checksReadscache + 30250 reads per writeDatakey-value by hashone key per lookup, 6 TBClicksevents on a streamoff the critical pathAbuselimits, checks, expiryprotects the domain
  • request
  • cache miss
  • event
  • batch
  • failed request

Step 1 of 12

Concept

The brief: a link shortener

Time to bring it all together, top-down as in HLD and LLD. The brief: a service where you paste a long URL and get a short one back, like example.link/Qx7mT2p. Whoever opens the short one lands on the original.

Before drawing boxes, define what working means. It must create short links and redirect. It should expire links and count clicks. And what matters most: redirects have to be fast and always available, because if the service goes down every link ever shared breaks. Creating a link, on the other hand, can take a little longer.

Step 2 of 12

Concept

Put numbers on it

Napkin math first (module 01), with example values. Assume 200 million new links a month: about 80 writes per second. If each link is opened about 50 times, that is about 4,000 redirects per second on average and close to 12,000 at peak.

Over five years that is 12 billion links. At about 500 bytes each, 6 TB. Two things stand out: the system is read-heavy (50 reads for every write) and there is a lot of data, but it is very simple.

What changed

  • 80 writes/s · 4,000 redirects/s · 12,000 at peak
  • 12 billion links ≈ 6 TB over 5 years

Step 3 of 12

Solution

The simplest thing that works

Two endpoints. POST /links stores a URL and returns a code; GET /{code} looks that code up and answers with a redirect.

One table is enough: code (primary key), long_url, created_at and expires_at. A few stateless API servers behind a load balancer, plus one database, make a perfectly good first version.

What changed

  • Stateless API servers
  • Links table keyed by the code

Step 4 of 12

Problem

Where do codes come from? Try a hash

First idea: hash the long URL and keep its first 7 characters. Nobody needs to coordinate, and the same URL always gives the same code.

But 7 characters can't hold a whole hash, so different URLs will end up sharing a code, and with billions of links that happens all the time. Every insert has to check whether the code already belongs to another URL and retry with a variation. On top of that, two people shortening the same URL get the same code, so neither can have their own expiry or their own statistics.

What changed

  • Code = first 7 characters of hash(url)
  • Collisions: check and retry on every insert

Step 5 of 12

Solution

Count, then encode

Better: give each link a unique number and write it in base 62, with digits, lowercase and uppercase letters. If the number going in is unique, the code coming out is unique too, with nothing to check.

Seven base-62 characters cover 62^7 ≈ 3.5 trillion links, about 290 times what you need. The numbers come from what you saw in Unique IDs at scale: each API server reserves a block of a million ids from a small counter service and uses it up locally.

What changed

  • Counter service handing out blocks of ids
  • Code = the id written in base 62
  • No more collision checks

Step 6 of 12

Problem

Case: codes you can walk through

Counter codes come out in order: gMA8, gMA9, gMAa. Anyone can walk the whole space and harvest every link ever created, including "private" documents and password reset links someone shortened.

The fix keeps uniqueness and drops the order. Either you shuffle each id with a reversible, key-dependent permutation before encoding it, or you pick 7 random characters and let the table's unique key reject the rare duplicate.

What changed

  • Sequential codes can be enumerated
  • Ids are shuffled before encoding
  • Codes look random and still never repeat

Step 7 of 12

Solution

Reads rule: cache them

Now the read path. A few links get most of the clicks (what is being shared today, not last year's) and a link never changes once created. That is the ideal case for a cache (see Caching).

Put an in-memory cache in front with code → long URL. In the example, about 90% of redirects are answered there in a millisecond and the store only gets the misses: from 4,000 down to 400 lookups per second. Since links don't change, there is almost nothing to invalidate: a TTL and LRU eviction are enough.

What changed

  • Cache: code → long URL
  • 90% of redirects never reach the store
  • Redirect from 25 ms to 5 ms (example values)

Step 8 of 12

Trade-off

Which redirect: 301 or 302?

301 Moved Permanently lets the browser keep the answer, so that person's next click never even reaches you. It is the cheapest request possible, but you can no longer count that click, change the destination or expire the link for them.

302 Found is temporary: every click comes back through you. More load, but you keep control and analytics. Most shorteners pick 302 and let the cache absorb the cost.

What changed

  • Decision: answer with 302 to keep analytics and control

Step 9 of 12

Solution

Six terabytes of keys: spread them

12 billion rows won't sit comfortably on one machine. But look at how they are used: every query is "give me this code". No joins, no ranges, no multi-row transactions.

That is exactly what a distributed key-value store is for (see SQL or NoSQL). Partition by a hash of the code so load spreads evenly (Sharding, Consistent hashing) and keep three copies of every partition in different zones (Replication). The scene shows four partitions.

What changed

  • One database → partitioned key-value store
  • 3 replicas of each partition, in different zones
  • Every redirect touches exactly one partition

Step 10 of 12

Technique

Counting clicks without slowing them

Product wants the click count of each link. The naive way, UPDATE links SET clicks = clicks + 1 on every redirect, turns 4,000 cheap reads per second into 4,000 writes, all on the hottest rows.

Instead, the API server drops a tiny click event onto a stream and answers the redirect right away. A consumer adds the events up per link every few seconds, in batches (see Message queues and Batch and stream processing).

What changed

  • Click events → stream
  • A consumer aggregates the counts in batches
  • The redirect is unchanged: still about 5 ms

Step 11 of 12

Problem

Case: spammers love shorteners

A short link hides where it goes, perfect for phishing. A script starts creating 3,000 links a minute pointing to fake bank pages. Soon your whole domain is on blocklists and every one of your users' links stops working.

Defend in layers. Limit link creation per account and per IP (Rate limiting), with 429 for the excess. Check every destination against phishing and malware lists when it is created and again later. And make links expire, so abandoned ones stop being a risk.

What changed

  • Rate limit on POST /links
  • Destination safety check
  • Links expire (TTL)

Step 12 of 12

Summary

The finished design

Codes: a shuffled counter written in base 62 gives unique codes with no checks and makes them hard to walk through.

Reads: a cache in front and 302, because there are 50 reads for every write and you want to keep analytics.

Data: a key-value store partitioned by a hash of the code, with three copies of each partition.

Clicks and abuse: events on a stream off the critical path, plus limits, destination checks and expiry to protect the domain.

Notice the method more than the answer: requirements → numbers → simple design → find the bottleneck → fix it → repeat.

You will learn

  • Go from a brief to requirements and numbers
  • Generate short codes that never repeat
  • Design the read path: cache and redirect type
  • Store billions of key → value pairs
  • Keep analytics and abuse off the critical path