System design interview question

Design a URL shortener

TinyURL, bit.ly, t.co: “design a URL shortener” is often the first system design question you get, because it is small enough to finish and still has real decisions in it — how codes are made unique, how long they are, and how a redirect stays instant when one link is opened thousands of times a second. Here is how to walk into it, and then how to practise it until the answer is yours.

Practise URL Shortener (TinyURL)

Multiple choicePick the design from four
Fill the gapsFill the gaps in one drawn for you
Build from scratchBuild it on a blank canvas

Practise it on a canvas

Free with an account.

The question, as an interviewer would set it

A team is building a link shortener. A user pastes a long URL and gets back a short link; anyone who opens the short link is redirected to the original address. Every short link must carry a code that is unique across the whole system, and the service will hand out billions of them over time. The mappings from code to URL are tiny, never change once written, and are looked up far more often than they are created — a popular link can be opened thousands of times a second. Redirects have to feel instant even under that read load, while creating a link can be a little slower.

What it is really testing

Every phrase that matters in the brief is a requirement in disguise. Spot them before you draw a single box.

“a code that is unique across the whole system”
A way to mint identifiers that never collide, without a single central counter everyone waits on.
“looked up far more often than they are created”
A read-heavy store that scales out for tiny key→value rows.
“Redirects have to feel instant even under that read load”
An in-memory cache in front of the store for the hottest links.

Back of the envelope

New links: 100 million a month → ~40 a secondAn assumption to say out loud. If the interviewer has a number in mind, they will give it to you.
Redirects: ~100 per link created → ~4,000 a secondThe average. One viral link alone can take thousands a second.
Codes over ten years: 100 million × 120 months → ~12 billionWhich is what decides how long a code has to be.
Storage: ~500 bytes per link → ~6 TB over ten yearsSmall. This question is about reads and uniqueness, not about size.

Questions to ask first

Can people choose their own code, or only receive a generated one?
Do links expire, or live forever?
Do we need click counts and analytics?
How many links are created a day, and how many redirects?
Must two people shortening the same URL get the same code?

The trade-offs you will be pushed on

1.How do many servers hand out codes that never clash, without checking with each other on every request?
2.How long must a code be to last for years?
3.A link goes viral. What keeps its redirects instant?
4.Permanent or temporary redirect — and what does each cost you?

Now answer it

The same design always gets the same score, with the reason behind every requirement — then defend it against the trade-offs above.