System Design HLD-19.01
Design a URL shortener
Design a URL shortener: base62 codes from counters or hashes, a cached redirect path, 301 vs 302, custom aliases, expiry and async click analytics.
The problem
A URL shortener turns a long link, full of path segments and tracking parameters, into a short one like sho.rt/3Hk9xQ. Anyone who opens the short link is redirected to the long one. People paste these links into posts, messages and printed material, so a link that stops working, even years later, is a broken promise.
It looks like a weekend project: a table with two columns. It becomes a real design problem at scale, because three things pull against each other: every code must be unique and short, redirects must be fast for links that suddenly go viral, and the business wants analytics on every click without slowing the redirect down.
Requirements
Functional
- Create a short link for a long URL, optionally with a custom alias (
sho.rt/winter-sale). - Redirect a short link to its long URL.
- Optional expiry: a link can stop working after a date.
- Click analytics per link: total clicks, clicks per day, referrers and countries.
Non-functional
- Scale: 100 million new links a month; redirects outnumber creations about 100 to 1.
- Latency: redirects p99 under 50 ms at the server; creation can take a few hundred milliseconds.
- Availability: redirects are the product, so they must be highly available (99.99 percent). Link creation can tolerate brief outages.
- Durability: a created link must never be lost or point somewhere else.
- Codes should be hard to enumerate, so private links are not trivially discovered.
Out of scope
- User accounts and billing, link editing, QR codes, malware scanning of target URLs (mentioned under Extensions).
Estimates
Assume 100 million new links a month, 100 redirects per link, 500 bytes per stored link and five years of retention.
# Back-of-the-envelope numbers for a URL shortener.
NEW_PER_MONTH = 100e6 # new short links per month
READ_RATIO = 100 # redirects per new link
RECORD_BYTES = 500 # code, long URL, owner, timestamps
YEARS = 5
SEC_PER_MONTH = 30 * 86_400
writes = NEW_PER_MONTH / SEC_PER_MONTH
reads = writes * READ_RATIO
records = NEW_PER_MONTH * 12 * YEARS
tb = records * RECORD_BYTES / 1e12
print(f"writes: {writes:,.0f}/s avg, {2 * writes:,.0f}/s peak")
print(f"redirects: {reads:,.0f}/s avg, {2 * reads:,.0f}/s peak")
print(f"links in {YEARS} years: {records / 1e9:.1f} billion, {tb:.1f} TB")
for k in (6, 7):
space = 62 ** k
print(f"{k} chars: {space:,} codes, {space / records:,.0f}x need")
# Cache if 20% of a day's redirects were for distinct links
hot = 0.2 * reads * 86_400
print(f"hot set: {hot * RECORD_BYTES / 1e9:.0f} GB")Output
writes: 39/s avg, 77/s peak
redirects: 3,858/s avg, 7,716/s peak
links in 5 years: 6.0 billion, 3.0 TB
6 chars: 56,800,235,584 codes, 9x need
7 chars: 3,521,614,606,208 codes, 587x need
hot set: 33 GB What these numbers decide:
- Writes are tiny: about 40 per second, under 80 at peak. A single database leader could take them; we will still spread the data for storage and reads.
- Reads are the load: about 3,900 redirects per second on average and 7,700 at peak, before any viral link. They must come from a cache.
- Storage is modest: 6 billion links and about 3 TB over five years. That fits a sharded key-value store comfortably.
- Code length: 6 base62 characters give 56.8 billion codes, about 9 times the five-year need; 7 characters give 3.5 trillion. We use 7 to leave room for growth and for random-looking codes, which waste part of the space.
- Cache size: if a fifth of a day's redirects were all for distinct links, that is about 33 GB of hot data, which fits in a small cache cluster.
API
POST /v1/links
body: { "url": "https://shop.example.com/...", "alias": "winter-sale", "expires_at": "2027-01-31T00:00:00Z" }
201 Created { "code": "winter-sale", "short_url": "https://sho.rt/winter-sale" }
409 Conflict if the alias is taken
GET /{code}
302 Found Location: https://shop.example.com/...
404 Not Found if unknown, 410 Gone if expired
GET /v1/links/{code}/stats?from=2026-10-01&to=2026-10-31
200 OK { "clicks": 18234, "by_day": [...], "top_referrers": [...] }
Creation needs an idempotency keyA client-chosen unique key sent with a request so the server can recognize retries and return the original result instead of acting twice. header ( Idempotency and safe retries ) so a retried POST does not create two links for one click of a button.
Data model
One main table, keyed by the code:
| Field | Type | Notes |
|---|---|---|
code | string, primary key | 7-character base62 code or custom alias |
long_url | string | up to a few KB |
owner_id | string | nullable for anonymous links |
created_at | timestamp | |
expires_at | timestamp | nullable |
Every redirect is a single lookup by code, and there are no joins, so a key-value or wide-column store fits well ( Choosing the right database ). The partition key is code, which spreads data and load evenly because codes are effectively random. A secondary table links_by_owner(owner_id, created_at, code) serves "my links" pages. Click events live elsewhere, in an append-only analytics store, because they are a hundred times more numerous and are queried by time, not by key.
High-level design
- Write path The link service holds a block of ids from the range allocator, takes the next one, encodes it in base62 and writes code -> URL to the database. Custom aliases are written with a conditional insert that fails if the code exists.
- Read path The redirect service looks the code up in the cache. Almost every request is a hit; on a miss it reads the database and fills the cache (cache-aside). It returns 302 with the long URL in the Location header.
- Async path After answering, the redirect service emits a click event (code, time, referrer, country) to an append-only log. Analytics workers aggregate events into per-link counters. A slow analytics pipeline never slows a redirect.
Notice that creation and redirect are separate services. They have completely different load (40 versus 4,000 requests per second), different availability needs and different scaling, so splitting them lets the redirect fleet scale and deploy on its own.
Deep dives
Deep dive 1: Generating short codes
There are three common ways to get a unique code.
Hash and truncate. Hash the long URL (for example with MD5 or SHA-256), encode it in base62 and keep the first 7 characters. No coordination is needed and the same URL always gets the same code. But different URLs can produce the same 7 characters. By the birthday paradoxThe surprising fact that collisions among random values become likely once you have about the square root of the number of possible values., the chance of at least one collision becomes large once the number of links nears the square root of the code space, so every insert must check whether the code already exists and, if so, retry with a salt. That turns every write into a read-then-write.
Counter plus base62. Give every link a unique integer and write it in base 62, using the 62 characters 0-9a-zA-Z. Codes never collide and stay as short as possible. A single global counter would be a bottleneck and a single point of failure, so a range allocatorA service that hands out disjoint blocks of ids, such as 1,000 at a time, so servers can assign ids locally without coordinating on each one. hands each link-service instance a block of ids (say 1,000 at a time) stored in a coordination service or a database row ( Coordination services (ZooKeeper, etcd) ). An instance that crashes wastes the rest of its block, which is harmless.
Pre-generated random keys. A background job generates random 7-character codes, checks they are unused, and stores them in a pool; servers pop codes from the pool. Codes are unguessable and there are no collisions at write time, at the cost of running and monitoring the pool.
We choose counter ranges plus base62, with one twist: sequential ids give sequential codes, so anyone can walk 3Hk9xQ, 3Hk9xR, ... and discover other people's links. Before encoding, we pass the id through a fixed, reversible bit shuffle (for example a small block cipher keyed with a secret). The mapping is still one-to-one, so there are still no collisions, but consecutive ids no longer produce neighbouring codes.
Deep dive 2: The redirect path, 301 or 302
The redirect response decides who can cache it:
- 301 Moved Permanently: browsers and proxies may cache the redirect, so repeat visits never reach your servers. Cheaper and faster, but you lose those clicks from analytics, and you cannot change or expire the link for anyone who has cached it.
- 302 Found (or 307): not cached by default, so every click reaches the redirect service. You keep complete analytics and full control.
We choose 302, because analytics and expiry are requirements. The cost is that every click reaches us, which the estimates already account for. To keep latency low, the redirect service should run in several regions behind GeoDNS or anycast ( Global traffic: GeoDNS, anycast and GSLB ), each with its own cache and a read replica of the URL data.
Caching works unusually well here. A short link never changes after creation, so a cached entry never goes stale; the only invalidation needed is on expiry or takedown, when we delete the key. The hot set follows a heavy-tailed pattern: a few links get most clicks, so a modest cache gives a very high hit ratio. Viral links create hot keys ( Thundering herd, cache stampede and hot keys ): one code read hundreds of thousands of times a second can overload the single cache node that owns it. Keep a tiny in-process cache of the hottest few thousand codes in each redirect server, which absorbs such spikes before they reach the shared cache.
Deep dive 3: Click analytics without slowing redirects
Writing a row to an analytics database on every redirect would put a second write on the hottest path. Instead the redirect service sends a small event to a durable log ( Message queues vs pub/sub vs event streams ) after responding, ideally through a local buffer so a log outage never blocks redirects. A stream processor ( Stream processing ) aggregates events into counters per link per minute, and stores them in a time-series or columnar store for the stats API.
Two details matter. Bots and link previewers (chat apps fetch links to show previews) inflate counts, so filter known user agents. And because the log delivers at least once, the aggregator must deduplicate by an event id or accept small overcounts, which is usually acceptable for marketing analytics.
Custom aliases and expiry
A custom alias is just a code the user chose. It lives in the same table, and creation uses a conditional insert ("insert if not exists") so two users racing for winter-sale cannot both win; the loser gets 409. Reserve words like api, admin and stats, and keep aliases out of the generated code space, for example by requiring at least one hyphen or a different length, so a future generated code can never collide with an alias.
Expiry is checked on read: if expires_at has passed, return 410 Gone and evict the cache entry. A background job deletes expired rows later in batches, so cleanup never competes with the redirect path. Cached entries should carry a TTL no longer than the time left to expiry.
Try it
Try this:
- In counter mode, enter 61, then 62. Why does the code get one character longer? Enter 3521614606207 (that is 62^7 - 1) and see the largest 7-character code.
- Switch to hash mode with code length 4 and 10,000 URLs. How many collisions do you get? Now set the length to 7 and push the URL count to 100,000.
- With length 5, find roughly where the chance of a collision passes 50 percent. Compare it with the square root of 62^5.
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Viral link (hot key) | One cache shard overloaded, rising latency | Per-server in-process cache for top codes, replicas for hot keys |
| Cache cluster down | All redirects hit the database: at a 99 percent hit ratio, 100x its normal read load | Database read replicas sized for it, request coalescing, shed analytics first |
| Range allocator down | New links fail once servers exhaust their blocks | Servers prefetch the next block early; allocator runs replicated |
| Analytics log down | Click events lost or delayed | Local buffer on each server, redirects never wait on the log |
| Code enumeration | Private links discovered | Shuffled ids, rate limits per client, longer codes for private links |
| Region outage | Redirects fail for that region | Multi-region read path with replicated URL data, DNS failover |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Counter ranges + base62 (chosen) | No collisions, shortest codes, no read-before-write | Needs an allocator; codes guessable unless shuffled |
| Hash and truncate | No coordination; same URL gives the same code | Collisions need checks and retries on every write |
| 302 redirect (chosen) | Full analytics, expiry and takedown keep working | Every click costs a request to us |
| 301 redirect | Browsers cache it, so less load and faster repeat visits | Lost analytics; cannot change or expire cached links |
| Async analytics through a log (chosen) | Redirect latency unaffected by analytics | Stats lag by seconds to minutes; at-least-once duplicates |
Extensions
- Malware and phishing checks on target URLs at creation, with a takedown path that deletes the code from the cache everywhere.
- Deduplication: return the existing code when the same user shortens the same URL again (a lookup by URL hash).
- Link editing for paid users, which makes cache invalidation necessary and rules out 301.
- Per-tenant custom domains (
go.brand.com/...), which turns the key into (domain, code).
In the wild
Where you will see this: public link shorteners, the short links that social networks wrap around every posted URL so they can count clicks and check for abuse, and internal "go links" inside companies (go/oncall). All of them face the same choices: how codes are generated, whether redirects are permanent, and how clicks are counted without slowing the redirect.
Check yourself
-
Why does the design use 302 instead of 301 redirects?
Show answer
B. Browsers cache 301s, which would hide clicks from analytics and prevent expiry A cached 301 never reaches the server again, so the click is not counted and the link cannot be changed or expired for that browser.
-
With hash-and-truncate codes, why must every insert check for an existing code?
Show answer
B. Two different URLs can produce the same truncated code Truncating a hash to 7 characters maps many URLs to the same space; by the birthday paradox collisions appear far earlier than the space size suggests.
-
A server holding ids 5,000 to 5,999 crashes after using 5,240. What happens?
Show answer
B. Ids 5,241 to 5,999 are never used, which is harmless Range allocation trades a few unused ids for no per-request coordination. Gaps do not matter; duplicates would.
-
One link goes viral and its cache shard is overloaded. What helps most?
Show answer
B. A small in-process cache of hot codes on each redirect server A hot key concentrates load on one shard; caching it on every server spreads that load across the whole fleet.
-
Why are click events sent to a log instead of written directly to an analytics database?
Show answer
B. It keeps the slow, high-volume analytics write off the redirect path The redirect responds immediately; aggregation happens later, so an analytics slowdown never slows redirects.
Recap
- Redirects outnumber creations about 100 to 1, so the design centres on a cached read path.
- Counter ranges plus base62 give collision-free 7-character codes; shuffle ids so codes are not guessable.
- 302 keeps analytics and expiry working; 301 trades them for less load.
- Short links never change, so caching is easy; watch for hot keys from viral links.
- Click analytics flow asynchronously through a log so they never slow a redirect.
Next up
- Crack the system design round learning path