dineshblog

Search Tech Journey

Find topics, journeys and posts

back to blog
system designintermediate 15m2026-07-06

URL Shortener — IDs, Storage, Cache, CDN

A deep-dive on IDs, Storage, Cache, CDN — part of a 24-topic evergreen learning series.

Why this session matters

Part of a 24-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 (skim before the session)

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.

ChoiceFit
DynamoDB / CassandraHash-partitioned by short_code. Horizontal scale. 90 TB is fine.
BigtableSame model, GCP-flavoured.
Postgres (sharded)Works to a point. At 600k read QPS you need read replicas + Citus. Operationally heavier.
Redis (sole store)Too expensive at 90 TB and not durable enough for source of truth.

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:

Official docs:

Blog posts:

In-depth research material

Videos

LeetCode — Encode And Decode Tinyurl

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

Pre-read (skim before the session)

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)

FailureWhat happensMitigation
Counter shard downWrites stallBatched IDs in app cache buy 5–10 m
Redis cluster splitDB absorbs traffic brieflyCircuit-breaker + serve stale
CDN poisoningWrong long URL servedHMAC-signed 302; short TTL
DynamoDB hot partitionThrottling on one keyCache absorbs; spread analytics writes
Mass abuse scraperEats cache + DB capacityNegative-cache misses; WAF rate-limit

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:

Official docs:

Blog posts:

In-depth research material

Videos

LeetCode — Lru Cache

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.

← previous

Spark Execution Model — Jobs, Stages, Shuffles, Catalyst

next →

SOLID Principles & Design Patterns — SRP, OCP, LSP, ISP, DIP