Lesson 10 of 15 Case Studies

Design a URL Shortener (TinyURL)

URL shortener system design step by step: requirements, estimates, base62 codes, ID generation, database and cache choices, redirects and analytics.

50-60 min intermediate 0/15 lessons done
Course contents Lesson 10 of 15 · 0 done
On this page (11 sections)
  1. The problem
  2. 1. Requirements
  3. 2. Estimates
  4. 3. API and data model
  5. 4. Generating short codes
  6. 5. High-level design
  7. 6. Storage
  8. 7. Deep dives
  9. Key takeaways
  10. Exercises
  11. Quiz

The problem

Design a service like TinyURL or bit.ly: users submit a long URL and get a short one such as sho.rt/g9Xk2Pq; visiting the short URL redirects to the original. It’s the most common warm-up design question because it touches estimation, ID generation, storage, caching and scale.

1. Requirements

Functional

  • Create a short link for a long URL (optionally with a custom alias and an expiry).
  • Redirect a short link to its long URL.
  • Basic click analytics (count per link).

Non-functional

  • 100M new links per day; reads 100x writes.
  • Redirect latency p99 under 50 ms worldwide.
  • Redirects highly available (99.99%); a link once created must never be lost.
  • Short codes shouldn’t be easily guessable in sequence (nice to have).

2. Estimates

From lesson 2: ~1.2k writes/s, ~115k reads/s average, ~350k at peak, ~91 TB over five years before replication. Code length: 62^7 ≈ 3.5 trillion, comfortably more than the ~180 billion links we’d create in five years, so 7 base62 characters.

3. API and data model

POST /v1/links     {long_url, alias?, expires_at?}  -> 201 {code, short_url}
GET  /{code}       -> 301 or 302, Location: long_url

links(code PK, long_url, owner_id, created_at, expires_at)

301 or 302? A 301 (permanent) lets browsers cache the redirect, cutting load, but you stop seeing repeat clicks. A 302 (temporary) sends every click through you, which analytics needs. Most shorteners use 302 (or 307).

4. Generating short codes

This is the heart of the problem. Options:

a) Hash the URL (MD5/SHA, take 7 base62 characters). Same URL gives the same code (free dedup), but truncated hashes collide; you must check the database and retry with a salt, which adds a read to every write.

b) Random 7-character code, check for collision, retry. Simple, unguessable; collision checks are cheap while the space is mostly empty (180B of 3.5T is ~5% full after five years).

c) Unique counter → base62. Every link gets a unique integer id, encoded in base62. No collisions ever. The challenge is generating unique ids across many servers without a bottleneck. A clean solution is range leasing: a coordinator (a database row or etcd) hands each app server a block of 1,000 ids; the server mints codes locally until the block runs out.

"""Short codes for a URL shortener: base62 of a unique numeric id."""
import string

ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase  # 62 chars


def encode(n: int) -> str:
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))


def decode(code: str) -> int:
    n = 0
    for ch in code:
        n = n * 62 + ALPHABET.index(ch)
    return n


class IdRangeAllocator:
    """Each app server leases a block of ids so it can mint codes without coordination."""

    def __init__(self, block_size=1000):
        self.next_block_start = 1  # in production this counter lives in a database or ZooKeeper/etcd
        self.block_size = block_size

    def lease(self):
        start = self.next_block_start
        self.next_block_start += self.block_size
        return iter(range(start, start + self.block_size))


if __name__ == "__main__":
    print("7 chars of base62 cover", f"{62 ** 7:,}", "codes")
    allocator = IdRangeAllocator()
    server_a, server_b = allocator.lease(), allocator.lease()
    for server, ids in (("A", server_a), ("B", server_b)):
        n = next(ids)
        print(f"server {server}: id {n} -> {encode(n)}")
    big = 3_521_614_606_207
    print(big, "->", encode(big), "->", decode(encode(big)))
7 chars of base62 cover 3,521,614,606,208 codes
server A: id 1 -> 1
server B: id 1001 -> g9
3521614606207 -> ZZZZZZZ -> 3521614606207

Sequential ids produce guessable codes. If that matters, scramble the id with a reversible permutation (e.g. multiply by a large odd number modulo 62^7, or a small block cipher) before encoding, or use option (b).

Custom aliases simply attempt an insert with the alias as primary key; a unique-key violation returns 409 Conflict.

5. High-level design

                     +--------------------- CDN / edge (optional) ---------------------+
client --> GeoDNS --> load balancer --> stateless app servers --> cache (Redis cluster)
                                              |                      | miss
                                              |                      v
                                              +--> id-range service  KV store (sharded by code)
                                              +--> click events --> queue --> analytics workers --> OLAP store

Redirect path: look up code in the cache; on a miss read the store and fill the cache (cache-aside, lesson 4). Popular links are read millions of times, so the hit ratio is very high. Then return 302 and publish a click event asynchronously so analytics never slows the redirect.

Create path: validate the URL, take the next id from the local block, encode, write to the store, return the code.

6. Storage

Access is a pure key lookup by code and the data is huge, so a distributed key-value or wide-column store (DynamoDB, Cassandra) sharded by code fits well. A sharded relational database also works. Replicate 3x across zones for durability. Expired links are filtered on read and removed by a background job.

7. Deep dives

  • Hot links: a viral link could overload one cache shard; keep a small in-process LRU on app servers for the hottest codes.
  • Multi-region: replicate the store to several regions; redirects are reads, so each region serves locally. Writes go to the region that owns the id block, so ids never collide.
  • Abuse: rate-limit creation per user/IP (next lesson) and check URLs against malware lists.
  • Analytics at scale: aggregate clicks per minute in the stream processor before writing, rather than one database write per click.

Key takeaways

  • 7 base62 characters cover trillions of links; estimates justify caching and sharding.
  • Counter + base62 with leased id ranges avoids collisions without a central bottleneck; random codes trade a collision check for unguessability.
  • Redirects are a cache-heavy key lookup; send analytics through a queue so it never slows the redirect.
  • Use 302 if you need click analytics; 301 if you want to minimise load.

Exercises

  1. Implement a reversible scrambler so consecutive ids produce unrelated-looking codes, and verify you can decode back.
  2. Estimate the cache size needed to hold the hottest 20% of links created in the last month.
  3. Extend the design to let users edit where a link points. What changes in caching?

Quiz

  1. Why might a URL shortener return 302 instead of 301?
  2. What’s the main drawback of truncating a hash of the URL to make the code?
  3. How does range leasing avoid a bottleneck on id generation?
Show answers
  1. With 302 every click passes through the service, so it can count clicks and change destinations; 301 gets cached by browsers.
  2. Truncated hashes can collide, so every write must check for an existing code and retry.
  3. Each server gets a block of ids at once and allocates locally; the coordinator is contacted only once per block.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).