Building the shortener, one box at a time

Part of the free System Design course on LogicWiz, in the chapter: Design a URL shortener. The interactive whiteboard exercises and simulations run in the app.

Week 10: One box at a time

"We had one server and one database. The Diwali SMS went out, and the link inside it stopped working for everyone."

Anita, the morning after SwiftKart's first campaign

The simplest version, and where it breaks

Start with what a first-year student would draw: a client, one link service and one database.

A redirect arrives. The service reads the row for the code and answers with a redirect. A create arrives. The service makes a code and writes the row. It works, and for a small blog it is the right answer.

Now apply the numbers from the last lesson. At peak there are 10,000 redirects a second. SwiftKart's working figure for a database is about 2,000 simple queries a second. That is five times too much, and one machine also means one failure ends everything.

Kabir asks Meera a question for every box she adds: "Which number made you draw it?" The rest of this lesson answers that question five times.

Spread the work: a balancer and several copies

The first fix is for the service. It keeps no data of its own, so any copy can answer any request. We call that stateless. A redirect needs no login and no memory of the visitor.

Assume one instance handles about 3,000 redirects a second. Four instances give 12,000, a little above the peak. If one fails, three still carry 9,000, so watch for overload and add a fifth if needed. In front of them sits a load balancer, a box with one address that spreads requests over the copies and skips a broken one. Run the balancer as a pair, so it is not a single point of failure (one part whose failure stops everything).

This step costs almost nothing, but it does not help the database. The four copies would still send 10,000 reads a second to it.

Earn the cache

A cache is a faster copy of data you already have. Here it is Redis, a store that keeps data in memory. The service looks in the cache first. On a miss (the code is not there), it reads the database and puts the answer in the cache. This pattern is called cache-aside: the service, not the cache, loads the data.

The numbers say it works. The hot set is about 2 GB, small enough for memory. If 95% of redirects are cache hits, the database sees 10,000 * 5% = 500 reads a second. That is comfortable.

Two details matter. First, a link's target never changes, so a cached entry goes stale only through expiry or a delete. So the cache entry's time to live (TTL, how long it stays before it is removed) is capped by the link's expiry, and a delete also removes the entry. Second, cache the answer "this code does not exist" for about a minute. A dead link on an old poster, opened thousands of times, then asks the database once a minute, not on every click. Random guesses are all new codes, so they still reach the database. Lesson three limits those per caller.

Meera's wrong belief: "Add more database replicas instead, they are simpler." Replicas would work, but you would pay for a cluster sized for the peak, and reads that go to disk hurt p99. A 2 GB cache is cheaper and faster.

The links store and the click path

The database holds 9 TB with three copies, and its only question is "which row has this code?". That suits a replicated key-value store: it spreads rows over machines by the code, keeps three copies, and does one thing well. Name the trade-off aloud: you lose joins and ad-hoc queries. A sharded relational database also works if you have a reason. Do not pick it only because it feels safer.

Two more boxes finish the picture.

  • Click path. Counting a click must never slow the redirect. So the service sends a small event to a queue (a durable waiting line) and does not wait for a reply. An aggregator reads the events, adds them up per minute and per day, and writes the totals to a stats store. The numbers lag a few minutes, which the requirements allow.
  • Code allocator. Creating a code needs a number nobody else has used. A small allocator hands each service instance a block of 1,000 numbers. The next lesson explains why.

Add monitoring for redirect p99, cache hit ratio and the rate of 404 answers, and the design is complete.

Walk one create and one redirect

Create. The client sends a POST. The service takes the next number from its block, say 1,048,213, scrambles it, encodes it in base62 as seven characters, and writes the row. It returns 201 with the short URL. For a custom alias, it does a conditional insert (write only if the code is free). If the code exists, the answer is 409 and nothing is overwritten. A new alias also clears any cached "not found" for that code.

Redirect. One request, step by step:

sequenceDiagram
  participant C as Browser
  participant S as Link service
  participant R as Redirect cache
  participant D as Links store
  participant Q as Click queue
  C->>S: GET /aZ3k9Qx
  S->>R: look up code
  alt hit, about 95%
    R-->>S: long URL
  else miss
    S->>D: read by code
    D-->>S: long URL
    S->>R: fill with TTL
  end
  S-)Q: click event, no waiting
  S-->>C: 302 Location: long URL

Now build it. Start from the naive version and add what the numbers demanded.

📌 Summary: One server and database cannot take 10,000 redirects a second. Add a balancer with stateless copies, a cache for the 95% hot reads, a key-value store, and a queue so clicks never slow the redirect.

What Meera learns next

The picture is complete, but two boxes hide hard questions. Where do the codes really come from, and what does the redirect status do to your analytics? Next lesson: the deep dives, and what an interviewer asks when you finish drawing.

Check your understanding

  1. A single database can serve about 2,000 simple queries a second. The shortener peaks at 10,000 redirects a second. What is the first number-driven fix for the database?
  2. The click queue is down for ten minutes during a campaign. What should happen to redirects?
  3. A poster printed an old code that was deleted. Fans open it 2,000 times a second. The cache never has it, so every request reaches the database. What is the standard fix?
  4. A teammate says "use a relational database with joins, it is the safe choice". The shortener only ever looks up one row by its code. What is the best reply?