System Design · Lesson 8 of 18

URL Shortener

End-to-end TinyURL: API, schema, base62 codes, caching, analytics and abuse.

  • Advanced
  • 50 min read
  • 5 objectives

Before this lessonLesson 7: Unique ID Generator

What you will learn

  • Size a shortener: traffic, storage, bandwidth and cache memory
  • Compare hashing, counters and a Key Generation Service for short codes
  • Design the redirect path with 301/302, caching, hot keys and lazy expiry
  • Partition and replicate billions of links, across regions
  • Build an async click-analytics pipeline and defend against abuse

Your Progress

0 of 18 lessons 0%

  • Lessons0 / 18
  • Completed0
  • Est. time left~ 16 hours

Progress is saved in this browser. No account needed.

Tip: pressing Next marks this lesson complete automatically.

Design a URL shortener like TinyURL or bit.ly: someone pastes https://shop.example/collections/spring/sale?utm_source=newsletter&utm_campaign=apr and gets back https://sho.rt/Xk29aQ1. Anyone who opens the short link lands on the original page. It is the classic first system design question, and it looks trivial — a hash map with a web server in front. The interview is really about everything around that hash map: how you mint billions of unique, unguessable codes without collisions or coordination, how you serve tens of thousands of redirects per second in single-digit milliseconds, how you count clicks without slowing the redirect down, and how you stop the service from becoming a phishing launderette.

Why do people want short links at all? They fit in an SMS, a tweet, a printed poster or a QR code; they hide ugly tracking parameters; they are easy to read out loud; and — the part that pays the bills — every click passes through the shortener, so the link owner gets analytics on who clicked, from where, and when. Keep that last point in mind: it decides the 301-vs-302 question later, and it is why "just let the CDN cache it" is not a complete answer.

This lesson builds directly on Lesson 7: Unique ID Generator (how to mint IDs) and Lesson 3: Scaling and Caching (cache-aside, eviction, stampedes). The rate limiter that protects the create API is the next lesson, Lesson 9.

Step 1 — Clarify the requirements

Spend two or three minutes here. Each answer below changes a later decision, and saying which decision it changes is what makes the questions sound senior rather than scripted.

  • Can the same long URL get different short codes? (Decides whether hashing the URL is even allowed. Answer: yes — two marketers shortening the same landing page want separate click counts.)
  • Custom aliases? (Adds a uniqueness check on a user-chosen string and a reserved-word list.)
  • Do links expire? (Adds an expiry column, a lazy check on read, and a cleanup job.)
  • Accounts, or anonymous? (Anonymous creation is the abuse vector; it changes rate limiting and captcha needs.)
  • Analytics depth? (A single counter is a column; per-country, per-referrer, per-hour time series is a pipeline.)
  • Must codes be unguessable? (Rules out a plain auto-increment counter encoded in base62.)
  • Private links? (Adds a permission check on the hot path.)

Functional, in scope for v1

  • Create a short link for a long URL; return a code of at most 7 characters.
  • Redirect GET /{code} to the long URL.
  • Optional custom alias (up to 16 characters) and optional expiry; a default expiry for anonymous links (say one year).
  • Owners can view, update the destination of, and delete their links.
  • Click analytics: total clicks, clicks per day, top countries, top referrers, device type.
  • A public REST API with per-developer API keys and quotas.

Explicitly out of scope

QR-code rendering, A/B split links, deep links into mobile apps, branded custom domains per customer (mention it as a v2: it is a (domain, code) composite key), link-in-bio pages and a full BI product. Naming these shows you know what the real products sell.

Non-functional

  • Scale: 200M new links per month; 100:1 reads to writes; keep links for 10 years.
  • Latency: redirect p99 < 20 ms server-side (the user is waiting to see a different site, so every millisecond here is pure overhead); create p99 < 200 ms.
  • Availability: 99.99% for redirects. If the shortener is down, every printed poster, every email campaign and every tweet containing a link is broken at once. Creation can tolerate a little less (99.9%).
  • Consistency: a link must redirect correctly within about a second of creation (people click their own link immediately to test it); analytics may lag by a minute; a deleted or disabled link must stop redirecting within seconds.
  • Security: codes are not enumerable; destinations are scanned for malware and phishing; private links are enforced.

Step 2 — Back-of-the-envelope estimation

new_per_month   = 200_000_000
read_write      = 100
SECONDS_MONTH   = 30 * 86_400
years_kept      = 10
row_bytes       = 400        # code, long_url (~200 B avg), owner, timestamps, flags, index overhead
redirect_bytes  = 350        # 302 response: status line, Location header, a few other headers

# --- Traffic ---
writes = new_per_month / SECONDS_MONTH
reads  = writes * read_write
print(f"creates:   {writes:,.0f}/s avg, {writes * 5:,.0f}/s peak")
print(f"redirects: {reads:,.0f}/s avg, {reads * 5:,.0f}/s peak")

# --- Storage ---
rows = new_per_month * 12 * years_kept
print(f"rows after {years_kept}y: {rows / 1e9:.0f} billion   storage: {rows * row_bytes / 1e12:.1f} TB"
      f" (x3 replicas = {rows * row_bytes * 3 / 1e12:.0f} TB)")

# --- Bandwidth ---
print(f"ingress: {writes * row_bytes / 1e3:,.0f} KB/s   egress: {reads * redirect_bytes / 1e6:,.1f} MB/s")

# --- Cache: 80/20 rule over one day of distinct links ---
reads_per_day = reads * 86_400
naive  = 0.2 * reads_per_day * row_bytes            # the textbook number: 20% of REQUESTS
distinct_links_touched = 40_000_000                   # assumption: links clicked at least once/day
smart  = 0.2 * distinct_links_touched * row_bytes    # 20% of distinct LINKS
print(f"redirects/day: {reads_per_day / 1e9:.2f} B")
print(f"cache, 20% of requests: {naive / 1e9:,.0f} GB   20% of distinct links: {smart / 1e9:,.1f} GB")

# --- Key space ---
for n in (6, 7, 8):
    space = 62 ** n
    print(f"base62 len {n}: {space:,} codes -> {rows / space:.4%} used after {years_kept}y")
Output
creates:   77/s avg, 386/s peak
redirects: 7,716/s avg, 38,580/s peak
rows after 10y: 24 billion   storage: 9.6 TB (x3 replicas = 29 TB)
ingress: 31 KB/s   egress: 2.7 MB/s
redirects/day: 0.67 B
cache, 20% of requests: 53 GB   20% of distinct links: 3.2 GB
base62 len 6: 56,800,235,584 codes -> 42.2533% used after 10y
base62 len 7: 3,521,614,606,208 codes -> 0.6815% used after 10y
base62 len 8: 218,340,105,584,896 codes -> 0.0110% used after 10y

What the numbers actually decide

  • ~390 creates/s at peak is tiny. Any database handles it. The write path is not where the difficulty is; generating unique codes across many app servers without a hot coordination point is.
  • ~39k redirects/s at peak is the real load, and it is almost entirely point reads by primary key. That is a cache problem. With a 90%+ hit rate, the database sees a few thousand reads per second — comfortably a replicated cluster, not an exotic system.
  • ~10 TB over ten years (≈30 TB with three replicas) will not fit on one box forever, so the data must be partitionable. It does not need partitioning on day one; it needs a partition key chosen on day one (the code).
  • Bandwidth is irrelevant. A redirect response is a few hundred bytes. Say so and move on — interviewers like it when you drop a dimension that does not matter.
  • The textbook cache estimate is too big. "Cache 20% of a day's requests" gives ~53 GB, but many of those requests are for the same links. What you actually cache is 20% of the distinct links clicked that day — a few GB. Either number fits in a small Redis cluster, but the second shows you understand what a cache holds.
  • Seven base62 characters are plenty. Six characters (56.8B codes) would be 42% consumed after ten years, which makes random generation collide constantly. Seven characters (3.5T) are under 1% used. Pick 7 and justify it with that line of output.

Step 3 — API design

Two very different surfaces: a management API (authenticated, rate-limited, JSON) and the redirect endpoint (public, anonymous, as small as possible). They are served from different paths and, at scale, from different fleets.

## Management API  (https://api.sho.rt, JSON, authenticated)
## Every call carries  Authorization: Bearer <api_key>
## The key maps to an account + a quota tier (e.g. free: 1k creates/day, 60/min)

POST /api/v1/links
  Headers: Idempotency-Key: 5b1e...        (optional, recommended for retries)
  {
    "long_url":     "https://shop.example/collections/spring/sale?utm_source=newsletter",
    "custom_alias": "spring-sale",          // optional, 4-16 chars, [A-Za-z0-9_-]
    "expires_at":   "2027-04-01T00:00:00Z", // optional; default depends on account
    "visibility":   "public",               // public | private
    "redirect":     302                     // 302 (default) | 301
  }
  -> 201 { "code": "spring-sale", "short_url": "https://sho.rt/spring-sale",
           "long_url": "...", "expires_at": "...", "created_at": "..." }
     400 INVALID_URL | 400 UNSUPPORTED_SCHEME (only http/https)
     400 ALIAS_RESERVED ("api", "admin", "login", ...)
     409 ALIAS_TAKEN
     422 DESTINATION_BLOCKED (on a malware / phishing list)
     429 QUOTA_EXCEEDED + Retry-After
     # Same Idempotency-Key + same body -> same 201 response, no second link.

GET    /api/v1/links/{code}           -> 200 link metadata | 404 | 403 (not owner)
GET    /api/v1/links?cursor=<opaque>  -> 200 { links: [...], next_cursor }  # owner's links
PATCH  /api/v1/links/{code}  { long_url?, expires_at?, visibility? }
                                      -> 200 | 403 | 404 | 422 DESTINATION_BLOCKED
DELETE /api/v1/links/{code}           -> 204 | 403 | 404
       # soft delete: status='deleted', cache invalidated, code NOT recycled

GET /api/v1/links/{code}/stats?from=2026-09-01&to=2026-09-23&granularity=day
  -> 200 { total: 48211, human: 45102,
           series: [{ bucket: "2026-09-01", clicks: 1320 }, ...],
           top_countries: [{ "IN": 20112 }, ...], top_referrers: [...],
           devices: { mobile: 0.71, desktop: 0.27, other: 0.02 },
           freshness_seconds: 60 }                # analytics lag, stated honestly

## Redirect endpoint  (https://sho.rt, public, no auth for public links)

GET /{code}
  -> 302 Location: <long_url>      Cache-Control: private, max-age=0
     301 Location: <long_url>      Cache-Control: public, max-age=86400  (opt-in)
     404                           never existed (or malformed code)
     410                           expired, deleted, or disabled for abuse
     401 / 403                     private link, viewer not signed in / not allowed

API decisions worth defending

  • The API key identifies the caller, not the user in the body. It is what quotas and rate limits hang off. Without per-key quotas, one script can burn through millions of codes an hour and fill your database with junk — the key space is huge, but your storage bill and your abuse team are not.
  • Idempotency-Key on create. A mobile client that retries a timed-out create would otherwise mint two links; harmless-looking, but it splits the owner's analytics across two codes.
  • Redirect answers 404 for "never existed" and 410 for "existed, now expired or removed". Search engines and link checkers treat them differently, and support can tell the two apart in logs.
  • The redirect endpoint lives on the root path of a short domain (sho.rt/{code}), so the management API must sit under a prefix like /api/, and words such as api, login, admin must be reserved from aliases.
  • PATCH of the destination is allowed but audited. Changing where a popular link points is a known attack (a harmless link goes viral, then is swapped to a phishing page), so edits are re-scanned and logged.

Step 4 — Data model

Observations first: billions of small rows (under 1 KB); every read is a lookup by exact key; the only relationship is "which user owns this link"; reads outnumber writes 100 to 1. That profile fits a key-value or wide-column store (DynamoDB, Cassandra) and it also fits a sharded relational database perfectly well. Say that both work and pick on operational grounds.

-- =========================================================
-- LINKS  (the source of truth; partitioned by hash(code))
-- =========================================================
links (
  code         VARCHAR(16) PRIMARY KEY,   -- 7-char KGS code, or a custom alias
  long_url     TEXT NOT NULL,             -- up to ~2 KB; validated + normalised host
  url_hash     BYTEA NOT NULL,            -- sha256(long_url): find every code for a bad URL
  owner_id     BIGINT NULL,               -- NULL for anonymous links
  is_alias     BOOLEAN NOT NULL DEFAULT FALSE,
  visibility   SMALLINT NOT NULL DEFAULT 0,   -- 0 public, 1 private (see link_acl)
  redirect     SMALLINT NOT NULL DEFAULT 302, -- 301 is an explicit opt-in
  status       SMALLINT NOT NULL DEFAULT 0,   -- 0 active, 1 disabled (abuse), 2 deleted
  created_at   TIMESTAMPTZ NOT NULL,
  expires_at   TIMESTAMPTZ NULL,          -- checked on EVERY read (lazy expiry)
  updated_at   TIMESTAMPTZ NOT NULL
);
-- NOT here: a click counter. See click_rollups.
CREATE INDEX ON links (url_hash);                        -- abuse takedowns
-- Owner dashboard: a separate table / GSI partitioned by owner, not a scatter-gather
links_by_owner ( owner_id BIGINT, created_at TIMESTAMPTZ, code VARCHAR(16),
                 PRIMARY KEY (owner_id, created_at, code) );

-- =========================================================
-- ACCOUNTS AND API KEYS
-- =========================================================
users    ( id BIGINT PRIMARY KEY, email TEXT UNIQUE NOT NULL, plan TEXT NOT NULL,
           created_at TIMESTAMPTZ NOT NULL );
api_keys ( key_hash BYTEA PRIMARY KEY,           -- store a hash, never the raw key
           user_id BIGINT NOT NULL, quota_per_day INT NOT NULL,
           quota_per_min INT NOT NULL, revoked BOOLEAN NOT NULL DEFAULT FALSE );

-- =========================================================
-- PRIVATE LINKS
-- =========================================================
link_acl ( code VARCHAR(16), principal TEXT,     -- 'user:42' or 'group:eng'
           PRIMARY KEY (code, principal) );      -- one partition per code

-- =========================================================
-- KEY GENERATION SERVICE  (its own small database)
-- =========================================================
unused_keys ( key CHAR(7) PRIMARY KEY );         -- rolling pool, topped up offline
used_keys   ( key CHAR(7) PRIMARY KEY,           -- handed out (assigned or burned)
              handed_to TEXT, handed_at TIMESTAMPTZ );

-- =========================================================
-- ANALYTICS  (OLAP store: ClickHouse / Druid / BigQuery)
-- =========================================================
click_rollups ( code VARCHAR(16), bucket TIMESTAMP,   -- minute, hour or day
                country CHAR(2), referrer_domain TEXT, device TEXT,
                is_bot BOOLEAN, clicks BIGINT,
                PRIMARY KEY (code, bucket, country, referrer_domain, device, is_bot) );
-- raw click events: Parquet in object storage, 90-day retention

-- =========================================================
-- CACHE  (Redis)
-- =========================================================
SET link:Xk29aQ1  '{"u":"https://shop.example/...","x":1806000000,"s":0,"r":302}' EX 86400
SET link:nope123  '__missing__' EX 60                  -- negative cache

Modelling decisions to explain

  • The primary key is the code itself, not a surrogate integer. Every redirect is WHERE code = ?; a surrogate would add an index hop to the hottest query in the system.
  • No click counter on the link row. A viral link gets thousands of clicks per second. UPDATE links SET clicks = clicks + 1 turns the hottest row into a lock-contention hotspot and puts a write on every read. Clicks go to a log; counts live in separate rollup tables.
  • No UNIQUE(long_url). We decided in Step 1 that the same URL may have many codes. If product wants "reuse my existing link for this URL", that is a per-owner lookup index (owner_id, url_hash), not global uniqueness.
  • url_hash is stored so abuse tooling can find every code pointing at a newly reported bad URL in one indexed query and disable them all at once.
  • SQL vs NoSQL? Choose DynamoDB/Cassandra if you want effortless horizontal scaling and are happy with single-key access only. Choose sharded Postgres/MySQL (or a Vitess-style layer) if you want the owner dashboard queries, conditional inserts and transactions for free. The access pattern is simple enough that either is a defensible answer; what is not defensible is claiming you need joins.

Step 5 — High-level design

flowchart LR subgraph create [Create path] OWN[Owner / API client] --> LB1[Load balancer] LB1 --> API[Link API service
auth, quota, validation] API --> KGS[Key Generation Service] KGS --> KDB[(Key DB
unused / used)] API --> LDB[(Links store
sharded by code)] API --> SCAN[Safety scanner
async] end subgraph redirect [Redirect path] BR[Browser] --> EDGE[CDN / edge] EDGE --> LB2[Load balancer] LB2 --> RED[Redirect service
stateless] RED --> LC[In-process
hot-key cache] RED --> RC[(Redis cluster)] RC -->|miss| LDB RED -->|click event| K[(Kafka: clicks)] end K --> STREAM[Stream aggregator] STREAM --> OLAP[(Rollups / OLAP)] OLAP --> DASH[Analytics API] SCAN --> LDB

Two paths with opposite profiles. Creates are rare, authenticated and can afford a few extra milliseconds for validation and key allocation. Redirects are public and hot, and touch nothing but caches in the common case. Clicks leave the redirect path as fire-and-forget events.

What each component owns

  • Link API service — validation, normalisation, auth, quotas, alias checks, writing the link row. Stateless.
  • Key Generation Service (KGS) — the only thing that knows which codes are free. Hands out batches of pre-generated random codes.
  • Links store — the source of truth for code → destination, partitioned by code, replicated three ways.
  • Redirect service — a tiny, separately deployed and separately scaled fleet. Its only job: resolve, check expiry/status/permission, emit a click event, answer 301/302/404/410.
  • Redis cluster plus a small in-process cache for the handful of viral codes.
  • Kafka + stream aggregator + OLAP store — the analytics pipeline. If all three are down, redirects still work.
  • Safety scanner — checks destinations against threat feeds after creation and on a schedule; flips status to disabled.

Where the load balancers go

There are three natural places: between clients and the app servers, between app servers and the cache tier, and between app servers and the database tier. In practice the second and third are usually client-side — the Redis cluster client and the database driver know the partition map and route directly — while the first is a real L7 balancer. Start with round robin: it is simple and pulls dead nodes out on failed health checks. Its weakness is that it ignores load; a node stuck in a long GC pause keeps receiving its share. Move to least-outstanding-requests (or power-of-two-choices) so slow nodes naturally receive less. For redirects, put an anycast CDN/edge in front of everything: TLS terminates close to the user, and the edge can absorb bot floods.

Step 6 — Walk one redirect end to end

sequenceDiagram participant B as Browser participant E as Edge / CDN participant R as Redirect service participant L as In-process cache participant C as Redis participant D as Links store participant K as Kafka B->>E: GET /Xk29aQ1 E->>R: forward (not cached: 302 is private) R->>R: validate charset and length R->>L: get Xk29aQ1 L-->>R: miss R->>C: GET link:Xk29aQ1 C-->>R: miss R->>D: SELECT by code (replica) D-->>R: destination, expires_at, status R->>C: SET link:Xk29aQ1 EX 86400 plus jitter R->>R: check expiry, status, permission R-->>B: 302 Location: https://shop.example/spring-sale R-)K: click event (async, batched) B->>B: follows Location to destination

The worst case — a miss in both caches — costs one replica read. The common case ends at the in-process cache or Redis, a few hundred microseconds to a millisecond. The click event is published after the response is written and never blocks it.

The order of operations, and why

  1. Reject malformed codes before any I/O. Scanners and bots request /wp-login.php and /../../etc/passwd all day. A charset and length check turns those into free 404s instead of cache misses and database reads.
  2. Check the caches before the store, and cache the misses too. A burst of requests for a code that does not exist (someone enumerating, or a typo in a printed flyer) would otherwise bypass the cache every time. Store a short-lived "not found" marker.
  3. Check expiry and status on every read, even from cache. The cleanup job may be days behind; correctness cannot depend on it. This is the lazy-expiry rule.
  4. Write the response, then publish the click. The event goes into an in-memory buffer that a background thread flushes to Kafka in batches. If the buffer is full, drop the event and increment a counter. Losing 0.01% of click events is acceptable; adding 5 ms to every redirect is not.

301 or 302 — the question that is really about analytics

StatusBrowser behaviourEffect for the shortenerUse when
301 Moved PermanentlyCaches the redirect, often indefinitely; later clicks never reach youLowest load, but clicks are invisible, and you cannot change or disable the destination for anyone who already clickedOwner explicitly wants a permanent alias and no analytics
302 FoundNot cached by default; every click comes backEvery click is counted; destination edits and abuse takedowns take effect immediatelyThe default for a shortener
307 Temporary RedirectLike 302, but guarantees the method is preservedSame as 302; matters only if something POSTs to a short linkAPI-style links
308 Permanent RedirectLike 301, method preservedSame trade-off as 301Rare

The wrong answer is "301, because it is cheaper". It is cheaper precisely because you stop seeing the traffic — which is the product — and a cached 301 to a destination that later turns malicious can never be taken back. Say "302 with Cache-Control: private, max-age=0 by default, 301 as an opt-in", and mention that the load saved by 301 is load a cache already absorbs.

Step 7 — Generating the short code

This is the core algorithmic question. There are four families of answers; know all four and why three of them lose.

ApproachHow it worksStrengthFatal flaw (or cost)
Hash + truncateSHA-256 or MD5 of the URL, take ~42 bits, base62-encode to 7 charsStateless, no coordinationSame URL always yields the same code (violates Step 1); collisions grow with the table and need a check-and-retry on every insert
Hash of URL + salt/user/sequenceHash url + user_id or url + counterDistinct codes per userStill collides by the birthday bound; anonymous users have no id; a counter brings back the coordination you hoped to avoid
Counter + base62Auto-increment or Snowflake ID, encodedNever collides, simpleSequential codes are enumerable: anyone can walk ...aQ1, ...aQ2 and scrape every link. Snowflake IDs are 64-bit, so the code is 11 chars, not 7
Pre-generated random keys (KGS)Generate random unique codes offline; hand them outShort, unguessable, no collision check on the hot pathA new service to run, and a little bookkeeping — the right trade

A fifth option is random code + conditional insert (INSERT ... IF NOT EXISTS, retry on conflict). With a 3.5T space and under 1% used, the retry rate stays tiny, and it needs no extra service. It is a perfectly good answer for a smaller system; the KGS is what you reach for when you want zero retries and a way to reserve key ranges per region.

import hashlib, math

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
INDEX = {ch: i for i, ch in enumerate(ALPHABET)}
BASE = len(ALPHABET)                      # 62

def encode(n: int, width: int = 0) -> str:
    """Integer -> base62, left-padded to `width` so every code has the same length."""
    if n < 0:
        raise ValueError("negative")
    digits = []
    while True:
        n, r = divmod(n, BASE)
        digits.append(ALPHABET[r])
        if n == 0:
            break
    return "".join(reversed(digits)).rjust(width, ALPHABET[0])

def decode(code: str) -> int:
    n = 0
    for ch in code:
        n = n * BASE + INDEX[ch]          # KeyError on '-', '/', etc.: reject as 404
    return n

for n in (0, 61, 62, 3_843, 1_000_000_007, 62 ** 7 - 1):
    c = encode(n, width=7)
    assert decode(c) == n
    print(f"{n:>17,} -> {c}")

# --- Approach A: hash the long URL and truncate ---
def hash_code(url: str, length: int = 7, salt: int = 0) -> str:
    digest = hashlib.sha256(f"{url}#{salt}".encode()).digest()
    n = int.from_bytes(digest[:8], "big") % BASE ** length
    return encode(n, width=length)

print(hash_code("https://example.com/spring-sale?utm_source=mail"))
print(hash_code("https://example.com/spring-sale?utm_source=mail"))   # deterministic
print(hash_code("https://example.com/spring-sale?utm_source=mail", salt=1))

# Birthday bound: expected colliding pairs when k codes are drawn at random from N
def expected_collisions(k: int, n: int) -> float:
    return k * (k - 1) / (2 * n)

N7 = BASE ** 7
for k in (1_000_000, 100_000_000, 24_000_000_000):
    p_next = k / N7                        # chance the NEXT insert collides
    print(f"{k:>14,} links: ~{expected_collisions(k, N7):>14,.1f} collisions so far,"
          f" next insert collides with p={p_next:.5%}")

# Pure brute force: shrink the space to see collisions happen for real
small = 62 ** 3                            # 238,328 codes
seen, first_hit = set(), None
for i in range(small):
    c = hash_code(f"https://site.test/page/{i}", length=3)
    if c in seen:
        first_hit = i
        break
    seen.add(c)
print(f"3-char space {small:,}: first collision after {first_hit:,} inserts"
      f" (sqrt(pi*N/2) predicts ~{math.sqrt(math.pi * small / 2):,.0f})")
Output
                0 -> 0000000
               61 -> 000000z
               62 -> 0000010
            3,843 -> 00000zz
    1,000,000,007 -> 015ftgN
3,521,614,606,207 -> zzzzzzz
CFTu0a9
CFTu0a9
iwvt9tQ
     1,000,000 links: ~           0.1 collisions so far, next insert collides with p=0.00003%
   100,000,000 links: ~       1,419.8 collisions so far, next insert collides with p=0.00284%
24,000,000,000 links: ~  81,780,669.4 collisions so far, next insert collides with p=0.68151%
3-char space 238,328: first collision after 1,097 inserts (sqrt(pi*N/2) predicts ~612)

What this code shows

  • Base62, not base64. Base64 adds + and /, which are special characters in URLs; URL-safe base64 uses - and _, which is fine for machines but awkward to read aloud. Base62 is the usual compromise. Some services also drop look-alike characters (0 O 1 l I) and use base56 or base58 for codes people will type from paper.
  • Hashing is deterministic — the same URL produced the same code twice. That is a bug for us (two marketers, one landing page) unless you salt it, and then you have lost the only advantage hashing had.
  • The birthday bound bites earlier than intuition says. In a 238k-code space the first collision arrived after about a thousand inserts, not a hundred thousand. At 24B links in a 7-char space, each new insert collides with probability ~0.7%, so a hash-based scheme needs a read-before-write (or a conditional write plus retry) on every create forever.
  • Normalisation is its own trap. HTTP://Shop.Example/a?x=1, http://shop.example/a?x=1 and http://shop.example/a?x%3D1 may or may not be the same resource. Lower-case the scheme and host, drop default ports, and leave the path and query exactly as given — "fixing" percent-encoding in the path can change which page loads.

Step 8 — The Key Generation Service

The KGS generates random 7-character codes ahead of demand, stores them in a key database with two logical sets — unused and used — and hands them to app servers in batches. Because every code was unique when generated, the create path never checks for collisions.

import random
from collections import deque

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

class KeyDB:
    """Two tables, as in the classic design: keys not yet handed out, and keys that were."""
    def __init__(self, n_keys: int, length: int, seed: int = 7):
        rng = random.Random(seed)
        keys = set()
        while len(keys) < n_keys:                       # generated OFFLINE, ahead of demand
            keys.add("".join(rng.choice(ALPHABET) for _ in range(length)))
        self.unused = deque(sorted(keys))
        rng.shuffle(self.unused)                        # random order: codes are not guessable
        self.used = set()

class KGS:
    """Hands out keys in batches. The move unused -> used happens BEFORE the batch
    leaves, inside one critical section, so no two callers can ever see the same key."""
    def __init__(self, db: KeyDB):
        self.db = db
        self.batches_served = 0

    def take_batch(self, size: int) -> list[str]:
        # In production: DELETE ... RETURNING / a Redis SPOP / an atomic range claim.
        batch = [self.db.unused.popleft() for _ in range(min(size, len(self.db.unused)))]
        self.db.used.update(batch)                      # marked used even if never assigned
        self.batches_served += 1
        return batch

class AppServer:
    def __init__(self, name: str, kgs: KGS, batch_size: int):
        self.name, self.kgs, self.batch_size = name, kgs, batch_size
        self.local: deque[str] = deque()                # in-memory key buffer

    def shorten(self, long_url: str, store: dict) -> str:
        if not self.local:
            self.local.extend(self.kgs.take_batch(self.batch_size))
        code = self.local.popleft()
        assert code not in store, "duplicate code!"     # the property we care about
        store[code] = long_url
        return code

    def crash(self) -> int:
        lost = len(self.local)                          # keys burned, never reused
        self.local.clear()
        return lost

db = KeyDB(n_keys=20_000, length=6)
kgs = KGS(db)
servers = [AppServer(f"app-{i}", kgs, batch_size=500) for i in range(4)]
store, lost = {}, 0
rng = random.Random(42)

for req in range(12_000):                               # requests land on random servers
    rng.choice(servers).shorten(f"https://site.test/{req}", store)
    if req == 6_000:
        lost += servers[2].crash()                      # app-2 dies mid-batch

print(f"links created:  {len(store):,}   distinct codes: {len(set(store)):,}")
print(f"batches served: {kgs.batches_served}   keys marked used: {len(db.used):,}")
print(f"burned by crash: {lost}   still buffered in live servers: "
      f"{sum(len(s.local) for s in servers)}   unused left: {len(db.unused):,}")
print("sample codes:", list(store)[:4])

# --- Why the critical section matters: a racy KGS that reads THEN marks ---
unused, used, handed = deque(["aZ3k9Q", "Pq81xL"]), set(), []
def racy_read():            return unused[0]            # SELECT key FROM unused LIMIT 1
def racy_mark(key):
    if key in unused: unused.remove(key)
    used.add(key)                                       # UPDATE ... SET used = true
a = racy_read(); b = racy_read()                        # two servers interleave here
racy_mark(a); racy_mark(b); handed += [a, b]
print("racy KGS handed out:", handed, "-> duplicate!" if a == b else "")
Output
links created:  12,000   distinct codes: 12,000
batches served: 26   keys marked used: 13,000
burned by crash: 496   still buffered in live servers: 504   unused left: 7,000
sample codes: ['xBnXCD', 'ZVQOk6', 'xkh5pf', '2CygkS']
racy KGS handed out: ['aZ3k9Q', 'aZ3k9Q'] -> duplicate!

The design points, one by one

  • Concurrency. The last lines show the bug: two servers read the same "next free key" before either marks it used. The fix is to make take and mark one atomic step — DELETE FROM unused_keys ... RETURNING key with SKIP LOCKED, a Redis SPOP key n, or a single KGS process that serialises handouts behind a lock. Keys move to used the moment they leave the KGS, not when they are assigned to a link.
  • Batching. App servers take 500–1,000 keys at a time and hand them out from memory, so the KGS sees one call per few seconds per server rather than one per create. It is off the hot path entirely.
  • Crashes waste keys, and that is fine. The simulated crash burned 496 keys. At 3.5T keys, losing a thousand per crash per server for a decade is a rounding error. Trying to "return" unassigned keys on shutdown adds a failure mode for no benefit.
  • Single point of failure? The KGS is one, but a soft one: every app server holds a buffer of keys, so a KGS outage stops creates only after the buffers drain — minutes, not milliseconds. Run a standby replica, or better, give each KGS instance a disjoint slice of the key space so several run active-active with no coordination at all.
  • Key DB size. You do not pre-generate all 3.5T codes (that would be ~25 TB of strings). Keep a rolling pool of, say, a few hundred million unused keys and top it up in the background; generate new candidates randomly, and drop any that already exist in used or as an alias.
  • Reusing purged keys. You can return the code of a deleted or expired link to the pool, but do not do it quickly: someone may still hold the old link in an email, and re-pointing it at a stranger's page is a privacy and security hole. Quarantine recycled codes for a year, or simply never recycle — the space is big enough.
  • Multi-region. Give each region its own key slice (for example, the KGS in each region only generates codes whose hash falls into its range), so regions never hand out the same key even during a network partition.

Step 9 — Custom aliases

  • Same table, same key space. An alias is just a code the user chose. Insert with a conditional write (INSERT ... ON CONFLICT DO NOTHING / DynamoDB attribute_not_exists(code)) and return 409 ALIAS_TAKEN if it fails. Never "check then insert" — two users requesting launch at the same moment will both pass the check.
  • Keep aliases out of the generated range. Either require aliases to be at least 8 characters or contain a -, or have the KGS skip any code that exists as an alias. Otherwise a user can take Xk29aQ1 before the KGS hands it out, and the KGS's "unique" key collides.
  • Reserved words. Block api, admin, login, static, health, brand names and a profanity list. Limit length (16 is typical) and charset ([A-Za-z0-9_-]).
  • Case sensitivity. Generated codes are case-sensitive (that is where base62's density comes from), but aliases are read aloud and typed, so normalise aliases to lower case at creation and at lookup — or users will create Launch and launch as different links and confuse everyone.
  • Squatting. Short, attractive aliases (/sale, /jobs) are a finite resource. Restrict aliases shorter than 5 characters to paid or verified accounts.

Step 10 — Partitioning and replication

At 10 TB you need several database nodes. The question is what decides which node a link lives on.

import bisect, hashlib, random
from collections import Counter

rng = random.Random(3)
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
codes = ["".join(rng.choice(ALPHABET) for _ in range(7)) for _ in range(60_000)]
# Destinations are wildly skewed: most links point at a handful of big sites.
sites = ["www.amazon", "www.youtube", "docs.google", "zoom.us", "github", "news.site"]
long_urls = [rng.choices(sites, weights=[40, 25, 15, 10, 7, 3])[0] for _ in codes]

def spread(counter, shards=4):
    loads = sorted(counter.values(), reverse=True)
    return f"max/min shard load = {loads[0] / loads[-1]:.2f}"

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

# 1. Range on the FIRST LETTER OF THE LONG URL: 'w' swallows everything.
by_url_letter = Counter(min(ord(u[0]) - ord("a"), 25) * 4 // 26 for u in long_urls)
print("range on long_url letter :", spread(by_url_letter))
# 2. Range on the first char of a RANDOM code: fine, because the codes are uniform.
by_code_char = Counter(ALPHABET.index(c[0]) * 4 // 62 for c in codes)
print("range on random code char:", spread(by_code_char))
# 3. Hash of the code, mod N.
print("hash(code) mod 4         :", spread(Counter(h(c) % 4 for c in codes)))

# Adding a 5th shard: how many keys have to move?
moved_mod = sum(1 for c in codes if h(c) % 4 != h(c) % 5) / len(codes)

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
        self.hashes = [p for p, _ in self.points]
    def owner(self, key):
        i = bisect.bisect(self.hashes, h(key)) % len(self.points)
        return self.points[i][1]

before, after = Ring(["s0", "s1", "s2", "s3"]), Ring(["s0", "s1", "s2", "s3", "s4"])
moved_ring = sum(1 for c in codes if before.owner(c) != after.owner(c)) / len(codes)
print(f"add a 5th shard -> mod-N moves {moved_mod:.0%} of keys, consistent hashing moves {moved_ring:.0%}")
Output
range on long_url letter : max/min shard load = 24.22
range on random code char: max/min shard load = 1.08
hash(code) mod 4         : max/min shard load = 1.01
add a 5th shard -> mod-N moves 80% of keys, consistent hashing moves 20%
  • Range-based partitioning on the long URL (all destinations starting with a on shard 1, and so on) is the classic wrong answer: destinations cluster on a few big sites, so one shard gets 24x the load of another. It also partitions on a field you never look up by.
  • Range on the code is actually balanced — because KGS codes are uniformly random — and it keeps range scans possible. But custom aliases are not random (lots of sale-...), and a future change to how codes are generated could silently skew it.
  • Hash of the code is the robust default: balanced regardless of how codes are made, and every lookup is a single-shard point read.
  • Consistent hashing (with virtual nodes) is what makes adding capacity cheap: going from four shards to five moved ~20% of keys instead of ~80%. DynamoDB and Cassandra do this for you; with sharded SQL you do it with a fixed number of logical shards (say 1,024) mapped onto physical hosts, and move logical shards whole.
  • Replication: three replicas across availability zones. Redirects read from any replica — a few hundred ms of replication lag is fine for everything except "I just created this and clicked it", which you solve by writing the new link into Redis at creation time (write-through for creates), so the first click never depends on a replica catching up.
  • Owner queries ("list my links") do not know the code, so they would scatter to every shard. Serve them from a secondary index partitioned by owner_id (a global secondary index in DynamoDB, or a separate links_by_owner table).

Step 11 — Caching

Redirect traffic is extremely skewed: a tiny number of links get most of the clicks, and most links are clicked a handful of times in their first week and never again. That is the ideal shape for an LRU cache.

import random, itertools
from collections import OrderedDict

class LRUCache:
    """What Redis 'allkeys-lru' approximates: a hash map plus recency order."""
    def __init__(self, capacity: int):
        self.capacity, self.data = capacity, OrderedDict()
        self.hits = self.misses = 0

    def get(self, key, load):
        if key in self.data:
            self.data.move_to_end(key)          # touched: now most recent
            self.hits += 1
            return self.data[key]
        self.misses += 1
        value = self.data[key] = load(key)      # cache-aside fill on miss
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)       # evict least recently used
        return value

    @property
    def hit_rate(self):
        return self.hits / (self.hits + self.misses)

LINKS, REQUESTS = 100_000, 400_000
rng = random.Random(1)
# Zipf-like popularity: link k gets weight 1/k. A few links are viral, most are nearly dead.
cum = list(itertools.accumulate(1 / k for k in range(1, LINKS + 1)))
traffic = rng.choices(range(LINKS), cum_weights=cum, k=REQUESTS)

top20 = sum(1 for t in traffic if t < LINKS * 0.2) / REQUESTS
print(f"share of clicks going to the top 20% of links: {top20:.0%}")

for pct in (0.5, 2, 5, 20):
    cache = LRUCache(int(LINKS * pct / 100))
    for code in traffic:
        cache.get(code, load=lambda c: f"https://dest/{c}")
    print(f"cache holds {pct:>4}% of links -> hit rate {cache.hit_rate:.1%}")
Output
share of clicks going to the top 20% of links: 87%
cache holds  0.5% of links -> hit rate 43.9%
cache holds    2% of links -> hit rate 57.2%
cache holds    5% of links -> hit rate 66.2%
cache holds   20% of links -> hit rate 79.7%

Reading the result

  • The 80/20 rule holds roughly — here 87% of clicks went to the top 20% of links — and caching 20% of links gave an ~80% hit rate. The hit rate includes cold misses (the very first click on each link always misses), which is why real systems with repeat traffic do better than this simulation.
  • Returns diminish fast. Going from 0.5% to 2% of links bought 13 points of hit rate; from 5% to 20% bought 13 more for four times the memory. Size the cache from measured hit-rate curves, not from a formula.
  • LRU is the right default because popularity decays with age: yesterday's viral link is today's dead one. LFU keeps old celebrities too long. Redis allkeys-lru (or allkeys-lfu with decay) implements this approximately, with random sampling instead of an exact linked list.

Cache design details

  • Cache-aside for reads, write-through for creates. Creates write the new link to Redis immediately, which covers the "click my own link" case and replica lag. Reads fill on miss.
  • TTL of about a day, with jitter (±10%), so a burst of links created together does not expire together. The TTL is a safety net; the eviction policy does the real work.
  • Invalidation on change. Delete, disable or edit → DEL link:{code} in Redis and publish an invalidation message that app servers use to drop their in-process copy. Because in-process caches are only a few seconds of TTL, a missed invalidation self-heals quickly.
  • Negative caching. Cache "not found" for 30–60 s so enumeration attempts and broken links do not hammer the store. Keep it short: a link may be created seconds after a miss.
  • Hot keys. A link in a Super Bowl ad might get 100k clicks per second — more than one Redis shard wants to serve for one key. Add a tiny in-process LRU (a few thousand entries, 5–10 s TTL) in every redirect server; at 50 servers that turns 100k Redis reads per second into roughly 10. Detect hot keys by sampling and promote them, rather than caching everything locally.
  • Stampede protection. When a hot key misses, only one request per server should go to the database (single-flight / request coalescing); the rest wait for its result.
  • Cache replicas. With a Redis cluster, each shard has a replica for failover; reads can go to replicas if one shard's primary is saturated. If the whole cache tier is lost, the database must survive the cold start — which is another reason for the in-process layer and for pre-warming the top links from yesterday's analytics.

Step 12 — Low-level design: the redirect handler

The redirect service is small enough to write out completely. The interesting parts are the order of checks, lazy expiry, negative caching and the non-blocking analytics buffer.

from collections import deque
from dataclasses import dataclass

ALPHABET = set("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_")

@dataclass
class Link:
    code: str
    long_url: str
    expires_at: float | None = None
    status: str = "active"            # active | disabled (abuse) | deleted
    permanent: bool = False           # owner opted in to 301 (no analytics wanted)

MISSING = object()                    # negative-cache sentinel

class Redirector:
    def __init__(self, db: dict, clock, event_buffer_size: int = 3):
        self.db, self.clock = db, clock
        self.cache: dict[str, object] = {}
        self.events: deque = deque()
        self.buffer_size = event_buffer_size
        self.dropped = 0

    def _lookup(self, code: str):
        hit = self.cache.get(code)
        if hit is not None:
            return None if hit is MISSING else hit
        link = self.db.get(code)
        self.cache[code] = link if link else MISSING   # cache 404s too (short TTL in prod)
        return link

    def handle(self, code: str, meta: dict) -> tuple[int, dict]:
        # 1. Cheap rejects before any I/O: bad charset or length can never exist.
        if not (1 <= len(code) <= 16) or not set(code) <= ALPHABET:
            return 404, {}
        link = self._lookup(code)
        if link is None:
            return 404, {}
        # 2. Lazy expiry: an expired link is never served, even if the sweeper is behind.
        if link.expires_at is not None and self.clock() >= link.expires_at:
            self.cache.pop(code, None)
            return 410, {}                               # Gone: it existed, and ended
        if link.status != "active":
            return 410, {}
        # 3. Fire-and-forget analytics: bounded buffer, drop rather than block.
        if len(self.events) < self.buffer_size:
            self.events.append({"code": code, "ts": self.clock(), **meta})
        else:
            self.dropped += 1
        if link.permanent:
            return 301, {"Location": link.long_url, "Cache-Control": "max-age=86400"}
        return 302, {"Location": link.long_url, "Cache-Control": "private, max-age=0"}

now = [1_000.0]
db = {
    "Xk29aQ1": Link("Xk29aQ1", "https://shop.example/spring-sale"),
    "promo":   Link("promo", "https://shop.example/promo", expires_at=1_500.0),
    "docs":    Link("docs", "https://docs.example/start", permanent=True),
    "b4dL1nk": Link("b4dL1nk", "https://phish.example/login", status="disabled"),
}
r = Redirector(db, clock=lambda: now[0])
meta = {"country": "IN", "referrer": "t.co"}

for code in ("Xk29aQ1", "promo", "docs", "b4dL1nk", "nope123", "../etc", "Xk29aQ1"):
    print(f"{code:<8}", *r.handle(code, meta))
now[0] = 2_000.0                                         # time passes: promo expires
print("promo after expiry:", r.handle("promo", meta)[0])
print(f"events buffered: {len(r.events)}   dropped: {r.dropped}")
Output
Xk29aQ1  302 {'Location': 'https://shop.example/spring-sale', 'Cache-Control': 'private, max-age=0'}
promo    302 {'Location': 'https://shop.example/promo', 'Cache-Control': 'private, max-age=0'}
docs     301 {'Location': 'https://docs.example/start', 'Cache-Control': 'max-age=86400'}
b4dL1nk  410 {}
nope123  404 {}
../etc   404 {}
Xk29aQ1  302 {'Location': 'https://shop.example/spring-sale', 'Cache-Control': 'private, max-age=0'}
promo after expiry: 410
events buffered: 3   dropped: 1

What an interviewer is listening for

  • Validation before I/O. ../etc never touched a cache or a database.
  • Negative caching with a sentinel, so a missing code is as cheap as a present one.
  • Lazy expiry: promo redirected at t=1,000 and returned 410 at t=2,000 with no cleanup job involved.
  • A bounded event buffer that drops rather than blocks — the fourth event was dropped and counted, and the redirect was unaffected.
  • Per-link 301/302 choice, with explicit Cache-Control so an intermediary cannot cache a 302 by mistake.
  • Disabled links. Here they return 410. Real products often show an interstitial warning page instead ("this link was reported as phishing") so a user knows why it did not open.

Step 13 — Expiry and cleanup

  • Lazy deletion is the correctness mechanism. Every read checks expires_at. An expired link is never served, whether or not it has been physically deleted yet.
  • A background sweeper is the storage mechanism. It walks one shard at a time, off-peak, in small batches (a few thousand rows with pauses), deleting rows past expiry plus a grace period. Aggressively scanning for expired rows at peak would compete with redirects for the same disks.
  • Let the store do it where possible. DynamoDB TTL and Cassandra TTL delete expired items in the background for free. In Postgres, partition by creation month and drop old partitions for links that all share the default expiry.
  • Default expiry. Anonymous links expire after a year unless someone clicks them; account links never expire by default. Deleting links that have not been clicked in six months is tempting, but storage is cheap (all ten years is ~10 TB) and a dead link in a printed book is a real user complaint. Keep them.
  • Keys after expiry. As in Step 8: quarantine, or never recycle.

Step 14 — Click analytics

Analytics is the product for paying customers, and it is also the part most candidates get wrong by putting a counter on the link row. Here is the pipeline.

flowchart LR R[Redirect servers
in-memory buffer] -->|batched produce| K[(Kafka topic: clicks
partitioned by code)] K --> ENR[Enricher
geo-IP, UA parse, bot filter] ENR --> AGG[Stream aggregator
1-min windows per code] AGG --> RT[(Realtime counters
Redis / OLAP)] AGG --> ROLL[(Hourly and daily rollups
code, bucket, country, count)] K --> RAW[(Raw events in object storage
Parquet, 90-day retention)] RAW --> BATCH[Nightly batch job
recompute and correct] BATCH --> ROLL ROLL --> DAPI[Analytics API] RT --> DAPI

The redirect server's only analytics work is appending to a buffer. Everything else happens downstream and can lag, fail and be replayed without users noticing.

  • What to capture per click: code, timestamp, country and city (from IP, then discard or truncate the IP for privacy), referrer, user agent (parsed to browser/OS/device), and a bot flag. Do not store raw IPs longer than you need.
  • Partition the Kafka topic by code so all clicks for a link go to one partition and one aggregator can count them without cross-worker coordination. A viral code makes one partition hot; split its key (code#0..code#7) and merge in the rollup.
  • Aggregate in windows, write rollups. The aggregator keeps per-minute counters in memory and writes (code, minute, country) → count once per window — one write per bucket instead of one per click. Hourly and daily tables are rolled up from those. The dashboard reads rollups, never raw events.
  • Exactly-once is not required, but double counting on replay is ugly. Give each event an id; the aggregator's windowed writes are idempotent upserts keyed by (code, bucket, dims), and commit Kafka offsets together with the state (Flink/Kafka Streams do this). The nightly batch job over raw events is the source of truth and corrects any drift.
  • Bots. Link-preview crawlers (chat apps and social networks fetch every link to render a preview), security scanners and uptime checkers can outnumber humans on a fresh link. Flag them by user agent and behaviour and report "human clicks" separately — customers notice when their numbers look inflated.
  • If Kafka is down, redirect servers keep a bounded local buffer, then drop and count. Redirects never fail because analytics did.

Step 15 — Security, permissions and abuse

Private links

Store a visibility on each link (public or private) and, for private links, an ACL table keyed by code whose rows are the user ids or groups allowed to open it. The redirect service checks the viewer's session cookie against the ACL and returns 401 (not logged in) or 403 (logged in, not allowed). Private links must never be served with a cacheable redirect, and their ACL is cached with a short TTL so revocations take effect quickly. With a wide-column store, the ACL row key is the code and the column names are the allowed user ids — one point read.

Abuse and phishing

Short links hide the destination, which makes them a favourite tool for phishing and malware. A shortener that does not fight this ends up on blocklists itself, and then every link on the domain stops working in email clients and browsers.

  • At creation: rate-limit per API key, per account and per IP (Lesson 9); require captcha for anonymous bursts; reject destinations on known threat lists; block shortening other shorteners' links (redirect chains are a classic evasion trick).
  • After creation: scan asynchronously against threat-intelligence feeds, and re-scan periodically — attackers create a clean link, wait for it to spread, then change what the destination serves.
  • On report: use the url_hash index to disable every code pointing at the bad URL, DEL them from cache, and serve a warning interstitial.
  • Enumeration: random codes make guessing expensive (with 24B links in 3.5T codes, a random guess hits a real link 0.7% of the time — which is why sensitive links must be private, not merely obscure). Rate-limit 404s per IP at the edge.
  • Open-redirect abuse and the preview trick: offer a preview URL (sho.rt/Xk29aQ1+) that shows the destination without following it, which is a trust feature for cautious users.

Step 16 — Going multi-region

  • Redirects are read-only and global, so serve them from every region: anycast or latency-based DNS sends users to the nearest one, each with its own cache and a local read replica of the links store.
  • Creates can be multi-writer without conflicts because each region's KGS owns a disjoint key slice. Two regions can never mint the same code, so a globally replicated table (DynamoDB global tables, Cassandra multi-DC) never sees a write conflict on the code. Custom aliases are the exception: route alias claims to one home region (or use a strongly consistent global table) so two regions cannot grant launch to two people.
  • The replication gap. A link created in Mumbai and clicked a second later in Frankfurt may not have replicated. Mitigate by publishing the new link directly into every region's cache at creation, or by having a local miss fall back to the home region (the code's key slice identifies it) before returning 404.
  • Deletions and takedowns must propagate fast. Send them as broadcast invalidations to every region's cache, not only through replication.
  • Failover: if a region dies, DNS stops sending traffic there; every other region already has the data. Creates for that region's key slice pause until another region takes over its slice (a lease, or pre-allocated backup slices).

Step 17 — Failure modes

What failsWhat users seeMechanism
One Redis shard downSlightly slower redirects for some linksReplica promotion; in-process cache shields hot keys; single-flight to the store
Entire cache tier lostHigher latency, no errors if planned forStore sized for cold-start read rate; pre-warm top links from analytics; shed bot traffic at the edge
Links store replica lagNothingCreates are written through to cache; replica misses fall back to the primary before 404
KGS downNothing for minutes; then creates failApp-server key buffers; standby KGS or disjoint active-active slices; fall back to random-code + conditional insert
Kafka / analytics downDashboards lag; redirects unaffectedBounded buffers, drop-and-count; nightly batch recomputes
Safety scanner downNew links slightly riskier for a whileCreate still checks the synchronous blocklist; rescans catch up
Viral linkNothingIn-process hot-key cache; split hot Kafka key; edge absorbs the connection load
Short domain blocklistedEvery link broken in email and browsersPrevent it: aggressive abuse scanning, fast takedowns, a relationship with blocklist operators
A region lostUsers re-routed; slightly higher latencyData already replicated; DNS failover; key slice handed over
Enumeration or bot floodNothingCharset check, negative cache, per-IP 404 rate limits at the edge

Step 18 — Observability

  • Redirect SLIs: p50/p99 latency, error rate split by status (a jump in 404s may be a broken campaign or an enumeration attack; a jump in 5xx is you), and cache hit rate per tier.
  • Create SLIs: success rate, KGS buffer depth per server (alert well before zero), unused key pool size, alias conflict rate.
  • Analytics SLIs: Kafka consumer lag, dropped-event counter on redirect servers, gap between realtime counts and nightly batch counts.
  • Safety SLIs: time from report to takedown, share of new links flagged, blocklist status of the short domain (check it continuously; it is an existential risk).
  • Alert on symptoms: page on "redirect p99 above 50 ms for 5 minutes" or "5xx above 0.1%", not on CPU.

The trade-off summary — how to close

  • Pre-generated random keys over hashing. We pay for a small extra service; we get 7-character, unguessable codes with no collision check on the create path, and many codes per URL.
  • 302 by default over 301. We pay with more redirect traffic, which caches absorb; we keep analytics, destination edits and abuse takedowns working.
  • Hash-partitioned key-value access by code. Every redirect is one single-shard point read; owner queries go through a separate index.
  • Three cache layers (edge for connections, Redis for the working set, in-process for hot keys), with negative caching and lazy expiry. The database sees a small fraction of redirect traffic.
  • Analytics fully asynchronous through Kafka, windowed rollups and a nightly batch correction. We accept losing a tiny fraction of events in exchange for never slowing or failing a redirect.
  • Security as a first-class feature: quotas per API key, async scanning and rescanning, fast takedowns, private links with ACLs. For a shortener, abuse handling is what keeps the domain usable.
  • What I would build first: one region, Postgres with replicas, Redis, random codes with conditional inserts. The KGS, sharding and the Kafka pipeline arrive when the numbers call for them.
// Write your solution here
// Write your solution here
// Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 9Rate LimiterToken bucket, sliding window, Redis counters and where to place a limiter.