Designing a URL Shortening Service like TinyURL

Every case study in this chapter follows the same seven steps from System Design Interviews: A step by step guide, and builds its design from the components in the System Design Master Template. Keep both open beside you, and try each problem yourself before reading the solution.

Why do we need URL shortening?

URL shortening is used to create shorter aliases for long URLs. We call these shortened aliases "short links." Users are redirected to the original URL when they open these short links. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs.

For example, if we shorten the following URL through TinyURL:

https://www.designgurus.io/course/grokking-the-system-design-interview

We would get:

https://tinyurl.com/vzet59pa

The shortened URL is less than half the size of the actual URL, and the longer the original link, the bigger the saving.

URL shortening has other uses as well. Companies track individual links to analyze the audience and measure the performance of an ad campaign. Short links can also be optimized for different devices, or used to hide the original affiliate URL.

If you haven't used tinyurl.com before, please try creating a new shortened URL. Spend some time going through the various options their service offers. This will help you a lot in understanding this chapter.

Try it yourself

Before reading the solution, try designing it. Aim to produce four things: the requirements, a rough load estimate, the API, and a first drawing of the components.

Sketch it here

Designing a URL Shortener (video)

Here is a video discussing how to design a URL Shortener:

The write path runs at about 200 requests per second. A request arrives, the shortening service takes a key, and one row is inserted.

The read path runs at 20,000 requests per second, a hundred times heavier. A request arrives, the redirect service looks the key up, and returns a redirect.

That asymmetry is the most useful thing on the page. Everything expensive we add later belongs on the read path: the cache and the read replicas. The write path needs none of that. Its problem is not capacity but correctness. Every write must get a key that no other write has ever used. That is where step 6 goes next.

Step 6: Go Deep

Generating the key

This is the central question of the design: how do we produce a short, unique key for each URL?

How long should the key be? The usual answer is six characters. For this design, six is wrong.

We are storing 30 billion links. Six characters from a 62-character alphabet give about 56.8 billion possible keys. So more than half of all possible keys would point to a real link. Someone typing random characters would find a working link about every other try. That breaks the guessability requirement we agreed on in step 1.

Seven characters is the shortest length that fixes it. The keyspace grows to 3.5 trillion keys, and only 0.9 percent of them are ever used. A random guess now finds a working link about once in 117 tries. Rate limiting covers the rest of the risk.

This is a trade worth naming in the interview: one extra character makes guessing about sixty times harder.

Which alphabet? Base62, meaning A-Z, a-z, and 0-9. Base64 is often suggested, but base64 adds two more characters: + and /. Both cause trouble inside a URL. A slash splits the key into two path segments. A plus is often read as an encoded space by form handlers and proxies. So in practice, both end up percent-encoded. That makes links longer and harder to read, which works against the reason for shortening them. If you want base64, use the URL-safe variant with - and _ instead.

Now, where do keys come from? There are two answers. The difference between them is the real content of this problem.

Hash the URL. Run MD5 or SHA-256 over the long URL and keep the first seven characters of the encoded output. It is simple, and it has two problems.

The first problem: the same URL always produces the same key. So two users shortening the same link get the same short link. That sounds efficient, but it is not what you want. The two users may need different expiry times or separate click statistics. Worse, one of them may delete the link and break it for the other. Appending a counter or the user id to the hash input fixes this.

The second problem is the one that matters. We keep only seven characters, so we throw away most of the hash. Seven base62 characters hold about 42 bits. That means different URLs will collide, and at 30 billion stored links they will collide often. Every write then becomes a loop: generate a key, ask the database whether it is taken, and on a conflict start again. That loop runs on the request path while the user waits. It also gets slower as the keyspace fills.

Pre-generate the keys instead. A standalone Key Generation Service (KGS) produces random keys ahead of time and keeps them in a pool. Shortening a URL is then just: take a key from the pool, insert the row, done. No hashing, no collision check, no retry.

The uniqueness check has not disappeared. It has moved off the request path, into a background job where nobody is waiting. That is the whole trade. Stating it that way is a much stronger answer than either design on its own.

How big is the pool? It only has to stay ahead of demand, not cover the keyspace. At 17 million new links a day, a pool of one billion keys is about two months of buffer. One billion seven-character keys is only about 7 GB. The generator refills the pool continuously. Refilling is easy. With 0.9 percent of the keyspace used, a random candidate is already free about 99 times out of 100.

How does KGS avoid handing the same key to two servers? By handing out keys in whole blocks. A block is moved out of the unused pool and marked used before it leaves. A server asks for a block of, say, a thousand keys. KGS marks them used in one operation and hands them over. The server keeps the block in memory and answers writes locally. Two servers can never be given the same block.

If a server dies holding 900 unspent keys, those keys are lost. That is fine. We have trillions of them, and the alternative is coordinating on every single write.

Is KGS a single point of failure? Yes, and there are two protections against it. First, a standby takes over if the primary dies. Second, every shortening server still holds a block of keys in memory. So even during a failover, writes keep working.

What about custom aliases? Here, a uniqueness check on the request path is unavoidable. The user chose the value, so we cannot pre-approve it. Try to insert it. If the alias is taken, return an error and ask for another. That is acceptable because custom aliases are rare. Impose a sensible length limit, say 16 characters, so storage stays predictable. This limit is also why the data model stores the short key as varchar(16) rather than a fixed seven characters. The same column has to hold custom aliases too.

What happens on a redirect

This is 99 percent of the traffic, so it is worth examining carefully.

The lookup checks the cache first, and goes to the database on a miss. Then come three checks, each with its own answer:

• The key does not exist: 404 Not Found.
• The link has expired: 410 Gone. This is more accurate than 404. It tells the caller the link existed but is now removed, and the caller treats it differently.
• The link is private and the caller may not see it: 403 Forbidden if they are signed in, 401 Unauthorized if they are not. The distinction matters. 401 means "sign in and try again." 403 means "we know who you are, and the answer is no."

Otherwise, return 302 Found with the original URL in the Location header, and send a click event without waiting for it.

Why 302 and not 301? Both redirect the user. The difference is caching. A 301 says the move is permanent. Browsers cache it, so later clicks never reach our servers at all. That saves us traffic, but it also destroys our click statistics, and analytics is a stated feature. A 302 means every click still reaches our servers. If you did not need per-click analytics, 301 would be the better answer. Saying exactly that is what the interviewer is listening for.

Caching

The read path is a hundred times heavier than the write path, so this is where a change makes the biggest difference.

Put an in-memory cache like Redis in front of the database. Each cache entry holds everything a redirect needs: the original URL, the expiry time, and the visibility flag. On a cache hit, all the checks from the walkthrough above run without touching the database at all.

On a miss, the service reads the row from the database, returns the redirect, and writes the row back into the cache for next time.

Caching is usually hard because of updates. A write can race a cached copy and leave the cache stale. That can't happen here, because a link's destination never changes after it's created. An entry leaves the cache in only two ways, and both are cheap: expiry is checked against the cached row itself on every hit, and a DELETE call evicts the key as part of handling the request.

Size the cache at the 200 GB we estimated. Then tune it from the observed hit rate rather than from theory. Once warm, a cache this size should answer roughly ninety percent of reads. That is the hit rate the redirect walkthrough assumed. LRU (evict the least recently used entry) is the right eviction policy. A link is read most when it is new, so the links being read now are the ones worth keeping.

Cache expired and missing keys too, with a short time to live. Otherwise every request for a dead link becomes a database read.

Partitioning and replication

30 billion rows do not fit on one machine, so we partition the data by the short key. Take a hash of the key and map it to one of N partitions. The keys came from a random generator, so they spread evenly on their own. No partition becomes hotter than another.

Use consistent hashing so that adding or removing a machine moves a small part of the data rather than remapping everything.

You may see range-based partitioning proposed here, splitting on the first character of the key. It is worth knowing why we are not doing that. Range partitioning is the right tool when you need ordered scans, and we have no query that reads a range of keys. It also becomes unbalanced the moment keys stop being uniformly random, for example once custom aliases are included.

Replicate every partition to at least two other machines. Replicas serve reads, which helps with the read-heavy load. They also mean losing a machine does not lose data. Managed stores like DynamoDB and Cassandra do all of this for you. But interviewers ask how it works underneath, so be ready to explain the mechanism rather than the product name.

Expiry and cleanup

Links have an expiry date, so somebody has to remove them. Scanning the database constantly for expired rows would add permanent load for no benefit. So clean up lazily instead:

• When a request arrives for an expired link, return 410 and delete the row then.
• Run a low-priority cleanup job during off-peak hours to remove links nobody has asked for.

Some expired links will therefore stay in the database past their expiry date. That is fine, because they are never served to anyone.

Do not put expired keys back in the pool. It is tempting, because keys look like a resource worth recovering. But think about what a recycled key means. A short link printed on a poster, saved in a bookmark, or embedded in an old email suddenly points at somebody else's destination. That is a security problem, not a tidiness problem. The keyspace is 3.5 trillion, so there is nothing worth recovering anyway.

Analytics

Analytics is a stated requirement. The only rule that matters is this: analytics must never run on the redirect path.

Where AI Fits in This Design

After the main design, interviewers often ask one more question: where would AI fit in this system?

For a URL shortener, start with what does not need AI. Key generation, the redirect path, and caching follow fixed rules and finish in a few milliseconds. AI adds nothing there, and saying so is a strong answer.

The one real fit is screening. A short link hides its destination. That makes shorteners a favorite tool for phishing: tricking a person into opening a fake page built to steal information. So screen what people shorten. After a link is stored, a background worker sends its destination URL to a classifier, a model that labels the page as safe or suspicious. The worker writes that label to the link's row as one more flag.

Notice where this runs: after the write, never during the redirect. The redirect path already checks flags on the row, such as visibility and expiry. A suspicious flag joins the checks that already exist, so the redirect stays as fast as before.

Then say what happens when the model is wrong. A false positive, a safe page marked suspicious, disables a customer's working link. So a flagged link should show a warning page, or go to human review, not be deleted silently.

💡 In the interview: spend your time on key generation and the read path, and move quickly through everything else. The requirements, the estimates, and the API together should take about ten minutes. Two moments give the interviewer most of the information. The first is when you notice that a six-character key breaks the guessability requirement. It shows you check your own design against what you agreed, rather than reciting a known answer. The second is when you explain that KGS exists to move the uniqueness check off the request path. That is a general principle, not just a fact about URL shorteners. If you have time left, 301 versus 302 is the follow-up you are most likely to be asked. Have the analytics reason ready.

Key takeaway: a URL shortener is a small amount of data under a very uneven load, roughly a hundred reads for every write. The whole design follows from that. Pick a key length that actually satisfies the guessability requirement, which means seven base62 characters rather than the usual six. Pre-generate keys in a background service, so no write ever waits on a collision check. Hand keys out in blocks, so no two servers can collide. Serve reads from a cache in front of a partitioned database. Remember that a link's destination never changes, so an update can never make a cached entry wrong. The expiry is stored in the cached row, and a delete removes the key. Return 302 rather than 301 so clicks keep reaching you. Return 410 rather than 404 for expired links. Keep analytics on a queue, so no redirect ever waits on it.