The problem
Design a service like TinyURL or bit.ly: users submit a long URL and get a short one such as sho.rt/g9Xk2Pq; visiting the short URL redirects to the original. It’s the most common warm-up design question because it touches estimation, ID generation, storage, caching and scale.
1. Requirements
Functional
- Create a short link for a long URL (optionally with a custom alias and an expiry).
- Redirect a short link to its long URL.
- Basic click analytics (count per link).
Non-functional
- 100M new links per day; reads 100x writes.
- Redirect latency p99 under 50 ms worldwide.
- Redirects highly available (99.99%); a link once created must never be lost.
- Short codes shouldn’t be easily guessable in sequence (nice to have).
2. Estimates
From lesson 2: ~1.2k writes/s, ~115k reads/s average, ~350k at peak, ~91 TB over five years before replication. Code length: 62^7 ≈ 3.5 trillion, comfortably more than the ~180 billion links we’d create in five years, so 7 base62 characters.
3. API and data model
POST /v1/links {long_url, alias?, expires_at?} -> 201 {code, short_url}
GET /{code} -> 301 or 302, Location: long_url
links(code PK, long_url, owner_id, created_at, expires_at)
301 or 302? A 301 (permanent) lets browsers cache the redirect, cutting load, but you stop seeing repeat clicks. A 302 (temporary) sends every click through you, which analytics needs. Most shorteners use 302 (or 307).
4. Generating short codes
This is the heart of the problem. Options:
a) Hash the URL (MD5/SHA, take 7 base62 characters). Same URL gives the same code (free dedup), but truncated hashes collide; you must check the database and retry with a salt, which adds a read to every write.
b) Random 7-character code, check for collision, retry. Simple, unguessable; collision checks are cheap while the space is mostly empty (180B of 3.5T is ~5% full after five years).
c) Unique counter → base62. Every link gets a unique integer id, encoded in base62. No collisions ever. The challenge is generating unique ids across many servers without a bottleneck. A clean solution is range leasing: a coordinator (a database row or etcd) hands each app server a block of 1,000 ids; the server mints codes locally until the block runs out.
"""Short codes for a URL shortener: base62 of a unique numeric id."""
import string
ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase # 62 chars
def encode(n: int) -> str:
if n == 0:
return ALPHABET[0]
out = []
while n:
n, rem = divmod(n, 62)
out.append(ALPHABET[rem])
return "".join(reversed(out))
def decode(code: str) -> int:
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
class IdRangeAllocator:
"""Each app server leases a block of ids so it can mint codes without coordination."""
def __init__(self, block_size=1000):
self.next_block_start = 1 # in production this counter lives in a database or ZooKeeper/etcd
self.block_size = block_size
def lease(self):
start = self.next_block_start
self.next_block_start += self.block_size
return iter(range(start, start + self.block_size))
if __name__ == "__main__":
print("7 chars of base62 cover", f"{62 ** 7:,}", "codes")
allocator = IdRangeAllocator()
server_a, server_b = allocator.lease(), allocator.lease()
for server, ids in (("A", server_a), ("B", server_b)):
n = next(ids)
print(f"server {server}: id {n} -> {encode(n)}")
big = 3_521_614_606_207
print(big, "->", encode(big), "->", decode(encode(big)))
7 chars of base62 cover 3,521,614,606,208 codes
server A: id 1 -> 1
server B: id 1001 -> g9
3521614606207 -> ZZZZZZZ -> 3521614606207
Sequential ids produce guessable codes. If that matters, scramble the id with a reversible permutation (e.g. multiply by a large odd number modulo 62^7, or a small block cipher) before encoding, or use option (b).
Custom aliases simply attempt an insert with the alias as primary key; a unique-key violation returns 409 Conflict.
5. High-level design
+--------------------- CDN / edge (optional) ---------------------+
client --> GeoDNS --> load balancer --> stateless app servers --> cache (Redis cluster)
| | miss
| v
+--> id-range service KV store (sharded by code)
+--> click events --> queue --> analytics workers --> OLAP store
Redirect path: look up code in the cache; on a miss read the store and fill the cache (cache-aside, lesson 4). Popular links are read millions of times, so the hit ratio is very high. Then return 302 and publish a click event asynchronously so analytics never slows the redirect.
Create path: validate the URL, take the next id from the local block, encode, write to the store, return the code.
6. Storage
Access is a pure key lookup by code and the data is huge, so a distributed key-value or wide-column store (DynamoDB, Cassandra) sharded by code fits well. A sharded relational database also works. Replicate 3x across zones for durability. Expired links are filtered on read and removed by a background job.
7. Deep dives
- Hot links: a viral link could overload one cache shard; keep a small in-process LRU on app servers for the hottest codes.
- Multi-region: replicate the store to several regions; redirects are reads, so each region serves locally. Writes go to the region that owns the id block, so ids never collide.
- Abuse: rate-limit creation per user/IP (next lesson) and check URLs against malware lists.
- Analytics at scale: aggregate clicks per minute in the stream processor before writing, rather than one database write per click.
Key takeaways
- 7 base62 characters cover trillions of links; estimates justify caching and sharding.
- Counter + base62 with leased id ranges avoids collisions without a central bottleneck; random codes trade a collision check for unguessability.
- Redirects are a cache-heavy key lookup; send analytics through a queue so it never slows the redirect.
- Use 302 if you need click analytics; 301 if you want to minimise load.
Exercises
- Implement a reversible scrambler so consecutive ids produce unrelated-looking codes, and verify you can decode back.
- Estimate the cache size needed to hold the hottest 20% of links created in the last month.
- Extend the design to let users edit where a link points. What changes in caching?
Quiz
- Why might a URL shortener return 302 instead of 301?
- What’s the main drawback of truncating a hash of the URL to make the code?
- How does range leasing avoid a bottleneck on id generation?
Show answers
- With 302 every click passes through the service, so it can count clicks and change destinations; 301 gets cached by browsers.
- Truncated hashes can collide, so every write must check for an existing code and retry.
- Each server gets a block of ids at once and allocates locally; the coordinator is contacted only once per block.