Design a URL Shortener (TinyURL / bit.ly)
The classic warm-up question. Deceptively simple functionally, and a perfect vehicle for ID generation, extreme read/write skew and cache design.
Covers: ID generation, base62 encoding, redirect path, read-heavy caching, custom aliases, analytics, expiry
This problem is asked constantly because it is small enough to finish and rich enough to probe. The features take two minutes; the interesting part is that reads outnumber writes by roughly 100:1 and the whole system is essentially a giant, globally distributed hash table with a redirect on top.
Requirements
| Type | Requirement |
|---|---|
| Functional | Shorten a long URL to a short code; redirect a short code to the original |
| Functional | Optional custom alias; optional expiry |
| Functional | Basic click analytics |
| Non-functional | 100 M new URLs/day; 100:1 read:write ratio |
| Non-functional | p99 redirect under 100 ms globally |
| Non-functional | 99.99% availability on the redirect path; shortening may be less available |
| Non-functional | Codes must not be guessable in sequence for private links |
| Out of scope | User accounts, teams, billing, link previews |
Back-of-envelope
- Writes: 100 M/day ÷ 86,400 ≈ 1,160/s average, ~3,500/s peak. Modest.
- Reads: 100× that ≈ 116,000/s average, ~350,000/s peak. This is the whole problem.
- Storage: 100 M/day × 500 B ≈ 50 GB/day ≈ 18 TB/year. Ten years ≈ 180 TB, so plan for sharding or a distributed KV store.
- Key space: base62 with 7 characters gives 62⁷ ≈ 3.5 trillion codes. At 100 M/day that is 96 years. Seven characters is the right answer.
URL shortener architecture
Note the asymmetry: the write path is ordinary, and the read path is a CDN plus cache designed to almost never touch the database.
Flow
- ClientCDN / edge
- CDN / edgeLoad balancer(miss)
- Load balancerApp servers
- App serversID allocator(on create)
- App serversRedis(read)
- RedisKey-value store(miss)
- App serversAnalytics queue(click event)
30-second answer
Hashing the URL and truncating produces collisions that you must detect and resolve, and it leaks that two users shortened the same link. A global counter encoded in base62 is collision-free and compact but produces sequential, guessable codes and needs a coordination point. The practical answer is a counter with per-host pre-allocated ranges, so each server allocates from memory with no coordination, combined with a bijective scramble of the integer before encoding so the output is not sequentially guessable. For private links, generate random codes and rely on a uniqueness constraint.
| Approach | Collisions | Guessable | Coordination | Verdict |
|---|---|---|---|---|
| MD5/SHA of URL, truncated | Yes - must check and retry | No | None | Extra read on every write |
| Global counter → base62 | None | Yes - sequential | Single allocator | Needs scrambling |
| Counter with per-host ranges | None | Yes unless scrambled | Rare - one call per 10k IDs | Best default |
| Random 7 chars + unique constraint | Rare, retry on conflict | No | None | Best for private links |
| Snowflake-style ID | None | Partly | None | Longer codes than needed |
BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n: int) -> str:
if n == 0:
return BASE62[0]
out = []
while n:
n, r = divmod(n, 62)
out.append(BASE62[r])
return "".join(reversed(out))
class RangeAllocator:
"""One coordination call per 10,000 IDs instead of one per request."""
def __init__(self, store, block=10_000):
self.store, self.block = store, block
self.next_id, self.limit = 0, 0
def next(self) -> int:
if self.next_id >= self.limit:
start = self.store.incr_by("url:counter", self.block) - self.block
self.next_id, self.limit = start, start + self.block
self.next_id += 1
return self.next_id - 1
# Sequential integers leak volume and let anyone enumerate every link.
# A modular multiplicative inverse scrambles them bijectively: no collisions,
# no lookup table, and the mapping is exactly reversible.
P = 2_147_483_647 # coprime with M
M = 62 ** 7 # 7-char base62 space
PINV = pow(P, -1, M) # modular inverse, for decoding
def to_code(seq: int) -> str: return encode((seq * P) % M).rjust(7, "0")
def to_seq(code: str) -> int: return (decode(code) * PINV) % MSay these points
- 7 base62 characters give 3.5 trillion codes - decades of headroom.
- Range-allocated counters remove per-request coordination.
- Scramble sequential IDs bijectively so codes are not enumerable.
- Random codes plus a uniqueness constraint for private links.
- Custom aliases require a conditional insert and a reserved-word list.
Avoid these mistakes
- A single global counter on the hot path.
- Sequential codes that let anyone enumerate every link in the system.
- Hash-and-truncate without a collision-resolution strategy.
- Read-then-write for custom alias uniqueness.
Expect these follow-ups
- How do you guarantee no two servers ever issue the same code?
- How would you support 100-character vanity URLs for enterprise customers?
- What happens when the ID space is finally exhausted?
30-second answer
Layer the reads: CDN at the edge, Redis in the region, then the key-value store. Link popularity follows a power law, so a few gigabytes of cache serves well over 95% of traffic and the database sees only a few thousand QPS. On the status code, 301 is permanent and cacheable by browsers and proxies, which makes redirects nearly free but means you stop seeing repeat clicks and can never change the destination. 302 is temporary and uncached, so every click reaches you - full analytics and editable destinations, at the cost of full traffic. Most commercial shorteners use 302 precisely because analytics is the product.
| 301 Permanent | 302 Found / 307 | |
|---|---|---|
| Browser caches it | Yes, often indefinitely | No |
| Subsequent clicks reach you | No | Yes |
| Analytics | First click only | Every click |
| Can change the destination later | Effectively no | Yes |
| Load on your system | Very low | Full |
| SEO link equity | Passes | Historically weaker |
The cache tiering
| Layer | Hit rate | Latency | Traffic reaching the next layer |
|---|---|---|---|
| CDN edge (301 only) | ~80% | 10–30 ms | 70,000/s |
| Redis, regional | ~95% of the rest | ~1 ms | 3,500/s |
| KV store | - | 5–10 ms | 3,500/s - comfortable |
Two cache layers turn 350,000 QPS into ~3,500 QPS at the database. Nothing exotic is required, only the layering.
def redirect(code):
url = redis.get(f"u:{code}")
if url is None:
url = kv.get(code) # sharded by code
# Cache the miss briefly too: scanners probe nonexistent codes constantly.
redis.setex(f"u:{code}", 3600 if url else 60, url or "")
if not url:
return 404
# Analytics must never block the redirect. Fire and forget.
queue.publish_nowait({
"code": code, "ts": time.time(),
"ref": request.headers.get("referer"),
"ua": request.headers.get("user-agent"),
"ip": anonymise(request.remote_addr), # truncate for GDPR
})
return redirect_response(url, status=302)Analytics without slowing the redirect
- Publish click events to a queue or log; never write to a database on the redirect path.
- Aggregate in a stream processor into per-minute and per-day rollups; keep raw events only briefly.
- For very high-cardinality questions like unique visitors, use HyperLogLog - approximate cardinality in about 12 KB per counter, with roughly 2% error, instead of storing every visitor ID.
- Anonymise or truncate IP addresses at ingest, not later. It is far easier to never store the data than to delete it correctly.
Say these points
- CDN + Redis + KV turns 350k QPS into ~3.5k QPS at the database.
- 301 is cacheable and kills analytics; 302 preserves analytics and costs full traffic.
- Cache negative lookups - scanners probe nonexistent codes constantly.
- Analytics is fire-and-forget, never on the redirect path.
- Guard against open-redirect abuse and redirect loops.
Avoid these mistakes
- Writing a click row to the database on every redirect.
- Choosing 301 while promising per-click analytics.
- No negative caching, leaving an easy path to hammer the database.
- Ignoring abuse: shorteners are a favourite phishing vector.
Expect these follow-ups
- A single link goes viral at 500,000 requests per second. What happens?
- How would you support link expiry without scanning the whole dataset?
- How do you count unique visitors per link without storing every visitor?
Showing 2 of 2 questions for design-a-url-shortener.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Build a working URL shortener
Implement the design end to end, at small scale but with every architectural decision from this lesson present.
Requirements
- Implement range-allocated IDs with a bijective scramble, and prove codes are non-sequential.
- Implement the redirect path with Redis caching including negative caching.
- Support custom aliases with a race-safe conditional insert and a reserved-word list.
- Publish click events asynchronously and aggregate them into per-day counts.
- Load test the redirect path and report cache hit rate and p99 latency.
Stretch goals
- Add link expiry using a TTL rather than a scanning job.
- Count unique visitors per link with HyperLogLog and compare accuracy against exact counting.