system-design

Design a URL Shortener (TinyURL / bit.ly)

Difficulty: Tier 1 (warm-up) Asked at: Almost everywhere — Tkxel, Systems Ltd, Careem, Amazon, Google phone screens Time budget: 45 min

The classic first system design question. It looks trivial (“it’s just a hash map”) and that’s the trap: the interviewer is watching whether you clarify, estimate, and reason about a read-heavy system at scale — not whether you can shorten a string. Master this one and you have the shape of every design round.

Prerequisites: The Framework, Caching, Unique ID Generation

1. Requirements

Always start here. Ask, don’t assume.

Functional:

Non-functional:

Out of scope (state this explicitly): click analytics (assume a separate pipeline consumes redirect logs), user accounts/auth, spam/malware detection (mention it exists in the real world).

🎙️ “Before I design — is analytics in scope, or does a separate system handle it? And do we need custom aliases?” Clarifying scope up front is the single highest-value move in this round.

2. Back-of-the-envelope estimation

Assume 100 million new URLs / month.

Key-space check: how many characters does the code need?

🚨 The numbers tell the whole story: writes are easy, reads need a cache, storage is modest, 7-char codes suffice. Every design decision below follows from these numbers.

3. API design

POST /urls
  body: { longUrl, customAlias?, expiresAt? }
  → 201 { shortUrl: "https://sho.rt/aB3xK9p" }

GET /{shortCode}
  → 301 Moved Permanently, Location: <longUrl>
  (or 302 if you want redirects to hit your server each time — see deep dive)

DELETE /urls/{shortCode}   (optional, if users manage links)

301 vs 302: 301 (permanent) lets browsers/CDNs cache the redirect → fewer hits to your server, but you lose per-click tracking. 302 (temporary) means every click hits you → good for analytics, more load. 🚨 This is a trade-off the interviewer will probe — state it explicitly.

4. Data model

A single table/collection keyed by the short code:

Field Type Notes
short_code string (PK) 7 chars, base-62
long_url string the destination
created_at timestamp  
expires_at timestamp? optional
creator_id string? if accounts exist

Access pattern is purely key → value (short_code → long_url). This is a textbook key-value / NoSQL use case — no joins, no complex queries. A relational DB works too, but the access pattern doesn’t need it.

5. High-level design

flowchart LR
    Client -->|POST /urls| LB[Load Balancer]
    Client -->|GET /code| LB
    LB --> App1[App Server]
    LB --> App2[App Server]
    App1 --> Cache[(Cache<br/>Redis)]
    App2 --> Cache
    Cache -.miss.-> DB[(Key-Value Store<br/>sharded on code)]
    App1 --> IDGen[ID / code generator]

Write path: app server generates a code (§6), writes code → longUrl to the DB, returns the short URL.

Read path: app server checks the cache; on hit, return the redirect immediately; on miss, read the DB, populate the cache, return the redirect. 🚨 The cache is the load-bearing decision — it absorbs the 20K reads/sec so the DB stays quiet.

App servers are stateless → scale horizontally behind the load balancer.

6. Deep dives

6a. How do you generate the short code?

Three approaches — know all three and the trade-offs:

Approach How Pro Con
Hash + truncate MD5/SHA the long URL, take 7 base-62 chars Stateless, deterministic Collisions — must check-and-retry; same URL → same code (may be undesirable)
Counter + base-62 Global auto-increment, encode the number No collisions ever Counter is a bottleneck; codes are sequential/guessable
Counter with ranges ⭐ Each app server grabs a block of IDs (e.g. 1,000) from a central allocator, hands them out locally No collisions, no per-write bottleneck Codes still roughly sequential; small gaps if a server dies

Recommended: counter-with-ranges (like a distributed ID generator / Snowflake-style or a Zookeeper/DB range allocator). No collisions, no bottleneck. If guessability matters, XOR/permute the counter before encoding so codes aren’t obviously sequential.

Custom aliases: check the code isn’t taken (a single DB read on the PK); if free, insert; if taken, return a 409. Store alongside the same table.

6b. Scaling the read path

At 20K reads/sec, the DB alone would strain. The cache does the heavy lifting:

6c. Scaling storage

6 billion rows / 3 TB. Shard the key-value store on short_code (consistent hashing so adding nodes doesn’t reshuffle everything → Consistent Hashing). Each lookup is O(1) on the PK. This scales horizontally to any size.

6d. Availability & failure

7. Bottlenecks & scaling further

  1. DB read load → cache (done). Then read replicas. Then shard.
  2. Code generator bottleneck → range-based allocation removes the single counter.
  3. Hot key → key replication / CDN / in-process cache.
  4. Global latency → CDN + multi-region read replicas; a 301 can even be served from the CDN edge.
  5. Storage growth → shard on code; expire old links to reclaim space.

8. Trade-off summary

Decision Chosen Alternative Why
Consistency Availability (AP) Strong consistency A dead redirect is worse than a slightly stale one
Code generation Counter + ranges Hash+truncate / single counter No collisions, no bottleneck
Storage Sharded key-value store Relational Access is pure key → value
Redirect 301 (cacheable) 302 (trackable) Fewer server hits; analytics via async logs
Read scaling Cache-first DB replicas only Read-heavy → cache gives the biggest win cheapest

9. Follow-up questions an interviewer may ask

How do you prevent two users from getting the same code? With range-based counter generation, codes are globally unique by construction — each server hands out numbers from a disjoint block, so no two codes ever collide. With hash-and-truncate you'd need a conditional insert (insert only if the code doesn't exist; on conflict, append a salt and retry). The range approach avoids the read-before-write entirely, which is why it's preferred at scale.
How do you handle analytics (click counts) without slowing redirects? Don't do it synchronously on the redirect path — that would add latency and coupling. Instead, emit an event (short_code, timestamp, referrer, geo) to a message queue / log stream (Kafka) *asynchronously* as a fire-and-forget after issuing the redirect, and have a separate consumer aggregate counts into an analytics store. This keeps the redirect fast and decouples analytics failures from the core service. Note the 301- vs-302 tension: 301 lets browsers cache the redirect, so you *miss* some clicks; if accurate analytics matter, use 302 so every click hits you (at the cost of more load).
What if someone shortens a malicious URL? Real shorteners run destination URLs against a safe-browsing/malware blocklist (e.g. Google Safe Browsing) at creation time and periodically re-scan. You can also rate-limit creation per user/IP to curb abuse, and support takedown of reported links. This is out of scope for the core design but worth naming to show real-world awareness.
How would you support link expiration efficiently? Store `expires_at` on the record. On read, check it and return 404/410 if expired (lazy expiration). Physically reclaim space with a background job (or a TTL feature of the store, e.g. Redis/DynamoDB TTL) that deletes expired rows. Lazy-check-on-read guarantees correctness even if the cleanup job lags.
Why not just use a hash map in memory? 3 TB over 5 years doesn't fit in one machine's memory, and an in-memory-only store loses everything on restart. You need durable, sharded storage. The cache *is* effectively an in-memory hash map — but it's a front for a durable, horizontally-scalable backing store, not a replacement for it.

10. What junior / mid / senior answers look like

Further reading

This site is open source. Improve this page.