Design Case Studies · Lesson 05

Design: URL Shortener

A URL shortener looks deceptively simple — until you need to serve a billion redirects per day, count every click accurately, and avoid generating the same short code twice. This is an original design created for this course.

1 · Requirements

Start with a concrete brief. A URL shortener must:

Non-requirements for this design: real-time analytics dashboards, link expiry (can be added later), geographic redirect rules. Stating these out loud in an interview earns points — it shows scope control.

2 · Design decisions

2a. Key generation: counter vs hash

Think of the short code as a ticket number at a deli. Strategy 1: the deli has a ticket machine — you pull the next sequential number and encode it. Strategy 2: you hash the order itself and hope two orders never hash alike. The ticket machine is deterministic; the hash approach is probabilistic.

This design uses base62 of a counter with a distributed counter (e.g. Redis INCR or a Snowflake-style ID) to avoid the single-writer bottleneck while keeping code length short and collisions impossible.

2b. 301 vs 302 — the cache vs analytics trade-off

Both status codes redirect the browser, but with very different long-term behaviour:

301 lets the CDN and browser cache the redirect, so at massive scale the server load approaches zero for popular links. The price is losing click counting after the first request. 302 guarantees every click is counted but every click costs a server round-trip. Most commercial URL shorteners use 302 by default because analytics are the product, and add 301 as an opt-in "performance mode" for users who don't need tracking.

2c. Cache hot links and CDN

With 302 redirects, the redirect server is in the critical path of every click. Mitigate this with two caching layers:

1. CDN edge: cache /:code → 302 + Location header at the edge. Even with 302, the CDN can serve the redirect header if Cache-Control allows short TTLs (e.g. Cache-Control: public, max-age=60). The click still hits the CDN PoP — far faster than origin — and the analytics counter is updated asynchronously by a stream of CDN access logs.
2. In-process LRU cache: each redirect server holds the top ~100k hot links in memory. Lookup is sub-millisecond. Evict on a TTL of a few minutes to stay consistent with updates.

See Caching (rel-07) for cache invalidation strategies and TTL tuning.

2d. Rate-limit link creation

The read path (redirect) is naturally self-throttling — you can only request links that exist. The write path (create link) is the abuse vector: spammers create millions of phishing links. Rate-limit by API key (for authenticated users) and by IP (for unauthenticated). See Rate Limiting (rel-03) for token-bucket and sliding-window algorithms. A reasonable default: 100 link creations per hour per API key, 10 per hour per unauthenticated IP.

3 · The API model

# 1. Create a short link
POST /v1/links
Authorization: Bearer <api_key>
Content-Type: application/json

{
  "url": "https://example.com/very/long/path?with=many&query=params",
  "alias": "launch2026"  # optional custom alias
}

# Response 201
{
  "code": "launch2026",
  "short_url": "https://shr.example/launch2026",
  "original_url": "https://example.com/very/long/path?with=many&query=params",
  "created_at": "2026-06-20T10:00:00Z"
}

# Conflict — alias already taken
# Response 409
{
  "error": "alias_conflict",
  "message": "The alias 'launch2026' is already in use."
}

# Rate limit exceeded
# Response 429 with Retry-After header

# 2. Redirect (the hot path)
GET /launch2026   # or /:code at the redirect domain

# Response 302 (tracking) or 301 (performance mode)
HTTP/1.1 302 Found
Location: https://example.com/very/long/path?with=many&query=params
Cache-Control: public, max-age=60
X-Link-Code: launch2026

# Code not found → 404
HTTP/1.1 404 Not Found
{ "error": "link_not_found" }

# 3. Link analytics
GET /v1/links/launch2026/stats?from=2026-06-01&to=2026-06-20
Authorization: Bearer <api_key>

# Response 200
{
  "code": "launch2026",
  "total_clicks": 142837,
  "unique_ips": 98204,
  "top_countries": [
    { "country": "US", "clicks": 54012 },
    { "country": "IN", "clicks": 31440 }
  ],
  "top_referrers": [
    { "referrer": "twitter.com", "clicks": 28900 }
  ]
}

4 · Evaluation & latency budget

Read-heavy scaling

With a 100:1 read/write ratio, the redirect path is the system's heartbeat. The CDN absorbs the majority of traffic — popular links like a viral tweet hit hundreds of millions of times will be cached at CDN PoPs globally. The redirect server only sees CDN cache misses (cold start, low-traffic links, TTL expiry). The in-process LRU cache eliminates most database reads even after CDN misses.

Write path

Link creation is rare but critical — it must not fail silently. The counter service (Redis INCR) is the only synchronous external call on the write path; it's fast (~1 ms) and Redis replication provides durability. The database write is synchronous to return the short URL to the caller. Analytics writes are always async — a dropped analytics event is far less severe than a dropped link creation.

Latency budget

# Alias taken by another user → 409 Conflict
{
  "error": "alias_conflict",
  "message": "'sale' is already in use. Try 'sale-2026' or omit alias for auto-generation.",
  "suggestions": ["sale-2026", "mysale"]
}

# Alias taken by the SAME user, same target URL → 200 (idempotent)
{
  "code": "sale",
  "short_url": "https://shr.example/sale",
  "reused": true
}

# Alias taken by the same user, DIFFERENT target URL → 409
# (changing the destination silently would break existing links)

Under the hood: the core mechanism

The two mechanisms that make a URL shortener work are the base62 encoding of a counter (write path) and the three-layer cache lookup (read path). Both are worth tracing numerically so you can answer "how short is the short code?" and "how fast is the redirect?"

Base62 encoding: worked numeric trace

Base62 uses the alphabet 0–9 a–z A–Z (62 characters). To encode a counter integer, repeatedly divide by 62 and collect the remainders — the remainders in reverse order give the encoded string. The alphabet index maps remainder → character.

# Alphabet: index 0='0', 1='1', …9='9', 10='a', 11='b', …35='z', 36='A', …61='Z'

# Example 1: counter id = 125
125 ÷ 62 = 2 remainder 1   → character '1'
  2 ÷ 62 = 0 remainder 2   → character '2'
# remainders collected in reverse: '2', '1'
short code = "21"

# Example 2: counter id = 3844  (62²)
3844 ÷ 62 = 62 remainder 0  → character '0'
  62 ÷ 62 =  1 remainder 0  → character '0'
   1 ÷ 62 =  0 remainder 1  → character '1'
short code = "100"   # 3-char code starts at id 3844

# Example 3: counter id = 56,800,235,584  (62⁶ = first 7-char code)
# IDs 0 – 62^6-1 (= 56,800,235,583) fit in exactly 6 base62 chars
# That is 56 billion unique short codes from 6 characters
6 chars → 56 billion codes  # ample for any URL shortener

# Decode is the reverse: treat each character as a digit in base-62
"21" → 2 × 62¹ + 1 × 62⁰ = 124 + 1 = 125   ✓

A monotonically increasing Redis INCR counter guarantees no two clients ever get the same integer — so no two codes collide. The base62 encoding of that integer is computed locally (no additional round-trip). This is why the counter approach is strictly better than hashing for collision avoidance: hash-based codes require a "does this code exist?" DB read before every write.

Collision handling for custom aliases

Custom aliases bypass the counter — the caller supplies an arbitrary string. The uniqueness check is a simple SELECT on the alias column (which has a unique index). The race condition where two concurrent requests try to claim the same alias is handled by letting the DB unique constraint be the final arbiter: the first writer's INSERT succeeds; the second gets a unique-constraint violation, which the API layer catches and returns as a 409.

# Write path for a custom alias (pseudocode)
function create_link(url, alias):
  try:
    code = alias if alias else base62(redis.INCR("link_counter"))
    db.execute("INSERT INTO links (code, url) VALUES (?, ?)", code, url)
    return 201, { code, short_url: "https://shr.example/" + code }
  except UniqueConstraintViolation:
    return 409, { error: "alias_conflict" }

Redirect read path: worked lookup trace

The redirect is the hot path. Follow a request for GET /abc123 through all three layers:

# Step 1: Request arrives at CDN edge PoP (e.g. Cloudflare London)
GET /abc123
→ CDN checks its cache for key "abc123"
  CDN HIT:  serve cached 302 Location header immediately — ~5 ms
  CDN MISS: forward to origin redirect server

# Step 2: Origin redirect server (CDN miss)
→ check in-process LRU cache (hot_links["abc123"])
  LRU HIT:  return 302 Location — ~1 ms
  LRU MISS: query the links DB

# Step 3: DB lookup (both caches missed)
SELECT url FROM links WHERE code = 'abc123'  -- indexed; ~5 ms
  FOUND:  populate LRU cache, respond:
          HTTP/1.1 302 Found
          Location: https://example.com/very/long/path
          Cache-Control: public, max-age=60
  NOT FOUND: HTTP/1.1 404 Not Found  {"error":"link_not_found"}

# CDN caches the 302 response for 60 s at the edge
# Next request for /abc123 from any user near that PoP hits the CDN HIT path

The analytics counter is intentionally not on this synchronous path. Each redirect server writes a click event to an in-memory ring buffer, which is flushed to a stream (Kafka or Kinesis) every second. An analytics consumer aggregates these into pre-computed hourly counts. Approximate counts with a ~1-second lag are far better than making every redirect block on a DB UPDATE counter = counter + 1.

Operating & debugging it

The two most common problems are cache invalidation mistakes (a link is updated but old redirects keep serving) and counter skew (the Redis counter diverges, producing gaps or — worse — duplicate codes on failover). Both are diagnosable with standard tools.

Inspect the redirect path live

Symptom → cause → fix

1. Test a redirect with curl -i first; read x-cache to know whether origin was involved.
2. Force an origin hit with -H "Cache-Control: no-cache" and read x-redirect-latency-ms.
3. Verify the DB row directly: SELECT code, url, created_at FROM links WHERE code = 'abc123'.
4. Check Redis counter health: compare the current value against expected links-per-hour rate.
5. After any link update, confirm CDN purge happened; re-run curl -i to verify x-cache: MISS on the next request.

Sources & further reading

• MDN — 301 Moved Permanently
• MDN — 302 Found
• Cloudflare — Cache Behavior (redirect caching)
• Redis INCR command — atomic counter
• AWS Architecture Blog — Building a URL shortener on AWS