Chapter 29 of 33

Design a URL Shortener

A URL shortener turns a long link such as https://example.com/courses/dbms/normalization?utm_source=whatsapp&utm_campaign=gate2027 into something like https://sho.rt/EAVIhfD. Clicking the short link redirects the browser to the original. Services like Bitly and TinyURL handle huge numbers of such clicks every day. It is the most common "first" system design interview question because it is small enough to finish in 45 minutes, yet it touches almost every chapter so far: estimation, API design, ID generation, databases, caching, sharding and analytics.

We will follow the method from How to Approach a System Design Interview: requirements, estimation, API, data model, high-level design, deep dives, and trade-offs.

A URL shortener maps a short, unique code to a long URL. Creating a mapping is a write; following a short link is a read that returns an HTTP redirect to the long URL.


Step 1: Requirements

Functional

  1. Given a long URL, return a short URL that is unique.

  2. Visiting the short URL redirects to the long URL.

  3. Optional: users may choose a custom alias (sho.rt/gate-2027).

  4. Optional: links may expire.

  5. Optional: basic click analytics (count, country, referrer).

Non-Functional

  • Very low redirect latency (tens of milliseconds); the redirect sits in front of every click.

  • High availability for redirects: a dead shortener breaks every link ever shared.

  • Codes must not collide and should not be easily guessable in sequence.

  • Read-heavy: each link is created once and clicked many times.


Step 2: Back-of-the-Envelope Estimation

Assumptions (state them out loud in an interview): 100 million new links per day, 10 redirects per new link, links kept for 5 years, about 500 bytes per record, and peak traffic twice the average. The numbers below were computed with a script, using the method from Back-of-the-Envelope Estimation.

# Back-of-the-envelope numbers for the URL shortener
new_urls_per_day = 100_000_000          # 100 million new short links per day
read_write_ratio = 10                   # 10 redirects for every new link
years = 5
bytes_per_record = 500                  # code + long URL + timestamps + owner
peak_factor = 2

seconds_per_day = 86_400
write_qps = new_urls_per_day / seconds_per_day
read_qps = write_qps * read_write_ratio
total_records = new_urls_per_day * 365 * years
storage_tb = total_records * bytes_per_record / 1e12
reads_per_day = new_urls_per_day * read_write_ratio
cache_gb = 0.20 * reads_per_day * bytes_per_record / 1e9   # cache hottest 20% of a day's reads

print(f"Write QPS (avg / peak): {write_qps:,.0f} / {write_qps*peak_factor:,.0f}")
print(f"Read QPS  (avg / peak): {read_qps:,.0f} / {read_qps*peak_factor:,.0f}")
print(f"Records in {years} years: {total_records:,}")
print(f"Storage: {storage_tb:,.2f} TB")
print(f"Cache for hot 20% of daily reads: {cache_gb:,.0f} GB")
print(f"Read egress: {read_qps*bytes_per_record/1e6:,.1f} MB/s")
for n in (6, 7, 8):
    print(f"62^{n} = {62**n:,}  enough? {62**n >= total_records}")

Output:

Write QPS (avg / peak): 1,157 / 2,315
Read QPS  (avg / peak): 11,574 / 23,148
Records in 5 years: 182,500,000,000
Storage: 91.25 TB
Cache for hot 20% of daily reads: 100 GB
Read egress: 5.8 MB/s
62^6 = 56,800,235,584  enough? False
62^7 = 3,521,614,606,208  enough? True
62^8 = 218,340,105,584,896  enough? True

What these numbers tell us:

  • About 1,200 writes/s and 12,000 reads/s on average (about 23,000 at peak). Reads dominate, so caching matters most.

  • About 182.5 billion records and roughly 91 TB over 5 years (before replication). This does not fit comfortably on one database server, so we plan for sharding.

  • 6 base62 characters give 56.8 billion codes, which is not enough. 7 characters give about 3.5 trillion, enough with a large margin. So codes are 7 characters.

  • Bandwidth is tiny (a redirect response is small); it is not a bottleneck.


Step 3: API Design

POST /api/v1/urls
Authorization: Bearer <token>            (optional, for user-owned links)
Body: { "long_url": "https://...", "custom_alias": "gate-2027", "expires_at": "2027-03-01T00:00:00Z" }
201 Created
Body: { "code": "EAVIhfD", "short_url": "https://sho.rt/EAVIhfD", "expires_at": "..." }
409 Conflict  if the custom alias is taken;  400 Bad Request if the URL is invalid

GET /{code}
301 or 302 redirect   with header  Location: https://the-long-url
404 Not Found         if the code does not exist;  410 Gone  if it expired

301 or 302?

301 Moved Permanently

302 Found (temporary)

Browser caching

Browsers may cache it; repeat clicks may skip our server

Not cached by default; every click reaches us

Server load

Lower

Higher

Analytics accuracy

Undercounts repeat clicks

Counts every click

Changing or expiring the target later

Cached copies may ignore the change

Takes effect immediately

If analytics or editable links matter, choose 302 (or 307); if minimum load matters most, 301 (or 308). Say the trade-off; either answer is fine when justified. The POST and redirect paths should also be protected with rate limits per user and per IP (chapter Rate Limiting), because shorteners attract spammers.


Step 4: Data Model

Table: url_mapping
  code         CHAR(7)       PRIMARY KEY       e.g. "EAVIhfD"
  long_url     VARCHAR(2048)
  user_id      BIGINT        NULL
  created_at   TIMESTAMP
  expires_at   TIMESTAMP     NULL

Table: users        (user_id, email, plan, ...)          small, separate

The access pattern is almost entirely "look up one row by code". There are no joins on the hot path. Both a sharded relational database (MySQL/PostgreSQL, sharded by code) and a key-value / wide-column store (DynamoDB, Cassandra) fit well. A key-value store gives easy horizontal scaling; a relational store gives a simple unique constraint for custom aliases. Either is defensible, as discussed in SQL vs NoSQL Databases.


Step 5: High-Level Design

                                  +-----------------+
   Browser --- GET /EAVIhfD --->  |  Load balancer  |
   App ------ POST /api/v1/urls ->|  (+ rate limit) |
                                  +--------+--------+
                                           |
                       +-------------------+-------------------+
                       v                                       v
              +-----------------+                     +-----------------+
              | Redirect service|                     | Shorten service |
              | (stateless)     |                     | (stateless)     |
              +--+-----------+--+                     +--+-----------+--+
       1. get   |           | 2. miss                    |           | get an ID block
                v           v                            |           v
          +-----------+  +-------------------------+     |   +----------------+
          |  Redis    |  |  url_mapping database   |<----+   | ID range       |
          |  cache    |  |  (sharded by code,      | insert    | allocator      |
          | code->url |  |   replicated)           |           | (ZooKeeper/etcd|
          +-----------+  +-------------------------+           |  or a DB row)  |
                |                                              +----------------+
                | 3. publish click event (async)
                v
          +-----------+     +---------------------+
          |  Kafka    | --> | Analytics consumers | --> analytics store (columnar)
          +-----------+     +---------------------+

Redirect path (the hot path): look up the code in Redis; on a miss, read the database and fill the cache (cache-aside, from Caching); return the redirect; publish a click event to a queue without waiting for analytics. Splitting redirect and shorten services lets each scale independently: there are ten times more redirects.


Step 6: Deep Dive, Generating Unique Codes

This is the heart of the interview. There are three main approaches.

Approach A: Hash the Long URL

Compute SHA-256 (or MD5) of the URL, convert it to base62 and keep just 7 characters of it (for example, take the hash modulo 627, which keeps its last 7 base62 digits). The same URL always gives the same code, which deduplicates for free.

Problem: collisions. Truncating to 7 characters leaves 627 ≈ 3.5 × 1012 possible codes. By the birthday paradox, collisions appear far sooner than you might expect: with 1 million codes the chance that some pair collides is already about 13%, and with 10 million it is practically certain. So each insert must check "does this code exist with a different URL?" and on collision retry (for example, hash the URL plus a counter). It works, but every write needs a read-before-write or a conditional insert, and retries grow as the table fills.

Give every new link a unique integer ID and encode it in base62 (digits 0 to 9, a to z, A to Z). Unique IDs mean no collisions by construction, so no retry logic.

Worked example: encode 125. 125 ÷ 62 = 2 remainder 1. 2 ÷ 62 = 0 remainder 2. Reading remainders from last to first: digits 2, 1 → characters "2" "1" → "21", padded to 7 characters: 0000021.

A single global counter would be a bottleneck and a single point of failure. The standard fix is range allocation: a coordination service (ZooKeeper, etcd, or a single database row updated atomically) hands each app server a block of, say, 1,000 IDs. The server uses its block from memory and asks for a new block only when it runs out. If a server crashes, the unused part of its block is simply skipped; gaps are harmless.

Sequential IDs produce sequential codes (...0001, ...0002), which lets anyone enumerate everyone's links. A cheap fix is to shuffle the ID before encoding with a one-to-one function: multiplying by a constant that shares no factor with 627 modulo 627 maps every ID to a different code. This hides the order from casual guessing; it is not cryptographic secrecy, so private documents should still need authentication.

Approach C: Pre-Generated Keys (Key Generation Service)

A separate service generates random unused 7-character codes ahead of time and stores them in a "free keys" table. App servers take keys in batches and mark them used. This avoids both collisions and predictability, at the cost of an extra service and storage for unused keys, and care so that two servers never receive the same key.

Approach

Collisions

Predictable?

Extra components

Dedup same URL

Hash + truncate

Yes, need check and retry

No

None

Automatic

Counter + base62 (+ shuffle)

None

Only if not shuffled

ID range allocator

Needs a lookup if wanted

Pre-generated keys

None (if handed out carefully)

No

Key generation service + key store

Needs a lookup if wanted

Code: Base62, Range Allocation and Shuffling

This Python program implements approach B with two app servers sharing a range allocator, and shows the hash approach for comparison.

import hashlib
import threading

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)                      # 62
CODE_LEN = 7
SPACE = BASE ** CODE_LEN                  # 62^7 possible codes


def encode(num: int) -> str:
    """Base62-encode a non-negative integer, left-padded to CODE_LEN characters."""
    chars = []
    while num > 0:
        num, rem = divmod(num, BASE)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars)).rjust(CODE_LEN, ALPHABET[0])


def decode(code: str) -> int:
    num = 0
    for ch in code:
        num = num * BASE + ALPHABET.index(ch)
    return num


# Multiplying by a constant that shares no factor with 62^7 (= 2^7 * 31^7) is a
# one-to-one shuffle of [0, SPACE): consecutive IDs give unrelated-looking codes.
# This only hides the sequence from casual guessing; it is not encryption.
MULTIPLIER = 2_305_843_009_213          # odd and not divisible by 31
assert MULTIPLIER % 2 and MULTIPLIER % 31


def scramble(n: int) -> int:
    return (n * MULTIPLIER) % SPACE


class RangeAllocator:
    """Stands in for a coordination service that hands each app server a block of IDs."""

    def __init__(self, block_size: int):
        self.next_start = 1
        self.block_size = block_size
        self.lock = threading.Lock()

    def take_block(self) -> range:
        with self.lock:
            start = self.next_start
            self.next_start += self.block_size
            return range(start, start + self.block_size)


class AppServer:
    def __init__(self, name: str, allocator: RangeAllocator, store: dict):
        self.name, self.allocator, self.store = name, allocator, store
        self.block = iter(())

    def _next_id(self) -> int:
        try:
            return next(self.block)
        except StopIteration:                 # block used up: fetch a new one
            self.block = iter(self.allocator.take_block())
            return next(self.block)

    def shorten(self, long_url: str) -> str:
        n = self._next_id()
        code = encode(scramble(n))
        self.store[code] = long_url           # in reality: a conditional insert in the DB
        return code


if __name__ == "__main__":
    print("encode(125) =", encode(125), "  decode back =", decode(encode(125)))
    print("Largest 7-char code:", encode(SPACE - 1), "=", f"{SPACE - 1:,}")

    store = {}
    allocator = RangeAllocator(block_size=1000)
    a, b = AppServer("A", allocator, store), AppServer("B", allocator, store)
    urls = ["https://example.com/courses/dbms/normalization",
            "https://example.com/courses/os/paging",
            "https://example.com/courses/cn/tcp-handshake"]
    for server, url in [(a, urls[0]), (b, urls[1]), (a, urls[2])]:
        code = server.shorten(url)
        print(f"server {server.name}: {code} -> {url}")

    # Collision check: scramble must be one-to-one on a sample
    sample = {scramble(i) for i in range(1, 200_001)}
    print("distinct codes for 200,000 IDs:", len(sample))

    # Hash-based approach: keep 7 base62 digits of a SHA-256 digest (digest mod 62^7)
    def hash_code(url: str) -> str:
        digest = int.from_bytes(hashlib.sha256(url.encode()).digest(), "big")
        return encode(digest % SPACE)

    print("hash code:", hash_code(urls[0]), "(same URL -> same code every time)")

Output:

encode(125) = 0000021   decode back = 125
Largest 7-char code: ZZZZZZZ = 3,521,614,606,207
server A: EAVIhfD -> https://example.com/courses/dbms/normalization
server B: qfNSxkF -> https://example.com/courses/os/paging
server A: jbRqyvg -> https://example.com/courses/cn/tcp-handshake
distinct codes for 200,000 IDs: 200000
hash code: dn3mAPQ (same URL -> same code every time)

Server A used IDs 1 and 2 from its block (1 to 1,000) and server B used ID 1,001 from its own block, yet the codes look unrelated, and 200,000 consecutive IDs produced 200,000 distinct codes. Server A and B never coordinate per request, only once per 1,000 links.

Custom Aliases

Store custom aliases in the same table, with the primary key enforcing uniqueness: the insert either succeeds or fails with "duplicate key", which becomes 409 Conflict. To avoid a custom alias clashing with a future generated code, either reserve a different length or character pattern for aliases, or rely on the same uniqueness check for generated codes too.


Step 7: Deep Dive, Scaling Reads and Storage

  • Cache: link popularity is very skewed (a viral link gets millions of clicks). Caching the hot 20% of a day's reads needs about 100 GB, easily held by a small Redis cluster, with LRU eviction (chapter Cache Strategies & Eviction Policies). A cache hit ratio above 90% is realistic.

  • Negative caching: also cache "code not found" briefly, so bots requesting random codes do not hammer the database.

  • Sharding: shard by code using consistent hashing (chapter Consistent Hashing). Every lookup knows its shard from the code alone, so there are no scatter-gather queries.

  • Replication: each shard has replicas, which serve reads and take over on failure. Since a mapping never changes after creation, replication lag only affects a link in the first moments of its life; the shorten service can write through to the cache to cover that window.

  • CDN / edge: very popular redirects can even be served from edge locations close to users.


Step 8: Analytics, Expiry and Abuse

  • Analytics must never slow the redirect. The redirect service publishes a small event (code, time, country from IP, referrer, user agent) to Kafka; consumers aggregate counts into a columnar or time-series store. If the analytics pipeline is down, redirects still work (chapter Message Queues & Pub/Sub).

  • Expiry: check expires_at on read (lazy expiry, return 410) and run a periodic background job to delete or archive expired rows. Expired codes should generally not be reused, so old printed or shared links never point to someone else's content.

  • Abuse: shorteners are used to hide phishing links. Check new URLs against malware/phishing lists, rate-limit creation, and allow reporting and disabling of codes.


Common Mistakes

  • Choosing 6 characters without doing the maths. 626 ≈ 56.8 billion is less than the 182.5 billion links estimated here.

  • Hashing and truncating without handling collisions.

  • A single auto-increment counter with no plan for its failure or throughput limit.

  • Updating analytics synchronously in the redirect path (one database write per click).

  • Using 301 while also promising exact click counts or editable links.

  • Forgetting validation: only allow http/https targets, limit URL length, and block links to the shortener itself (redirect loops).


Interview Questions

1. How long should the short code be for 500 million new links per month kept for 10 years?

Total = 500M × 12 × 10 = 60 billion. 626 ≈ 56.8 billion is not enough; 627 ≈ 3.52 trillion is. So use 7 characters.

2. Why is base62 used instead of base64?

Standard base64 includes + and /, which have special meanings in URLs and would need escaping. Base62 uses only letters and digits, which are safe everywhere in a URL path. (URL-safe base64 replaces them with - and _, which also works.)

3. How do multiple servers generate unique IDs without contacting a central service on every request?

Range allocation: each server reserves a block of IDs (for example 1,000) from ZooKeeper, etcd or an atomic database counter, then assigns IDs from memory. Alternatives are Snowflake-style IDs (timestamp + machine ID + sequence), though those produce larger numbers and therefore longer codes.

4. The same long URL is submitted twice. Should it get the same code?

It depends on requirements. Returning the same code saves space but needs a lookup index on the long URL (or a hash-based design), and different users may want separate links with separate analytics and expiry. Many services give each user their own code. State the choice and its cost.

5. How would you keep redirect latency low worldwide?

Stateless redirect servers in several regions behind geo-DNS or anycast, a regional Redis cache in front of the database, read replicas per region (mappings are immutable, so replication is simple), asynchronous analytics, and edge caching for very hot links.


Summary

  • Two operations: shorten (write, ~1,200/s here) and redirect (read, ~12,000/s, ~23,000/s at peak). The system is read-heavy.

  • Estimate first: 182.5 billion links over 5 years means 7 base62 characters and about 91 TB, so shard the data.

  • Recommended code generation: unique ID + base62, with range allocation across servers and an optional one-to-one shuffle to hide the sequence. Hashing needs collision handling.

  • Redirect path: cache → database → 302/301 redirect, with click events sent asynchronously to Kafka.

  • Shard by code, replicate each shard, cache hot links, and handle expiry, custom aliases and abuse.

A URL shortener is a giant, read-heavy key-value lookup: get the key generation right, cache aggressively, and keep everything else off the redirect path.