Codes, redirects, expiry: the deep dives

Part of the free System Design course on LogicWiz, in the chapter: Design a URL shortener. The interactive whiteboard exercises and simulations run in the app.

Week 10: The three hard parts

"I said hashing never collides. The interviewer asked me to do the sum. The sum said it does."

Meera, in a mock interview with Kabir

Deep dive 1: codes that never collide

Every interviewer asks: "How do you make the short code?" There are three families of answer. Compare them with numbers.

Weak: hash the URL, keep 7 characters. A hash is a fixed-size fingerprint of its input. Encode it in base62 and cut it to seven characters, and two different URLs can share a code. The same URL always gets the same code too, so two campaigns cannot have separate analytics or expiry. You still need a collision check, so the hash bought you very little.

Good: random codes with a check, or one counter. Pick seven random characters and write the row only if the code is free, a conditional insert. If it exists, pick again. Late in life, 6 billion links sit in a space of 3.5 trillion, so about 1 create in 580 collides and needs one retry. That is cheap, and random codes cannot be guessed in order. The cost is a conditional write on every create.

The other good option is one global counter, encoded in base62. There are no collisions at all, but every create waits on one row. The codes are also in order, so anyone can try aZ3k9Qx and then aZ3k9Qy and copy every link.

Great: counter ranges plus a scramble. A small allocator (etcd, or one database row updated atomically) hands each service instance a block of 1,000 numbers. The instance issues them from memory. At 40 creates a second, the allocator sees one call every 25 seconds. Before encoding, the instance passes the number through a fixed, one-to-one scramble, so neighbouring numbers give codes that look unrelated and no two numbers share a code.

The trade-off: if an instance crashes, the rest of its block is lost. Against 3.5 trillion codes, that waste does not matter. In return there are no collision checks and no hot row (one row that every request must update). A scramble is not security, though. With 1 code in 580 being real, a scraper still finds links, so rate-limit unknown-code requests per IP address.

Write the plan for codes in the Data notes.

Deep dive 2: the redirect at 10,000 a second

Weak: read the database on every click. A big store can do it, but you pay for a cluster sized for the peak, and every slow disk read lands in your p99.

Good: a cache in front. The service checks Redis first. At a 95% hit ratio, the database sees about 500 reads a second. Cache "not found" for a minute too. This is the design we built, and it is a solid answer.

Great: the cache, the right status code, and the edge. The status code is a real decision.

Use 302. A 301 saves load, but you lose repeat clicks and you can never expire the link for browsers that already saved it. You pay in load, which the estimate already covers.

For a campaign link about to go viral, let a CDN (a set of servers near users that cache responses) keep the 302 for 60 seconds. The origin barely notices a spike. The trade-off: clicks served at the edge never reach your service, so count them from CDN logs, and an expired link may still redirect for up to a minute.

Deep dive 3: expiry and cleanup

Weak: a nightly job that scans every row. It looks for expires_at in the past and deletes. After 5 years that is a scan of billions of rows, run against the live store. Between runs, expired links keep working for up to a day. A tempting extra is to reuse freed codes, but then an old SMS opens a stranger's page. Never reuse a code.

Good: check expiry when you read. The service compares expires_at with the clock and answers 410 Gone. The cache TTL is the smaller of the normal TTL and the time left, so the cache never outlives the link. It is correct at once, but dead rows pile up.

Great: check on read, and let the store delete. Write each row with a TTL set to the expiry plus a grace period, say 30 days. Many key-value stores can expire rows by themselves, so no scan is needed. Counter codes are never issued twice, so a deleted row cannot be taken again. For custom aliases, keep a tiny tombstone, so nobody claims an old alias. During the grace, support can still answer "that link expired" with a 410, and an owner can extend it. After it, the row is gone and the code answers 404. Stats rows follow their own, longer retention.

The trade-off is storage held through the grace period, and the edge cache, which can serve an expired link for up to 60 seconds.

What breaks, and how you notice

• A Redis node dies. Misses jump and the store sees thousands of reads. Alert on hit ratio and store latency. Limit cache refills so the rush does not flatten the store.
• The allocator is unreachable. Instances use their blocks: with 4 instances sharing 40 creates a second, a full block lasts at most about a minute and a half. Then creates fail. Redirects are unaffected. Lease the next block early.
• One link goes viral. At 50,000 clicks a second, one cache shard runs hot. Keep that code in each service instance's memory for a few seconds, or let the CDN serve it.
• Spam and scanning. A sudden rise in creates or in 404 answers is the sign.

What Mid and Senior sound like

A Mid answer has the right rates (40 and 10,000), seven-character base62, a sound way to keep codes unique, a cache in front of a replicated store, and a redirect status. A Senior answer also explains why ranges beat hashing, makes codes hard to enumerate, argues 302 against 301 in terms of analytics and expiry, keeps clicks off the redirect path, and plans for hot keys and abuse.

Expect these follow-ups.

• Two users want the same alias? A conditional insert. The second gets a 409.
• Two regions? Give each region its own blocks, so codes never collide. Replicate the links store and redirect from the nearest copy.
• Phishing links? Rate-limit creates, scan targets in the background, and disable a bad code.

📌 Summary: Make codes from counter ranges plus a scramble, not hashes. Use 302 with a cache. Check expiry on read, let the store delete later, and never reuse a code.

What Meera learns next

Kabir's last follow-up stays with Meera: "How do you stop one script creating a million links, or guessing codes all night?" Both are one caller using more than a fair share. Next chapter: design a rate limiter.

Check your understanding

1. A design picks random 7-character base62 codes and writes with insert-if-absent. After 6 billion links in a space of 3.5 trillion, about what share of creates needs a retry?
2. Marketing wants exact click counts per day and the power to switch off a link. The team debates 301 against 302. Which is right, and why?
3. The code allocator is unreachable for ten minutes. Four instances each hold a fresh block of 1,000 and creates run at 40 a second. What do users see?
4. To save code space, a team proposes to delete expired links nightly and give their codes to new links. What goes wrong?