URL shortener
A URL shortener maps a short key like sho.rt/3QdyUh to a long URL and redirects every click. It is a key-value store with a 100:1 read skew. The core decision is how to mint keys: hashing or random keys must be checked for collisions, while counter ranges handed out to each server and base62-encoded never collide and need one coordination call per thousand links. Redirects are an O(1) cache lookup; about 500 bytes per link means 100M links a day is roughly 90 TB over five years, and a cache holding a small slice of links absorbs most clicks.
The problem
Section titled “The problem”Short links exist because long URLs break in emails, look bad in posts, and can’t be counted. Bitly, TinyURL, t.co and goo.gl (now retired) all do the same two things: create a short key for a URL, and redirect anyone who visits the key. The business value is usually in a third thing: click analytics.
The goals pull against each other:
| Goal | What it means | Pulls toward |
|---|---|---|
| Short keys | 6-8 characters, easy to type | Small key space, so collisions and exhaustion matter |
| Unique and safe keys | Never hand out a key twice; don’t let people enumerate links | Coordination, or randomness plus checks |
| Fast redirects | Every click adds your latency to someone’s page load | Caching, no work on the hot path |
| Accurate analytics | Count every click with referrer and country | Not letting browsers cache the redirect (302, not 301) |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Create a short link for a long URL. Redirect a short key to its URL. Optional custom alias and expiry date. Click counts per link. | Do the same long URL and user get the same key back? Can links be edited or deleted? Are custom aliases a paid feature? |
| Scale | 100M new links/day, 100:1 reads to writes, 5 years retention. | Peak vs average? Is this a public service or an internal one (much smaller)? |
| Latency | Redirect under ~10 ms at p99 inside the data center. Create can take 100 ms. | Global users? Then the redirect should be served near them. |
| Consistency | A newly created link must work on the very next click (read-your-writes). Analytics can lag minutes. | Does an edit or delete need to take effect instantly everywhere? |
| Availability | Redirects must stay up; a dead redirect breaks someone else’s page. Creates can degrade first. | Is a stale redirect acceptable for a few minutes? |
| Out of scope | User accounts, billing, the analytics UI, QR codes. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Storage is large but easy (it is append-mostly and keyed). The number that forces design decisions is redirect QPS, which sets the cache and the click pipeline, and key-space use, which decides the key length.
What to say out loud: “About 1,200 creates a second and 230K redirects a second at peak. 7 base62 characters give 3.5 trillion keys, so five years uses 5% of the space. Storage is ~90 TB, so the store is sharded by key. The read path is a cache in front of that store.”
API and data model
Section titled “API and data model”Two endpoints. The redirect endpoint is the product; the create endpoint is admin.
POST /links { long_url, alias?, expires_at? } -> 201 { key, short_url } 409 if alias taken, 400 if URL invalidGET /{key} -> 302 Location: long_url 404 unknown, 410 expired or disabledGET /links/{key}/stats?from&to -> { clicks, by_day[], by_country[] }
Link (primary key: key) key string, 6-8 base62 chars, or a user alias long_url string, up to ~2 KB owner_id string? created_at timestamp expires_at timestamp? -- null = never disabled bool -- abuse takedown, without deletingTwo decisions hide in that sketch:
- Is create idempotent? If the same user shortens the same URL twice, return the existing key. That needs a secondary index on
(owner_id, hash(long_url)). Without it, retries create duplicate links, which is harmless but wastes keys. Hashing the URL to make the key gives this for free, which is its main attraction. - The key is the partition key. Every read is a point lookup by key, so any store that shards by key works: a wide-column store (Cassandra, DynamoDB), or sharded MySQL/Postgres. There are no joins and no range scans on the hot path. Pick on operations, not features.
High-level design
Section titled “High-level design”Step through each flow. The create path talks to the store; the redirect path should almost never need to.
| Component | Role | Why it’s there |
|---|---|---|
| Web tier (×N) | Stateless. Validates, mints keys from a local id range, serves redirects. | Scales horizontally; any node can serve any key. |
| Key allocator | Hands each web node a block of ids (e.g. 1,000) from one counter. | Unique keys with no per-create coordination. |
| Redirect cache | Key → record, LRU-evicted, sharded by key. | Clicks are skewed; a small cache absorbs most of them. |
| URL store | The source of truth, sharded by key, replicated 3×. | 90 TB does not fit on one machine; point reads only. |
| Click events | An append-only log (e.g. Kafka) partitioned by key. | Analytics at full redirect rate without slowing redirects. |
| URL scanner | Checks destinations against malware and phishing lists. | Shorteners are an abuse magnet; see below. |
Deep dive: minting short keys
Section titled “Deep dive: minting short keys”There are four common ways to make the key. Pick each one below, slide the number of stored links, and watch what happens to collisions, length and coordination.
| Strategy | Collisions | Coordination | Guessable | Notes |
|---|---|---|---|---|
| Hash the URL (MD5/SHA, keep 7 chars) | Yes, must check | None | No | Same URL → same key, so dedupe is free. On collision, rehash with a salt. |
| Random 7 chars | Yes, must check | None | No | Simple. Each create is a conditional insert that may need a retry. |
| One global counter → base62 | Never | Every create | Yes: 3QdyUh, 3QdyUi… |
The counter is a hot spot and a single point of failure. |
| Counter ranges per server | Never | 1 call per block | Yes, unless shuffled | Default. Flickr’s “ticket servers” and many id services work like this. |
The collision math is the birthday bound: with K possible keys, a collision somewhere becomes likely after about √K keys. For 7 characters that is √(3.5 × 10¹²) ≈ 1.9 million links, which you pass on day one. So random and hashed keys always need a check. The check is a conditional insert and stays cheap, about one try per create, until the table is a large fraction full.
Counter ranges skip the check. To stop people enumerating your links by incrementing a key, run the id through a reversible shuffle before encoding it, for example a small block cipher or an XOR-and-multiply bijection over the id space. The key still decodes to a unique id, but neighbours look unrelated. The unique id generator deep dive covers other id schemes, such as Snowflake.
mint_key(): if local.next > local.end: -- block used up local <- allocator.reserve(1000) -- one atomic increment on a consistent store id <- local.next; local.next <- local.next + 1 return base62(shuffle(id)) -- shuffle: a bijection, so still unique
base62(id): -- digits 0-9, a-z, A-Z repeat: emit ALPHABET[id mod 62]; id <- floor(id / 62) until id = 0 return the emitted characters reversedPrefetch the next block when the current one is 80% used, so a slow allocator never blocks a create. A crashed node loses the rest of its block, which is fine: gaps don’t matter, uniqueness does.
Deep dive: the redirect path and caching
Section titled “Deep dive: the redirect path and caching”Redirects are about 99% of traffic, and clicks follow a power law: a link shared by a large account gets millions of clicks, and most links get almost none. That skew is what makes caching work. Slide the skew and the cache size below, then look at the cold start on the right.
What to take from it:
- Cache size buys less and less. At a typical skew, the first few percent of links give most of the hit ratio. Past that, each doubling of the cache gains a few points.
- LRU is close to ideal for this workload. The caching concept page covers LRU mechanics and alternatives such as LFU.
- The dangerous moment is a cold cache. After a restart or a flush, almost every click goes to the database at once. Warm caches before they take traffic, and coalesce concurrent misses for the same key into one database read.
handle GET /{key}: rec <- cache.get(key) if rec is missing: rec <- single_flight(key, () -> store.get(key)) -- one DB read per key, however many waiters cache.set(key, rec or NOT_FOUND, ttl = rec ? min(24h, rec.expires_at - now) : 60s) -- negative entries expire fast if rec is NOT_FOUND: return 404 if rec.disabled or rec.expires_at < now: return 410 emit_async(click_event(key, now, referrer, country)) -- never wait for analytics return 302, Location: rec.long_url, Cache-Control: private, max-age=0301 or 302? This choice decides whether you can count clicks.
| Status | Meaning (RFC 9110) | Browser behaviour | Use when |
|---|---|---|---|
301 Moved Permanently |
The resource has moved for good | Cached, often indefinitely; repeat clicks never reach you | No per-click analytics; you want the least load |
302 Found |
Temporarily elsewhere | Not cached unless headers say so | Default when you count clicks |
307 / 308 |
Same as 302 / 301, but the method can’t change | As above | Rarely matters for GET links |
A middle path: 301 with Cache-Control: max-age=3600 cuts repeat traffic and still sees each visitor once an hour.
Analytics goes through the click log, never through the store. Consumers aggregate per key per minute (a streaming rollup) into a time-series table. Exact unique-visitor counts need the raw events; approximate ones can use HyperLogLog sketches at a few KB per link.
Deep dive: aliases, expiry and abuse
Section titled “Deep dive: aliases, expiry and abuse”Custom aliases share the namespace with generated keys. Two rules keep them apart: aliases may contain characters generated keys never use (a hyphen, say), and a reserved list blocks words like api, login and brand names. Uniqueness must be enforced by the store with a conditional insert (insert only if the key is absent). A “read, see it’s free, then write” check races when two users ask for the same alias at once, the same check-then-act bug as in the rate limiter.
Expiry has two halves, as in any TTL design:
- Lazy check on read. The redirect handler compares
expires_atwith now and returns 410. Correctness never depends on a cleanup job running on time. - Background sweep. A job deletes or archives expired rows in batches, using the store’s native TTL if it has one (DynamoDB TTL, Cassandra TTL). That reclaims space.
- Cache TTL never outlives the link. Cap the cache entry’s TTL at
expires_at - now, or a cached record could redirect after the link has died. - Don’t reuse expired keys by default. Old links live on in emails and printed flyers; reusing a key sends those readers somewhere new.
Abuse. Shorteners hide destinations, so spammers and phishers love them. Defences, in order of where they run:
- At create: check the URL against Google Safe Browsing or a similar list, rate-limit creates per account and IP, and block URLs that point back to the shortener (redirect loops).
- After create: rescan periodically, since a domain can turn malicious later. A takedown sets
disabled = trueand purges the cache key; it does not delete the row, so there is an audit trail. - At redirect: optionally show an interstitial (“you are leaving for…”) for links flagged as suspicious.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Cache node down | Its keys miss; DB read rate jumps | Consistent hashing so only that node’s keys move; request coalescing; DB sized for the post-failure miss rate |
| Cache flushed / cold start | DB overload, redirect timeouts | Warm before taking traffic; ramp traffic; single-flight on misses |
| Store shard down | Creates fail for its key range; misses on its keys fail | Replicas with automatic failover; cached keys keep redirecting |
| Key allocator down | Nodes can’t get new blocks | Large blocks plus early prefetch give minutes of runway; allocator on a replicated consistent store |
| Hot link (viral) | One cache shard saturated | Small in-process cache in each web node for the hottest keys; replicate hot keys |
| Click pipeline backed up | Analytics lag | Redirects don’t wait on it; the log buffers hours; consumers catch up |
| Key-guessing scanner | Many 404s, DB load from misses | Negative caching, rate limits per IP, shuffled ids |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Redirect, cache hit | O(1), ≈1 ms with the network | ≈500 B per cached link |
| Redirect, miss | O(1) cache + O(log n) index probe on one shard, ≈5 ms | — |
| Create | O(1) key mint + one conditional insert, ≈10 ms | ≈500 B per link (×3 replicas) |
| Mint key from range | O(1) local; one allocator call per 1,000 | O(1) per node |
| base62 encode | O(key length) = O(log₆₂ id) | 7 chars covers 3.5 × 10¹² ids |
| Storage, 5 years at 100M/day | — | ≈180B links ≈ 90 TB, ≈270 TB replicated |
| Click events, 10B a day | O(1) append | ≈100 B each ≈ 1 TB/day raw |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Analytics or not (301 vs 302), custom aliases, expiry, scale, read:write ratio.
- Estimate (5 min). Creates/s, redirects/s, storage, and the key length from the key space.
- API and data model (5 min). Two endpoints, one table keyed by short key.
- Key generation (10 min). Compare hashing, random and counters. Land on counter ranges with base62 and explain why there is no collision check. Mention a shuffle for unguessable keys.
- Read path (10 min). Cache in front of the store, the skew argument, negative caching, 302 and the click log.
- Harden (5-10 min). Expiry, abuse, cold cache, hot links, multi-region (replicate the store async; a new link might 404 briefly in a far region, so route the creator’s next read to the home region or fall back to it on a miss).
Follow-ups to expect: “Two users shorten the same URL. Same key?” Per user, yes via an index on the URL hash; across users, usually no, so per-user analytics stay separate. “How would you make keys 6 characters?” 62⁶ ≈ 57 billion: enough for about 1.5 years at this rate, so either accept longer keys later or reclaim expired ones. “Redirects in 20 ms worldwide?” Serve them at the edge with a regional cache or a key-value store replicated to each region.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Flickr: Ticket servers, distributed unique primary keys on the cheap: a counter service built from two MySQL servers, the ancestor of range allocation.
- RFC 9110 §15.4: Redirection 3xx: the exact semantics of 301, 302, 307 and 308.
- Google Safe Browsing: the API most link services use to screen destinations.
- Redis: key eviction: LRU and LFU approximations for a cache like the redirect cache.
Concept pages to drill: Hash maps · Caching · TTL and expiry · Randomization · API design · Idempotency