Problem RestatementProblem
Design a service that turns a long URL like https://example.com/products/shoes?color=red&size=10 into a short one like https://sho.rt/aZ3kP9. When someone opens the short link, we send them to the original URL. Users can also pick a custom alias (sho.rt/summer-sale) and set an expiry date.
This is a read-heavy system. A link is created once but may be clicked millions of times, so redirects must be very fast.
RequirementsRequirements
1.1 Functional
- Create a short URL for a long URL.
- Redirect a short URL to the original.
- Optional: custom alias, expiry date, and click counts.
- Shortening the same URL twice (by the same user) returns the same code.
1.2 Non-Functional
- Low latency: redirect in under ~50 ms.
- High availability: broken links are very visible to users.
- Short codes should not be guessable in order (so people cannot list all links).
1.3 Scale Estimates
- 100 million new URLs per month ≈ 40 writes/sec.
- Read:write ratio 100:1 → 4,000 redirects/sec on average, peaks of 20K/sec.
- Over 5 years: 6 billion URLs × ~500 bytes ≈ 3 TB.
- Code length: base62 (a–z, A–Z, 0–9) with 7 characters gives 62^7 ≈ 3.5 trillion codes, which is plenty.
1.4 API Design
/v1/urlswith { long_url, custom_alias?, expires_at? } → { short_url }/{code}→ HTTP 301 or 302 redirect to the long URL./v1/urls/{code}/stats→ click counts.High-Level ArchitectureArchitecture
2.1 Overview
- Write service: validates the URL, generates a code, and saves the mapping.
- Redirect service: looks up the code (cache first, then DB) and returns the redirect.
- ID generator: hands out unique numbers that we convert to base62.
- Database: a key-value store (DynamoDB or Cassandra) keyed by code, which is ideal for simple lookups at huge scale.
- Cache (Redis): keeps popular codes in memory.
- Analytics pipeline: click events go to Kafka and are counted asynchronously, so redirects stay fast.
2.2 Architecture Diagram
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
U["User"] -->|"POST /urls"| WS["Write Service"]
WS --> IDG["ID Range Allocator"]
WS --> DB[("URL Store - code to long_url")]
V["Visitor"] -->|"GET /aZ3kP9"| RS["Redirect Service"]
RS --> C[("Redis Cache")]
RS -->|"cache miss"| DB
RS -->|"click event"| K[("Kafka")]
K --> AN["Click Counter"]Data ModelData model
Table: urls (key-value store, partition key = code)
code "aZ3kP9"
long_url "https://example.com/products/shoes?..."
user_id 42
created_at 2026-09-19
expires_at 2027-09-19 (optional)
Table: url_by_user_hash (to return the same code for a repeated URL)
key = hash(user_id + long_url) → codeGenerating Short Codes
This is the main discussion point.
Option 1 — Hash the URL (e.g., MD5, take the first 7 base62 characters). The same URL always gives the same code, which is nice. But two different URLs can produce the same 7 characters (a collision). Then we must check the DB and retry with a salt, which adds reads on every write. Option 2 — Counter + base62 (our choice). Give every new URL a unique number and convert it to base62. Number 125 becomes "21", for example. No collisions, ever. To avoid one central counter being a bottleneck or single point of failure:- An ID Range Allocator (backed by a small strongly consistent store like ZooKeeper or a DB row) hands each write server a block of 1 million numbers.
- Each server uses its block locally with no network calls, and asks for a new block when it runs out.
- If a server crashes, the unused part of its block is skipped. That is fine, since there are trillions of numbers.
Key FlowsFlows
5.1 Create
- Validate the URL (format, not on a malware blocklist).
- If the user shortened this exact URL before, return the existing code.
- Take the next number from the local block, scramble it, base62-encode it, and save it.
5.2 Redirect
- Look up the code in Redis. On a hit, redirect immediately.
- On a miss, read the DB, store the result in Redis with a TTL, then redirect.
- If the code is missing or expired, return 404.
- Send a click event to Kafka without waiting for it.
Deep Dive A — Handing out short codesDeep dive
Every new link needs a code no one else has. At 100M links a day, how that code is produced decides whether writes stay fast.
Pick random characters and check the database
Generate 7 random base62 characters, SELECT to see whether the code exists, insert it if not.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
sequenceDiagram
participant A as Writer A
participant B as Writer B
participant DB as Links table
A->>DB: SELECT where code = aZ3kP9
DB-->>A: not found
B->>DB: SELECT where code = aZ3kP9
DB-->>B: not found
A->>DB: INSERT aZ3kP9 - long URL 1
B->>DB: INSERT aZ3kP9 - long URL 2
Note over DB: one link silently overwrites the otherTwo writers can pass the same check. It also costs an extra read on every create, and as the table fills the retry loop runs more often.
Hash the long URL
Take an MD5 or SHA of the URL and keep the first 7 base62 characters. No coordination, and the same URL naturally maps to the same code.
Collisions still happen — different URLs, same prefix — so you still need the insert-if-absent check, and now the fallback (lengthen? rehash with a salt?) is fiddly. It also rules out custom aliases and makes expiry awkward, because the code is a property of the URL rather than of this particular link.
Hand each server a range of numbers
A small key-generation service owns a counter. A server asks for a block once — "you own 1,000,000 to 1,999,999" — and then hands out codes from that block in memory, base62-encoded, with no coordination at all.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
S1["API server 1"] -->|"claim a block"| KGS["Key service - counter in ZooKeeper or a DB row"]
S2["API server 2"] -->|"claim a block"| KGS
KGS --> B1["block 1,000,000 to 1,999,999"]
KGS --> B2["block 2,000,000 to 2,999,999"]
B1 --> C1["base62 encode - no collision possible"]
B2 --> C1Creates cost no extra read, codes are unique by construction, and a server crash only burns the rest of its block — cheap, since 62^7 is about 3.5 trillion codes. Custom aliases are inserted straight into the same table with a unique constraint, which is the one real collision check the system needs. Keep the database's unique index on code regardless: it is the safety net that makes every other layer optional rather than load-bearing.
Deep Dive B — 301 vs 302, caching and hot linksDeep dive
- 301 (permanent): browsers cache the redirect, so repeat visits never reach us. That means less load, but we cannot count those clicks.
- 302 (temporary): every click reaches us. Good for analytics. bit.ly-style products that sell analytics use 302.
- Hot links: a link in a viral tweet can get 50K clicks/sec. Redis handles this easily, and we can also cache at the CDN edge for a few seconds.
- Cache size: about 20% of links get 80% of clicks. Caching the top 20% of daily active codes (a few GB) gives a high hit rate.
- Expiry: check
expires_aton read, and run a daily cleanup job (or use a DB TTL feature) to delete old rows.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Code generation | Counter ranges + base62 | No collisions, no hot counter | Hash + collision check: simpler, extra reads |
| Storage | Key-value DB | Simple lookups, huge scale | SQL: fine at small scale, harder to shard |
| Redirect code | 302 | Accurate analytics | 301: less load, no click data |
| Analytics | Async via Kafka | Redirects stay fast | Synchronous counter update: slower, more fragile |
Common Follow-up QuestionsFollow-ups
- "How do you stop abuse?" Rate-limit link creation per user or IP, and check URLs against malware lists (like Google Safe Browsing) on creation and again periodically.
- "How do you go multi-region?" Give each region its own ID ranges so no coordination is needed, replicate the URL table to all regions, and serve redirects from the nearest one.
- "Why not just use a DB auto-increment?" One database becomes the bottleneck and a single point of failure. Ranges give the same result without that.
Wrap-UpWrap-up
Hand out unique numbers in blocks to each server, scramble and base62-encode them into 7-character codes, and store code → long_url in a key-value store. Serve redirects from a Redis cache with a DB fallback, push click events to Kafka asynchronously, and choose 302 when analytics matter.