Design a URL Shortener

• 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.

• 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.

• 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.

• 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.

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.
   1. Browser requests the short URL.
   2. Edge function looks up the code in the edge KV.
   3. On a miss, the edge calls the regional redirect service, which checks its cache and then the mapping store.
   4. Edge returns the redirect with cache headers chosen by policy.
   5. Edge emits a click event to the stream without waiting.
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.
   1. Owner submits a long URL, optionally a custom alias and expiry.
   2. API validates the URL and checks the destination against the block list and safe-browsing.
   3. API obtains a code: a custom alias is reserved with a conditional write; otherwise the key generator supplies the next code from its range.
   4. Mapping is written with put-if-absent; the write fails only for a custom alias already taken.
   5. API warms the regional cache and the edge KV so the first click is already a hit.
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.
   1. Owner changes the destination or disables the link.
   2. API updates the mapping store and bumps a version.
   3. API invalidates or overwrites the regional cache and edge KV entries.
   4. Time-based expiry is enforced at read time by every tier, not by a deletion job.
   5. Click-limit expiry is enforced by the analytics pipeline flipping a flag once the count is reached.
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.
   1. Clicks arrive at hundreds of CDN PoPs simultaneously.
   2. The first request at each PoP misses to the regional redirect service, which serves it from Redis.
   3. Click events flood the stream; the edge batches them and the topic is partitioned by code.
   4. Analytics aggregates per hour; the owner sees the spike within minutes.
   5. If the destination turns out to be malicious, the safety flag propagates through the same invalidation path and the edge serves an interstitial.
5. Click analytics without touching the redirect path — Approximate, delayed, and completely decoupled. Every decision here protects redirect latency.
   1. Edge workers buffer click events and ship them in batches.
   2. Stream job aggregates per code per hour by dimension and maintains running totals.
   3. Aggregates are written to the analytics store; raw events go to cold storage.
   4. Owner opens the dashboard; queries hit the analytics store only.
   5. Running totals feed click-limit expiry back to the mapping store.

Ask: Hash the URL, random string, or counter? How do you get unique, short, unguessable codes with no hot spot?

Good answers name: Ranged counter + bijective scramble + base62, Random 7-char code with retry on collision, Hash of the URL, Base62 of a global auto-increment.

Our pick: A Key Generation Service that claims ranges of 10 000 from a strongly consistent counter (Postgres sequence, ZooKeeper, or a DynamoDB atomic counter) and hands out codes as base62(scramble(n)) where scramble is a bijection on [0, 62^7) such as multiplication by a large odd constant modulo 62^7 with a secret offset. Codes are 7 characters, unique by construction, and non-sequential. Custom aliases bypass the generator and are reserved with a conditional write. Reserve a block of the space so aliases and generated codes cannot collide (for example, generated codes never start with a digit). For private links, append or mix in random bits.

1. A KGS instance crashes with 8 000 unused ids in its range. Problem?
   No. The ids are simply never used; the space is 3.5 trillion. Gaps have no cost. The only rule is that a range is never handed out twice, which the atomic increment guarantees.
2. How would you make codes truly unguessable rather than just non-sequential?
   Use a keyed permutation: a small-block cipher (a Feistel network over 42 bits with a secret key) instead of a public multiply-mod. Then the sequence cannot be reversed without the key. Or generate random codes and pay the conditional-write check. Say which threat you are defending against; for public marketing links, non-sequential is enough.
3. Case sensitivity: is x7Kq2 the same as X7KQ2?
   Base62 is case sensitive, which is fine for browsers but bad for people reading a code off a poster. Options: keep base62 and accept it; or use a case-insensitive base32 alphabet without ambiguous characters (no 0/O, 1/l) at the cost of 8 characters instead of 7. Product decision; for typed links prefer the unambiguous alphabet.
4. Why not use the database's own unique constraint and just retry random codes?
   You can, and at 0.2 % occupancy collisions are rare. The counter approach avoids a round trip per attempt and gives deterministic latency, and matters more if you go shorter (6 chars) or if the space fills. It is also easier to reason about at 400 creates per second across many instances.

Ask: Which redirect status do you return, and how does that interact with analytics and edits?

Good answers name: 302 / 307 by default, short private cache, 301 as an owner option, 301 always, Meta refresh / JavaScript redirect page.

Our pick: 302 (or 307 to preserve method) with Cache-Control: private, max-age=60 so a browser hammering the same link within a minute does not re-request but everything else is counted, plus Referrer-Policy so the destination sees the referrer for its own analytics. Offer 301 as a per-link setting for customers who want SEO equity and accept that clicks and edits will not be tracked. Flagged links serve a 200 interstitial page instead of a redirect.

1. A link is 302 but the owner sees far fewer clicks than the destination's analytics. Why?
   Usually bots and prefetchers: link previews in chat apps, email scanners, and crawlers hit the short link and get counted, while destination analytics run JavaScript that bots do not execute. Or the reverse: browsers cached a 301 from a previous setting. Filter known bot user agents in the pipeline and report human and bot clicks separately.
2. How do you handle HEAD requests and link previews?
   Answer HEAD with the same status and Location and do not count it as a click, or count it separately. Preview bots often send HEAD or identify themselves; classify them so a message with a link shared to 50 people does not register 50 clicks before anyone taps.
3. What headers matter for security on the redirect?
   Never reflect user input into the response body; validate the scheme at creation so a javascript: URL cannot be stored; set Referrer-Policy deliberately; add HSTS on the short domain; and rate limit resolution of unknown codes to slow enumeration and typosquat scanning.

Ask: Edge KV, regional Redis, and the database: why three tiers, and how do edits not serve stale destinations for hours?

Good answers name: Edge KV + regional Redis + durable store; write-through on create; overwrite on edit; short TTLs; expiry checked at read, Regional cache only, no edge, Long TTLs everywhere for maximum hit rate.

Our pick: Three tiers with explicit contracts. Create: write the store, then write-through to regional Redis and edge KV. Redirect: edge KV hit serves; miss goes to regional service which fills from Redis or the store and writes back to the edge with a 1-hour TTL. Edit or disable: update the store, overwrite Redis and edge KV; propagation SLO 60 s, stated in the UI. Expiry: expires_at and flags travel with the mapping and are checked at every tier on read, so no invalidation is needed for them. Unknown codes are negatively cached for 10 seconds only. Monitor edge hit rate (target above 99 %), regional hit rate, and the 99th percentile edit propagation time measured by a canary.

1. A user creates a link and clicks it immediately from another continent, and gets a 404. Why, and fix?
   A negative cache entry at that PoP from a previous probe of the same code, or the edge KV write-through has not propagated there yet. Fixes: never negatively cache for more than a few seconds; on a miss, always consult the origin for codes created in the last minute (the origin knows creation time); and warm the edge on create in the creator's region at least.
2. How big does the edge KV need to be?
   The hot set: the top ~50 M links by recent traffic at ~500 B is 25 GB, replicated to every PoP. Edge KV products cap value sizes and total size; if the platform limit is lower, keep the very hot set at the edge (the top few million) and let the regional tier absorb the rest.
3. Would you put the whole mapping table at the edge instead of a cache?
   For 3 TB, no; edge stores are for tens of GB. But this is a real design point: some shorteners with smaller tables replicate the entire mapping set to every region and treat the database as the source of truth only, so redirects never miss. At this scale, a hot-set cache with a regional tier is the practical middle.

Ask: Six billion tiny rows, point lookups by code, global durability. SQL or key-value?

Good answers name: Managed key-value store partitioned by code, multi-region (DynamoDB global tables / Cassandra), Sharded relational database, Single relational database.

Our pick: A key-value table keyed by code with the URL, owner, timestamps, expiry, click limit, and flags; a second table (or global secondary index) keyed by owner with created-time sort for management pages. Multi-region replication for durability and local reads by the regional redirect services. Alias reservation is a conditional put; because cross-region replication is eventual, route all alias creations through one home region so two regions cannot both succeed. Generated codes are unique by construction, so they can be written in any region. Archive expired and deleted rows to cold storage after a retention period, keeping a tombstone so the code is not reused.

1. Should you ever reuse a code after its link expires?
   Not for a long time. Old QR codes and printed materials keep pointing at it, and reuse would send people to an unrelated destination. Keep a tombstone (410) for years. The key space is large enough that reuse buys nothing.
2. How do you list a user's 200 000 links quickly?
   From the owner index, sorted by creation time with cursor pagination, never by scanning the main table. For search within an owner's links (by destination host or title), stream link events into a search index; do not add that capability to the key-value store.
3. What is the consistency story between the store and the caches during a regional failover?
   The store is multi-region and the caches are per region, so a failed region's users are routed to another region whose caches warm quickly from the replicated store. Edits made in the last few seconds before the failure might not have replicated; they are re-applied when the region returns because the mapping carries a version. Redirects never see an inconsistent state worse than "slightly old destination".

Ask: Shorteners hide destinations, which is exactly what attackers want. How do you keep the service usable and not a phishing tool?

Good answers name: Layered: creation-time URL checks, periodic re-scan, per-user and per-IP creation limits, interstitial on suspicion, non-sequential codes, negative-cache and rate limit on unknown codes, Creation-time checks only, Require accounts and manual review for everything.

Our pick: At creation: normalise and validate the URL, block dangerous schemes and known bad hosts, check safe-browsing with a cached verdict, and apply rate limits (per account tier, per IP for anonymous). After creation: periodic re-check of destinations weighted by click volume, abuse reports, and a domain reputation score; flagged links serve an interstitial warning page with a click-through, or are disabled for confirmed malware. Destination edits re-trigger the checks. Codes are non-sequential, unknown codes are rate limited and briefly negatively cached, and private links can use longer random codes. Analytics per destination host help spot campaigns early.

1. A spammer creates 100 k links to the same host from rotating IPs. Detection?
   Aggregate creations by destination host per hour: a new host receiving thousands of new links from many creators is the signature. Automatically flag the host for review and interstitial its links. The rate limiter alone cannot catch distributed creation; the destination-side aggregate can.
2. Interstitial or hard block?
   Interstitial for suspicion (uncategorised new domain, reports), hard block for confirmed malware and phishing from safe-browsing or manual review. Interstitials preserve legitimate traffic when the classifier is unsure and give users the information to decide.
3. Does hiding the destination behind a short link have a legal or privacy angle?
   Yes: users may not know where they are going, so a preview endpoint (append + to the code, as bit.ly does) that shows the destination without redirecting is good practice. Analytics must avoid storing raw IPs and must offer owners and clickers the retention and deletion guarantees local law requires.