Design: a URL shortener, one machine

Problem & API Contract

A URL shortening service (like TinyURL or Bitly) converts a long URL into an alias of around 7 characters. When accessed, the short URL issues an HTTP 301 (Permanent) or HTTP 302 (Found) redirect to the original destination URL.

URL Encoding Strategies

flowchart LR LongURL["Original Long URL"] --> Method{"Encoding Strategy"} Method --> Hash["MD5 / SHA256 Hash + Truncate"] Method --> Counter["Monotonic Auto-Increment Counter + Base62"] Hash --> Collision["Collision Handling: Probe / Salt"] Counter --> Safe["Zero Collision Guarantee"]

Base62 vs. MD5 Hash Truncation

MD5 / SHA256 with Truncation: Hashing the URL yields a 128-bit (MD5) or 256-bit (SHA-256) digest, shown as 32 or 64 hex characters. Taking the first 7 characters introduces hash collision risks (the Birthday Paradox). Handling collisions requires checking the database on every insert and appending a salt if a collision occurs.
Monotonic Counter with Base62 (Recommended): Using characters [0-9, a-z, A-Z] (62 distinct characters), a 7-character string supports 62⁷ approx 3.52 trillion unique URLs. An incremental integer ID converted to Base62 guarantees zero collisions without database lookups (it fits in 7 characters while the ID stays below 62⁷; a full 64-bit value needs 11):
```
function toBase62(num) {
  const chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let str = "";
  while (num > 0n) {
    str = chars[Number(num % 62n)] + str;
    num = num / 62n;
  }
  return str || "0";
}
```

HTTP 301 vs. HTTP 302 Redirects

301 communicates a permanent redirect and is commonly cached; 302 communicates a temporary redirect but may also be cached when response headers permit it. Neither status alone guarantees whether every later navigation reaches the origin. Set explicit Cache-Control policy for the product's mutability and analytics needs, and distinguish origin request logs from CDN or edge logs.

Worked example: does it fit on one machine?

Writes: 1 million new links per day is about 12 per second on average, perhaps 100 per second at peak.
Reads: 100 million redirects per day is about 1,160 per second on average, perhaps 5,000 per second at peak.
Storage: about 500 bytes per row (code, URL, owner, timestamps) x 365 million rows per year is about 180 GB per year, which a single PostgreSQL instance on NVMe handles easily.
Hot set: if 20% of the links created in the last month receive most clicks, that is 6 million rows x 500 B = 3 GB. It fits in the database buffer cache, or in a local LRU cache inside the application.

Conclusion: one primary database, a read replica for failover and one or two stateless app servers are enough. Scaling out (next unit) becomes necessary at 100x this load.

Code generation options

Approach	Collisions	Guessable?	Coordination	Notes
Base62(auto-increment ID)	None	Yes, sequential	The database sequence	Short (a 7-character code covers 62^7, about 3.5 trillion)
Base62(permute(ID))	None (the permutation is one-to-one)	Not easily	The database sequence	For example a small Feistel network or multiplication by an odd constant modulo 62^7
Random 7 characters + unique insert	Rare; retry on conflict	No	None beyond a unique index	With 100 million codes in use, the chance a new code collides is 100M / 3.5T, about 0.003%
Hash(URL) truncated	Possible (birthday bound)	No	A unique index	Same URL gives the same code, which you may or may not want. Salt and retry on collision

Redirect status codes

Code	Meaning	Browser caching	Method preserved?
301	Moved permanently	Cached aggressively unless headers say otherwise	May change POST to GET
302	Found (temporary)	Only if Cache-Control or Expires allow it	May change POST to GET
307 / 308	Temporary / permanent	Same as 302 / 301	Yes

Bitly returns 301 with short cache lifetimes. Whichever code you choose, set explicit Cache-Control so the behaviour is deliberate rather than dependent on browser defaults.

More videos on this topic