URL Shortener System Design

Why this session matters

Part of a 36-topic learning series on engineering, ML, and LLM systems. Each session is a 90-minute deep-dive on one topic — designed so anyone can pick it up cold. Every two topics are followed by a revision session with recall prompts and hands-on drills.

Part 1: URL Shortener Part 1 — Numbers, IDs, Storage

Why this session matters

It builds on the rhythm of one focused topic, paced so you have time to actually absorb it rather than rush.

Agenda

• Back-of-envelope at 100M writes/day, 10B reads/day
• Three ID schemes — hash, counter+base62, Snowflake — trade-offs
• Choosing the storage engine — KV store vs SQL vs NoSQL
• Schema design and idempotency on the write path
• Why the cache + CDN discussion is its own session (Part 2)

Pre-read (assume zero background — watch/skim in order)

Videos (in this order, ~60–90 min total — do this before the session, not during):

1. System Design Basics — ByteByteGo — ~10 min. The vocabulary (load balancer, cache, DB, replication) if you're new.
2. URL Shortener System Design — System Design Interview — ~15 min. Classic FAANG interview problem walkthrough.
3. TinyURL Design — Gaurav Sen — ~20 min. Alternative walkthrough with different tradeoffs.
4. Base62 Encoding Explained — Coding Cleric — ~8 min. The math behind short-code generation.
5. Consistent Hashing — Hussein Nasser — ~15 min. How to shard the URL database.

Notes to skim (if any term above felt fuzzy):

• New to system design at all? System Design Primer (GitHub) — the canonical free resource.
• New to databases? Session 08 (Postgres Internals) is a prereq if you don't know what "index" or "primary key" mean.
• Reference materials (keep tabs open): High Scalability blog · AWS Well-Architected Framework.

Prerequisite check before you start: you should be comfortable with (a) what a database index does, (b) client → server → DB request flow, (c) rough idea of horizontal vs vertical scaling. If any shaky, do the ByteByteGo basics video fully.

Deep dive

1. The shape of the problem

TinyURL looks trivial until you put numbers on it. Design for 100M new URLs/day, 10B reads/day, 5-year retention and let the layers fall out.

2. Back-of-envelope (always do this first)

• Writes: 100M / 86,400 s ≈ 1.2k QPS average, 6k QPS at 5× peak.
• Reads: 10B / 86,400 s ≈ 115k QPS average, 600k QPS at peak. R:W ≈ 100:1.
• Storage: 100M × 365 × 5 ≈ 180 B records. Each record ≈ 500 B (short, long, owner, created_at, expires_at, click_count) → 90 TB. Plus 2–3× replication.

State these numbers out loud before you talk about anything else. They drive every subsequent decision.

3. ID / short-code scheme — three real options

Option A — Hash(long_url)[:7] in base62

• ✅ Deterministic, idempotent (same long → same short).
• ❌ Collisions need a check-and-retry against an index. Extra round trip.
• ❌ Doesn't help if two users want different shorts for the same URL.

Option B — Auto-increment counter + base62

• ✅ No collisions ever. Shortest codes (6–7 chars for 100B records: log₆₂(1e11) ≈ 6.1).
• ❌ Single counter = single point of contention.
• ✅ Mitigate with batch allocation: each app server reserves 10k IDs at once via INCRBY counter 10000 on Redis. Local cache, lock-free use, refill when low.

Option C — Snowflake (64-bit)

• 41 bits timestamp | 10 bits machine_id | 12 bits sequence → coordination-free, sortable by time.
• Base62 of 64 bits = 11 chars (too long). Truncate to 48 bits → 8 chars.
• ✅ No coordination required across machines.
• ❌ Codes leak creation time and machine_id (mild info leak).

Pick: For 100M/day I'd choose counter with batched allocation (Option B). Simplest, shortest codes, contention solved by batching. State the alternative and why you rejected it.

4. Storage — the access pattern is point-lookup by short code

This is textbook KV: O(1) lookup by single key, no scans.

Pick: DynamoDB (or Cassandra if you self-host). Hash-partition by short_code.

Schema:

short_code  STRING  PK
long_url    STRING
owner_id    STRING
created_at  TIMESTAMP
expires_at  TIMESTAMP
meta        MAP<STRING,STRING>      -- UTM, custom tags

Add a secondary index on (owner_id, created_at) only if you need owner-scoped listings — they're not on the hot path.

5. Write path

1. Validate URL (length ≤ 2048, scheme http/https, blocklist).
2. Idempotency check: if hash(long_url, owner) already exists → return it.
3. Pop next short_code from local batch (refill via INCRBY 10000 on Redis).
4. Conditional put to DynamoDB (so we catch the very rare race).
5. Async publish to Kafka — analytics consumer aggregates later.
6. Return 201 with short URL.

Two failure modes to think about now:

• Counter shard dies. Batched IDs in app caches keep writes alive for minutes. Alert, re-elect.
• Conditional put fails. Hash collision (rare with 64-bit codes). Increment local counter and retry.

6. Owner / multi-tenant data model

If you want custom aliases (https://tinyurl.com/dinesh-blog) you need:

• Uniqueness across the global namespace.
• A reserved-words blocklist (admin, api, login, etc.).
• Per-owner quota tracking (count + storage).
• A second logical table aliases (alias_str PK, short_code, owner_id) so resolution still goes through the same KV path.

7. Putting it on the map

┌───────┐     ┌───────────┐
│ User  │────▶│ Load bal. │ HTTPS
└───────┘     └────┬──────┘
                   │
            ┌──────▼──────┐
            │  Shorten    │  POST /api/shorten
            │  service    │  (validates, picks id)
            └──────┬──────┘
                   │   put
            ┌──────▼──────┐    INCRBY 10000
            │  DynamoDB   │◀───── Redis counter shard
            └──────┬──────┘
                   │ async event
            ┌──────▼──────┐
            │   Kafka     │ → analytics consumer
            └─────────────┘

Read path lives in Part 2 — that's where cache, CDN, hot-key handling, and stale-while-revalidate go. Putting both in one session is what made the 28-day plan feel rushed.

8. Numbers you should be able to defend

• Why 6–7 char codes? log₆₂(180B / collision-safety-factor) ≈ 6.5 — pick 7 for headroom.
• Why DynamoDB over Postgres? At 600k read QPS, sharding Postgres is a job in itself. DynamoDB charges by request and storage — predictable.
• Why batched IDs? At 6k peak write QPS with a 10k batch, you refill once every ≈ 1.7 s per app server. Counter QPS = app_servers / 1.7.
• Why conditional put? Race window is microseconds, but at 100M/day even microsecond races happen daily.

9. What we're saving for Part 2

• Cache layer (Redis cluster), 95% hit-rate math at Zipf 0.9
• CDN edge — doing the 302 at the edge for read-heavy keys
• Hot-key problem — viral short codes
• Abuse / safe-browsing integration
• Analytics — Kafka → Flink → ClickHouse
• Multi-region trade-offs

Reading material

Books:

• System Design Interview Vol. 1 — Alex Xu (ch. 8: Design a URL Shortener)
• Designing Data-Intensive Applications — Martin Kleppmann (chs. 2, 3, 6 for storage & indexing)
• Database Internals — Alex Petrov (ch. on B-trees vs LSM trees — why Postgres vs Cassandra for the mapping table)

Papers:

• Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) — the lookup pattern at the heart of any KV-backed shortener.
• Bigtable: A Distributed Storage System for Structured Data (OSDI 2006) — wide-column design alternative.

Official docs:

• PostgreSQL — SERIAL & BIGSERIAL reference
• Snowflake ID generator (Twitter) — README
• Redis — INCR / INCRBY for counter-based IDs

Blog posts:

• How Bitly works (engineering) — bitly's own writeups.
• Hashids: short, unique, non-sequential IDs — the encoding scheme used by half the industry.
• Designing a URL Shortener — Code Karle — clean writeup with capacity math.

In-depth research material

• Twitter Snowflake — github.com/twitter-archive/snowflake — the 64-bit ID generator everyone copies.
• Sony's sonyflake — github.com/sony/sonyflake — Snowflake-style with longer machine lifetime.
• Instagram Engineering — Sharding & IDs — how Instagram generates IDs across shards.
• Discord — How Discord Stores Billions of Messages — same KV-lookup pattern at scale.
• system-design-primer — github.com/donnemartin/system-design-primer — ~270k ★, includes URL shortener exercises.
• Stripe Engineering — Designing APIs for humans (idempotency keys) — relevant for write idempotency on POST /shorten.

Videos

• Beginner System Design Interview: Design Bitly w/ a Ex-Meta Staff Engineer — Hello Interview · 59 min — the most thorough modern walkthrough; covers numbers, capacity, ID schemes, KV vs SQL.
• Design a URL Shortener (Bitly) — System Design Interview — NeetCodeIO · 48 min — clean, interview-paced, with whiteboard diagrams.
• Tiny URL — System Design Interview Question — TechPrep · 9 min — quick capacity-math refresher; useful as a primer.
• How Does a URL Shortener Work? — ByteByteGo · 6 min — animated overview from Alex Xu's channel.
• TinyURL System Design — codeKarle — codeKarle · 24 min — different framing (capacity → API → DB schema → cache); a useful second perspective.

LeetCode — Encode And Decode Tinyurl

• Link: https://leetcode.com/problems/encode-and-decode-tinyurl/
• Difficulty: Medium
• Why this problem: Counter + base62 keeps codes short; hash-based adds idempotency at cost of collisions.
• Time-box: 30 minutes. Look up the editorial only after.

Assignment / Deliverables

Give yourself a clean 2-hour window and complete all of these before moving on:

1. Read the deep-dive above end-to-end — no skimming. Take notes in your own words.
2. Solve the LeetCode problem below without help first. Only look at the hint after 15 focused minutes; only look at editorial after 30. Log your time.
3. Reproduce one code snippet locally. Pick the snippet that felt least obvious and get it running in a scratch file / notebook.
4. Draw the core diagram from memory. Paper, whiteboard, or tldraw — doesn't matter. If you can't, re-read section 2 and try again.
5. Write a 3-line takeaway in your prep journal: what surprised you, what you still don't understand, what you'd read next.
6. Skim one item from the Reading material section. Bookmark the rest for the weekend.
7. Commit any code + notes to your prep repo with message session-NN: <one-line summary>.

Stretch (optional, +30 min): explain today's topic to a rubber duck / a friend / a voice note. If you can't teach it in 5 minutes, you don't own it yet — flag it and revisit next weekend.

Post-session checklist

By the end of this session you should be able to:

• State the back-of-envelope numbers (QPS write, QPS read, storage) for the spec.
• Pick an ID scheme and defend the choice; name what you sacrificed.
• Defend the choice of KV store over RDBMS at this scale.
• Sketch the write path including idempotency and async analytics.
• Solve the LeetCode encode-and-decode-tinyurl problem using your chosen scheme.

Generated from sessions_data.py + content_part*.py. To edit a video / leetcode / title, edit the data file and re-run write_sessions.py.

Part 2: URL Shortener Part 2 — Cache, CDN, Hot Keys, Abuse

Why this session matters

It builds on the rhythm of one focused topic, paced so you have time to actually absorb it rather than rush.

Agenda

• Read path with cache + CDN + KV — the 95% hit-rate math
• Hot-key problem — viral links blow up one Redis shard
• Edge caching strategy — do the 302 at the edge
• Abuse, phishing, safe-browsing integration
• Analytics pipeline — never block the redirect

Deep dive

1. The read path — where most of the QPS lives

From Part 1: 600k peak read QPS, R:W ≈ 100:1. If every read hit DynamoDB you'd burn money and latency. Solution: layered cache.

User  →  CDN edge  →  Load balancer  →  Resolver svc  →  Redis  →  DynamoDB
         (95% hit)                       (95% hit on miss)   (5% miss)   (last resort)

At steady state, a 95% CDN hit and a 95% Redis hit means the DB sees 600k × 0.05 × 0.05 = 1,500 QPS — totally fine for DynamoDB.

2. Cache hit-rate math (Zipf 0.9)

Short-link traffic is heavily Zipfian — a few links get most of the clicks. With shape parameter ≈ 0.9, the top 10% of codes account for ~85% of traffic. Caching the top 1M codes (out of 180B) in a 10 GB Redis cluster gives you the 95% number above.

Key choices:

• TTL: 24h with stale-while-revalidate — serve stale on background refresh.
• Negative cache: cache misses too (5 min TTL) so attacks scraping random codes don't hit DB.
• Cache key: short:{code} namespace. Value: serialised (long_url, expires_at).

3. Sequence diagram for the redirect

User ── GET /aB3xY9 ──▶ CDN
                              │
                  cached? ──yes──▶ 302 → long URL
                              │
                              no
                              │
                              ▼
                            LB → Resolver
                                       │
                              Redis GET short:aB3xY9
                                       │
                          hit ──yes──▶ 302 + Cache-Control
                                       │
                                       no
                                       ▼
                              DynamoDB GetItem
                                       │
                                       ▼
                              Redis SETEX 24h
                                       ▼
                              302 + Cache-Control public, max-age=86400

Key: the Cache-Control header tells the CDN (and the browser) to cache the 302 itself, so the second hit doesn't even reach Redis.

4. The hot-key problem

A single viral link can hit 50k QPS on its Redis shard, saturating one CPU. Mitigations:

• Edge cache doing the 302 — the CDN absorbs it.
• Client-side cache — the 302 has Cache-Control: public, max-age=86400 — browser remembers.
• Two-level cache — a process-local LRU (1k entries) on every resolver instance. Per-instance hit rate is small but on the hottest 10 keys it absorbs all the load.
• Request coalescing — if 100 requests for the same key arrive at the resolver in the same 50 ms while it's in flight, fold them into one DB read.
• Sharded counters — only relevant if you're updating a click count synchronously (you shouldn't — see analytics).

5. Edge caching strategy

If you're on Cloudflare Workers / Fastly Compute / AWS CloudFront with Lambda@Edge, you can run the 302 logic at the edge:

edge worker:
  code = path[1:]
  if code in edge_kv:
    return Response.redirect(edge_kv[code], 302)
  long = await origin.get(`/api/resolve/${code}`)
  edge_kv.set(code, long, ttl=86400)
  return Response.redirect(long, 302)

Cloudflare Workers KV is eventually consistent (good enough for redirects) and edge-replicated. P99 hot-path latency drops from ~50 ms to <5 ms.

6. Abuse and security

• Phishing / malware — integrate with Google Safe Browsing API on write; re-scan periodically. Block on hit.
• PII in URLs — hash for analytics; drop query-string tokens.
• Rate limiting — per-IP and per-API-key on writes (e.g. 100 / min). Use a token bucket in Redis with INCR + EXPIRE.
• Custom-alias squatting — maintain a blocklist (admin, api, login…) and disallow.
• Open redirects that bypass auth on partner sites — emit Referrer-Policy: no-referrer on the 302.
• HMAC-signed 302s to detect CDN cache poisoning.

7. Analytics — fire-and-forget

Never write analytics on the hot path. Pattern:

resolver:
  emit Kafka event {code, ts, ua, ip, referer}  # async, non-blocking
  return 302

Downstream:

• Flink / Spark Structured Streaming consumes the Kafka topic.
• Aggregates per-minute counts into ClickHouse or Druid for dashboards.
• Daily roll-ups into the warehouse for retention analysis.

If you write to a time-series DB on the hot path: +50 ms latency, -50% capacity. Don't.

8. Multi-region

Reads are dominantly edge-cached, so a single write region + global read replicas works to ~1B URLs:

• Write region: us-east-1 → DynamoDB Global Table replicates everywhere (eventual, ~1 s).
• Read regions: every continent. Resolver hits local DynamoDB replica on cache miss.
• Latency budget: edge serves at <10 ms; on full miss, regional read is ~30 ms.

Beyond 1B writes, partition codes by prefix across regions; route at the edge based on prefix. Conflict-free because codes are unique by construction.

9. Failure modes (the interviewer will ask)

10. Numbers to know for the interview

• 600k peak read QPS → 95% CDN + 95% Redis → 1.5k QPS at DB.
• Cache cost: top 1M of 180B keys gets 95% hit. ~10 GB Redis.
• CDN cost: depends on egress, but typically 10–20% of total infra at this scale.
• DynamoDB cost: ~$1.25 per million read units at on-demand; far cheaper than self-host SQL at this scale.

11. What's next (the next session — CAP / PACELC)

the next session zooms out from one system to the general theory: what does it actually mean for a distributed system to be 'consistent' or 'available'? You'll need it for every subsequent SYS session.

Reading material

Books:

• System Design Interview Vol. 1 — Alex Xu (ch. 8 continued: caching layer; ch. 7: rate limiter)
• Designing Data-Intensive Applications — Kleppmann (ch. 5: Replication, ch. 8: Trouble with Distributed Systems)
• The Linux Programming Interface — Michael Kerrisk (relevant for kernel-level rate-limit primitives if you're curious)

Papers:

• Web Caching with Consistent Hashing (Karger et al., 1997) — the paper that gave us consistent hashing.
• Memcached: A Distributed Memory Object Caching System (Facebook, 2013) — how Facebook ran one of the largest caches ever.

Official docs:

• Redis — Caching patterns reference
• Cloudflare Workers KV / Cache API
• Fastly — Edge caching basics

Blog posts:

• Caching at Netflix: The Hidden Microservice — Netflix Tech Blog
• How Discord Stores Trillions of Messages — Discord — cache layering at scale.
• Cloudflare — Why & how we use Workers KV
• Hot-key mitigation (Stripe Engineering) — relevant patterns.

In-depth research material

• system-design-primer — Caching section — exhaustive comparison of strategies.
• Cloudflare blog — DDoS mitigation case studies — abuse-handling patterns directly applicable to short-link redirects.
• Netflix EVCache — github.com/Netflix/EVCache — Memcached-on-EC2 production code.
• Pinterest Memcached Engineering blog
• Bitly — Why we use NSQ + Redis — the messaging+cache stack behind a real shortener.
• The Twelve-Factor App: Backing Services — the philosophy behind treating cache/CDN as attached resources.

Videos

• Cache Systems Every Developer Should Know — ByteByteGo · 6 min — animated overview of cache-aside, read-through, write-through, write-back.
• Caching Pitfalls Every Developer Should Know — ByteByteGo · 7 min — the failure modes (thundering herd, cache stampede, hot keys, TTL drift).
• Caching in System Design Interviews — Hello Interview — Ex-Meta Staff Eng · 30 min — interview-grade walk through the strategy palette.
• What Is A CDN? How Does It Work? — ByteByteGo · 4 min — CDN basics in 4 minutes — the layer in front of the shortener.
• How does Caching on the Backend work? — Software Developer Diaries · 23 min — middle-tier cache layout: which calls hit Redis vs application memory.

LeetCode — Lru Cache

• Link: https://leetcode.com/problems/lru-cache/
• Difficulty: Medium
• Why this problem: Doubly-linked list + hash-map; both ops O(1).
• Time-box: 30 minutes. Look up the editorial only after.

Assignment / Deliverables

Give yourself a clean 2-hour window and complete all of these before moving on:

1. Read the deep-dive above end-to-end — no skimming. Take notes in your own words.
2. Solve the LeetCode problem below without help first. Only look at the hint after 15 focused minutes; only look at editorial after 30. Log your time.
3. Reproduce one code snippet locally. Pick the snippet that felt least obvious and get it running in a scratch file / notebook.
4. Draw the core diagram from memory. Paper, whiteboard, or tldraw — doesn't matter. If you can't, re-read section 2 and try again.
5. Write a 3-line takeaway in your prep journal: what surprised you, what you still don't understand, what you'd read next.
6. Skim one item from the Reading material section. Bookmark the rest for the weekend.
7. Commit any code + notes to your prep repo with message session-NN: <one-line summary>.

Stretch (optional, +30 min): explain today's topic to a rubber duck / a friend / a voice note. If you can't teach it in 5 minutes, you don't own it yet — flag it and revisit next weekend.

Post-session checklist

By the end of this session you should be able to:

• Draw the full read path including CDN, Redis, DB — with hit/miss arrows.
• Defend the 95/95 cache hit math with a Zipf assumption.
• Solve the hot-key problem with at least 3 layered techniques.
• Sketch the analytics pipeline; explain why it can't be on the hot path.
• Solve lru-cache (Medium) — the workhorse of every cache layer.

Generated from sessions_data.py + content_part*.py. To edit a video / leetcode / title, edit the data file and re-run write_sessions.py.