Design a URL Shortener

By the end of this lesson you will have designed a complete URL shortener, the classic first system design question, using the eight-step method from the introduction. You will generate short codes with base62, hand out IDs to many servers without collisions, and cache redirects so they stay fast at peak.

Step 1: requirements

A URL shortener turns a long link into a short one, such as sho.rt/aB3x9Kq, and redirects anyone who opens the short link to the original. Think of it like a token number at a sweet shop counter: the token is short and easy to call out, and it maps to a full order written in the shop's book.

Functional requirements (agreed with the interviewer):

• Create a short link for a long URL, optionally with a custom alias such as sho.rt/diwali-sale.
• Redirect a short link to its long URL.
• Links may have an expiry date.
• Basic click counts per link (nice to have).

Non-functional requirements:

• Redirects must be very fast (p99 under 50 ms at the server) and highly available: a broken redirect breaks every campaign that used it.
• Short codes must be unique and hard to guess in bulk.
• The system is read-heavy: links are created once and opened many times.

Step 2: estimates

DAY = 86_400
new_links_per_month = 30_000_000
reads_per_link = 100                       # read:write ratio
bytes_per_link = 500                       # long URL, code, owner, timestamps
years = 5

writes = new_links_per_month / (30 * DAY)
reads = writes * reads_per_link
total_links = new_links_per_month * 12 * years
storage_gb = total_links * bytes_per_link / 1e9

print(f"Writes: {writes:,.0f}/s average, ~{writes * 3:,.0f}/s peak")
print(f"Reads : {reads:,.0f}/s average, ~{reads * 3:,.0f}/s peak")
print(f"Links in {years} years: {total_links:,} -> {storage_gb:,.0f} GB")

for length in [6, 7, 8]:
    print(f"base62 codes of length {length}: {62 ** length:,} possible")

Writes: 12/s average, ~35/s peak
Reads : 1,157/s average, ~3,472/s peak
Links in 5 years: 1,800,000,000 -> 900 GB
base62 codes of length 6: 56,800,235,584 possible
base62 codes of length 7: 3,521,614,606,208 possible
base62 codes of length 8: 218,340,105,584,896 possible

What these numbers say:

• Writes are tiny. Reads are a few thousand per second at peak: easy for a cached service.
• 900 GB over five years fits comfortably in a sharded or even a single well-sized key-value store.
• Base62 (digits, lowercase and uppercase letters) with 7 characters gives over 3.5 lakh crore codes, far more than 180 crore links. 7 characters is enough.

Step 3: API

POST /v1/links HTTP/1.1
Host: api.sho.rt
Authorization: Bearer <token>
Content-Type: application/json

{"long_url": "https://shop.example.in/sale?utm_source=sms", "alias": null, "expires_at": "2027-01-31"}

HTTP/1.1 201 Created
Content-Type: application/json

{"code": "aB3x9Kq", "short_url": "https://sho.rt/aB3x9Kq"}

GET /aB3x9Kq HTTP/1.1
Host: sho.rt

HTTP/1.1 302 Found
Location: https://shop.example.in/sale?utm_source=sms
Cache-Control: private, max-age=90

301 or 302? A 301 Moved Permanently lets browsers cache the redirect forever, which saves load but means later clicks never reach you (no click counts, no way to change or expire the link). A 302 Found (or 307) sends every click through your servers. Since we want counts and expiry, we choose 302 with a short cache time.

Step 4: data model

One main table, looked up only by code:

Every read is "get by code", so a key-value store or a relational table with the code as primary key both work. Sharding, if ever needed, uses code as the partition key (Sharding & Partition Keys). Click counts go to a separate analytics pipeline, not this table.

Step 5: generating short codes

There are three common approaches:

1. Hash the URL (for example SHA-256) and take 7 characters. The same URL gives the same code, but different URLs can collide, so you must check and retry.
2. Random codes, checked for uniqueness on insert (a unique constraint). Simple and hard to guess; collisions are rare while the space is mostly empty.
3. A unique counter, encoded in base62. No collisions at all. But a single global counter is a bottleneck and makes codes guessable in sequence.

A neat version of option 3 avoids the bottleneck: a small ID allocator hands each app server a block of numbers (say 1,000 at a time). The server uses its block locally with no network calls, and asks for a new block when it runs out. If a server crashes, the unused numbers in its block are simply skipped.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62(n):
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

class BlockAllocator:                      # the central service, called rarely
    def __init__(self, start, block):
        self.next, self.block = start, block
    def take(self):
        first = self.next
        self.next += self.block
        return first, first + self.block

class AppServer:
    def __init__(self, name, allocator):
        self.name, self.alloc = name, allocator
        self.cur, self.end = allocator.take()
    def new_code(self):
        if self.cur == self.end:
            self.cur, self.end = self.alloc.take()
        n, self.cur = self.cur, self.cur + 1
        return base62(n)

alloc = BlockAllocator(start=62 ** 6, block=1000)     # start at 7 characters
s1, s2 = AppServer("app-1", alloc), AppServer("app-2", alloc)
print("app-1:", [s1.new_code() for _ in range(3)])
print("app-2:", [s2.new_code() for _ in range(3)])
print("app-1:", s1.new_code())

app-1: ['1000000', '1000001', '1000002']
app-2: ['10000g8', '10000g9', '10000ga']
app-1: 1000003

Sequential codes are guessable, which lets people walk through everyone's links. If links may be private, either use random codes or scramble the number with a reversible shuffle before encoding. Custom aliases are inserted with the same unique constraint; if the alias is taken, return 409 Conflict.

Step 6: high-level design

                    +-----------+
browser / app  -->  |    CDN    |  (optional: caches popular 302s briefly)
                    +-----+-----+
                          v
                   +--------------+
                   | Load balancer|
                   +------+-------+
           +--------------+---------------+
           v                              v
  +-----------------+            +-----------------+
  | Redirect service|            | Link API service| --- ID block allocator
  | (read path)     |            | (create path)   |
  +--------+--------+            +--------+--------+
           |  miss                        |
           v                              v
    +-------------+   fill       +------------------+
    | Redis cache | <----------- | Links DB (KV or  |
    +-------------+              | SQL, by code)    |
           |                     +------------------+
           +--> click events --> queue --> analytics store

The read and write paths are separate services, so a spike in redirects never slows link creation. Click counting is asynchronous: the redirect service drops an event on a queue and returns immediately (Message Queues & Event Streaming).

Step 7: deep dive on the hot read path

Link popularity is very uneven: one link in an SMS campaign can get lakhs of clicks in an hour, while most links are rarely opened. That makes caching extremely effective.

import random
from collections import OrderedDict

rng = random.Random(21)
links = 100_000
weights = [1 / (i + 1) for i in range(links)]          # a few links are very popular
clicks = rng.choices(range(links), weights=weights, k=50_000)

def hit_ratio(capacity):
    cache, hits = OrderedDict(), 0
    for code in clicks:
        if code in cache:
            hits += 1
            cache.move_to_end(code)
        else:
            cache[code] = True
            if len(cache) > capacity:
                cache.popitem(last=False)
    return hits / len(clicks)

for cap in [100, 1_000, 10_000]:
    print(f"LRU cache of {cap:>6,} links ({cap / links:.1%} of all): hit ratio {hit_ratio(cap):.0%}")

LRU cache of    100 links (0.1% of all): hit ratio 29%
LRU cache of  1,000 links (1.0% of all): hit ratio 50%
LRU cache of 10,000 links (10.0% of all): hit ratio 69%

Caching a small fraction of links absorbs a large share of clicks. With real campaign traffic, which is often even more concentrated, the share is higher. Expired links are checked on read (and removed by a background job), and a deleted or expired link must also be deleted from the cache.

Step 8: trade-offs and extensions

• 302 over 301: more load, but we keep analytics, expiry and the ability to block a link.
• Counter blocks over hashing: no collisions and no retries, but codes need scrambling to avoid guessing.
• Abuse: shorteners are attractive to spammers and phishers. Check new URLs against safe-browsing lists, rate-limit creation, and let users report links.
• Analytics: stream click events to a columnar store for per-day counts by city and device, never blocking the redirect.

Common mistakes

• Choosing 301 and then wondering why click counts stop.
• One global counter in one database row, which becomes a write bottleneck and a single point of failure.
• Hashing URLs without handling collisions.
• Counting clicks synchronously in the redirect path.
• Ignoring abuse and phishing.

Key points

• A URL shortener is read-heavy: tiny write rate, thousands of redirects per second at peak.
• Seven base62 characters give trillions of codes, enough for years.
• Block-based ID allocation avoids both collisions and a central bottleneck; scramble IDs if guessing matters.
• Use 302 redirects when you need analytics or expiry.
• Separate the read and write paths, cache hot links, and count clicks asynchronously.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62(n):
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

def decode62(code):
    n = 0
    for ch in code:
        n = n * 62 + ALPHABET.index(ch)
    return n

for n in [0, 61, 62, 3_843, 56_800_235_584]:
    code = base62(n)
    print(f"{n:>14,} -> {code:8} -> {decode62(code) == n}")

             0 -> 0        -> True
            61 -> Z        -> True
            62 -> 10       -> True
         3,843 -> ZZ       -> True
56,800,235,584 -> 1000000  -> True