Cruxly › System design › Design Exercises

Short Links at Scale

id generation without coordination; 10000:1 reads

Prompt: design a service that turns a long URL into a short one, and redirects. Support custom aliases, link expiry, and a click count per link.

Give yourself 40 minutes before reading on. The interesting part is not the hash function.

Applying the four moves: Scope — create, redirect, custom alias, expiry, click count; accounts and analytics dashboards are out, said out loud. Estimate — the number that matters is the read:write ratio, and the move worth practising here is catching your own first figure as implausible (10,000:1 per day gives ~11.6 million reads/s) and correcting it out loud to ~300k peak reads/s. Sketch — 1,000 writes/s fits one primary, so the sketch is a key-value store with a cache in front; resist sharding writes that don't need it. Deep dive — key generation without coordination between generators, then the click counter as a hot-write problem hiding inside a read-heavy system.

Scope and numbers

In scope: create a short link, redirect, custom alias, expiry, click count. Out of scope: user accounts, analytics dashboards, malicious-URL scanning, previews. Name them so they are not omissions.

Estimate. Say 100 million new links a day and a 10,000:1 read:write ratio.

Writes: 10^8 / 10^5 s = 1,000 writes/s average, ~3,000 peak.
Reads: 10 million redirects/s? No — sanity-check that. 10,000:1 gives 10^12 reads/day, which is implausible. Revise: the ratio applies per link over its lifetime, not per day. Take reads as 10^10/day = 100,000 reads/s, ~300,000 peak.
Storage: 100M/day x ~500 bytes = 50 GB/day, ~18 TB/year. Five years is 90 TB.

Catching your own implausible number out loud is worth more than never producing one. Interviewers remember the correction.

What the numbers say. 1,000 writes/s is comfortably one primary — no sharding needed for writes yet, though 90 TB will force partitioning on volume eventually. 300,000 reads/s is the whole problem, and it is a pure key-value lookup of an immutable record, which is the most cacheable workload that exists.

Generating the key

A 7-character key over [A-Za-z0-9] gives 62^7 ≈ 3.5 x 10^12 — about a century at 100M/day. Good.

Option A: hash the URL, take 7 characters. Deterministic, so the same URL collapses to one key. Collisions are certain by the birthday bound well before you exhaust the space, so every insert needs a uniqueness check and a retry with a salt. That check is a read-before-write on the hot path, and the retry loop's latency is unbounded in the worst case. Also, determinism is a problem for custom expiry: two users shortening the same URL with different expiries cannot share a key.

Option B: a global counter, base-62 encoded. No collisions ever. The counter is a single point of coordination and therefore a bottleneck and a failure point. Keys are sequential, so they are enumerable — anyone can walk your entire database. Both are disqualifying at this scale.

Option C (chosen): pre-allocated ranges. A coordination service hands each application instance a block of one million counter values. The instance issues from its block with no network call at all, and requests a new block when it is running low. Collisions are impossible by construction, coordination happens once per million links, and an instance dying merely wastes the rest of its block — which is free, because the space is enormous.

The sequentiality remains. Fix it by a fixed bijective scramble of the integer before encoding — a reversible mix so adjacent counters produce unrelated-looking keys. Not security, just non-enumerability, and say it that way: "this is obscurity, not access control; if a link needs to be private it needs an actual permission check."

Custom aliases go through a separate path: insert into the same table with a uniqueness constraint, and let the constraint reject duplicates. Reserve a namespace so a custom alias can never collide with a generated one — for example, generated keys are always exactly 7 characters and custom ones must differ in length, which removes the interaction entirely.

Storage and the read path

The record is tiny and immutable after creation:

key (PK) | long_url | created_at | expires_at | owner_id

Partition by hash of key. Every read is a point lookup on the partition key, which is the cheapest possible query shape.

The read path is a cache problem. Link popularity is extremely skewed — a small fraction of links serve nearly all redirects. Cache aggressively:

CDN / edge. The redirect is an HTTP 301/302 with no personalisation, so it can be served at the edge. This is the single biggest win: most redirects never reach your origin.
Shared cache tier behind that, holding the hot set. At ~500 bytes a record, even 100 million hot links is 50 GB — a modest cluster.
Database as the backstop.

Records are immutable, so there is no invalidation problem — the hardest part of caching is simply absent here. The exceptions are deletion and expiry, and both are handled by setting the cache TTL no longer than the remaining link lifetime.

301 versus 302 is the question interviewers ask here and it is a real trade. A 301 (permanent) lets browsers and intermediaries cache the redirect, which removes traffic from you entirely — and it means you never see those clicks and can never change or revoke the link for that user. A 302 (temporary) keeps every click flowing through you. Choose 302 and say why: click counting and revocability are product requirements, and the traffic is the business you are in.

Click counting

A synchronous increment per redirect is 300,000 writes/s against a single row per popular link — a hot-row disaster that would also add latency to the one thing that must be fast.

Redirect first, count asynchronously. Emit an event to a log, return the 302 immediately. Consumers aggregate.

Then choose the counting guarantee explicitly, because this is where the question is going:

Approximate, cheap (chosen). Each app instance keeps in-memory per-link counters and flushes aggregates every 10 seconds. A crash loses up to 10 seconds of counts for that instance. Click counts are a vanity metric; losing a handful is undetectable and the cost saving is enormous.
Exact. Every click is a durable event, deduplicated by a request ID, aggregated downstream. Now click counting costs more than redirecting does.

Say the choice in those terms: "I'm making click counts explicitly approximate — within about 1% — because exactness here costs more than the redirect path itself and no user can tell the difference. If this were billable ad clicks, that answer inverts completely and I'd want a durable event per click with dedupe." Recognising that the right answer flips with the business context is the signal.

Edge caching interacts here: any redirect served by the CDN is invisible to your counter. Either accept the undercount and say so, or use a 302 with a short CDN TTL and accept the traffic.

Expiry, deletion, and the failure modes

Expiry. Do not scan for expired rows. Store expires_at, check on read, and let a background compaction reclaim space lazily. Set the cache TTL to min(default_ttl, time_until_expiry) so an expired link cannot outlive its expiry in cache.

Deletion. Mark deleted, remove from cache immediately, reclaim later. Immediate cache removal matters because the whole design leans on cached immutability.

Failure modes to raise unprompted:

Cache tier down. 300,000 reads/s hits the database directly and it will not survive. Mitigation: the CDN layer absorbs most of it even if your cache is gone; beyond that, accept degraded latency and shed load rather than cascading. Worth saying that this is the scenario that actually takes the service down.

Counter-block service down. New links cannot be created once instances exhaust their blocks. Mitigation: request the next block at 20% remaining, not at zero. That is 200,000 spare IDs: about 3 minutes if one instance takes all 1,000 writes/s, about 33 minutes per instance if ten share them. Size the block bigger if you want hours of headroom. Redirects are entirely unaffected, which is the right blast radius — say so.

Hot link. One link goes viral. It is cached everywhere, so this is the easy case — it is the one thing a read-only immutable workload handles naturally. Say it, because it inverts the usual expectation.

Abuse. Short links hide their destination, so the service will be used for phishing. Out of scope as declared, but naming it in one sentence — "in production this needs a scanner on the write path and a takedown mechanism" — shows product judgement without spending time.

How to say it in the interview

"Two things stand out before I draw anything: reads outnumber writes by about ten thousand to one, which makes this a caching and replication problem rather than a sharding one; and ID generation has to work without the generators talking to each other."

Checklist

Derived the read:write ratio and said it makes this a caching problem, not a sharding one
Sanity-checked an implausible number and corrected it out loud
Chose an ID scheme needing no per-write coordination, and said what the others cost
Made generated keys non-enumerable and called it obscurity, not security
Kept custom aliases from colliding with generated keys by construction
Noted that immutable records remove the invalidation problem entirely
Chose 301 vs 302 and named the trade
Made click counting asynchronous and explicitly approximate
Handled expiry by checking on read rather than scanning
Named what happens when the cache tier is lost

Practice this interactively