Design a URL Shortener

bit.ly at scale: turn long URLs into short codes, redirect in milliseconds from anywhere, count the clicks.

Difficulty: medium. Patterns: key-generation, caching, cdn, analytics. Reported at Amazon, Microsoft, Google, Adobe, Atlassian.

Study shows every answer; Practice hides them until you have produced your own.

Functional requirements

• Shorten a URL. Return a short code like sho.rt/x7Kq2. Optional custom alias and expiry.
• Redirect a short code to the original URL. HTTP 301 or 302 depending on whether clicks should be counted (302) or cached by browsers (301).
• Click analytics. Total clicks, clicks over time, referrer, country, device per link. Approximate counts are fine; the totals must not drift wildly.
• Link management. Owners can list, edit the destination, disable, or delete their links. Anonymous links are allowed with limits.
• Expiry. Links can expire at a time or after N clicks; expired codes return 410 Gone and are not reused for a long time.
• Abuse controls. Block known-malicious destinations, rate limit creation, and show an interstitial for suspicious links.
• Out of scope. QR code generation, branded domains per customer (mention how), and the full analytics dashboard UI.

Non-functional requirements

• Redirect latency (p99 < 50 ms globally). Redirects are served at the edge from cache. A redirect that goes to the origin database is the exception.
• Scale (100 M new links/month · 10 B redirects/month). Read to write ratio around 100:1. The write path is boring; the read path is a CDN problem.
• Availability (99.99 % for redirects). Links are embedded in emails, posters, and tweets for years. A redirect outage breaks the internet in small ways everywhere.
• Durability (no lost mappings). A short code that stops resolving is a broken link forever. Mappings are replicated across regions.
• Code length (7 characters). Base62, 62^7 ≈ 3.5 trillion codes. Short enough to type, large enough to never run out.
• Unpredictability. Sequential codes let anyone enumerate every link. Codes must not be guessable.
• Analytics freshness (minutes). Counts do not need to be real time; they must never block a redirect.

Back-of-envelope estimates

• Links created per second: ~40 avg · ~400 peak. 100 M/month ÷ 2.6 M s ≈ ~40/s. Peaks 10× during campaigns. A single database handles this trivially.
• Redirects per second: ~4 k avg · ~40 k peak. 10 B/month ÷ 2.6 M s ≈ ~3.9 k/s; viral spikes 10×+ on a single link. Served from CDN and cache; origin sees only misses.
• Total links after 5 years: ~6 B. 100 M/month × 60 months = 6 B mappings. 62^7 ≈ 3.5 T codes, so 7 characters uses under 0.2 % of the space and collisions are not a concern.
• Mapping storage: ~3 TB. Per link: code (7 B) + URL (~200 B avg, up to 2 KB) + owner, timestamps, flags (~50 B) + index overhead ≈ ~500 B. 6 B × 500 B = 3 TB. Fits a modest sharded store; a single node with SSDs could hold it, but not serve it globally.
• Cache hit rate needed: > 99 %. Redirect popularity is Zipfian: the top 1 % of links get ~90 % of clicks. A cache holding the hot ~50 M mappings (~25 GB) yields 99 %+ hits, so the origin sees ~40 misses/s average. The CDN edge in front of it catches most of that again.
• Click events per day: ~330 M. 10 B/month ÷ 30 = ~330 M events/day at ~200 B each (code, ts, referrer, UA hash, geo) ≈ 66 GB/day raw. Aggregate per link per hour and keep raw for 30 days.
• Key space check: 62^7 ≈ 3.5 T. 62 characters (a–z, A–Z, 0–9) to the power 7 = 3.52 × 10^12. At 100 M/month it would take 3 000 years to exhaust. Six characters (57 B) would last 47 years but is uncomfortably enumerable.

Components

• Browser / app: Follows short links (the read path) and, for owners, creates and manages links through the web app or API.
• CDN edge (edge cache + edge function): Terminates the redirect request close to the user. An edge function looks up the code in the edge KV cache and returns the redirect directly; on a miss it calls the redirect service. Also emits a click event to the analytics pipeline without waiting for it.
• Edge KV (replicated to PoPs): A globally replicated key-value store at the CDN (code → URL, flags, expiry). Populated on link creation and on misses; a few tens of GB covers the hot set everywhere.
• Redirect service: Origin for redirects: check the regional cache, then the mapping store; apply expiry, disabled, and safe-browsing flags; return 301/302/410. Stateless and replicated per region.
• Regional cache (Redis · code → mapping): Second cache tier per region, holding the hot tens of millions of mappings so the database only sees genuinely cold codes. Invalidated on edit and delete.
• Link API (create · manage): The write path: validate the URL, check the block list, allocate a code (or reserve the custom alias), write the mapping, warm caches, and return the short URL. Rate limited per user and IP.
• Key generation service (pre-generated ranges): Hands out unique, non-sequential 7-character codes without coordination on the hot path. Each API instance claims a range of counter values from the store and encodes them with a bijective scramble to base62.
• Mapping store (DynamoDB / Cassandra · key=code): code → { url, owner, created, expires, flags, click_limit }. Point lookups by code, so a key-value or wide-column store partitioned by code is ideal. Multi-region replication for durability and local reads. A secondary table indexes owner → codes for management pages.
• Range counter (small strongly consistent store): A single monotonic counter that hands out ranges of 10 000 ids atomically (ZooKeeper, a Postgres sequence, or DynamoDB atomic increment). Touched once per range, so its throughput is irrelevant.
• Click stream (Kafka): Click events from the edge and the redirect service, keyed by code. High volume, short retention. Feeds aggregation and raw archival.
• Analytics pipeline (stream aggregation): Aggregates clicks per code per hour by country, referrer, and device; maintains total click counts (also used to enforce click-limit expiry); writes raw events to cold storage.
• Analytics store (ClickHouse / warehouse): Hourly aggregates per code for dashboards, plus raw events for 30 days. Queried by owners, never by the redirect path.
• Safe-browsing checker (Google Safe Browsing · internal lists): Checked at creation and periodically re-checked for existing links. A flagged destination gets an interstitial warning or is disabled; the flag propagates through the caches.

User flows

1. Follow a short link. The path that runs ten billion times a month. Almost all of it happens at the CDN edge; the origin only sees cold codes.
2. Create a short link. Validate, allocate a code without a central hot spot, write once, warm the caches. Forty a second on average, which is easy; the design is about correctness and abuse.
3. Edit, disable, or expire a link. Mappings are cached in several tiers, so a change is an invalidation problem. The design accepts a bounded propagation delay and makes expiry checkable everywhere.
4. One link goes viral: 30 k clicks per second. A single hot key. The layered caches make it a non-event for the origin, and the analytics pipeline absorbs the burst through batching.
5. Click analytics without touching the redirect path. Approximate, delayed, and completely decoupled. Every decision here protects redirect latency.

Deep dives

1. Generating short codes. Hash the URL, random string, or counter? How do you get unique, short, unguessable codes with no hot spot?
2. 301 vs 302 and the caching contract. Which redirect status do you return, and how does that interact with analytics and edits?
3. Cache tiers and invalidation. Edge KV, regional Redis, and the database: why three tiers, and how do edits not serve stale destinations for hours?
4. Choosing the mapping store. Six billion tiny rows, point lookups by code, global durability. SQL or key-value?
5. Abuse: phishing, spam, and enumeration. Shorteners hide destinations, which is exactly what attackers want. How do you keep the service usable and not a phishing tool?