The canonical "small system, deep details" question. The architecture is simple on purpose — what is being tested is key generation, the read/write asymmetry, and estimation.
Requirements
Functional
- Shorten a long URL to a short one; redirect a short URL to the original.
- Optional custom aliases and expiry.
- Click analytics.
Non-functional
- Redirects must be fast — tens of milliseconds; this is the user-facing path.
- Highly available. A dead shortener breaks every link ever shared.
- Short keys are non-guessable enough that people cannot enumerate others' links.
Estimation
State the arithmetic; interviewers grade the method, not the numbers.
Writes: 100M new URLs/month ≈ 40 writes/second
Reads: 100:1 read/write ratio ≈ 4,000 reads/second
Storage: 100M/month × 5 years = 6B URLs
~500 bytes/record (long URL, key, owner, timestamps)
6B × 500B = 3 TB
Cache: 20% of daily reads ≈ 350M reads/day → hot set of a few GBTwo conclusions to state: it is overwhelmingly read-heavy, so caching matters more than anything; and 3 TB does not fit one machine comfortably, so plan for sharding.
Key length
base62 = [a-zA-Z0-9] = 62 characters
62^6 = 56 billion
62^7 = 3.5 trillionSix characters covers 6B URLs with room to spare. 7 is the safe answer — it gives three orders of magnitude of headroom for a single extra character.
Generating keys
Option 1 — hash the URL. MD5(long_url) truncated to 7 base62 characters. Simple and
stateless, but truncation collides, so every write needs a "does this key exist" check and a retry loop. Deterministic hashing does give free deduplication of identical URLs, which is a real benefit.
Option 2 — a counter, base62-encoded. No collisions by construction, and the encoding is
trivial:
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n):
out = []
while n:
n, rem = divmod(n, 62)
out.append(ALPHABET[rem])
return "".join(reversed(out)) or "0"The problem is the counter itself: a single global counter is a bottleneck and a single point of failure. The standard fix is ranged allocation — each application server leases a block (say 1,000 ids) from ZooKeeper or a database sequence, and hands them out locally. One coordination round trip per thousand URLs, no collisions, no hot counter.
Sequential ids are guessable, so if that matters, either XOR the counter with a secret before encoding, or use a random key with a uniqueness check. This trade-off — sequential and cheap versus random and private — is the discussion the question wants.
Option 3 — pre-generated keys. A separate service fills a table with random unused
keys; servers claim batches. Removes generation from the request path entirely, at the cost of another service.
Storage
A key-value store is the natural fit: every read is a point lookup by short key.
short_key (PK) | long_url | user_id | created_at | expires_atShard by short_key with consistent hashing. There are no range queries, no joins and no
transactions on the hot path, so DynamoDB, Cassandra or a sharded relational store all
work — this is a case where "SQL or NoSQL" genuinely does not matter much, and saying so
with a reason is better than picking dogmatically.
Analytics is a separate write path: appending a click row per redirect would double the write load on the serving store. Emit events to a queue such as Kafka and aggregate offline.
The read path
GET /aX9k2Bq
→ CDN / edge cache
→ application server
→ Redis cache (hit ~90%+ — URL popularity is heavily skewed)
→ key-value store
→ 301/302 redirectCache with LRU; the access pattern follows a power law, so a small cache covers most traffic. Entries are immutable once created, which is a caching gift — no invalidation problem beyond deletes and expiry.
301 versus 302
A genuine design decision with consequences:
- 301 Moved Permanently — the browser caches the redirect and stops asking. Minimal
server load, and you lose click analytics after the first visit.
- 302 Found — every click comes through your servers, so analytics are complete and the
destination can be changed later. More load.
Most shorteners choose 302 for exactly that reason. Say which you would pick and why.
Follow-ups to expect
- Custom aliases — same table, check uniqueness on write, reserve a namespace so they
cannot collide with generated keys.
- Expiry — a TTL column plus a background cleanup job; lazily delete on read as well.
- Rate limiting creation to stop spam and enumeration — see
- Analytics at scale — event stream into a columnar store, not row-per-click in the
serving database.
- Malicious URLs — check against a safe-browsing list on creation.
- Multi-region — reads are served from the nearest region; writes go to a primary or
use region-prefixed key ranges to avoid cross-region coordination.
Track this problem on the System Design sheet.
Frequently asked
How long should a short URL key be?
Seven base62 characters. 62^6 is 56 billion and 62^7 is 3.5 trillion, so at 100M URLs a month, six characters is enough for decades and seven gives three orders of magnitude of headroom for one extra byte.
Should I use a hash or a counter to generate short URLs?
A counter with base62 encoding avoids collisions entirely, but a single global counter is a bottleneck — so each server leases a block of ids from a coordination service and hands them out locally. Hashing is stateless and deduplicates identical URLs for free, but truncation collides, so every write needs an existence check and retry.
Should a URL shortener return 301 or 302?
- A 301 is cached by the browser, so subsequent clicks never reach your servers — which minimises load but destroys click analytics and prevents ever changing the destination. Most shorteners accept the extra traffic of a 302 to keep both.