Case study: URL shortener

"Design a URL shortener" is one of the most common design questions. It looks small. A user gives a long web address and gets a short one. When anyone opens the short address, they go to the long one. The question tests whether you can put the basic parts together: estimate, IDs, cache, index and load balancer.

A weak answer draws boxes and says "use a hash" and "add a cache". A strong answer starts from numbers. It shows how many requests arrive, how the short code is made, and what happens on one click. It says why one database is enough today, and which number would make you split the data.

At SDE-1 level you should explain create and redirect. At SDE-2 level you should estimate the load and choose the ID and the cache with numbers. At SDE-3 level you should also say what breaks first when traffic grows.

Think of a cloakroom at a wedding hall. You give your coat and get a small ticket with a number. Then you show the ticket and get the coat. A URL shortener is the same. A URL is a web address. The long URL is the coat. The short URL is the ticket. The service keeps the pair and gives back the long address when someone shows the short one.

What we build

1. Create. A user sends a long URL and gets a short URL. The user may also ask for a name of their own (an alias) and an end date.
2. Redirect. When someone opens the short URL, the browser goes to the long URL.
3. Count clicks. The owner can see how many people clicked.

Speed matters most for the redirect, because a person waits for it. A short link must never lead to the wrong address.

There are two calls (lesson 9). POST /links sends the long URL and returns 201 Created with the short URL. If the alias is taken, it returns 409 Conflict. GET /{code} is the click. It returns 302 Found with a Location header that holds the long URL (lesson 7), or 404 Not Found for an unknown code.

The data is one table, links. Its columns are the code (the part after the slash), the long URL, the creation time, an optional end time, and the owner. Every click looks up one row by its code.

Making the short code

Write the code in Base62 (lesson 23): 62 symbols, which are digits and small and capital letters. Seven symbols give 62 to the power of 7 = 3,521,614,606,208 codes, about 3.5 trillion. There are three ways to choose the code.

1. Counter ranges (lesson 23). Each app server takes a block of 1,000 numbers from one central counter and turns each number into Base62. No clash is possible. The cost: codes come in order, so anyone can try the next code and read all links one by one. That is fine for public links and bad for private ones.
2. A random code. The server picks 7 random symbols. Nobody can guess the next one. A clash is possible, so the table has a unique constraint on the code (lesson 22). The database refuses a second row with the same code. On a refusal, the server picks a new code and tries again.
3. A hash of the long URL. A hash turns the URL into a number, and you keep the first 7 symbols. Two different URLs can give the same 7 symbols. Also, the same URL always gets the same code, so two users cannot have separate click counts. You still need the unique constraint and a retry, so this way has no gain over a random code.

A user's own alias goes into the same column. The unique constraint decides who is first, and the loser gets 409.

The redirect and the cache

The path of a click is: Browser -> Load balancer (lesson 28) -> App server -> Cache -> Database. The app servers keep no state, so the load balancer can use any of them.

The app uses cache-aside (lesson 32). It reads the cache with the code as the key. On a miss it reads the database and stores the answer. A link almost never changes, so a long TTL is safe. The TTL of an entry must never be longer than the time left before the link ends. After the end time, a click returns 404 Not Found. When a link is edited or deleted, the app writes the database first and then deletes the cache entry. When a link is created, the app also writes it into the cache, so the first click is already a hit. The first minutes after sharing are often the busiest.

If thousands of people open one new link at once and its entry is missing, you get a stampede (lesson 35). Request coalescing makes one request load the entry while the others wait. Programs that guess codes also try codes that do not exist. Each one is a miss and costs a database lookup. The fix is to store "not found" in the cache for a short time, for example 60 seconds. If someone creates that code in the meantime, the create step overwrites the "not found" entry.

Click counts are a trap. A write to the database for each click is a heavy load. Keep a counter in Redis with INCR (lesson 37), and let a small job add the totals to the database from time to time.

Which redirect code? A 301 lets the browser remember the target and skip our server next time. We would lose counts and the chance to change the target (lesson 7). We use 302.

The index

A click runs SELECT long_url FROM links WHERE code = 'aB3xY9Z'. The primary key on code gives a B-tree index (lesson 20). With 300 entries in a page, 3 levels reach 27,000,000 entries and 4 levels reach 8,100,000,000. A lookup reads 4 index pages and then the row. Without the index the database would scan every row. To list "my links", add a composite index on (owner_id, created_at). It costs one more index update for each new link.

Random codes land on random places in the index. Lesson 23 says this slows inserts when the table is big. The write rate here is low, so this is acceptable.

When would you split the data?

The other choice is to split the table into parts. Each part lives on its own database server. A rule picks the part from the code. For example, take a hash of the code (lesson 28), divide it by the number of parts, and use the remainder as the part number. Every click then asks only one server.

Splitting costs a lot. A query over all parts, such as "my links", must ask every part, or you keep a second table. Changing the number of parts means moving data. So do not split until a number forces you. One server has three limits: disk space, CPU, and memory for the index. The worked example finds each limit.

Assumptions (made up to teach with, not real traffic):

• 100,000,000 (10 crore) new links a month, and 1,000,000,000 (100 crore) clicks a month. That is 10 clicks for each new link.
• We keep links for 5 years, which is 60 months. Peak factor is 3 (lesson 14).
• A row takes 500 bytes, with its index entries. We keep one copy of the data, so the storage formula of lesson 15 has no copies factor.
• The database server has 8 cores, which is 8,000 ms of CPU per second. We plan for 70% busy. A read that reaches the database costs 4 ms of CPU, and a write costs 8 ms.
• One database server holds at most 8 TB of data on its disks. A cache server has 64 GB of memory. A cache entry takes 150 bytes. The hit rate is 90%, because most clicks come soon after a link is shared.

Step 1: requests per second. A 30-day month has 30 x 86,400 = 2,592,000 seconds.

• New links = 100,000,000 / 2,592,000 = 38.6 per second. At peak: 38.6 x 3 = 116.
• Clicks = 1,000,000,000 / 2,592,000 = 385.8 per second. At peak: 385.8 x 3 = 1,157.

Step 2: storage and the code.

• Rows = 100,000,000 x 60 = 6,000,000,000.
• Storage = 6,000,000,000 x 500 bytes = 3,000,000,000,000 bytes = 3 TB. The long URLs alone take 6,000,000,000 x 100 bytes = 600 GB.
• Seven symbols: 6,000,000,000 / 3,521,614,606,208 = 0.0017, which is 0.17%. This answers the predict box. Six symbols give 56,800,235,584 codes. Then 6,000,000,000 / 56,800,235,584 = 10.6% would be used, so about 1 new code in 10 would clash at the end. We choose 7.
• A new random code clashes with a chance of at most 0.17%, so a retry is rare. Over five years this is about 6,000,000,000 x 0.17% / 2 = 5,100,000 retries, which is under 1 retry in 1,000 inserts. The unique constraint catches each one.
• With counter ranges and blocks of 1,000, the central counter is called 116 / 1,000 = 0.116 times per second at peak.

Step 3: the database without a cache.

• Clicks = 1,157 x 4 ms = 4,628 ms. New links = 116 x 8 ms = 928 ms. Total = 5,556 ms, which is 5,556 / 8,000 = 69%. That is just under our 70% target, with no room to grow.
• If every click also wrote a count to the database: 1,157 x 8 = 9,256 ms, which is 116% of the server. This is why we keep click counts in Redis.

Step 4: the database with the cache.

• Misses = 1,157 x 10% = 115.7 per second, and 115.7 x 4 = 463 ms.
• Total = 463 + 928 = 1,391 ms, which is 1,391 / 8,000 = 17%.
• If the cache restarts empty, the load goes back to 69%. The database survives, but it has no room.
• Cache size: links shared in the last 7 days are 100,000,000 / 30 x 7 = 23,300,000. At 150 bytes that is 3.5 GB, which fits one cache server.

Step 5: the index.

• 6,000,000,000 rows / 300 = 20,000,000 leaf pages. At 8 KB a page that is 160 GB, too big for memory.
• The levels above hold 66,667 + 223 + 1 = 66,891 pages, which is 66,891 x 8 KB = 535 MB. That fits in memory.
• A lookup reads 3 pages from memory and 1 leaf page from an SSD at 0.15 ms (lesson 14). Then it reads the row, which is a second SSD read of 0.15 ms. So a lookup takes about 2 x 0.15 = 0.3 ms of disk time.
• Random inserts at 116 per second read 116 x 0.15 ms = 17 ms of SSD time each second. That is nothing.

Step 6: a viral link. Assumption: a TV advertisement sends 50,000 clicks per second to one link. A database read takes 20 ms (lesson 31). If the entry is missing, 50,000 x 0.02 = 1,000 more requests arrive while the first one loads. That is 1,001 queries x 4 ms = 4,004 ms of CPU, all at once. It is half of the 8,000 ms that the database has in one second. With the entry written at creation, or with coalescing, there is 0 or 1 query.

Step 7: the limits of one server.

So the disk is the first limit, at about 2.7 times today's number of links. At that point you split the data into parts by the code. The CPU limit comes at 4 times today's load.

• A random code solves guessing and the need for a central counter. It costs a rare retry and a larger index spread. I would change to counter ranges when I want the shortest codes and no retry, and links are public.
• The cache solves a database at 69% load, which went to 17%. It costs memory (3.5 GB) and a delay before an edit or delete shows, unless the app deletes the entry. I would change the TTL if links change often.
• 302 solves counting clicks and changing the target. It costs one request to our server for every click. I would use 301 if I never count and never change.
• One database solves simplicity: no split, no moving data. It costs a single point of failure (lesson 28): if it stops, new links fail, and clicks fail on cache misses. I would split the data when the disk or the CPU reaches the limit in Step 7.

"Hash the long URL and keep 7 characters. Clashes will not happen." They happen. With 6,000,000,000 links and 3.5 trillion codes, about 5,100,000 inserts would clash. You still need the unique constraint and a retry.

"A URL shortener needs its data split over many servers from the first day, because it is for scale." The load here is 116 new links per second, and the database is 17% busy. A split would add work and no benefit. Split when a limit in Step 7 comes near.

"A 301 is always better, because it is faster." The browser then skips our server on repeat visits. Clicks are not counted, and a changed target does not reach that browser.

1. Name three ways to make the short code. Give one cost of each.
2. A shortener gets 50,000,000 new links a month and 2,000,000,000 clicks a month. Rows are 500 bytes and kept for 60 months. (a) What is the average number of clicks per second? (b) How much storage is needed? (c) What share of the 7-symbol codes is used at the end?
3. A teammate wants to write the click count into the database on every click. The peak is 600 clicks per second, and a write costs 8 ms of CPU on a server with 8 cores. What do you say?