Design a URL shortener with click analytics

A URL shortener turns a long web address into a short one, such as https://s.example/kY9pF34, and sends whoever opens the short one on to the long one. The design that holds up gives every link a random seven-character code in base 62, stores the code and the long URL in a table whose primary key is the code, answers each click with a 302 redirect from a cache in front of that table, and writes a click event to a log, so that counting happens later and off the redirect’s path. Abuse is stopped where links are made: rate limits, a check of the target and rules for custom names. This case study builds the design from its requirements, with estimates that a script recomputes, a working service in SQLite, collision rates for every code length and a 12 KB sketch that counts unique visitors, and then takes it to ten and a hundred times the traffic.

Scope: the questions to ask first

“Design a URL shortener” leaves out most of what decides the design. Ask, and write down the answer you assume when nobody gives one:

• Who creates links? Signed-in accounts, and anonymous visitors with tighter limits.
• Can people choose the code? Accounts can pick a custom alias such as spring-sale.
• Can a link change or end? Its target never changes, because people have already shared or printed it. Owners can disable a link, and a link may carry an expiry.
• What do owners see? Clicks per day, unique visitors, countries, referring sites and device types, at most a minute late.
• How big? Six million new links and 600 million clicks a day, from users all over the world.
• What must never happen? A click that fails, a redirect to the wrong place, or a link that keeps working after it was disabled for abuse.

The functional requirements follow from the answers: create a short link, with an optional alias and expiry; redirect anyone who opens it; show its owner the statistics; disable it. The non-functional requirements carry the numbers:

• Redirects are the product. They take at most 10 ms of server time at the 99th percentile and are available 99.99 % of the time, about 4.3 minutes of downtime in a 30-day month.
• Creating links may be slower and less available: 99.9 %.
• Links last for years, and codes must not reveal how many links exist or when each one was made.
• Statistics may lag by a minute and unique visitors may be about 1 % off, but no click may be counted twice.

Estimates, recomputed by a script

The sheet follows the method of the estimation drills, with this service’s assumptions as named numbers at the top. Try the arithmetic yourself first, then run it, change an assumption and run it again.

# The estimate sheet of a URL shortener with click analytics (lesson system-design-hld/design-url-shortener).
# Every assumption is a named number at the top: change one and run the sheet again. Sizes are decimal
# (1 GB = 10**9 bytes), rates are per second, and the busiest hour carries PEAK times the daily average.
import math

DAY = 86_400

NEW_LINKS_PER_DAY = 6_000_000
CLICKS_PER_DAY = 600_000_000  # redirects a day, spread over links of every age
PEAK = 3
LINK_ROW = 500  # bytes per link: code, long URL, owner, times, index entries
COPIES = 3
YEARS = 5
REDIRECT = 450  # bytes of one 302 response, headers included
EVENT = 150  # bytes of one click event in the log
HOT_LINKS = 40_000_000  # links that receive almost every click (check this against real traffic)
CACHE_ENTRY = 600  # bytes per cached link, with the cache's own overhead
SERVER_RPS = 4_000  # redirects one server sustains, measured with a load test
TARGET = 0.6  # the highest utilisation allowed per server
SPARES = 2
CODE_LENGTH = 7


def two_figures(x):
    """x rounded to two significant figures, as an estimate deserves."""
    if x == 0:
        return 0
    digits = 1 - math.floor(math.log10(abs(x)))
    return round(x, digits)


def rate(x):
    return f"{two_figures(x):,.0f}/s"


def size(n_bytes):
    for unit, scale in (("PB", 10**15), ("TB", 10**12), ("GB", 10**9), ("MB", 10**6)):
        if n_bytes >= scale:
            return f"{two_figures(n_bytes / scale):g} {unit}"
    return f"{n_bytes:.0f} B"


def bits(bytes_per_second):
    mbit = bytes_per_second * 8 / 10**6
    return f"{two_figures(mbit / 1000):g} Gbit/s" if mbit >= 1000 else f"{two_figures(mbit):g} Mbit/s"


def servers(peak_rps):
    return math.ceil(peak_rps / (SERVER_RPS * TARGET)) + SPARES


creates = NEW_LINKS_PER_DAY / DAY
redirects = CLICKS_PER_DAY / DAY
links = NEW_LINKS_PER_DAY * 365 * YEARS
codes = 62**CODE_LENGTH

print("URL shortener: the estimate sheet")
print(f"  Creates    {rate(creates)} on average, {rate(creates * PEAK)} at the peak")
print(f"  Redirects  {rate(redirects)} on average, {rate(redirects * PEAK)} at the peak")
print(f"             ({CLICKS_PER_DAY // NEW_LINKS_PER_DAY} redirects for every link created)")
print(f"  Links      {two_figures(links / 10**9):g} billion in {YEARS} years; {CODE_LENGTH}-character codes:")
print(f"             {two_figures(codes / 10**12):g} trillion, {links / codes:.2%} used after {YEARS} years")
print(f"  Storage    {size(links * LINK_ROW)} of links, {size(links * LINK_ROW * COPIES)} with {COPIES} copies")
print(f"  Bandwidth  {bits(redirects * PEAK * REDIRECT)} of redirects at the peak")
print(f"  Click log  {size(CLICKS_PER_DAY * EVENT)} a day, {size(CLICKS_PER_DAY * EVENT * 365)} a year")
print(f"  Cache      {HOT_LINKS // 10**6} million hot links x {CACHE_ENTRY} B = {size(HOT_LINKS * CACHE_ENTRY)}")
print(f"  Servers    {servers(redirects * PEAK)} redirect servers at {TARGET:.0%} of {SERVER_RPS:,}/s each,")
print(f"             {SPARES} of them spares")
print()
print("Growth                       1x          10x         100x")
rows = [
    ("Redirects at peak", lambda k: rate(redirects * PEAK * k)),
    ("Creates at peak", lambda k: rate(creates * PEAK * k)),
    ("Redirect servers", lambda k: f"{servers(redirects * PEAK * k):,}"),
    ("Click log at peak", lambda k: f"{size(redirects * PEAK * EVENT * k)}/s"),
    ("Links, 5 years, x3", lambda k: size(links * LINK_ROW * COPIES * k)),
    ("Code space used", lambda k: f"{links * k / codes:.1%}"),
]
for label, cell in rows:
    print(f"  {label:<19}" + "".join(f"{cell(k):>13}" for k in (1, 10, 100)))

URL shortener: the estimate sheet
  Creates    69/s on average, 210/s at the peak
  Redirects  6,900/s on average, 21,000/s at the peak
             (100 redirects for every link created)
  Links      11 billion in 5 years; 7-character codes:
             3.5 trillion, 0.31% used after 5 years
  Storage    5.5 TB of links, 16 TB with 3 copies
  Bandwidth  75 Mbit/s of redirects at the peak
  Click log  90 GB a day, 33 TB a year
  Cache      40 million hot links x 600 B = 24 GB
  Servers    11 redirect servers at 60% of 4,000/s each,
             2 of them spares

Growth                       1x          10x         100x
  Redirects at peak       21,000/s    210,000/s  2,100,000/s
  Creates at peak            210/s      2,100/s     21,000/s
  Redirect servers              11           89          871
  Click log at peak       3.1 MB/s      31 MB/s     310 MB/s
  Links, 5 years, x3         16 TB       160 TB       1.6 PB
  Code space used             0.3%         3.1%        31.1%

Five decisions come out of it:

• Reads dominate. There are 100 redirects for every create: 21,000 a second at the peak against 210 creates. The cache and most of the servers belong to the redirect path, and one database primary can take the writes for years.
• The links are small. Five years of links need 16 TB with three copies, a table to partition rather than a storage problem.
• Seven characters are enough. After five years only 0.31 % of the 3.5 trillion codes are taken. At a hundred times the creates the space would be 31 % full, and the design would add an eighth character.
• The click log outweighs the links. At 33 TB a year it is the largest store, so the analytics design decides the storage bill.
• Bandwidth does not matter. Redirects are a few hundred bytes, 75 Mbit/s at the peak.

DAY = 86_400

COMPONENTS = {
    "load balancer",
    "API servers",
    "create checks",
    "redirect servers",
    "shared cache",
    "links table",
    "click log",
    "stream aggregator",
    "stats store",
}


def link_sheet(new_per_day, clicks_per_day, peak, row_bytes, copies, years, redirect_bytes):
    """Four figures of a URL shortener's estimate sheet, as a dictionary."""
    # Replace this line with your code.
    return {}


def redirect_path():
    """The components a click may have to wait for before its redirect is sent."""
    # Replace this line with your code.
    return set()

import math

from link_sheet import COMPONENTS, link_sheet, redirect_path

LESSON = dict(new_per_day=6_000_000, clicks_per_day=600_000_000, peak=3, row_bytes=500, copies=3, years=5,
              redirect_bytes=450)
SMALL = dict(new_per_day=200_000, clicks_per_day=8_000_000, peak=4, row_bytes=400, copies=2, years=2,
             redirect_bytes=500)


def near(actual, expected):
    """Within 10%, as an estimate should be."""
    return math.isclose(actual, expected, rel_tol=0.10)


def test_rates():
    """turns daily counts into rates a second at the peak"""
    sheet = link_sheet(**LESSON)
    assert near(sheet["peak_creates"], 208)
    assert near(sheet["peak_redirects"], 20_833)
    small = link_sheet(**SMALL)
    assert near(small["peak_creates"], 9.26)
    assert near(small["peak_redirects"], 370)


def test_storage():
    """keeps every link of the period with its copies"""
    assert near(link_sheet(**LESSON)["stored_bytes"], 1.64e13)
    assert near(link_sheet(**SMALL)["stored_bytes"], 1.17e11)


def test_bandwidth():
    """turns the peak redirects into megabits a second"""
    assert near(link_sheet(**LESSON)["egress_mbit"], 75.0)
    assert near(link_sheet(**SMALL)["egress_mbit"], 1.48)


def test_redirect_path():
    """keeps everything that runs after the answer off the click's path"""
    path = redirect_path()
    assert path <= COMPONENTS, f"unknown names: {sorted(path - COMPONENTS)}"
    assert path == {"load balancer", "redirect servers", "shared cache", "links table"}

The API

Owners use three operations; everyone else uses one.

Errors use codes clients already understand: 409 Conflict for an alias that is taken, 422 Unprocessable Content for a URL the service refuses, and 429 Too Many Requests when a creator is over a limit. The idempotency key solves an ordinary failure: a client whose request timed out cannot know whether the link was made. Stripe’s API documents the pattern: the server saves the result of the first request with a key and answers retries with the same key from that saved result, and the keys are pruned once they are a day or more old (Stripe API reference).

The data model

The links table holds one row per link, and every redirect reads it by code:

Two more structures sit beside it. A table of each owner’s links, keyed by owner and creation time, lists “my links” without scanning the links table, which is partitioned by code. The statistics never touch the links table at all: click events go to a log, and an aggregator keeps one row per link and day with the click count, a unique-visitor sketch and small breakdowns by country, referring site and device.

Any store with a primary key and an insert that fails when the key exists will do: a relational database partitioned by a hash of the code, or a key-value store that offers a conditional write. One primary takes 210 inserts a second with room to spare; partitioning is for the size and for the tenfold growth.

The high-level design

Follow one link through it. A create request reaches an API server, which runs the create checks, draws a random code and inserts the row; if the insert fails because the code exists, it draws another. A click reaches a redirect server, which looks the code up in its own memory, then in the shared cache, then in the links table, answers 302 and hands a click event to a background sender. The sender ships events in batches to the click log, and an aggregator turns them into the numbers owners see. Each path can fail without stopping the others: a slow aggregator delays statistics, never a redirect.

Deep dive: generating short codes

Four ways of making codes come up in every design discussion:

• Hash the long URL and keep the first seven base-62 characters of the hash. The same URL always gets the same code, and different URLs still collide.
• Draw a random code and check it on insert. Seven characters come from a secure random source, and the primary key refuses a duplicate.
• Count, and write the count in base 62. Codes never collide, but they show the order in which links were made and how fast.
• Keep a pool of codes made in advance. A background job fills a table with unused random codes, and servers take them in batches.

How soon do random codes collide? Sooner than intuition says, and less often than it fears:

# Random short codes: how soon two of them collide, and what that costs (lesson system-design-hld/design-url-shortener).
# With N possible codes and n codes already issued:
#   - the chance that at least one pair collided is 1 - exp(-n(n-1) / 2N), the birthday bound;
#   - the chance that the next random code is already taken is n / N. That is also the chance that a stranger who
#     types a random code lands on somebody's link.
import math

ALPHABET = 62  # 0-9, a-z, A-Z


def any_collision(n, space):
    """The chance that n random codes from `space` contain at least one repeat."""
    return -math.expm1(-n * (n - 1) / (2 * space))


def show(p):
    """A probability as a percentage with two significant figures."""
    if p >= 0.995:
        return "~100%"
    digits = max(0, 1 - math.floor(math.log10(p * 100)))
    return f"{p * 100:.{digits}f}%"


print("Chance of at least one collision among n random codes")
print(f"{'n codes':>16}" + "".join(f"{f'{k} chars':>13}" for k in (6, 7, 8)))
for n in (10**4, 10**5, 10**6, 10**7, 10**8):
    print(f"{n:>16,}" + "".join(f"{show(any_collision(n, ALPHABET**k)):>13}" for k in (6, 7, 8)))

print()
print("Chance that the next code (or a stranger's guess) hits a taken one")
print(f"{'n codes':>16}" + "".join(f"{f'{k} chars':>13}" for k in (6, 7, 8)))
for n in (10**6, 10**8, 10**10, 11 * 10**9):
    print(f"{n:>16,}" + "".join(f"{show(n / ALPHABET**k):>13}" for k in (6, 7, 8)))

links = 11 * 10**9  # five years of the estimate sheet
for k in (6, 7):
    space = ALPHABET**k
    # Each insert retries until it finds a free code: on average p / (1 - p) extra tries when a share p is taken.
    extra = sum((i / space) / (1 - i / space) for i in range(0, links, links // 1000)) / 1000
    print(f"{k} characters: {extra:.2%} extra tries per insert on average over five years")

Chance of at least one collision among n random codes
         n codes      6 chars      7 chars      8 chars
          10,000       0.088%      0.0014%    0.000023%
         100,000         8.4%        0.14%      0.0023%
       1,000,000        ~100%          13%        0.23%
      10,000,000        ~100%        ~100%          20%
     100,000,000        ~100%        ~100%        ~100%

Chance that the next code (or a stranger's guess) hits a taken one
         n codes      6 chars      7 chars      8 chars
       1,000,000      0.0018%    0.000028%  0.00000046%
     100,000,000        0.18%      0.0028%    0.000046%
  10,000,000,000          18%        0.28%      0.0046%
  11,000,000,000          19%        0.31%      0.0050%
6 characters: 11.14% extra tries per insert on average over five years
7 characters: 0.16% extra tries per insert on average over five years

The first table is the birthday problem. After a million random seven-character codes the chance that two of them are equal is already 13 %, and after ten million it is a near certainty, so random codes always need a uniqueness check. The second table is the one the design depends on: the chance that the next code is taken is simply the share of the space in use, 0.31 % after five years, so the check almost never fires and an insert needs 0.16 % extra tries on average. With six characters the space would be 19 % full by the fifth year, and about one insert in nine would retry.

The same table answers a security question. Once the service is five years old, a stranger who types random codes lands on a real link 0.31 % of the time, so a script trying 100 codes a second finds about 1,100 links an hour. No short code is secret, however it is made. A link to something private needs a long random token, or the target needs its own access check.

A counter still has a place when the store cannot insert “only if absent” cheaply. Each server leases a block of numbers, and every number is encrypted with a secret key by a format-preserving cipher over the seven-character space, such as FF1 from NIST SP 800-38G (NIST), so that codes look random and never collide. The share of the space in use, and so the guessing rate above, stays the same.

The random design in code, with its checks:

# A URL shortener small enough to read in one sitting (lesson system-design-hld/design-url-shortener): random
# 7-character base-62 codes kept unique by the table's primary key, custom aliases, checks on the target URL, and
# the redirect handler with its status codes. SQLite in memory stands in for the links table. The random source
# and the clock are passed in, and the random source is seeded so that every run prints the same; a real service
# passes secrets.SystemRandom() and reads a clock.
import random
import sqlite3
from urllib.parse import urlsplit

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
ALIAS_CHARS = set("abcdefghijklmnopqrstuvwxyz0123456789-")
OWN_HOST = "s.example"
RESERVED = {"about", "admin", "api", "help", "login", "settings", "static", "stats"}
MAX_URL = 8_000  # RFC 9110 recommends supporting URIs of at least 8,000 octets
MAX_TRIES = 5


class Rejected(Exception):
    """A create request the service refuses, with the HTTP status it answers."""

    def __init__(self, status, reason):
        super().__init__(reason)
        self.status = status
        self.reason = reason


class Shortener:
    def __init__(self, db, rng, length=7):
        self.db, self.rng, self.length = db, rng, length
        self.retries = 0
        db.execute(
            "CREATE TABLE links (code TEXT PRIMARY KEY, long_url TEXT NOT NULL, owner TEXT NOT NULL,"
            " created_ms INTEGER NOT NULL, expires_ms INTEGER, disabled INTEGER NOT NULL DEFAULT 0)"
        )

    def check_url(self, url):
        if len(url) > MAX_URL:
            raise Rejected(422, "URL too long")
        parts = urlsplit(url)
        if parts.scheme not in ("http", "https"):
            raise Rejected(422, f"scheme '{parts.scheme}' not allowed")
        if not parts.hostname:
            raise Rejected(422, "no host")
        if parts.hostname == OWN_HOST:
            raise Rejected(422, "points back at the shortener")

    def check_alias(self, alias):
        if not 4 <= len(alias) <= 30 or not set(alias) <= ALIAS_CHARS:
            raise Rejected(422, "aliases use a-z, 0-9 and -, 4 to 30 long")
        if alias in RESERVED:
            raise Rejected(422, "reserved word")

    def random_code(self):
        return "".join(self.rng.choice(ALPHABET) for _ in range(self.length))

    def create(self, url, owner, now_ms, alias=None, ttl_ms=None):
        """Stores a link and returns its code; raises Rejected with the status to answer."""
        self.check_url(url)
        if alias is not None:
            self.check_alias(alias)
        expires = now_ms + ttl_ms if ttl_ms else None
        for _ in range(1 if alias else MAX_TRIES):
            code = alias or self.random_code()
            try:
                with self.db:  # one transaction: the primary key refuses a code that exists
                    self.db.execute("INSERT INTO links VALUES (?, ?, ?, ?, ?, 0)", (code, url, owner, now_ms, expires))
                return code
            except sqlite3.IntegrityError:
                if alias:
                    raise Rejected(409, "alias taken") from None
                self.retries += 1
        raise Rejected(503, f"no free code after {MAX_TRIES} tries")

    def disable(self, code):
        with self.db:
            self.db.execute("UPDATE links SET disabled = 1 WHERE code = ?", (code,))

    def redirect(self, code, now_ms):
        """The answer to GET /<code>: a status and its headers."""
        row = self.db.execute("SELECT long_url, expires_ms, disabled FROM links WHERE code = ?", (code,)).fetchone()
        if row is None:
            return 404, {"Cache-Control": "no-store"}
        long_url, expires, disabled = row
        if disabled or (expires is not None and now_ms >= expires):
            return 410, {"Cache-Control": "no-store"}
        return 302, {"Location": long_url, "Cache-Control": "no-store"}


def attempt(label, svc, *args, **kwargs):
    try:
        code = svc.create(*args, **kwargs)
        print(f"  {label:<44} 201 {code}")
        return code
    except Rejected as e:
        print(f"  {label:<44} {e.status} {e.reason}")


def show(svc, code, now_ms, note=""):
    status, headers = svc.redirect(code, now_ms)
    assert headers["Cache-Control"] == "no-store"
    target = f"-> {headers['Location']}" if "Location" in headers else note
    print(f"  GET /{code:<12} {status}  {target}")
    return status


HOUR = 3_600_000
svc = Shortener(sqlite3.connect(":memory:"), random.Random(7))
now = 10 * HOUR  # milliseconds on the injected clock

print("Creating links")
guide = attempt("https://example.com/guide?utm_source=mail", svc, "https://example.com/guide?utm_source=mail", "u1", now)
sale = attempt('alias "spring-sale"', svc, "https://shop.example/sale", "u2", now, alias="spring-sale")
attempt('alias "spring-sale" again', svc, "https://other.example/", "u3", now, alias="spring-sale")
attempt('alias "admin"', svc, "https://shop.example/", "u2", now, alias="admin")
attempt('alias "Spring-Sale"', svc, "https://shop.example/", "u2", now, alias="Spring-Sale")
attempt("javascript:alert(1)", svc, "javascript:alert(1)", "u4", now)
attempt(f"https://{OWN_HOST}/{guide}", svc, f"https://{OWN_HOST}/{guide}", "u4", now)
offer = attempt("a link that expires after one hour", svc, "https://shop.example/offer", "u2", now, ttl_ms=HOUR)

print("Redirecting (every answer carries Cache-Control: no-store)")
assert show(svc, guide, now) == 302
assert show(svc, sale, now) == 302
assert show(svc, "zzzzzzz", now, "no such code") == 404
svc.disable(guide)  # by its owner, or after an abuse report
assert show(svc, guide, now, "disabled") == 410
assert show(svc, offer, now + HOUR - 1) == 302
assert show(svc, offer, now + HOUR, "expired one hour after it was made") == 410

print("Collisions on purpose: 2-character codes, 62**2 = 3,844 of them")
tiny = Shortener(sqlite3.connect(":memory:"), random.Random(7), length=2)
made = refused = 0
for i in range(3_000):
    try:
        tiny.create(f"https://example.com/{i}", "load-test", now)
        made += 1
    except Rejected:
        refused += 1
print(f"  {made:,} links stored, {tiny.retries:,} retries, {refused} refused after {MAX_TRIES} tries")
print(f"  (the table is {made / 62**2:.0%} full, and the primary key let no duplicate in)")

Creating links
  https://example.com/guide?utm_source=mail    201 kY9pF34
  alias "spring-sale"                          201 spring-sale
  alias "spring-sale" again                    409 alias taken
  alias "admin"                                422 reserved word
  alias "Spring-Sale"                          422 aliases use a-z, 0-9 and -, 4 to 30 long
  javascript:alert(1)                          422 scheme 'javascript' not allowed
  https://s.example/kY9pF34                    422 points back at the shortener
  a link that expires after one hour           201 Qy6nB3W
Redirecting (every answer carries Cache-Control: no-store)
  GET /kY9pF34      302  -> https://example.com/guide?utm_source=mail
  GET /spring-sale  302  -> https://shop.example/sale
  GET /zzzzzzz      404  no such code
  GET /kY9pF34      410  disabled
  GET /Qy6nB3W      302  -> https://shop.example/offer
  GET /Qy6nB3W      410  expired one hour after it was made
Collisions on purpose: 2-character codes, 62**2 = 3,844 of them
  2,895 links stored, 2,416 retries, 105 refused after 5 tries
  (the table is 75% full, and the primary key let no duplicate in)

Three details carry over to a real service. The primary key checks uniqueness inside the insert, so two servers that draw the same code at the same moment cannot both succeed. Aliases go through the same key, so “taken” is the database’s answer rather than a race between a read and a write; they are lower case only, because the path of a URL is case-sensitive (RFC 3986) and Spring-Sale and spring-sale would be two links that people cannot tell apart. And the last part fills a two-character space to 75 % on purpose: retries climb steeply as a space fills, 105 inserts gave up after five tries, and the primary key still let no duplicate in. The example seeds Python’s random so that its output is the same on every run; a service draws from secrets.SystemRandom(), which uses the most secure source the operating system provides (Python documentation).

Deep dive: the redirect path

A redirect is a few hundred bytes: a status line, a Location header and a small body. Its status code decides who may answer the next click without asking the service.

RFC 9110 defines all four. A 301 or 308 response is heuristically cacheable: when no Cache-Control says otherwise, a browser or a shared cache may store it and reuse it without asking again. 302 and 307 are not, and are stored only when the response says so. 307 and 308 also forbid a client to change the method, while after a 301 or 302 a client may send a POST again as a GET (RFC 9110). Clicks are GET requests, so for a shortener the real choice is between permanent and temporary.

Answer with 302 and Cache-Control: no-store, which tells every cache not to keep the response (RFC 9111). Every click then reaches a redirect server, which keeps the counts complete and lets a disabled link stop at once. A 301 saves repeat visitors one request, but their clicks are never counted, and a browser that kept the redirect sends people on to a target that has since been disabled.

Inside the service, a lookup passes up to three layers. Each redirect server keeps the hottest few hundred thousand links in its own memory, which answers without a network trip. The shared cache holds the hot set, 24 GB in the sheet, one network round trip away. The links table answers what both miss, and the answer is written back to the shared cache: the cache-aside pattern. The hit ratio decides the table’s load: at 21,000 redirects a second, 99 % hits leave 210 reads a second for the table and 95 % leave 1,050. A cache emptied by a restart sends all 21,000 to the table, which is why new cache nodes are warmed before they take traffic, as the cold-start simulation in “Where caches live” shows.

Unknown codes need care too. Scanners try random codes, and every miss would reach the table. Keep a “no such code” entry in the shared cache for a minute, delete it when a custom alias with that name is created, and count each client’s 404 answers: a client that collects many is scanning.

Deep dive: click analytics without slowing redirects

A redirect server never writes to a database while a click waits. It appends a small event to a buffer in memory and answers; a background sender ships the buffer to the click log every few hundred milliseconds. The event carries what the statistics need and nothing more:

• an event id, so that duplicates can be dropped;
• the code and the time;
• the country, looked up from the client’s address, which is then dropped;
• the referring site’s origin and the device class;
• a visitor key: a keyed hash of the address and the user agent, with a secret that changes every day.

Why not UPDATE links SET clicks = clicks + 1 on every click? A popular link would become one row that every click locks: a link at 20,000 clicks a second needs 20,000 updates a second of a single row, and they queue behind each other. A log takes the clicks as appends, spread over partitions, and the aggregator adds them up in memory.

Logs deliver at least once: a sender that times out and resends can store an event twice. Kafka’s design documentation says the default guarantee is at-least-once delivery, and that its idempotent producer lets the broker drop resent duplicates by a producer id and a sequence number on each message (Kafka documentation). The aggregator also remembers the event ids of the last few minutes and skips any it has seen, so a retried event is never counted twice. If the log is down, the sender keeps buffering up to a limit and then drops events and counts what it dropped: losing some statistics is better than failing redirects.

Unique visitors are harder than clicks, because counting them exactly means remembering every visitor. A HyperLogLog sketch counts them in a fixed amount of memory with a small error. Redis documents its version as using at most 12 KB per key with a standard error of 0.81 %, with PFADD to add an item, PFCOUNT to count and PFMERGE to combine sketches (Redis documentation). The script below builds a sketch of the same size and checks it against an exact set:

# Unique visitors per link with a HyperLogLog, against an exact set (lesson system-design-hld/design-url-shortener).
# The sketch keeps 2**14 = 16,384 registers of 6 bits, 12 KB in all, the size Redis documents for its HyperLogLog
# (standard error 0.81 %). Visitor ids are made up from a seeded random source, so every run prints the same.
import hashlib
import math
import random

P = 14
M = 1 << P  # registers
ALPHA = 0.7213 / (1 + 1.079 / M)  # the bias correction of the original HyperLogLog estimator
SKETCH_BYTES = M * 6 // 8


def hash64(item):
    return int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")


class HyperLogLog:
    def __init__(self):
        self.registers = bytearray(M)

    def add(self, item):
        h = hash64(item)
        index = h >> (64 - P)  # the first 14 bits choose a register
        rest = h & ((1 << (64 - P)) - 1)  # the other 50 bits
        rank = (64 - P) - rest.bit_length() + 1  # where their first 1 bit is
        if rank > self.registers[index]:
            self.registers[index] = rank

    def count(self):
        raw = ALPHA * M * M / sum(2.0**-r for r in self.registers)
        zeros = self.registers.count(0)
        if raw <= 2.5 * M and zeros:
            return M * math.log(M / zeros)  # small counts: linear counting on the empty registers
        return raw

    def merge(self, other):
        """The union of two sketches: the larger value of every register."""
        out = HyperLogLog()
        out.registers = bytearray(map(max, self.registers, other.registers))
        return out


def kb(n_bytes):
    return f"{n_bytes / 1000:,.0f} KB" if n_bytes < 10**6 else f"{n_bytes / 10**6:.1f} MB"


rng = random.Random(42)
print("Unique visitors of one link in one day: an exact set against a 12 KB sketch")
print(f"  {'link':<8}{'clicks':>9}{'exact':>9}{'sketch':>9}{'error':>8}{'set of ids':>12}")
for name, uniques in (("small", 800), ("medium", 20_000), ("viral", 100_000)):
    visitors = [f"{name}-{rng.getrandbits(64):016x}" for _ in range(uniques)]
    clicks = [v for v in visitors for _ in range(rng.randint(1, 4))]  # each visitor clicks 1 to 4 times
    sketch, exact = HyperLogLog(), set()
    for v in clicks:
        sketch.add(v)
        exact.add(v)
    est = sketch.count()
    print(f"  {name:<8}{len(clicks):>9,}{len(exact):>9,}{est:>9,.0f}{(est - len(exact)) / len(exact):>+8.1%}{kb(16 * len(exact)):>12}")
print(f"  (the set keeps a 16-byte hash per visitor; every sketch stays at {SKETCH_BYTES:,} bytes)")

print("Two days merged register by register, as PFMERGE does")
day1 = [f"d-{rng.getrandbits(64):016x}" for _ in range(30_000)]
day2 = day1[:12_000] + [f"d-{rng.getrandbits(64):016x}" for _ in range(18_000)]  # 12,000 come back
s1, s2 = HyperLogLog(), HyperLogLog()
for v in day1:
    s1.add(v)
for v in day2:
    s2.add(v)
both = s1.merge(s2).count()
truth = len(set(day1) | set(day2))
print(f"  day 1 {s1.count():,.0f}, day 2 {s2.count():,.0f}, both days {both:,.0f} (exact {truth:,}, {(both - truth) / truth:+.1%})")
print(f"  adding the two daily counts would claim {s1.count() + s2.count():,.0f}")

print("How far off is a sketch? 12 links of 70,000 visitors each")
errors = []
for i in range(12):
    sketch = HyperLogLog()
    for _ in range(70_000):
        sketch.add(f"spread-{i}-{rng.getrandbits(64):016x}")
    errors.append(sketch.count() / 70_000 - 1)
rms = math.sqrt(sum(e * e for e in errors) / len(errors))
print(f"  typical error {rms:.2%} (theory 1.04 / sqrt(16,384) = {1.04 / math.sqrt(M):.2%}); worst {max(errors, key=abs):+.2%}")

Unique visitors of one link in one day: an exact set against a 12 KB sketch
  link       clicks    exact   sketch   error  set of ids
  small       2,017      800      796   -0.5%       13 KB
  medium     50,411   20,000   20,114   +0.6%      320 KB
  viral     249,521  100,000   98,990   -1.0%      1.6 MB
  (the set keeps a 16-byte hash per visitor; every sketch stays at 12,288 bytes)
Two days merged register by register, as PFMERGE does
  day 1 30,166, day 2 29,928, both days 48,423 (exact 48,000, +0.9%)
  adding the two daily counts would claim 60,094
How far off is a sketch? 12 links of 70,000 visitors each
  typical error 0.77% (theory 1.04 / sqrt(16,384) = 0.81%); worst +1.44%

Three results matter. The sketch stays within about 1 % at every size, while the exact set for one viral link grows to 1.6 MB in a day. Merging two days’ sketches counts visitors who came on both days once, as long as both days use the same visitor key: 48,423 against an exact 48,000, where adding the daily counts would claim 60,094. And over twelve links of 70,000 visitors the typical error was 0.77 %, close to the theory’s 0.81 %.

The daily secret is a trade-off to say out loud. Visitor keys cannot follow a person from one day to the next, which is the point, but for the same reason the merge above does not work across days: the same person hashes differently each day. A service that must report weekly uniques keeps a weekly sketch with a weekly secret, and accepts that it links one person’s clicks within that week.

Not every click is a person. Chat apps and social sites fetch links to draw previews, and security scanners open them to check the target. Classify these by user agent and by the networks they come from, and report them apart from human clicks instead of silently dropping them, so that owners can see why the two numbers differ.

Deep dive: abuse

Short links hide where they lead, which makes them useful to phishing and malware campaigns. The defences sit on the create path, where they cost nothing per click:

• Limits on creating. Limit per account and per address, with tighter limits for anonymous creators; the rate-limiting algorithms lesson compares the algorithms.
• Checks of the target. Allow only http and https, refuse links back to the shortener itself (they make loops), cap the length, and look the URL up in lists of unsafe sites. Google’s Safe Browsing APIs check URLs against such lists; their documentation says they are for non-commercial use and points commercial services to the Web Risk API (Google).
• Checks later. A target that was clean when the link was made can turn bad. Check links again when their traffic jumps and on a schedule, and show a warning page instead of the redirect while the abuse team looks into a report.
• Rules for aliases. Reserve the words of the product’s own paths (api, admin, login, help), and refuse aliases that imitate well-known brands.
• Disabling. A disabled link answers 410 Gone, and a block ordered by a court can answer 451 Unavailable For Legal Reasons. A 410 is heuristically cacheable and a 451 is cacheable by default (RFC 7725), so send Cache-Control: no-store with both, and purge any cache that holds the old redirect.

Growth: what breaks at 10x and 100x

The growth table of the sheet shows where the pressure goes.

• At 10x, 210,000 redirects a second at the peak need 89 redirect servers, and the shared cache is split over several nodes by code. The links table is partitioned by a hash of the code; 2,100 creates a second fit a few partitions. The click log carries 31 MB/s and needs enough partitions for the aggregators to keep up.
• At 100x, 2.1 million redirects a second from one region would need 871 servers and keep most users far from them. Redirects move to several regions, each with a replica of the links table and its own caches. A CDN can cache each redirect for a few minutes with s-maxage, the shared-cache lifetime of RFC 9111, while clicks are counted from the CDN’s request logs; disabling a link then includes purging it from the CDN. Codes get an eighth character, because seven would be 31 % full within five years.

A link created in one region must also work in the others before replication has copied it. A replica that has no row for a code asks the region that owns the code before it answers 404. The code can say which region owns it, for example through its first character, which also keeps two regions from issuing the same code; the fallback then costs one cross-region request, and only for brand-new links.

Trade-offs and the options rejected

Cost notes

The bill is small, and two lines dominate it. Links take 16 TB with copies, and bandwidth is 75 Mbit/s. The click log, 33 TB a year, is the largest store, so keep raw events only for a set number of days, enough to rerun the aggregation after a bug, and keep the daily rows and sketches after that. Compute is the redirect fleet, about 11 servers at today’s peak, and a cache cluster that holds 24 GB with a replica.

What each level is expected to cover

These are general expectations for the levels of a design round, not any company’s own rubric:

• Early career: the API with its status codes, a table keyed by code, base-62 codes and why seven characters are enough, and a cache in front of the table.
• Mid-level: the estimates, collisions handled by a unique key, 302 against 301 and what it does to the counts, and analytics through a log.
• Senior: every choice tied to a number, failures handled (a cold cache, a log that is down, duplicate events), abuse and privacy, and the plan for ten times the traffic.
• Staff: reads and creation in several regions, counting at the edge, the cost of the analytics data, and how the system is changed safely while it runs.

Exercise and self-check

The estimate exercise above checks the numbers. This one checks the code at the heart of the design:

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode(n, width=7):
    """n in base 62, padded on the left with "0" to `width` characters."""
    # Replace this line with your code.
    return ""


def decode(code):
    """The number that `code` stands for in base 62."""
    # Replace this line with your code.
    return 0

from base62 import ALPHABET, decode, encode


def raises_value_error(call):
    try:
        call()
    except ValueError:
        return True
    return False


def test_small_numbers():
    """writes the first numbers with padding"""
    assert encode(0) == "0000000"
    assert encode(9) == "0000009"
    assert encode(10) == "000000a"
    assert encode(61) == "000000Z"
    assert encode(62) == "0000010"


def test_largest_code():
    """uses all seven characters for the largest number"""
    assert encode(62**7 - 1) == "ZZZZZZZ"
    assert decode("ZZZZZZZ") == 62**7 - 1


def test_known_codes():
    """reads codes as base-62 numbers"""
    assert decode("10") == 62
    assert decode("kY9pF34") == 1_191_111_784_618
    assert encode(1_191_111_784_618) == "kY9pF34"


def test_round_trip():
    """gives every number back unchanged"""
    for n in (1, 3_843, 3_844, 916_132_831, 1_234_567_890_123):
        assert decode(encode(n)) == n


def test_width():
    """pads to the width it is given"""
    assert encode(5, width=3) == "005"
    assert encode(3_843, width=2) == "ZZ"


def test_refuses_numbers_that_do_not_fit():
    """raises ValueError outside 0 to 62**width - 1"""
    assert raises_value_error(lambda: encode(-1))
    assert raises_value_error(lambda: encode(62**7))
    assert raises_value_error(lambda: encode(3_844, width=2))


def test_refuses_other_characters():
    """raises ValueError for a character outside the alphabet"""
    assert raises_value_error(lambda: decode("abc-def"))
    assert len(ALPHABET) == 62

Interview questions

Should a URL shortener redirect with 301 or 302? With 302 Found, or 307, and Cache-Control: no-store, whenever the service counts clicks or may disable links. RFC 9110 makes 301 and 308 heuristically cacheable, so a browser or a shared cache may reuse the redirect without asking the service again: repeat clicks are then never counted, and a link disabled for abuse keeps working for anyone whose browser kept the old answer. 302 and 307 are reused only when the response allows it. For clicks, which are GET requests, 302 and 307 behave the same; 307 only adds that a client must not turn a POST into a GET. A 301 suits a link that never changes and whose clicks nobody counts.

How long should short codes be? Long enough that the space stays mostly empty for the service’s lifetime, which is a calculation, not a matter of taste. Seven characters of base 62 (0-9, a-z, A-Z) give 62 to the power 7, about 3.5 trillion codes. A service that creates 6 million links a day uses 11 billion of them in five years, 0.31 % of the space, so a new random code is almost never taken. Six characters, 57 billion codes, would be 19 % full, and about one insert in nine would retry. The share in use is also how often a stranger’s random guess finds a real link, so private content needs much longer codes.

Key takeaways

• Estimate first: 100 redirects per create puts the cache and the servers on the redirect path, and the click log, not the links, is the largest store.
• Random seven-character codes with the primary key as the uniqueness check leave 99.7 % of the space unused for five years; no short code is secret.
• Redirect with 302 and Cache-Control: no-store so that every click is counted and a disabled link stops at once.
• Count clicks from a log, drop duplicates by event id, and count unique visitors with 12 KB sketches that merge.
• Stop abuse on the create path, check targets again later, and answer 410 or 451 with explicit cache headers.
• At 100x, serve redirects from several regions or the CDN, count from logs, and add an eighth character.