11.1 — URL Shortener

Someone pastes https://mtrx.sh/a7Kd9Qz into a group chat. Two hundred people tap it over the next hour. Every one of those taps is a request that must find one row, in one database, somewhere in the world, and answer with a redirect before the tapper notices a delay — because the shortener is not the page they wanted, it is the toll booth in front of it. If the toll booth takes 300 ms, every link ever shared through you feels slow.

That is the whole problem, and it is why this looks like a trivial system and is not. A shortener contains, in miniature, four things that appear in almost every design in this Part: generating identifiers that must be unique forever, a read/write ratio so lopsided that the cache stops being an optimisation and becomes the serving tier, an analytics pipeline that must never be allowed to slow the thing it measures, and a latency budget small enough that you have to account for it in milliseconds.

1. Requirements

Functional. Create a short URL from a long one, optionally with a custom alias and an expiry date. Redirect a short URL to its target. Report basic analytics — how many times a link was clicked, broken down by day and country.

Non-functional, with numbers.

• Redirect latency under 50 ms at the 99th percentile, measured server-side. This is not a comfort target. The redirect sits on the critical path of someone else's page load, so your latency is added to a page you do not control.
• Availability for reads at 99.99% or better. Links are forever. A shortener that goes down does not inconvenience its own users, it breaks every link anyone has ever shared, including the ones printed on physical posters.
• Codes must be unguessable enough that walking the namespace is impractical, because links are often semi-private — an unlisted document, a personal invitation.
• Writes are rare, reads are enormous. Get the ratio confirmed; it decides everything.

Out of scope for today: user accounts and authentication, link editing, paid tiers, branded domains, and full malware scanning (I will name where it plugs in, but not design the scanner).

The clarifying questions, and what each answer changes

"What is the read/write ratio?" If the answer is 10:1 this is a modest database problem. If it is 100:1 or more, the design becomes a cache with a database attached, and every later decision follows from that. Assume 100:1 unless told otherwise.

"Do links expire, or live forever?" Forever means storage grows without bound and you need a tiering story for old data. Expiry means the cached value has to carry the expiry too, which quietly removes the "entries are immutable" gift that makes the rest of the design easy.

"Can the same long URL be shortened twice?" If yes, code generation can be random and stateless. If the product wants one code per URL, you need a lookup by long URL, which means a second index on a 100-million-row-per-month table, and deduplication becomes a write-path cost.

"Do we need to revoke a link after it is created?" This is the question that decides 301 versus 302, and therefore your entire traffic volume. Ask it in the requirements phase, not at minute thirty.

"Is analytics a product feature or a nice-to-have?" If it is the product, you cannot let browsers cache redirects, and the read volume you must serve yourself goes up by an order of magnitude.

2. Estimation

Assume 100M new URLs per month and the 100:1 read/write ratio.

Writes. 100M ÷ 2.6M seconds in a month ≈ 40 writes per second on average, call it 120 per second at peak. What that forces: almost nothing. Forty writes a second is what a single unremarkable database instance does while idle. So the write path may afford expensive work — a uniqueness check, a blocklist lookup, a synchronous cache population — without any of it mattering. Recognising that a number rules nothing out is as useful as recognising that one rules something out, because it tells you to stop optimising there.

Reads. 100 × 100M = 10 billion redirects a month ÷ 2.6M seconds ≈ 4,000 per second average, and with a 3× peak factor, ~12,000 per second at peak. What that forces: this is the design. Twelve thousand point lookups a second against a database is possible but expensive and fragile, and it will not hold a 50 ms tail under load. So the answer has to be served from memory.

Storage. Each row holds the code (7 bytes), the long URL (average ~200 bytes, but allow for the 2,000-byte monsters), a few timestamps and an owner identifier — call it 500 bytes per row with index overhead. 100M rows × 500 bytes = 50 GB per month, 600 GB per year, and with 3× replication, 1.8 TB per year on disk. What that forces: very little in year one, and something real by year five. Multi-terabyte is fine for any partitioned store, but "links live forever" means you should decide the retention and tiering policy now — cold links moved to cheaper storage — rather than discovering it when the primary is full.

Cache. Link traffic follows a power law: a small fraction of links carry most of the clicks, because links go viral or they die. Caching the hot 10 million codes at ~500 bytes each is 5 GB of RAM. What that forces: the entire architecture. Five gigabytes fits in one modest cache node with room to spare, which means a 99%+ hit rate is affordable, which means the database sees roughly 120 reads per second instead of 12,000 — a hundredfold reduction, at the cost of one commodity machine. This single number is the reason the design works.

The latency budget, spent on paper. Fifty milliseconds sounds generous until you write down where it goes:

Step	Budget	Note
Edge/load balancer to service	3 ms	same region
Service overhead, parsing, logging	2 ms
Cache lookup (hit)	1–2 ms	network round trip in-datacentre
Emitting the click event	0 ms	fire-and-forget into a local buffer
Response serialisation	1 ms
Total on a hit	~8 ms
Database lookup on a miss	+5–15 ms	1% of requests
Headroom left for the tail	~35 ms	garbage collection pauses, retries, noisy neighbours

What that forces: the budget is comfortable only if the cache hit rate stays high. At a 50% hit rate the p99 collapses into database territory, which is why cache hit rate is the primary alarm for this system, not CPU.

3. API

Three endpoints carry the product.

POST /urls
Content-Type: application/json
Idempotency-Key: 9f2c1b7a-3e5d-4a80-9c11-6b0f2d7e4a55

{ "longUrl": "https://example.com/a/very/long/path?with=params",
  "customAlias": "spring-sale",
  "expiresAt": "2027-01-01T00:00:00Z" }

201 Created
Location: https://mtrx.sh/spring-sale

{ "code": "spring-sale", "shortUrl": "https://mtrx.sh/spring-sale",
  "longUrl": "https://example.com/a/very/long/path?with=params",
  "expiresAt": "2027-01-01T00:00:00Z", "createdAt": "2026-07-31T09:14:02Z" }

GET /a7Kd9Qz
→ 302 Found
  Location: https://example.com/a/very/long/path?with=params
  Cache-Control: private, max-age=0

GET /urls/a7Kd9Qz/stats?from=2026-07-01&to=2026-07-31&cursor=eyJkIjoiMjAyNi0wNy0xNSJ9
→ 200 OK
  { "code": "a7Kd9Qz", "totalClicks": 184223,
    "byDay": [ { "date": "2026-07-15", "clicks": 9911 } ],
    "nextCursor": "eyJkIjoiMjAyNi0wNy0xNiJ9",
    "freshnessSeconds": 22 }

Idempotency. Creating a link is not naturally repeatable — retry the request and you get a second link to the same target, which is confusing for the user and wasteful for you. The client sends an Idempotency-Key; the service stores it with the created code under a unique index, so a retry with the same key returns the original 201 body rather than creating anything (10.4). This costs one extra row and one extra lookup on a path that runs forty times a second, which is free.

Pagination on stats. Click history is a time series that grows while you read it, so it uses a cursor rather than an offset. An offset query over a moving list shows some days twice and skips others (9.6.2). The cursor here is just an encoded date, which is honest about what it is: the opaque cursor rule exists so you can change the encoding later without breaking clients.

The error envelope, one shape everywhere:

409 Conflict
{ "error": { "code": "alias_taken",
             "message": "That alias is already in use.",
             "requestId": "req_01J9F3K7Q" } }

The status codes that carry meaning here: 400 for a malformed or non-HTTP URL, 409 for a custom alias already taken, 422 for a URL that is well-formed but refused (blocklisted domain), 410 Gone for a link that existed and expired — which is genuinely different from 404, and telling the two apart is what lets a client show "this link has expired" rather than "not found" — and 429 when a creator exceeds their rate limit.

One decision to state out loud: 301 or 302. 301 Moved Permanently lets browsers, proxies and CDNs cache the mapping, often for a very long time. Your traffic collapses, which is wonderful for cost and latency. It also destroys two things: analytics, because cached redirects never reach your servers at all, and revocability, because clients keep using their cached answer and you cannot take a link down. For a shortener, revocation is a safety requirement — links get reported as phishing and must stop working within minutes, not whenever a browser cache expires. So 302 Found is the usual choice, made deliberately, and the extra traffic is precisely what the cache tier exists to absorb. The middle ground worth naming: 302 with a short Cache-Control: max-age=60 at the CDN recovers much of the traffic saving, bounds staleness to a minute, and keeps analytics approximately complete from edge logs (10.14.3).

4. Data model

urls
  code          VARCHAR(16)  PRIMARY KEY     -- 'a7Kd9Qz' or 'spring-sale'
  long_url      TEXT         NOT NULL
  created_at    TIMESTAMPTZ  NOT NULL
  expires_at    TIMESTAMPTZ  NULL            -- NULL = never
  owner_id      UUID         NULL
  is_custom     BOOLEAN      NOT NULL
  status        SMALLINT     NOT NULL        -- active | disabled | takedown

idempotency
  key           UUID         PRIMARY KEY
  code          VARCHAR(16)  NOT NULL
  created_at    TIMESTAMPTZ  NOT NULL

click_rollup                                 -- written by the analytics consumer
  code          VARCHAR(16)
  day           DATE
  country       CHAR(2)
  clicks        BIGINT
  PRIMARY KEY (code, day, country)

Access patterns, before the partition key:

Query	Frequency	Returns
Look up by code	12,000/s peak	one row
Insert one row	120/s peak	—
Idempotency check by key	120/s peak	one row
Stats for one code over a date range	~10/s	≤ 400 rows
Find links owned by a user	rare	tens of rows

Partition key: code, hashed. Every high-volume access is a point lookup by code, so a hash partition spreads perfectly across nodes and there is no query that wants a range scan over codes (10.6). The rarer "links owned by a user" query does not get to choose the key — it is served by a secondary index and is allowed to be slower, which is exactly the trade you should state rather than hide.

Indexes and what each one is for:

• Primary key on code — the redirect. This is the only index that matters at scale.
• Unique index on idempotency.key — makes the duplicate-create impossible rather than unlikely.
• Index on owner_id — the user's link list, low volume.
• click_rollup keyed by (code, day, country) — the stats query reads a contiguous range and nothing else.

Notice what is not here: no index on long_url. Adding one would let you deduplicate links, and it would cost an index on a 200-byte variable-length column across a table growing by 100M rows a month. If the product wants deduplication later, the cheaper spelling is a separate table keyed by a hash of the long URL, which indexes 16 fixed bytes instead of 200 variable ones.

5. Architecture

The read path first, because it is 99% of what this system does.

Figure 1 — The read path. Every component here exists to protect one 50 ms budget. The service holds no state, so it scales by adding copies; the cache holds the power-law hot set; and the click event leaves through a buffer so that analytics can be slow, or entirely dead, without a single user noticing.

The write path is a different shape, and drawing it separately makes the asymmetry obvious: this side of the system does forty things a second and is allowed to be careful.

Figure 2 — The write path. Forty requests a second means every step here is affordable. The database's unique index is the collision detector: the code is not checked before insertion, it is simply inserted, and the rare rejection triggers one retry.

And the failure path, which is the panel nobody draws and the one an interviewer remembers.

Figure 3 — The failure path. Each layer removes a fraction of the load rather than all of it, and that is the point: survival here is arithmetic, not a single trick. The last layer works only because of a property of the data — mappings are immutable, so replica lag cannot serve a wrong answer.

Read path in words: the tap arrives at the edge and is routed to the nearest region. A stateless redirect service extracts the code, looks it up in the shared cache, and on a hit — 99 times in 100 — checks the expiry carried in the cached value, appends a click event to an in-process buffer, and returns a 302. On a miss it reads the row, writes it into the cache, and answers. Nothing on this path waits for anything that is not needed to produce the redirect.

Write path in words: validate that the URL is well-formed and uses http or https (a javascript: target in a shortener is a stored cross-site-scripting delivery service), check the domain against the blocklist, generate a random 7-character code, insert it, and let the unique index reject the rare collision so you can regenerate and retry. Populate the cache and return 201.

6. Deep dives

6.1 Generating the code

This is the one genuinely interesting choice, and there are four real options.

Option 1 — hash the long URL. Take a SHA-256 of the URL and keep the first 7 base62 characters. This is deterministic: the same URL always produces the same code, which deduplicates storage for free. It also leaks information — anyone can check whether a particular URL has been shortened by computing its code — and it still needs collision handling, because truncating a hash to 42 bits is not injective. Custom aliases sit awkwardly beside it.

Option 2 — random 7 characters of base62. Base62 is the digits, the lowercase and the uppercase letters: 62 symbols, so 62⁷ = 3,521,614,606,208 possible codes, about 3.5 trillion. Generate one at random, insert, and let the unique index catch a collision.

The arithmetic that makes this safe is worth doing on the board. After a full year you have 1.2 billion codes in a 3.5-trillion space, so the chance that a freshly generated code is already taken is 1.2e9 ÷ 3.5e12 ≈ 1 in 3,000. Over the whole first 100 million inserts, the expected number of collisions is roughly n²/2N = (10⁸)² ÷ (2 × 3.5×10¹²) ≈ 1,400 collisions in total — about one every twenty hours, each costing one extra insert attempt. The unique index handles it; you never need a "check if it exists" query, because checking and then inserting is a check-then-act race anyway, and the constraint is the only mechanism that is actually atomic.

Option 3 — a global counter encoded to base62. Take an ever-increasing integer and write it in base 62: 125 becomes "cb" (125 = 2×62 + 1, and symbol 2 is c if you index digits-then-lowercase-then-uppercase, symbol 1 is b). Codes are the shortest possible and collisions are impossible by construction. Two problems, both fatal for a public shortener. They are sequential, so anyone can enumerate your entire corpus by counting upward, which turns "unlisted" links into "listed" ones. And a single global counter is a distributed coordination point (11.5).

Option 4 — a counter with per-instance ranges, plus a scramble. Each service instance claims a block of 10,000 identifiers from a coordinator, hands them out locally, and claims another block when it runs low. That removes per-write coordination while keeping the density. Then run each number through a bijective scramble — a small fixed-key block cipher over the integer range — so consecutive counters produce codes that look unrelated. This is the right answer when code length genuinely matters, and it is more machinery than most products need.

Choose option 2. Seven random base62 characters, unique constraint as the collision detector, retry on conflict. It is unguessable, needs no coordination at all, and its failure mode is a retry that happens once a day. Custom aliases live in the same table and the same namespace, so they get uniqueness from the same constraint — with a reserved-word list so that nobody registers api, admin, login, static or health and shadows a real route.

Rejected explicitly, and why: option 3's density is not worth enumerability for a product where links are shared privately, and option 4's machinery is not worth it while 7 characters remain short enough that nobody complains.

6.2 The cache is the system

Key by code, value is {longUrl, expiresAt, status}. Evict by least-recently-used, which matches the traffic shape exactly: link popularity decays over hours and days, so the least-recently-used entry is genuinely the least likely to be needed next (9.7.30).

Three refinements turn a working cache into a durable one.

Negative caching. If a request arrives for a code that does not exist, remember that fact for 30 seconds. Without this, a script scanning random 7-character codes produces a 100% miss rate, and every one of those misses is a database read. With it, the scanner mostly hits your cache and your database never notices. The cost is that a link created in the last 30 seconds may briefly appear to be missing, which is why the write path populates the cache directly rather than relying on invalidation (10.14.2).

Stampede protection. A viral link is a single key receiving thousands of requests per second. When that key expires or is evicted, every one of those requests misses simultaneously and they all read the same database row at the same instant. The fix is request coalescing: the first miss for a key starts the read and every other request for that key waits on the same in-flight promise, so 4,000 concurrent misses produce one query. The subtlety worth naming is that the in-flight entry must be removed in a finally block — if a failed load leaves the entry in place, every future request for that key waits forever on a rejected promise.

Immutability is a gift, and you should say so. A code-to-URL mapping never changes once written. That means the cache needs no invalidation protocol at all: the only mutations are deletion and expiry. It also means read replicas can serve the miss path without any staleness risk, and it means multi-region replication has almost no conflicts to resolve. Naming a property of the data that removes a class of problems, rather than adding a mechanism to solve it, is one of the strongest moves available in a design round.

6.3 Analytics that cannot slow the redirect

Every redirect emits {code, timestampMs, referrer, countryCode, deviceClass}. The rules that keep this safe:

Never increment a counter in the database on the redirect path. That single line of code converts a cached read into a database write at 12,000 per second, and it couples redirect availability to analytics availability — if the counter store is down, links stop working. This is the most common wrong answer to this problem and it is worth naming as wrong before anyone asks.

Buffer locally, flush in batches. The service appends the event to an in-memory buffer and a background task ships batches of a few thousand to the stream every second or so (10.8.1). The redirect never waits. The cost, stated honestly: if a service instance is killed mid-flight, you lose up to one second of click events from that instance. For click analytics that is an acceptable loss, and saying "we accept losing about a second of events on an instance crash, because these are counts and not money" is a better answer than pretending the pipeline is lossless.

Aggregate downstream, keep the raw log. Consumers roll events into (code, day, country) counters. Unique-visitor counts use a HyperLogLog sketch, which estimates cardinality in a fixed 12 KB per key with about 2% error and, more importantly, merges — so daily sketches can be combined into a monthly unique count, which exact daily counts can never be (10.18). If someone later demands exact numbers, the durable stream can be replayed.

State a freshness target. "Stats are at most 60 seconds behind" is a number the dashboard's credibility rests on, and it becomes an alarm on consumer lag (10.10).

6.4 Abuse, takedown, and the part that is actually hard operationally

A shortener is a laundering service for bad links, and this is the deep dive that separates people who have run one from people who have read about one.

On write: reject non-http(s) schemes, reject links to your own domain (which lets someone build an infinite redirect loop), and check the domain against a blocklist.

After write, continuously: a benign target can turn malicious the day after it is shortened, because the attacker controls the destination and you only stored a pointer. So there is a background re-scanner that walks links by popularity — the most-clicked links get rechecked most often, because that is where harm scales.

Takedown must be fast, and this is where 302 pays for itself. Setting status = 'takedown' in the database does nothing on its own, because 99% of traffic never touches the database. The takedown path must actively evict the key from the cache in every region, and the service must treat a takedown as a 410 Gone with an interstitial page rather than a silent failure. Measure this: "time from report to link dead" is a real operational number, and with 301 it would have been "whenever browsers feel like it", which is not an answer you can give a regulator.

Rate limit creation per account and per IP, because the cheapest attack on a shortener is to create ten million links pointing at a target and use your domain's reputation as the delivery vehicle (9.7.5).

7. Decision Ledger

Decision	Alternatives	Why this	What it costs
Random 7-char base62	hash of URL; global counter; ranges + scramble	unguessable, zero coordination, index catches collisions	not deterministic; ~1,400 retries per 100M inserts
302 redirect	301; 307	keeps analytics and revocation	full traffic hits us; no browser caching
Cache-first serving	database with read replicas only	99% hit rate meets 50 ms at 1% of the database load	cache outage is a 100× spike; needs its own failure plan
Async click stream	synchronous counter increment	redirect stays fast and independent	counts lag ~60 s; ~1 s of events lost per instance crash
Hash partition on code	range partition; partition by owner	every hot query is a point lookup	no range scans; owner queries use a secondary index
No index on long_url	unique index for deduplication	keeps a 100M-rows-per-month table cheap to write	duplicate links exist; deduplication needs a hash table later
Negative caching, 30 s	none; longer TTL	turns a namespace scan from a database attack into a cache hit	a just-created link can appear missing for 30 s unless the writer populates the cache

8. Scale and failure

At 10× (120,000 redirects/second). The single cache node stops being enough, so the cache shards by code — trivially, because the key is already a hash. The stateless service tier grows by adding copies. And the biggest lever appears: put the redirect itself at the CDN edge. A 302 with a short Cache-Control is cacheable content, so a large share of traffic never reaches your region at all, and the analytics arrive from edge logs a few minutes late instead of in real time. That is a deliberate trade of analytics freshness for a large cost reduction, and it belongs in the ledger.

At 100× (1.2 million/second). Multi-region active-active. This is unusually easy here, and the reason is worth stating precisely: records are immutable and uniquely keyed, so replicating them between regions produces no conflicts to resolve. The only genuinely shared state is code allocation, and that is solved without coordination by giving each region its own prefix character or its own scramble key, so two regions cannot mint the same code even in principle. A design where the 100× answer is "the data shape means there is nothing to coordinate" is a design that got its identifiers right at minute twelve.

Namespace exhaustion. 3.5 trillion codes at 100M a month is roughly 2,900 years. The migration path, if it were ever needed, is additive — start issuing 8-character codes while all 7-character codes keep working — which is worth one sentence because interviewers ask.

What breaks	Blast radius	How you find out	What keeps it running	Recovery
Shared cache down	every read falls to the database — a 100× spike	cache hit-rate alarm; p99 latency	in-process L1, request coalescing, load shedding, read replicas	warm from the top-N code list before restoring traffic
Database primary down	writes fail; cached reads unaffected	write error rate	degrade to read-only with a clear 503 on POST	promote a replica; replay buffered creates
Analytics consumer stalled	stats go stale; redirects unaffected	consumer lag alarm vs the 60 s target	events keep buffering in the durable log	add consumers; lag drains as the exit condition
One region unreachable	users in that region only	health checks; regional error rate	edge routes to the next region	none needed — data is replicated and immutable
Namespace scan / scraping	database read amplification	miss-rate alarm; requests per source IP	negative caching plus per-IP limits	none needed if negative caching is on
Malicious link goes viral	reputation, not availability	abuse reports; click-rate anomaly	takedown evicts cache in all regions, serves 410	measured as time-from-report-to-dead

The recovery detail people miss: a cache that comes back empty reproduces the incident, because restoring full traffic to a cold cache is exactly the same event as losing a warm one. Pre-warm from the top-N list maintained by the analytics pipeline, then ramp traffic through the load shedder rather than opening it in one step.

What the interviewer will push on

"Why not 301? You'd cut your traffic by 90%." They are checking whether you know that a caching decision is also a control decision. The tell in a good answer is that you name revocation, not just analytics — an abusive link that browsers have cached permanently is a problem you cannot fix by deploying code. The common wrong answer is "301 is for permanent moves and this is permanent", which is reasoning from the specification's wording instead of from the consequence.

"Your cache dies at peak. Walk me through the next sixty seconds." They are checking whether the cache was designed as infrastructure or assumed as magic. A strong answer gives the arithmetic — 12,000 requests a second arriving at a database sized for 120 — then names the four mitigations in order of how much load each removes, and finishes on the recovery trap that a cold cache is the same incident again. The weak answer is "we'd add more cache nodes", which does not help during the sixty seconds in question.

"Why don't you check whether the code exists before inserting it?" This is a race-condition probe dressed as a performance question. The answer is that a check followed by an insert is exactly the check-then-act pattern that two concurrent requests can both pass, so the check does not remove the need for the constraint — it only adds a query. The unique index is the only step that is actually atomic, so it should be the mechanism, and the retry-on-conflict path is the collision handler.

"How do you deduplicate — same long URL, same short code?" They want to see you price a feature rather than agree to it. The mechanism is a lookup keyed by a hash of the long URL. The costs are a second index on a very large table, a write path that now does a read first, and a product consequence people forget: shared codes mean shared click counts, so two users who shorten the same article can see each other's traffic. That last point is the tell that you thought about the feature rather than the schema.

"Where does the 50 ms actually go?" They are checking whether the latency budget is a slogan. Walk the table from section 2 — 8 ms on a hit, plus 5–15 on a miss, leaving about 35 ms of headroom for tail effects — and name what eats the tail: garbage collection pauses, a cold connection pool, a retry after a dropped packet, and a noisy neighbour on the cache node. Candidates who cannot decompose the budget usually cannot defend the architecture either, because the architecture was chosen to fit it.

"Ten million links are created by one account in an hour. What happens?" They are probing the abuse surface, which is the real operational cost of running a shortener. Good answer: per-account and per-IP creation limits, a reputation check on the target domain, and the observation that the danger is not load — 10M creates an hour is only 2,800 a second — but that your domain becomes the delivery mechanism for someone else's phishing campaign, and domain reputation, once lost, takes months to recover.

Volunteer this, because nobody asks: the shortener's hardest number is not latency, it is time from abuse report to link dead, and the entire caching design either serves that number or fights it. 302 plus active cache eviction on takedown gets it to seconds. 301 makes it unbounded. That single operational requirement, surfaced in the requirements phase, decides the traffic profile of the whole system — which is a good example of a non-functional requirement quietly choosing the architecture.

Next: 11.2 — where the object stops fitting in a row. A URL is 200 bytes and a video is 4 GB, and that one change moves the data out of the database, puts the upload on a different path from the download, and makes resumability a first-class requirement rather than a nicety.

Recall

• Shape: ~40 writes/s against ~12,000 reads/s peak — a 100:1 read-dominated system built to a 50 ms p99 budget, where the cache is the serving tier and the database is the backing store.
• The number that decides it: caching 10M hot codes at ~500 bytes = 5 GB of RAM, which turns 12,000 reads/s into ~120 database reads/s.
• Codes: 7 random base62 = 62⁷ ≈ 3.5 trillion; ~1,400 collisions expected across the first 100M inserts, all handled by a unique index plus retry — never check-then-insert. Alternatives: hash (deterministic, leaks), counter (dense, enumerable), ranges + scramble (dense and unguessable, more machinery).
• 301 vs 302: 301 collapses traffic but destroys analytics and revocation; 302 keeps both at full traffic cost. Revocation is the deciding argument, because takedown must be measured in seconds.
• Cache details: LRU on a power-law hot set · negative caching so a namespace scan cannot become a database scan · request coalescing so a viral key's eviction is one query, with the in-flight entry cleared in a finally · immutability means no invalidation protocol at all.
• Analytics: buffered, batched, asynchronous; never a synchronous counter. HyperLogLog for unique visitors because sketches merge. State a freshness target and alarm on consumer lag.
• Scale: 10× shards the cache and pushes 302s to the edge (trading analytics freshness for cost); 100× is multi-region active-active, easy because records are immutable and uniquely keyed, with per-region code prefixes removing the last coordination point.
• Failure: cache down = 100× database spike (L1 + coalescing + shedding + replicas, then warm before restoring traffic); database down = read-only degrade; analytics down = invisible to users.

Self-test: Why is this a cache design rather than a database design? Give the four code strategies with one cost each. What exactly does 301 destroy? Why is check-then-insert wrong? Where do the 50 ms go? What makes 100× multi-region unusually easy here?

Quiz Bank

FoundationalWalk the estimation and say what each number rules in or out.

Writes. 100M new URLs a month ÷ 2.6M seconds ≈ 40 per second, ~120 at peak. This rules nothing out, and noticing that is the point: forty writes a second is idle load for one database instance, so the write path can afford a blocklist lookup, an idempotency check, a uniqueness retry and a synchronous cache population without any of them mattering. Effort spent optimising here is wasted.

Reads. 100:1 gives 10 billion redirects a month ≈ 4,000 per second average, ~12,000 at peak. This rules out serving from the database. Twelve thousand point lookups a second is technically possible but will not hold a 50 ms tail once connection pools, garbage collection and a noisy neighbour are in the picture, and it makes the database a single point of failure for every link ever shared.

Storage. ~500 bytes per row × 100M rows a month = 50 GB a month, 600 GB a year, ~1.8 TB a year after 3× replication. This rules nothing out either — it is a modest amount of data — but it does force a policy decision, because links live indefinitely: what happens to a link nobody has clicked in five years? Deciding tiering now is cheaper than discovering it later.

Cache. Traffic follows a power law, so the top ~10M codes carry most of the clicks: 10M × 500 bytes = 5 GB of RAM. This rules in the entire architecture. One commodity cache node absorbs 99% of reads, the database sees roughly 120 reads a second, and the 50 ms budget is met with about 8 ms of work on a hit.

Latency. The budget decomposes to roughly 3 ms at the edge, 2 ms of service overhead, 1–2 ms for the cache round trip and 1 ms to serialise, so ~8 ms on a hit with ~35 ms of headroom for the tail. That headroom is what pays for garbage collection pauses and the occasional retry, and it evaporates the moment the hit rate falls.

AppliedCompare the four short-code generation strategies, with the arithmetic.

(1) Hash the long URL. Take the first 7 base62 characters of a SHA-256. Deterministic, so the same URL always yields the same code, which deduplicates storage for free. Two problems: truncation means collisions still exist and need handling, and determinism is an information leak — anyone can test whether a given URL has been shortened. Custom aliases have to live outside the scheme.

(2) Random 7 base62 characters. 62⁷ = 3,521,614,606,208 ≈ 3.5 trillion codes. Generate, insert, and let a unique index reject the collision. The expected number of collisions across the first 100 million inserts is about n²/2N = (10⁸)²/(2×3.5×10¹²) ≈ 1,400 in total — roughly one every twenty hours, each costing one retry. No coordination anywhere, unguessable, and the uniqueness guarantee is the database's rather than yours (10.4).

(3) Global counter encoded to base62. The densest possible codes and zero collisions by construction, since the counter never repeats. But the codes are sequential, so anyone can walk the entire corpus by counting, which turns every unlisted link into a listed one; and a single global counter is a coordination point that must be highly available and monotonic (11.5).

(4) Counter with per-instance ranges plus a bijective scramble. Each instance claims blocks of 10,000 numbers, so coordination happens once per 10,000 writes instead of once per write. Then each number is passed through a small fixed-key permutation over the range, so 1,001 and 1,002 produce codes that look unrelated. Keeps density, defeats enumeration, and costs a coordinator plus a scramble to implement and never lose the key for.

Recommendation: (2). It is the only option with no coordination at all, its failure mode is one retry a day, and 7 characters is short enough that density buys nothing a user would notice. Choose (4) instead only if code length is a product requirement — a printed code, an SMS with a strict character limit.

InterviewShould redirects be 301 or 302, and what does the choice actually change?

301 Moved Permanently invites browsers, proxies and CDNs to cache the mapping, frequently for a very long time and sometimes until the browser cache is cleared. What you gain is enormous: most repeat clicks never reach your servers, so traffic, cost and latency all fall sharply. What you lose is two things, and both are severe for a shortener.

First, analytics. A cached redirect produces no request, so the click is invisible. For a product whose paid tier is "see who clicked your links", that is not a trade-off, it is a deleted feature.

Second, and more seriously, revocation. Once a browser has cached a 301, you cannot take the link down for that browser. A shortener receives abuse reports constantly, and "how long from report to link dead" is an operational number you may have to defend to a hosting provider, a payment processor or a regulator. With 301 the honest answer is "unbounded". With 302 plus active cache eviction it is "seconds".

302 Found is treated as temporary, so clients re-request every time. Every click is observable and every mapping stays mutable, at the cost of serving all the traffic yourself — which is exactly what the cache tier is for, and the arithmetic says one 5 GB cache node covers it.

The middle ground worth naming: serve 302 but let the CDN cache it for 60 seconds. You recover a large share of the traffic saving, staleness is bounded to a minute so takedown still works within an acceptable window, and analytics becomes approximately complete by reading edge logs instead of origin logs. That is a deliberate, statable trade between fidelity and cost, and offering it unprompted is what a senior answer sounds like (10.14.3).

307 Temporary Redirect exists too, and differs from 302 by preserving the HTTP method. For a shortener where all traffic is GET, it changes nothing, but knowing why it exists is a cheap point.

StaffYour cache tier goes down at peak. Describe what happens, what you would have built to survive it, and how you recover.

What happens, in numbers. The 99% of requests normally answered from RAM all fall through to the database at once. At 12,000 requests a second that is a hundredfold load increase onto a store sized for 120 reads a second. Without protection the sequence is predictable: the connection pool saturates in under a second, queries queue, latency crosses the 50 ms budget and then the client timeout, clients and CDNs retry, and the retries increase the load — the amplification failure from 10.9. What began as a cache outage becomes a full read outage, which is worse, because a degraded cache still had a database behind it and an overloaded database has nothing behind it.

What survives it, and it must be built in advance.

A local in-process cache in every service instance. A few megabytes per instance holding the hottest few thousand codes absorbs a large fraction of the event on its own, because the power law that makes the shared cache effective makes a tiny local cache effective too. It costs almost nothing and it is the single highest-value mitigation.

Request coalescing. Concurrent misses for the same code collapse into one database read (9.7.30). During a cache outage the misses are heavily concentrated on hot keys, so this removes more load than it does in normal operation.

Load shedding above a database-safe concurrency limit. Return a fast 503 to the excess rather than letting everything queue. Ninety per cent of users succeeding beats one hundred per cent timing out, and a fast rejection does not hold a connection.

Read replicas sized for a multiple of normal miss traffic. The redirect path is allowed to read from a replica because mappings are immutable, so replica lag cannot produce a wrong answer. This is a property of the data doing the work of a mechanism, and it should be said out loud.

Edge caching of 302s with a short TTL, which keeps a share of traffic off the origin entirely for the duration of the incident.

How you recover, and the trap. Bring the cache back and it is empty. Restoring full traffic to an empty cache is the same 100× spike you just survived, so the naive recovery reproduces the incident — this is the detail that separates people who have done it from people who have read about it. Pre-warm from the top-N code list that the analytics pipeline already maintains, then ramp traffic back through the load shedder rather than flipping it open in one step, and watch hit rate rather than error rate as the exit condition.

The lesson to record in the ledger: in a cache-first design the cache is not an optimisation layer, it is the primary serving tier. It needs the same redundancy, the same failure rehearsal, the same capacity planning and the same documented warm-up procedure that you would give a database — and the moment you write "99% hit rate" in an estimation, you have accepted that obligation.

Flashcards

FlashURL shortener shape

40 writes/s vs 12,000 reads/s peak; 50 ms p99; ~8 ms of real work on a cache hit. The design is a cache in front of point lookups. Storage modest, links live forever.

FlashCode generation arithmetic

7 random base62 = 62⁷ ≈ 3.5 trillion. ~1,400 collisions expected over 100M inserts, all caught by a unique index. Never check-then-insert — that is a race, not a check.

Flash301 vs 302

301: traffic collapses, but analytics and revocation die. 302: every click seen, every link revocable, full traffic. Takedown speed is the deciding argument. Middle ground: 302 with a 60 s CDN TTL.

FlashCache specifics

10M hot codes × 500 B = 5 GB. LRU · negative caching (30 s) so scans cannot become database load · request coalescing with the in-flight entry cleared in finally. Immutable entries ⇒ no invalidation protocol.

FlashCache-outage survival stack

In-process L1 → coalescing → load shedding → read replicas (safe because mappings are immutable) → edge caching. Recovery: warm from top-N before restoring traffic.

FlashMulti-region gift

Immutable, uniquely-keyed records replicate with no conflicts. Per-region code prefixes remove the only shared state, so 100× needs no cross-region coordination at all.

Scenario Drill

DrillThe interviewer adds three requirements: links must support expiry, creation must be rate-limited per user, and a dashboard must show clicks per country in near-real-time. Extend the design and name what each addition costs.

Expiry. Add expires_at to the row and to the cached value, then check it in the service on every read. Putting it in the cached value is the whole trick: if expiry lived only in the database, an expired link would keep working for as long as it stayed cached, which is exactly the class of bug that is invisible in testing and obvious in production. Cleanup is the second half — deleting expired rows from a table growing by 100M rows a month with DELETE sweeps is painful, so partition the table by creation month and drop whole partitions (10.6).

What it costs: the "records are immutable" property weakens. Entries are now time-varying, which means the multi-region story gains one mutable dimension and the replica-read argument needs a caveat. Keep the damage small by treating expiry as data evaluated at read time rather than as a deletion event that has to propagate — the row stays, the check is local, and nothing has to be invalidated anywhere.

Per-user creation rate limits. The write path was stateless; now it needs identity and a shared counter. Use a token bucket keyed by user, held in the same cache tier, with tiers as configuration rather than code (9.7.5). Return 429 with Retry-After through the standard error envelope.

What it costs: the write path gains a dependency, so it needs a stated failure policy for when the limiter store is unreachable. Fail-open keeps the product working and lets an abuser through; fail-closed protects you and breaks legitimate creation during an unrelated outage. The defensible middle for a shortener is fail-open below a global safety limit and fail-closed above it, so a limiter outage cannot be turned into unlimited link creation. Which one you chose, and why, is the graded part — not the token bucket.

Clicks per country, near-real-time. The click event already carries a country code derived at the edge from the client address, so no new data collection is needed. Add a stream consumer maintaining windowed counts per (code, country, minute) in a fast store, with the raw stream retained so exact numbers can be recomputed if the aggregation is ever wrong (10.8.2).

What it costs: "near-real-time" has to become a number. Pick a freshness target — say 30 seconds — write it into the dashboard as a visible "as of" timestamp, and alarm on consumer lag against it (10.10). Without the visible timestamp, users treat a lagging dashboard as a broken product; with it, they treat a 45-second delay as information. You also inherit a stream-processing component to operate, and the honest admission that the newest window is always partial.

What did not change, and why that is the answer. The redirect path is still edge → stateless service → cache → 302, and its 8 ms of work is untouched. Expiry became a field check already in RAM. Rate limiting landed on the write path, which was running at 3% of its capacity. Analytics landed in the pipeline that was already asynchronous. Three product requirements arrived and none of them entered the 50 ms budget — that placement is the demonstration the interviewer is looking for, and it is only possible because the read path was kept deliberately thin from the start.

The one thing that would break this pattern, worth naming before they ask: a requirement that the redirect depends on fresh mutable state — "links stop working after 100 clicks", say. That puts a counter read and a counter write on the critical path, and no amount of caching hides it, because the counter is the thing that must not be stale. The honest answer would be a per-instance approximate counter with periodic reconciliation, and an explicit statement that the limit is enforced within a small overshoot rather than exactly.