Design a Link Shortener

At 9:58 on results day, a state board's server shortens one long results URL. At 10:00 an SMS carrying sl.example/aB3x9Kq reaches 15 lakh Class 12 students; the full address would have eaten most of the 160 characters an SMS allows. Within a minute, phones in hostels, buses and kitchens tap the link, thousands every second. The results site is ready for them, but every tap passes through the shortener first. If its one database stalls, students stare at a spinner and blame the board. Seven characters stand between a student and a mark sheet, and this chapter makes them never fail.

You are building a free, public link shortener. Someone pastes a long URL and gets back a short link such as sl.example/aB3x9Kq; anyone who opens it lands on the long page. About 4 million links are created a day, they end up on posters, in SMS offers and in chats, and owners want to know how many people clicked. The results-day link is our running example: we follow it from its creation to its last click.

Before drawing any boxes, pin down what the service must do and how well. The results link from the opening makes each requirement concrete.

A link shortener maps a short code, the seven characters after the domain, to a long URL. It answers every visit to the code with an HTTP redirect: a tiny response whose Location header tells the browser where to go next. The browser follows it on its own, so the student never sees the shortener at all.

The functional requirements on the left are what users ask for; the non-functional ones on the right decide the design.

One requirement outranks the rest: reads dwarf writes, and every read must be fast and available. The board creates its link once; 15 lakh students open it. A broken short link also cannot be repaired after the fact, because nobody can recall an SMS or reprint ten thousand posters. How many reads does that add up to across the whole service? The next page sizes it.

Requirements say what to build; numbers say where to spend the effort. Assume 4 million new links a day, each opened about 100 times over its life, links kept for 5 years, and about 500 bytes per link (the data model page explains the 500). For peaks, assume 5 times the average, which covers SMS blasts and results-day posters.

Here is the full set, including the numbers that size the cache and the network:

One number drives the design: about 23,000 redirects a second at peak. Storage is a few terabytes, bandwidth is small because a redirect carries only a header, and the hot set fits in one machine's memory.

Two checks on the reasoning. Why do average redirects equal creates times 100? Once the service has run for a while, each day's clicks equal the lifetime clicks of one day's links. And where does the results link fit? If half of 15 lakh students tap within two minutes, that is 7.5 lakh taps in 120 seconds, about 6,000 a second. That fits inside the peak, but it all lands on one code, a problem the caching page returns to.

The numbers say the redirect is the call that matters, so the API keeps it as small as possible. Three kinds of call cover the product: create a link, follow a link, and inspect or delete a link. Creation and management live under /api/v1 and need an API key or a signed-in user. The redirect is a bare path on the short domain, so links stay short.

POST /api/v1/links
Authorization: Bearer <token>
Idempotency-Key: 7c1e9f52
{ "long_url": "https://results.example.in/2026/class-12?roll=123456",
  "expires_at": "2027-03-31T00:00:00Z" }   # optional, as is "custom_alias"
→ 201 Created
{ "code": "aB3x9Kq", "short_url": "https://sl.example/aB3x9Kq" }

GET /aB3x9Kq
→ 302 Found
Location: https://results.example.in/2026/class-12?roll=123456

GET /api/v1/links/aB3x9Kq/stats
→ 200 OK { "clicks": 1204311, "last_7_days": [1150220, 30410, 9120, 6005, 4210, 2600, 1746] }

DELETE /api/v1/links/aB3x9Kq
→ 204 No Content

The redirect has no body: the browser follows the Location header on its own.

Four details in that sketch each prevent a real failure:

• Idempotent creation: the board's server times out at 9:58 and retries. With the same Idempotency-Key, it gets the same code back instead of a second link, so the SMS and the stats point at one record. The service remembers each key for about a day.
• Validation: accept only http and https URLs up to a sensible length, such as 2,000 characters, and refuse links that point back at the shortener, so nobody builds redirect loops.
• Clear errors: 409 Conflict when an alias is taken, 404 Not Found for unknown codes, 410 Gone for expired or disabled links, and 429 Too Many Requests when a client creates too fast.
• Cheap stats: the stats call reads pre-counted daily rows, never raw click events, so it stays fast for a link with a million clicks.

With the calls fixed, the store must answer one question millions of times: for this code, what is the long URL? That is a lookup by primary key, with no joins and no range scans.

A key-value store fits links well: the code is the key, the record is the value, and the store spreads keys across machines and keeps three copies, as in Designing a Key-Value Store. "List my links" needs a lookup by owner, which links_by_owner, keyed by owner_id, answers without scanning every link.

A relational database also works at this size: 3.7 TB split by code across a handful of shards, each with read replicas. The choice leans relational when owners need rich queries over their own links, such as filters by campaign. It leans key-value as reads grow, because a key-value store adds machines without re-sharding by hand. Either way, click counts live in their own table: they change constantly, and the redirect must never wait on them.

Where did 500 bytes per link come from? A record holds a 7-byte code, a long URL of 100 to 200 bytes on average, and about 40 bytes of ids, dates and flags. Rounding up to 500 bytes leaves room for the owner table, indexes and the store's own overhead.

The pieces are known; now arrange them so the busy path stays short. Split the system by how it is used. A small create service handles about 46 writes a second, using blocks of numbers from an ID range service that the deep dives explain. A separate, widely replicated redirect service handles thousands of reads a second, mostly from a cache. A load balancer sends each request to one or the other by path, and both share the link store. Here is results morning on those boxes.

The store served one read for the whole crowd. The redirect path never generates anything, never writes to the link store and never waits for analytics, so you scale it by adding redirect servers and cache nodes. Splitting the paths also contains failures: a bad release of the create service leaves every existing link working.

Clicks are counted off the hot path. Consumers read the click queue, a message queue as in Message Queues, add up clicks per code in memory for a few seconds, and write one batched increment per code into daily_clicks. Without batching, the results link would send about 6,000 writes a second to its row for today, the hot-key problem from Sharded Counters. With it, that row takes one write every few seconds from each consumer.

The paths are drawn; the hardest questions are about the code itself, starting with its length. A code is written in base62: the digits 0 to 9, the letters a to z and the letters A to Z. Think of a car's odometer with 62 symbols on each wheel instead of 10. Every extra wheel multiplies the count by 62, so a code of length L can take 62^L values.

Here is how long each length lasts at 4 million links a day:

Six characters would last decades if codes were used one after another. We still choose seven: codes spread at random through the space need room, growth needs headroom, and one more character costs little to type. Seven characters also make guessing hard: with 7.3 billion links in 3.5 trillion slots, a random guess finds a real link about once in 500 tries, so failed lookups still need a rate limit.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base62(n, width=7):
    digits = []
    while n > 0:
        n, r = divmod(n, 62)
        digits.append(ALPHABET[r])
    return "".join(reversed(digits)).rjust(width, "0")

to_base62(125)         # "0000021", because 125 = 2 × 62 + 1
to_base62(62**7 - 1)   # "ZZZZZZZ", the last 7-character code

Padding with the alphabet's zero keeps every code exactly 7 characters, whatever the number.

Printed links get typed by hand, and 0 and O, or l, 1 and I, are easy to confuse. Some services drop such look-alikes and use about 58 characters; seven of them still give 58^7 ≈ 2.2 trillion codes. Case matters too: aB3x9Kq and ab3x9kq are different codes, so no proxy or CDN in front of the service may lowercase paths.

Picture the ticket counters at a busy railway station. Either every clerk checks a shared register before issuing a number, or each clerk collects a booklet of pre-numbered tickets in the morning and returns only when it runs out. Code generation offers the same choice. There are three standard approaches:

The table hides how early hashing collides. By the birthday effect, the same maths that makes two people in a class of 23 likely to share a birthday, random 7-character codes are likely to produce their first collision after only about 2.2 million links: roughly 1.2 times the square root of 3.5 trillion. That is before the end of day one, so every hashed insert must be a conditional write with a retry.

A single counter never collides, but every create writes one shared row, and consecutive codes let anyone walk through every link. Ranges keep the counter but take it off the hot path, like the clerk's booklet. Ready-made IDs do not fit: a random UUID needs 22 base62 characters, and a 64-bit time-ordered ID from Unique IDs and Sequencers needs 11, while 7 characters hold only about 42 bits.

What does a collision cost in practice, and what does a range save? The next page watches both.

Here are both approaches on the same create server, five years in, when 7.3 billion codes are already taken. Count the calls each create makes.

Hashing pays for uniqueness on every create, and the bill grows as the table fills. A range pays once per 1,000 creates: at 230 creates a second across the whole fleet, that is one block request about every 4 seconds. Prefetching at half use takes even that call off the create path, so a create is always exactly one write.

Hashing keeps one real advantage: the same URL gives the same code, which saves a lookup when deduplication matters. For a public shortener with per-owner stats and deletes, that is rarely wanted, as the check questions show. Ranges win, but they add a service every create server depends on. The next page asks what it stores and how it fails.

Ranges move the shared counter off the hot path, but every create server now depends on the range service. So what does it store, and what happens when part of it fails?

Its only state is the next free number. That number lives in a small consensus group of 3 or 5 nodes, as in Consensus, Leader Election and Coordination, so losing one node changes nothing. A block is taken with compare-and-set: a write that says "set next to N + 1,000, but only if it still equals N". The group applies it only if the condition holds.

That one rule handles each awkward case:

• Two copies of the service race for the same block: one write succeeds; the other's condition fails, so it rereads N and takes the next block.
• A reply is lost and the create server asks again: it gets a fresh block, and the first one is simply never used.
• A create server crashes halfway through its block: the rest of the block is skipped.

In every case ranges may waste numbers but never hand one out twice, and with 3.5 trillion codes, waste costs nothing. Block size trades waste against outage tolerance. A server that fetches its next block at half use, with blocks big enough to outlast the longest range-service outage you plan for, never notices a short outage, and a crash wastes at most one block.

Codes are settled. The next question is what the redirect response itself should say.

A code now maps to a URL; the response that sends the browser on decides who remembers that mapping. The redirect is one HTTP response with a Location header, and its status code sets the default for caching.

A 301 is like telling a student the exam hall has moved for good: they never ask again. A 302 is a notice on the door: they read it every time. The difference shows in four places:

Two details sharpen the table. First, a 301 does not hide all clicks: each browser still makes its first visit, so a results link tapped once by each of 15 lakh phones loses little counting. What a 301 truly loses is control: a link you disable keeps working from every browser that cached it, and you cannot purge a browser. Second, headers override the default either way: a 301 sent with Cache-Control: max-age=300 is remembered for only 5 minutes, and a 302 is cached only when its headers allow it.

So a shortener that promises counts, expiry and takedowns returns 302, or 307, which behaves the same for a GET and also tells the browser to keep the request method. The advice flips for permanent links with no statistics, where a 301 saves traffic, and for marketing links whose owners want search engines to credit the destination, which they generally do for a 301. Return 302 when you must be able to change your mind about a link.

A 302 sends every tap to us, all 23,000 a second at peak, so the server side must answer from memory. The redirect service uses cache-aside, as in Distributed Caches: look up the code in the cache, and on a miss read the store and fill the cache with a TTL of about an hour.

Popularity is extremely skewed. A results link or a forwarded chat message gets lakhs of clicks while most links get a handful, so a 10 GB cache of about 20 million recent and popular links absorbs most reads. Skew also creates the opposite problem: the results link sends about 6,000 taps a second to one key, which lives on one cache node.

Four rules handle the edges:

• Hot keys: keep a tiny in-process cache on each redirect server, with a TTL of a few seconds. The results link is then answered from every server's own memory, no cache node takes the whole burst, and a disabled link still stops within seconds.
• Negative caching: remember unknown codes for a minute, so a mistyped code on a poster cannot hammer the store. Random guessing needs the 404 rate limit instead, because every guess is a new code.
• Confirm before caching a miss: replicas can lag a second or two, so a brand-new link may look missing. On a miss for a well-formed code, read the primary copy before answering 404, or a fresh link would fail for a whole minute.
• Invalidate on change: when a link is deleted, disabled or expires, delete its cache entry, and never cache a link past its expires_at.

With these rules, the store sees mostly first clicks on new links, a small fraction of the 23,000 a second. The design is complete; the next part asks what breaks it.

Walk the design part by part and ask what happens when each piece fails or overloads, ideally at 10:00 on results morning. The guiding rule is simple: protect the redirect path first. The table lists the usual suspects:

Every row has the same shape: the redirect path may slow down but never breaks, while creates and analytics are allowed to pause. That ordering is the design's priority list written as failure handling.

Every choice so far bought something and cost something. Naming both is what turns a list of boxes into a design you can defend and change later:

• 302 over 301: more traffic to our servers, in exchange for accurate counts and takedowns that work within seconds.
• Ranges over hashing: no collision checks and one write per create, at the cost of a small consensus-backed service and a scramble to hide the order.
• Eventual analytics: click counts lag by seconds or minutes so that redirects stay fast.
• Seven characters: one more than strictly needed, for headroom and harder guessing.

The bill is modest, and it is not link storage. The redirect fleet and the click pipeline dominate it: 400 million click events a day at about 200 bytes each is roughly 30 TB of raw data a year, far more than the 3.7 TB of links stored over five years. Keep raw clicks for a few weeks and daily totals for good. Network egress, the big bill for media products, barely registers here, because a redirect is a few hundred bytes and peak traffic is about 100 Mbps.

One more trade-off hides in plain sight: we chose a key-value store for the hot path and accepted that "list my links" needs a second table kept in step. That is the usual price of designing storage around the busiest question.

Optional: custom aliases, expiry and abuse, which a public shortener needs once the core works.

Next year the board wants sl.example/hsc26, not aB3x9Kq, so students can type it from a newspaper. A custom alias is a code the user chose, stored in the same table, so lookups do not change. Creating one must be race-free: if a coaching centre asks for hsc26 at the same moment, only one request may win.

put_if_absent(key = "hsc26", value = { long_url, owner_id, is_custom: true })
  inserted    → 201 Created
  key exists  → 409 Conflict: alias taken; suggest hsc26-results or hsc2026

A conditional write, insert only if the key is absent, lets the store pick exactly one winner.

• Reserve words: block aliases such as api, admin, login and help, plus offensive words and lookalikes of official bodies.
• Keep generated and custom codes apart: a generated code could one day equal someone's alias. Either insert generated codes with the same conditional write and skip taken ones, or keep exactly 7 characters for generated codes and require aliases of any other length.
• Limit aliases: allowed characters only, 4 to 30 characters long, and a cap per account so nobody squats on thousands of names.

Expiry is a field, expires_at. The redirect service checks it on every read and answers 410 Gone once it has passed, and cache entries never outlive it. A background job later deletes or archives expired rows in small batches; until it runs, the check on read keeps behaviour correct.

Results day draws fraud as well as students. Within hours, fake "results" links that ask for a fee or a login spread by SMS, and a short link hides where it leads. Such links harm users, and they can get the shortener's whole domain blocked by email and SMS filters, breaking every honest link with it. Each threat has a matching defence:

Most defences sit on the create path, where traffic is small and a check costs little; only the takedown touches the redirect path, and 302 is what makes it fast.

Some services add an optional preview page, such as sl.example/preview/aB3x9Kq, that shows the destination before redirecting. Careful users can check a link first, and the abuse team gets a softer tool for suspicious links: a warning page instead of a redirect.

A 45-minute round leaves about 40 minutes of design once introductions and your own questions are done. Here is how to spend them on a link shortener.

Pick code generation if they ask how two servers avoid the same code, or what happens when the ID service dies. Pick 301 versus 302 and caching if they ask about latency, counts or taking down a bad link. If they ask for more scale, go to edge-cached redirects, the first drill question.

Once your design is on the board, interviewers change one thing to see how you adapt. Try each question before opening the answer.