URL shortener
Diagram
Changed in this tab
Requirements
What it does
- Create a short link for a long URL.
- Redirect a short link to the original.
- Support a custom alias and an expiry date.
How well it does it
- Redirect in under 100 ms.
- Serve about 100 reads for every write.
- Never lose a link.
- Keep short codes hard to guess in sequence.
Scale
| Assumption | Result | |
|---|---|---|
| New links | 100M a month | about 40 a second |
| Redirects | 100 for each new link | about 4,000 a second |
| Storage | 500 bytes a link, kept 5 years | about 3 TB |
| Short code | 7 characters of base62 | 3.5 trillion codes |
Key decisions
- A counter in base62, not a hash
- A global counter encoded in base62 never collides and keeps codes short. A hash needs a collision check on every write.
- Cache the hot links
- A small share of links gets most of the traffic. Redis answers those redirects without touching the store.
- A key-value store for links
- Every lookup is by short code and needs no joins, so a key-value store scales out more simply than a relational one.
- Redirect with 302 by default
- A temporary redirect sends every click through the service, so clicks can be counted. A 301 is cached by browsers: less load, but repeat visits become invisible.
Trade-offs
- A counter makes codes predictable. Shuffling the bits fixes that and makes the generator more complex.
- The cache can keep serving a link for a short time after it is deleted. A short expiry limits that window.
- One counter is a single point of failure. Handing each API server its own range of numbers removes it.