02. URL Shortener — Low-Level Design¶
~20 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)
The HLD named the boxes. This file opens the two that carry the design's weight — code generation and the redirect resolver — and pins down the data, the algorithms, and the concurrency corners where a shortener actually breaks.
Data models¶
The system of record is a single logical table, keyed by short code. In a relational store it looks like this; in a KV store the same fields become the value under key code.
CREATE TABLE url_mapping (
code VARCHAR(10) PRIMARY KEY, -- base62 short code, ≤10 chars
long_url TEXT NOT NULL, -- destination, up to ~2 KB
owner_id BIGINT NULL, -- null for anonymous links
created_at TIMESTAMP NOT NULL,
expires_at TIMESTAMP NULL, -- null = never
is_custom BOOLEAN NOT NULL DEFAULT FALSE,
status SMALLINT NOT NULL DEFAULT 1 -- 1=active, 0=disabled (kill-switch)
);
-- Secondary index only where a non-key query truly exists:
CREATE INDEX idx_owner ON url_mapping (owner_id); -- "list my links"
Two deliberate choices. First, code is the primary key, because every hot query is a point lookup by code — that makes reads a single index seek and gives a clean shard key. Second, there is no unique index on long_url: two users shortening the same destination should get two independent codes with their own owners, expiries, and analytics identities, so we do not deduplicate by URL.
The allocator keeps its own tiny table:
CREATE TABLE id_range (
range_name VARCHAR(32) PRIMARY KEY, -- e.g. 'global'
next_id BIGINT NOT NULL -- next unallocated integer
);
Analytics events are not stored here at all; they are emitted to the event bus with the shape { code, ts, referrer, country, ua_class } and land in the separate append-optimized store described in the HLD.
Component internals¶
Component 1 — Code generation (the range-vending allocator)¶
Responsibility: produce a unique short code per new link, with no collisions and no per-write coordination.
The core idea is to separate allocating a unique integer (which needs coordination, done rarely and in bulk) from turning an integer into a code (pure, local, done per write).
Service interface (app-server side):
class CodeGenerator:
def next_code() -> str # returns a fresh base62 code
def _refill_block() -> None # fetches a new range from the allocator
class IdAllocator: # the central range-vendor service
def allocate_block(size: int) -> (int start, int end) # atomic
Block allocation (central, atomic, rare). When a server's local block runs dry, it calls allocate_block(size=1000). The allocator advances id_range.next_id by size in a single atomic step and returns the claimed window:
UPDATE id_range
SET next_id = next_id + :size
WHERE range_name = 'global'
RETURNING next_id - :size AS start, next_id - 1 AS end;
Because the update is atomic (a single row, one transaction, or a compare-and-swap in a KV store), two servers refilling at the same instant get disjoint windows — [4,000,000..4,000,999] and [4,001,000..4,001,999] — and never the same integer.
Local minting (per write, no coordination). The server keeps (current, block_end) in memory and, on each write, takes current, increments it, and encodes it. Only when current > block_end does it refill. So the allocator is touched roughly once per 1,000 writes.
def next_code(self):
if self.current > self.block_end:
self.current, self.block_end = allocator.allocate_block(1000)
n = self.current
self.current += 1
return base62_encode(n)
base62 encoding. Map the integer into the alphabet 0-9A-Za-z (62 symbols):
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
def base62_encode(n: int) -> str:
if n == 0:
return ALPHABET[0]
out = []
while n > 0:
n, rem = divmod(n, 62)
out.append(ALPHABET[rem])
return "".join(reversed(out))
Hiding the sequence. Raw base62 of a counter leaks growth rate (consecutive links get near-consecutive codes). If that matters, permute the integer before encoding with a reversible transform — multiply by a large odd constant modulo 62^7 and add an offset, or run it through a Feistel network. The mapping stays one-to-one (still collision-free) but consecutive integers scatter across the keyspace, so codes look random without any collision handling.
Why not hashing? Hashing the long URL (e.g. first 7 chars of a base62-encoded SHA) is stateless and needs no allocator, but it collides — two different URLs can produce the same 7 chars — so every write needs a read-check-and-retry loop, and load spikes make those retries worse exactly when you can least afford them. Counter-plus-range sidesteps collisions entirely, which is why it is the default here.
Component 2 — Redirect resolver (cache-aside with stampede control)¶
Responsibility: resolve a code to a URL in one in-memory hop for the common case, protect the store on misses, and never let analytics slow the response.
def resolve(code: str) -> Redirect | NotFound:
# 1. Negative cache: known-bad codes short-circuit to 404.
if cache.is_negative(code):
return NotFound()
# 2. Positive cache hit — the overwhelming common case.
url = cache.get(code)
if url is not None:
emit_click_async(code) # fire-and-forget
return Redirect(url)
# 3. Miss: coalesce concurrent misses for the same code behind one lock,
# so a hot cold-key does not stampede the store.
with single_flight(code):
url = cache.get(code) # double-check: another waiter may have filled it
if url is None:
row = store.get(code)
if row is None or is_expired(row) or row.status == DISABLED:
cache.set_negative(code, ttl=30) # short negative TTL
return NotFound()
url = row.long_url
cache.set(code, url, ttl=86400) # long positive TTL
emit_click_async(code)
return Redirect(url)
Three details carry the weight. The negative cache with a short TTL stops a flood of requests for a nonexistent code from repeatedly hitting the store, while staying short enough that a just-created code becomes resolvable quickly. Single-flight coalescing ensures that when a viral link is cold, only one request touches the store and the rest reuse its result. Put the campaign scenario on it: when sho.rt/bf26's 24-hour cache entry expires mid-sale, 30,000 requests hit the app tier in the same second with no cached value. Without coalescing, that is 30,000 simultaneous reads against one store shard — the shard browns out, latency spikes, and the miss never gets filled, so the next second brings another 30,000. With coalescing, exactly one request reads the store, fills the cache, and the other ~29,999 wait a few milliseconds and read the fresh entry. This is the line between a graceful cache miss and a self-inflicted outage. And emit_click_async never blocks: it enqueues to a local buffer flushed to the event bus, so analytics load and event-bus hiccups cannot leak into redirect latency.
Core algorithm — custom alias reservation¶
Custom aliases are the one write that needs a synchronous uniqueness guarantee, and doing it wrong causes two users to both "win" the same alias. A read-then-write check has a race: both read "free," both write. The fix is a conditional insert that lets the store enforce uniqueness atomically:
INSERT INTO url_mapping (code, long_url, owner_id, created_at, is_custom)
VALUES (:alias, :url, :owner, now(), TRUE)
ON CONFLICT (code) DO NOTHING; -- primary key is the guard
-- If zero rows inserted, the alias was taken → return 409.
In a KV store the equivalent is a put-if-absent / conditional write. Either way the primary-key constraint is the single source of truth for "is this code taken," so concurrency is resolved by the store, not by application logic.
Sequence diagram — a cold redirect under a burst¶
Client A Client B App single_flight Redis URL Store
│ GET /aZ8kQ2 │ │ │ │ │
├─────────────┼────────▶│ get(aZ8kQ2) │ │ │
│ │ ├────────────────┼───────────▶│ (miss) │
│ │ GET /aZ8kQ2 │ │ │
│ ├────────▶│ get(aZ8kQ2) │ │ (miss) │
│ │ ├─ acquire(code) ▶│ │ │
│ │ │ (B waits ...) │ │ │
│ │ ├────────────────┼────────────┼─────────────▶│ read
│ │ │◀───────────────┼────────────┼──────────────┤ row
│ │ ├─ set(aZ8kQ2) ──┼───────────▶│ (fill) │
│ │ ├─ release(code) ▶│ │ │
│◀────────────┼─ 302 ───┤ │ │ │
│ │◀─ 302 ──┤ (B reuses filled cache, no 2nd store read) │
One store read serves both clients; the second request is coalesced behind the first and served from the freshly filled cache.
Concurrency and edge cases¶
- Duplicate code minting: impossible by construction — disjoint integer ranges per server mean no two servers ever encode the same integer, and within a server the counter is single-threaded per block (guard with an atomic increment if the server is multi-threaded).
- Lost ID block on crash: if a server dies mid-block, the unused integers in its block are simply skipped forever. That is fine — the keyspace is 3.5 trillion wide, so leaking a few thousand codes per crash is negligible, and it buys us zero-coordination minting.
- Expiry: checked at read time (
is_expired) rather than by a background sweep on the hot path, so an expired link returns404immediately even if a janitor job has not yet deleted the row. A low-priority batch job reclaims expired rows for storage. - Delete/kill-switch propagation: on delete or disable, actively invalidate the Redis entry and purge the CDN path; do not wait for TTL. Between purge and propagation,
302links stop resolving immediately (clients re-ask us), while301links may linger in client caches — a reason to default to302. - Idempotent creation: if a client retries a
POSTafter a network timeout, it may create a second code for the same URL. This is acceptable (URLs aren't deduped), but a client can pass an idempotency key that the server records to collapse retries into one code if exactly-once creation is desired. - Cache/store skew after backfill: because mappings are immutable, a stale cache entry can only ever be missing (never wrong), so cache-aside backfill is always safe — there is no read-your-writes hazard on the value itself.