Designing for Scale · URL Shortener

The problem this post solves

A URL shortener takes a long URL and returns a short alias, then takes that alias and redirects to the original URL.

At ten requests a second, this is a web framework tutorial backed by a single relational table. At ten thousand requests a second, it exposes the fundamental tension between generating unique identifiers concurrently and serving reads with absolute minimum latency.

This post tears down the toy version and builds the scaled version. It focuses on the single hardest part of the problem: how to generate a unique string without making every writer wait in line at a centralized counter.

First principles

Capacity and constraints

Assume a system writing 100 million new URLs per month (about 40 per second) and reading 10 billion URLs per month (about 4,000 per second). This is a read-heavy system with a 100:1 read/write ratio.

For the short URL, a 7-character string using base62 (A-Z, a-z, 0-9) provides $62^7$ combinations, which is roughly 3.5 trillion. This is enough capacity to run for thousands of years at the assumed write rate.

Architecture

The system splits cleanly into two paths: the read path (redirection) and the write path (generation).

The Read Path

The read path is trivial but its latency requirement is extreme. Users click short links expecting instant redirection; any delay here is perceived as network lag.

Because the read/write ratio is 100:1, and because a shortened URL's mapping is immutable, this is a perfect candidate for heavy caching.

When a user requests http://short.ly/aBcDeF:

1. The CDN checks if the 301 redirect for aBcDeF is cached at the edge. If yes, it responds instantly.
2. If not, the API server checks Redis. If found, it responds and updates the CDN.
3. If not, the API server queries the database, updates Redis, and responds.

The Write Path: Generating the Identifier

This is the actual engineering problem. We need to turn a long URL into a unique 7-character base62 string.

Approach 1: Hash and truncate. Take the MD5 or SHA256 hash of the long URL, encode it in base62, and take the first 7 characters. Problem: Collisions. Two different URLs might hash to the same first 7 characters. You have to check the DB, and if there's a collision, append a salt and re-hash. This requires a database read before every write. It is too slow.

Approach 2: Global Database Counter. Use a relational database with an auto-incrementing ID. Convert the base-10 ID to base62. ID 1000 becomes g8. Problem: The single database node handling the auto-increment becomes the availability and throughput bottleneck. You cannot easily shard an auto-incrementing sequence across multiple primary databases.

Approach 3: ZooKeeper / Distributed Token Service. Use a centralized coordination service (like ZooKeeper) to hand out blocks of IDs to the API servers.

The Scaled Architecture

When an API server receives a shorten request:

1. It takes the next available integer from its in-memory block (e.g., 1,000,042).
2. It converts 1,000,042 to base62.
3. It inserts (base62_string, long_url) into the database.
4. Because the block was uniquely assigned to this server, a collision is impossible. No read-before-write is required.

Failure modes

Using a random generator. Relying on randomness and checking the DB for collisions works fine at low scale but causes latency spikes and DB thrashing as the table grows and collisions become more frequent.

Not caching the 404s. If a malicious user requests millions of invalid short links, every request will miss the CDN, miss Redis, and hit the database. Caching the fact that a link does not exist (with a short TTL) protects the database from denial-of-service attacks.

What to carry forward