Dev Learning
Read-heavy / caching

Link shortener

Design a service that turns a long URL into a short one, and sends anyone who visits the short link to the original. Anyone can create links; links do not expire by default.

starterCachingBack-of-envelope estimationSQL vs NoSQL — and why, not just namesCDNsIndexes and what makes a query slowLatency numbers worth memorisingAPI design — pagination, versioning, errorsTransactions, isolation and locking

Where’s the slack?

Reads: none. Writes: seconds.

A person is standing in front of a blank browser tab waiting to be redirected. There is nowhere to hide latency on the read path.

The redirect has zero slack. It is the product, it happens before any page renders, and a human is watching a spinner. Two hundred milliseconds here is noticeable; a second feels broken. So the read side of this problem is mostly a caching problem.

The write path has plenty of slack, and candidates often forget to use it. A person creates a link once, on purpose, and waiting 300 ms for it is fine. So on writes you can afford a database round trip, a uniqueness check, even a retry. On reads you can afford none of that.

Analytics has a lot of slack. A creator does not need their click count within a second of the click. So counting can be asynchronous, batched, approximate, and moved off the redirect path. That matters, because otherwise every redirect becomes a write.

So: The slack profile decides the design: the redirect is served from memory with no database on the path, creation is allowed to be slow and careful, and click counting goes into a queue and is aggregated later. Get those three budgets right and the rest is bookkeeping.

Work it through

Five stages, gated. You write your answer for each stage before its model answer unlocks. That is the core of the method.

Loading your progress…

Reference material for this problem. The diagrams below are here to check your own against once you have drawn it, not to read first.

The lifecycle

RequestedcreatorCode chosensystemStoredsystemServedvisitorDisabledcreator or systemCollisionunique constraint rejects it, generate again and retryCustom code takensame constraint, return a clean error to the userCache not warmedfirst click misses and falls through to the databaseCode does not existnegative cache, then a clean 404 — never a redirect to nowhereDestination is maliciousdisable, broadcast invalidation, accept the short TTL window
A link's life. The solid path is what most people draw; the branches below are where the design decisions are.

The numbers

Link creations~40 / sec (120 peak)
Redirects~4,000 / sec (12,000 peak)
Storage after 5 years~1.2 TB — one machine

So the hard part is read latency, not write throughput and not storage. Design the redirect to answer from memory; leave the write path simple and synchronous.

The estimate that decides the design. Reads beat writes a hundred to one.

The architecture

hit ~99%missinsertfire and forgetVisitorEdge / LBRedirect svcstatelessCachecode → URLDatabaseunique(code)CreatorCreate svcClick queueAggregator
Reads never touch the database in the normal case. Writes are synchronous and careful. Counting is off the hot path.

The mechanism

UserCachehas itDatabase
request inanswer back — the database never woke up
The normal redirect: answered from cache without touching the database. Nearly all traffic should look like this.

The decision this turns on

A
Random code + unique constraint
  • —3.5 trillion possibilities at 7 characters, so collisions are rare.
  • —No global coordination: any server can generate one.
  • —Codes are not guessable, so nobody can enumerate your links.
  • —Needs a retry loop on the rare constraint violation.
B
Counter encoded in base62
  • —No collisions at all, by construction.
  • —Shortest possible codes, since no space is wasted.
  • —The counter is a coordination point: a single sequence every server needs.
  • —Sequential codes are enumerable, leaking both your links and your volume.
Which one: Random with a unique constraint. The retry cost is negligible at 40 writes a second, and codes that cannot be enumerated are a requirement for a service that redirects to arbitrary destinations. Take the counter only if you need the absolute shortest codes and can accept guessable ones.
The main decision on the write path.

Follow-ups you should expect

Many interviews are decided in the follow-ups, not the first diagram.

10x traffic tomorrow. What fails first?The cache just died. What happens?The write worked but the response was lost and the client retried. What happens?Why this database and not Postgres?What does this cost per month?One user reports a slow request. How do you debug it?Now make it multi-region.A whole region is down. What do users see?

Same shape, other products

Few people write. Many read, and they read the same few things.

Your estimate comes back with reads outnumbering writes by 50x or more. The write path is a non-problem and you should say so out loud instead of designing it.

Others with this shape: URL shortener · Pastebin · News feed read path · Leaderboard

Before you leave
Try this problem again in a week without reading anything. Comparing what you write then with what you wrote today shows you what stuck.
Stuck, or new to this?Read the full worked solutionAll five stages end to end, with the diagrams and the costs, written out the way you would say it. Best read after you have had a go.Read it →

How it is really built

Write your own answer first. Then read how teams who run this at scale describe it. Their constraints were real, and the write-ups often say what their choices cost.

  • Amazon Dynamo paper ↗The key-value store this problem usually ends at, and why it chose availability over consistency.