Worked Example: Designing a URL Shortener

The chapter How to Structure Any Design Interview Answer gave you a checklist: clarify, estimate, sketch, find the bottleneck, discuss the trade-off. This chapter runs that checklist on one real question, start to finish, talking the way you would in the room. The question is a classic warm-up: design a URL shortener, like bit.ly or TinyURL. A user pastes a long address and gets back a short one, and anyone who opens the short one ends up on the long one.

Picture a company switchboard. Nobody remembers the direct line of the person they need, say 555-0142, so the company hands out short extensions such as 4417. You dial 4417 and the receptionist looks it up. She does not connect you herself. She says, "That is 555-0142, please call that number," and you make the second call yourself. A URL shortener is that receptionist for web addresses.

• -The short code, such as `abc123`, is the extension.
• -The long URL is the full phone number.
• -The receptionist is the server. She looks the code up in a table, which is the database, and replies with the real address.
• -Her reply, "call this number instead", is a **redirect**: a response whose only job is to point the browser somewhere else. The browser then makes the second request on its own.
• -A receptionist who keeps the most requested extensions on a sticky note by the phone is a **cache**.

Start by asking what the system must do, and what it must not try to do. Say your assumptions aloud: they are part of the answer.

• -**Functional** (what it does): a user submits a long URL and gets a short one back. Opening the short URL sends the visitor to the original. Optional extras: custom aliases, links that expire, click counts.
• -**Out of scope** (say this out loud): user accounts, editing a link after it is created, and spam or abuse detection. Naming what you are not solving is itself a signal.
• -**Non-functional** (how well it does it): a redirect must feel instant, under 100 ms, and the service must almost never be down, because if it breaks, every link ever shared through it breaks too. Creating a link may be a little slower than following one.

An estimate exists to show where the hard part is, so the arithmetic only needs to be quick and roughly right. Assume 100 million new links a month. A link is created once but clicked many times, so assume 100 clicks (reads) for every creation (write), a ratio of 100:1. A month has about 2.6 million seconds (30 days × 86,400 seconds). Assume traffic at its busiest is 5 times the average, and that each stored link takes about 500 bytes: the long URL, the short code, a date and a little more.

Start with the simplest design that could work, then add only what the numbers demand. One table maps each short code to its long URL. The diagrams show the two paths through the system: creating a link, and following one.

On the read path the app server checks the cache first, and only on a miss reads the database and saves the answer in the cache. This is the cache-aside pattern from the Caching Strategies chapter. The reply to the browser is a redirect: the long URL, and the instruction to go there.

How much does the cache help? Clicks are not spread evenly: a small number of popular links get most of them. So suppose 95 of every 100 clicks find their code already in the cache, a 95% hit ratio (the chapter Why Caching Works explains hit ratios). Then only 5% of the 20,000 peak reads, which is 1,000 reads a second, ever reach the database.

Try it with these numbers: 20,000 reads a second at peak and a 95% hit ratio. Move the hit ratio to see how much the cache shields the database, then switch the cache off to preview the failure described in Step 5.

The estimate said reads are the hard part, and the cache handles those. The one decision the numbers cannot settle is how to create a short, unique code for each new link, which is why interviewers usually push here. Seven characters is the usual target: short enough to type, long enough to last. Use letters and digits: 0-9, a-z and A-Z make 10 + 26 + 26 = 62 characters, which is called base62. Seven of them give 62 multiplied by itself 7 times (62^7), about 3.5 trillion possible codes, far more than the 6 billion links we expect.

A hash function turns any text into a fixed-length scrambled value, and the same text always gives the same value. Hash the long URL, write the result in base62 and keep the first 7 characters as the code. The base62 step matters. Hash values are usually written in hexadecimal, which has only 16 characters, and 7 of those give just 16^7 = 268 million codes, fewer than the 6 billion links we expect.

The weak spot is collisions: two different URLs can end up with the same 7 characters. So before saving, the server must check whether the code is already taken and, if it is, try again. That check is an extra database read on every write, and it fails more often as the table fills. With 6 billion of the 3.5 trillion codes used, about 1 new code in 600 collides.

The alternative is to number the links 1, 2, 3 and so on, and write each number in base62. The digits 0-9 stand for 0 to 9, a to z for 10 to 35, and A to Z for 36 to 61. Link 125 becomes `21`, because 2 × 62 + 1 = 125, and link 1,000,000 becomes `4c92`. Two links never get the same number, so there are no collisions and no "is it taken?" check. Codes also stay short: even the 6-billionth link needs only 6 characters, and 7 characters last until 3.5 trillion.

The catch is not speed, since 40 new links a second is nothing for one counter. It is that several app servers need numbers from the same counter. If every create request asks the counter for the next number, then when the counter is down nobody can create a link, and every create pays a network trip to it. This is the ticket server from the Generating Unique IDs at Scale chapter, with the same weakness: one machine that everything depends on.

The standard fix is to hand out numbers in blocks. Each app server asks the counter for a block of 1,000 numbers, say 52,000 to 52,999, and the counter then moves on so nobody else is given those. The server hands out numbers from its own block with no network call, and comes back only when the block runs out.

Here is the arithmetic. With 4 app servers sharing 40 creates a second, each uses 10 numbers a second, so a block lasts 100 seconds and the counter is asked once every 25 seconds in total. It even survives a short outage: a server with 600 numbers left can keep creating links for another 60 seconds. If a server crashes, the unused part of its block is simply skipped, and gaps are harmless because codes need to be unique, not consecutive.

One more cost: consecutive numbers make guessable codes. Someone can try `4c93`, then `4c94`, and read every link, and the numbers also reveal how many links you create. A common remedy is to scramble each number with a reversible mixing step before writing it in base62, so neighboring links get unrelated codes and the no-collision guarantee stays.

Every choice costs something. Three trade-offs are worth saying out loud.

• -**301 or 302 redirect?** Back at the switchboard: a 301 means "moved permanently", so the browser writes the long address in its own address book and never asks you again. Repeat clicks cost you nothing, but you can no longer count them or change where the link points. A 302 means "moved temporarily": the browser asks you every time, which costs a request per click and keeps you in control. A service that wants click counts needs a 302.
• -**Consistency.** If you chose hashing, the "is this code taken?" check must see the latest data, because two requests that both see a code as free at the same instant would both claim it. That is strong consistency, and it means reading from the primary database. The counter approach never needs the check. What can lag is the spread of a brand-new link to replicas and caches: if a replica is 2 seconds behind, the first click on a link made 1 second ago may get "not found". That is eventual consistency, and for a short link it is an acceptable trade, not a correctness bug.
• -**The cache goes down.** With a 95% hit ratio the database sees 1,000 reads a second at peak. Without the cache, all 20,000 fall through: 20 times more. A database that was comfortable at 1,000 slows down, and then everything waiting on it slows too, including creating links. There are two defenses. Run the cache as several nodes, so one failure loses only a share of it. And shed load: let through only as many lookups as the database can take and return a fast error to the rest, which beats letting every request wait until all of them fail. This is the cascading failure from the Circuit Breakers chapter.