URL Shortener

Alright. Sit down. Let me set the scene the way it actually happens in real life, because most tutorials skip this part and it's the most important part.

You've just joined a startup as engineer #4. Your CTO drops by your desk on a Monday morning with coffee in hand and says: "We need a URL shortener. Like bit.ly. Something we can offer as a service to marketing teams. Ship an MVP in 8 weeks. Handle whatever traffic comes. Oh — and it needs to be reliable, we're pitching to Fortune 500 customers."

She walks away.

Now — what do you do?

Ninety percent of engineers (junior AND senior, honestly) do the wrong thing here: they open a whiteboard and start drawing boxes. Load balancer. Cache. Database. Kafka for some reason. It's a reflex.

Don't.

The first hour of any system design is not architecture. It's understanding what you're actually being asked to build. Because "URL shortener" is a wildly under-specified problem. Is this internal or public? Analytics or no analytics? Custom aliases? Rate limits? Retention forever, or expire after 30 days?

Every one of those questions changes the architecture. If you draw the architecture first and THEN answer them, you're going to redesign three times.

The whole journey at a glance

Before we dive in, here's where these 17 chapters are actually going. Every 10× in scale forces a fundamentally different architecture. Play with the interactive evolution below — click each tier, watch the components stack up, read the added-in-this-tier badges:

Chapter map: Ch 5 walks through L4 in full. Ch 6 + 6.5 walks through the cache decision, cache-aside flow, and read replicas. Ch 7 + 7.5 + 7.6 walks through global topology, analytics, and security defense-in-depth. Ch 8 walks through L7 as business strategy, not tech.

That's the whole arc. Each scale added something the previous scale couldn't handle. Chapter 5 walks you through building L4 from scratch. Each subsequent chapter shows what BREAKS at the next tier and what you add to fix it — never a rewrite, always an evolution.

Why URL shorteners exist — 20 years of scaling history

Before you design a URL shortener, know why they were invented and how the design has evolved. The interview question "design a URL shortener" is really asking "can you build a Bit.ly?" — and the answer only makes sense if you know the history that shaped what a modern URL shortener actually is. Play through the interactive timeline below — it auto-plays through 20 years of scaling history, or click any era to focus:

The three lessons that shape the modern architecture:

1. Analytics is the product, not shortening. From 2008 onward, every serious shortener sold click analytics. That's why we use 302 not 301 (so every click reaches your server), why we build Kafka-based click pipelines at scale (Ch 7.5), and why L7 sells for 100× more revenue than L4.

1. Abuse detection is non-negotiable. TinyURL's decline + goo.gl's shutdown both trace to abuse. Modern shorteners have Google Safe Browsing integration + real-time URL scanning + rate limiting from day one. Ch 7.6 covers this.

1. Scale is monetization. At L4 you have a hobby project. At L7 you have a $50-500M/yr business. Every scale tier unlocks a new customer segment (individual → SMB → enterprise → platform). Chapter 8 is really about business strategy, not technology.

So here's the discipline I want you to build in this course: before you draw anything, you ask questions. That's Chapter 1. We're going to walk through exactly what to ask, and — this is the part most tutorials skip — WHY each question matters, because if you don't understand why, you'll ask them mechanically like a checklist and get useless answers.

Ready? Let's go.

Before we start designing URL Shortener, I want to answer the one question that separates good candidates from great ones:

Why does the architecture change as traffic grows?

Most tutorials just show you the "final architecture at 1B RPS" and call it a day. That's memorizing the answer. You need to understand why each layer exists — because each layer exists to unblock a specific bottleneck that the previous architecture had.

The whole game of system design is a loop:

```
SCALE ↑ → Something BREAKS → Add a REDESIGN → new BOTTLENECK → next REDESIGN → ...
```

You start at 100 RPS on a single VM. You grow to 10K RPS and the database melts — you add a cache. You grow to 1M RPS and the regional LB caps out — you go multi-region. You grow to 1B RPS and network round-trip becomes the wall — you move compute to the edge.

Every senior engineer has this loop internalized. They see any system and can immediately tell you which component will break next, and why.

The interactive simulator

Drag the RPS slider across 8 tiers — from 100 RPS to 1 BILLION RPS. Watch:
- The architecture changes — components appear and disappear
- Traffic flows through each component (animated dots)
- Each component shows a capacity gauge — green (healthy), yellow (stressed), red (BROKEN)
- When something breaks, the simulator explains what broke and why, and what redesign fixes it

The 8 tiers explained

The 5 patterns you'll see over and over

Study these until you can spot them without thinking:

1. Horizontal scaling — take the bottleneck component and run N copies with a load balancer. Works until the component behind it (usually DB) becomes the new bottleneck.
2. Caching — put a faster tier in front of a slower one. Trade fresh data + memory for latency + throughput. The "92% hit ratio" is not lucky — it's what happens when your access pattern has locality.
3. Sharding — split state into shards, route each request to its shard. Works until you have cross-shard queries or need atomic multi-shard writes.
4. Async decoupling — move slow work off the hot path via a queue. Users get 202 Accepted immediately, worker processes when it can. Cost: eventual consistency.
5. Multi-region — the last redesign, the most expensive. Data has to live in multiple places, which means CAP theorem is in your face.

Each of the following chapters teaches ONE of these patterns. By the end of Chapter 12, you'll be able to enter the simulator at any RPS tier and mentally sketch the architecture without help.

Newbie insight: the simulator's break-point explanations are the CORE of what interviewers are testing when they ask "what happens at 10× the current load?" The senior engineer doesn't recite an architecture — they walk through the failure mode + the redesign. Practice this out loud.

Good. You're back. Let's talk about the six questions.

I'm going to walk you through every question I would ask if I were interviewing for a Staff role at Google right now. Each one comes with the "why" — what changes in the architecture based on the answer. Learn the "why" and you'll never need to memorize a checklist again.

Notice the pattern: every question either (a) changes what components appear in your architecture, (b) changes the scale you're designing for, or (c) changes the trade-off you're forced to make. If a question doesn't do one of those three things, don't ask it — you're wasting interview time.

Read through the questions below. For each one, before you look at the "why," ask yourself: what would change if the answer flipped? If you can articulate that, you've earned the right to ask the question.

Now — while we're here, let me also drop in the requirements. Functional (what it does) and non-functional (how well it does it). These aren't guesses. They're the result of the clarifying questions. You ask questions → you get answers → the requirements crystallize. Then and only then do you touch a whiteboard.

This is the chapter where I tell you the truth: capacity estimation is not optional, and most candidates blow it.

Not because it's hard. Because they don't understand it as reasoning, so they memorize numbers ("Twitter has 500M users") and can't derive anything else.

Here's the mental model I want you to build: capacity estimation is a funnel of ratios.

• Start with the top: how many people use the product?
• Multiply by activity: how many requests per person per day?
• Divide by seconds: what's the average requests per second?
• Multiply by peak factor: what's the peak?
• Add storage math: bytes per request × requests per day = storage per day
• Add bandwidth math: bytes per response × requests per second = bandwidth

If you know the funnel, you can estimate any system in 3 minutes. You are not memorizing numbers. You are memorizing a process.

Here's the funnel visualized — every row is derived from the row above by ONE arithmetic operation. Drag the sliders below to see how each row responds:

Notice how each row implies the next. You cannot skip a step. The DAU number sets the whole funnel. The peak factor (usually 2-3×) is where amateurs fall off — they design for average and their system falls over at 12:30pm every day.

From RPS to "how many boxes?"

The funnel above gives you peak RPS. But that number alone doesn't tell you how much infrastructure to spin up. The missing step — the one most tutorials skip — is:

peak_rps × safety_margin ÷ (rps_per_box × cpu_utilization) = box count

Let me unpack each term, because this is where senior candidates separate from the pack:

• rps_per_box — how many requests a single instance can serve, empirically. For a URL shortener redirect (mostly a MySQL primary-key lookup), a Node.js or Go service on an m5.large handles roughly 1500-2000 RPS at 70% CPU. Reference: TechEmpower Round 22 benchmarks. Get this wrong and every other estimate is off.
• cpu_utilization — you never run boxes at 100% CPU. Above ~80% CPU, latency spikes non-linearly (queueing theory) — one bad GC pause and you drop requests. Target 60-70% as the steady-state ceiling.
• safety_margin — buffer for the "oh no" moments: a viral traffic spike, a bad rollout that halves capacity, one AZ failing over. 1.5× is the industry-standard minimum; senior engineers use 2× when the workload is variable.
• HA floor — even if the math says you only need 2 boxes, Multi-AZ availability requires a minimum of 3 (one per AZ, plus one for rolling deploys without going below 2 healthy). This is where you get the "3 EC2 medium instances will be sufficient" answer you'll see quoted throughout this course — it comes from the HA floor at the L4 / MVP scale.

Play with the calculator below. Notice how the answer changes when you flip between L4 (10K RPS), L5 (100K RPS), and L6 (1M RPS) presets:

The interview soundbite: "I'd size the app tier at ⌈peak_rps × 1.5 ÷ (1500 × 0.6)⌉ boxes, with a minimum of 3 for Multi-AZ HA. At 100K peak RPS that's 167 required by math, so 167 m5.large boxes — about $12K/month on-demand, or $4K/month on 3-year reserved. The database is a separate calculation because it's stateful."

Below you'll see the actual numbers for our URL shortener at scale. Trace through them. Understand where each number comes from. If you can't derive one, come back to this chapter until you can. The derivation is the skill; the numbers are just outputs.

One thing many candidates miss: peak RPS is usually 2-3x average. Traffic isn't uniform across a day — everyone reads Twitter at lunch. If you design for average, you fall over at 12:30pm. Design for peak.

Also — and this is where senior candidates separate: your estimation directly implies your architecture. 10K RPS is a single MySQL. 100K RPS needs a cache. 1M RPS needs sharding. If you can't map estimation to architecture in your head, you're not ready for Chapter 5.

The API is the contract between your service and everyone who uses it. This is the ONLY thing your users see. Everything else — cache, database, sharding, Kafka — is invisible implementation detail. So get this right.

For a URL shortener you need three endpoints. Just three. If you design more, you're over-scoping. If you design fewer, you're missing something.

But inside those three endpoints there are four subtle decisions that separate a junior design from a senior one:

1. What's the redirect status code? 301 or 302? These are NOT interchangeable — one lets browsers cache the redirect forever (analytics undercount by 90%), the other doesn't. Wrong choice = wrong product.

2. How do you handle idempotency? If a client double-taps the "shorten" button, do they get one URL or two? Junior devs let it create two. Seniors design an idempotency-key header on day 1.

3. What's your versioning strategy? /v1/urls or /urls?version=1 or Accept: application/vnd.company.v1+json? All three work; only one is boring, obvious, and forever-compatible.

4. How do you handle authentication? Public endpoint (anyone can shorten) or authenticated (API key)? Both are valid — but they change your rate-limiting strategy and your abuse-prevention story fundamentally.

What the API round-trip actually looks like on the wire

Before you go further, let's watch the actual bytes fly. Here's what happens when a user POSTs a new URL and then somebody clicks the resulting short link. This is the wire-level view — headers, status codes, timing, the whole thing:

A newbie should read every arrow. Notice:

• POST is uncacheable. The CDN forwards every POST to origin. That's fine because writes are 1% of traffic.
• The Idempotency-Key check happens BEFORE code generation. Client double-taps → server returns the same short_code from cache instead of creating two. See Chapter 3.5 for the RFC-cited pattern.
• Fire-and-forget analytics. The Kafka publish happens in a background task after the 302 goes out. If Kafka is down we still redirect the user; we just drop one analytics event. That's the Google SRE "auxiliary services never block the primary path" principle (Chapter 7.5) in action.
• Cache-Control: no-cache on the 302. Prevents browsers from caching the redirect forever (see Chapter 3.5 on why 302 beats 301 for analytics).

Numbered decisions map (deep-dives)

Every step in the diagram above ties to a deeper chapter:

1. Idempotency-Key header semantics → Chapter 3.5 (RFC draft-ietf-httpapi-idempotency-key-header, Stripe's pattern)
2. Short-code generation strategy → Chapter 4.5 (5 approaches from random+check to KGS pool)
3. INSERT + Multi-AZ commit → Chapter 5 (MySQL CPU derivation, 5ms sync commit math)
4. CDN edge caching for redirects → Chapter 7 (95% offload derivation, CDN comparative)
5. Cache-aside pattern with SETNX stampede protection → Chapter 6 (the L5 evolution)
6. Fire-and-forget Kafka analytics → Chapter 7.5 (partitioning math, Flink exactly-once)

Look at the API table below. See how each endpoint hints at these decisions? That's not accidental. Every field in a good API spec is defending against a future problem.

Chapter 3 named the four subtle decisions. Now I'm going to defend each one with the actual RFC references and real-company practices — the level of rigor an interviewer expects at L5+.

Here's the rule you should internalize: any time you cite a technical behavior, cite the standard. "302 means temporary redirect" is weak. "Per RFC 7231 §6.4.3, 302 Found indicates the resource resides temporarily under a different URI, and clients SHOULD NOT cache it unless indicated by Cache-Control" is strong. In an interview, the second answer signals someone who has read the specs. Do that.

Let's go endpoint by endpoint, then cross-cutting.

Endpoint 1: POST /v1/urls — the create path

Why POST (not PUT)?

Per RFC 9110 §9.3.3 (HTTP Semantics, 2022), PUT is used when the client specifies the target URI. Here the server generates the short_code, so the client cannot know the URI ahead of time — that makes POST correct.

If we let the client specify a custom alias (e.g. sysd.link/team-offsite), we could argue for PUT /v1/urls/team-offsite — but that's a different endpoint semantically. Our design keeps POST as the default create; custom aliases are a POST with a custom_alias field.

Status code on success: 201 Created

RFC 9110 §15.3.2: 201 Created SHOULD be returned when the request has been fulfilled and a new resource created. Include a Location header pointing to the new resource:

http
HTTP/1.1 201 Created
Location: /v1/urls/aB3xY9
Content-Type: application/json

{"short_code": "aB3xY9", "short_url": "[https://sysd.link/aB3xY9](https://sysd.link/aB3xY9)", ...}

Why not 200 OK? 200 is generic success — you leave the interviewer wondering if you know the difference. 201 is the correct answer. Both work in practice; the interview probe tests whether you know the RFC.

Why not 202 Accepted? 202 is for async processing where the create is queued but not yet done. Since URL creation is synchronous (one MySQL INSERT), 201 is right.

Payload validation — 400 Bad Request cases

Reject early. Return 400 Bad Request (RFC 9110 §15.5.1) with a JSON body describing what failed:

References: OWASP Top 10 2021 (owasp.org/Top10), RFC 9110 for HTTP semantics.

The Idempotency-Key header — how to defend safe retries

This is the pattern Stripe made famous (docs: stripe.com/docs/api/idempotent_requests). Client attaches a UUID header on each POST:

http
POST /v1/urls HTTP/1.1
Idempotency-Key: 8e6b3c9d-4f2a-4d5e-9c1a-2b3f7a8e5c4d
Content-Type: application/json

{"long_url": "[https://example.com/very-long-url](https://example.com/very-long-url)"}

Server logic (all in Redis, ~1ms overhead):

1. On POST, hash the key + user_id → Redis lookup
2. If found → return the previously-generated response (identical body, 201)
3. If not found → do the create, cache {key_hash: response} in Redis with 24-hour TTL

Why 24 hours? Long enough to survive mobile network issues + client retries. Short enough that Redis memory footprint is bounded.

Why this matters: on flaky mobile networks, the client might retry a POST that already succeeded (response was lost in transit). Without an idempotency key, we create two short_codes for one URL. With it, retries are safe — same key returns same short_code.

References: RFC draft-ietf-httpapi-idempotency-key-header (in-progress IETF standard, 2024); Stripe Idempotent Requests documentation.

Endpoint 2: GET /r/{code} — the redirect path (the important one)

This is 99% of your traffic. Every design decision here compounds. Get it wrong, and the wrong answer echoes across billions of requests.

Why /r/{code} and not just /{code}?

The /r/ prefix separates the redirect route from the API route so the load balancer, CDN, and reverse proxy can route them differently:

• /r/* → CDN + specialized redirect service, aggressive caching, short-lived TLS termination
• /v1/* → API service, no caching, longer connection reuse, different rate limits

Real-world example: [bit.ly/aB3xY9](https://bit.ly/aB3xY9) — Bit.ly uses the bare host + code, but then their edge routes it to a redirect-optimized backend. Same pattern, different path prefix.

The single most-probed API decision: 301 vs 302 vs 307 vs 308

This is where every URL shortener candidate gets tested. Here's the full comparison table with RFC citations:

Note on method preservation: RFC 9110 §15.4.2 documents that historically many clients rewrote POST → GET on 301/302 despite RFC 7231's earlier intent — which is why 307 and 308 were introduced to explicitly preserve the method. For URL shortener (which handles GET redirects only), method preservation is a non-issue, and 302 remains the standard choice.

What each code MEANS to a browser:

• 301 Moved Permanently: the browser records "sysd.link/aB3xY9 → example.com forever." Next time the user clicks the same short URL, the browser doesn't even ask your server — it goes straight to example.com. You never see the click. Your analytics undercount by 60-90% depending on browser cache lifetime.
• 302 Found: the browser records "sysd.link/aB3xY9 → example.com right now, ask again next time." Every click hits your server. Analytics work. Bandwidth cost slightly higher.
• 307 Temporary Redirect: same as 302 but method-safe (a POST stays a POST). Irrelevant for URL shortener because we only handle GETs.
• 308 Permanent Redirect: same as 301 but method-safe. Irrelevant here for the same reason.

Which does the URL shortener pick — and defend?

Default answer: 302. Because we want:
1. Analytics that work. Every click counted. If we sell "click-tracking analytics" as a feature (Bit.ly Pro's core value proposition), we MUST see every click.
2. The ability to retarget a short_code. If the destination URL changes (owner rotates a marketing campaign), the new destination takes effect immediately. With 301, browsers keep sending users to the old URL for days or weeks.
3. A/B testing capability. With 302, we can send 50% of clicks to variant A, 50% to variant B, and the destination decision happens per-request. With 301, the browser has already cached one destination.

When 301 is the right answer: ultra-high-volume redirects where every redirect hitting your server is a cost problem (e.g. hyperlinks from a search engine to canonical pages). Not the URL shortener case.

What Bit.ly actually does

Per Bitly's official support docs (support.bitly.com/hc/en-us/articles/230897368) as of 2024-2025, Bitly's default is 301 (Permanent Redirect) for standard short links — chosen for SEO, browser cache savings, and edge caching efficiency. But — and this is where the folklore gets fuzzy — Bitly ALSO serves 302 (Temporary Redirect) for any link where the destination URL is editable, dynamic, or a file-sharing target that may move (Google Drive links, editable custom links, some paid-plan features).

Empirical check (do this yourself, it's the interview signal that separates candidates who researched from candidates who parrot tutorials): create a fresh short URL on Bitly, hit it with curl -I, and inspect the response. On many accounts today you'll see HTTP/2 302 — because Bitly's newer default treats freshly-created links as potentially editable until the account tier upgrades them to permanent.

Interview honesty: this nuance is a great signal to bring up. "Bitly's docs say 301, but I tested and got 302 on a fresh link — likely because Bitly treats editable links as temporary. Both are valid; the tutorial claim 'Bitly uses 301' is simplified." That answer is worth 3 points of extra depth.

The "301 + pixel-tracking wrapper" pattern — a general technique, not exclusively Bitly

The "301 + JS-wrapper pixel" pattern is a well-known technique in URL-shortener design circles for combining 301's browser-cache savings with 302-like analytics accuracy. It's frequently attributed to Bitly in system-design blog posts (Educative, various Medium articles), but I could not find primary Bitly engineering documentation that confirms this specific implementation is deployed at bit.ly today.

Treat it as a design pattern, not a company case study. The mechanics below are worth studying because they teach a real trade-off; the "Bitly does this exactly" attribution is folklore that this course chooses not to propagate.

The trade-off cocktail:
- ✓ Reduces server load ~90% (repeat clicks hit browser cache after first hit)
- ✓ Analytics still work (pixel fires on wrapper page render)
- ✗ Adds ~50-200ms of latency (wrapper page render + JS execution before nav)
- ✗ Doesn't work if user's browser blocks JS/pixels (privacy extensions)
- ✗ Wrapper HTML is a distinct URL — bookmarks + link-preview crawlers see it, not the destination

Do NOT propose this in an L4 interview. It's an L6-scale optimization that's genuinely brilliant for extreme-volume shorteners with monetized analytics, but naive to reach for at 10K RPS when 302 is fine. Interviewers who know URL shorteners well have seen this "cool hack" proposed 100 times by candidates who read the same blog post — leading with it signals derivative thinking, not depth.

Who actually uses which redirect code — the real-world table

The "301 vs 302 vs 307 vs 308" question shows up in every senior-level HTTP interview. The RFCs define the semantics; production systems reveal what those semantics buy in practice. Study this table before the interview — it's what separates candidates who've read RFCs from candidates who've operated infrastructure:

The 3-line RFC-timeline explanation:

• RFC 2616 (1999) — 301/302 ambiguous about method preservation. Real browsers demoted POST→GET on both. Devs relying on POST-preservation got burned silently.
• RFC 7231 (2014) — codified 307 as "temporary redirect with method preservation." Fixed the missing primitive.
• RFC 7538 (2015) — codified 308 as "permanent redirect with method preservation." Fixed it for the permanent case.
• RFC 9110 (2022) — current HTTP semantics spec. Consolidates + clarifies but doesn't change the 4-code taxonomy.

Rule of thumb for interviews:

• GET-only workload (URL shortener, static site canonicalization, blog post migrations): 301 or 302, based on caching preference. 307/308 add nothing.
• Anything with POST/PUT/DELETE that might redirect (API gateways, payment flows, admin panels): 307 (temporary) or 308 (permanent). Never 301/302 — you'll silently lose write payloads.
• Serving both: use different codes per route. There's no rule that a service uses only one.

The precise Cache-Control behavior — the L6 depth

Per RFC 9111 (HTTP Caching, 2022) §4.2.2, responses with certain status codes are cacheable by default absent explicit Cache-Control — this includes 200, 203, 204, 206, 300, 301, 404, 405, 410, 414, 501. 302 is NOT in this default-cacheable set — a browser will not cache it unless the response includes Cache-Control: max-age=N.

For URL Shortener, the practical setting is:

http
HTTP/1.1 302 Found
Location: [https://example.com/very-long-url](https://example.com/very-long-url)
Cache-Control: no-cache
X-Analytics-Event: click-recorded

The Cache-Control: no-cache is belt-and-suspenders — even browsers that decide to cache 302 by mistake will re-validate on next click.

References: RFC 9110 (HTTP Semantics, 2022), RFC 9111 (HTTP Caching, 2022), RFC 7538 (308 Permanent Redirect, 2015), MDN Web Docs — HTTP Redirects.

Where the analytics event fires

The pattern:

1. Redis lookup for short_code → get long_url
2. Fire-and-forget a Kafka event: {code, timestamp, ip_hash, user_agent, referer}
3. Return 302 with Location header

Never block the redirect on analytics. If Kafka is down, we still redirect the user; we just lose that one analytics event. The trade-off (correct latency vs 100% analytics coverage) is explicitly acceptable — RFC 3339 timestamps + at-least-once semantics on Kafka means eventual accuracy.

Endpoint 3: GET /v1/urls/{code}/stats — the analytics path

Authentication: token-based, only the creator sees stats

Return 401 Unauthorized (RFC 9110 §15.5.2) if no auth. Return 403 Forbidden (§15.5.4) if the token belongs to a different user.

http
GET /v1/urls/aB3xY9/stats HTTP/1.1
Authorization: Bearer <jwt>

Why JWT? RFC 7519 defines the token structure. We use asymmetric signing (RS256, RFC 7518 §3.3) so any service can verify without needing the private key. Best practice per OAuth 2.0 (RFC 6749) — short-lived access tokens (~15 min), refresh tokens for renewal.

Rate limit: separate bucket per user

http
HTTP/1.1 200 OK
X-RateLimit-Limit: 60
X-RateLimit-Remaining: 47
X-RateLimit-Reset: 1735689600

Headers per the informal-but-widely-adopted RateLimit convention (draft-ietf-httpapi-ratelimit-headers, IETF in-progress standard). Bucket per user_id, not per IP — a browser tab hammering stats shouldn't rate-limit other users behind the same corporate NAT.

Cross-cutting decision 1: API versioning strategy

Three options, all valid, one right for us:

Recommendation: URL path. Reasoning:
- 90% of REST APIs in production use this (GitHub API, Stripe API, Twilio API, Twitter API, Spotify API — cite as needed)
- CDN caches work correctly (each version has a distinct cache key)
- Devtools users immediately see the version in the URL
- Deprecation is explicit — /v1/* returns Deprecation header per RFC 8594

Antipattern to avoid: never version APIs implicitly ("the endpoint changed last Tuesday"). Explicit versioning is a contract.

References: RFC 9110 §12 (Content Negotiation), RFC 8594 (Deprecation header, 2019), the "Web API Design" cookbook by Brian Mulloy (apigee.com, e-book), major public API docs (GitHub, Stripe).

Cross-cutting decision 2: Authentication strategy per tier

Three tiers, three auth models:

Why three tiers? Growth funnel. Anonymous is free trial (viral onboarding). API key is developer adoption. OAuth is paid tier with personalized product.

The critical L5+ point: authentication is a rate-limiting axis, not just a security axis. Anonymous traffic is rate-limited per IP; authenticated traffic is rate-limited per identity. This changes DDoS strategy — you can't ban an IP without blocking a whole corporate network, but you can ban an API key instantly.

References: RFC 6749 (OAuth 2.0, 2012), RFC 7519 (JWT, 2015), RFC 6750 (Bearer Token Usage), OpenID Connect Core 1.0 (openid.net/specs/openid-connect-core-1_0.html).

Cross-cutting decision 3: Rate limiting

Three algorithms (see also Cloudflare's engineering blog "How we built rate limiting capable of scaling to millions of domains" at blog.cloudflare.com):

Recommendation for URL Shortener: token bucket. Simplest to implement (INCR + EXPIRE), acceptable precision, cheapest on Redis. Return 429 Too Many Requests (RFC 6585 §4) with a Retry-After header (RFC 9110 §10.2.3) when exceeded.

Example:

http
HTTP/1.1 429 Too Many Requests
Retry-After: 42
X-RateLimit-Limit: 60
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1735689642

{"error": "rate_limit_exceeded", "retry_after_seconds": 42}

References: RFC 6585 (Additional HTTP Status Codes, 2012), RFC 9110 §10.2.3, Cloudflare Engineering Blog on rate limiting, AWS API Gateway documentation on throttling.

Cross-cutting decision 4: CORS (Cross-Origin Resource Sharing)

Per the W3C CORS specification (fetched from fetch.spec.whatwg.org, formerly W3C REC-cors-20140116):

• /v1/* endpoints: enable CORS via Access-Control-Allow-Origin: * (for public shortening endpoint) or specific origins (for authenticated stats)
• /r/* redirect endpoint: do not enable CORS. These are top-frame navigations, not XHR/fetch requests. Enabling CORS here signals attackers you accept cross-origin requests to your redirect endpoint (rarely useful, sometimes exploited).

Preflight caching: Access-Control-Max-Age: 86400 (1 day) so browsers don't preflight every request.

References: WHATWG Fetch Standard (fetch.spec.whatwg.org) — the current authoritative source for CORS, superseding W3C CORS REC.

The full interview soundbite

When the interviewer asks "walk me through your API design decisions":

"Three endpoints — POST /v1/urls returning 201 with Location header, GET /r/{code} returning 302 with Cache-Control: no-cache so we see every click, and GET /v1/urls/{code}/stats behind JWT auth per RFC 7519. Per RFC 9110 §15.4.3, 302 is the correct choice over 301 because we're a URL shortener with analytics as a product feature — 301 lets browsers cache the redirect and we lose 60-90% of clicks. 307/308 add method preservation which is irrelevant here since we only serve GETs. Idempotency via the client-provided Idempotency-Key header, dedup'd in Redis with 24h TTL — following the Stripe pattern that's now on IETF standards track. Versioning in the URL path — /v1/ — because it's cacheable per-version and every major public REST API uses it (Stripe, GitHub, Twilio). Three auth tiers — anonymous (60/hr per IP), API key (1000/hr per key), OAuth 2.0 (unlimited per user) — because auth is our rate-limiting axis, not just security."

That's an 80-second answer that shows you've read the specs.

References — the master list for this chapter

• RFC 9110 — HTTP Semantics (2022): rfc-editor.org/rfc/rfc9110 — the current authoritative spec for status codes, methods, headers, redirects.
• RFC 9111 — HTTP Caching (2022): rfc-editor.org/rfc/rfc9111 — cache-control semantics, default cacheability.
• RFC 7538 — 308 Permanent Redirect (2015): rfc-editor.org/rfc/rfc7538 — introduced 308 alongside RFC 7231's 307.
• RFC 6585 — Additional HTTP Status Codes (2012): rfc-editor.org/rfc/rfc6585 — 429 Too Many Requests.
• RFC 6749 — OAuth 2.0 (2012): rfc-editor.org/rfc/rfc6749.
• RFC 7519 — JSON Web Token (2015): rfc-editor.org/rfc/rfc7519.
• RFC 6750 — OAuth 2.0 Bearer Token Usage (2012): rfc-editor.org/rfc/rfc6750.
• RFC 8594 — HTTP Deprecation Header (2019): rfc-editor.org/rfc/rfc8594.
• draft-ietf-httpapi-idempotency-key-header — IETF in-progress spec on Idempotency-Key: datatracker.ietf.org/doc/draft-ietf-httpapi-idempotency-key-header/
• draft-ietf-httpapi-ratelimit-headers — IETF in-progress spec on RateLimit headers: datatracker.ietf.org/doc/draft-ietf-httpapi-ratelimit-headers/
• WHATWG Fetch Standard — CORS authoritative spec: fetch.spec.whatwg.org
• OWASP Top 10 2021 — A03:2021 Injection (javascript: / data: URI risks): owasp.org/Top10/A03_2021-Injection/
• Stripe Idempotency Documentation: stripe.com/docs/api/idempotent_requests
• Cloudflare Rate Limiting Engineering Blog: blog.cloudflare.com — search "rate limiting"
• MDN Web Docs — HTTP Redirects: developer.mozilla.org/en-US/docs/Web/HTTP/Redirections

Read these primary sources at least once. When an interviewer probes a specific RFC section number, the strongest signal you can give is "yes, I've read §6.4.3." That's the difference between reading blogs and reading standards.

Here's a fact that will surprise you: the URL shortener data model is just three columns. short_code, long_url, created_at. Optionally a fourth: expires_at.

That's it. Three columns, one table, one primary key, one index.

But: look at how much you can build with three columns. Bit.ly does exactly this. So does TinyURL. So do all the URL shorteners you've ever used. When someone asks "should we use MongoDB because we might add fields later?" the answer is: no, just ALTER TABLE. MySQL does it in seconds.
## The schema visualized

Here it is as an interactive schema explorer — click the "deferred" tables to see FK relationships light up, hover columns for type + constraint details, and adjust the storage-math slider to see how many shards you need at any DAU:

Read the diagram like this:

• PK = primary key (unique, indexed).
• FK = foreign key (references another table's PK).
• UK = unique constraint (indexed).
• The three "deferred" tables (users, teams, analytics_events) exist as columns/FKs in your head so the growth path stays smooth, but you don't build them at L4.

What this makes concrete that a static ASCII sketch glosses over: the exact column types, PK/FK/UK constraints, and cardinality of every relationship. In an interview, drawing this level of detail signals "I've built one of these before" — not just "I've read about it."

The interesting decisions in the data model aren't about what columns to have — they're about:

1. What's the primary key? A random string. Not an auto-increment counter (leaks growth rate and creation time). Not a UUID (too long for a short URL).

1. How do we index? Primary key on short_code (obvious). Optional index on created_at for retention cleanup.

1. What's the size math? 12 bytes for short_code + 200 bytes avg for long_url + 8 bytes timestamp = ~220 bytes per row. At 1M writes/day for 10 years = 3.6B rows × 220 bytes = ~800GB. Fits in one MySQL. No sharding needed for a decade at this rate.

Why this schema is a perfect fit for MySQL (the clustered-index advantage)

Here's a MySQL-specific detail that pays off enormously for this workload: MySQL InnoDB stores the row data INSIDE the primary-key B+tree. The PK is called a clustered index — the leaf pages of the B+tree contain the actual row data (short_code, long_url, created_at), not just a pointer.

That means every redirect query — SELECT long_url FROM urls WHERE short_code = ? — traverses the B+tree exactly once, and the answer is right there in the leaf. One I/O per warm lookup. No secondary index dereference.

Compare to Postgres, where the primary key is a separate B-tree that points into a heap file. A cold lookup is 2 I/Os: index → heap. Twice the I/O cost. On the redirect hot path where 99% of traffic is PK lookups, MySQL's clustered index is a legitimate structural advantage.

Practical implication for the derivation in Chapter 4.75: MySQL's warm-hit cost is ~40µs vs Postgres's ~50µs. Small in isolation, meaningful at 100K QPS.

When it hurts: if you add secondary indexes (say, on created_at for retention scans), every secondary-index lookup has to dereference through the PK to reach the row. Two I/Os. But for our schema, secondary indexes are optional and rarely scanned on the hot path.

The actual CREATE TABLE (with reasoning per column)

Here's the exact DDL. Every constraint is deliberate — I'll explain each one:

sql
CREATE TABLE urls (
  short_code    CHAR(7)      NOT NULL,
  long_url      VARCHAR(2048) NOT NULL,
  created_at    TIMESTAMP(3) NOT NULL DEFAULT CURRENT_TIMESTAMP(3),
  expires_at    TIMESTAMP(3) NULL,
  PRIMARY KEY (short_code),
  INDEX idx_expires (expires_at)          -- optional; only if you TTL-delete
) ENGINE=InnoDB
  DEFAULT CHARSET=utf8mb4
  ROW_FORMAT=DYNAMIC
  KEY_BLOCK_SIZE=8;

Column-by-column reasoning:

Table-level options:

• ENGINE=InnoDB — the only serious choice. MyISAM has no crash recovery.
• CHARSET=utf8mb4 — supports emoji-in-URLs (yes, that's a thing since 2018). utf8 (MySQL's 3-byte broken variant) fails on 4-byte codepoints.
• ROW_FORMAT=DYNAMIC — variable-length columns stored on overflow pages when they don't fit; efficient for our long_url mix.
• KEY_BLOCK_SIZE=8 — 8KB compressed page. Halves storage for the primary key B-tree in exchange for ~2% CPU. Reference: MySQL InnoDB Table Compression.

What we deliberately did NOT add (and why):

• `INDEX idx_long_url` — no. Reverse lookups (URL → codes) are 1 in 10,000 requests, done from analytics dashboards, not the hot path. Adding this index doubles write cost.
• `user_id BIGINT` — no at L4. Add it when you need auth/analytics — schema migration via online tools is safe (See pt-online-schema-change).
• `click_count INT` — DO NOT DENORMALIZE. Every click would UPDATE this row → hot row contention → dead system. Click counts live in a separate analytics pipeline (Chapter 8). Reference: Facebook's TAO paper — they learned this the hard way with the "like count on the post" problem.
• `is_deleted BOOLEAN` — no soft-delete. Just HARD DELETE. Soft-delete is a footgun that grows the table indefinitely. If you need audit, log deletes to a separate append-only table.

The lookup flow — every step, every I/O, every microsecond

Here's what happens end-to-end when a browser hits https://sh.rt/aB3xY9k:

Step-by-step trace:

text
[1] Browser
    → GET /aB3xY9k HTTP/1.1
    → Host: sh.rt
    | ~5 ms  (LB to app server, in-region)

[2] Load balancer
    → hash consistent (based on short_code) → app server pod
    | ~0.1 ms

[3] App server
    → Parse "aB3xY9k" from URL path
    → cache_hit = redis.get("url:aB3xY9k")   # Chapter 6
    → if cache_hit: skip to [7]
    | ~0.3 ms (Redis in-region hit)

[4] MySQL query planner
    → SELECT long_url FROM urls WHERE short_code = 'aB3xY9k'
    → Planner: PK lookup, choose clustered-index seek
    | ~5 μs

[5] InnoDB buffer pool lookup
    → hash "aB3xY9k" against buffer pool index
    → 90% hit rate for warm data
    | Warm: ~40 μs   Cold: ~1 ms (page from disk)

[6] Clustered B+tree traversal
    → 4 levels deep for 3.6B rows: root → internal → internal → leaf
    → Each level = 1 pointer follow in-memory (buffer pool)
    → Leaf page contains the row directly (short_code, long_url, created_at)
    → NO secondary index dereference (clustered!)
    | ~20 μs

[7] App server
    → Build HTTP 302 response
    → Location: {long_url}
    → Cache-Control: private, max-age=90
    | ~50 μs

[8] Browser
    → Receives 302
    → Fires GET on long_url
    | Total end-to-end: ~5-6 ms warm, ~7-8 ms cold

Latency budget breakdown (warm path, 90% of traffic):

Interview soundbite: "The clustered B+tree is why MySQL is our right choice here — the leaf page IS the row, so a warm PK lookup is one buffer-pool hit at ~40µs. If we went with PostgreSQL, the PK is a separate B-tree that points to a heap tuple — cold lookups pay 2 I/Os instead of 1. At 100K QPS that difference is real: it's the reason Uber, Pinterest, GitHub, Shopify all default to MySQL for hot-key workloads. The remaining latency is network — the hot path is ~99% network, ~1% database."

The write flow (for completeness)

Symmetric for POST /v1/urls:

text
[1] Browser POST /v1/urls {long_url: "https://..."}
[2] LB → App server pod
[3] App generates short_code (Ch 4.5 Approach 4 = KGS pop)
[4] MySQL: INSERT INTO urls (short_code, long_url) VALUES (?, ?)
    → PK B-tree insert = 1 page dirty
    → Redo log fsync = 1 IOPS
    → Binlog fsync = 1 IOPS (Multi-AZ)
    | ~2 ms (durable commit)
[5] Redis: SET url:{short_code} = long_url TTL 24h
    | ~0.3 ms
[6] App returns 201 Created + short_url
    | Total: ~5-7 ms

Why writes are slower than reads: 2× fsync (redo + binlog) + PK B-tree page-dirty + optional cache warm. Read = 1 buffer-pool hit (no disk).

Optimization decisions I would NOT recommend

• Cache the row in memcached AND Redis — dual-cache adds complexity + stale-cache bugs. Pick one.
• Materialize URL parse in a column — some tutorials suggest storing domain, path, query_string split out. Don't. Waste of space, breaks URL round-tripping (URL encoders/decoders differ).
• Use INT for short_code — you'd need to base62-encode on every read. Wastes CPU for zero storage gain vs CHAR(7).
• HASH partition by short_code first byte — premature. At 800GB single MySQL handles it. Partition when you have real evidence, not conjecture.

Table design references

• MySQL 8.0 InnoDB Storage Engine — dev.mysql.com/doc/refman/8.0/en/innodb-storage-engine.html — the clustered-index architecture.
• MySQL InnoDB Table Compression — dev.mysql.com/doc/refman/8.0/en/innodb-table-compression.html — KEY_BLOCK_SIZE reference.
• Uber's Postgres→MySQL migration — eng.uber.com/postgres-to-mysql-migration — clustered-index advantage discussed.
• Facebook TAO paper — research.facebook.com/publications/tao — why click_count denormalization killed the like-button.
• pt-online-schema-change — docs.percona.com/percona-toolkit/pt-online-schema-change.html — how to add columns to a 3.6B-row table without downtime.

Senior insight: the data model is the second-hardest thing to change in production. Only the API is harder. If you design it wrong, migration at 1B rows takes 3 months and 4 outages. So spend time here. Look at the model below and ask yourself: if I had to serve 100x more traffic, would this schema hold up? If yes, move on. If no, redesign now.

Read this carefully. Short-code generation is the single hardest problem in the URL shortener design, and 90% of candidates fumble it. Not because it's obscure — because they treat it as a one-liner ("just hash the URL") when it's actually 5 nested design decisions.

If you get this wrong, the interviewer will drill into it and expose the gap. If you get it right, they'll believe everything else you say. So we're going to spend 18 minutes here.

The requirements (what "good" looks like)

A short_code must be:

1. Unique — no two URLs share a code
2. Unpredictable — attackers can't guess the next code (scraping, enumeration attacks)
3. Short — 6-8 chars typical (that's the whole product's value proposition)
4. Cheap to produce — no expensive RPCs on the create path
5. Collision-free at scale — at 1B URLs the collision handling can't be O(N)
6. Consistent across regions — two data centers can't hand out the same code

Every approach below trades some of these off. Your job in the interview is to state which trade-off you're accepting and why.

The character-space math (this is the derivation you MUST know)

You get to pick your alphabet:

• base10 [0-9] = 10 chars — human-readable but 10 chars is 10 chars, code length is huge
• base16 [0-9a-f] = 16 chars — hex, still short-alphabet
• base36 [0-9a-z] = 36 chars — url-safe, case-insensitive
• base62 [0-9a-zA-Z] = 62 chars — the standard for URL shorteners (case-sensitive, URL-safe)
• base64url [0-9a-zA-Z_-] = 64 chars — slightly denser but _ and - cause copy-paste confusion

Everyone in the industry uses base62. Bit.ly, TinyURL, goo.gl (RIP), t.co, ow.ly — all base62. Follow the convention.

Now the math. Given base62 and code length L, the total code space is 62^L:

Here's what that growth looks like — the choice of code length is a fundamentally exponential decision. Each additional character multiplies the total code space by 62×, adding roughly 50 years of runway at typical creation rates.

Real-world creation rates & runway (6-char base62 sweet spot):

Interpretation: 6 chars is the industry sweet-spot. Below that = you'll run out. Above that = you're paying URL-length tax for zero benefit.

Interview soundbite: "I'd start with 6 chars — 56 billion codes handles 10 years at 5M creates/day. If growth exceeds forecast we can extend to 7 chars without changing the algorithm — new URLs just get longer codes."

How base62 encoding actually works — the mechanics you MUST know

Every previous "we base62-encode 6 chars" line has waved hands at the actual algorithm. Here it is in detail. Interviewers will drill in on this because it's a genuine "did you build one or read about one?" test.

The base62 alphabet

Pick an alphabet — 62 unique URL-safe characters. Two common orderings:

• `0-9A-Za-z` → "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" (Bit.ly-style, digits first)
• `A-Za-z0-9` → "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" (some libraries)

The choice is arbitrary — but permanent. Once you deploy, existing codes are indexed by the alphabet you chose. Changing it means every stored code decodes to a different value. So pick, document, and never change.

The encoding algorithm — repeated division by 62

Given a numeric value n (integer, 32-bit, 64-bit, whatever), the algorithm:

text
    encode(n):
      digits = []
      while n > 0:
        remainder = n mod 62
        digits.append(alphabet[remainder])
        n = n div 62
      return reverse(digits)

Concrete worked example — encode the counter value `12,345,678` with alphabet 0-9A-Za-z:

Read the collected digits in reverse: p, n, g, 6 → `png6`.

That's a 4-character code. Not 6. Which brings us to the padding problem.

The padding problem — small counters produce short codes

If your auto-increment counter starts at 1, then:
- encode(1) → "1" (1 char)
- encode(62) → "10" (2 chars)
- encode(3,844) → "100" (3 chars)
- encode(12,345,678) → "png6" (4 chars)
- encode(916,132,832) (= 62^5) → "100000" (6 chars — first time we hit 6 chars naturally)

Two fixes:

Fix A — Zero-pad on the left.

text
    pad_left(encode(n), 6, alphabet[0])
    // encode(12345678) → "png6" → pad → "00png6"

Guarantees fixed length. But early codes are ugly ("000001", "000002") and predictable — attacker who sees "000042" can guess "000043" exists.

Fix B — Offset the counter by 62^5.

text
    initial_counter = 62^5 = 916,132,832
    // encode(counter) is guaranteed ≥ 6 chars from the start
    // encode(916,132,833) → "100001" (6 chars)
    // encode(12,345,678 + 916,132,832) → "1png6" nope let me recompute
    //   = encode(928,478,510) → "1p6QMc" or similar 6-char result

Fixed-length forever, no leading zeros. This is what Bit.ly Classic and TinyURL do.

The random-bytes → base62 problem (modulo bias)

For Approach 1 (random + collision check), you generate random bytes and convert to a 6-char base62 code. If you're careless, you get modulo bias — some characters appear more often than others.

Why it happens: 62^6 = 56,800,235,584. If you generate 32 random bits (2^32 = 4,294,967,296), you have only 7.5% of the target space — you literally CAN'T produce most 6-char codes. If you generate 64 random bits (2^64 = 18,446,744,073,709,551,616) and take mod 62^6, you get uniform distribution because 2^64 / 62^6 = 324,752,533 codes per bucket with a tiny sub-bucket remainder that would bias the last ~5.4M codes IF you didn't discard them.

The correct algorithm:

text
    generate_random_6char():
      SPACE = 62^6                       // 56,800,235,584
      MAX = 2^64 - (2^64 mod SPACE)      // largest multiple of SPACE that fits in 64 bits
      loop:
        bytes = crypto.randomBytes(8)    // 64 random bits
        n = uint64_from_bytes(bytes)
        if n < MAX:                      // rejection sampling — reject the biased tail
          return pad_left(encode(n mod SPACE), 6, alphabet[0])
        // else retry — this happens < 0.001% of the time in practice

Without rejection sampling, ~5.4M of the 2^64 values map to the "over the multiple" range and slightly bias 5.4M codes toward being more likely. In practice this is imperceptible for our use case (56 billion codes, imperceptible bias), but the rejection-sampling loop is the correct algorithm and adds ≤ 1 ns per generation.

The decoding algorithm — base62 → integer (for Approach 2)

If you use counter-based codes and want to recover the counter from a short_code (for analytics, debugging), the reverse works:

text
    decode(code):
      n = 0
      for char in code:
        n = n * 62 + alphabet.index_of(char)
      return n

For alphabet 0-9A-Za-z and code "png6":
- p = 51 → n = 0 × 62 + 51 = 51
- n = 49 → n = 51 × 62 + 49 = 3,211
- g = 42 → n = 3,211 × 62 + 42 = 199,124
- 6 = 6 → n = 199,124 × 62 + 6 = 12,345,678 ✓

Trivia: you can only decode counter-based codes back to a counter. Random-generated codes decode to a random number — meaningless. That's a security feature: random codes don't leak "how many URLs exist" or "creation order."

Concrete code samples (production-ready)

Python (Approach 2 — counter-based):

python
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def encode(n: int, min_length: int = 6) -> str:
    if n == 0:
        return ALPHABET[0] * min_length
    digits = []
    while n > 0:
        digits.append(ALPHABET[n % 62])
        n //= 62
    return "".join(reversed(digits)).rjust(min_length, ALPHABET[0])

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

JavaScript / TypeScript (Approach 1 — random with rejection sampling):

typescript
const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const SPACE = 62n ** 6n;  // 56,800,235,584
const MAX_U64 = 2n ** 64n;
const CUTOFF = MAX_U64 - (MAX_U64 % SPACE);

export function generateShortCode(): string {
  while (true) {
    const bytes = crypto.getRandomValues(new Uint8Array(8));
    let n = 0n;
    for (const b of bytes) n = (n << 8n) | BigInt(b);
    if (n < CUTOFF) {
      let value = n % SPACE;
      const digits: string[] = [];
      for (let i = 0; i < 6; i++) {
        digits.push(ALPHABET[Number(value % 62n)]);
        value /= 62n;
      }
      return digits.reverse().join("");
    }
    // < 0.0000001% retry rate — imperceptible
  }
}

Go (Approach 1 with crypto/rand):

go
import (
    "crypto/rand"
    "encoding/binary"
    "math/big"
)

const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

func generateShortCode() string {
    space := new(big.Int).Exp(big.NewInt(62), big.NewInt(6), nil)  // 62^6
    for {
        var b [8]byte
        _, _ = rand.Read(b[:])
        n := new(big.Int).SetUint64(binary.BigEndian.Uint64(b[:]))
        maxU64 := new(big.Int).Lsh(big.NewInt(1), 64)
        cutoff := new(big.Int).Sub(maxU64, new(big.Int).Mod(maxU64, space))
        if n.Cmp(cutoff) < 0 {
            value := new(big.Int).Mod(n, space)
            code := make([]byte, 6)
            div := big.NewInt(62)
            for i := 5; i >= 0; i-- {
                var mod big.Int
                value.DivMod(value, div, &mod)
                code[i] = alphabet[mod.Int64()]
            }
            return string(code)
        }
    }
}

Interview soundbite for the mechanics

"For a 6-char base62 code from an integer counter, the algorithm is repeated division by 62 — take remainder, index into a 62-char URL-safe alphabet, right-to-left. To guarantee exactly 6 chars, either pad-left with alphabet[0] or offset the counter to start at 62^5. For random-generated codes, I generate 64 bits, use rejection sampling to avoid modulo bias, and mod by 62^6. Alphabet order is arbitrary but permanent — once shipped, don't change it or existing codes decode wrong."

Now you can defend the mechanics against any interviewer follow-up. Back to the approaches.

Approach 1: Random + collision check

The naive approach. On each create:

sql
LOOP:
  code = base62(random 32 bits)  -- 6 chars from 2^32 = 4B space, need trim to 62^6
  INSERT INTO urls (short_code, long_url) VALUES (code, $url)
    ON DUPLICATE KEY UPDATE short_code = short_code
  IF rows_affected == 1: return code
  ELSE: continue LOOP
END

Collision probability (the birthday paradox — critical!): in a space of N codes with K URLs already stored, probability of collision on the next insert ≈ K/N.

For 6-char base62 (56.8B codes):

Here's the same math as a growth curve — collision probability grows LINEARLY with URLs stored (that's what makes it manageable at first, then sudden):

Reading the curve:

Rule of thumb: Approach 1 (random + collision check) works UP TO ~1% of code space filled (for 6-char = 570M URLs). Beyond that, escalate to KGS pre-generation.

Verdict: works up to ~100M URLs comfortably. Above that, the retry loop becomes a MySQL write-amplification problem (each collision = 1 wasted write + 1 wasted index probe).

Where this wins: L4 (10K RPS), small shorteners, MVP. Bitly used this for its first years.

Where this loses: L6+ scale. You DO NOT want a stampede of collision retries during a viral event.

Approach 2: Counter + base62 (the "Bit.ly Classic")

Every create gets an auto-increment ID. Encode the ID in base62.

```
INSERT INTO urls (long_url) VALUES ($url) RETURNING id;
short_code = base62_encode(id);
UPDATE urls SET short_code = $code WHERE id = $id;
```

Pros:
- Zero collision probability (integer PK is unique by definition)
- Codes are sequential — good for range scans, backups, retention
- Simple to reason about

Cons — and these are big:
- Enumeration attack: knowing code abc123 tells you abc124 exists. Scrapers dump your entire URL corpus in 24 hours.
- Growth-rate leak: a competitor can shorten one URL a day for a month. Diff the codes. Now they know your daily create volume.
- Single writer bottleneck: the counter is one row. Every create takes an exclusive lock. At 100K creates/sec you saturate the counter row.
- Cross-region coordination: two regions can't hand out the next counter value independently.

Bit.ly's actual fix (2010-era): they used counter + XOR with a secret salt before base62. That obfuscates predictability. Still single-writer, still cross-region, but not enumerable.

Where this wins: L4 single-region, when you can accept the enumeration risk. Historical Bit.ly.

Where this loses: anything with adversarial users, anything multi-region, anything above 10K creates/sec.

Approach 3: Hash-based (MD5 or SHA-256 → truncate → base62)

Deterministic function of the URL:

```
raw = MD5(long_url + random_salt).digest() -- 16 bytes
code = base62(raw[0:6]) -- take first 6 bytes → base62
try_insert(code, long_url)
if conflict:
regenerate_with_different_salt()
retry
```

Same URL → same code: is this a feature or a bug?
- Feature at L4-L5: users who shorten the same URL twice get one code (nice UX, saves storage).
- Bug at L6+: users EXPECT that shortening the same URL twice gives two codes (different analytics buckets, different expiration).

The industry answer: randomize the salt on every create, so URL → many possible codes. Only dedupe when you want to.

Collision probability: identical to Approach 1's birthday paradox — you're picking 48 bits (6 base62 chars ≈ 48 bits) from a 62^6 = 56.8B space. Same math.

Pros:
- No coordination — every server generates codes independently
- No counter row, no cross-region write coordination
- Fast (MD5 is ~500 MB/s single-threaded)

Cons:
- Still has collision-retry loop at scale
- If you skip the salt, same URL → same code — usually you WANT them distinct
- Slightly more CPU per create than Approach 2

Where this wins: L5-L6, single-region or independent multi-region, up to ~500M URLs.

Where this loses: L7 (1B+ URLs) where collision rate becomes painful.

Approach 4: Key Generation Service (KGS) — the scale winner

Pre-generate unique codes into an "available" pool. Consumers pull codes from the pool at create time. No collision at runtime.

Architecture:

• KGS worker (batch job, runs continuously): generates 100M unique codes, writes to available_codes table
• KGS server (thin API, hot path): "give me N codes." Marks them as claimed, returns them.
• URL Shortener service: on create, takes 1 code from KGS, inserts URL row with that code.

Here's the flow — as a live interactive animation. Play with the worker rate + traffic rate sliders, then try "worker fleet dies" and watch the pool drain to zero. The alert banner turns red as depth drops:

The SQL underneath the animation:

sql
-- KGS worker
LOOP FOREVER:
  code = random_base62(6)
  INSERT IGNORE INTO available_codes (code, claimed) VALUES (code, false)
END

-- KGS server (called by shortener)
UPDATE available_codes SET claimed = true, claimed_at = NOW()
  WHERE code IN (
    SELECT code FROM available_codes
    WHERE claimed = false
    LIMIT 100
    FOR UPDATE SKIP LOCKED  -- concurrent-safe claim
  )
RETURNING code;

The magic: collision handling moves from the hot path (creating a URL) to the cold path (batch pre-generation). At 100K creates/sec, all you're doing is a locked read from a "available" pool.

Pool sizing: if you generate 10M/day and consume 5M/day, pool stays healthy. Monitor SELECT COUNT(*) WHERE claimed = false and alert if it drops below 24h of forecast supply.

Fault tolerance:
- KGS server dies → shortener uses a local batch of 1000 pre-fetched codes (retry with next batch on refill)
- KGS DB dies → same fallback, plus emergency batch generation locally
- Never should the create path fail because KGS is unhealthy

Pros:
- No collision-retry on hot path (all pre-generated)
- Horizontal-scale: sharded KGS pools per region
- Predictable latency (create is 1 DB write, no retry loop)

Cons:
- Two extra services to build and operate (worker + server)
- Pool must be monitored (starve = outage)
- Slightly more complex than Approach 1-3

Where this wins: L6-L7 (1M+ creates/sec, multi-region). This is what Bit.ly moved to. This is what any serious shortener uses at scale.

KGS deep-dive: throughput, latency, and mitigation math

Before we move on, let me answer three questions every interviewer will drill on:

1. "How much can one KGS worker actually generate per second?"
2. "You added an extra network hop — what does that cost us in latency?"
3. "The pool starves — what actually happens?"

1. KGS throughput ceiling — the 3 floors

Question: Can one KGS worker keep up with 1M creates/sec?

Answer: No. Let me derive the throughput of a single KGS worker generating random 6-char base62 codes and INSERT IGNORE-ing them into MySQL:

Floor 1 — CPU cost of code generation:

• random_base62(6) = 6 × getrandom() calls + 6 × modulo ops. Modern CPUs: ~500ns per code on a c6i.xlarge (2.4 GHz). That's 2M codes/sec theoretical (single-threaded).
• With 4 worker threads on the same box → ~8M codes/sec generated, but this is CPU-only; disk is next.

Floor 2 — MySQL INSERT IGNORE throughput:

• Each generated code = 1 INSERT IGNORE against MySQL. On a db.r6i.2xlarge (8 vCPU, 64 GB RAM, 8K IOPS baseline) with a single-column PRIMARY KEY (code CHAR(6)) and no other indexes:
• IOPS floor: each batch = 1 log write + 1 data page write × 8 (batch size) → ~30K IOPS peak, exceeds 8K baseline
• Conclusion: one KGS worker + one MySQL box = ~10-30K codes/sec sustained. NOT 2M — the CPU cost was never the bottleneck; MySQL was.

Floor 3 — Consumption rate (what we need to serve):

• L5 target: 100K creates/sec = need 100K codes/sec produced sustained + ~2x overprovision for burst = 200K codes/sec.
• L6 target: 1M creates/sec = need 1M codes/sec produced + 2x = 2M codes/sec.
• Conclusion: at L5 we need ~10 KGS workers (each 20-30K codes/sec into partitioned pool tables). At L6 we need ~100 workers, sharded by code-prefix.

The scaling math for the pool table:

Interview soundbite: "One KGS worker + MySQL box sustains ~10-30K codes/sec. To feed 1M creates/sec (L6), I need ~100 KGS workers writing to a 32-shard pool table. The CPU cost of generating codes is trivial (~500ns each); the real ceiling is MySQL INSERT throughput. And at L7 you must switch to 7-char codes because 6-char space (56B) can't hold 24h of L7 pool inventory."

2. Latency cost of the extra hop — and how to hide it

The naive concern: create path was App → MySQL (2ms). With KGS it becomes App → KGS → MySQL (App) → MySQL (URL) = 4ms. Doubled the create latency!

The fix: local batch pre-fetch.

Every app server pre-fetches a batch of N codes from KGS before it needs them, holds them in memory, and consumes locally. The KGS hop happens 1 in every N creates, not every create.

Batch size math:

• App server sustains 1000 creates/sec. If it pre-fetches 100 codes, the batch lasts 100 ms.
• KGS round-trip (in-region) ≈ 1-2 ms. Amortized over 100 creates = 10-20 μs per create. That's noise vs the 2ms MySQL write.
• If batch = 10 codes → refill every 10 ms, amortized cost 100-200 μs per create. Still noise.
• If batch = 1 (worst case, no batching) → KGS hop on every create = full 2 ms per create.

Trade-off:

Sweet spot: batch = 100-1000. Latency amortization <1% AND wasted codes on crash are negligible against a 56B pool.

Interview soundbite: "The extra KGS hop looks scary but amortizes to noise with local batch pre-fetch. Batch of 100 hides the 1-2ms KGS RTT to 20μs per create — invisible in the create latency budget. The only downside is up to 100 wasted codes per app-server crash, which is 0.00000018% of the pool — irrelevant."

3. Pool starvation — what actually happens

Scenario: KGS workers stall (bug, deploy, DB failover). Pool depth drops. What breaks first?

Failure sequence:

• T=0: KGS worker fleet stops producing codes. Pool depth stops growing.
• T=+1s to T=+24h: consumption continues, pool depth decreases at 100K/sec (L5) or 1M/sec (L6).
• Alert threshold: fire alert when pool depth = 24h of forecast supply. This gives on-call 24h to intervene.
• Second alert: at 6h of supply — page loudly, escalate to secondary.
• Emergency mitigation:
• T=+pool depth 0 without mitigation: create path FAILS. Redirect path unaffected. This is a Sev-1 outage.

Pool depth alerting math:

• At L5 100K creates/sec, 24h supply = 100K × 86400 = 8.64B codes. Fire when pool < 8.64B.
• At L6 1M creates/sec, 24h supply = 86.4B codes — very close to the 56B ceiling of 6-char base62. At L6+ you MUST run 7-char codes (3.5T space) to keep 24h supply headroom.

Two extra guardrails:

1. Watchdog script runs every 5 min: SELECT COUNT(*) FROM available_codes WHERE claimed=false. If below threshold, page.
2. Circuit breaker at app-server: if KGS timeouts exceed 10/sec, flip to inline collision-check for 60s, alert.

Interview soundbite: "Pool starvation is a Sev-1 but it never surprises you — the alert fires 24h before creates fail, so you have a full business day + on-call rotation to intervene. And the app-server local batches + inline-collision fallback mean the create path degrades gracefully rather than failing outright. This is the same pattern as any pre-generated pool (Kafka partition IDs, DB sequence caches, JWT signing keys)."

KGS references

• Bit.ly Engineering blog — word.bitly.com — multi-post series on their evolution from counter → KGS.
• Percona sysbench MySQL benchmarks — percona.com/blog testing-mysql-performance-in-the-cloud — INSERT throughput numbers referenced above.
• MySQL 8.0 SKIP LOCKED semantics — dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html — the concurrent-safe claim pattern.
• Amazon Aurora IOPS baselines by instance type — docs.aws.amazon.com Aurora storage — for the 8K IOPS floor.

Approach 5: Snowflake ID (or "truncated Snowflake")

Twitter's Snowflake: 64-bit ID = 41 bits timestamp + 10 bits node + 12 bits sequence. Unique across all nodes without coordination.

For URL shortener: encode the Snowflake in base62. 64 bits = 11 base62 chars. Too long for a URL shortener.

The trick: truncate to 6-8 chars by using less-precise timestamp + smaller node/sequence bits. Example:
- 20 bits timestamp (relative to epoch, ~12 days of unique values before wrap)
- 8 bits node (256 nodes)
- 12 bits sequence per ms per node (4K creates/ms/node)
- Total: 40 bits = 7 base62 chars

Here's the exact bit-layout of that 40-bit truncated Snowflake with a region prefix so no two regions can EVER collide — visualized as an interactive SVG (hover a segment to see its role):

Reading the layout above:

Encoding math: 40 bits ÷ ~5.95 bits/char (log₂ 62) = 6.72 base62 chars → round up to 7-char short codes.

Example: 001|00010110|10111001|011001101010 → aB3xY9k

The runtime generation flow — how one ID actually gets built

The 40-bit layout above shows what an ID looks like. It does NOT show how a running server produces one when a POST /v1/urls request lands. That's a different — and equally important — visual. Step through the interactive 7-step algorithm below — try the "clock went back" and "sequence overflow" scenarios to see the 2 danger branches that cause 90% of Snowflake production incidents:

now_ms = System.nanoTime() / 1_000_000

What the flowchart makes obvious that the ASCII buries: the two branches that hide operational risk. The Step 2 decision (clock went backwards) is where 90% of Snowflake production incidents live — the fail-loud path exists explicitly so you don't silently corrupt IDs. The Step 4 → Over branch (sequence exhaustion) is the throughput ceiling — spinwait is fine at ~1μs but if you see it dominating your latency profile, you've maxed out per-node throughput and need to add nodes.

Newbie mentor commentary — read this before you code it:

1. Step 3 (the lock) is the part people skip. Under single-threaded load a Snowflake generator works without locking. Under high concurrency (typical of a production URL shortener at L5+), two threads can hit sequence++ at the exact same nanosecond, both read the same value, both write the same new value, and you get a DUPLICATE short code. This bug ships to production, causes rare mysterious 409 CONFLICT errors on retries, and takes 3 weeks to debug. Add the lock on day 1.

1. Step 4 (the sequence overflow spinwait) is the subtle correctness bug. If you generate more than 4,096 IDs in a single millisecond (which happens at 4M+ RPS per node), the sequence exhausts. Naive code overflows and duplicates last-ms IDs. Correct code spinwaits (busy-loops for ~1 microsecond) until the next millisecond and resets. Spinwait is fine at this scale because it's < 1000ns — but you must code it explicitly.

1. Step 6 (base62) has an ordering trap. The alphabet you pick fixes the sort order of your short codes forever. Consistent alphabets: 0-9a-zA-Z (base62 standard), a-zA-Z0-9 (some libraries), A-Za-z0-9 (URL-safe base62). Pick one, document it, never change it.

1. Steps 1-7 must fit in <1 microsecond wall clock. Anything you add here (a database write to record the ID, a call to Redis, logging with a JSON serializer) will destroy your ID generation throughput. Log to a buffer, batch-flush. Persist the ID only when the URL insert happens downstream.

The clock-skew failure mode — Snowflake's #1 production incident

Every Snowflake deployment eventually hits this. Every one. It's the operational risk that separates "we tested Snowflake in dev" from "we ran Snowflake in production for a year." Here is what happens:

NTP resyncs your server's wall-clock. This can happen for many reasons: leap second adjustment, VM migration, hypervisor pause, NTP daemon restart. The result: your server's clock JUMPS BACKWARDS.

The failure timeline

The three survival strategies

The monitoring you must have

References for the clock-skew problem:
- Twitter Snowflake source — github.com/twitter-archive/snowflake — the original monotonic-clock implementation.
- Discord "How Discord Stores Trillions of Messages" — discord.com/blog/how-discord-stores-trillions-of-messages — includes their Snowflake variant and the operational learnings.
- Google TrueTime — cloud.google.com/spanner/docs/true-time-external-consistency — the alternative approach that Google Spanner uses (hardware clocks with bounded uncertainty).
- Kleppmann Ch 8 (Distributed Systems Trouble) — Designing Data-Intensive Applications, section on "Unreliable Clocks" — the canonical reference.

Interview soundbite for Snowflake operational risk: "The 40-bit layout is the easy part. The hard part is clock skew — NTP resync can jump your wall-clock backwards, break uniqueness guarantees, and cause silent duplicate short codes. I'd use a monotonic clock (System.nanoTime in Java, monotonic library in Go, Instant.now() with steady_clock in C++) to compute the timestamp bits — never the wall clock. If a monotonic option isn't available, I'd add a hard fail-loud check on now_ms < last_recorded_ms and monitor that counter as a critical SLO. Clock drift is Snowflake's #1 production incident cause; it needs a plan on day 1."

Pros:
- Zero coordination between nodes
- Roughly time-ordered (nice for DB clustering)
- Fits in 7 chars if you're careful

Cons:
- Timestamp wraps → collision possible if you're not careful about epoch selection
- Leaks approximate creation time (fine for shortener; problem for privacy-sensitive systems)
- Sequence bits must be sized carefully or you rate-limit yourself

Where this wins: L6-L7, multi-region, when you want no coordination and can accept the time-leak.

Where this loses: anywhere the ordering leak matters, or when 7-char codes are unacceptable.

How this evolves across scales

This is the interview soundbite you memorize:

Collision handling: what to say in the interview

The interviewer will ask: "What happens if two servers generate the same code?"

Your answer, at every level:

• L4 (Approach 1): "INSERT with / MySQL: use INSERT IGNORE /. If the insert affects zero rows, retry with a new random code. Retry cost negligible at our URL count."
• L5 (Approach 3): "Same — hash includes a random salt. On collision, regenerate with new salt. Retry loop bounded to 3 attempts before we alert."
• L6 (Approach 4/KGS): "It literally cannot happen — codes are pre-generated and marked-claimed atomically. The only failure mode is the pool starving, which we monitor and alert on 24h of headroom."
• L7 (Approach 4 sharded): "Same, plus regional pools use disjoint code prefixes (region_1 uses codes with bit 63 = 0, region_2 uses bit 63 = 1) so cross-region collision is mathematically impossible."

The five decisions summarized

Now — a warning. Do not memorize this table. Derive it. In the interview, walk the interviewer through the requirements → math → approach choice. If you memorize and they probe with "what if we needed 5-char codes?" or "what if predictability was fine?", you lose. If you derived it, you can re-derive with new constraints.

References (16 items)

• Twitter Snowflake (2010) — original engineering blog: blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake. Source for the 64-bit ID layout used in Approach 5.
• Instagram — "Sharding & IDs at Instagram" (2012): instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c. Their variant of Snowflake for photo IDs.
• Discord Snowflake documentation: discord.com/developers/docs/reference#snowflakes. Production reference implementation.
• Bit.ly — engineering blog on their short-code architecture: word.bitly.com (multiple posts across 2010-2018). Documents their evolution through counter → hash → KGS-style pool.
• Zipf, George Kingsley (1949) — Human Behavior and the Principle of Least Effort (Addison-Wesley). The origin of Zipf's law, used to justify why "top 10% of codes get 90% of traffic" is a reasonable prior.
• Birthday paradox math — Feller, W. (1968) An Introduction to Probability Theory and Its Applications, Vol. 1 (3rd ed., Wiley), Chapter II §3. Where collision probability P ≈ K²/(2N) comes from.
• WHATWG URL Standard — url.spec.whatwg.org. Authoritative reference for URL-safe character sets including base62's [A-Za-z0-9].
• MySQL 8.0 Reference Manual — INSERT syntax with IGNORE / ON DUPLICATE KEY UPDATE: dev.mysql.com/doc/refman/8.0/en/insert-on-duplicate.html. For the collision-handling semantics used in Approaches 1 and 4.
• CockroachDB `unique_rowid()` docs — cockroachlabs.com/docs/stable/AUTO_INCREMENT. Production reference for cluster-wide unique ID generation without centralized coordination.
• RFC 4122 — UUID standard (2005): rfc-editor.org/rfc/rfc4122. For comparing base62 codes against UUIDs (both mentioned in the "why not UUID" discussion).

Every previous chapter has quoted numbers at you. "10K RPS is a single MySQL + 3 app servers." "At 100K RPS the DB primary saturates at ~85% CPU." "1M RPS needs sharding."

If you're paying attention, you've been asking the right question: how do you KNOW that? Where do those numbers come from?

That's the question this chapter answers, once, from first principles. Not with a memorized table you'll forget in a week — with a framework you can re-derive on a whiteboard in front of an interviewer for ANY system.

Interviewers probe this specifically. When they ask "how do you know it's 10K RPS and not 30K?" they aren't looking for you to recall a Medium article. They're looking for you to say: "It's derived. Here's the math." Then walk them through it.

By the end of this chapter you'll be able to:

• Compute app-server RPS from CPU, latency, and concurrency
• Compute MySQL primary QPS from buffer pool hit rate and IOPS
• Compute Redis single-node QPS from memory bandwidth
• Identify which component is the bottleneck at any RPS
• Defend your capacity numbers using Little's Law + M/M/1 queueing theory
• Recognize when you've hit the queueing cliff (~80% CPU)

This is the math foundation that makes every subsequent chapter defensible.
## Section 1 — The 5 questions every capacity claim must answer

Before I quote any number, I answer these 5. If someone quotes a capacity number without answering all 5, they're guessing.

text
    ══════════ THE 5 QUESTIONS ══════════

    1. WORKLOAD
       What does ONE request do?
       (Redirect = 1 DB point-lookup + base62 decode + HTTP 302
        Checkout = 5 API calls + payment provider + inventory check)
       Different workloads have different per-request cost.

    2. HARDWARE
       What box am I running on?
       (m5.large = 2 vCPU + 8 GB RAM + gp3 3000 IOPS is very different
        from m5.2xlarge = 8 vCPU + 32 GB RAM + io2 20000 IOPS)

    3. LATENCY TARGET
       What P99 do users tolerate?
       (< 10 ms for redirect vs < 500 ms for checkout — the target
        constrains throughput more than raw CPU does, via queueing)

    4. CPU UTILIZATION TARGET
       Where does steady-state land?
       (60% is the standard target. 80% is the queueing cliff.
        Section 3 shows why.)

    5. SAFETY MARGIN
       What multiplier for the "oh no" moments?
       (1.5× for viral spikes, 2× for AZ failover absorption.
        1.0× — no headroom — is negligence.)

Rule: any capacity number you cite without answering all 5 is superstition. Interviewers hear the difference immediately.

Section 2 — Little's Law (the ONE equation you must know)

This is the single most important equation in system design. Memorize it. Use it in every interview.

text
    ══════════ LITTLE'S LAW ══════════

         L  =  λ  ×  W

    L = number of requests in the system at any moment (concurrency)
    λ = throughput (requests per second)
    W = latency (seconds per request)

    Rearranged:  λ = L / W    or    W = L / λ

Little's Law is a queueing-theory identity — it holds for ANY stable system, regardless of arrival distribution, service distribution, or scheduling. It works for a Starbucks queue. It works for a Node.js app server. It works for MySQL.

Applied to a URL Shortener app server

• Each redirect takes 10 ms end-to-end (W = 0.01 s). This includes the DB round-trip.
• One app server, sized to keep CPU at 60%, can handle 30 concurrent requests without degradation (L = 30).
• Throughput per app server = L / W = 30 / 0.01 = 3,000 RPS.

One box, three thousand RPS. That's the derivation.

Now watch what happens when latency changes:

• If latency doubles to 20 ms (something got slow — a slow DB, a GC pause, a bad query), throughput per box HALVES to 1,500 RPS.
• If latency drops to 5 ms (a warm cache path), throughput per box DOUBLES to 6,000 RPS.

This is why P99 latency and throughput are the same conversation. You cannot improve one without affecting the other. Interviewers love candidates who see this.

Applied to MySQL

• A point-lookup query (SELECT ... WHERE short_code = ?) with a warm buffer pool takes ~50 microseconds of CPU.
• MySQL can run ~40 such queries in parallel on a 2-vCPU box (each vCPU handles ~20 simultaneous "active" queries at 60% utilization).
• Throughput = 40 / 0.00005 = ~800,000 QPS theoretical on pure CPU.
• BUT: real queries have DB round-trip + connection overhead + logging. Realistic ceiling: ~20-25K QPS for warm-hit point lookups (see Section 5 for the full derivation with IOPS).

The interview soundbite

"I use Little's Law to derive throughput. L = λ × W. On my app tier with 10ms latency and 30 concurrent requests, that's 3,000 RPS per box at 60% CPU. If I need 10K RPS, I need 4 boxes (round up from 3.3 for safety). That's why I picked 3 boxes for L4 — I have 10ms latency and a small safety margin."

That soundbite ends interviews well.

Section 3 — Why 80% CPU is the queueing-theory cliff

Every senior engineer knows "don't run servers above 80% CPU." Junior engineers assume it's a rule of thumb. It's not — it's queueing theory.

For an M/M/1 queue (Poisson arrivals, exponential service times, single server), the mean response time relates to utilization U as:

text
    ══════════ THE UTILIZATION CLIFF ══════════

    mean_response_time  =  base_service_time  ×  1 / (1 - U)

    U = 0.50 (50% CPU)  →  response =  2× base   (fine)
    U = 0.60 (60% CPU)  →  response =  2.5× base (the target)
    U = 0.70 (70% CPU)  →  response =  3.3× base
    U = 0.80 (80% CPU)  →  response =  5× base   (danger zone)
    U = 0.90 (90% CPU)  →  response = 10× base   (P99 starts melting)
    U = 0.95 (95% CPU)  →  response = 20× base   (users complain)
    U = 0.99 (99% CPU)  →  response = 100× base  (dead)

    Plotted, this is a HOCKEY STICK. The knee is at ~70-80%.

This is why senior engineers target 60% CPU steady state — you have room for a 2x traffic spike before you cross the cliff. If you steady-state at 80%, one bad rollout or one AZ failover pushes you into 100x baseline latency and everything melts.

Real-world manifestation

The M/M/1 approximation is optimistic (real systems have variance beyond exponential — GC pauses, disk seeks, network jitter — so the cliff is actually WORSE than the formula suggests). Reality: at 85% CPU, real Java/Go services often exhibit 20-50x P99 latency compared to 60% CPU. This is what you see in every real incident post-mortem: "we were fine at 60% CPU, then traffic doubled and P99 went from 20ms to 3 seconds."

The interview probe

Interviewer: "Why do you target 60% CPU and not 80%?"

You: "M/M/1 queueing says mean response time is base × 1/(1-U). At 60% I'm at 2.5x base and my P99 is stable. At 80% I'm at 5x base and one hiccup — a GC pause, a slow query, an AZ failover — pushes me over the cliff. Real systems have more variance than M/M/1, so 80% in production behaves like 95% on paper. 60% gives me a 2x buffer before the cliff. That's my viral-spike headroom."

Reference: Kleinrock, Queueing Systems Vol. 1 (1975) — the foundational textbook. All the pop-science "80% CPU" wisdom traces back to this.

Section 4 — Deriving app-server RPS from scratch

Everything is a derivation. Never memorize; always compute.

Step 1 — quantify per-request CPU

For a URL Shortener redirect (GET /r/{code} → DB lookup → 302 response):

• Parse HTTP request + decode headers: ~10 µs CPU
• Await DB round-trip (5 ms, mostly wall-clock wait, ~5 µs CPU cost for context switch): ~5 µs CPU
• Deserialize DB response + build 302 with Location header: ~50 µs CPU
• Emit access log + metric: ~30 µs CPU
• Framework overhead + kernel + TCP: ~100 µs CPU

Total per request: ~200 µs CPU on a modern Go/Node/Java service.

Where does 200 µs come from? Empirical. TechEmpower Round 22 benchmarks Go on m5.large at ~30K RPS for a "single query" benchmark. 30K RPS × 200 µs = 6 vCPU-seconds/second across 2 vCPUs = 300% utilization → the benchmark runs at ~100% CPU. Dividing back: at 100% CPU, per-request cost is ~66 µs; add production overhead (logging, metrics, TLS termination) and you land at 200 µs realistic.

Step 2 — apply Little's Law

Given:
- 2 vCPUs (m5.large)
- 60% target utilization
- ~200 µs per request

CPU-bound ceiling: 2 cores × 60% ÷ 200 µs = 6,000 RPS theoretical.

Step 3 — but wait, we need concurrency to fill CPU

Each request BLOCKS on the DB round-trip (5 ms wall-clock wait). If the app were single-threaded, we could handle only 200 requests/sec (1 second ÷ 5 ms). We need concurrency.

With modern async runtimes (Node event loop, Go goroutines, Java Loom), we can hold ~25-30 concurrent requests on 2 vCPUs before CPU becomes the bottleneck.

Applying Little's Law:
- L = 30 concurrent
- W = 5 ms (DB) + 5 ms (CPU work + network) = 10 ms
- λ = L / W = 3,000 RPS realistic

Step 4 — the safety margin

At 3,000 RPS realistic with 60% CPU, we have ~40% CPU headroom. A viral spike doubling traffic pushes us to 6,000 attempted RPS → we hit the CPU wall → autoscaling kicks in and adds more boxes. Meanwhile latency spikes to ~5x baseline briefly (M/M/1 says 80% → 5x base). Users experience 50 ms P99 for 90 seconds until scaling completes. Recoverable.

Number to remember

~3,000-5,000 RPS per m5.large app server for redirect-type workloads at 60% CPU, with healthy P99 latency.

For a heavier workload (checkout with 5 downstream calls), this drops to ~500-1,500 RPS per box. Always derive from your specific workload — never assume 3K.

Section 5 — Deriving MySQL primary QPS from scratch

Now the interesting derivation. This is what breaks at 100K RPS in Chapter 6.

Step 1 — the query pattern

For URL Shortener, 100% of reads are the point lookup:

sql
    SELECT long_url FROM urls WHERE short_code = ?

The primary key is short_code. In MySQL InnoDB, the primary key IS a clustered index — the table's rows are STORED IN the primary-key B-tree. A PK lookup = 1 disk I/O (or 1 buffer pool hit for warm data). This is a slight but important advantage over MySQL, where PK is a separate B-tree pointing to a heap (2 I/Os per lookup).

Step 2 — cost per query

Warm hit (row in InnoDB buffer pool):
- B-tree traversal (3-4 levels for ~1B rows): ~5-10 µs
- Row extraction + result serialization: ~20 µs
- Network + connection overhead: ~20 µs
- Total: ~50 µs CPU per warm hit

Cold miss (row must come from disk):
- NVMe read: ~100-200 µs wall-clock (mostly I/O wait, ~5 µs CPU)
- Plus the same 40 µs of processing
- Total: ~200 µs wall-clock, ~45 µs CPU per cold miss

Step 3 — the two ceilings

MySQL is constrained by whichever hits first: CPU or IOPS.

CPU ceiling (assuming 100% warm-hit):
- 2 vCPUs (db.m6i.large) × 60% utilization ÷ 50 µs = ~24,000 QPS

IOPS ceiling (assuming 100% cold-miss):
- gp3 EBS baseline: 3,000 IOPS. That's 3,000 QPS.
- io2 provisioned: up to 20,000 IOPS. That's 20,000 QPS.
- Local NVMe (i3/i4 instances): 100,000+ IOPS. That's 100K+ QPS.

In production with a Zipfian access pattern:
- Top 10% of short_codes serve 80% of traffic (long-tail distribution)
- InnoDB buffer pool holds the hot set warm
- Realistic hit rate: 90-95% warm

Effective QPS = 0.9 × 24,000 (warm) + 0.1 × 3,000 (cold on gp3) = ~22,000 QPS

Number to remember: ~20-25K read QPS per MySQL db.m6i.large primary at 60-70% CPU, assuming Zipfian access + gp3 storage. If you provision io2, you can push into 50K+ range on the same box.

Step 4 — the write side

Writes are different beasts. Every INSERT must:
1. Acquire row lock: ~5 µs
2. Write to redo log buffer: ~10 µs
3. Flush redo log to disk (sync commit): ~500 µs on gp3, ~50 µs on local NVMe
4. Update the primary key B-tree: ~20 µs
5. Multi-AZ semi-sync replication round-trip: ~5 ms if in same-region cross-AZ, ~50 ms cross-region

For URL Shortener with Multi-AZ RDS (semi-sync to standby):
- ~5 ms per commit dominated by cross-AZ replication
- Single-connection write throughput: 1000 ms / 5 ms = 200 writes/sec per connection
- With 32 parallel connections (typical pool size): ~6,000-8,000 writes/sec total

Number to remember: ~5-10K write QPS per MySQL db.m6i.large primary with Multi-AZ sync commit.

Applied to URL Shortener at each tier

• 10K RPS = 9,900 reads + 100 writes → reads at 40% of CPU capacity (9,900 / 24,000), writes at 1% (100 / 8,000). Comfortable.
• 50K RPS = 49,500 reads + 500 writes → reads at 200% of one primary! Would need cache OR read replicas. This is L5 territory.
• 100K RPS = 99K reads → 4× a single primary. Even with 3 read replicas we're at 25K per box → 100% saturated. Cache is mandatory.
• 1M RPS = 990K reads → impossible on any single-primary architecture. Sharding + cache + replicas required.

The bottleneck sequence in the URL Shortener journey isn't invented — it's derived from these ceilings.

Section 6 — Component-limit cheat sheet (with derivations)

The single-page reference every engineer should carry mentally. Each row is DERIVABLE from Sections 4-5.

text
    ══════════ COMPONENT CEILINGS ══════════

    Component               Peak RPS/QPS   Ceiling reason
    ──────────────────────────────────────────────────────────
    App server              3-5K RPS       CPU + concurrency
    (m5.large 2 vCPU)                      at 60% target
    ──────────────────────────────────────────────────────────
    App server              12-20K RPS     Linear scale with cores
    (m5.2xlarge 8 vCPU)
    ──────────────────────────────────────────────────────────
    MySQL primary reads     20-25K QPS     CPU at 60% + 90% warm
    (m6i.large 2 vCPU)                     buffer pool hit rate
    ──────────────────────────────────────────────────────────
    MySQL primary writes    5-10K QPS      Multi-AZ sync commit
    (m6i.large 2 vCPU)                     dominates (~5 ms/commit)
    ──────────────────────────────────────────────────────────
    MySQL read replica      20K reads      Same as primary reads
    (per node)                             (async replication
                                            for isolation)
    ──────────────────────────────────────────────────────────
    Redis single-node       100K-1M QPS    CPU (single-threaded)
                                            + network bandwidth
                                            (10 Gbps NIC ceiling)
    ──────────────────────────────────────────────────────────
    Redis cluster           10M+ QPS       Linear scale across
    (16-node example)                       shards; shard-key
                                            distribution matters
    ──────────────────────────────────────────────────────────
    L7 Load Balancer (ALB)  500K-1M RPS    AWS docs; can go higher
                                            with pre-warming request
    ──────────────────────────────────────────────────────────
    L4 Load Balancer (NLB)  10M+ RPS       Kernel-bypass path;
                                            near-zero per-packet CPU
    ──────────────────────────────────────────────────────────
    CDN edge (per POP)      100K+ RPS      Practically limitless
    (CloudFront, Cloudflare)                per POP; global fleet
                                            is billions of RPS

Rule: memorize the RANGES, not the exact numbers. Derive to the exact number for your workload during the interview. Interviewers respect derivation over recitation.

Section 7 — The URL Shortener bottleneck sequence

Now the payoff. Every architecture evolution in this journey is derivable from the ceilings in Section 6:

text
    ══════════ URL SHORTENER BOTTLENECK SEQUENCE ══════════

    RPS      What breaks first             Why                              What we add
    ────────────────────────────────────────────────────────────────────────────────────
    1K       Nothing.                       3 apps × 3-5K each = 9-15K RPS   Nothing yet
                                            capacity. DB at 4% of ceiling.

    10K      App tier is the tight one     Need 3-5 boxes to hit 10K RPS    Autoscaling
                                            at 60% CPU target. DB at 40%.    group; no other
                                                                              changes needed.

    50K      MySQL reads hit ceiling       One primary maxes at ~25K reads. Read replicas
                                            Would need 2 primaries or        (2-3 async
                                            replicas + cache.                replicas).

    100K     Replicas hit IOPS ceiling     Replicas share the same disk-    Cache-aside on
                                            IOPS distribution as primary.    Redis with 90%
                                            Random reads on cold data melt   hit rate
                                            gp3 EBS.                         (offloads 90% of
                                                                              reads from DB).

    500K     Regional ALB caps out         AWS ALB soft limit ~500K RPS     Multi-region
                                            per LB. Cross-continent latency  Route 53 latency
                                            > 100ms doesn't fit our SLO.     routing + CDN.

    1M       Cross-region write throughput Global writes with sync          Async cross-region
                                            replication add 100ms P99.       replication +
                                            No single-primary write side     eventual
                                            can absorb 100K writes/sec.      consistency.

    10M+     Speed of light                Even with edge caches, cross-    Move redirect
                                            continent RTT is ~100ms          compute to CDN
                                            baseline. Can't be less.         edge workers
                                                                              (Cloudflare, EC).

Every transition is derivable from a component's ceiling being crossed. Not memorized. Derived.

Show this table to an interviewer and walk them through the derivations. That is what "senior" looks like.

Section 8 — Interview technique — "walking the numbers" out loud

The skill isn't knowing the numbers. It's SAYING the numbers in a way that shows you derived them.

Practice each of these out loud until you can do it in 30 seconds without pausing:

For 10K RPS (L4)

"At 10K RPS with a 100:1 read:write ratio, I have 9,900 read QPS and 100 write QPS. My app tier is 3 × m5.large: each box does ~3-5K RPS at 60% CPU with 10ms latency by Little's Law (L=30 concurrent × 10ms). My DB is one MySQL m6i.large primary. Reads at 9,900 QPS ÷ 25K ceiling = 40% CPU. Writes at 100 QPS = 1%. Both well under queueing-theory cliff. This is the correct MVP."

For 100K RPS (L5)

"At 100K RPS my app tier scales linearly — 30 boxes across 3 AZs. But my DB hits the reads ceiling: 99K QPS ÷ 25K per primary = need 4 primaries or read replicas. Even 3 replicas + 1 primary = 4 × 25K = 100K capacity, which puts each at 100% utilization — over the cliff. Cache is mandatory here. Redis at ~1M QPS single-node capacity absorbs 90% of reads (Zipfian) → DB drops to 10K QPS at 40% utilization. This is the L5 architecture."

For 1M RPS (L6)

"At 1M RPS my regional ALB caps out (~500K per LB). I go multi-region with Route 53 latency routing. Reads: 990K QPS × 90% cache hit = 99K on DB, needs sharded MySQL (Vitess) across 4-8 shards to stay under 25K per primary. Writes: 10K writes/sec fits one primary; 100K writes/sec at extreme tail needs sharding by short_code hash. Cross-region async replication accepts eventual consistency in exchange for regional read latency < 20ms. This is L6."

Rehearse these until you can say them without notes. In real interviews you might get 60-90 seconds per tier — that's enough for the derivation IF you've rehearsed. Otherwise you'll skip the math and it will show.

The interview meta-lesson

The interviewer never cares about the exact number. They care whether you:

1. Understand which component is the bottleneck (you named it: app tier, DB reads, DB writes, LB, network)
2. Can derive the number (you cited Little's Law, showed the math, referenced the ceiling)
3. Know the queueing cliff (you mentioned 60% target, not 80%, and you explained M/M/1)
4. Chose the right mitigation (cache before sharding, replicas before microservices, CDN before edge compute)

If you can do those 4 things, you can defend any capacity claim they push back on. That's what separates Staff-level from Senior-level in the system-design loop.

References (33 items)

• Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley. — Foundational reference for M/M/1 utilization math.
• Little's Law — Little, J. D. C. (1961). A Proof for the Queuing Formula: L = λW. Operations Research. — The original 1961 proof.
• Kleppmann, M. (2017). Designing Data-Intensive Applications. O'Reilly. Chapter 1 covers reliability + throughput + latency; Chapter 7 covers transactions/replication for the MySQL derivation.
• TechEmpower Framework Benchmarks — techempower.com/benchmarks — where the "Go on m5.large does ~30K RPS" empirical number comes from.
• MySQL 8.0 Reference Manual — InnoDB Buffer Pool — dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html — for the buffer-pool warm-hit derivation.
• AWS Aurora + RDS MySQL performance benchmarks — the real-world reference for the 20-25K read QPS ceiling on m6i.large.
• AWS ALB limits — docs.aws.amazon.com/elasticloadbalancing/latest/application/load-balancer-limits.html — where the 500K-1M RPS-per-LB ceiling comes from.

Interview soundbite for this chapter as a whole:

"I derive every capacity number I quote. Little's Law gives me throughput from latency and concurrency. M/M/1 tells me the utilization cliff is at 80% CPU so I target 60% steady-state. Component ceilings — 3-5K RPS per app box, 20-25K QPS per MySQL primary, 500K-1M RPS per ALB — flow from that same math applied to specific hardware. When I say '10K RPS is a single MySQL,' I mean the read side is at 40% of the 25K ceiling and I have 60% headroom for viral spikes."

Ship this and you never get pushed back on capacity claims again.

This is the chapter that separates senior candidates from junior ones — and the answer is counterintuitive.

The right architecture for launch is the simplest possible thing that works. Not the most impressive. Not the most future-proof. The simplest.

Here's why: you have 8 weeks and 3 engineers. Every additional component you add is a new failure mode, a new deployment, a new monitoring surface, a new library to learn. Complexity has a cost, and at the MVP stage, the cost is time to market — which is your only real KPI.

So what's the MVP architecture?

• 1 load balancer (AWS ALB, ~$25/mo)
• 3 stateless app servers (t3.large in an ASG, ~$180/mo)
• 1 MySQL (RDS db.m6i.large Multi-AZ, ~$170/mo)

Total: ~$400/mo. Handles 10K RPS comfortably. Ships in 8 weeks.

Why 3 app servers — the derivation (this is what interviewers drill into)

"3 app servers" sounds arbitrary. It isn't. It's the minimum of three independent floors — you take whichever is highest.

Floor 1 — Raw throughput math (from [Chapter 4.75, Section 4](#chapter-4-75-bottleneck-derivation)).

Per-box capacity for the URL Shortener redirect workload on a t3.large (2 vCPU, 8 GB RAM):
- Per-request CPU cost: ~200 µs (parse HTTP + await 5ms DB round-trip + serialize 302 + emit log)
- Per-box throughput at 60% CPU: 2 cores × 0.6 ÷ 200 µs = 6,000 RPS theoretical
- Realistic with async runtime concurrency (Little's Law with L=30, W=10ms): ~3,000 RPS/box sustained

At 10K peak RPS: 10,000 ÷ 3,000 = 3.33 boxes → round up to 4 for pure throughput.

But wait — that's peak. Average RPS is lower (~2-3× ratio). And we have to price in safety margin. Recompute at the correct point:
- Average RPS: 10K ÷ 2.5 (peak factor) = 4,000 RPS
- Boxes at average: 4,000 ÷ 3,000 = 1.33 → 2 boxes
- With 1.5× safety margin for viral spikes: 3 boxes

Floor 2 — Multi-AZ high-availability floor.

AWS Well-Architected Reliability Pillar requires you to distribute across ≥2 availability zones for the 99.9% SLA that RDS Multi-AZ promises. Concretely:
- 2 AZs is the minimum for automatic failover on AZ loss (single-AZ = full outage during the ~1 AZ event per year, which happens; see AWS us-east-1 Dec 2021 outage postmortem).
- With 2 AZs, if you run 2 boxes (one per AZ), a single-AZ failure drops you to 1 box → 50% capacity. That's not a "brief blip," it's an outage during the AZ failure duration (typically 30 min - 2 hr).
- With 3 boxes across 3 AZs, single-AZ loss drops you to 2 boxes = 67% capacity. Absorbable for most workloads.

Floor 3 — Rolling-deploy floor.

You will deploy ~5-10 times/week. During a rolling deploy, one box is being replaced (~90s in a well-tuned ASG). If you run 2 boxes:
- Deploy takes one box out → 1 box left → 50% capacity mid-deploy
- If a spike hits during that 90s window, you drop requests
- Also violates the AWS Well-Architected guideline of "no single point of failure at any moment"

With 3 boxes, rolling deploy leaves you with 2 boxes at any moment (67% capacity). Absorbable.

The final answer: max(Floor 1, Floor 2, Floor 3) = max(3, 3, 3) = 3 app servers

Not 2 (fails Floor 2 + Floor 3). Not 4 (over-provisioned for L4). Exactly 3.

References for this derivation:
- AWS Well-Architected Framework — Reliability Pillar — the "distribute across AZs" guidance.
- AWS Auto Scaling best practices — rolling deployments — 90s replacement time and N-1 capacity during refresh.
- AWS us-east-1 December 2021 outage postmortem — real-world evidence of ~1 major AZ event per year at AWS.
- Google SRE Book — "Handling Overload" — the queueing-theory basis for the 60% CPU steady-state target.
- Kleinrock, L. (1975). Queueing Systems Vol 1. Wiley. — the M/M/1 math behind Little's Law and the 80% utilization cliff (also cited in Chapter 4.75).

Why NOT 5 or 10 app servers?

Real question junior engineers ask: "wouldn't 5 or 10 servers be safer?"

5+ boxes at L4 wastes money without adding meaningful availability. You've already covered:
- AZ failure (3 AZs, quorum survives loss of 1)
- Rolling deploys (2 of 3 always healthy)
- Peak spikes (1.5× safety margin baked in)
- Individual box crash (ASG replaces in 90s, other 2 boxes absorb)

Adding a 4th or 5th box protects against... what exactly? Two simultaneous AZ failures? That's the "region loss" scenario, which requires multi-region (L6), not more app servers. Two simultaneous box crashes in the SAME AZ? Uncorrelated failures at 3 boxes have vanishing probability (~10^-6 per year). Not worth the money.

The economics: 5 boxes = ~$300/mo, 3 boxes = $180/mo. That $120/mo × 12 = $1,440/year gets you 0 improvement in your 99.9% SLA. It buys you comfort, not availability.

When the number changes

3 is right for L4. It changes at L5 and L6:

• L5 (100K RPS, [Chapter 6](#chapter-6-l5)): horizontal scaling to ~10-30 boxes across 3 AZs, still stateless
• L6 (1M RPS, [Chapter 7](#chapter-7-l6)): 30 boxes per region × 3 regions = 90 total, with regional-level failure handling

Each transition has its own Floor 1/2/3 math. Never memorize the count — always derive it from the current traffic + reliability requirements.

Why db.m6i.large for MySQL? (the DB sizing derivation)

Same interviewer probe as "why 3 app servers?" — "why the m6i.large and not m6i.xlarge or db.t3.medium?" The answer is the same 3-floor discipline. This time the floors are: CPU capacity, memory (buffer pool), and disk IOPS.

Floor 1 — CPU capacity for our target QPS.

At 10K RPS with 100:1 read:write = 9,900 reads/sec + 100 writes/sec. Per Chapter 4.75, Section 5:

• Read CPU cost with 90% InnoDB buffer pool warm hit rate: 145 µs wall (50 µs CPU)
• Total CPU per second: 9,900 × 50 µs + 100 × 100 µs (writes) = 505 ms/sec CPU
• On a 2-vCPU db.m6i.large (2000 ms/sec CPU budget), that's 25% utilization
• With safety margin (peak factor 2.5× + AZ failover absorption 1.5×), we still stay well under 80% queueing cliff

Floor 1 says: db.m6i.large (2 vCPU) is sufficient. Cheaper options?

• db.t3.medium (2 vCPU BURSTABLE) — CPU credits system means sustained 30 min at 100% credits drop to 20% baseline. UNACCEPTABLE for a redirect service. Rule: never use T-family for anything with sustained CPU > 20% baseline.
• db.t3.large (2 vCPU BURSTABLE) — same problem.

db.m6i.large is the cheapest non-burstable general-purpose 2-vCPU option. Floor 1 = db.m6i.large.

Floor 2 — Memory for the InnoDB buffer pool.

Working set: at 10K RPS with Zipf α ≈ 1, the top 10% of URLs get 90% of traffic. Estimating 100M URLs stored (10 years × 1M/day retention math), top 10% = 10M URLs × 220 bytes = ~2.2 GB working set. Add InnoDB internal overhead (data dictionary, adaptive hash index, undo tablespaces) → ~3-4 GB actual buffer pool need.

• db.m6i.large — 8 GB RAM. Setting innodb_buffer_pool_size = 6 GB (70-80% of RAM per MySQL 8.0 best practice) → 6 GB buffer pool ≈ 3× the working set. Comfortable warm-hit rate 92-95%.
• db.m6i.xlarge (16 GB RAM, 2× the cost) — overkill at L4, wastes budget.
• db.t3.medium (4 GB RAM) — 3 GB buffer pool ≈ 1.4× working set. Marginal warm-hit rate ~85%. Hits IOPS ceiling faster on cold misses (see Floor 3).

Floor 2 = db.m6i.large (or larger, but m6i.large is enough).

Floor 3 — Disk IOPS.

RDS db.m6i.large ships with gp3 EBS at 3,000 baseline IOPS + throughput 125 MiB/s. Our cold-miss rate: 10% × 9,900 reads = ~990 IOPS on cold reads. Well under the 3,000 baseline. Writes: 100/sec × ~2 IOPS/write (redo + binlog + tablespace) = ~200 IOPS.

• gp3 3,000 IOPS baseline = 3× headroom. Comfortable.
• io2 (16K IOPS provisioned) — overkill at L4, but the right upgrade path at L5+ when cold-miss traffic scales to 3K+ IOPS.

Floor 3 = gp3 storage on db.m6i.large is sufficient.

The final answer: max(Floor 1, Floor 2, Floor 3) = db.m6i.large + gp3

• 2 vCPU: 25% CPU at 10K RPS (Floor 1 comfortable)
• 8 GB RAM: 3× working set headroom (Floor 2 comfortable)
• gp3 3K IOPS: 3× headroom on cold-miss volume (Floor 3 comfortable)
• Cost: ~$170/mo Multi-AZ (with $0.10/GB-mo × 100 GB storage) — the number that appears in Chapter 5's cost table

Why NOT skip Multi-AZ to save $85/mo?

Same reason we don't skip Multi-AZ on the app tier: single-AZ = ~1 outage/year at AWS (us-east-1 historical postmortems). At 10K RPS, one 4-hour AZ outage means ~144M failed redirects. For a $85/mo saving on infra, you'd need the product to tolerate ~2% annual downtime. No consumer product does.

When does the DB size upgrade?

Trigger: CPU sustained above 60% OR cold-miss IOPS above 2,000 (75% of gp3 baseline).

Upgrade path:

1. First: add read replicas at L5 (see Chapter 6) to offload read CPU. Buys ~10× read headroom.
2. Second: scale UP the primary to db.m6i.2xlarge (8 vCPU, 32 GB) when writes cross ~5K/sec. Buys ~4× write headroom.
3. Third: shard the primary at L6 (see Chapter 7) when writes cross ~10K/sec sustained. Buys unlimited horizontal headroom (Vitess).

References for this derivation:

• MySQL 8.0 Reference Manual — InnoDB Buffer Pool sizing — 70-80% of RAM best practice
• AWS EC2 burstable performance credits docs — why T-family isn't right for a DB
• AWS EBS gp3 pricing/performance — 3K baseline IOPS + $0.08/GB-mo
• AWS RDS pricing calculator — Multi-AZ premium is ~$85/mo for db.m6i.large
• AWS us-east-1 outage postmortems — real historical evidence for Multi-AZ ROI

Here's what that L4 architecture looks like on a whiteboard:

Total: $400/mo · 5 boxes · 3 engineers hold it all in their heads.

Every arrow above is a hop that costs latency. Every box above is a failure mode. L4 is the minimum count of arrows and boxes that solves the problem. If you can draw fewer boxes and still meet the requirements, use fewer boxes.

No cache. No Kafka. No microservices. No Kubernetes. No. These are all wrong choices for the MVP because they don't solve any problem you have at 10K RPS.

I know this hurts. You spent 2 years learning distributed systems and I'm telling you to build a monolith. But look — every FAANG company started as a monolith. Facebook was a PHP monolith until ~2010 (The Facebook Engineering Blog — "HipHop for PHP"). Amazon was a Perl monolith until Bezos wrote the "services or fired" memo. The reason to introduce complexity is that a real problem forces you to. Never before.
## The "what you deliberately did NOT build" visual

Here's the diagram they never show you in FAANG blog posts, but the one that actually matters at L4 — the components you chose not to add, and the reason each rejection is defensible. Try the interactive comparison below — toggle each &quot;overbuilt&quot; component to see cost + timeline slip in real time:

How to read the two columns side-by-side: each ADDITIONAL box in the over-built version corresponds to a specific problem-you-do-not-yet-have. The table below defends every rejection with a concrete threshold — read it against the diagram:

RULE: every box you add must delete a problem you actually have. If you add a box to prevent a problem you MIGHT have someday, you added complexity you MUST maintain today. That trade is bad.

Interview soundbite for this visual: "The senior-engineer skill is not knowing what to add. It's knowing what to not add and being able to defend the omission. At L4 I omitted CDN, WAF, API Gateway, Auth Service, Redis, Kafka, microservices, K8s, Elasticsearch, and BigQuery — and I can name a specific reason for each. If someone challenges me on any one of them, I have a metric-based threshold at which I would add it. That threshold is L5 for some, L6 for others, L7 for a few."

Why this matters for the newbie: every engineer starts by wanting to add cool tech. FAANG interviews specifically probe the opposite instinct: "you don't need this yet." Practice out loud: "I considered a CDN. I chose not to add it because at 10K RPS MySQL is at 30% CPU. When the hot 10% of URLs starts dominating requests, I'd add CloudFront in front. Threshold: p99 origin latency > 100ms." Do that for every rejected box.

Where does "30% CPU" come from? (the derivation you must own)

Every number I quote in this chapter is derived, not memorized. Here's the MySQL-CPU math for 10K RPS on a db.m6i.large (2 vCPU, 32 GB RAM):

Step 1 — the query pattern. We split 10,000 RPS into 9,900 reads (SELECT by short_code) and 100 writes (INSERT). That's the 100:1 read:write ratio a URL shortener has by definition.

Step 2 — cost per query. A point lookup on an indexed column in MySQL:
- Warm hit (row is in the innodb_buffer_pool_size pool): ~50 microseconds of CPU
- Cold hit (row must be fetched from disk): ~1 millisecond wall-clock (mostly NVMe IO wait, ~50µs CPU)

Step 3 — the hit rate. innodb_buffer_pool_size is 25% of 32GB = 8GB. Our full row set is 800GB (10 years' worth). The buffer pool can only hold ~1% of data. But URL popularity is Zipfian — the top 10% of URLs get ~90% of traffic. Even if our buffer pool holds only 1% of data, it holds the hot 1%, so the warm-hit rate settles around 90% once the cache is warmed.

Step 4 — the CPU math.
- 9,900 reads/sec × 90% warm × 50µs = 445 ms CPU/sec (on reads)
- 9,900 reads/sec × 10% cold × 50µs = 49 ms CPU/sec (CPU part of cold; IO wait doesn't count as CPU)
- 100 writes/sec × 100µs (redo log + B-tree insert) = 10 ms CPU/sec
- Total: ~504 ms CPU/sec used out of 2000 ms available (2 vCPU) = ~25% CPU

Step 5 — the honest bound. I rounded aggressively. Add ~5% for connection pool overhead, ~5% for background InnoDB purge/InnoDB purge thread, and you land at ~30-35% CPU sustained at 10K RPS. That's the number I quote in the design.

Step 6 — the safety margin. At ~30% CPU with 2-3x peak factor, we have ~70% headroom before saturation. That headroom is what absorbs viral events, backup pressure, and misconfigured queries. Do not run steady-state above 50% CPU on a single-primary MySQL — the queueing theory wall (utilization × wait time) melts your p99 above ~70% sustained.

Interview probe: "How do you know it's 30% and not 60%?" Answer: I derived it. Give them the 4-step math above. Interviewers love this — it proves you're not repeating a Medium article.

Below you'll find the L4 design in full detail — every decision, every alternative I considered, every reason why I picked what I picked. Read it carefully. This is the reference architecture. When someone asks you "how would you design a URL shortener?" in an interview, this is your first answer. Then, if they push, you evolve it. That's Chapter 6.

Here's what always happens in an interview: you say "MySQL," and the interviewer immediately asks:

"Why not PostgreSQL? Why not DynamoDB? What if I told you we're a Postgres shop — how does your design change?"

If you shrug or say "MySQL has better JSON support," you've failed the probe. The right answer walks through requirements → workload shape → each option's fit → the specific reason THIS workload picks THIS database.

I'm going to give you all four candidates head-to-head, with the exact math and the exact "if you picked X, here's how the design evolves" branches. When you're done reading this, you can defend any choice against any interviewer.

Step 1: what does the URL shortener actually ask the database to do?

Requirements — spelled out so we can grade each option against them:

1. Point lookup by primary key on the read path: SELECT long_url FROM urls WHERE short_code = ? — 99% of read traffic
2. Insert with PK uniqueness check on the write path: INSERT IGNORE INTO urls ... — 1% of traffic
3. Very few range scans — the hot path is entirely random-access
4. Read-your-writes consistency for the URL creator (they just clicked "shorten," they expect the redirect to work immediately)
5. Eventual consistency acceptable for analytics (5-minute lag OK)
6. Row size ~220 bytes, mostly small strings
7. Storage growth: 800GB in 10 years at 1M writes/day
8. Multi-region strategy needs an answer at L6+
9. Cost matters — the database is 60% of our infrastructure bill at L5+

Now grade the four candidates.

MySQL (the default recommendation)

The internals you MUST know:

• InnoDB MVCC (Multi-Version Concurrency Control) via undo tablespaces: readers never block writers, writers never block readers. Great for a shortener where reads dominate.
• Clustered B+tree index on the primary key: MySQL InnoDB stores the row data INSIDE the primary-key B+tree. SELECT long_url FROM urls WHERE short_code = ? traverses the tree (3-4 levels for 3.6B rows) and the row data is IN the leaf. One I/O per warm lookup. Compare to Postgres: separate heap + PK index = 2 I/Os per cold lookup.
• Redo log (InnoDB's Write-Ahead Log): every write goes to the redo log first, then to disk. Durability tunable via innodb_flush_log_at_trx_commit (1 = full ACID, 2 = trade small durability window for throughput).
• Buffer pool: innodb_buffer_pool_size = 70-80% of RAM (~24GB on m6i.large's 32GB). InnoDB does all its caching in-process; the OS page cache is largely bypassed. Very different tuning philosophy from Postgres.
• Query optimizer: cost-based since 5.7. Statistics-driven, gets better every major release.
• InnoDB purge thread: reclaims old row versions from undo logs. Runs automatically; can lag under heavy churn but rarely a problem.

Throughput math (this is the derivation you should own):
- Point lookup with warm buffer pool: ~40µs CPU (slightly faster than Postgres because clustered index means no heap dereference).
- Point lookup with cold buffer pool (disk hit): ~1ms wall (NVMe SSD)
- 2 vCPU on m6i.large = 2000ms of CPU per second
- At 90% buffer pool hit rate: 90% × 40µs + 10% × 1ms = 136µs per lookup wall time (IO dominates)
- CPU-only capacity: 2000ms / 40µs = 50,000 QPS ceiling (if 100% warm hits)
- Realistic sustained: ~20-25K QPS at 50-60% CPU with 90% warm-hit rate (see Chapter 4.75 for the full derivation from first principles)

Multi-region story:
- L4/L5: single primary, Multi-AZ synchronous standby (RDS-managed failover in 30-90s)
- L6: async binlog replication to secondary regions (5-500ms lag), OR Aurora MySQL Global Database (managed, <1s lag)
- L7: sharded across regions with Vitess — YouTube-tested horizontal sharding at billions-of-rows scale. This is the killer feature vs Postgres.

Cost:
- L4 (Multi-AZ RDS m6i.large): $170/mo
- L5 (m6i.4xlarge + 2 replicas): $2,400/mo
- L6 (r6i.8xlarge Aurora MySQL Global × 3 regions): $18,000/mo
- L7 (Vitess cluster 32 shards × 3 regions): $80,000/mo

Wins: rich SQL, mature tooling, familiar to every engineer, JSON column type (5.7+) with functional indexes, native full-text search (InnoDB FTS), extensive ecosystem, MVCC snapshot isolation "just works," excellent monitoring via performance_schema + sys schema, best-in-class Vitess for sharding, Aurora MySQL is a well-loved AWS-managed variant.

Loses: Postgres has richer types (arrays, hstore, PostGIS, tsvector); Postgres's SQL is slightly more standard-compliant; JSONB with GIN indexes in Postgres is more mature than MySQL JSON with functional indexes.

Verdict for URL Shortener: MySQL wins at L4-L7 by default. The clustered index is a slight but real edge for point-lookup workloads (1 I/O vs 2). Vitess is the L6+ killer feature.

PostgreSQL (the "we're a Postgres shop" alternative)

Same MVCC concept, same B-tree indexes, but with important differences:

• MVCC via xmin/xmax: Postgres stores per-row transaction IDs. Old row versions accumulate in the same table (called "bloat") until VACUUM reclaims them. Different implementation than InnoDB's undo tablespaces, same visibility guarantees.
• Heap-organized tables + separate PK index: the primary key is a B-tree that points INTO a heap file. A cold PK lookup = index I/O + heap I/O = 2 I/Os (vs MySQL's 1 with clustered index). For URL shortener where 100% of lookups are PK-based, this is a small but real disadvantage.
• WAL (Write-Ahead Log): same purpose as InnoDB redo log. Sync via synchronous_commit and wal_sync_method.
• shared_buffers: 25% of RAM (~8GB on m6i.large's 32GB). Postgres relies on the OS page cache for the other 75% — different philosophy from InnoDB. This is why sizing recommendations differ so dramatically.
• VACUUM / autovacuum: reclaims dead tuples from bloat. Runs automatically; can lag under heavy churn and cause table bloat if misconfigured.
• Extensions: PostGIS (geospatial), pg_stat_statements (query analysis), hstore, tsvector (full-text), pgvector (embeddings) — the extension story is Postgres's biggest edge.

Throughput math:
- Point lookup with warm buffer pool: ~50µs (slightly slower due to heap dereference)
- Cold hit: ~1ms (same NVMe latency)
- 2 vCPU capacity: ~40K QPS ceiling, realistic ~15-20K sustained (vs MySQL's ~20-25K)

"If you picked PostgreSQL, how does the design evolve?" — this is the interview question the user asked. Here's the branch:

• L4 (10K RPS): identical architecture — LB + 3 app servers + Postgres Multi-AZ (RDS or Aurora Postgres). Same $170/mo. Same 8-week timeline. Nothing changes except the DB engine and the buffer pool tuning knob.

• L5 (100K RPS): still identical — cache-aside with Redis in front, async streaming-replicated read replicas. Reads scale linearly with replicas. For read-your-writes on the create path, use synchronous_commit=on with a nearby standby.

• L6 (1M RPS): this is where MySQL wins by default. Postgres path requires Citus (Postgres extension for horizontal sharding, Microsoft-owned since 2019, powers Azure Cosmos DB for Postgres). Citus is mature but has less production battle-testing than Vitess at billions-of-rows scale. Alternative: CockroachDB (Postgres-wire-compatible NewSQL, ~2x cost but built-in horizontal scale + globally distributed).

• L7 (1B RPS): Citus + Redis cluster + edge caching. Or CockroachDB for multi-region active-active. Both work; Vitess ecosystem is more mature at this scale.

When PostgreSQL beats MySQL for a URL shortener specifically:
- Your team is already on Postgres (organizational fit dominates technical fit)
- You need JSONB with GIN indexes for a companion analytics workload
- You need PostGIS (geo queries on click origin)
- You need the richer SQL standard (window functions, CTEs — MySQL has them but Postgres's are more mature)
- Your team hires from the data-analyst pool (Postgres is dominant in analytics)

When MySQL still wins:
- Vitess at L6+ (this is the biggest single reason)
- Clustered index for point-lookup-dominant workloads
- Simpler default configuration for a small ops team
- Aurora MySQL is best-in-class among managed MySQL variants

Cassandra (the "write-heavy globally distributed" pick — wrong for us, know why)

Cassandra is the right answer for a different problem.

• Wide-column store, tunable consistency (per-query), no single leader
• Writes scale linearly with node count (each node accepts writes for its token range)
• Reads at eventual consistency are the sweet spot; strong consistency requires quorum reads (RF=3, R=2, W=2)
• No joins, no complex queries — you denormalize at write time

Point lookup latency: ~5-10ms p99 (across the network to at least one replica). MySQL is ~1ms local.

For URL shortener:
- Read path: fine. Cassandra can handle 99% point lookups at scale.
- Write path: overkill — at 100K writes/day (1 write/sec avg) we don't need write-parallel scaling.
- Operational cost: 5+ nodes minimum for RF=3 with even one AZ failure tolerance. That's $2K+/mo minimum before you have any workload. MySQL does the same job at $170/mo at L4.

"If someone forces Cassandra on us, how does the design evolve?"
- L4: 3 Cassandra nodes (RF=3), $2K/mo. Overkill but works. Cache-aside still valuable.
- L5-L6: benefits materialize — no read-replica routing (all nodes serve reads), automatic rebalancing, no manual sharding.
- L7: strong contender. Discord, Netflix use Cassandra at billions-of-rows scale for exactly this workload shape.

When Cassandra actually wins for URL Shortener:
- 500M+ URLs, write-heavy pattern (unusual for shorteners)
- Multi-region ACTIVE writes with tunable consistency
- Team already operates Cassandra (no learning curve)

When it loses: everything below L7. Operational overhead + latency cost don't pay back until you're at write-heavy planet-scale.

DynamoDB (the "just don't operate a database" pick)

Managed KV, pay per read/write, auto-scales.

• Point lookup: ~5-10ms p99 in region (single-digit ms with DAX cache)
• Write: ~5-10ms p99, strongly consistent by default (waits for majority of storage nodes)
• Auto-sharding: partition-key-based, invisible to you
• Global tables: multi-master multi-region, ~1s cross-region propagation

Cost math (this is the derivation the interviewer will ask):

DynamoDB On-Demand pricing (us-east-1, as of 2025):
- Read Request Unit (RRU): $0.25 per million (eventually consistent) or $0.50 per million (strongly consistent)
- Write Request Unit (WRU): $1.25 per million
- Storage: $0.25/GB/month

At 10K RPS with 100:1 R:W:
- 9,900 read/sec × 86,400 = 855M reads/day = 25.7B reads/month
- Cost: 25,700 × $0.25 = $6,425/month (eventually consistent, 4KB items)
- Write cost: 100/sec × 86,400 × 30 = 259M writes/month = $323/month
- Storage 800GB: $200/month
- Total: ~$7,000/month at L4 vs $400/mo for MySQL.

But at L6 (1M RPS):
- 990K read/sec = 2.57 TRILLION reads/month
- Cost: $642,500/month. Yes, that's real.
- Provisioned capacity with reserved pricing brings it down ~50%, so $321K/mo.
- Compare MySQL L6: $18K/mo.

DynamoDB is 15-30x more expensive at high scale. In exchange:
- Zero operational burden (no upgrades, no failover, no capacity planning)
- Multi-region built-in (Global Tables)
- Auto-scaling on hot partitions

"If your interviewer forces DynamoDB, how does the design evolve?"
- L4: LB + 3 app servers + DynamoDB. NO MySQL, NO Redis (DAX is optional). Simpler diagram, higher $/RPS.
- L5: add DAX (managed cache) — $0.30/hour per t3.small × 3 nodes = ~$650/mo. Cache hit rate 90%+ cuts DynamoDB read cost ~10x. Now the math is competitive.
- L6: Global Tables handle multi-region. No sharding logic in the app. Cost is still 15-30x MySQL, but ops team is 1 person instead of 5.
- L7: at 1B RPS the cost is astronomical ($6M+/mo). Only chosen if AWS-committed and can pay for the ops relief.

When DynamoDB wins:
- All-in on AWS, lock-in acceptable, ops budget < $200K/yr
- Truly bursty traffic (auto-scaling saves money vs provisioning peak)
- Team is 3 engineers, none want to operate a database

When it loses:
- Cost sensitivity — MySQL is 15-30x cheaper at scale
- Multi-cloud portability required
- Complex queries needed (DynamoDB is KV; joins/aggregations require Redshift/Athena on the side)

The decision tree (memorize the branches, not the answers)

Walk through the interactive tree yourself — answer Q1-Q4 in order and see which DB you land on. Try different answers to explore each branch: