Design a URL Shortener (like bit.ly)

The prompt: design a service that turns https://example.com/some/very/long/path?with=params into https://sho.rt/aZ3k9Qx, and redirects anyone who visits the short link.

1. Requirements

Functional

• Create a short link for a long URL; optionally accept a custom alias.
• Redirect a short link to its long URL.
• Optional: expiry dates and click counts.

Non-functional

• Very high availability: if redirects fail, millions of links across the internet break.
• Low redirect latency: under ~50 ms server-side.
• Durability: links must never be lost.
• Codes should not be easily guessable in sequence (nice to have).

2. Estimates

Assume 100 million new links a month and 100 redirects per link (read:write = 100:1).

• Writes: 10⁸ / (2.5 × 10⁶ s) ≈ 40 links/s (peak ~100/s).
• Reads: 40 × 100 = 4,000 redirects/s (peak ~10–20K/s).
• Storage: one row is ~500 bytes (code, long URL, owner, timestamps). 10⁸ × 12 × 5 years × 500 B ≈ 3 TB. That is modest, but more than we’d like on one machine long-term.
• Cache: 20% of last month’s links: 0.2 × 10⁸ × 500 B ≈ 10 GB, which fits on one Redis node.

Conclusion: a read-heavy, latency-sensitive lookup by key. Caching matters most; writes are easy.

3. API

POST /v1/links   { "url": "https://…", "alias": "optional", "expires_at": "optional" }
     → 201 { "code": "aZ3k9Qx", "short_url": "https://sho.rt/aZ3k9Qx" }
GET  /{code}     → 302 Found, Location: <long url>   (404 if unknown, 410 if expired)

301 or 302? A 301 (permanent) is cached by browsers, so repeat clicks never reach us, which is cheaper but kills analytics. Use 302 if you count clicks.

4. Data model

links
  code        varchar(10)  PRIMARY KEY
  long_url    text
  owner_id    bigint       (nullable)
  created_at  timestamp
  expires_at  timestamp    (nullable)

The only hot query is get long_url by code, so a key-value store (DynamoDB, Cassandra) or a relational DB with the code as primary key both work. At 3 TB and 20K reads/s, a key-value store with built-in sharding by code is the simplest to scale.

5. Generating short codes

This is the heart of the question. With base62 (a–z A–Z 0–9), 7 characters give 62⁷ ≈ 3.5 trillion codes.

Option A: hash and truncate. Take md5(long_url), base62-encode it, keep 7 characters. Collisions happen, so check whether the code exists and, if it does, rehash with a salt. Each write costs an extra read, and the check-then-insert races under concurrency (use a conditional insert).

Option B: a counter + base62 (recommended). Give every link a unique integer ID and encode it in base62:

id 125,000,000,001  →  base62  →  "8M0kX7"

There are no collisions by construction. The question becomes how to generate unique IDs across many servers:

• a ticket server / range allocator: each app server leases a block of 1 million IDs from a central counter (stored in a strongly consistent DB or ZooKeeper) and hands them out locally, so the counter is touched once per million links;
• or Snowflake-style IDs (timestamp + machine ID + sequence).

Sequential IDs make codes guessable. If that matters, scramble the ID with a reversible bijection before encoding (multiply by a large odd number mod 62⁷, or a small Feistel cipher). Codes still never collide.

Custom aliases: insert with a uniqueness check (a conditional put); return 409 if taken.

6. High-level design

flowchart LR
  U[Users / browsers] --> CDN[CDN / edge]
  CDN --> LB[Load balancer]
  LB --> W[Write API]
  LB --> R[Redirect service]
  W --> IDS[ID range allocator]
  W --> DB[(Key-value store<br/>sharded by code)]
  R --> C[(Redis cache)]
  C -. miss .-> DB
  R -->|click event| K[[Kafka]]
  K --> AN[Analytics consumers] --> OLAP[(Analytics DB)]

Redirect path (the hot path):

1. GET /aZ3k9Qx reaches a redirect server.
2. Check Redis; on a hit (≈90%+), return 302 immediately.
3. On a miss, read the key-value store, populate the cache, return 302.
4. Fire a click event asynchronously; never make the user wait for analytics.

Popular links can even be cached at the CDN edge with a short TTL, which takes the load off origin entirely.

Write path: validate the URL (and check it against a malware/phishing blocklist), get the next ID from the local block, encode it, insert, return.

7. Deep dives

Analytics. Writing a DB row per click at 20K/s is wasteful. Publish click events (code, time, country, referrer, device) to Kafka; consumers aggregate counts per minute into an analytics store (ClickHouse, Druid, BigQuery). Counts lag by seconds, which is fine.

Expiry. Check expires_at on read and return 410. A background job deletes expired rows; store TTLs in the cache too.

Availability. Replicate the KV store across three zones; run redirect servers in several regions behind geo-DNS. The redirect path depends only on the cache and the KV store, not on the ID allocator, so redirects keep working even if writes are degraded.

Abuse. Rate-limit link creation per user/IP, scan destinations against blocklists, and allow takedowns (a disabled flag checked on redirect).

Hot links. A viral link can send 100K requests/s to one cache key. Replicate hot keys, keep a tiny in-process LRU cache on each redirect server, and let the CDN absorb it.