Design a URL Shortener.

The interviewer slides a marker across the table. "Design bit.ly." It sounds like a ten-minute problem: hash the URL, store it, redirect. Then come the follow-ups. How do two servers avoid handing out the same code? What happens when one link goes viral? Why did you pick 302 and not 301? The question is small on purpose, so every decision shows.

Functional requirements#

Non-functional requirements#

POST /api/v1/urls
Authorization: Bearer <api key>
{ "long_url": "https://example.com/very/long/path?utm=x", "alias": "spring-sale", "expires_at": "2031-01-01" }

201 Created
{ "code": "aZ3kL9q", "short_url": "https://sho.rt/aZ3kL9q" }

GET /aZ3kL9q
302 Found
Location: https://example.com/very/long/path?utm=x

DELETE /api/v1/urls/aZ3kL9q        → 204 (owner only)

• An alias that is already taken returns 409 Conflict.
• Unknown and expired codes return 404, and the 404 is cached too (more on that below).

%% title: URL shortener: create path and redirect path
flowchart TD
  U@{ icon: "sd:users", label: "Users, browsers, apps" } --> LB@{ icon: "sd:load-balancer", label: "Load balancer" }
  LB -->|"POST /api/v1/urls"| WS["Shorten service<br/>holds a block of IDs"]:::core
  LB -->|"GET /{code}"| RS["Redirect service"]:::hot
  WS -->|"next block of 10,000"| KA@{ icon: "sd:key", label: "Range allocator<br/>(one counter row)" }
  WS -->|"put-if-absent"| DB@{ icon: "sd:database", label: "URL store<br/>key-value, sharded by code" }
  RS -->|"1 · cache-aside"| R@{ icon: "tech:redis", label: "Redis<br/>hot codes + 404s" }
  RS -->|"2 · on miss"| DB
  RS -->|"click event, async"| K@{ icon: "tech:kafka", label: "Kafka · clicks" }
  K --> AN@{ icon: "sd:chart", label: "Click counts" }
  class U client
  class LB edge
  class KA,DB store
  class R cache
  class K queue
  class AN service

• Shorten service: validates the URL, takes the next ID from its local block, turns it into a 7-character code and writes code → long_url with put-if-absent.
• Redirect service: stateless. Looks up the code in Redis, falls back to the URL store, answers with a 302, and publishes a click event without waiting for it.
• URL store: a key-value lookup by code, so any store that shards by key works (a key-value database, or sharded SQL keyed on code).
• Click counts: a consumer aggregates Kafka events into per-link counters; they lag by seconds to a minute, as agreed.

Deep dive 1: Where do codes come from?#

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
SPACE = 62 ** 7            # ~3.5 trillion codes
MULT = 1_580_030_173       # any odd number not divisible by 31 is coprime to 62^7

def to_code(n: int) -> str:
    n = (n * MULT) % SPACE          # bijective scramble: unique in, unique out
    out = []
    for _ in range(7):
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

The scramble only hides the order from casual eyes; it is not encryption. If enumeration is a real threat (private documents behind short links), use random codes with put-if-absent, or longer codes.

Deep dive 2: Making the redirect fast and cheap#

• Cache-aside in Redis: read the code from Redis; on a miss, read the store and set it with a TTL. With a skewed click distribution, most redirects never touch the store.
• Cache the misses too: scanners try random codes. Storing "not found" for a short TTL stops them from hammering the store.
• Viral links: one code can get a burst far above its neighbours. Short-lived caching at a CDN edge, or a small in-process cache in each redirect server, absorbs it before it reaches a single Redis shard.
• Clicks off the critical path: the redirect publishes a click event to Kafka and returns. If Kafka is slow, the redirect still works; counts catch up later.
• Expiry on read: the cached value carries expires_at, and the redirect service checks it before answering, so an expired link stops at once even if a cache entry outlives it.

• The full version of this problem, with sharding, hot keys and rate limits at 100M links a day: Week 1 Capstone: URL Shortener at Scale
• Sharding the URL store by code, consistent hashing: Week 1 · Day 1: Partitioning Deep-Dive
• Viral links and hot keys: Week 1 · Day 4: Hot Keys and Skew
• Cache-aside, TTLs and negative caching: Week 4 · Day 1: Caching Patterns
• Edge, in-process and Redis caches together: Week 4 · Day 5: Multi-Tier Caching
• Rate-limiting the create API: Week 1 · Day 3: Rate Limiting at Scale
• Base 62 and capacity math: Week 0 · Part 3: Back-of-the-Envelope Estimation