URL Shortener

URL Shortener: From Weekend Project to Global Platform

Complete course text · ready to convert into website content · Java Spring Boot + MySQL for the origin; provider-native JavaScript/TypeScript at the edge · animated diagrams noted inline

Introduction — Why URL Shorteners?

The URL Shortener is the perfect first system design problem. Not because it's easy — because everything that makes distributed systems hard is packed into a system that seems trivial on paper.

The functional requirement is a single sentence:

Turn a long URL into a short one, and when someone clicks the short one, send them to the long one.

You could build a working version over a weekend on your laptop. But real URL Shorteners at real companies serve billions of clicks per day. 📐 Public reporting suggests bit.ly handles on the order of ~10 billion clicks per month (illustrative reference, not independently verified). Twitter had to build its own (t.co) just to fit URL previews into 280-character tweets. TinyURL was one of the earliest infrastructure services acquired for its user base. 📐 The specific traffic numbers here are illustrative anchors — public figures for these services are not always independently verifiable; treat them as scale-order references, not benchmarks.

The complexity doesn't come from the logic. It comes from three things:

1. Reads dominate writes — but by how much depends on the scale. Every short link is created once but clicked many times. At startup scale the ratio is roughly ~100:1; at extreme scale it approaches ~10,000:1 because viral consumption grows without proportional URL creation growth. Your read path has to be blazing fast at every scale. Your write path can afford to be careful. Both statements are true throughout the course — but the ratio is phase-dependent because URL creation is an independent product-usage variable, not a fixed fraction of redirect traffic. See the Traffic Composition table at Phase 4 for the explicit numbers.

2. Latency is the product. A user clicks a short link and waits. If they wait more than 200 milliseconds, the experience feels broken. Every redirect must complete in tens of milliseconds. There is no acceptable "slow path."

3. You cannot lose data. If a short URL stops resolving, every promotional email, printed QR code, social media post, and business card containing that URL becomes broken forever. Uptime and durability are not features — they are the business.

By the end of this course, you will have designed a URL Shortener that starts as a weekend project and evolves into an aspirational edge-first architecture modeled at 1 billion requests per second (📐 an extreme-scale illustrative tier — no real URL Shortener currently operates at 1B RPS; we teach this scale because the architectural lessons for the frontier of possibility apply to many read-heavy services). Every architectural change will be forced by a specific bottleneck we hit — never chosen for buzzword compliance.

We build this using Java (Spring Boot 3) as the application language and MySQL as the primary database. These are deliberate choices. MySQL because it is the most operationally understood relational database on the planet — the same database that scales YouTube, Slack, GitHub, and Square. Spring Boot because it is what powers the majority of production systems at scale.

We will never migrate to NoSQL just because we hit high traffic. Instead, we will evolve MySQL — using sharding via Vitess. NoSQL is a trade-off, not an inevitability. Understanding when to make that trade (and when not to) is what senior engineers do.

[🎬 ANIMATED DIAGRAM · `evolution-simulator`]
> A single interactive widget the reader can scrub through the entire course with. Six tabs: Foundation (naive MVP) → Phase 1 (10K RPS) → Phase 2 (100K RPS) → Phase 2.5 (1M RPS) → Phase 3 (10M RPS) → Phase 4 (1B RPS). Each tab animates the architecture growing: new boxes appear with a highlight pulse, arrows redraw, a bottleneck callout at the bottom explains why the previous tier broke. The reader can navigate by clicking tabs, using prev/next arrows, or scrubbing a phase slider. No autoplay — the reader drives the story.

Let's begin.

Requirements and the API Contract

A URL Shortener sounds trivial until you write the API contract. The contract is where product ambiguity meets scale-visible consequences — and every downstream architectural decision (caching, sharding, analytics pipeline, error semantics) has to respect it. This chapter fixes the contract before we touch capacity math.

Functional requirements (canonical)

• POST /api/v1/shorten — create a short code from a long URL. Idempotent when the caller supplies an Idempotency-Key header.
• GET /{shortCode} — issue a redirect. Public, unauthenticated, cache-friendly.
• GET /api/v1/urls/{shortCode} — read metadata (creation time, click count summary, owner). Authenticated.
• DELETE /api/v1/urls/{shortCode} — deactivate. Never physically deletes at extreme scale — flags as status = DELETED so that the reverse-lookup guard still works during the KV propagation window.

Non-functional requirements

• Availability target: 99.95% for the redirect path (26 min/month downtime budget). URL-creation path can tolerate slightly lower availability without user-visible impact.
• Latency: redirect P99 < 200ms globally at Phase 4 (design target, not guarantee — see the Observability chapter for how this becomes an SLO).
• Durability: created short-code → long-URL mappings must not silently vanish. This is stronger than an availability target — a partial outage is recoverable; a lost mapping is not.

Error taxonomy (must be explicit — this is where candidates lose points in interviews and where analytics pipelines silently miscount in production)

Why 410 vs 404 matters: many URL Shorteners collapse both into 404. This is a lost teaching opportunity and a genuine bug. 404 says "this was never a thing"; 410 says "this was a thing and is intentionally gone." Analytics, SEO, and abuse-detection pipelines behave differently for the two — SEO crawlers de-index 410 immediately but re-check 404s; abuse pipelines track 410 as evidence of successful takedown. Surface the distinction in the contract, not just in the code.

Idempotency (design decision)

POST /api/v1/shorten with Idempotency-Key: <uuid> returns the same short code for the same (idempotency_key, api_key_id) for 24 hours. This lets clients safely retry on network errors without minting duplicate codes.

Implementation — and why the obvious version is broken.

The tempting implementation is: look up (idempotency_key, api_key_id) in Redis; on hit return the cached code, on miss proceed through the KGS path and cache the result. That implementation is not idempotent. It is a check-then-act race: two concurrent retries of the same request both miss the cache, both proceed to KGS, and both mint a different short code. The client that retried on a network timeout — precisely the case this feature exists to serve — now owns two URLs. The window is small, but retry storms are exactly when concurrent duplicates arrive, so the race fires when it hurts most.

Idempotency is a concurrency property, not a cache lookup. You need a primitive that atomically tests and claims in one operation:

```
SET idempotency:{apiKeyId}:{key} {requestId} NX EX 86400
```

• Winner (SET returned OK): proceeds through the KGS path, creates the URL, then writes the resulting short code back into the same key.
• Losers (SET returned nil): read the key. If it holds a completed result, return it with 201 and Idempotency-Replayed: true. If it still holds an in-progress marker, the original is still running — return 409 Conflict with Retry-After: 1 rather than blocking a request thread waiting on another request's completion.

Make the database authoritative, not Redis. Redis is a fast path, and fast paths lose data — an eviction, a failover, or an AOF truncation drops the claim and reopens the race. The durable guarantee comes from a constraint:

sql
ALTER TABLE urls
  ADD COLUMN idempotency_key VARCHAR(64) NULL,
  ADD COLUMN api_key_id      BIGINT      NULL,
  ADD CONSTRAINT uq_idempotency UNIQUE (api_key_id, idempotency_key);

Now the worst case when Redis loses the claim is a duplicate `INSERT` that MySQL rejects, not a duplicate URL. Catch the constraint violation, re-read the existing row, and return that short code. The generated code popped from the KGS queue is discarded — a leaked ID, which the KGS design already tolerates (see the KGS durability section).

Same key, different body. If a caller reuses an Idempotency-Key with a different long_url, that is a client bug, not a replay. Store a hash of the request body alongside the claim and return 422 Unprocessable Entity on mismatch. Silently returning the first URL for a second, different request is the worst available outcome — it looks like success and is not.

The teaching point: every layer here is doing one job. The SET NX collapses check-and-act into a single atomic step so the common path is fast and correct. The UNIQUE constraint makes correctness survive the cache being wrong. Neither alone is sufficient — Redis alone races on eviction, MySQL alone puts a round-trip on every retry. This layering (fast probabilistic path, durable authoritative backstop) is the same pattern as the cache-aside design in Phase 2, applied to a correctness property instead of a latency one. so observability can distinguish replays from fresh mints.

OpenAPI schema (illustrative)

yaml
paths:
  /api/v1/shorten:
    post:
      operationId: shortenUrl
      requestBody:
        content:
          application/json:
            schema:
              type: object
              required: [longUrl]
              properties:
                longUrl:    { type: string, format: uri, maxLength: 2048 }
                customAlias: { type: string, pattern: "^(?=.*[-_])[A-Za-z0-9_-]{4,20}$" }   # Option B: must contain - or _
                expiresAt:  { type: string, format: date-time }
      parameters:
        - in: header
          name: Idempotency-Key
          schema: { type: string, format: uuid }
      responses:
        "201": { description: Created }
        "409": { description: Custom alias already taken }
        "429": { description: Rate limited }

What you now understand

The API contract is not paperwork. It is the boundary where product decisions (410 vs 404, idempotency semantics, custom-alias validation regex) become architecturally binding. Every downstream cache, analytics event, and CDN rule must respect it. Every decision the rest of this course makes about capacity, sharding, and edge caching starts with these five endpoints.

Canonical Capacity Model

Before we design a single line of architecture, we agree on the ceiling numbers we will use throughout the course. Every capacity claim in every phase derives from this one table. If you find a number elsewhere in the course that seems to disagree with this table, this table is the source of truth.

Each row carries a provenance label so you can tell the difference between "AWS publishes this" and "this course assumes this":

• 📗 VERIFIED DOC — number stated in official vendor documentation
• 📊 PUBLISHED BENCHMARK — number from a reproducible third-party benchmark (TechEmpower, Percona sysbench, redis.io, Confluent)
• 📐 ILLUSTRATIVE ASSUMPTION — a round number this course adopts for pedagogical clarity; your real workload may differ 2-3× either way
• ⚙️ WORKLOAD-DEPENDENT ESTIMATE — heavily dependent on your specific request shape; the number is the URL Shortener workload's typical value
• 🧮 DERIVED CALCULATION — a number calculated mathematically from other assumptions above (not itself a documented fact — the label makes clear it inherits its accuracy from the assumptions feeding it)

Fact-vs-Assumption Teaching Framework

Before we teach any capacity number, agree on categories. When you leave this course, you should be able to look at any system-design claim and immediately classify it:

Real senior engineers earn trust by knowing which category any given number belongs in. When someone says "MySQL supports 25K QPS," a senior engineer asks: on what hardware, for what schema, with what buffer pool, on what row size — and if the answer is any of "I don't know" / "for our workload" / "trust me," the number is an assumption or an estimate, not a fact.

The Capacity Table

RPS anchor conversions

For readers who think in requests per day / month:

The 1B RPS tier is deliberately aspirational: no single real URL Shortener runs at 1 billion requests per second. We include it because at that scale, the bottleneck migrates from your servers to physics (speed of light, packet-loss rate, TCP window scaling), and the architectural lessons for the frontier of possibility are worth teaching even if you never build there.

Why we care about provenance labels

An earlier draft of this course said "MySQL supports 25K QPS" as if it were a fact. It is not. MySQL supports 25K point-select QPS on a specific 2-vCPU box with a warm buffer pool serving 100-byte rows over gigabit networking. Change any of those variables and the number moves 2-10× either way.

Provenance labels force us to be honest. When you use this course to size a real system, look at the label:
- If it says 📗 VERIFIED DOC, cite the vendor doc and you can defend the number in a design review.
- If it says 📊 PUBLISHED BENCHMARK, the number is real but for a specific workload; validate against your workload.
- If it says 📐 ILLUSTRATIVE ASSUMPTION or ⚙️ WORKLOAD-DEPENDENT, benchmark your own service. The course number is a starting point, not a truth.

Real senior engineers earn trust by knowing the difference between what they've measured and what they've assumed.

Foundation — The Naive Prototype (~100 requests/day)

Goal

Get it working. That's it.

At this stage we are not thinking about scale, latency, redundancy, or anything else. We just need to prove the concept — that we can shorten a URL and redirect users to it.

The Architecture

The simplest possible thing:

• One Java Spring Boot server, running on a single machine
• One MySQL database, running on the same machine (or the same cloud VPC)
• No cache, no load balancer, no redundancy

[🎬 ANIMATED DIAGRAM · `phase-1-mvp-flow`] (widget ID is historical — this widget lives in the Foundation chapter despite the `phase-1-` prefix; the ID is preserved to avoid breaking any live website references.)
> Sequence diagram: a user's browser sends POST /shorten?url=https://example.com/very/long/url to Spring Boot. Spring Boot generates a short code, INSERTs into MySQL, returns {shortUrl: "sho.rt/abc1234"}. Then a second user clicks sho.rt/abc1234 — Spring Boot does SELECT long_url WHERE short_code = 'abc1234', gets the row, returns HTTP 302 redirect. Two arrows animated in sequence.

The Data Model

We start with one table:

sql
CREATE TABLE urls (
  id          BIGINT AUTO_INCREMENT PRIMARY KEY,
  short_code  VARCHAR(10)  NOT NULL,
  long_url    VARCHAR(2048) NOT NULL,
  created_at  DATETIME DEFAULT CURRENT_TIMESTAMP
);
CREATE UNIQUE INDEX idx_short_code ON urls (short_code);

Why the choices:

• `BIGINT` id — even at massive scale we won't exhaust it. INT runs out at 2 billion; we plan for more.
• `VARCHAR(10)` short_code — 7-character codes today, room for the future 8-character migration (Phase 3+) without a schema change.
• `VARCHAR(2048)` long_url — browsers historically capped URLs around 2000 characters; 2048 is a safe upper bound.
• `UNIQUE INDEX idx_short_code` — uniqueness enforced by the named index, not a column-level UNIQUE constraint. We pick one mechanism and use it consistently. A named index is easier to reference in ALTER, DROP INDEX, index-hint syntax, and EXPLAIN output than an anonymous column constraint. (Earlier drafts declared both NOT NULL UNIQUE on the column and the named index — that duplicated the enforcement mechanism, added no safety, and made EXPLAIN harder to read. Fixed.)
• `created_at` — gives us debuggability now, becomes important for expiry later.

The Algorithm — The Naive Approach

For the first version, when a user submits a long URL, we hash it and use the first 7 characters as the short code:

java
@Service
public class ShortenerService {

    private final UrlRepository repo;

    public String shorten(String longUrl) {
        // MD5 here is a demonstration of a naive hashing approach — NOT a security primitive.
        // MD5 is cryptographically broken; never use it for authentication, signatures, or
        // any integrity-critical use case. The point of this section is to *fail* — see below.
        // Explicit UTF-8 encoding: never rely on the platform default charset for hash inputs;
        // the same string can produce different bytes on different JVMs otherwise.
        String code = DigestUtils.md5DigestAsHex(longUrl.getBytes(StandardCharsets.UTF_8))
                                 .substring(0, 7);

        while (repo.existsByShortCode(code)) {
            String salted = longUrl + System.nanoTime();
            code = DigestUtils.md5DigestAsHex(salted.getBytes(StandardCharsets.UTF_8))
                              .substring(0, 7);
        }

        repo.save(new UrlEntity(code, longUrl));
        return code;
    }
}

The redirect path is even simpler:

java
@RestController
public class RedirectController {

    private final UrlRepository repo;

    @GetMapping("/{shortCode}")
    public ResponseEntity<Void> redirect(@PathVariable String shortCode) {
        return repo.findByShortCode(shortCode)
            .map(url -> ResponseEntity.status(302)
                                      .header("Cache-Control", "public, max-age=60")
                                      .location(URI.create(url.getLongUrl()))
                                      .build())
            .orElseGet(() -> ResponseEntity.notFound().build());
    }
}

Two details in this controller are load-bearing: the 302 status code and the Cache-Control header. Neither is arbitrary. Both matter far more once we introduce a CDN in Phase 4.

301 vs 302 vs 307 — the redirect status code matters

HTTP defines three redirect codes we care about:

• `301 Moved Permanently` — semantically indicates a permanent redirect; may be cached by browsers and intermediaries for long periods depending on cache directives and client behavior (per RFC 9111). Aggressive local caching can reduce origin-visible click volume, though the magnitude depends on browser mix and cache-directive interaction. Analytics for this course come from CDN edge logs (Model 2), not from origin-visible redirect requests — so the choice of 301 vs 302 primarily affects browser-side cache behavior, not the analytics pipeline.
• `302 Found` — a temporary redirect. Actual cache behavior depends on explicit response directives and intermediary/browser behavior. When paired with Cache-Control: public, max-age=60, CDN edge PoPs may cache briefly while long-term caching is limited. In practice, more origin-visible clicks are retained under 302 + short max-age than under 301 responses that lack explicit cache directives — but the exact magnitude depends on the browser/proxy mix in your traffic.
• `307 Temporary Redirect` — semantically identical to 302 for our purposes, but preserves the HTTP method across the redirect (a POST stays a POST). Not needed for URL Shortener (redirects always come from GET clicks), but worth knowing about.

We pick `302`. This is an architectural choice for this course, driven by the fact that URL Shorteners typically want origin-visible click events for analytics. The interaction between redirect status codes, browser caches, and CDN caches is nuanced — the RFC 9111 HTTP caching semantics determine actual behavior. Rather than universalize, we note the observed pattern: services that rely on precise per-click server-side telemetry typically choose 302 because 301 responses that lack explicit Cache-Control: no-store or short max-age are cached aggressively by many browsers, reducing origin visibility (magnitude of reduction is workload- and browser-mix-dependent — do not assume a universal 5-10× effect without measuring your own traffic).

Cache-Control — why we control CDN cache separately from browser cache

Now the second load-bearing detail. Cache-Control: public, max-age=60 tells intermediaries (CDN edge, corporate proxies) they may cache the response for 60 seconds. Browsers respect it too. Note what this header is and is not: it bounds how long a redirect response may remain cached — it is not an analytics mechanism. Analytics in this course come from the canonical CDN edge-log pipeline (Model 2), not from counting origin-visible redirect requests, so cache lifetime and analytics completeness are decoupled concerns.

Why does this matter? Because in Phase 4 we put CloudFront (or Cloudflare) in front of everything. Without an explicit Cache-Control:
- CloudFront's default for 302 responses is to not cache them at all → every click hits your origin → your 70% cache-hit-rate assumption evaporates
- Even worse, some CDNs default to caching for a very long time → same analytics-loss problem as 301

Explicit max-age=60 says: CDN, please cache the redirect at your edge PoP for 60 seconds. That's enough to absorb hot-URL bursts, short enough that browsers keep hitting our origin, and short enough that URL changes take effect quickly.

We add the header from Phase 1 not because we need CDN caching yet, but because the correct default is cheap to set now and expensive to retrofit later. Every reverse proxy, gateway, and cache in your future path will honor it.

At 100 requests per day (about 1 request every 15 minutes), this works flawlessly.

Capacity & Sizing at Foundation

Let us actually count. This is the discipline every phase will apply.

Traffic:
- 100 requests / day = 0.001 RPS average, ~0.01 RPS peak

App tier — Java Spring Boot on EC2 m5.large (2 vCPU, 8 GB RAM):
- Ceiling per box: ~1,200 RPS at 70% CPU (Tomcat parse + Jackson + JDBC + Spring dispatcher, ~800 μs per request — see the ceiling derivation section for the math)
- Load: 0.001 / 1,200 = ~0.0001% utilization
- Boxes needed: 1
- Why m5.large for the illustrative baseline? This is a course instance-selection decision — m5.large provides a predictable CPU without burst-credit behavior, which keeps the benchmark model simple and comparable across phases. Smaller EC2 families (like t3) can be more cost-efficient for small services if you understand their burst semantics; we choose m5.large here to teach the capacity-math discipline against a stable per-box RPS reference.

Database — MySQL on RDS db.m6i.large (2 vCPU, 8 GB RAM):
- Ceiling per box (reads): ~20,000-25,000 read QPS at 70% CPU
- Ceiling per box (writes): ~5,000-10,000 write QPS
- Load: essentially zero
- Boxes needed: 1 (no replica yet — single point of failure by design at this scale)

Load Balancer: none. DNS points directly at the EC2 instance. Adding a load balancer with one box is pure overhead.

Cache: none. There is nothing to cache at 1 request per 15 minutes.

Cost estimate: ~$130 / month (1 × m5.large + 1 × db.m6i.large + 30 GB storage).

[🔗 REFERENCE WIDGET · `SystemSizingDiagram`]
> The reader can move the RPS slider to see how the current architecture responds. At 100 req/day, the widget shows all components green and unused. Every component has an expand/collapse panel with its ceiling math visible.

When to Evolve — the Trigger to Phase 1 (10K RPS)

Do not evolve on aesthetics. Evolve on measurable pain. From the Foundation baseline, the trigger to move to Phase 1 is:

• Metric: collision retry rate on new URL creation (a counter incremented every time you enter the while loop and re-hash)
• Threshold: a business decision — some services accept 1% retry rate for weeks, others fix it at 0.01% because the write-latency variance is user-visible. Choose based on your SLO for URL-creation latency.
• What actually happens: truncated hashing creates probabilistic collisions whose frequency grows with the number of existing URLs. There is no clean mathematical boundary; every collision requires an extra database round-trip, which makes write latency unbounded — the tail latency of your URL-creation endpoint becomes a function of how "unlucky" a specific request is.
• How to measure: add a counter shortener.collisions.rehash incremented every time you enter the while loop. Alert when the 1-minute rolling average exceeds your chosen threshold.

The honest teaching message: truncated hashing is a solved problem, not a scale problem. When deterministic write latency and guaranteed uniqueness become more valuable than the simplicity of probabilistic hashing, replace truncated hashing with database-generated IDs + Base62. That's the trigger — not a magic URL count.

If your collision rate is still 0.0001% at 100,000 URLs, congratulations, your naive algorithm is holding — but you are living on borrowed time. Move to Phase 1 preemptively.

Note: Phase 1's trigger is not a scale trigger — it is a code-quality trigger. You will hit collisions at 10,000 URLs whether you receive 100 or 10,000 RPS. Phase 1's Base62 upgrade is an algorithm improvement that happens to be table stakes for any real load.

The Breaking Point — Collisions and Round-Trips

Your service catches on with a small community. You now have 10,000 links stored. Suddenly things get slow — but not because of hardware limits.

MD5 truncated to 7 characters produces collisions.

Two entirely different long URLs can hash to the same first 7 characters. When this happens, your code does a database lookup to check for collision, sees it exists, then re-hashes, then does another lookup. Now imagine three, four, five colliding URLs in a row. Every INSERT becomes 3-5 database round-trips.

Worse: MD5 gives no upper bound. You could try 100 hashes before finding a free code. Your system becomes non-deterministic — same input, different latency depending on what's in the database.

Even worse: you have to check the database on every write, coupling writes tightly to database performance before we've done anything interesting.

We need a fundamentally different approach.

What you now understand

• Why single-machine architectures are fine at low traffic
• Why hashing with truncation is a mathematical dead end
• Why database round-trips per write compound into user-visible latency

Phase 1 — 10K RPS: Foundation Upgrade with Base62 Encoding

Goal

Eliminate the possibility of collisions, permanently.

The Insight

If every URL row has a unique integer ID (which MySQL's AUTO_INCREMENT gives us for free), then converting that integer to a base-62 string produces a mathematically unique short code. Zero collisions. Zero retry loops. Zero pre-write database round-trips.

What is Base62?

Positional number systems use a set of "digits":

• Base 10 uses 0-9. The number 100 in base 10 = one hundred.
• Base 62 uses 0-9, a-z, A-Z. The number 100 in base 62 = a very different number.

Why 62? Because URLs are case-sensitive — we can use uppercase and lowercase as distinct characters. And the entire alphabet is URL-safe: no percent-encoding, no special characters.

[🎬 ANIMATED DIAGRAM · `base62-conversion`]
> Number 10000 on the left, animated repeated division: 10000 ÷ 62 = 161 rem 18 → 'i', 161 ÷ 62 = 2 rem 37 → 'B', 2 ÷ 62 = 0 rem 2 → '2'. Remainders assembled bottom-up: 2Bi. Then reverse the animation with the reader providing a code and the widget decoding it back to a number.

The Java Implementation

java
public final class Base62 {

    private static final String ALPHABET =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int BASE = ALPHABET.length(); // 62

    // Precomputed inverse for O(1) decode lookup.
    private static final int[] INVERSE = new int[128];
    static {
        java.util.Arrays.fill(INVERSE, -1);
        for (int i = 0; i < ALPHABET.length(); i++) {
            INVERSE[ALPHABET.charAt(i)] = i;
        }
    }

    private Base62() {}

    /**
     * Encode a non-negative long into Base62.
     * Rejects negative input (IDs must be non-negative).
     * Zero encodes to "0" as a special case (no leading-zero digit otherwise).
     */
    public static String encode(long id) {
        if (id < 0) {
            throw new IllegalArgumentException("Base62.encode requires non-negative id, got " + id);
        }
        if (id == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.append(ALPHABET.charAt((int) (id % BASE)));
            id /= BASE;
        }
        return sb.reverse().toString();
    }

    /**
     * Decode a Base62 string to a long.
     * Rejects null, empty, invalid characters, and overflow.
     * Overflow protection: 62^11 exceeds Long.MAX_VALUE, so any input longer than 11 chars,
     * or one that overflows during accumulation, throws rather than silently wrapping.
     */
    public static long decode(String code) {
        if (code == null || code.isEmpty()) {
            throw new IllegalArgumentException("Base62.decode requires non-empty code");
        }
        if (code.length() > 11) {
            throw new IllegalArgumentException("Base62.decode input too long (max 11 chars): " + code);
        }
        long result = 0;
        for (int i = 0; i < code.length(); i++) {
            char c = code.charAt(i);
            int digit = (c < 128) ? INVERSE[c] : -1;
            if (digit < 0) {
                throw new IllegalArgumentException("Base62.decode invalid character '" + c + "' at index " + i);
            }
            // Overflow-safe multiply-then-add.
            if (result > (Long.MAX_VALUE - digit) / BASE) {
                throw new ArithmeticException("Base62.decode overflow for input: " + code);
            }
            result = result * BASE + digit;
        }
        return result;
    }
}

Notes on the hardening (this is production-grade behavior worth teaching, not incidental defensiveness):

• Rejects negative input. IDs are non-negative by contract. Silently encoding -1 as "" or a nonsense string is a lurking bug.
• Rejects invalid decode characters. Naïve ALPHABET.indexOf(c) returns -1 for unknown chars, which then quietly subtracts from the accumulator. The hardened version throws.
• Rejects decode overflow. 62¹¹ exceeds Long.MAX_VALUE. A malicious or buggy client sending a 20-char code would silently wrap into a small number and hit the wrong row. The hardened version throws.
• O(1) decode lookup table. String.indexOf is O(alphabet size); a precomputed int[128] inverse is one array access per character. At hundreds of thousands of decodes/sec on the origin, this matters.

The Shortener Service Becomes

The naive approach would be to INSERT a row with short_code = null, read back the auto-generated id, encode it, then UPDATE. That does not work — the Phase 1 schema declared short_code VARCHAR(10) NOT NULL (uniqueness enforced by the named idx_short_code index), so the first INSERT trips a NOT NULL constraint violation before we can get the ID back.

We need to allocate the ID before the row is inserted. Two clean options:

Option A — Dedicated ticket-sequence table (the "Flickr ticket server" pattern). A tiny secondary table exists solely to mint unique IDs via AUTO_INCREMENT. We generate the ID first, then INSERT the full row.

sql
CREATE TABLE url_ticket_seq (
    id   BIGINT AUTO_INCREMENT PRIMARY KEY,
    stub CHAR(1) NOT NULL UNIQUE
) ENGINE=InnoDB;

INSERT INTO url_ticket_seq (stub) VALUES ('a');

java
@Service
public class TicketSequence {
    private final JdbcTemplate jdbc;

    public long nextId() {
        // CRITICAL: MySQL's LAST_INSERT_ID() is session-scoped (per-connection).
        // Two separate JdbcTemplate calls do NOT guarantee reuse of the same
        // physical JDBC connection from the pool — the REPLACE may run on
        // connection A while the SELECT LAST_INSERT_ID() lands on connection B,
        // returning a stale/incorrect value under concurrency. We use a
        // ConnectionCallback so both statements are guaranteed to execute
        // on the same connection.
        return jdbc.execute((ConnectionCallback<Long>) conn -> {
            try (Statement st = conn.createStatement()) {
                st.executeUpdate("REPLACE INTO url_ticket_seq (stub) VALUES ('a')");
                try (ResultSet rs = st.executeQuery("SELECT LAST_INSERT_ID()")) {
                    rs.next();
                    return rs.getLong(1);
                }
            }
        });
    }
}

@Service
public class ShortenerService {
    private final TicketSequence tickets;
    private final UrlRepository  repo;

    public String shorten(String longUrl) {
        long   id   = tickets.nextId();
        String code = Base62.encode(id);
        repo.save(new UrlEntity(id, code, longUrl));
        return code;
    }
}

Why this connection-safety detail matters. LAST_INSERT_ID() in MySQL is session-scoped — its value lives on the specific JDBC connection that executed the INSERT/REPLACE. If you naïvely call jdbc.update("REPLACE INTO …") followed by jdbc.queryForObject("SELECT LAST_INSERT_ID()", …), Spring's JdbcTemplate acquires and releases a connection per call — meaning the SELECT may run on a different pooled connection and return either 0 or an ID minted by an entirely different request. Under concurrency this produces silent duplicate IDs and wrong-URL mappings.

ConnectionCallback (shown above) forces both statements onto the same physical connection. Alternatives that achieve the same guarantee: wrap the calls in a TransactionTemplate block (which pins the connection for the transaction's duration), or use INSERT ... RETURNING where supported. The teaching pattern remains the same as INSERT + LAST_INSERT_ID: allocate a sequence value and retrieve it in one atomic connection-pinned operation.

REPLACE INTO on a 1-row table (keyed on the stub column) atomically replaces the row and bumps AUTO_INCREMENT. LAST_INSERT_ID() on the same connection returns the fresh ID. No collision check, no null insert, no two-phase write.

Option B — Nullable column + immediate UPDATE inside a transaction. Change short_code to NULLABLE, then in the same transaction: INSERT (with short_code = NULL), read LAST_INSERT_ID(), compute Base62(id), UPDATE the row to set short_code = <computed>. The uniqueness constraint on short_code is preserved as a regular UNIQUE index (MySQL treats multiple NULLs as distinct in a UNIQUE index, so momentarily-null rows do not conflict; MySQL does NOT have SQL Server-style filtered/partial unique indexes). Simpler than Option A but leaks null-short_code rows if a crash happens between INSERT and UPDATE — requires a garbage-collect job.

Recommended: Option A. The Flickr ticket-server pattern originated at Flickr precisely for this reason — it decouples ID generation from row insertion, gives you a durable monotonic counter, and lets you migrate to a distributed ID generator (KGS in Phase 4) without touching your urls table.

The Address Space

With 7 characters of Base62, we have 62^7 = 3,521,614,606,208 unique short codes — ~3.52 trillion. That sounds like a lot. But namespace lifetime is a function of your URL creation rate, not of your redirect RPS — the same independent-workload-variable lesson you already know from the read/write ratio, applied to the address space itself.

Namespace lifetime at this course's canonical write workloads (🧮 DERIVED CALCULATION):

7-character Base62 is fine for teaching Foundation and the early phases, but the canonical production KGS code length from Phase 3 onward is 8 characters. 62^8 = 218,340,105,584,896 (~218T). At 100,000/sec that is 🧮 ~69 years; at 30,000/sec, ~230 years. Eight characters buys enough runway that namespace exhaustion becomes a non-concern for the service's practical lifetime.

We keep `VARCHAR(10)` in the schema — that already provided the migration room. We use 7-char examples in Foundation, Phase 1, and Phase 2 where they aid teaching Base62 mechanics without adding character-length noise. From Phase 3 onward the canonical production code length is 8. The migration between them is designed below, not just asserted as a constant change.

Mixed 7/8-character namespace — the migration design:

• Invariant preserved: you never rewrite an issued short code. All 7-character codes ever issued must resolve forever.
• Route pattern: update from /{code:[0-9A-Za-z]{7}} to /{code:[0-9A-Za-z]{7,8}} — both lengths route to the same handler.
• KGS cutover strategy (chosen): at cutover, the KGS counter starts issuing IDs above 62⁷ = 3.52T. From that point forward, Base62.encode(id) produces 8-character output naturally (variable-length encoding, no zero-padding). Rejected alternative: zero-padding the encoder to always output 8 characters — cleaner-looking but rewrites the meaning of every previously-issued 7-character code. We keep encoding stable and let the length boundary follow from the ID range.
• Vitess hash vindex: input is short_code (string), not the underlying integer ID. The hash function works identically on 7- and 8-character inputs — this migration is transparent to sharding.
• Edge KV key format: the KV key is the code string itself, unchanged.
• Permanently-leaked IDs (from KGS Redis loss): each loss leaks ~10M codes. Against 218T space, negligible; do not reclaim.

At 8 characters, we really don't run out — but the runway is bought by the migration above, not by wishful thinking.

[🎬 ANIMATED DIAGRAM · `namespace-lifetime`] — Sliders for code length (6–10 chars) and URL creation rate (per second); shows address space and years-to-exhaustion live.

The Trade-offs of Base62

Positive:

• Zero collisions, mathematically guaranteed
• No pre-write database lookup
• Deterministic write latency
• URL-safe characters

Negative:

• Codes are sequential (aaaa2 → aaaa3 → aaaa4), which is enumeration-friendly. An attacker can guess adjacent codes to discover URLs that were meant to stay private.
• Requires AUTO_INCREMENT to work — which is a per-database sequence. When we shard MySQL later, this becomes a bigger problem.

We will fix both of these in Phase 3 with the Key Generation Service.

Capacity & Sizing at Phase 1 (10K RPS)

Base62 is the algorithm-level fix. Now let us size the infrastructure for the first real traffic tier — 10,000 requests per second sustained.

Traffic:
- 10,000 RPS average = ~864 million redirects / day = ~26 billion / month
- Peak assumption: 20,000 RPS (2× typical burst multiplier for a well-loved service)
- Read/write split: URL Shortener redirects dominate — assume 99% reads (9,900 RPS), 1% writes (100 RPS) at 10K RPS baseline

App tier — Java Spring Boot m5.large (⚙️ WORKLOAD-DEPENDENT — ~1,200 RPS/box):

Three separate capacity questions to answer, in order:

1. Steady-state throughput: 10,000 / 1,200 = 8.4 boxes
2. Peak throughput: 20,000 / 1,200 = 16.7 boxes
3. Peak throughput SURVIVING a single-AZ failure: if the fleet is spread across 3 AZs and one AZ dies, the surviving 2 AZs (2/3 of the fleet) must still handle peak traffic. So the total fleet must be 1.5× the peak-throughput number = 16.7 × 1.5 = 25 boxes.

Rounding for 3-AZ balance: 27 boxes total (9 per AZ).

• If one AZ fails: 18 boxes × 1,200 RPS/box = 21,600 RPS capacity — comfortably serves 20K peak
• If both AZs are healthy (steady state): 27 × 1,200 = 32,400 RPS capacity → 10,000 / 32,400 = 31% utilization (comfortable, but honest — you are paying for meaningful failure-headroom slack)

An earlier draft of this course used "18 boxes" without doing the AZ-failure math. With 18 boxes across 3 AZs = 6 per AZ, one AZ death leaves 12 boxes × 1,200 = 14,400 RPS capacity — cannot serve 20K peak. That earlier claim was wrong; the correct answer for surviving 1-AZ loss at peak burst is 27 boxes. Being honest about failure math matters more than looking economical on paper.

MySQL primary — RDS db.m6i.large (📊 PUBLISHED BENCHMARK):
- Read load: 9,900 RPS × 100% (no cache yet) = 9,900 read QPS — 40% of 25,000 QPS ceiling
- Write load: 100 RPS = 100 write QPS — 1% of 10,000 QPS ceiling
- Single primary handles it. No cache required at this tier yet. This is the pedagogically important observation — Phase 1 skips introducing Redis.
- HA requirement: 1 primary + 1 Multi-AZ synchronous standby (same box, different AZ). Failover completes in ~60 seconds.

Redis: not deployed at Phase 1. This is deliberate. MySQL absorbs the read load comfortably at 10K RPS, and adding Redis introduces a cache-consistency concern that isn't paying for itself yet. Redis becomes essential at Phase 2 (100K RPS).

Custom Aliases and Vanity URLs (Phase 1 anchor)

Now that Base62 is in place, we have to answer a real product question that will shape every future scale level: what if a user wants to pick their own short code?

Vanity aliases (bit.ly/my-launch) break several invariants of the KGS-Base62 pipeline in ways worth designing for now, at Phase 1, before we've built the harder infrastructure that will inherit these decisions:

• The KGS mints sequential numeric IDs; a user-chosen alias is not drawn from the KGS pool but shares the same urls.short_code column and the same UNIQUE index.
• User-chosen aliases must be checked against the entire existing namespace before minting.
• A reserved-word list (admin, api, login, settings, plus a maintained list of trademark/abuse terms) must be enforced at the API validation layer, not at the DB.
• Minimum length ≥ 4 chars so users don't squat inside the machine-generated 7-8-char namespace; maximum length 20.
• Character set stays [A-Za-z0-9_-] (same as machine codes plus - and _ for readability).
• Rate-limit custom-alias creates at ~10× the normal API rate because they force uniqueness checks and burn dictionary-word namespace.

The collision-check path at mint time is:

```
1. Validate alias format (regex + reserved-word set).
2. Redis SET NX EX <ttl> on key alias:reserved:{alias} with 30s TTL
→ if fails, return 409 CONFLICT immediately (someone else is minting the same alias right now).
3. Query MySQL by short_code = alias (indexed point lookup; at Phase 3+ this becomes a Vitess hash-vindex lookup).
→ if row exists, release reservation, return 409 CONFLICT.
4. INSERT into urls with short_code = alias, status = ACTIVE.
5. (Phase 4) Propagate to edge KV.
6. Return 201.
```

See CC-2 in the Cross-Cutting Architecture Concerns section for the full canonical reference, including the namespace-interaction discussion and the `custom-alias-collision` widget spec.

Load Balancer — AWS ALB (see "LCU is a Billing Dimension, Not a Hard Ceiling" section for the correct model):
- Modeled LCU consumption at 10K RPS: ~2 LCU (⚙️ WORKLOAD ASSUMPTION for URL Shortener request profile)
- 1 ALB, no capacity concern — LB cost is trivial compared to app-tier cost
- Deploy across 3 AZs (AWS handles this automatically) for durability

Order of magnitude: ~$0.107 per million redirects (🧮 $2,765/mo ÷ ~25.9B redirects/mo at 30-day month × 10K RPS; 📐 ILLUSTRATIVE — derived from this course's illustrative monthly cost, not a production budget). Higher per-redirect cost than earlier drafts because we correctly account for AZ-failure headroom at peak burst — this is the honest number, not an economy-optimized fantasy.

[🔗 REFERENCE WIDGET · `SystemSizingDiagram`]
> Move the slider to 10K RPS. Reader sees: 27 green app boxes (9 per AZ), 1 MySQL primary + 1 sync standby, 1 ALB, no Redis. Toggle "simulate 1 AZ failure" to see 9 boxes go red, 18 remaining × 1,200 = 21,600 RPS (still serves 20K peak). Toggle "add Redis anyway" to see MySQL relief that isn't needed at this scale.

[🔗 REFERENCE WIDGET · `ComponentCeilingsPanel`]
> RPS slider from 100 to 100K. At 10K RPS the reader sees which component is closest to its ceiling (MySQL primary at 40% is the answer — and that's why Phase 2's trigger is MySQL saturation). Hover on any component to see the derivation.

When to Evolve — the Trigger to Phase 2 (100K RPS)

• Metric 1 (throughput): MySQL primary read QPS
• Threshold: sustained > 15,000 read QPS (60% of the 25,000 QPS ceiling) — the point where you have ~4 months of runway before you saturate
• Metric 2 (latency): p50 read latency
• Threshold: > 20 ms — the point where the InnoDB buffer pool starts thrashing on cold data
• Metric 3 (cost signal): you are running MySQL at the largest single-instance size that still fits your budget

At Phase 1, MySQL is doing all the work. It handles 9,900 read QPS at 40% utilization. As traffic grows to 15,000 RPS, MySQL read QPS climbs to ~15,000 — 60% util, ~2 months from saturation.

That is when you introduce Redis. Not before. The pedagogy is clear: wait for the measured pain, then apply the smallest fix.

Watch the read-path latency curve. It stays flat under buffer-pool-friendly loads, then knees upward sharply once the working set outgrows RAM. That knee is your Phase 2 trigger.

Decision Snapshot at 10K RPS

📊 Your dashboard shows (6 weeks after launch):
- App tier CPU: 46% steady, 62% peak burst
- MySQL primary CPU: 40% steady, 55% during peak
- MySQL primary read QPS: 9,900 average, 14,500 peak
- MySQL primary write QPS: 100 average
- ALB LCU utilization: 8%
- p50 redirect latency: 12 ms
- p99 redirect latency: 45 ms
- Availability last 30 days: 99.98%

❓ Everything is green. Do you take action?

_{Answer + rationale below.}

✅ Answer: yes — but not the action a junior engineer expects. Do NOT add Redis, do NOT add read replicas, do NOT scale up. The answer is to project forward. At current growth rate (say 30% MoM), MySQL read QPS will hit 15K (60% util) in ~2 months and 25K (100% util) in ~3.5 months. Start planning the cache introduction now — order Redis cluster capacity, write the cache-aside code, plan the deployment. Ship it 4-6 weeks before you need it. If you wait until MySQL is at 90% CPU to introduce cache, you are already firefighting.

Senior insight: the moment to add complexity is when you can measure it will be needed 6-12 weeks out — not when you feel it. The moment to remove complexity is when you can measure it isn't needed. Reactive engineering is exhausting; predictive engineering is calm.

The Breaking Point — Read Latency Saturates MySQL at 100K RPS

Traffic grows 10×. Suddenly you are serving 100,000 RPS. Do the math:

• Reads: 99,000 QPS
• MySQL primary ceiling: ~25,000 read QPS
• Ratio: 99,000 / 25,000 = 4× — MySQL is 4× over its ceiling

More concerning: we're paying for a full round-trip and B-tree traversal on every redirect, when we could be serving them from RAM in microseconds.

The next architectural change is inevitable: introduce a cache.

What you now understand

• Why AUTO_INCREMENT is a clean source of uniqueness
• How positional number systems work at a mathematical level
• Why solving collisions once is worth the effort of a new algorithm
• Why sequential codes create a security concern for private URLs

Phase 2 — 100K RPS: The Latency Fix with Redis Cache

Goal

Bring median redirect latency below 10 milliseconds. Preferably below 5.

The Cache-Aside Pattern

We introduce Redis between our application and MySQL. Redis is an in-memory data store — a lookup is a hash-table probe, typically 3-4 microseconds inside a single machine, ~1ms including network hop.

The pattern:

• On read: check Redis first. If hit, return. If miss, read MySQL, write result to Redis with a TTL, return.
• On write: write to MySQL, then either invalidate Redis or populate it.

[🎬 ANIMATED DIAGRAM · `phase-2-cache-aside-flow`]
> Two side-by-side panels: (a) cache HIT — User → Spring Boot → Redis GET abc1234 → return. Timeline shows ~3ms. (b) cache MISS — User → Spring Boot → Redis GET abc1234 (nil) → MySQL SELECT → Redis SETEX abc1234 3600 https://… → return. Timeline shows ~12ms. A counter at the top of the widget shows a running 95% HIT / 5% MISS ratio and the weighted average latency.

The Java Implementation

java
@Service
public class UrlLookupService {

    private final JedisPool jedisPool;
    private final UrlRepository repo;
    private static final int TTL_SECONDS = 3600;

    public Optional<String> lookup(String shortCode) {
        try (Jedis jedis = jedisPool.getResource()) {

            String cached = jedis.get(shortCode);
            if (cached != null) return Optional.of(cached);

            Optional<UrlEntity> fromDb = repo.findByShortCode(shortCode);
            if (fromDb.isEmpty()) return Optional.empty();

            String longUrl = fromDb.get().getLongUrl();
            jedis.setex(shortCode, TTL_SECONDS, longUrl);
            return Optional.of(longUrl);
        }
    }
}

Why TTL, Not Forever?

Two reasons:

1. Memory reclaim. If a short code is created but never clicked, we do not want to keep it in Redis forever taking up space. TTL evicts cold entries automatically.
2. Consistency safety. If the long URL is ever updated (rare but possible), the cache will eventually reflect the new value even without an explicit invalidation.

The Cache Hit Rate at Scale

With uniform-distribution traffic across 100,000 short codes, the cache hit rate can be low — most requests are for "cold" URLs.

But URL Shortener traffic follows a power law: a small percentage of URLs receive the vast majority of clicks. In practice, 90-95% of requests hit fewer than 5% of URLs.

This means with a moderately-sized Redis (a few gigabytes), we can serve 90%+ of requests entirely from cache. MySQL now sees 10× less read traffic.

The New Latency Profile

• Cache HIT (95% of requests): ~3ms
• Cache MISS (5% of requests): ~12ms
• Weighted average: ~3.5ms

We hit our latency goal.

The Cache Stampede Problem

There is one subtle failure mode. Suppose a viral link's cache entry expires exactly at the moment the link is being clicked 500 times per second. All 500 requests miss the cache simultaneously, all 500 hammer MySQL to fetch the same row, and MySQL briefly falls over.

The fix is single-flight — only one request per short code fetches from MySQL; the others wait for its result. We add this to the lookup service:

java
private final ConcurrentHashMap<String, CompletableFuture<String>> inFlight
    = new ConcurrentHashMap<>();

private final ExecutorService dbExecutor;  // bounded pool, e.g. Executors.newFixedThreadPool(32)

private static final Duration UPSTREAM_TIMEOUT = Duration.ofMillis(500);

public Optional<String> lookup(String shortCode) {
    try (Jedis jedis = jedisPool.getResource()) {
        String cached = jedis.get(shortCode);
        if (cached != null) return Optional.of(cached);
    }

    CompletableFuture<String> future = inFlight.computeIfAbsent(shortCode, code ->
        CompletableFuture.supplyAsync(() -> {
            Optional<UrlEntity> fromDb = repo.findByShortCode(code);
            if (fromDb.isEmpty()) return null;

            String longUrl = fromDb.get().getLongUrl();
            try (Jedis j = jedisPool.getResource()) {
                j.setex(code, TTL_SECONDS, longUrl);
            }
            return longUrl;
        }, dbExecutor).whenComplete((res, err) -> inFlight.remove(code))
    );

    try {
        return Optional.ofNullable(
            future.orTimeout(UPSTREAM_TIMEOUT.toMillis(), TimeUnit.MILLISECONDS).join());
    } catch (CompletionException e) {
        // Timeout or upstream failure: fail open (return empty → app returns 503)
        // rather than blocking the Tomcat worker thread indefinitely
        inFlight.remove(shortCode);
        return Optional.empty();
    }
}

Three details in this code are load-bearing and worth calling out:

Detail 1 — the DB call is offloaded via `supplyAsync(..., dbExecutor)`, not run inline. This is the most subtle bug an earlier draft of this code contained. Blocking network I/O inside `ConcurrentHashMap.computeIfAbsent()` can create serious contention — depending on the JDK version and internal hashmap implementation details, the mapping function may hold internal locks that block other threads working on unrelated keys. The safe pattern is: keep the mapping function short (just create the asynchronous computation), and perform any blocking JDBC/network work outside the mapping operation. The fix is CompletableFuture.supplyAsync(..., dbExecutor): the lambda returns a Future immediately, so the mapping function completes in microseconds. Actual DB work happens on the dbExecutor pool, which is separate from Tomcat's request-handling pool. This architectural pattern (short mapping + async offload) applies broadly whenever you use concurrent maps for coordination — treat any concurrent-collection mapping function as a hot path that should not do I/O.

Detail 2 — the `.orTimeout(500 ms)` is not optional. Without it, a slow MySQL query would block the joining Tomcat worker thread indefinitely. Tomcat has a fixed pool (default 200 workers); if 200 requests all wait on a hung .join(), the entire app instance stops serving any traffic — including cache-hit traffic that should have been fast. A 500 ms upstream timeout is enough to survive typical MySQL hiccups (Multi-AZ failover completes in ~60 s but individual queries retry in <100 ms) and cheap to serve as a 503 back to the user — many browsers retry idempotent GET requests transparently on transient failure, though this behavior is not universal and should not be relied upon as a UX guarantee.

Detail 3 — this single-flight is per-JVM, not cluster-wide. The ConcurrentHashMap lives inside one Spring Boot process. With 3 app instances behind the ALB at Phase 3, a cache-expiry stampede can still send 3 concurrent queries to MySQL for the same key (one per JVM). That is still a ~166× reduction from the 500-per-second worst case, and it is enough for Phase 3's scale (MySQL comfortably handles 3 duplicated queries).

When is per-JVM single-flight not enough? At Phase 4 (24 app instances) and beyond, cache-expiry stampedes can generate 24 concurrent queries — still well within MySQL's ceiling, but if you had 100+ boxes and a genuinely viral single key, you would need cluster-wide deduplication:

• Redis-based distributed lock. SET singleflight:{code} <worker-id> NX EX 5 — only one worker across the fleet gets the lock, the others read from cache with tight retry.
• Probabilistic early expiration (XFetch algorithm). Each worker independently and randomly decides to refresh the cache before it expires. Over the fleet, only a tiny fraction of workers refresh at any moment. Elegant; no coordination.

For Phase 2 (~90 boxes) and Phase 3 (~2,700 boxes), per-JVM single-flight is the right answer. For genuinely extreme hot-key patterns, adopt XFetch. Complexity should follow measurable pain.

Capacity & Sizing at Phase 2 (100K RPS)

Traffic has grown 10× from Phase 1. Two things change: Redis becomes mandatory (MySQL can no longer handle 99K read QPS alone) and modeled LB LCU consumption climbs significantly (still not a hard cap, but a real cost + blast-radius signal).

Traffic:
- 100,000 RPS average = ~8.64 billion redirects / day = ~260 billion / month
- Peak assumption: 200,000 RPS (2× typical burst)
- Read/write split: 99% reads (99,000 RPS), 1% writes (1,000 RPS)

App tier — Java Spring Boot m5.xlarge (⚙️ WORKLOAD-DEPENDENT — ~2,400 RPS/box for this workload):

Three separate capacity questions to answer honestly, in order:

1. Steady-state throughput: 100,000 / 2,400 = ~42 boxes
2. Peak throughput: 200,000 / 2,400 = ~84 boxes
3. Peak throughput surviving 1-AZ failure (surviving 2 AZs must handle peak): total fleet = peak × 1.5 = 84 × 1.5 = 126 boxes

Canonical Phase 2 sizing: 126 m5.xlarge boxes, 42 per AZ across 3 AZs.

Verify: after one AZ fails, surviving 2 AZs = 84 boxes × 2,400 RPS/box = 201,600 RPS capacity — comfortably handles the 200K peak with tiny headroom.

• Steady-state utilization: 100,000 / (126 × 2,400) = 33% — honest headroom because we correctly account for AZ-failure survivability at peak burst
• Pedagogical alternative (do NOT use as canonical): 180 × m5.large at ~1,200 RPS/box would give same steady-state throughput headroom but with 2× the box count and 2× the operational overhead. m5.xlarge is the right pick above ~30K RPS.

Redis — cache.r6i.large (⚙️ WORKLOAD-DEPENDENT, published redis.io benchmarks suggest ~100-150K ops/sec for simple workloads, actual production numbers should be measured):
- With 90% cache hit rate (⚙️ workload assumption): 99,000 read RPS × 90% = 89,100 GET/sec + 9,900 SETEX/sec = ~99,000 ops/sec
- At the assumed ~100K ops/sec per node ceiling, single r6i.large is right at the edge. Redis becomes the next bottleneck — this is the pedagogically important observation: fixing one bottleneck (MySQL) moves the pressure to the next (Redis).
- Decision: shard to Redis Cluster with 3 nodes (each carries ~33K ops/sec = comfortable). Redis Cluster is also the right on-ramp to Phase 3+ where multi-shard cache becomes mandatory. The Cluster operational model is worth learning at this tier.

MySQL primary — db.m6i.large:
- Read load: 99,000 RPS × 10% cache miss = 9,900 read QPS — 40% of the ⚙️ workload-dependent ~25,000 QPS reference
- Write load: 1,000 RPS = 1,000 write QPS — 10% of the ⚙️ ~10,000 QPS reference
- Single primary handles it comfortably. This is why Redis was mandatory — without it, MySQL would face 99,000 read QPS (4× the reference), an unacceptable multiplier even given ⚙️ workload uncertainty.
- HA: 1 primary + 1 read replica (Multi-AZ). The replica is available for reads too if we chose, but keeping it as HA-only reduces replication lag concerns.

Load Balancer — AWS ALB (see "LCU is a Billing Dimension, Not a Hard Ceiling" section for the correct model):
- Modeled LCU consumption at 100K RPS: ~20 LCU per ALB (⚙️ WORKLOAD ASSUMPTION for URL Shortener request profile)
- Not a hard capacity limit. LCU is a billing dimension. AWS's per-region default quota is 50 ALBs per region (📗 verified, adjustable via Service Quotas console).
- Design decision: DNS-weighted routing to 2 ALBs for blast-radius reduction. Each carries ~10 LCU consumption modeled. Real per-ALB throughput at this workload should be validated with load testing, not derived from LCU math.

Order of magnitude: ~$0.046 per million redirects (🧮 $12,000/mo ÷ ~259B redirects/mo at 30-day month × 100K RPS; 📐 ILLUSTRATIVE) — 2.3× more efficient per redirect than at 10K RPS. Economies of scale kicking in.

[🔗 REFERENCE WIDGET · `SystemSizingDiagram`]
> Move the slider to 100K RPS. Reader sees 126 green app boxes (42 per AZ across 3 AZs), MySQL primary + replica, 3-node Redis Cluster, 2 ALBs. Toggle "simulate 1 AZ failure" to see 42 boxes go red; 84 surviving × 2,400 = 201,600 RPS still handles the 200K peak. Toggle "disable Redis" to see MySQL flip red at 99K QPS (4× over reference ceiling — dramatic visual).

[🔗 REFERENCE WIDGET · `ComponentCeilingsPanel`]
> RPS slider walks 10K → 1M. At 100K the reader sees LB approaching 80% (yellow), Redis at 99% single-node (red), MySQL at 40% (green). The widget makes clear that cache is what unlocked this tier — without Redis the entire architecture caps at ~25K RPS.

[🔗 REFERENCE WIDGET · `HotKeyLab`]
> "Your service handles 100K RPS smoothly. Now one blog post goes viral — that single URL receives 100,000 RPS by itself. What happens?" Reader picks the mitigation.

Security Architecture (Phase 2 anchor)

At 100K RPS, the mint API is now visible enough to attract abuse. Security is not a feature — it is architectural table stakes. This is where we install the security posture the rest of the course inherits.

Threat model (top 5 for Phase 2):

1. Open redirect for phishing. Attacker mints short.ly/PayPal-Login pointing at a phishing site. Mitigation: (a) URL scanning at mint time against Google Safe Browsing / VirusTotal / PhishTank; (b) delayed activation for suspicious domains; (c) after-the-fact takedown via user reports + automated abuse pipeline. Do NOT try to prevent all open redirects — the service is an open redirect. Invest in fast takedown (target: < 5 min from report to global cache invalidation).
2. SSRF via long-URL scanning. If the mint-time fetcher does a HEAD request to check reachability, it can be tricked into requesting internal IPs (http://169.254.169.254/latest/meta-data/). Mitigation: DNS resolution in a hardened resolver that rejects RFC 1918, loopback, link-local, and cloud metadata ranges. Egress from a dedicated VPC with no path to internal services.
3. Enumeration. Sequential Base62 codes let an attacker enumerate aaaaaaa, aaaaaab, ..., scraping the entire URL corpus. Mitigation: rate-limit by IP and API key on 404s.
4. Denial of wallet. Attacker generates massive request volume pointing at expensive origins to exhaust CDN egress budgets. Mitigation: per-code rate limits; alert on request rate > 100× normal for a single code.
5. API abuse / spam minting. Bot mints millions of shortlinks to flood downstream services. Mitigation: authenticated API keys for automated use; anonymous minting rate-limited to ~10/hour per IP; CAPTCHA on suspicious patterns.

TLS posture (installed here, unchanged through Phase 4): TLS 1.3 mandatory at the edge; TLS 1.2 only for legacy compat. HSTS with max-age=31536000; includeSubDomains; preload. Cert rotation via AWS ACM at the ALB. No cert lives on disk in the app tier.

WAF (canonical minimum): OWASP Core Rule Set for POST /api/v1/*; block POST /api/v1/shorten with longUrl containing javascript:, data:, vbscript: schemes; block payloads > 10KB.

HMAC secret rotation: every 90 days. Zero-downtime rotation: maintain HMAC_KEY_CURRENT and HMAC_KEY_PREVIOUS; verify against both during 90-day overlap window; mint only with CURRENT. Secrets in AWS Secrets Manager, injected at app-tier boot. Never commit HMAC keys to git; never log at DEBUG.

[🔗 REFERENCE WIDGET · `open-redirect-validator`]
> Reader pastes a candidate long URL; widget shows the mint-time validation pipeline (scheme allowlist → hardened DNS resolver → Safe Browsing check → decision). Toggle attacker payloads to observe rejection paths.

See CC-3 in the Cross-Cutting Architecture Concerns section for the full canonical reference. Phase 3 and Phase 4 add multi-region secret rotation and edge WAF respectively.

Observability — SLIs, SLOs, and Alerting (Phase 2 anchor)

At 100K RPS, you can no longer stare at a terminal. You need SLIs, SLOs, and burn-rate alerts anchored to error budget — installed here so the rest of the course can reference them.

Canonical SLIs:

Canonical SLOs (installed at Phase 2, tightened as the system matures):

• Redirect availability: 99.95% rolling 30-day (26 min downtime budget)
• Redirect P99 latency: < 200 ms globally, < 100 ms in-region (design target, not universal guarantee)
• Mint availability: 99.9% (43 min budget)
• Mint P99 latency: < 500 ms

Burn-rate alerts (multi-window, multi-burn-rate — Google SRE workbook pattern):

• Fast burn: 5% of 30-day budget in 1 hour → page immediately
• Slow burn: 10% of 30-day budget in 6 hours → ticket

Do NOT alert on "one bad request." Alert on budget consumption, not on individual errors. This is the single biggest observability lesson at scale.

[🔗 REFERENCE WIDGET · `slo-error-budget`]
> 30-day rolling burn-rate chart. Toggles inject errors ("regional outage 15min", "bad deploy 1hr elevated 5xx", "backend latency spike"). Widget shows fast-burn (page) vs slow-burn (ticket) vs within-budget states.

See CC-4 in the Cross-Cutting Architecture Concerns section for the full canonical reference including distributed tracing, log routing, and cardinality control. Phase 3 adds regional dashboards; Phase 4 addresses cardinality explosion at 1B RPS.

When to Evolve — the Trigger to Phase 3 (10M RPS)

• Metric 1 (throughput): Redis Cluster utilization
• Threshold: any single Redis Cluster shard exceeds 60% ops/sec — resharding pain is proportional to overshoot
• Metric 2 (latency): cross-region redirect latency for users outside your primary region
• Threshold: p95 latency > 200 ms for >20% of the user population
• Metric 3 (availability): single-region availability SLO
• Threshold: measured availability < 99.95% (about 22 minutes of downtime per month) — this typically hits after your first minor AZ-level incident
• Metric 4 (business): you get a paying customer in a geography where you have no infrastructure and they complain about performance

You do not evolve to Phase 3 (10M RPS) because of throughput — a single region handles 100K comfortably. You evolve because of physics (speed of light limits) and blast radius (one region = one bad afternoon from a global outage).

Decision Snapshot at 100K RPS

📊 Your dashboard shows during a Friday night:
- App tier CPU: 46%
- MySQL primary CPU: 40% (via Redis absorbing 90% of reads)
- Redis single-node CPU: 99% ⚠️
- Redis single-node network: 8.5 Gbps out of 10 Gbps ⚠️
- Cache hit rate: 90%
- ALB LCU: 80% ⚠️
- p50 redirect latency: 5 ms
- p99 redirect latency: 50 ms — up from 30 ms last week

❓ Two components are hot. Which do you fix first, and how?

_{Answer + rationale below.}

✅ Answer: Redis first, then LB. Redis at 99% single-node CPU + NIC saturation is a cliff waiting to happen — one traffic spike and you drop 10% of cache hits into MySQL, which then goes to 400% util in seconds. Solution: shard Redis into a 3-node Cluster. Each node handles 33% of ops = 33% util = comfortable. The LB at 80% LCU is warm but not urgent — split into 2 ALBs via DNS-weighted routing over the next week. Do them in that order because Redis failure would page your team; ALB throttling would only page some of your users.

Senior insight: when two components are hot, order them by blast radius on failure, not by utilization percentage. Redis at 99% has a much worse failure mode than LB at 80% — LB throttling degrades latency, Redis overload cascades into a database meltdown.

The Breaking Point — Single Region Cannot Serve the World

Your cache is fast. Your service is snappy at 100K RPS. Then traffic grows 100× — you are looking at 10M RPS incoming.

Do the math on a single-region architecture at 10M RPS:
- App tier: 10M / 1,200 = 8,300 boxes — operationally painful
- Redis: 10M × 90% hit = 9M GET/sec, needs ~30-shard Redis Cluster
- MySQL: 10M × 10% miss = 1M read QPS — 40× the single-primary ceiling; need heavy fanout
- ALB: 10M RPS = 2,000 LCU modeled consumption per region — vastly beyond any single ALB's practical throughput (regardless of the LCU billing). Multiple ALBs per region required, but the count is driven by (a) AWS ALB throughput quotas, (b) blast-radius isolation, (c) cost optimization at scale, not by a "25 LCU cap" that does not exist.
- Cross-continent latency: users in Sydney still pay ~300 ms to reach us-east-1

Physics wins. We need to distribute.

What you now understand

• Why in-memory caches beat disk lookups by 100-1000×
• How power-law traffic distributions make caching efficient
• Why cache TTL is a hedge against consistency drift
• Why cache stampedes happen and how single-flight fixes them

Phase 2.5 — 1M RPS: The Single-Region Ceiling (Do We Multi-Region Yet?)

Goal

Ask the honest question: at 1 million RPS, do we actually need to multi-region and shard yet? Or can a single well-tuned region still carry the load?

The knee-jerk answer at "1M RPS" is "obviously go global, obviously shard the database." A more careful engineer asks: let me see the numbers first.

The Architecture Under Evaluation

We stay in a single region (say us-east-1) but add CDN edge caching, and consider whether Vitess sharding is warranted yet.

[🎬 ANIMATED DIAGRAM · `phase-2-5-single-region-1m`]
> Reader sees the single-region 1M RPS canonical architecture: CDN globally distributed → us-east-1 origin → 3 ALBs → 375 Spring Boot m5.xlarge boxes (125 per AZ across 3 AZs) → Redis Cluster (3 shards + 3 replicas = 6 nodes) → MySQL (4-shard Vitess, still single region). Interactive CDN hit-rate slider (70% → 50% → 30% → 0%): origin RPS and required capacity indicators respond in real time — origin traffic climbs from ~300K RPS at 70% hit to 1M RPS at 0% hit as the CDN offloads less. Use representative grouping ("375 App Instances" card, expandable) rather than 375 individual boxes.

Do the Math — Origin Traffic After CDN

Global traffic: 1M RPS average, 2M peak
CDN hit rate: 70% typical for URL Shortener (short TTL, hot power-law distribution)
Origin RPS: 1M × 30% = 300K RPS to origin infrastructure

That is smaller than Phase 2 (100K RPS to origin) × 3 — so we are at ~3× Phase 2 origin scale, not 10× despite the 10× global traffic increase. The CDN did the heavy lifting.

Capacity Math at Origin (Single Region)

App tier — Java Spring Boot m5.xlarge (⚙️ workload-dependent ~2,400 RPS/box):
- Origin steady-state: 300K RPS
- Origin peak (2× steady): 600K RPS
- To survive 1-AZ failure at peak: 600K × 1.5 / 2,400 = 375 boxes total (125 per AZ)
- Canonical Phase 2.5 sizing: 375 m5.xlarge boxes (125 per AZ) — this correctly satisfies peak + 1-AZ-failure survivability
- Steady-state utilization: 300K / (375 × 2,400) = 33% — honest headroom because we correctly account for AZ-failure at peak burst
- Trade-off note: an earlier draft used 150 boxes (50/AZ) sized only for steady-state throughput, which does NOT survive a 1-AZ failure at 600K RPS peak (100 surviving boxes × 2,400 = 240K vs 600K required). If you deliberately choose the smaller 150-box fleet, be explicit that this tier is optimized for steady-state economics rather than peak-plus-failure survival.

Redis Cluster:
- Origin cache traffic: 300K × 90% hit + 30K SETEX = ~300K ops/sec
- cache.r6i.large: ⚙️ workload-dependent ~100K ops/sec → need 3-node Redis Cluster
- Plus 3 replicas for HA = 6 nodes total

MySQL (single-region Vitess, 4 shards):
- Read load: 300K × 10% miss = 30K read QPS → 7.5K per shard = 30% of the 25K QPS ceiling per shard
- Write load: 300K × 1% = 3K writes/sec → 750/shard = 7.5% of write ceiling per shard
- A single region with 4 shards handles this comfortably.
- Why 4 shards and not 1? Blast radius. If one shard's primary fails, only 25% of URLs are affected during the ~60s Vitess failover.

Load Balancers:
- 300K × 2 LCU/10K = 60 LCU modeled consumption per ALB
- Not a capacity ceiling — real per-ALB throughput at this workload is workload/quota-dependent (see "LCU is a Billing Dimension" section)
- We deploy 3 ALBs with DNS-weighted routing for HA + blast-radius isolation (not throughput math). Actual per-ALB capacity should be validated with load testing.

Order of magnitude: ~$0.016 per million redirects (🧮 $41,800/mo ÷ ~2.59T redirects/mo at 30-day month × 1M RPS; 📐 ILLUSTRATIVE) — best per-unit economy so far. Single region + CDN is remarkably efficient.

Decision Snapshot at 1M RPS

📊 Your dashboard shows:
- Origin app CPU: 46% (well-provisioned)
- Origin Redis Cluster CPU: 60% average (healthy)
- MySQL Vitess shards: 30% read util, 7% write util (comfortable)
- CDN hit rate: 70% (as designed)
- ALB LCU: 40% average across 3 ALBs (healthy)
- p50 US-east user latency: 15 ms
- p50 Sydney user latency: 320 ms ⚠️
- p95 Sydney user latency: 480 ms ⚠️
- Availability last 30 days: 99.94% ⚠️ (one 15-minute AZ-networking incident)

❓ What is the primary problem, and what do you do?

_{Answer + rationale below.}

✅ Answer: the primary problem is NOT throughput — every component is under 70% utilization. The primary problems are physics (cross-continent latency for Sydney users) and blast radius (one AZ incident nearly missed 99.95% SLO). Neither is fixed by "add more boxes." Both require multi-region deployment. Move to Phase 3.

Senior insight: the trap here is assuming high RPS means "shard for throughput." At 1M RPS, throughput is comfortable at a single region because CDN absorbed 70%. The forcing function is latency + availability, not capacity. Junior engineers see 1M RPS and reach for Vitess global sharding; senior engineers see 1M RPS and ask what the ACTUAL pain metric is.

When to Evolve — the Trigger to Phase 3 (10M RPS Multi-Region)

• Metric 1 (latency): cross-continent p95 latency > 200 ms for > 20% of user population
• Metric 2 (availability): measured availability < 99.95% (about 22 minutes downtime/month) — typically hits after the first minor regional incident
• Metric 3 (business): paying customers in a region where you have no infrastructure complain about performance
• Metric 4 (regulatory): data residency requirements (GDPR, per-country sovereignty) force per-region infra

None of these triggers are throughput. At 1M RPS with CDN, throughput is a solved problem. The evolution to Phase 3 is driven by physics and business, not by hitting a QPS ceiling.

When You Do NOT Evolve

If your users are geographically concentrated (say, all US, or all EU), your availability SLO is 99.9% not 99.99%, and you have no regulatory pressure — stay single-region. You will save ~50-60% of the cost while your users experience the same latency they always did. Not every high-RPS service needs to be multi-region. Multi-region is not a badge of honor; it is a targeted response to specific problems.

The Breaking Point — Physics, Not Capacity

Your traffic grows to 10M RPS. Even with CDN absorbing 70%, origin sees 3M RPS. The single-region architecture starts creaking:
- App fleet: 3M / 2,400 = 1,250 boxes in one region — operationally painful but doable
- Redis Cluster: needs 10-15 nodes in one region
- MySQL: 4 shards start feeling tight at 75K QPS per shard read load
- ALBs: 20+ ALBs in one region, DNS routing gets complex

But the real problem is not any of that. The real problem is that 40% of your users are cross-continent, and they experience 300+ ms latency on every cache miss. No amount of single-region optimization fixes physics.

Time to go multi-region.

Phase 3 — 10M RPS: Global Multi-Region + Vitess Sharding + KGS

Goal

Eliminate major single points of failure and reduce blast radius. Target sub-100ms latency for most users through geographic routing and regional placement; actual end-to-end latency depends on network path, last-mile conditions, cache state, and region selection — this is a design target, not a universal guarantee. Scale horizontally without theoretical ceiling.

The Architectural Overhaul

We change essentially everything simultaneously — but each change is driven by a specific bottleneck we now understand.

Change 1 — DNS-based geographic routing. Route53 (or Cloudflare DNS) sends users to their nearest region based on network latency. A user in Frankfurt hits eu-central servers; a user in Sydney hits ap-southeast.

Change 2 — Regional load balancer. In each region, an AWS ALB (Application Load Balancer) distributes traffic across multiple Spring Boot instances. If one instance dies, the ALB stops sending it traffic within seconds.

Change 3 — Horizontal cluster of app servers. Instead of one Spring Boot instance, we run hundreds of stateless instances per region; the canonical Phase 3 design uses 900 per region (see Capacity & Sizing below). Adding capacity is now "launch more instances." Removing capacity is "kill some instances." Neither affects data.

Change 4 — Redis Cluster instead of single-node Redis. Data is sharded across multiple Redis nodes. If one node fails, traffic reroutes to the remaining nodes, and only that shard's keys are temporarily affected.

Change 5 — Sharded MySQL via Vitess. We do not migrate to Cassandra or DynamoDB. Instead we use Vitess — a MySQL-compatible sharding layer originally built by YouTube. It gives us horizontal write scaling while keeping the operational tooling, backup story, and query language we already know.

Change 6 — Standalone Key Generation Service (KGS). Because we sharded MySQL, we no longer have a single AUTO_INCREMENT sequence. We need a dedicated service that hands out unique IDs to any app server on any shard.

Capacity & Sizing at Phase 3 (10M RPS)

Time to count boxes for a genuinely distributed system operating at 10 million requests per second globally.

Traffic:
- 10,000,000 RPS average globally = ~864 billion redirects / day = ~26 trillion / month
- Split 3 regions: 3.33M RPS avg per region, peak ~6.7M per region
- CDN 70% edge-cache hit rate: origin sees ~1M RPS per region average, ~2M peak per region
- Read/write split: 99% reads / 1% writes (same as prior tiers)

App tier per region — Java Spring Boot m5.xlarge (⚙️ workload-dependent ~2,400 RPS/box):
- Base origin load: 1M RPS / 2,400 = 417 boxes for steady-state throughput
- Peak with burst: 2M / 2,400 = 833 boxes for peak throughput
- Design decision: 900 boxes per region (300 per AZ) — sized for peak throughput plus small redundancy margin
- Explicit trade-off: 900 boxes handles the 2M/region peak (full fleet: 900 × 2,400 = 2.16M capacity). This tier does NOT survive a full 1-AZ failure at peak. After 1-AZ loss: surviving 600 boxes × 2,400 = 1.44M capacity vs 2M peak (28% capacity shortfall). This is an explicit design trade-off — for full AZ-failure survival at peak burst, the fleet would need to be 1,250 boxes per region (417 per AZ), a ~40% cost increase. At Phase 3 we accept the trade-off because (a) peak burst is brief, (b) most peak minutes are not coincident with an AZ failure, and (c) at 10M RPS scale the incremental $$M/month for AZ-failure-at-peak survivability is a business decision — state it, don't hide it.
- Steady-state utilization: 1M / (900 × 2,400) = 46% — comfortable at steady-state (peak headroom accepted as a scaling risk)
- Global total: 2,700 boxes
- At this scale, consider even larger instances (m5.2xlarge ~4,800 RPS/box → 450 boxes per region). Trade-off: larger blast radius per box failure.

Redis Cluster per region:
- Origin traffic hitting cache: 1M × 99% (redirects) = 990K read RPS/region
- With 90% cache hit rate: 990K × 90% = 891K GET/sec + 99K SETEX/sec = ~990K ops/sec per region
- cache.r6i.large ceiling: ~100K ops/sec/node
- Need: 10 shards per region at 100K ops/sec each; for HA add replicas → 10 primaries + 10 replicas = 20 nodes per region
- Global total: 60 Redis nodes

MySQL sharded via Vitess:
- MySQL read load: 990K read RPS × 10% cache miss = 99K read QPS per region
- Sharded across 32 shards globally (see Sharding Logic Deep Dive above): ~3K read QPS per shard per region
- Under the 25K QPS ceiling per shard = 12% utilization per shard. Sharded for blast radius and geographic locality, not throughput
- Write load: 1M × 1% = 10,000 writes/sec per region ÷ 32 shards = ~313 writes/sec per shard = 6% write utilization
- Deployment: 32 shards × (1 primary + 2 same-region replicas + 1 cross-region replica) = 128 MySQL instances globally
- Primary placement: round-robin across 3 regions (Shards 1-11 primary in us-east, 12-21 in eu-west, 22-32 in ap-south). Explicit trade-off: this design optimizes read locality (via same-region replicas) and operational simplicity, but because shard primaries are placed round-robin (not by writer-region affinity), some URL-creation writes cross regions — a user in Sydney creating a URL whose short_code hashes to a shard whose primary is in us-east-1 pays the cross-Pacific write latency. A production deployment with dominant write-locality requirements could adopt region-aware shard placement (map the shard key to a shard whose primary is in the writer's region) at the cost of more complex resharding operations. This course uses round-robin as the illustrative default because it demonstrates the multi-region operational model most clearly.

KGS per region:
- ID generation rate: 100,000 IDs/sec globally (⚙️ Phase 4 canonical workload — matches the KGS Capacity Sizing derivation below) → ~33,300 IDs/sec per region (2 KGS instances per region for HA = ~16,700 IDs/sec per instance)
- KGS ceiling per instance: ~200-500K IDs/sec pre-generated
- 1 KGS instance per region is enough — but for HA run 2 per region
- Global total: 6 KGS instances

Load Balancers per region:
- Origin load per region: 1M RPS × 2 LCU/10K = 200 LCU used
- Multiple ALBs per region (~8 ALBs per region for blast-radius isolation and AWS quota conversations) via DNS-weighted routing. The count is an operational choice driven by real-world ALB quotas + blast-radius policy, not a "25 LCU / ALB" math ceiling (which was an earlier-draft misconception).
- Global total: 24 ALBs

CDN (CloudFront / Cloudflare):
- Handles 70% of traffic globally = 7M RPS at the edge
- Effectively unlimited capacity, priced per request + per GB egress
- Cost: ~$30K-50K/month at this scale for a hot-URL-heavy workload

Order of magnitude: ~$0.023 per million redirects at 10M RPS (🧮 $600K/mo ÷ ~25.9T redirects/mo at 30-day month × 10M RPS; 📐 ILLUSTRATIVE). Unit economics improve with scale right up until you go multi-region. Note this is ~43% HIGHER per-redirect than the 1M single-region tier ($0.016/M → $0.023/M). Multi-region is bought with unit cost, not rewarded by it — you pay a per-redirect premium for latency and blast-radius isolation. That is a business decision, not an efficiency win. Name it as such in the design review.

[🔗 REFERENCE WIDGET · `SystemSizingDiagram`]
> Move the slider to 10M RPS. Reader sees the full multi-region topology: 3 regions × (900 app boxes + 20 Redis nodes + Vitess shards). Toggle "disable CDN" to see origin RPS jump from 1M to 3.3M per region — infrastructure would need to scale ~3× immediately.

[🔗 REFERENCE WIDGET · `VerticalVsHorizontalCurves`]
> Log-log chart comparing "one giant box" cost curve (flattens at hardware ceiling around 128 vCPU × ~100K QPS) vs "many small boxes" (linear, no ceiling). Reader sees the crossover point where horizontal wins — around 30 RPS, where two m5.large ($130) outperforms one m5.xlarge ($260) for the same throughput but adds redundancy.

[🎬 ANIMATED DIAGRAM · `phase-3-global-architecture`]
> Map view: users on 5 continents. Each user's request draws a line to Route53 → their nearest region's ALB. Inside the region, ALB fans out to 900 Spring Boot boxes. Boxes connect to (a) Redis Cluster (10-shard, 20 nodes/region), (b) Vitess vtgate → 32 sharded MySQL primaries + replicas, (c) KGS pod (Java + Redis queue backed by durable MySQL high-water mark). Highlight one full write path (user → Spring Boot → KGS → Vitess) and one full read path (user → Spring Boot → Redis) with contrasting colors.

The Key Generation Service — Deep Dive

This is the newest and most subtle piece. Let's walk through why it exists and how it works.

The problem. In a sharded MySQL setup, no single shard has knowledge of all IDs. If Shard 1 uses AUTO_INCREMENT and generates ID 5, and Shard 2 uses AUTO_INCREMENT and generates ID 5 too, we have a duplicate. Base62.encode(5) is the same short code — a collision, silent and catastrophic.

Naive solution: shard-offset AUTO_INCREMENT. Configure Shard 1 to start at 1, Shard 2 at 1,000,000,000, Shard 3 at 2,000,000,000. Works, but rigid. Adding a new shard requires careful upfront planning of how big each range will grow.

Twitter's Snowflake solution. Every ID is 64 bits: [timestamp | worker_id | sequence]. Distributed but stateful — every worker must know its unique ID, requiring coordination via ZooKeeper or Redis at startup.

Our chosen solution: the Key Generation Service (KGS).

The KGS is a dedicated Java service that pre-generates large batches of unique 7-character base62 codes and stores them in a Redis queue. Any app server, in any region, can pop a code from the queue and use it for a new URL. Codes are never repeated because they come from a monotonic counter — and critically, that counter's high-water mark is persisted to MySQL before any ID in the batch is used, so a KGS crash never resets IDs backwards.

sql
-- Durable KGS state — one row, updated atomically per batch
CREATE TABLE kgs_state (
    id      INT PRIMARY KEY,
    next_id BIGINT NOT NULL
) ENGINE=InnoDB;

INSERT INTO kgs_state (id, next_id) VALUES (1, 1);

java
// KGS orchestrator (bean 1)
@Service
public class KeyGenerationService {

    private final JedisPool jedisPool;
    private final KgsRangeAllocator allocator;   // separate bean; see below
    // ⚙️ KGS SIZING (from workload assumptions — see "KGS Capacity Sizing" below):
    //   Phase 4 workload: 100,000 URL creations/sec globally = ~33,000/sec/region
    //   Per KGS instance (2 per region for HA): ~16,700 IDs/sec sustained consumption
    //   Safety target: queue must hold 5+ minutes of consumption at peak
    //     → 5 min × 16,700/sec = ~5M codes per instance minimum
    private static final int LOW_WATERMARK   = 5_000_000;  // trigger refill early
    private static final int TARGET_QUEUE    = 10_000_000; // ~5 min safety window at 33K/sec regional consumption
    private static final int BATCH_SIZE      = 1_000_000;  // 1M codes per reservation

    // Refill check every 5s (not 60s from an earlier draft — 60s couldn't sustain 100K/sec)
    @Scheduled(fixedDelay = 5_000)
    public void refillQueue() {
        try (Jedis jedis = jedisPool.getResource()) {
            long queueSize = jedis.llen("kgs:available");
            if (queueSize >= LOW_WATERMARK) return;

            // Refill in loop until we approach the target queue depth
            while (queueSize < TARGET_QUEUE) {
                // 1. Atomically reserve a durable ID range via a SEPARATE Spring bean
                //    so Spring's transactional proxy applies. A crash after step 1
                //    leaks IDs but never reuses them.
                long batchStart = allocator.reserveRange(BATCH_SIZE);

                // 2. Materialize the batch of base62 codes
                List<String> batch = new ArrayList<>(BATCH_SIZE);
                for (int i = 0; i < BATCH_SIZE; i++) {
                    batch.add(Base62.encode(batchStart + i));
                }

                // 3. Shuffle to defeat casual enumeration, then enqueue
                Collections.shuffle(batch);
                jedis.rpush("kgs:available", batch.toArray(new String[0]));

                queueSize += BATCH_SIZE;
            }
        }
    }

    public String nextCode() {
        try (Jedis jedis = jedisPool.getResource()) {
            String code = jedis.lpop("kgs:available");
            // Queue exhaustion = a write-path failure — surface it as SEV-1
            if (code == null) throw new KgsQueueExhaustedException(
                "KGS queue is empty; URL creation temporarily unavailable");
            return code;
        }
    }

    // Operational metrics — expose via Micrometer / Prometheus
    // - kgs.queue.depth (gauge)
    // - kgs.refill.rate.per_sec (meter)
    // - kgs.allocation.latency.ms (histogram)
    // - kgs.range.reservation.latency.ms (histogram)
    // - kgs.queue.exhaustion.count (counter)
    // - kgs.consumption.rate.per_sec (meter)
}

// Range allocator (bean 2) — separate class so Spring's @Transactional proxy applies
@Service
public class KgsRangeAllocator {

    private final JdbcTemplate jdbc;

    @Transactional(isolation = Isolation.REPEATABLE_READ)
    public long reserveRange(int size) {
        // SELECT ... FOR UPDATE locks the single kgs_state row.
        // Any concurrent KGS instance's SELECT ... FOR UPDATE on the same
        // row blocks until this transaction COMMITs, guaranteeing
        // that no two allocations can produce overlapping ranges.
        Long start = jdbc.queryForObject(
            "SELECT next_id FROM kgs_state WHERE id = 1 FOR UPDATE",
            Long.class);
        jdbc.update(
            "UPDATE kgs_state SET next_id = ? WHERE id = 1",
            start + size);
        return start;
        // Transaction commits on return; MySQL binlog + Multi-AZ sync
        // durably persist the new next_id before the caller sees it.
    }
}

KGS Capacity Sizing — Why the New Numbers Work

An earlier draft of this course used BATCH_SIZE = 100,000 refilled every 60 seconds. That gives ~1,667 IDs/sec sustained per KGS instance — 60× too slow for the canonical Phase 4 workload of 100,000 URL creations/sec globally. Teaching that as production-safe would produce a system that runs out of IDs during the first traffic spike. Let us walk the math to make sure the new sizing actually sustains the workload.

Workload targets (⚙️ from canonical Phase 4 assumptions):

Refill throughput (⚙️ derived from code above):

Safety window (⚙️ if KGS itself pauses for any reason):

• Target queue depth: 10M codes per region
• Per-region consumption: ~33K codes/sec
• 🧮 Safety window if KGS pauses: 10,000,000 ÷ 33,000 = ~5 minutes
• Low-watermark trigger at 5M codes → 🧮 ~2.5 minutes of protection before refill must start
• If Redis queue is lost entirely, MySQL kgs_state.next_id (durable, Multi-AZ replicated) lets KGS resume in seconds without ID reuse

Queue exhaustion semantics:

• Queue empty → KgsQueueExhaustedException thrown from nextCode() → app tier returns HTTP 503 to the URL-creation endpoint
• The redirect endpoint is completely unaffected — reads don't touch KGS
• SEV-1 alert fires on kgs.queue.exhaustion.count metric increment
• On-call responds by (a) checking KGS pod health, (b) verifying MySQL kgs_state is available, (c) manually triggering a large batch reservation if automatic refill is stuck

Cross-region KGS resilience (design decision):

Each region's KGS operates on its own Redis queue but reserves ranges from the same durable kgs_state MySQL row. This centralizes the source-of-truth counter while decentralizing the queue. Two KGS instances per region (2/region × 3 regions = 6 total globally) provide N+1 HA within each region.

Open question 1 — concurrent refill. Two KGS instances in the same region can independently observe queue depth below the watermark and start refilling simultaneously. Duplicate IDs cannot occur — the MySQL SELECT ... FOR UPDATE in KgsRangeAllocator serializes range allocations. But bounded over-fill is tolerated by design: two instances refilling in parallel may push queue depth temporarily above TARGET_QUEUE by up to one batch size. This is intentional — the alternative would be a distributed lock (Redis SET-NX-EX) coordinating refill instances, which adds latency and a new failure mode. The over-fill "cost" is at most a few million extra codes sitting in the queue longer — well within capacity headroom. State this explicitly: no lease, bounded over-fill is preferred over lock coordination.

Open question 2 — cross-region failover. If both regional KGS instances fail simultaneously (both crashed, or the region's Redis Cluster is unavailable), the affected region's URL-creation write path degrades after the ~5-minute safety window expires. This is an operational degradation, not an implemented cross-region failover. Options for extending resilience:
- (a) Deploy 3 KGS instances per region (N+2 instead of N+1) to make simultaneous failure less likely.
- (b) Implement cross-region KGS routing at the app tier: if the local KGS queue is exhausted, app servers can call a peer region's KGS (via a per-region service endpoint) at the cost of cross-region write latency (~50-150ms depending on region pair).
- (c) During a region's KGS outage, accept the write-path degradation and rely on regional failover of the entire app tier to a healthy region.

This course adopts option (c) — regional-failure fallback via app-tier routing — as the illustrative design. Options (a) and (b) are production-grade extensions worth implementing but out of scope for the illustrative canonical architecture. Do not read the earlier "other regions can serve their traffic" wording as an implemented failover path — it is only true if the app tier itself fails over the whole regional workload.

Why the two-bean split matters. An earlier draft of this course had @Transactional on a method called from refillQueue() in the same bean. Spring's transactional behavior is implemented via a proxy around the bean; when a method calls another method of the same bean directly (`allocateBatch(BATCH_SIZE)`), the call goes through the raw `this` reference, bypassing the proxy — and the `@Transactional` annotation is silently ignored. The SELECT ... FOR UPDATE still runs, but without the surrounding transaction the row lock is released immediately after the SELECT, allowing a concurrent KGS instance's SELECT to see the same next_id and produce overlapping ranges — a silent duplicate-ID bug that surfaces months later as duplicate URLs.

Moving reserveRange to a separate `@Service` bean (KgsRangeAllocator) forces the call to go through Spring's proxy, guaranteeing the transaction actually happens. This is a subtle but critical Spring gotcha; the fix is worth teaching explicitly.

Concurrency guarantee. Two concurrent KGS instances calling reserveRange(BATCH_SIZE) simultaneously will serialize on the kgs_state row's FOR UPDATE lock — MySQL's row-level locking guarantees strict serialization. The second caller blocks until the first commits, then reads the updated next_id. No two allocations ever produce overlapping ranges.

Durability invariant. Allocated IDs may be leaked (if the KGS crashes between range reservation and Redis push, those 100K IDs are permanently unused). Allocated IDs are never reused — because the durable kgs_state.next_id MySQL value only ever increases.

KGS Durability — why we need MySQL behind Redis

Redis is fast but volatile by default. If the KGS's Redis crashes without persistence, the queue disappears — and if the in-memory counter also disappears, KGS restarts at ID 1 and starts generating codes we already handed out. That is silent duplicate URLs pointing at the wrong destinations — a catastrophic outcome for a URL Shortener.

Two layers of defense against this failure mode:

Layer 1 — MySQL-backed high-water mark. The kgs_state.next_id column is the durable source of truth for "the smallest ID we have not yet allocated." Before we generate any code in a batch, we SELECT ... FOR UPDATE and UPDATE the row inside a transaction — MySQL's binlog + Multi-AZ replication guarantees the write survives any KGS crash. If the Redis queue is lost, we simply re-allocate a new batch starting from next_id; no duplicates, at worst we leak 100,000 IDs (out of the canonical Phase 3+ space of 62⁸ ≈ 218 trillion — negligible).

Layer 2 — Redis AOF for the queue itself. We configure Redis with appendonly yes and appendfsync everysec. Under this setting, Redis fsyncs its append-only file to disk every second. However, do NOT interpret this as "at most 1 second of lost codes is safely re-generatable" — that framing is wrong. The correct invariant is: MySQL kgs_state.next_id advances before codes are pushed to Redis; once a range is durably committed to MySQL, those IDs are considered permanently allocated. If Redis loses queued codes (crash, AOF truncation, deleted persistence file), those IDs are permanently leaked — they are NOT regenerated on refill. The next refill cycle reads the current kgs_state.next_id (which already advanced past the lost range) and allocates a NEW range above it. This preserves the uniqueness invariant (no two allocations ever produce the same ID) at the cost of wasted ID space. Given the canonical Phase 3+ space of 62⁸ ≈ 218 trillion codes, occasional Redis-side losses of ~10M codes are negligible (🧮 ~5 × 10⁻⁵ % of the namespace per incident); do not "recover" leaked ranges — that would risk reuse. AOF's write amplification is fine here: KGS pushes 1M codes into Redis every few seconds under steady state, well within the ⚙️ workload-dependent ~100K ops/sec reference per node.

What NOT to do: rely on in-memory AtomicLong alone (as an earlier draft of this KGS did). That gives you a fast counter until the first crash — after which you happily hand out Base62(1), Base62(2), ... again, silently overwriting production URLs. This is the kind of bug that surfaces once, six months into production, and takes a full postmortem to diagnose.

Why this design?

• App servers do a single Redis LPOP for the next available code — around 1 millisecond.
• KGS instances refill the queue in the background — never blocking the write path.
• If the KGS becomes unavailable, the pre-generated queue provides approximately ~5 minutes of write-path continuity at the modeled ~33K IDs/sec regional consumption rate (🧮 10M queue ÷ 33K/sec ≈ 303 seconds). The safety window scales inversely with consumption — a burst that pushes regional consumption to 100K/sec shortens the window to ~1.7 minutes. Provision the queue depth for your workload's peak, not its average.
• Codes are unique because they come from a monotonic counter.
• Codes are statistically hard to enumerate because we shuffle the batch before enqueueing — adjacent codes in the queue are not adjacent in ID space, so a scraper cannot simply increment their last-seen code by one to find the next one. (⚠️ This is not cryptographic unpredictability — see the callout below.)
• Multiple KGS instances can safely run in parallel by partitioning the counter space (KGS-1 handles even ranges, KGS-2 handles odd, or by allocating chunks via a coordination service).

The New Write Path

java
@Service
public class ShortenerService {

    private final KeyGenerationService kgs;
    private final UrlRepository repo;

    public String shorten(String longUrl) {
        String code = kgs.nextCode();
        repo.save(new UrlEntity(code, longUrl));
        return code;
    }
}

Notice what is absent: no lookup for collision check, no round-trip retry. Just POP → INSERT → return. A write completes in about 10 milliseconds end-to-end.

Shuffling ≠ Cryptographic Unpredictability — an Honest Callout

An earlier draft of this course said the shuffled queue "defeats enumeration attacks." That claim was too strong. Here is the precise truth:

What shuffling gives you:
- A casual scraper who has your last-seen short code cannot guess the next one by incrementing. They would need to try random codes, and the canonical Phase 3+ address space of 62⁸ ≈ 218 trillion is far too big to brute-force randomly.
- Your codes look non-sequential to anyone browsing your redirect logs.

What shuffling does NOT give you:
- A determined adversary who observes millions of your issued codes over weeks can perform statistical analysis and recover much of the underlying counter sequence. The shuffle order is a permutation of ~100,000 sequential integers — it has ~log₂(100,000!) ≈ 1.5 million bits of entropy in theory, but each observation constrains the permutation. Sophisticated attackers can predict future code ranges within a few thousand IDs.
- Anyone with read access to the Redis queue (an ops mistake, a compromised worker) sees the exact ordered sequence.

When shuffling is enough:
- Public URL shortener where individual URL discovery is a nuisance, not a security breach.
- URLs contain no sensitive information — leaking one just points at a public destination.

When shuffling is NOT enough — you need cryptographic unpredictability:
- URLs behind auth (private company doc, confidential invoice, password reset link). If a determined adversary can enumerate any short code, they get free URLs to try against your auth layer.
- Rate-limited signup/verification links. Predictability lets adversaries pre-generate tokens.

How to actually get cryptographic unpredictability:

The instinct here is to keep the short code short and just make it unguessable — replace Base62.encode(id) with something like Base62.encode(HMAC_SHA256(secret, id)[:7 chars]). That instinct is wrong, and the math below shows why. The fix is not a better hash; it is recognizing that these are two different problems with two different answers.

First, the arithmetic that kills the truncated-HMAC idea.

Raw HMAC-SHA256 output is 256 binary bits. Truncating it to 7 Base62 characters keeps only 🧮 7 × log₂(62) ≈ 41.7 bits — you have thrown away 214 bits of the digest. The cryptographic strength of HMAC does not survive that truncation; what survives is the birthday bound of whatever space you truncated into:

• Address space: 62⁷ ≈ 3.52 × 10¹² codes
• 50% collision probability at 🧮 1.1774 × √(62⁷) ≈ 2.2 million codes
• Expected collisions for n items in a space of size N ≈ n² / 2N. At n = 10¹⁰ URLs (a plausible corpus for an extreme-scale shortener): 🧮 (10¹⁰)² ÷ (2 × 3.52 × 10¹²) ≈ ~14 million collisions

Going to 8 characters (62⁸ ≈ 218T, 🧮 8 × log₂(62) ≈ 47.6 bits) reduces that to 🧮 ~229,000 expected collisions — three orders of magnitude better, still not zero. Truncation to a human-typeable length and cryptographic collision resistance are in direct tension. You cannot have both. So stop trying, and split the problem:

Case A — the public URL shortener (this course's canonical design).

unique monotonic ID from KGS → optional permutation/shuffle → Base62

This is the right trade for a public shortener: the destination is public anyway, so leaking one code discloses nothing that a link-sharer did not already intend to share.

Case B — security-sensitive opaque tokens.

When the URL itself is the secret — a password-reset link, a confidential invoice, a signed document, an unauthenticated preview link — you need a token drawn from a space large enough that guessing is hopeless, and you accept that it will not be short:

cryptographically random 96-bit or 128-bit value → Base62

java
// Security-sensitive tokens: draw from a large space, do NOT truncate a digest.
private static final SecureRandom SECURE_RANDOM = new SecureRandom();

public static String opaqueToken(int bits) {          // 96 or 128
    byte[] raw = new byte[bits / 8];
    SECURE_RANDOM.nextBytes(raw);                     // CSPRNG, not java.util.Random
    return Base62.encodeBytes(raw);                   // no truncation anywhere
}

Note that encodeBytes(byte[]) is a different method from the Base62.encode(long) used for KGS IDs earlier in this chapter: a 96- or 128-bit value does not fit in a Java long (64 bits), so it must be encoded from the raw byte array via BigInteger rather than by repeated division on a primitive. Reusing the long encoder here would silently truncate your token back down to 64 bits — reintroducing the exact bug this section exists to prevent.

The length cost of unpredictability, stated plainly:

A 96-bit token is ~17 characters and a 128-bit token is ~22. That length is the price of unpredictability — pay it, or do not claim the property. Do not shorten a security token to make it prettier; you are trading an unguessable secret for a guessable one to save five characters.

Even at 96+ bits, keep the UNIQUE index on short_code. Collision probability is negligible, not zero, and the index converts an astronomically rare collision from a silent wrong-URL mapping into a loud, retryable INSERT failure. Uniqueness should be enforced, never merely assumed.

Where HMAC is still the right tool. HMAC earns its place when you need to verify a token you issued without a database lookup — recompute the MAC over the token body and reject garbage before it ever reaches MySQL, which is a real defense at 1B RPS. Use the full-width MAC as a separate appended field (token = random body + MAC tag), never as a truncated substitute for the token itself. That is authentication, not identifier generation.

The three properties, and which mechanism gives you which:

Uniqueness ≠ unpredictability ≠ collision resistance. They are three separate properties requiring three separate mechanisms, and truncation destroys the third while appearing to preserve the second. Conflating them is one of the most common security errors in system design interviews — and in production.

For this course's URL Shortener (public bit.ly-style service), plain Base62 + shuffle (Case A) is adequate — we are not protecting sensitive URLs. But we say so explicitly rather than overclaiming, and if the product ever adds private links, that is a Case B feature requiring a second, longer token format alongside the short public one — not a tweak to the existing generator.

The New Read Path

Structurally unchanged from Phase 3, but traffic now hits the regional Redis Cluster first. Cross-region reads are rare — URLs are typically shared and consumed in the same locale (a link tweeted from Sydney is mostly clicked by people in Sydney).

Vitess — Why MySQL Sharding, Not NoSQL?

The pop-culture answer for "high scale" is often Cassandra or DynamoDB. This is frequently the wrong answer. Here is why we stay with MySQL for URL Shortener specifically:

• Operational maturity. Every SRE, DBA, and backup tool understands MySQL. Cassandra and DynamoDB have steeper operational learning curves and more subtle failure modes.
• Cost. Managed DynamoDB is famously expensive at high throughput. Vitess-managed MySQL on EC2 is 3-5× cheaper than DynamoDB at comparable throughput profiles (workload-dependent).
• Query familiarity. SQL is the query language your team already knows. Cassandra's CQL is similar but limited (no joins, restricted WHERE clauses). DynamoDB requires access-pattern-first modeling — a paradigm shift.
• Vitess is battle-proven. It runs YouTube, Slack, GitHub, and Square. It doesn't just handle billion-row workloads; that is its native scale.
• Consistent transactions inside a shard. MySQL still gives us ACID within a shard, which we use for occasional "check-and-update" flows.

When would you migrate to NoSQL?

• Key-only access patterns. No range scans, no joins, no transactions. DynamoDB becomes competitive.
• Sustained >1 million writes per second. Cassandra's ring-based writes may become cost-competitive.
• You are already committed to a NoSQL-first cloud stack (e.g., all-AWS with heavy DynamoDB use elsewhere) and want operational uniformity.

For a URL Shortener specifically, none of these apply. MySQL + Vitess is the right answer.

Sharding Logic — Full Deep Dive

Sharding is the single most complex change in this course. Let us walk through it with the same rigor as everything else.

Why shard? (Ranked by importance for URL Shortener)

1. Blast radius. A single global MySQL primary means: if it dies, every region loses the write path simultaneously. Sharding gives you independent failure domains — one shard's outage affects one shard's data.
2. Geographic write locality. A US user creating a URL should hit a US-region database (5 ms writes), not a Frankfurt-region database (100+ ms cross-region writes). Sharding lets us route writes to a shard physically near the user.
3. Independent HA per region. Each region needs its own primary + replicas for independent failover. Sharding is what makes this operationally possible without weird master-master replication.
4. Future proofing. If we grow 100× to 100 B / month, adding shards is a routine operation. Growing a single unsharded database is not.

Notice what is not on this list at Phase 3: raw write throughput. At 30,000 write QPS globally sharded 32 ways = ~1,000 write QPS/shard, a single MySQL primary handles it comfortably (well within its 5-10K write ceiling). We are sharding for architectural reasons, not because we hit a QPS ceiling.

When should you shard?

You shard when at least one of these becomes true:
- Cross-region write latency exceeds acceptable UX bounds (>150 ms user-perceived)
- Single-region blast radius becomes unacceptable to the business (typically when you cross ~$X ARR)
- You are within 6 months of hitting the single-primary write ceiling (~5,000-10,000 write QPS) at current growth rate
- You need per-region data residency for regulatory reasons (GDPR, data-sovereignty laws)

You do not shard because "we might need it eventually." Sharding introduces permanent operational complexity: schema migrations become multi-shard rollouts, backups multiply by shard count (4× at Phase 2.5, 32× at Phase 3), and every new engineer has to learn the shard-routing rules.

How do we shard?

Two decisions:
1. Shard key — what column decides which shard a row lives on?
2. Shard function — how does the shard key map to a specific shard?

Shard key: `short_code`. Every read and write targets a single URL by its short_code, so this is the natural key. No cross-shard queries are ever needed for URL Shortener workload.

Shard function: hash-based vindex — NOT a prefix.

Here is a subtle trap that catches many first-time system designers, including an earlier draft of this very course. A tempting "obvious" shard function would be use the first 2 characters of `short_code` as the shard key — with 62² = 3,844 possible prefixes and (say) 32 shards, each shard would own about 120 prefixes. Clean, right?

Wrong. Base62-encoded IDs from a monotonic counter grow through the alphabet's leading characters progressively — Base62(1) = "1", Base62(62) = "10", Base62(3843) = "ZZ", Base62(3844) = "100", etc. Under variable-length Base62 output (no leading zero-padding), the first 62² = 3844 URLs produce codes 1-2 characters long, all starting with digits 0-9 or lowercase letters a-z. Under fixed-length 7-char output with leading zero-padding, sequential IDs start with "0" characters until the counter crosses 62⁶ ≈ 57 billion. Either way, sequential IDs from a monotonic counter concentrate on the low end of the leading-character space until the counter grows through most of the address space — for the canonical Phase 3+ 8-character Base62 space of ~218T, this concentration persists for ~230 years at 30K URL creations/sec (or ~69 years at 100K/sec). This is called monotonic key skew, and it silently defeats prefix-based sharding for the service's practical lifetime. Use a hash-based vindex instead.

The fix: hash the shard key before mapping to a shard. Vitess supports this natively via its hash vindex:

json
{
  "sharded": true,
  "vindexes": {
    "hash": { "type": "hash" }
  },
  "tables": {
    "urls": {
      "column_vindexes": [
        { "column": "short_code", "name": "hash" }
      ]
    }
  }
}

Under the hood Vitess applies `MD5(short_code) mod shard_count` (or an equivalent well-distributed hash — Vitess actually uses a deterministic 8-byte hash on the key). A monotonic counter's Base62 output has no correlation with its MD5 hash, so every shard receives statistically uniform write traffic from ID 1. The skew disappears.

Shard count: choose progressively as workload justifies.

• The hash vindex distributes writes uniformly regardless of the count — so the count is not chosen "for uniformity" but "for capacity headroom + operational blast radius"
• Vitess's hash vindex is deterministic — the same short_code always maps to the same shard on both reads and writes
• This course uses two shard counts across the RPS progression:
• Do not treat "32 shards" as universally correct. It is calibrated to this course's specific workload and evolution. If you were building a URL Shortener with 90:10 writes-to-reads (unusual), you would need many more shards from Day 1. If your total corpus fits comfortably in 1 primary and blast radius is not a business concern, don't shard at all.

Also updated in the sharding scheme: we removed the "shard by first 2 chars of short_code" strategy from an earlier draft precisely because it produces the monotonic-skew problem described above. The hash-based vindex is the only correct answer for a monotonic-ID-derived key.

How the application talks to shards:

Applications never talk to a specific shard directly. They talk to Vitess's vtgate — a stateless proxy that:
1. Parses the incoming SQL
2. Extracts the shard key from the WHERE clause
3. Routes the query to the correct shard(s)
4. Returns the response

java
@Configuration
public class DataSourceConfig {
    @Bean
    public DataSource dataSource() {
        HikariConfig config = new HikariConfig();
        config.setJdbcUrl("jdbc:mysql://vtgate.internal:15306/urls_keyspace");
        config.setUsername("app");
        config.setPassword("${MYSQL_APP_PASSWORD}");
        return new HikariDataSource(config);
    }
}

To the application, this looks like a single MySQL database. Under the hood, Vitess is fanning out to the configured shards (4 at Phase 2.5, 32 at Phase 3). This is the pattern's central magic: operational complexity moves into a middleware layer, application code stays clean.

Ripple effects — every choice cascades.

Sharding forces the following downstream changes:

• No `AUTO_INCREMENT` for IDs — sequences are per-shard, so IDs from different shards would collide. This is why we introduce the KGS. Sharding causes KGS.
• No cross-shard JOINs — Vitess technically supports them, but performance is scatter-gather across all shards (4 in Phase 2.5 single-region, 32 in Phase 3 multi-region). For URL Shortener we never need them; our schema is one table with one lookup column. This is why URL Shortener is a perfect sharding candidate.
• No global UNIQUE constraints across shards — we cannot enforce UNIQUE(short_code) at the MySQL layer if short_code spans shards. But the KGS pre-generates globally unique codes, so this constraint is guaranteed at the source.
• Backups per shard — each shard needs its own backup schedule and restore procedure (4 at Phase 2.5, 32 at Phase 3). Vitess has tooling for this (vtctl Backup), but it is real operational work.
• Rebalancing on growth — Vitess provides the Reshard workflow: it copies a shard's data to two new shards live, catches up on the writes that happened during the copy, then atomically flips traffic. Zero downtime, but it is a multi-hour operation you carefully plan.

Failure semantics:

• One shard fails (primary lost) — the primary impact is confined to reads and writes for the data hashed to that shard. Naively that suggests ~1/N of URLs (1/32 ≈ 3% at Phase 3, 1/4 = 25% at Phase 2.5), but real user-visible behavior depends on: (a) replica topology + whether reads can fail over to replicas immediately, (b) the Vitess failover automation (typically 30-60 second window in which writes to that shard fail while promotion completes), (c) the client's write-retry policy — a Kafka-buffered retry queue may absorb short outages transparently, (d) whether the failure affects a primary or a replica, (e) consistency requirements at the caller (stale reads from replicas may be acceptable for redirects but not for URL creation confirmation). The naive "1/32 of URLs" number is an upper bound on affected data; actual user-visible impact is workload- and topology-dependent.
• Vitess vtgate fails — the proxy layer is stateless, run 3+ instances behind an ALB, one death is tolerated.
• All shards in a region fail — Route53 fails traffic over to another region. Writes for URLs whose "home region" was the dead one may see cross-region latency temporarily; reads still work from CDN + Redis + other-region replicas.

Multi-Region MySQL — Replication, Consistency, RPO, RTO, Failover

An earlier draft of this course said "Shard 1 primary in us-east-1, replicas in eu-west / ap-south" without saying what happens when a primary fails. That is where the interesting engineering lives. Let us unpack it.

Where writes go.

Every shard has exactly ONE primary at any moment. That primary lives in ONE region. Writes to that shard travel to that region regardless of where the user is. If a US user creates a URL that hashes to Shard 5 whose primary is in eu-west-1, the write pays ~90 ms cross-Atlantic latency.

Design choice: which shards' primaries go in which region?

• Round-robin — spread primaries evenly (Shard 1 → us-east, Shard 2 → eu-west, Shard 3 → ap-south, Shard 4 → us-east, ...). Simplest. Some fraction of writes always pay cross-region latency.
• Locality-optimized — inspect the shard-key hash to align a URL's home shard with the creator's region. Requires the app tier to know the user's region at write time and hash accordingly. Adds latency at write, saves latency at every future read/write of the same URL.
• Neither for URL Shortener — because URLs are read-heavy (~10,000:1 at extreme scale) and writes are already async in the user's mind (they submit, wait a few hundred ms, done), we choose round-robin placement simplicity. Write latency dispersion is acceptable. A production system with dominant write-locality requirements could adopt region-aware shard placement at the cost of more complex resharding operations — see the Phase 3 sharding trade-off callout for detail.

Where reads go.

Every shard has multiple replicas — typically 1 primary + 2 replicas — spread across 3 AZs in the primary's region, and 1 replica in each other region for HA.

• Same-region read — hits a local replica. ~5-10 ms.
• Cross-region read — only happens if the local replica is stale beyond acceptable freshness OR the whole region is failing over. ~100 ms.
• Read via cache — for the 90-99% of URL Shortener reads that hit Redis, MySQL is not touched at all. This dominates the read-latency story.

Sync vs async replication.

Two knobs on MySQL replication:

• Async replication (default) — primary commits when local write completes; replicas catch up "eventually." Fastest primary writes (~5 ms). Replication lag varies: typically 50-500 ms, can spike to seconds under load. On primary failure, up to that lag window of writes are lost.
• Semi-sync replication — primary waits for at least one replica to acknowledge before returning success to the client. Slower primary writes (~10-20 ms). Replication lag near zero. On primary failure, the acknowledged writes are already on the replica.
• Sync replication (rare) — primary waits for a quorum of replicas. Slowest (~30-100 ms cross-AZ). Strongest guarantee. Rarely used at scale because of the latency cost.

For URL Shortener, we choose semi-sync within a region + async across regions. Rationale: losing 200 ms of writes on a primary failure is acceptable (the user retries), but region-crossing sync writes would slow down every URL creation to 100+ ms — unacceptable for user experience.

RPO — Recovery Point Objective.

RPO is "how much data can we lose in a failure event?" Measured in seconds/minutes of writes.

• Same-region primary failure with semi-sync: RPO ~0 seconds (acknowledged writes survived on a replica in another AZ).
• Whole-region failure with async cross-region replication: RPO ~500 ms - 2 seconds (the lag window at the moment of failure).
• Simultaneous multi-region failure: RPO up to the entire replication lag between the last-standing region and the previous primary — potentially minutes.

For URL Shortener that RPO is acceptable — the writes lost are URLs that were being created in the moment of failure, and users can and will retry.

RTO — Recovery Time Objective.

RTO is "how long until the system is back?" Measured in seconds/minutes of downtime.

• Same-region primary failure with automated failover: RTO ~30-60 seconds (Vitess's EmergencyReparentShard promotes a replica to primary). During this window, that shard's writes fail; reads still work from replicas.
• Whole-region failure with cross-region promotion: RTO ~2-5 minutes (Vitess needs to promote a replica in another region, reconfigure vtgate routing, warm the new primary's buffer pool). Writes for that shard fail during the window.
• Simultaneous multi-region failure: RTO is "as long as it takes humans to intervene." Design for it not happening (spread across independent failure domains — regions in different geographic areas, not adjacent).

What the user actually sees during a failure.

• App reads: cache-hit reads are unaffected (Redis Cluster survives one node death). Cache-miss reads pay a bit more latency until the promoted replica warms up.
• App writes: for URLs on the dying shard, INSERT fails for the 30-60 sec RTO. App retries — or better, queues the write to Kafka and returns the pre-generated short_code from the KGS queue (the code is already committed to kgs_state; the URL body write can be replayed once the shard recovers).
• Analytics writes: unaffected — Kafka has its own multi-broker HA independent of MySQL.

The one hard constraint you cannot avoid.

Writes for a given shard are serialized through its primary. If your workload has a hot shard (one URL receiving 90% of writes — think a viral link's click-count updates), the primary is the bottleneck no amount of horizontal replication fixes. This is why we cache the redirect path and route click events to Kafka rather than MySQL — the MySQL write path is precious, we do not spend it on things that can be aggregated.

Load Balancer Capacity — LCU is a Billing Dimension, Not a Hard Ceiling

An earlier draft of this course treated 25 LCU as a hard per-ALB throughput ceiling. That framing was incorrect and worth unpacking honestly.

What LCU actually is (📗 VERIFIED DOC):

AWS's official documentation is clear: an LCU (Load Balancer Capacity Unit) is a BILLING dimension, not a per-ALB throughput cap. AWS charges you per LCU-hour consumed. There is no documented "your ALB stops working at 25 LCU" limit — ALBs auto-scale internally and AWS has published cases of single ALBs handling >1 million RPS for cache-friendly workloads.

1 LCU = the maximum of four workload dimensions in any given hour:
- New connections / second
- Active connections
- Processed bytes / hour
- Rule evaluations / second

(Reference: AWS Elastic Load Balancing pricing documentation.)

What our course was doing:

The "25 LCU / ALB" number that appeared in earlier drafts was a course modeling assumption used to teach capacity planning discipline — pretending there was a hard-and-fast cap. In reality, real-world ALB throughput is limited by AWS's internal auto-scaling and quotas that are workload-specific and adjustable via support tickets.

What we teach going forward:

• 📗 VERIFIED FACT: AWS bills the ALB per LCU. The 4 dimensions above define LCU consumption. This is the vendor-documented model.
• ⚙️ WORKLOAD ASSUMPTION: For URL Shortener's specific request profile (small responses, brief connections, single-rule routing), approximately 2 LCU per 10,000 RPS is consumed. This ratio should be validated with load testing against your specific request shape.
• 📐 ILLUSTRATIVE DERIVATION: At the modeled workload, 10K RPS ≈ 2 LCU, 100K RPS ≈ 20 LCU, 1M RPS ≈ 200 LCU per ALB. These are cost drivers, not hard limits.

Real-world ALB scaling operations (the honest engineering answer):

• For any traffic level, capacity planning is: (a) measure LCU consumption in staging, (b) confirm your account's ALB quota via the AWS Service Quotas console, (c) request quota increases if approaching them, (d) load-test with production-shaped traffic.
• Under high-throughput workloads, AWS may auto-scale your ALB behind the scenes; hitting a genuine capacity issue typically manifests as elevated `TargetResponseTime` p99 latency, not a hard cutoff.
• If you approach limits: DNS-weighted routing splits traffic across multiple ALBs (each with its own quota).
• The right way to plan LB capacity is with monitoring dashboards on `RequestCount`, `ActiveConnectionCount`, `NewConnectionCount`, and `ConsumedLCUs` metrics — plus AWS Support engagement well before a ceiling matters.

Practical implication per phase:

The honest takeaway: LB sizing at any tier is dominated by operational blast-radius decisions and AWS quota conversations, not by "hitting an LCU ceiling." Do not derive theoretical LB throughput caps from LCU math and treat them as reality.

Decision Snapshot at 10M RPS

📊 Your dashboard shows at 3 AM on a Tuesday:
- 3 regions each running normal ops
- Aggregate app CPU: 46% — healthy
- MySQL Vitess: 32 shards, average 12% read util, 6% write util
- Redis Cluster: 60 nodes across 3 regions, 60% average util
- CDN hit rate: 70% (normal)
- Shard 17 primary in eu-west-1 CPU: 94% ⚠️
- Shard 17 read QPS: 22,000 (of 25,000 ceiling) ⚠️
- Cache hit rate on Shard 17-owned keys: 8% (rest of the fleet averages 92%)
- All other shards normal
- Traffic on one particular short URL pQr7xY2 in Shard 17's key range: ~500K RPS and climbing

❓ One shard is running hot on READS. What is happening and what do you do?

_{Answer + rationale below.}

✅ Answer: you have a hot KEY problem cascading into a hot SHARD problem — not a shard-key-distribution problem. Distinguish clearly:

• Hot shard would mean the shard function is distributing keys unevenly. Our hash vindex (hash(short_code)) is uniform on the input; there is no way for the shard function itself to send 8× traffic to one shard unless the input distribution is skewed.
• Hot key means one specific short URL is being clicked millions of times per second (a truly viral link — think a president's tweet, a Super Bowl ad QR code, a live-stream announcement URL). Every request for that one key routes to the shard that owns it. That is what we see: pQr7xY2 is receiving 500K RPS by itself, and Redis Cluster's cache for that one key can serve maybe 100K RPS from a single node. Cache misses cascade to MySQL Shard 17, where they saturate the single primary.

Two mitigations, in order of speed:

1. Immediate (this minute): promote pQr7xY2 to CDN edge cache with an aggressive 5-minute TTL. Origin traffic on that key drops to near zero. Shard 17's read pressure returns to normal within minutes.
2. Short-term (this hour): for URL Shortener specifically, promote the top-10K URLs to a local process cache with 1-second TTL on every app box. This is the "hot-key mitigation pattern" — pre-cache aggressively hot keys in every JVM. Cache stampede is limited to 1 refresh per second per box, ~2,700 refreshes per second total, comfortable for MySQL.
3. Long-term (this week): key-level rate limiting for pathological hot keys — if any single short_code receives >100K RPS sustained, apply per-IP-per-key rate limiting to detect actual DoS attempts vs organic viral traffic.

Senior insight — critical distinction: hot-key and hot-shard are different diseases with different treatments. If your shard function is hash-based, sequential IDs from KGS cannot produce shard skew — the hash defeats any input ordering. Do not conflate the two: a bad shard-key choice would make ALL keys concentrate on some shards from Day 1, not just one URL going viral on Tuesday night. The correct engineering response to a hot key is caching at higher tiers, not "restripe the shards."

[🔗 REFERENCE WIDGET · `HotKeyLab`]
> Reader interactively simulates a hot-key event: pick from CDN edge cache, local process cache, request coalescing, key-level rate limiting. Widget shows which mitigation restores healthy origin load and at what recovery time. Explicit hot-key vs hot-shard distinction taught inside the widget.

Security and Observability at Phase 3 (per-phase extensions)

The Phase 2 Security and Observability anchors installed the posture; going multi-region forces two specific extensions.

Security extension — multi-region HMAC secret rotation. Rotating the HMAC key across 3 regions is no longer a single-region operation. The canonical zero-downtime rotation now becomes:

1. T=0: Publish HMAC_KEY_NEW to AWS Secrets Manager in all three regions simultaneously. Verification: HMAC_KEY_PREVIOUS accepted, HMAC_KEY_CURRENT accepted, HMAC_KEY_NEW accepted-but-not-yet-minting.
2. T+15 min: Wait for all app tiers in all regions to pick up the new secret (app-tier secret refresh polls every 5 min in this course; add margin).
3. T+30 min: Flip HMAC_KEY_CURRENT ← HMAC_KEY_NEW globally. Minting now uses the new key.
4. T+90 days: Retire the old key (which is now HMAC_KEY_PREVIOUS).

Do not rotate one region at a time — a request minted in us-east-1 and validated in eu-west-1 during a rolling rotation window would fail HMAC verification. Rotate atomically across regions.

Observability extension — regional dashboards and cross-region tracing. SLOs remain global but each region now gets its own dashboard (per-region availability, per-region P99 latency, per-region shard-primary write latency). Distributed traces must propagate across the region boundary — the app tier sets a traceparent header on the cross-region write when a shard primary is in another region, so a single request's trace shows the cross-region hop and its ~50-150ms cost explicitly. This is the mechanism that lets an SRE tell "was this slow because of code or because we crossed an ocean?"

The Breaking Point — Hot Analytics Writes

Everything works. Latency is great. Availability is high. Then the product team asks a reasonable question:

"How many clicks did short URL abc1234 receive today?"

The naive answer: INSERT into a clicks table on every redirect, then SELECT COUNT(*) when someone asks.

At 10,000 redirects per second across the fleet, that's 10,000 writes per second to MySQL — competing with actual URL creation writes, saturating the write path, and giving us contention where we had none.

We need an asynchronous, high-throughput analytics pipeline.

When to Evolve — the Trigger to Phase 4 (1B RPS)

• Metric 1 (contention): MySQL primary CPU or lock contention when analytics-adjacent queries fire
• Threshold: CPU spikes >20% coincide with dashboard queries, or INFORMATION_SCHEMA.INNODB_LOCK_WAITS shows sustained blocking on rows the redirect path also touches
• Metric 2 (business): the product team asks for click-count analytics you cannot answer in <10 s
• Metric 3 (cost signal): you are running MySQL at 3× the size it needs for redirects, purely to serve dashboards

Phase 4 is not triggered by a raw capacity number. It is triggered by a workload-shape shift: analytics queries are cheap in isolation but expensive when they run against your operational database because they touch a lot of rows, hold locks, and evict useful pages from the InnoDB buffer pool.

[🔗 REFERENCE WIDGET · `BottleneckDetective`]
> Metric snapshot: App CPU 28%, Redis CPU 35%, MySQL CPU 98%, Cache hit rate 91%, p99 780 ms. Reader is asked "What is the primary bottleneck?" — options: (a) app, (b) Redis, (c) MySQL — analytics writes competing with URL creation, (d) network. Correct answer is (c). Senior insight: "Look for coincidence between dashboard queries and CPU spikes — that pattern implicates analytics workload, not core traffic."

The Final Architecture — Phase 3 Snapshot

Before we move to Phase 4, here is the concrete Phase 3 topology in text form. This is the state of the world after 5 architectural evolutions:

```
Route 53 (Geo DNS)
│
┌───────────────────────┼───────────────────────┐
│ │ │
us-east-1 eu-west-1 ap-south-1
│ │ │
CloudFront CloudFront CloudFront
Edge PoPs Edge PoPs Edge PoPs
│ (30% miss) │ │
▼ ▼ ▼
8 × ALB 8 × ALB 8 × ALB
│ │ │
900 × Java Spring Boot 900 × Java Spring Boot 900 × Java Spring Boot
│ │ │
┌───┴───┐ ┌───┴───┐ ┌───┴───┐
▼ ▼ ▼ ▼ ▼ ▼
Redis Vitess Redis Vitess Redis Vitess
Cluster vtgate Cluster vtgate Cluster vtgate
(20 nodes) │ (20 nodes) │ (20 nodes) │
▼ ▼ ▼
┌────────────────────────────────────────────────────────────┐
│ MySQL sharded via Vitess — 32 shards globally, hash vindex │
│ ~11 shards primary in us-east, ~11 in eu-west, ~10 in ap │
│ Each shard: 1 primary + 2 same-region replicas + │
│ 1 cross-region replica = 4 nodes/shard │
│ Global total: 32 × 4 = 128 MySQL instances │
└────────────────────────────────────────────────────────────┘

KGS (2 per region for HA, 6 total) — Redis queue backed by
durable kgs_state MySQL high-water mark
```

Global inventory: 2,700 app boxes (m5.xlarge), 128 MySQL nodes (32 shards × 4), 60 Redis nodes (20 per region), 24 ALBs (8 per region via DNS-weighted routing), 6 KGS instances, CDN globally. ~$600K / month.

What you now understand (Phase 3)

• Why single databases have hard scaling ceilings and how sharding removes them
• Why sharded databases need a coordinated ID generator (and why the KGS pattern is elegant)
• How to derive box counts, database counts, and cache counts from measured RPS rather than by rule of thumb
• Why edge caching is the single most powerful architectural pattern for read-heavy workloads
• Why the NoSQL migration is a trade-off, not an inevitability
• How multi-region architectures are shaped by physics (speed of light) as much as by software

Phase 4 — 1B RPS: Edge Compute Frontier + Async Analytics at Scale

Goal

Capture every click at the edge without slowing the redirect path. Purge expired URLs to reclaim storage. Handle abuse gracefully. Important precision: "capture every click" here means the edge/CDN logging layer records the redirect event for every request served; the durable raw log then feeds a sampled, filtered analytics pipeline. It does NOT mean every click is retained/processed in Kafka/Flink/ClickHouse — the downstream pipeline samples 1-in-100 by design. See the analytics pipeline section for the precise processing model.

The Analytics Pipeline

The redirect path must never wait for the analytics write. The click event is fire-and-forget from the user's perspective.

We introduce Kafka as an asynchronous message queue.

[🎬 ANIMATED DIAGRAM · `phase-4-analytics-pipeline`]
> Canonical 1B analytics flow, not per-click origin writes. Two visually-separated paths:
>
> User-visible redirect path (top row): User → Cloudflare edge Worker → Workers KV lookup → 302 response. Learner can play this path solo — no dependency on any analytics component.
>
> Async analytics path (bottom row): CDN edge logs → durable log delivery (S3/R2) → post-delivery analytics sampling (1% at ingestion, ⚙️ workload assumption) → Kafka → Flink → ClickHouse (historical dashboards) + Redis (real-time counters).
>
> Interactive controls: (a) toggle Analytics ON / OFF — verify the redirect path is unchanged when analytics is disabled; (b) Raw traffic slider (1B events/sec → 10M events/sec after sampling) — Kafka/Flink/ClickHouse pressure indicators respond; (c) Show async separation mode — visually emphasizes that the 302 return does not wait on any downstream analytics component. No autoplay — learner drives the animation. Reduced-motion mode swaps continuous flow animation for step-wise reveal. Component group labels ("Kafka: 144 brokers", "Flink: 1,020 task managers", "ClickHouse: 48 nodes") use representative grouping, not literal per-instance rendering.

Contrast Example — Model 1 (Origin-side Java Analytics), Rejected at Extreme Scale

The Java code below illustrates the Model 1 (origin-side logging) anti-pattern from the analytics 3-way comparison — kept in the course as a teaching contrast, not as the canonical Phase 4 implementation. Every URL Shortener implementation goes through this stage before moving to Model 2 (CDN edge log ingestion) at extreme scale. Understanding what this code does — and why it doesn't scale — is important for understanding why the canonical Phase 4 architecture routes analytics through CDN edge logs instead.

java
// ⚠️  MODEL 1 — ORIGIN-SIDE ANALYTICS
// This is REJECTED as the canonical Phase 4 implementation because at 1B RPS
// it forces every redirect through origin infrastructure, defeating the CDN.
// It is included here as a teaching contrast, NOT as production Phase 4 code.
//
// Canonical Phase 4 architecture (Model 2) captures analytics from CDN edge logs,
// not from per-request origin code — see "The Analytics Pipeline" section above.

@Service
public class ClickTrackingService {

    private final KafkaTemplate<String, ClickEvent> kafka;

    @Async
    public void recordClick(String shortCode, String userIp, String userAgent) {
        ClickEvent event = new ClickEvent(
            shortCode, userIp, userAgent, Instant.now());
        kafka.send("clicks", shortCode, event);
    }
}

Under Model 1, @Async runs the tracking on a separate thread pool so the redirect doesn't wait on Kafka. If Kafka is briefly unreachable, analytics events are dropped — a design decision that trades analytics completeness for redirect availability. This pattern works fine up through ~100K RPS. Above that, forcing every redirect through origin (to run this Java code) means edge caching can no longer serve the majority of traffic — which is the whole point of the CDN at extreme scale. The canonical Phase 4 architecture instead lets the CDN handle redirects at edge and captures analytics from the CDN's own request logs (Model 2), decoupling analytics from the origin request path entirely.

The Flink Aggregator

Flink is a stream processor. It reads from Kafka, aggregates click counts in tumbling windows (1-minute, 1-hour, 1-day) by short_code, and writes results to two destinations:

• ClickHouse — columnar analytics database. Fast at "count clicks between date X and Y grouped by country." Powers dashboards, deep dives, per-day counts.
• Redis — real-time counters. Powers "1,247 clicks so far today" widgets.

Because Flink processes events in windows and uses checkpointing, we get exactly-once processing semantics inside Flink — but that is a narrower guarantee than most engineers assume. Let us be precise.

Exactly-Once Processing vs Exactly-Once Effects

Three delivery models, in ascending order of guarantee:

• At-most-once — the event may be lost. Never duplicated. (Fire-and-forget UDP.)
• At-least-once — the event is never lost. May be duplicated. (Kafka default consumer, TCP with retransmit.)
• Exactly-once — the event arrives exactly once. Never lost, never duplicated. (Requires coordination.)

Flink's checkpointing gives you exactly-once processing inside Flink. Meaning: Flink's own state (windowed counts, running aggregates) reflects each click exactly once, even if Flink crashes and restarts mid-window. Great.

But exactly-once processing ≠ exactly-once effects at the sink. Consider this timeline:

```
1. Flink task reads click event from Kafka partition offset 42
2. Flink windows the event, produces "shortcode:abc1234 count += 1"
3. Flink task starts writing to ClickHouse
4. Flink task CRASHES before committing its checkpoint (offset 42)
5. Flink task restarts, reads the SAME offset 42 from Kafka
6. Flink writes to ClickHouse AGAIN
7. Result: click counted twice in ClickHouse
```

The Kafka read + Flink processing was exactly-once — offset 42 gets processed to completion in Flink's checkpointed state. But the ClickHouse sink saw the write twice.

To get exactly-once effects at the sink, one of three things must hold:

1. The sink is idempotent — writing the same row twice produces the same result. For a click counter, INSERT (shortcode, hour, +1) is NOT idempotent; UPSERT (shortcode, hour, count = latest) IS idempotent if the value is a rolling sum keyed on (shortcode, hour, source-offset).
2. The sink participates in a distributed transaction with Flink — Flink's checkpoint commit and the sink's write are two-phase-committed. ClickHouse does not support this. Kafka does (Kafka → Kafka pipelines can be exactly-once end-to-end).
3. You accept "effectively-once" — a small probability of duplication, deduplicated downstream by an idempotency key or dedup window.

For our URL Shortener analytics, we pick option 3 with a specific mitigation: attach (kafka_partition, offset) as an idempotency key on every ClickHouse insert. Implementation note (verify against your ClickHouse version): ClickHouse's ReplacingMergeTree table engine deduplicates rows with the same sort key during background merges — not synchronously at insert time. This gives eventually-idempotent effects, not immediate deduplication. For strict deduplication on read you use SELECT ... FINAL (higher cost) or the deduplicate_blocks_in_dependent_materialized_views setting for materialized views. Verify the exact semantics for your ClickHouse version and table engine choice before relying on this — do not assume "attach a key = exactly-once" without validating that your chosen engine actually enforces uniqueness on your access pattern.

At this level of pedagogy: total effect is eventually-consistent exactly-once at the click-count level for aggregate reads, at the cost of one extra column in ClickHouse and background-merge latency. This is close to but not equivalent to true exactly-once at every read.

What we do NOT claim:

• We do NOT claim "checkpointing means no double counting." That is wrong; see the timeline above.
• We do NOT claim "exactly-once semantics" without qualifying the sink behavior.

What we DO claim:

• Flink gives us exactly-once processing within its own state.
• Effects on ClickHouse are exactly-once only because we added an idempotency-key column.
• A duplicate click event in Kafka (which is possible if the emitting app retries a failed send) would be counted once, because our idempotency key catches it.

For an interactive teaching moment, imagine the same click event fires 3 times. Reader predicts: at-most-once = 0-3 counted, at-least-once = 3-∞ counted, exactly-once-processing = 1 counted internally but potentially duplicated at sink, exactly-once effects = exactly 1 counted at the sink. Only the last is what we want.

Data Purging

URL Shorteners often let users set expiry (e.g., "expire this link in 30 days"). We need a background process to purge expired URLs and reclaim storage.

java
@Scheduled(cron = "0 0 3 * * *")
@SchedulerLock(name = "purgeExpiredUrls",
               lockAtMostFor = "PT1H",
               lockAtLeastFor = "PT30M")
public void purgeExpired() {
    LocalDateTime cutoff = LocalDateTime.now();
    int batchSize = 10_000;

    while (true) {
        List<UrlEntity> expired = repo.findExpiredBatch(cutoff, batchSize);
        if (expired.isEmpty()) break;

        repo.deleteAll(expired);

        try (Jedis jedis = jedisPool.getResource()) {
            expired.forEach(e -> jedis.del(e.getShortCode()));
        }
    }
}

We batch and process in chunks to avoid holding locks or exhausting memory.

Runs daily at 3 AM, when redirect traffic is at its lowest and MySQL has spare I/O capacity for the writes.

@Scheduled in a fleet — why the naive version breaks

Look at that @Scheduled annotation again. If you deployed it as-is on a single-instance service, it fires once per day. Fine.

But we are Phase 3 — we run 900 Spring Boot instances per region × 3 regions = 2,700 boxes across the fleet. All of them boot from the same JAR. All of them have the same @Scheduled(cron = "0 0 3 * * *") annotation. All of them wake up at exactly 3 AM local time and start deleting expired rows.

That's 24 concurrent purge jobs hammering MySQL simultaneously — the exact opposite of "when MySQL has spare capacity." Each one runs the same SELECT ... WHERE expires_at < NOW() LIMIT 10000 query, they all grab overlapping rows, they all try to DELETE the same rows, MySQL locks contend, dead rows are deleted 24 times, half the jobs error out with lock timeouts, and your 3 AM shows up as a P0 page.

This is a distributed cron problem, and it has two clean solutions:

Solution A — ShedLock (annotation-based distributed lock).

Add the @SchedulerLock annotation shown above and configure ShedLock with a Redis or JDBC LockProvider:

java
@Configuration
@EnableScheduling
@EnableSchedulerLock(defaultLockAtMostFor = "PT1H")
public class SchedulingConfig {

    @Bean
    public LockProvider lockProvider(DataSource dataSource) {
        return new JdbcTemplateLockProvider(
            JdbcTemplateLockProvider.Configuration.builder()
                .withJdbcTemplate(new JdbcTemplate(dataSource))
                .usingDbTime()
                .build());
    }
}

-- MySQL side (one-time DDL)
CREATE TABLE shedlock (
    name       VARCHAR(64) PRIMARY KEY,
    lock_until TIMESTAMP(3) NOT NULL,
    locked_at  TIMESTAMP(3) NOT NULL,
    locked_by  VARCHAR(255) NOT NULL
);

At 3 AM, all 24 instances wake up and race to insert-or-update a row in the shedlock table with name = 'purgeExpiredUrls'. Only one succeeds. The other 23 see the lock is held and immediately skip. When the winner finishes, lockAtLeastFor = 30m prevents any other instance from running the job for another 30 minutes (defense against clock skew across the fleet).

Solution B — Kubernetes CronJob (external scheduler).

Move the purge logic out of the app entirely and into a dedicated Kubernetes CronJob that runs a small purger container as a single replica. The app tier stops containing the @Scheduled annotation at all:

yaml
apiVersion: batch/v1
kind: CronJob
metadata:
  name: url-purger
spec:
  schedule: "0 3 * * *"
  concurrencyPolicy: Forbid    # never run two purgers at once
  successfulJobsHistoryLimit: 3
  failedJobsHistoryLimit: 3
  jobTemplate:
    spec:
      template:
        spec:
          containers:
          - name: purger
            image: our-registry/url-purger:1.2.3
          restartPolicy: OnFailure

concurrencyPolicy: Forbid is the load-bearing line. Kubernetes will refuse to launch a second purger pod if yesterday's is still running. No lock table needed; the scheduler enforces mutual exclusion.

Which do we pick? ShedLock is simpler to introduce — it's an annotation change and one config bean, no new deployment surface. Kubernetes CronJob is cleaner architecturally — batch jobs deserve their own lifecycle, their own CPU budget, their own alerts, separate from user-facing request traffic.

We use Kubernetes CronJob for anything that runs longer than 5 minutes (purge, backup verification, warm-up scripts, expiry compaction) and ShedLock for anything shorter than 5 minutes (cache warm-up, metrics rollup). Both patterns coexist happily.

Capacity & Sizing at Phase 4 (1B RPS)

At 1 billion requests per second, edge compute becomes mandatory. No practical origin infrastructure can absorb 1B RPS — nor should it try. The architecture shifts fundamentally: the origin becomes a control plane, and the data plane lives at the CDN edge.

Traffic:
- 1,000,000,000 RPS average globally = ~86 trillion redirects / day
- This is aspirational. No real URL Shortener runs at this scale today. We teach it because the architectural lessons matter for any read-heavy service near the frontier of possibility.

Traffic Composition — Being Precise about Writes vs Redirects

Earlier drafts of this course carried a contradiction that this correction pass resolves explicitly. Please distinguish these two traffic streams as independent workload variables:

⚙️ WORKLOAD ASSUMPTIONS (for this course's illustrative 1B RPS scenario):

Do NOT force a "1% write ratio" mechanically from earlier tiers. The 99:1 read/write ratio at Phase 1 was appropriate for a small startup where each user creates ~1 URL and clicks their own + friends' URLs. At 1B RPS the reads are dominated by viral consumption, not by user creations. Write rate is a product-usage variable, not a fraction of read rate.

The architectural pivot: Edge Compute.

Instead of the redirect logic running on Spring Boot in a region, we deploy it as Cloudflare Workers running at 300+ edge PoPs. The redirect never touches origin under normal operation.

Coding Convention — Origin is Java, Edge is Provider-Native

This course's stated convention is: origin/backend code = Java + Spring Boot 3. That convention cannot mechanically extend to edge functions — Cloudflare Workers do not run JVM bytecode. Extending the convention would either force us to invent a fictional runtime or lie about what deploys where.

We resolve this explicitly:

• Origin/backend code: Java + Spring Boot 3 — as before
• Edge function code: JavaScript / TypeScript (Cloudflare Workers' native runtime) — because that is what actually runs at the edge

Below is the actual edge function — fenced as JavaScript, honestly:

javascript
// Cloudflare Worker (deployed globally to 300+ PoPs)
// Language: JavaScript (edge runtime); NOT Java despite the origin convention
// Canonical responsibility: KV lookup → 302. Analytics is NOT written here per-click.
export default {
  async fetch(request, env, ctx) {
    const shortCode = new URL(request.url).pathname.slice(1);

    // 1. Edge KV lookup (Cloudflare Workers KV — durable, eventually consistent)
    const longUrl = await env.URL_MAP.get(shortCode);
    if (!longUrl) {
      // Fall through to origin for cache-miss lookup (URL was created recently
      // and hasn't propagated to this PoP yet, or has been evicted)
      return fetch(`https://origin.sho.rt/${shortCode}`);
    }

    // 2. Analytics is captured via Cloudflare's built-in edge logging (Model 2),
    //    NOT via per-click KV writes. Cloudflare's Logpush + our S3/R2 bucket +
    //    a batch Lambda ships the request log to Kafka. This means:
    //    - Zero per-click KV writes (KV writes/sec/key are constrained at 1 anyway)
    //    - Analytics latency is 1-5 min (acceptable — nobody needs per-second precision)
    //    - Origin sees near-zero analytics load

    return Response.redirect(longUrl, 302);
  }
};

Why Cloudflare Workers (primary), not CloudFront Functions?

We choose Cloudflare Workers as the primary for this course because: (a) the 1 ms CPU cap on CloudFront Functions is too tight for our KV lookup + analytics fire pattern, (b) Workers KV is more feature-rich for the URL map use case (bulk write, longer TTLs), (c) Cloudflare's operational maturity for global edge deployments is well documented.

Multi-CDN reality check: in practice at 1B RPS you deploy on BOTH Cloudflare Workers AND CloudFront (or Fastly Compute@Edge) for vendor redundancy. The primary vs alternate designation is about "which is default DNS routing" not "we only deploy on one." One possible traffic split is 90/10 during a controlled migration or resilience test with instant flip capability during a vendor outage — the exact ratio is a design decision, not a universal recipe.

The design targets low single-digit / sub-10 ms edge execution time because the Worker runs at a PoP typically within ~30 ms network round-trip of most user locations. End-to-end user-perceived latency depends on PoP distance, network conditions, KV lookup performance, and workload — the sub-10-ms target refers to the code execution portion, not the full end-to-end path.

What runs at origin now.

The origin still runs Java Spring Boot + Redis Cluster + Vitess-sharded MySQL + KGS, but the ORIGIN FLEET AT 1B RPS IS LARGER than at 10M RPS because origin traffic (post-99%-edge-hit) is larger than Phase 3's origin traffic (post-70%-CDN-hit).

Origin traffic derivation at 1B RPS:

App tier per region — Java Spring Boot m5.xlarge (~2,400 RPS/box, ⚙️ workload-dependent):

1. Steady-state throughput: 3.33M / 2,400 = ~1,389 boxes
2. Peak throughput: 6.67M / 2,400 = ~2,778 boxes
3. Peak throughput surviving 1-AZ failure (need 1.5× peak so surviving 2 AZs handle peak): 2,778 × 1.5 = ~4,167 boxes
4. Rounding for 3-AZ balance: ~4,200 boxes per region (1,400 per AZ)
5. Global app fleet at 1B RPS: 4,200 × 3 = ~12,600 boxes (⚠️ MUCH larger than Phase 3's 2,700 boxes — the higher edge hit rate reduces origin RPS × 3 vs Phase 3, but the underlying redirect volume is 100× larger, so origin traffic is still 3.3× Phase 3's origin traffic, requiring a proportionally larger fleet)

MySQL Vitess (32 shards, unchanged from Phase 3):
- Reads at origin: 3.33M/region × 99% × (1 - 0.9 Redis hit) = ~330K read QPS to MySQL per region
- Across 32 shards globally, most sharded reads route to same-region primary + replicas: ~10K read QPS per shard = ~40% utilization (⚙️ headroom exists)
- Writes: 100K/sec globally ÷ 32 shards ≈ 3,125 writes/sec/shard = ~30-60% of the per-shard write ceiling (still within limits, requires monitoring)
- Same 128 MySQL nodes as Phase 3 — sharding was sized for growth and 32 shards remains appropriate

Redis Cluster per region:
- Redis absorbs the 90% cache-hit majority of origin reads: 3.33M × 99% × 90% = ~3.0M GET/sec per region, plus ~330K SETEX/sec from cache-miss population = ~3.3M ops/sec per region
- 📗 Published redis.io benchmarks suggest ⚙️ ~100K ops/sec per cache.r6i.large node as an approximate reference for simple workloads. Do NOT size at 100% of this reference in production — benchmark ceilings and safe operating points are different things.
- ⚙️ Target production utilization: 60% of the modeled per-node reference = 60K effective ops/sec per node (leaves headroom for CPU spikes, GC-like pauses, network jitter, and command-mix variance)
- 🧮 Nodes needed per region: 3.3M ÷ 60K = ~55 primary shards per region
- With 1 replica per shard for HA: ~55 primaries + ~55 replicas = ~110 Redis nodes per region
- Global Redis: ~330 nodes globally (~110 per region × 3 regions) — significantly larger than Phase 3's 60 nodes because origin traffic is 3.3× larger AND we're sizing at 60% target utilization rather than the nominal benchmark ceiling. The pedagogical point: benchmark ceiling ≠ safe production operating point; teach the discipline of leaving explicit headroom.

KGS:
- 100K writes/sec globally ÷ 3 regions = ~33K IDs/sec per region
- Well within KGS 📐 illustrative ceiling (~200-500K/instance)
- Same 6 KGS instances (2 per region) as Phase 3

ALBs:
- Modeled LCU consumption at 6.67M peak RPS/region: 6.67M × 2 LCU/10K = ~1,334 LCU/region (⚙️ workload assumption — LCU is a billing dimension, not a hard throughput cap)
- Practical ALB count per region is an operational decision driven by workload testing, quota planning, and blast-radius policy (typically ~15-20 ALBs per region at this tier). Do not compute a false-precision global total; the exact number depends on account quotas and load-testing outcomes.

Edge KV capacity model:
- URLs stored at edge: only the "hot tail" (say, top 10 million URLs by recent click count). Long-tail URLs live only in origin MySQL.
- Edge KV size: 10M URLs × 200 bytes = 2 GB per PoP. Cheap.
- Edge KV read RPS: 1B RPS × 99% hit = 990M reads/sec globally. Cloudflare Workers KV paid-tier documented policy is "Unlimited reads" (📗 VERIFIED DOC — Cloudflare KV Limits page, retrieved this session). However, "Unlimited" in vendor pricing language is not the same as guaranteed per-PoP throughput; real per-PoP capacity is 🧮 DERIVED CALCULATION based on our chosen distribution model (990M ÷ ~300 PoPs = ~3.3M/PoP average) — actual capacity requires load testing and must be validated per production workload.
- Important constraint (📗 VERIFIED DOC): Cloudflare Workers KV enforces at most 1 write per second per key. For URL Shortener this is fine because URLs are immutable once created; if you use KV for anything mutable (view counters, edit-in-place), this rules out synchronous per-write invalidation.
- KV is eventually consistent (📗 VERIFIED DOC). After a write, propagation to all PoPs takes up to ~60 seconds. First-time reads of a brand-new URL may miss at edge and fall through to origin during this propagation window.

Origin sees now (using the workload assumptions above):
- Redirect miss traffic to origin: 10M RPS globally (🧮 = 1B × 1% edge miss)
- URL creation writes: 100K RPS globally (⚙️ workload assumption; distributed across 32 shards ≈ 3,125 writes/sec/shard, within per-shard write ceiling)
- Analytics writes at origin: 10M events/sec globally (🧮 = 1B × 1% post-delivery analytics sampling; goes to Kafka, NOT MySQL)

Additional origin roles:

1. Edge KV population. After every URL creation, origin publishes to Cloudflare Workers KV. Propagation to all edge PoPs takes 30-60 seconds. First-time reads of a brand-new URL may fall through to origin during this window.
2. Cache-miss fallback. If edge KV is missing an entry (URL creation lag, evicted for space), edge falls through to origin's Redis Cluster.
3. Analytics ingestion. Origin collects the edge log stream (see Model 2 in the analytics 3-way comparison above) and pipes through Kafka → Flink → ClickHouse.

Analytics at 1B RPS:
- 1B events/sec raw is beyond Kafka's practical throughput on any single cluster
- Sampling at the analytics ingestion layer — the canonical pipeline samples 1-in-100 events after CDN edge logs are durably delivered (see Model 2 canonical flow above). Standardized term: "post-delivery analytics sampling: 1%" (sampling happens after durable log delivery, not inside the Cloudflare Worker). ⚙️ WORKLOAD ASSUMPTION: 1% sampling reduces analytics data volume by 100×. Statistical accuracy of aggregate counts is not simply a function of sampling rate — it depends on the estimator (e.g., simple aggregation vs Horvitz-Thompson), sample size within the measurement window, variance of the metric being estimated, and the tolerable error bound. For high-volume aggregate counts (e.g., "total clicks last hour"), a 1% sample yields tight relative error because the effective sample size per URL is still large; for tail-count metrics (e.g., "clicks on URL X in the last minute" for rarely-clicked URLs), the error can be substantial. Do not present sampling rate as a substitute for statistical confidence — model your estimator and quantify error explicitly. (Non-canonical optimization: sampling could alternatively be implemented at the Worker layer to reduce log-delivery volume; this is cheaper in log egress but LOSES the unsampled durable record — you cannot re-sample or reprocess events later. Only choose this if egress cost dominates and reprocessing is not a requirement.)
- Aggregation at edge (optional optimization) — Cloudflare Workers can pre-aggregate clicks in local memory over 1-second windows before forwarding to Kafka. Reduces event volume another 10-100× depending on hot-key concentration. ⚙️ WORKLOAD ASSUMPTION: this course models WITHOUT edge aggregation (simpler pedagogy); real production deployments should measure whether aggregation is worth the code complexity.
- Regional Kafka clusters — each region has its own Kafka (see analytics tier sizing below), MirrorMaker replicates aggregate results (not raw events) to a global cluster for cross-region analytics.

Multi-CDN for resilience.

At this scale, being locked to a single CDN vendor is a business-risk P0. We deploy on both CloudFront + Cloudflare with DNS-weighted routing between them. If Cloudflare has a global outage (rare but not unprecedented — see July 2019), CloudFront serves. RTO for CDN failover: 5-10 minutes for DNS propagation.

Cost model at 1B RPS — 📐 ILLUSTRATIVE COST-DRIVER MODEL, NOT A PRODUCTION ESTIMATE

An earlier draft of this course multiplied 1B RPS by simplified public list pricing to produce a ~$25M-42M / month total. That number was not defensible: at this scale, negotiated CDN contracts, committed bandwidth tiers, regional traffic distribution, edge execution pricing, and multi-CDN duplication dominate the economics. Exact production cost at 1B RPS cannot be responsibly estimated from simplified public list pricing.

Instead of a fake precise total, we teach the cost drivers — the categories a real production team must model against negotiated pricing:

Rule of thumb (⚙️ workload-dependent): at 1B RPS, expect CDN + bandwidth to be the majority of total infrastructure spend by a factor of ~10× over origin infrastructure. Your specific mix depends on your contract terms — a company with a favorable multi-year CloudFront commit will see very different economics than a spot-pricing deployment.

Do not use this course's tables to build a production budget. Use them to identify which cost drivers to negotiate hardest with your vendors.

Order of magnitude for unit economics: URL Shortener per-redirect cost at extreme scale is a small number of tenths of a cent per thousand redirects, dominated by the CDN line. The absolute monthly total for a legitimate 1B RPS service is measured in tens of millions of dollars per month — but that's an outcome of negotiations, not a spreadsheet formula on public list pricing.

Where the bottleneck lives at 1B RPS.

• ❌ NOT origin infrastructure — edge compute absorbs 99% of the redirect volume
• ❌ NOT MySQL — reduced to handling URL creation writes; 100,000 writes/sec globally sharded 32 ways = ~3,125 writes/sec/shard, within the per-shard write reference range (⚙️ workload-dependent)
• ❌ NOT bandwidth — a URL redirect response is ~200 bytes; total bandwidth is meaningful but not the primary throughput constraint
• ✅ CDN cost — CDNs are the single biggest cost line and negotiated pricing dominates
• ✅ Global routing complexity — Route 53 → Cloudflare (primary) + CloudFront (alternate) + regional origins with health-check based failover
• ✅ Analytics pipeline sizing — 10M sampled events/sec (from 1B raw × 1% post-delivery analytics sampling) is where "just add another Kafka broker" stops working; you need proper stream architecture
• ✅ Organizational complexity — teams to run CDN configs, edge deploys, edge KV synchronization, multi-CDN traffic engineering. This is what changes at 1B RPS: the challenge stops being technical and becomes organizational.

Decision Snapshot at 1B RPS

📊 Your on-call SEV1 pager fires:
- CloudFront edge health: DEGRADED across 40% of PoPs globally ⚠️
- Cloudflare edge health: HEALTHY
- Origin dashboards: all green (behind edge, no traffic reaches us)
- User-visible p50 latency for affected regions: from 25 ms → 380 ms ⚠️
- User-visible availability from affected regions: from 99.99% → 96.2% ⚠️⚠️
- Twitter shows customer complaints starting to trend

❓ Half your CDN is broken. Origin is fine. What do you do in the next 5 minutes?

_{Answer + rationale below.}

✅ Answer: shift traffic to Cloudflare via Route53 DNS-weighted routing update. Do NOT try to fix CloudFront — that is AWS's problem, not yours. Your job at 1B RPS is not to fix vendor infrastructure; it is to route around it. Change your Route53 weighted policy from 50% CF / 50% Cloudflare to 10% CF / 90% Cloudflare (keep a small CF fraction to detect CF's recovery). DNS TTL is 60 seconds so change propagates in about 2 minutes globally. Then page AWS support to file the incident, but do not block on their response.

Senior insight: at extreme scale, your business's availability is decoupled from any single vendor's availability by design. Multi-CDN is a resilience/business-continuity consideration whose value depends on your specific vendor outage history, contractual SLA, traffic volume, failover complexity, cost, DNS-behavior expertise, and operational maturity. The specific RPS threshold at which multi-CDN is worth its added complexity is not universal — the decision is business-driven. What IS universal: the operational muscle of knowing which lever to pull, in what order, without hesitation. Every senior engineer at this scale should have practiced this exact drill in staging with fault injection. If you have not practiced it, your first real vendor outage will be your first attempt.

[🔗 REFERENCE WIDGET · `FailureLab`]
> Reader picks from failure scenarios including the "one CDN vendor degrades" case. Widget shows the DNS-shift timeline, user impact curve, revenue impact estimate, and RTO.

We add analytics on top of the Phase 3 baseline. Only the analytics pipeline needs new hardware; Phase 3's app / DB / cache / LB tier is unchanged.

Analytics traffic:
- Every redirect emits 1 Kafka event (before sampling)
- Peak globally: 1B RPS at Phase 4 → 1 billion events/sec raw — beyond any practical single Kafka cluster
- We sample 1-in-100 at the analytics ingestion layer (after CDN edge logs are durably delivered — see Model 2 canonical flow) before publishing to Kafka → 10M events/sec globally, ~3.3M events/sec per region
- Note: analytics traffic tracks total redirects, not post-CDN — because even edge-served requests should log a click somewhere. How the edge tells the origin about a served click is a real design question — three viable models, each with a different trade-off:

Model 1 — Origin-side logging (what most first drafts do).

Every redirect passes through the origin app (CDN cache is bypassed for tracking). The redirect app writes a Kafka event before returning the 302.

text
User → CDN (miss on purpose) → Origin → Kafka → 302

• ✅ Accuracy: every click counted, no sampling
• ✅ Simple to implement
• ❌ Kills the CDN benefit — origin RPS = total RPS
• ❌ Origin becomes the bottleneck at any real scale

Model 2 — Edge log ingest (what most real production systems do).

CDN serves the redirect from the edge cache. CDN logs the request (CloudFront, Cloudflare, Fastly all support this). A batch job periodically ships the CDN logs to Kafka.

text
User → CDN edge → 302  (fast path, no origin)
CDN logs → S3 / R2 → periodic Lambda → Kafka

• ✅ Origin sees near-zero traffic
• ✅ Captures CDN-observed requests without relying on browser-side telemetry; completeness depends on CDN logging configuration, delivery reliability, retention, and ingestion health.
• ⚠️ Latency: analytics lags real time by 1-5 minutes (CDN log delivery is batched)
• ⚠️ Cost: log egress + processing pipeline
• ⚠️ Requires trusting CDN's logging correctness

Model 3 — Client-side beacon.

CDN serves the redirect. Downstream browser (after the redirect completes) fires a small POST /analytics beacon to a separate analytics endpoint.

text
User → CDN → 302  → Browser follows redirect  → Browser sends beacon → Analytics API

• ✅ Origin sees only beacon traffic (10-100 bytes each, cache-bypass)
• ⚠️ Accuracy: ~15-40% of clicks are lost to ad blockers, browsers with tracking-prevention, users navigating away before beacon fires
• ⚠️ Privacy/GDPR: browser beacons are often blocked or require consent
• ✅ Real-time (beacon arrives within seconds, not minutes)

Which we pick for this course.

We pick Model 2 (edge log ingest) as the primary model. Rationale:
- Captures CDN-observed requests without relying on browser-side telemetry (no ad-blocker attrition, no origin bottleneck); completeness depends on CDN logging configuration, delivery reliability, retention, and ingestion health
- The 1-5 min latency is acceptable for URL Shortener analytics (nobody needs per-second click counts)
- The pipeline (CDN → S3 → Lambda → Kafka) is a widely-used pattern for high-volume event pipelines

We add Model 3 as a secondary signal for real-time dashboards ("live clicks right now" widgets), acknowledging its accuracy limitations. Products where "1,247 people are clicking this right now" is a feature accept ad-blocker attrition as the price.

We reject Model 1 for anything above 100K RPS — it defeats the purpose of the CDN.

Analytics Pipeline Sizing at 1B RPS

Total click events: 1B RPS = 1B events/second raw. Beyond Kafka's practical throughput on any single cluster.

Sampling at the analytics ingestion layer: the canonical Model 2 pipeline (CDN edge logs → durable delivery → sampling/filtering) samples 1-in-100 after log delivery, giving ~10M events/sec into Kafka. ⚙️ WORKLOAD ASSUMPTION: sampling reduces event volume 100×. Accuracy depends on the target estimator — for the "total clicks per URL per hour" query in a heavy-tailed URL distribution, error is tight for hot URLs and looser for long-tail URLs. Model the error explicitly for your specific analytics query; do not conflate sampling rate with statistical confidence. (Alternative implementation: sampling could be moved to the Worker layer as an optimization to reduce log-delivery cost, at the price of losing the ability to re-sample from raw logs later.)

Kafka per region:
- Broker ceiling: ~50-100K messages/sec per kafka.m5.large broker (📊 PUBLISHED BENCHMARK)
- Peak load per region (post-sampling): 10M / 3 regions ≈ 3.3M events/sec per region
- Brokers needed per region: 3.3M / 75K/broker (mid-range assumption) = ~44 brokers, round to 48 brokers per region for headroom + replication factor 3 quorum
- Deployment: 48 brokers per region × 3 regions = 144 brokers globally
- Topic clicks: 96 partitions per region (2× broker count for consumer parallelism), replication factor 3

Flink per region:
- Task manager ceiling: ~10K events/sec per task manager (⚙️ WORKLOAD-DEPENDENT — simple windowed counts)
- Peak load per region: 3.3M events/sec → 330 task managers per region
- With HA + job manager: 340 Flink instances per region × 3 regions = 1,020 Flink instances
- Consider bigger instances (m5.2xlarge → ~40K events/sec/task) to reduce count by 4×

ClickHouse — centralized cluster:
- Insert rate globally: 10M events/sec (after aggregation to per-shortcode-per-minute rolls, effective insert rate ~5M rows/sec)
- ClickHouse insert ceiling per node: ~100-200K rows/sec (⚙️ WORKLOAD-DEPENDENT ESTIMATE — columnar bulk-insert numbers vary heavily by schema, table engine, batch size, and hardware; not independently verified against ClickHouse docs in this course)
- Nodes needed: 5M / 150K = ~33 nodes; round to 48-node cluster for HA + query capacity headroom
- Storage: 10M events/sec × 200 bytes × 86,400 sec/day = ~170 TB / day raw; with columnar compression (~10:1) and 90-day retention: ~1.5 PB total

Note: analytics cost is small compared to CDN + edge cost at 1B RPS. See the Cost Model at 1B RPS section for the full driver-by-driver picture and the honest caveat about not treating list-price arithmetic as a production budget.

[🔗 REFERENCE WIDGET · `SystemSizingDiagram`]
> Move the slider to 1B RPS + toggle analytics ON. Reader sees the Phase 4 (edge-first) topology overlay: Kafka, Flink, ClickHouse appearing in the sidebar. Cost line at the bottom reflects the illustrative extreme-scale model. Each component's ceiling panel now includes analytics load in its utilization number.

[🔗 REFERENCE WIDGET · `FailureLab`]
> Six failure scenarios: (1) one Redis Cluster node crashes, (2) one MySQL shard primary fails, (3) Kafka broker dies, (4) one whole region goes offline, (5) cache stampede on the viral URL, (6) CDN misconfiguration flushes cache globally. Reader picks the recovery strategy for each and sees the resulting p99 impact + data loss / recovery time.

[🔗 REFERENCE WIDGET · `AntiPatternsShowcase`]
> 10 anti-patterns compiled with "Why people choose it / Why it's wrong / When it becomes appropriate." Highlights for Phase 4: "Analytics on the hot path" (why we introduced Kafka), "Global synchronous writes" (why we shard), "NoSQL from day 1" (why we stayed with MySQL until forced), "Cache TTL of forever" (why we set 3600s).

Handling Abuse

At scale, abuse is inevitable:

• Phishing links. Someone shortens https://malicious.example.com/steal-your-password and shares it. Downstream we get abuse reports.
• Rate-limiting abuse. A single IP creates 100,000 short URLs per hour, either to spam or to enumerate.
• DDoS on the redirect path. Attackers hammer a specific short URL to exhaust our cache and back-end.

The Final Architecture at 1B RPS (Canonical)

Here is the canonical architecture at the 1B RPS scale level — every number in this section MUST match the derivations shown above in the Phase 4 Capacity section. If you find a conflict elsewhere in the course, this canonical block wins.

• Ingress (primary) — Route 53 DNS → Cloudflare Workers + Workers KV at 300+ edge PoPs (serves 99% of redirect traffic without touching origin)
• Ingress (secondary, multi-CDN resilience) — CloudFront Functions as alternate DNS-weighted destination (~10% by default; can flip to primary during Cloudflare outage)
• Origin ingress (on 1% cache miss) — Route 53 → per-region ALBs (~15-20 per region; the exact count is an operational decision based on workload testing, quota planning, routing design, and blast-radius policy) → Spring Boot cluster
• Origin application — Java Spring Boot 3, ~4,200 instances per region × 3 regions = ~12,600 app boxes (sized to survive 1-AZ failure at 6.67M RPS peak per region)
• Cache — Redis Cluster per region, ~55 shards + ~55 replicas × 3 regions = ~330 nodes globally (sized at 60% of the ⚙️ workload-dependent per-node reference to leave production headroom; benchmark ceiling ≠ safe operating point)
• Database — MySQL sharded via Vitess, 32 shards globally (hash vindex on short_code), 1 primary + 2 same-region replicas + 1 cross-region replica per shard = 128 nodes globally
• ID generation — Java KGS + Redis queue backed by durable kgs_state MySQL high-water mark, 2 instances per region × 3 = 6 KGS instances
• Analytics — Edge log ingest (Model 2 in the 3-way comparison above) → durable log delivery → post-delivery analytics sampling (1%) → per-region Kafka clusters (~48 brokers per region × 3 = ~144 brokers globally) → Flink stream processor (~340 task managers per region × 3 = ~1,020 instances globally) with idempotency-key inserts → 48-node ClickHouse cluster + Redis real-time counters
• Purging — Kubernetes CronJob (single replica, concurrencyPolicy: Forbid) at 3 AM UTC per region
• Abuse defenses — Safe Browsing integration (📗 verify availability + licensing before adopting) + per-IP rate limits (⚙️ illustrative policy — production limits should reflect your abuse-signal maturity) + multi-CDN edge caching

Approximate scale at this configuration:

• 1 billion RPS globally = 🧮 ~86.4 trillion redirects / day (1B × 86,400)
• Origin sees ~10M RPS globally after 99% edge cache hit = 🧮 3.33M RPS per region avg (10M ÷ 3)
• URL creation rate: 100,000 writes/sec globally = 🧮 ~8.64 billion new URLs/day (⚙️ ILLUSTRATIVE workload assumption — an explicit independent workload variable, NOT a percentage of read traffic)
• Analytics event volume after post-delivery sampling: 10M events/sec globally = 🧮 1B × 1%
• Approximate storage growth per day — analytics dominates. Distinguish the storage layers explicitly:
• Cost estimate: see the Cost Model at 1B RPS section above — this is a 📐 ILLUSTRATIVE COST-DRIVER MODEL, not a production estimate.

Failure model at 1B RPS:

• Cloudflare edge outage — DNS-shift traffic to CloudFront alternate. For existing replicated URL mappings (which are in Workers KV and mirrored to the alternate CDN's KV in advance), RPO is near-zero and RTO ≈ DNS TTL + propagation (typically 2-10 min, workload-dependent). For newly created mappings that were still propagating to alternate-CDN KV at the moment of outage (KV is eventually consistent, ~60s propagation window per verified Cloudflare docs), redirects may be temporarily stale or unavailable at the alternate edge and fall through to origin. Analytics events during the outage may be lost from the primary edge's log pipeline, though origin-side beacon fallback (Model 3) can partially compensate.
• One MySQL shard primary loss — see the shard failure discussion earlier; user-visible impact confined to that shard's data during ~30-60s Vitess failover; the topology's other 31 shards continue serving.
• Regional origin failure — traffic reroutes to surviving 2 regions. Each region's app fleet is sized for 3.33M RPS + 1-AZ failure headroom, NOT for absorbing another whole region's 3.33M RPS. This architecture as sized does NOT survive a full regional outage at peak burst — for regional-failure survivability each region would need to handle ~5M RPS instead of ~3.33M (🧮 5 / 3.33 ≈ 1.5, so ~50% more capacity per region, which is ~50% more app boxes globally). This is an explicit design trade-off, not an oversight — the incremental cost of full regional-failure survivability at peak burst is a business decision to make explicitly.

What you now understand

• Why the write path and read path have different consistency requirements
• Why message queues decouple critical paths from best-effort work
• Why stream processors handle exactly-once processing through checkpointing, and why exactly-once effects at the sink additionally require idempotent writes (and even then, ClickHouse's ReplacingMergeTree gives eventually-consistent — not synchronous — deduplication)
• Why Day-2 operations (purging, abuse defense, monitoring) are a first-class concern, not an afterthought
• Why per-phase capacity math (RPS × utilization / ceiling × N boxes) is the language senior engineers use — not "we'll figure it out at scale"
• Why edge compute (Cloudflare Workers, CloudFront Functions) is the correct pattern at extreme scale — origin becomes a control plane
• Why multi-CDN redundancy becomes a resilience/business-continuity consideration at sufficiently large scale (not a universal RPS threshold)

When to Evolve — Beyond 1B RPS

Above 1B RPS, further evolutions are typically driven by non-traffic forces, not by additional scale headroom. Consider progressing when any of these become dominant:

• Vendor diversity as a first-class requirement — one CDN + one cloud provider is a business-continuity risk at revenue-critical scale. Add a second cloud provider (multi-cloud), not just a second CDN.
• Regulatory / data residency constraints — GDPR right-to-erasure, per-country data sovereignty, PII segregation. Each new regulatory jurisdiction may require region-affinity constraints that override cost-optimal routing.
• Operational isolation — the size of the platform team and the number of independent product lines using the same short-URL service may drive multi-tenancy isolation (per-tenant KV namespaces, per-tenant Kafka topics) that changes the architecture more than raw throughput.
• New consistency requirements — if the product roadmap adds mutable URLs (edit-in-place), the Cloudflare KV "1 write/sec per key" hard constraint (📗 verified doc) forces a different edge architecture. Same for real-time counters visible at edge.
• Platform / organizational boundaries — Conway's Law starts dominating: the architecture must reflect team boundaries as they grow, not just capacity math.

None of these are "just add more shards / more regions." They are structural changes to the platform, requiring product + platform + business coordination — this is why 1B RPS is where the interesting work stops being infrastructure and starts being organization design.

[🔗 REFERENCE WIDGET · `DesignChallenge`]
> Capstone exercise. Reader picks a variation: (a) URL Shortener with per-user analytics dashboards (adds a users table, adds per-user rate limits, adds RBAC), (b) URL Shortener with click-fraud detection (adds ML pipeline), (c) URL Shortener for enterprise with custom domains + SSO. Widget walks them through requirements → capacity → architecture → bottlenecks → cost. Auto-scored against a rubric.

Security and Observability at Phase 4 (per-phase extensions)

Security extension — edge WAF and DDoS at 1B RPS. Two Phase-4 realities force new controls:

• Edge-level rate limiting. Cloudflare Workers KV counters implement per-code windowed rate limits (1-minute buckets), evaluated at every PoP. A single hot code cannot exceed 10× the fleet-wide rate without triggering a soft throttle at the edge — the origin never sees the excess traffic. This is the mechanism that makes "denial of wallet" attacks tractable.
• Edge WAF at 1B RPS. Cloudflare Bot Fight Mode + OWASP Core Rule Set at the edge for POST /api/v1/*. Critical constraint: WAF rules cost Worker CPU budget (50 ms cap). Complex regex-heavy rules that were cheap at 100K RPS become prohibitive at 1B RPS — measure before adding. Rule bloat is the #1 cause of Worker CPU overruns in production.
• DDoS posture. Volumetric attacks at 1B RPS scale are absorbed by the CDN provider's global capacity — this is a benefit of the edge-first architecture, not a feature we build. Application-layer L7 attacks (e.g., valid-looking POST floods to the mint API) are the residual risk; per-API-key rate limits + WAF challenge pages are the response.

Observability extension — cardinality control and analytics-vs-trace separation.

At 1B RPS, naive observability breaks in three specific ways:

1. Cardinality explosion. Per-shortcode metrics × 100 billion codes = infinite label cardinality — Prometheus will die. Solution: pre-aggregate by shortcode into ClickHouse; export only fleet-wide and top-K counters to Prometheus. Individual shortcode metrics live in the analytics tier, not the monitoring tier.
2. Trace sampling ≠ analytics sampling. Application traces (OpenTelemetry) sample at 0.1-1% for cost; post-delivery analytics samples at 1% for cost. These are different pipelines with different sample rates and different consumers. State this explicitly in dashboards or reviewers will conflate them.
3. Alert fatigue. Threshold alerts fire constantly at 1B RPS. The burn-rate alerts installed at Phase 2 are the reason the on-call schedule survives — every alert is now anchored to error-budget consumption, not raw event counts.

Log routing at 1B RPS. Application logs from ~12,600 origin boxes cannot be formatted line-by-line in the app tier without noticeable CPU cost. Access logs are routed directly from Cloudflare / ALB to log storage (S3 → Athena, or Cloudflare Logpush) — app-tier code emits only structured business events, not per-request access records.

Cross-Cutting Architecture Concerns (canonical reference)

Four cross-cutting concerns have been integrated into the appropriate scale-level chapters where they teach best in flow. This section keeps their canonical reference bodies so the scale-level anchors can point at them without duplicating content:

• Requirements and API Contract — teaching chapter now sits after the Introduction (before Canonical Capacity Model).
• Custom Aliases and Vanity URLs — anchored in Phase 1 (after the Base62 chapter); canonical body below as CC-2.
• Security Architecture — anchored at Phase 2 with extensions at Phase 3 and Phase 4; canonical body below as CC-3.
• Observability, SLIs, SLOs, and Alerting — anchored at Phase 2 with extensions per phase; canonical body below as CC-4.

Four other concerns inherently span every scale level and are canonically documented here: Migrations (CC-5), Data Lifecycle & Compliance (CC-6), Load Testing & Game Days (CC-7), Rejected Alternatives (CC-8).

CC-2 — Custom Aliases and Vanity URLs (canonical reference; anchored in Phase 1)

What changes:
1. Namespace collision: user-chosen alias must be checked against the entire existing namespace before minting. At Phase 4, this is a global uniqueness check against 62⁸ ≈ 218 trillion possible codes with ~10-100 billion allocated.
2. Reserved-word list: admin, api, login, settings, ~10 K profane/trademark terms. Enforce at the API validation layer, not the DB.
3. Length constraint: minimum 4 chars (to avoid squatting the machine-generated 7-8 char namespace), maximum 20.
4. Character set: [A-Za-z0-9_-] — same as machine-generated codes plus - and _ for readability.
5. Rate limit: custom aliases cost more (they force uniqueness checks and consume dictionary-word namespace) — throttle at ~10× normal API rate.

Collision-check path (canonical):

```
1. Validate alias format (regex + reserved-word set).
2. Redis SET NX EX <ttl> on key alias:reserved:{alias} with 30s TTL
→ if fails, return 409 CONFLICT immediately (someone else is minting the same alias right now).
3. Query Vitess by short_code = alias (hash-vindex point lookup).
→ if row exists, release reservation, return 409 CONFLICT.
4. INSERT into urls with short_code = alias, status = ACTIVE.
5. Propagate to edge KV.
6. Return 201.
```

Namespace interaction with KGS:
Custom aliases are NOT drawn from the KGS pool. KGS mints sequential numeric IDs → Base62-encoded 7-8 char codes. Custom aliases live in the same urls.short_code column and the same UNIQUE index — and that is a latent correctness bug, not a statistical curiosity.

Why "check the DB at mint time" is not sufficient. A uniqueness check when the alias is created only proves the alias does not collide with codes allocated so far. It says nothing about the future. Suppose a user reserves the alias mylaunch — eight characters, every one of them in the Base62 alphabet. That string decodes to a specific integer: 🧮 Base62.decode("mylaunch"). When the KGS counter eventually reaches that integer, it will emit exactly mylaunch. Not might — will, deterministically, given enough time. The counter is monotonic and the encoding is a bijection, so every pure-Base62 alias is a scheduled future collision with a known arrival date.

At that point the write path hits a UNIQUE violation on a code the KGS design assumes can never collide. The data stays correct — the index sees to that — but a user's URL creation fails for a reason the KGS has no retry logic for, because the whole premise of monotonic allocation is that codes never collide. The fix is to make the two namespaces provably disjoint, so the check is unnecessary rather than merely repeated.

Three ways to get disjointness, with real trade-offs:

This course chooses Option B. It buys mathematical disjointness for a small, explainable input constraint, and it preserves the product value of a vanity URL. Option A is the right choice if you want the distinction legible to humans reading the URL (useful for abuse triage: a ~ prefix instantly identifies user-supplied content). Option C is the honest choice only if unconstrained aliases are a hard product requirement — and if you take it, write a test that actually exercises the collision path, because production won't for years.

Note that Option B also cleanly resolves the reserved-word problem at the same time: /api, /admin, /health, /v1 contain no - or _, so they are already unreachable as aliases without a blocklist. Keep the blocklist anyway for the cases the rule doesn't cover (/admin-panel is a valid Option-B alias and should still be reserved).

[🔗 REFERENCE WIDGET · `custom-alias-collision`]
> Reader types a candidate alias, sees the collision-check path animate through Redis reservation → Vitess lookup → INSERT. Toggle "someone else picked this alias 200ms ago" to observe the race resolution.

What you now understand: custom aliases are a product feature with a small ID-generation impact but a large validation impact (reserved-word set, regex, rate-limit tier). The KGS pipeline is unaffected.

CC-3 — Security Architecture (canonical reference; anchored at Phase 2 with Phase 3 and Phase 4 extensions)

A URL Shortener is a redirect service, which makes it an attractive vehicle for open-redirect, SSRF, phishing, and malware distribution. Security is not a feature — it is architectural table stakes.

The Foundation → Phase 4 progression assumes short codes are minted by the system (Base62 of an ID). Custom aliases (`bit.ly/my-launch`) break several invariants — see the Phase 1 Custom Aliases anchor for the mint-time flow. Content on threat modeling starts here.

Threat model (top 5):

1. Open redirect for phishing: attacker mints short.ly/PayPal-Login pointing at a phishing site. Mitigation: (a) URL scanning at mint time against Google Safe Browsing / VirusTotal / PhishTank; (b) delayed activation for suspicious domains; (c) after-the-fact takedown via user reports + automated abuse pipeline. Do NOT try to prevent all open redirects — the service is an open redirect. Instead, invest in fast takedown (target: < 5 min from report to global KV propagation).
2. SSRF via long-URL scanning: if the mint-time URL fetcher does a HEAD request to check reachability, it can be tricked into requesting internal IPs (http://169.254.169.254/latest/meta-data/). Mitigation: DNS resolution in a hardened resolver that rejects RFC 1918, loopback, link-local, and cloud metadata ranges. Egress from a dedicated VPC with no path to internal services.
3. Enumeration: sequential Base62 codes let an attacker enumerate aaaaaaa, aaaaaab, ..., scraping the entire URL corpus. Mitigation: rate-limit by IP and API key on 404s; consider HMAC-obfuscated codes for private tiers (see HMAC section).
4. Denial of wallet: attacker generates 1 billion requests/day pointing at expensive origins to exhaust CDN egress budgets. Mitigation: per-code rate limits at the edge (Cloudflare Workers KV counter with 1-minute windowed limit); alert on request rate > 100× normal for a single code.
5. API abuse / spam minting: bot mints millions of shortlinks to flood downstream services. Mitigation: authenticated API keys required for automated use; anonymous minting rate-limited to ~10/hour per IP; CAPTCHA on suspicious patterns.

TLS posture:
- TLS 1.3 mandatory at the edge; TLS 1.2 accepted only for legacy client compatibility.
- HSTS with max-age=31536000; includeSubDomains; preload.
- Cert rotation via Cloudflare-managed certs at edge, AWS ACM at origin ALB. No cert lives on disk in the app tier.

WAF rules (canonical minimum):
- Cloudflare Bot Fight Mode on the mint API.
- OWASP Core Rule Set at Cloudflare for POST /api/v1/*.
- Custom rule: block POST /api/v1/shorten with longUrl containing javascript:, data:, vbscript: schemes.
- Custom rule: block payloads > 10KB (long URL max is 2 KB; larger indicates attack).

HMAC secret rotation (referenced from HMAC section):
- Rotation cadence: every 90 days.
- Zero-downtime rotation: maintain HMAC_KEY_CURRENT and HMAC_KEY_PREVIOUS; verify against both during 90-day overlap window; mint only with CURRENT.
- Secrets in AWS Secrets Manager, injected at app-tier boot; edge Workers read from Cloudflare Secrets binding.
- Never commit HMAC keys to git; never log the key even at DEBUG.

[🔗 REFERENCE WIDGET · `open-redirect-validator`]
> Reader pastes a candidate long URL; widget shows the mint-time validation pipeline (scheme allowlist → DNS resolution in hardened resolver → Safe Browsing check → decision). Toggle attacker payloads (javascript:alert(1), http://169.254.169.254/..., http://phishing.example) and observe rejection paths.

What you now understand: the service must actively defend the redirect path from being weaponized. This is architectural work at the edge (WAF, rate limits), mint time (URL scanning, SSRF-safe resolvers), and operational (abuse pipeline with < 5 min takedown).

CC-4 — Observability, SLIs, SLOs, and Alerting (canonical reference; anchored at Phase 2 with per-phase extensions)

At Phase 4 (1B RPS), naive observability breaks in three specific ways:

1. Cardinality explosion: per-shortcode metrics × 100 billion codes = infinite label cardinality. Solution: pre-aggregate by shortcode into ClickHouse; export only fleet-wide and top-K counters to Prometheus.
2. Trace sampling ≠ analytics sampling: application traces (OpenTelemetry) sample at 0.1-1% for cost; edge-log analytics samples at 1% for cost. These are different pipelines with different sample rates and different consumers. State this explicitly or reviewers will conflate them.
3. Alert fatigue: naïve threshold alerts fire constantly at 1B RPS scale. Use burn-rate alerts anchored to SLOs.

Canonical SLIs (Service Level Indicators):

Canonical SLOs:
- Redirect availability: 99.95% rolling 30-day (26 min downtime budget)
- Redirect P99 latency: < 200 ms globally, < 100 ms in-region (design target — see CC-1 note on absolutes)
- Mint availability: 99.9% (43 min budget)
- Mint P99 latency: < 500 ms

Burn-rate alerts (multi-window, multi-burn-rate — Google SRE workbook pattern):
- Fast burn: 5% of 30-day budget in 1 hour → page immediately
- Slow burn: 10% of 30-day budget in 6 hours → ticket
- Do NOT alert on "one bad request." Alert on budget consumption, not on individual errors. This is the single biggest observability lesson at scale.

Distributed tracing (edge → origin):
- Cloudflare Workers set a traceparent header per W3C Trace Context on the request that traverses to origin (only on cache miss / origin fetch, ~1% of requests).
- Origin app tier propagates through JDBC calls via OpenTelemetry Java Agent auto-instrumentation.
- Sampled at 0.1% at edge, 100% at origin (edge decides).
- Traces land in an OTLP collector → Jaeger / Tempo / Grafana Cloud (choice is orthogonal).

Log routing:
- Application logs: structured JSON, one line per event, traceId + spanId fields for correlation.
- Access logs: NOT in application logs — routed from ALB / Cloudflare directly to log storage (S3 → Athena or Cloudflare Logpush) to avoid app-tier CPU cost of formatting billions of log lines.

[🔗 REFERENCE WIDGET · `slo-error-budget`]
> Reader watches a 30-day burn-rate chart; slider injects errors (via toggles for "regional outage," "bad deploy," "backend latency spike") and observes the burn-rate alert semantics (fast-burn page vs slow-burn ticket vs within budget).

What you now understand: observability at 1B RPS is a sampling discipline (cardinality control, trace sampling, log routing) and a math discipline (SLOs + burn rate) — not a "just add Prometheus" checkbox.

CC-5 — Migrations and Cutovers

Migrations at scale are where architecture theory meets operational reality. This course commits to three canonical migrations. Each is online, reversible-until-committed, and rate-limited to respect downstream vendor constraints. Big-bang cutovers with downtime are not an option at any scale level from Phase 2 onward.

Migration A — 7-char → 8-char short codes (namespace expansion)

Trigger conditions (any of):
- 62⁷ ≈ 3.5T codes with ~40% allocated (~1.4T codes issued) → statistically approaching the collision zone even with KGS's collision-free allocation.
- Projected time-to-exhaustion at current mint rate drops below 12 months.
- Product decides to expand to a namespace-hungry integration (bulk imports, API partners).

Cutover strategy (chosen):

The KGS emits variable-length Base62 output naturally — no zero-padding. So an 8-character code is simply what Base62.encode(id) returns once id ≥ 62⁷. The question the earlier draft of this section left unanswered is how the counter gets there, and the honest answer is: not on its own.

The counter does not cross 62⁷ by itself on any useful timescale. Starting from a counter well below 62⁷, organic growth takes 🧮 3,521,614,606,208 ÷ 30,000/sec ≈ 3.7 years at Phase 3 write rates, or ≈ 1.1 years at Phase 4's 100K/sec. You do not wait for that. You force the transition with a one-shot high-water-mark bump, and the migration is over in a single transaction:

sql
-- Zero-downtime 7→8 character cutover.
-- Runs inside the SAME SELECT ... FOR UPDATE transaction that
-- KgsRangeAllocator already uses for every range allocation.
START TRANSACTION;

SELECT next_id FROM kgs_state WHERE id = 1 FOR UPDATE;

-- Advance to the 8-character boundary, never backwards.
-- GREATEST() makes this idempotent: re-running it is a no-op,
-- so a retried deploy cannot rewind or double-apply.
UPDATE kgs_state
   SET next_id = GREATEST(next_id, 3521614606208)   -- 62^7
 WHERE id = 1;

COMMIT;

No drain, no pause, no write-path outage. It is tempting to stop KGS allocation "briefly" to make the cutover feel safe, but that would take the URL-creation path down for the duration and buys nothing: KgsRangeAllocator already serializes every allocation behind SELECT ... FOR UPDATE, so the bump is just one more serialized transaction in that queue. Any concurrent refiller either commits before the bump (and allocates a final 7-char range) or after it (and allocates 8-char). Both are valid.

Codes already sitting in the Redis queue are unaffected. At bump time each region's queue holds up to 10M pre-generated codes below 62⁷. Those remain valid 7-character codes and drain naturally over the following ~5 minutes at 33K IDs/sec. This is exactly the mixed-length namespace the design already accommodates — there is nothing to purge, and purging them would leak 10M IDs for no benefit.

The `GREATEST()` is load-bearing. SET next_id = 3521614606208 would be a catastrophic bug if the counter had already passed 62⁷: it rewinds the high-water mark and reissues codes that are already live, mapping new URLs onto existing short codes. GREATEST() makes the operation monotonic and therefore safe to retry, which matters because deploy tooling retries.

Verification is immediate rather than a multi-day wait — the very next code popped after the bump is 8 characters:

```
T-1d: Deploy KGS build with the mixedLengthMode: true flag.
Effect: no functional change - the encoder was already
variable-length. The flag is an operational signal and a
rollback affordance, not a behaviour switch.

T=0: Run the one-shot GREATEST() bump above. Single transaction,
sub-millisecond, no write-path pause.
The counter is now at 62^7 exactly.

T+0-5m: Regional Redis queues drain their remaining sub-62^7 codes.
Mint traffic emits a decreasing mix of 7-char, then all 8-char.
Verification: first 8-char code emitted within seconds of the
first post-bump range allocation. Manual redirect /aaaaaaaa
resolves; generated-code regex is [A-Za-z0-9]{7,8} (NOT the {4,20}
alias range — these are disjoint namespaces, see CC-2).

T+24-72h: Observe: mint success rate unchanged, redirect P99 latency unchanged,
Vitess hash-vindex distribution unchanged (hash defeats length).

T+7d: Full validation window. Deploy any client SDKs that assumed max
length 7 → 8. Update marketing copy that mentions "7-character URLs."

T+30d: Migration considered complete.
```

Rollback:
- Before the bump transaction commits: trivially safe - nothing has changed. This is the only clean rollback point, and it lasts until you run one UPDATE.
- Between the bump and the first 8-char emission (a window of seconds to minutes while queues drain): still safe, but you must rewind kgs_state.next_id and confirm no 8-char code was emitted, which is a race against your own queue drain. Treat this window as already committed rather than as a rollback option.
- After first 8-char emission: rollback is not safe — rolling back to codeLength: 7 would strand every emitted 8-char code (they exist in MySQL, in Redis, in edge KV, but the flag says "we don't emit 8-char"). If a rollback is required after emission, keep codeLength: 8 and instead investigate the underlying issue. The migration is not truly "reversible" after first emission — this is the trade-off of variable-length encoding.

Client impact: none if all client-side validators use [A-Za-z0-9]{7,8} for generated codes. Break if any client hard-coded {7}. Note this is a different regex from the custom-alias rule (^(?=.*[-_])[A-Za-z0-9_-]{4,20}$) — conflating them reintroduces the namespace overlap CC-2 exists to prevent.

Migration B — Vitess resharding (4 shards → 32 shards, then 32 → 64+)

Trigger conditions:
- Single-shard write QPS approaching 80% of MySQL primary reference ceiling (⚙️ ~4K writes/sec/shard modeled at Phase 3).
- Single-shard disk usage approaching 60% (leaves resharding headroom).
- Any single-shard replication lag consistently > 1s during peak.

Cutover — Vitess `Reshard` workflow (canonical):

```
Phase B1 (T=0): Create workflow. Source keyspace has 4 shards;
destination has 32. VStream begins copying rows.

Phase B2 (T=0 to T+h): Copy phase. Duration depends on data size (~1TB per
shard × 4 = 4TB copied to 32 shards). At ~200MB/s
cluster throughput, expect 5-6 hours.

Phase B3 (T+h): Reads switched via SwitchTraffic --tablet-types=REPLICA.
Observation window: 24h. Monitor error rate on
destination shards.

Phase B4 (T+h+24h): Writes switched via SwitchTraffic --tablet-types=PRIMARY.
This is the point of no easy return. Observation
window: 24-72h.

Phase B5 (T+h+72h): Complete — drops source shards. Reserved for after
the 72h observation window with zero write errors.
```

Rollback criteria:
- Between B1 and B4: SwitchTraffic --reverse completes in seconds.
- Between B4 and B5: SwitchTraffic --reverse for writes still works, but any writes accepted on the destination during B4-B5 must be replayed back to source (Vitess handles this via reverse VStream). Non-trivial but well-supported.
- After B5: rollback requires a fresh reshard 32 → 4 (unlikely to be desired; if capacity was the trigger, the answer is more shards not fewer).

Edge KV backfill during Vitess reshard: the ~10M hot codes cached at edge KV do not need to change — the KV key is short_code → long_url, agnostic of which shard holds the row. The reshard is invisible to the edge.

Migration C — Edge KV backfill (cold-start new region, cold PoP)

Trigger: Cloudflare adds a PoP, or a new deployment region needs bootstrapping, or a KV namespace was accidentally deleted and needs restore.

Cutover strategy:

Cloudflare Workers KV has a write ceiling of 1 write per second per key (📗 verified doc) and a soft limit of ~1000 writes/second per namespace. Naive for code in codes: kv.put(code, url) at 10M codes and 1000 wps takes ~10,000 seconds (~2.8 hours).

Rate-limited parallel backfill:

```
1. Identify hot codes (top 10M by 7-day redirect count in ClickHouse).
2. Batch into groups of 1000; run 100 parallel Worker cron jobs each writing 100 batches/sec.
→ Aggregate: ~100K writes/sec (respects namespace soft limit but pushes it).
3. Duration: 10M keys / 100K wps ≈ 100 seconds per region.
4. During backfill: origin RPS for uncached codes spikes ~100× — origin must survive.
At Phase 4, origin peaks ~10M RPS from 1% edge miss; during KV cold-start it
would peak ~1B RPS if no throttle is in place. Solution: **rate-limit at edge
during backfill**, serving from a "system busy, retry in 5s" response for
requests that miss KV. This is an operational choice, not a design flaw.
```

Rollback: trivial — backfill just stops. Origin serves all uncached traffic until backfill resumes.

Capacity/cost impact:
- Migration A: zero cost impact (same infrastructure).
- Migration B: transient 2× storage during copy phase (~4TB → ~8TB), then equilibrium at ~1.5× original (32 shards × ~150GB each vs 4 shards × ~1TB each — less per shard means less headroom overhead). Cost neutral to slightly higher due to more instances.
- Migration C: transient origin RPS spike is the cost driver; ensure app-tier autoscaler has 3× normal capacity headroom before starting.

[🔗 REFERENCE WIDGET · `reshard-cutover`]
> Reader triggers a Vitess reshard from 4 → 32 shards. Watches the 5-phase workflow (Create → Copy → Switch reads → Switch writes → Complete) animate with time-scale accuracy (Copy = 5-6 hours). Failure-injection toggle: "destination shard error rate spikes" during B4 → observe reverse SwitchTraffic. Accessibility: keyboard-navigable phase timeline, ARIA live-region announcements at each phase transition.

Decision snapshot:

What you now understand: every migration in this course has a trigger, an online cutover, an explicit rollback criterion with a "point of no return," a capacity/cost delta, and a rejected alternative. That template is the migration architecture — not "when Vitess we reshard."

CC-6 — Data Lifecycle, Deletion, and Compliance

GDPR "right to erasure" is the hardest problem in this system. A URL Shortener stores a mapping (short_code → long_url) plus click analytics. Both may contain PII (the long URL may embed an email or user ID in query params; click analytics record IP). The deletion path spans 5+ storage systems with no distributed-transaction protocol between them.

Deletion tiers (canonical)

Why physical deletion is not immediate. At Phase 4 scale, immediate physical deletion across MySQL + Redis + KV + Kafka + ClickHouse + S3 logs would be a distributed transaction across 5+ storage systems with no coordination protocol. Instead:

• The user-visible deletion (redirect returns 410 Gone) completes in Tier 1's < 60s window.
• Deep purge of raw logs completes within the S3 retention window.
• This is defensible under GDPR "reasonable timeframe" (72 hours for confirmation, ~30 days for full purge is standard practice).

Implementation architecture:

```
User → DELETE /api/v1/urls/{code}
↓
[1] Mint API: UPDATE urls SET status='DELETED' WHERE short_code={code}
↓ (commit)
[2] Emit event to deletion-events Kafka topic
↓
┌─── Fanout consumer 1: KV purge across all PoPs (parallel writes)
├─── Fanout consumer 2: Redis cluster PUBLISH cache-invalidate:{code} per region
├─── Fanout consumer 3: ClickHouse tombstone insert; nightly ALTER TABLE ... DELETE
└─── Fanout consumer 4: S3 log filter set updated; next log-rotate applies filter
```

Each consumer is idempotent. Retries are safe. The Kafka topic gives the compliance auditor a single append-only log to point at for evidence.

PII in long URLs

The redirect service does not parse query strings — the long URL is opaque bytes. This means:

• Under GDPR, if a user submits a takedown for a specific short code, delete via Tier 1-4.
• Do not attempt to scan long URLs for PII proactively — false positive rate is high (?userid=42 is not PII; ?email=user@example.com is; the same request may have both) and the legal basis is user-driven takedown, not automated PII scanning.
• If the platform decides to offer proactive scanning (e.g., a "detect PII in your URLs" feature for enterprise), that becomes a separate opt-in service, not a compliance requirement.

Click analytics PII

• IP addresses: masked to /24 for IPv4 and /48 for IPv6 within 24 hours of capture; retained masked for aggregate analytics.
• User-agent strings: stored raw for 30 days, then aggregated into (browser, browser_major_version, os, os_major_version) tuples.
• Referer headers: stored per event; user takedown request removes rows for that short code.
• Geolocation derived at edge from IP; stored at city-granularity, never street-level. IP is discarded within 24 hours; derived geolocation persists.

Data residency

• EU-origin URL creations route to an EU region (Frankfurt); analytics for those codes stay in the EU ClickHouse cluster.
• Cross-region replication of the reverse-lookup (short_code → long_url) is fine — this is not PII, and users expect their short URLs to work globally.
• Cross-region replication of click analytics is gated by region policy — EU click analytics do not leave the EU cluster except in aggregated (non-PII) form for cross-region rollups.
• US and EU deletions are independently confirmed: a deletion issued from EU triggers Tier 1-4 in EU; the same short_code may also exist in US analytics if any US clicks occurred, and the US pipeline must run its own Tier 3-4. Cross-region confirmation is via a "deletion complete" Kafka event replicated to a central compliance topic.

Retention policies (canonical)

[🔗 REFERENCE WIDGET · `deletion-propagation`]
> Reader triggers a delete. Watches Tier 1 → Tier 4 propagation animate across MySQL, Redis, KV (with 60s propagation bar), ClickHouse, and S3 log retention — with real time-scale differences visualized (Tier 1: 60s bar; Tier 2: 5s bar; Tier 3: 24-72h bar; Tier 4: 90d bar). Callout: "Why is Tier 4 slow?" explains distributed-storage reality without single-transaction coordination. Accessibility: reduced-motion switches to a stepped indicator; screen-reader announces "Tier N complete."

Decision snapshot:

What you now understand: GDPR compliance in a URL Shortener is a tiered deletion problem where user-visible response is < 60s but deep raw-data purge takes days. This is defensible and standard; the architectural mistake is promising "immediate deletion" and failing.

CC-7 — Load Testing and Validating the Numbers

Every capacity number in this course carries a provenance label — 📗 verified, 📊 benchmarked, 📐 illustrative, ⚙️ workload-dependent, or 🧮 derived. The only way to convert an assumption into a fact is load testing under a representative traffic model. This chapter is how we do that at each scale level.

Canonical load-test profile

• Tool: k6 or Gatling. Both handle > 100K RPS from a single load-gen fleet with good tail-latency measurement. k6's JS/TS scripts are easier to version-control alongside application code; Gatling's Scala DSL has better report ergonomics for stakeholders. Either works; pick one and standardize.
• Traffic mix: 99% GET /{shortCode}, 1% POST /api/v1/shorten at Phase 3+ (per canonical write assumption; adjust for Phase 4 where writes are an independent workload variable).
• Key distribution: Zipfian with s = 0.9-1.0. Real click traffic is highly skewed — the top ~10K codes get ~80% of clicks. Uniform-random key distribution over-stresses cache and gives misleadingly bad numbers. This is the #1 load-test mistake.
• Ramp: 10% → 25% → 50% → 100% peak over 30 minutes; hold peak for 60 minutes; observe P50/P95/P99/P99.9 latency and error rate.
• Failure injection: kill one AZ mid-test; kill KGS; saturate one shard's hot key.

Sample k6 script (Phase 2 load test)

javascript
import http from 'k6/http';
import { check } from 'k6';
import { Rate, Trend } from 'k6/metrics';
import { randomZipfianKey } from './zipfian.js';

const redirectFailures = new Rate('redirect_failures');
const p99Latency = new Trend('redirect_p99', true);

export const options = {
  stages: [
    { duration: '5m',  target: 10000  },   // 10K RPS ramp
    { duration: '5m',  target: 25000  },
    { duration: '5m',  target: 50000  },
    { duration: '5m',  target: 100000 },   // full 100K RPS
    { duration: '60m', target: 100000 },   // hold peak
    { duration: '5m',  target: 0      },   // ramp-down
  ],
  thresholds: {
    'redirect_p99{status:"302"}': ['p(99)<200'],
    'redirect_failures':          ['rate<0.001'],
  },
};

// Zipfian-distributed key generator: s = 0.95
const KEY_POOL_SIZE = 10_000_000;
const ZIPF_S = 0.95;

export default function () {
  const code = randomZipfianKey(KEY_POOL_SIZE, ZIPF_S);
  const res = http.get(`https://short.ly/${code}`, { redirects: 0 });
  const ok = check(res, {
    'status 302': (r) => r.status === 302,
  });
  redirectFailures.add(!ok);
  p99Latency.add(res.timings.duration, { status: res.status });
}

Phase-specific load-test targets

At Phase 4, do not attempt a 1B RPS load test. The load-gen fleet cost approaches production cost. Instead: (a) load-test at ~10% (100M RPS), (b) extrapolate to 1B with explicit assumption of linear scaling, (c) validate the linearity assumption via smaller-scale ramps at 1M, 10M, 100M and check that latency stays flat.

Chaos exercises (production-safe cadence — weekly)

1. Terminate a random app-tier instance during peak. Expected: no user-visible impact; ALB removes unhealthy target within 30s.
2. Force AZ failover of MySQL primary. Expected: 30-60s write outage during failover; reads continue from replicas.
3. Inject 500ms Redis latency in one region. Expected: Redis timeouts trip; app falls through to MySQL; increased MySQL load; overall latency ↑ but no errors.
4. Simulate Cloudflare edge outage via DNS failover to CloudFront alternate. Expected: DNS TTL propagation ~5 min; user-visible for that window; existing KV entries continue serving from the alternate.
5. Kill KGS. Expected: 5-minute write-path continuity from the queue; explicit alert; escalation to on-call.
6. Saturate a shard's hot key with 100× normal RPS. Expected: hot-key mitigation (edge cache, process cache, coalescing) engages; shard remains healthy.

Game days (quarterly)

Full-day exercise: production traffic diverted to a staging environment mirroring Phase 3 or Phase 4; deliberate multi-failure injection; on-call team responds without prior notice of scenario. Written postmortem produced even for successful games — surface the why, not just the what worked.

What good looks like

• Load test runs monthly, is version-controlled with the codebase, and blocks deploys if P99 regresses > 20%.
• Chaos exercises produce written postmortems even when they succeed cleanly.
• Every capacity number in the course is annotated with the last date/tool it was validated against ("~3M ops/sec/Redis-node — last validated 2024-Q3 via redis-benchmark with 100:1 GET:SET, 128-byte values, pipeline=8").

Decision snapshot:

What you now understand: the number ~4,200 boxes/region at Phase 4 is a starting hypothesis — load testing decides whether it's 3,000 or 5,500 in your actual environment. The architecture doesn't change; the sizing does. And it's the load test that gives you the confidence to defend the number in the review room.

CC-8 — Rejected Alternatives (ADR-style)

Every scale-level chapter names what we chose. This section names what we rejected and why. Interviewers ask this. Architects need it. Every ADR here follows the same rhythm: context, rejection criterion, evidence, chosen alternative.

ADR-1 — NoSQL (DynamoDB / Cassandra) — REJECTED in favor of MySQL + Vitess

Context: URL Shortener's core lookup is a key-value read (short_code → long_url), which superficially fits NoSQL.

Rejection criterion:
- Write hot-key problem — a single viral URL creates a hot partition in DynamoDB/Cassandra that cannot be transparently split. MySQL + Vitess's shard-primary structure handles this with edge caching (the hot key never reaches MySQL).
- Secondary indexes — admin queries need (owner_id, created_at) range scans. DynamoDB GSI has additional cost and eventual-consistency semantics; Cassandra secondary indexes have well-known scale limitations. MySQL indexes are boring, well-understood, and fast for this workload.
- Transactional KGS range allocation — the KGS SELECT ... FOR UPDATE + UPDATE transaction is a 2-statement single-row transaction that MySQL executes in single-digit ms. Replicating this in DynamoDB requires optimistic-locking + retries, and Cassandra requires lightweight transactions (LWT) which have well-known performance cliffs.
- Per-request cost curves at 10M+ RPS — DynamoDB priced at per-request units becomes cost-prohibitive at extreme scale. Self-managed MySQL on EC2 is cheaper per query at Phase 4 by 5-10× (illustrative; workload-dependent).

Chosen: MySQL + Vitess. NoSQL is a cost trade-off here, not a performance necessity — DynamoDB would work functionally, but the fleet cost curve favors sharded MySQL at ≥10M RPS.

ADR-2 — Snowflake IDs (Twitter-style) — REJECTED in favor of KGS + Base62

Context: Snowflake IDs (timestamp + worker_id + sequence) are the industry-standard distributed ID scheme. Twitter uses them; many systems copy the pattern.

Rejection criterion:
- Length: Snowflake IDs are ~64 bits. Encoded to Base62 that's 11 characters (log₆₂(2⁶⁴) ≈ 10.75). Product requirement is short codes for user visibility — 7-8 chars is the target.
- Namespace density: Snowflake IDs use timestamp bits, so most of the 62¹¹ namespace is unused (only recent time windows are populated). Base62 of KGS-allocated sequential IDs is dense — every code in 62⁷/62⁸ is a valid mint.
- Zero-collision guarantee: Snowflake avoids collisions via worker_id partitioning; KGS avoids collisions via durable range allocation. Both work; KGS's guarantee lives entirely inside MySQL, which is where the source-of-truth already lives.

Chosen: KGS-allocated sequential IDs, Base62-encoded, 7-char at Phase 1-2, 8-char at Phase 3+. Snowflake wins only if we didn't care about code length.

ADR-3 — Managed analytics (Snowflake / BigQuery) — REJECTED in favor of Kafka + Flink + ClickHouse

Context: Managed analytics (Snowflake, BigQuery, Databricks) offer zero-ops ingestion with SQL query interfaces. Attractive for smaller teams.

Rejection criterion:
- Ingestion cost at 10M events/sec — managed analytics typically charge per event ingested at rates that dominate the analytics budget above ~100K events/sec.
- ClickHouse self-hosted has 10-100× better $/event at ≥10M events/sec (illustrative; validated by the ClickHouse benchmarks and multiple public case studies).
- Latency: managed analytics have ingestion-to-queryable latency of minutes to hours; our real-time-counter requirement is < 5s (Redis-fronted).

Chosen: Kafka + Flink + ClickHouse for streaming ingestion; Redis for real-time counters; ClickHouse for historical queries. Managed wins below ~100K events/sec — we chose self-hosted only because we cross that threshold.

ADR-4 — Consistent hashing for Vitess sharding — REJECTED in favor of hash vindex (mod N)

Context: Consistent hashing (Redis Cluster, Cassandra, DynamoDB partitions) shines when nodes come and go dynamically.

Rejection criterion:
- Vitess reshards via `Reshard` workflow — a planned, online operation with 5 clear phases and explicit "point of no return." This is more operationally predictable than implicit consistent-hash rebalancing.
- Debuggability: given a short_code, "which shard does it live on?" is hash(short_code) mod 32 — a single arithmetic op. With consistent hashing, the answer requires a ring lookup and is opaque.
- Reshard scope: during a Vitess reshard, exactly the shards being split are touched; other shards are unchanged. Consistent-hash rebalancing touches every neighboring node.

Chosen: hash vindex on short_code. The operational simplicity + explicit reshard beat consistent-hashing's implicit rebalancing for our workload profile.

ADR-5 — GraphQL for the mint API — REJECTED in favor of REST + OpenAPI

Context: GraphQL's query-flexibility superpower is celebrated for reducing over-fetching in front-end-heavy applications.

Rejection criterion:
- API surface area: the mint API has 4 endpoints (POST /shorten, GET /urls/{code}, DELETE /urls/{code}, GET /urls?owner_id=...). GraphQL's flexibility is unused.
- CDN caching: GET requests over REST cache trivially at Cloudflare; GraphQL POSTs with query-in-body require custom cache-key extraction.
- WAF maturity: OWASP CRS works out-of-the-box for REST; GraphQL WAF rules are less mature and higher-false-positive.
- Observability: REST route templates map 1:1 to Prometheus metric labels; GraphQL operation names require middleware to emit.

Chosen: REST + OpenAPI. GraphQL wins for internal admin dashboards (not covered here); for the public API, REST is the ecosystem-supported choice.

ADR-6 — Rust or Go at origin — REJECTED in favor of Java + Spring Boot 3

Context: Rust and Go both offer ~2-3× per-instance throughput vs Java for a URL-shortener-style workload.

Rejection criterion:
- Hire-ability + team size: the fleet cost differential (~$200K/month at Phase 4) is a rounding error compared to CDN + edge compute (>$500K/month). Hiring 10 senior Java engineers is materially easier than 10 senior Rust engineers in most markets.
- Ecosystem maturity: Vitess Java driver, Micrometer observability, OpenTelemetry Java Agent (auto-instrumentation), Spring Data with Vitess — all first-class. Go has good libraries; Rust's async ecosystem is still maturing for HTTP+DB workloads.
- Fleet-cost differential math: if we ran on Rust with 3× throughput per instance, we'd need ~4,200/3 ≈ 1,400 boxes/region instead of 4,200 — saving ~$200K/month at Phase 4. Meaningful but not budget-changing.

Chosen: Java + Spring Boot 3. Rust or Go would win on per-instance throughput; the fleet cost is a rounding error compared to the total AWS bill at Phase 4.

ADR-7 — Worker-side analytics sampling — REJECTED in favor of post-delivery sampling (Model 2)

Context: Sampling at the Worker (edge) is a common optimization — reduce log-delivery volume by 100× before it leaves the PoP.

Rejection criterion:
- Worker CPU budget is 50ms. Every ms spent on sampling logic is a ms less for the redirect. Random sampling is cheap; deterministic-hash-based sampling (needed for consistent per-code inclusion) is not.
- Loss of durable record. Worker-side sampling permanently discards 99% of events at the earliest possible point. If a bug in downstream processing is discovered later, you cannot re-sample or reprocess — the events are gone. Model 2 (post-delivery sampling) preserves the full unsampled record in S3 CDN logs, so reprocessing is always possible within the 90-day retention window.
- Cost trade-off: worker-side sampling saves log-egress cost (~1% of Phase 4 spend); Model 2 pays that cost in exchange for reprocessability. At Phase 4 the reprocessability is worth it.

Chosen: Model 2 — post-delivery analytics sampling. Worker-side sampling remains available as a non-canonical optimization for teams that cannot pay the log-egress cost.

ADR-8 — Postgres — REJECTED in favor of MySQL

Context: Postgres is architecturally competitive with MySQL for OLTP workloads. Many modern teams prefer Postgres for its type system and MVCC design.

Rejection criterion:
- Vitess ecosystem is MySQL-native. Vitess routes MySQL wire protocol, uses MySQL binlogs for VStream replication, and integrates with MySQL's replication topology. There is no equivalent Postgres-native "Vitess for Postgres" with the same maturity.
- Citus is the Postgres equivalent for sharding but is optimized for OLAP-style workloads, not the point-lookup OLTP profile of a URL Shortener.
- Team experience: for a course targeting career development, MySQL's ubiquity ensures the lessons transfer.

Chosen: MySQL. Choosing Postgres would mean building or buying Citus-scale tooling separately, absorbing an operational cost that MySQL + Vitess doesn't require.

What you now understand

An architect defends decisions by naming what they rejected. Every ADR here has a specific rejection criterion — not "we like Java better," but "the fleet cost differential is a rounding error and hire-ability + observability maturity favor Java." When you're asked in an interview or a design review "why not X?", the answer is not "X is bad" — it is "X is good for a different problem; here is the criterion that distinguishes." That distinction is the architect skill.

What You Have Learned — Overall

By walking through the Foundation and 5 Scale Levels, you now understand:

1. Why simple MD5 hashing fails — even at moderate scale, it produces collisions and unpredictable latency.
2. Why Base62 encoding is elegant — it converts the uniqueness of integers (which databases give us free) into uniqueness of short codes (mathematically guaranteed).
3. Why cache-aside is the default caching pattern — it's simple, doesn't require write-path consistency guarantees, and handles the read-heavy nature of URL shortener workloads.
4. Why single-flight fixes cache stampedes — when many requests hit the same missed key, only one goes to the database.
5. Why sharding is inevitable at scale — single databases have physical limits; MySQL with Vitess gives horizontal write scaling without the operational upheaval of a NoSQL migration.
6. Why you need a separate ID generator when sharding — AUTO_INCREMENT is per-database; distributed IDs must come from a dedicated service.
7. Why analytics must be asynchronous — synchronous writes on the redirect path bottleneck the whole system; message queues + stream processors decouple this cleanly.
8. When to consider NoSQL — rarely, for this workload. When you do, it is a cost trade-off, not a performance necessity.
9. How to distinguish "the system that works" from "the system that scales" — the first is the weekend project; the second is Foundation + 5 Scale Levels of forced architectural evolution.

You have traced a single system from ~100 requests / day (Foundation) to 1 billion requests / second (Phase 4 — an aspirational extreme-scale tier), and every decision was forced by a specific measured bottleneck — not by hype.

That's system design.