DevPath
Tracks

Design a URL Shortener

A full worked design: requirements, estimates, API, data model, base62 id encoding, redirect path, caching, scaling, and trade-offs such as 301 versus 302.

intermediate45 min#system-design#url-shortener#base62#id-generation#worked-example

Prerequisites: A Framework for System Design, Caching Strategies, Databases at Scale

Why it matters

The URL shortener is the "hello world" of system design. It is small enough to finish in an interview, yet it touches every part of the framework: requirements, estimation, API, data model, id generation, caching, and scaling. Working through it end to end shows you how the generic ideas from the earlier lessons combine in one concrete system.

Intuition

A shortener is a giant dictionary. The key is a short code like aZ3k9; the value is the long URL. Creating a short link means inventing a fresh key and storing the pair. Following one means looking the key up and redirecting. Everything interesting is in two questions: how do we invent unique short keys without collisions, and how do we make a lookup-heavy system fast and durable?

How it works

1. Requirements

Functional: create a short link for a long URL; redirect a short link to the original; optionally custom aliases and expiry. Non-functional: redirects must be very fast and highly available (a dead link is a broken page for someone else), codes must be unique, and links should not be easily guessable if they are private. Out of scope for now: analytics dashboards, user accounts.

2. Estimates

Assume 100 million new links per month and a read-to-write ratio of 100 to 1.

  • Writes: 100 million per month is about 40 per second on average (a month is about 2.6 million seconds).
  • Reads: 100 times that, roughly 4,000 per second on average, with peaks several times higher.
  • Storage: if each record is about 500 bytes, 100 million records per month is about 50 GB per month, or roughly 3 TB over five years before replication.
  • Code length: with 62 characters, 6 characters give about 56.8 billion codes and 7 give about 3.5 trillion. Seven is plenty for decades of growth.

This is a read-heavy system with modest write volume and a small total dataset, so caching helps a lot and a single sharded store is realistic.

3. API

POST /links        body: long_url, optional alias, optional expires_at
                   returns: short_code, short_url
GET  /{code}       returns: 301 or 302 redirect with Location header
                   404 if unknown, 410 if expired

301 versus 302. A permanent redirect (301) may be cached by browsers, which reduces your load but means you stop seeing those clicks and cannot change the target. A temporary redirect (302) sends every click through you, which keeps analytics and edits possible at the cost of more traffic.

4. Data model

One table or collection: code (primary key), long_url, created_at, expires_at, optional owner_id. The dominant access pattern is a point lookup by code, which fits a key-value store or a relational table with a primary-key index. Because lookups are by key, the shard key is the code itself.

5. Generating the code

Options:

  • Hash the URL and take the first few characters. Simple and gives the same code for the same URL, but different URLs can collide, so you must check and retry.
  • Random code with a uniqueness check. Not guessable, but needs a retry on collision.
  • Counter plus base62. Allocate a unique integer id and encode it in base 62 (digits, lowercase, uppercase). No collisions by construction and short codes. The downside is that sequential ids are guessable and enumerable. If that matters, shuffle the bits or use a keyed permutation of the id before encoding.

The counter must work across many servers. Common approaches: a central sequence service handing out ranges (each app server takes a block of, say, 1,000 ids and uses them locally, so the counter is touched rarely), or a time-and-machine-based id scheme. Range allocation wastes some ids on a crash, which is harmless.

Here is the counter-plus-base62 option encoding id 125, the first id the code below hands out. Repeated division by 62 produces digits from the right.

125
0
Start with n = 125 and an empty digit list.
step 1 / 4

Encoding 125 in base 62. Each division peels off the last digit, so digits come out in reverse and must be flipped at the end.

6. High-level design

 client --> load balancer --> app servers --> cache (code -> url)
                                   |               | miss
                                   |               v
                                   +-------> database (sharded by code)
                                   |
                              id allocator (hands out id ranges)

Read path (the hot one): check the cache; on a miss, read the database, fill the cache, return the redirect. Link mappings rarely change, so a long TTL with LRU eviction works well, and a small cache holds the popular head of the distribution.

Write path: validate the URL, take the next id, encode it, store the pair, return the short URL.

Client
Load balancer
App serversstateless
Id allocatorhands out id ranges
Cachecode to URL
Databasesharded by code
The whole system. The cache sits in front of the database to absorb the 100-to-1 read traffic, and the allocator is touched rarely because each app server reserves a block of ids.
ClientApp serverCacheDatabasePOST /links (long URL)store code to URLshort URLGET /21lookup 21missread 21long URL301 or 302 Location: long URL
Create (top three messages) writes once: take an id, encode it, insert the pair. Redirect (the rest) is the hot path. After the miss shown here the app also fills the cache, so later clicks stop at the cache.

7. Deep dives and trade-offs

  • Availability of the read path. Redirects dominate, so replicate the database and cache across zones. Writes can degrade independently.
  • Expiry. Check expires_at on read and clean up in a background job.
  • Abuse. Rate limit link creation and scan targets for malicious URLs.
  • Custom aliases. Insert with a unique constraint and return a conflict if taken.
  • Deleting and reusing codes. Avoid reusing a code quickly; an old link floating around should not suddenly point somewhere new.
OperationTimeNotes
Encode id to base62O(log_62 n)About 7 steps for trillions of ids
Redirect (cache hit)O(1)One cache lookup
Redirect (cache miss)O(1)One indexed database lookup
Create linkO(1)Allocate id, encode, insert

Code: base62 encoding and a tiny shortener

The id allocator here is a simple counter; in production it would hand out ranges from a shared service.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
def encode(n):
    if n == 0:
        return ALPHABET[0]
    digits = []
    while n > 0:
        n, r = divmod(n, 62)
        digits.append(ALPHABET[r])
    return "".join(reversed(digits))
 
def decode(code):
    n = 0
    for ch in code:
        n = n * 62 + ALPHABET.index(ch)
    return n
 
class Shortener:
    def __init__(self, start=125):
        self.next_id = start
        self.by_code = {}
        self.by_url = {}
 
    def shorten(self, url):
        if url in self.by_url:  # same URL gets the same code
            return self.by_url[url]
        code = encode(self.next_id)
        self.next_id += 1
        self.by_code[code] = url
        self.by_url[url] = code
        return code
 
    def resolve(self, code):
        return self.by_code.get(code)
 
for n in [0, 61, 62, 125, 1_000_000_000]:
    print(n, "->", encode(n), "->", decode(encode(n)))
print("62^6 =", 62 ** 6, "| 62^7 =", 62 ** 7)
 
s = Shortener()
a = s.shorten("https://example.com/a/very/long/path?x=1")
b = s.shorten("https://example.com/other")
again = s.shorten("https://example.com/a/very/long/path?x=1")
print(a, b, again == a)
print(s.resolve(b), s.resolve("zzz"))

Both versions print:

0 -> 0 -> 0
61 -> Z -> 61
62 -> 10 -> 62
125 -> 21 -> 125
1000000000 -> 15FTGg -> 1000000000
62^6 = 56800235584 | 62^7 = 3521614606208
21 22 True
https://example.com/other None

Id 125 is 21 because 125 = 2 * 62 + 1. A billion ids still fit in just six characters. Decoding the encoded value always returns the original id, which is the property that makes the scheme collision-free.

1
62^5
5
62^4
F
62^3
T
62^2
G
62^1
g
62^0
The id 1,000,000,000 as six base-62 digits, with each digit's place value underneath. Because 62^6 is about 56.8 billion, six characters already cover a billion ids.

Common pitfalls

  • Sequential ids that leak information. Anyone can walk 1, 2, 3... and discover every link, and learn your volume. Permute the id if links are private.
  • Hash truncation without collision handling. Two URLs can share a prefix. Check for conflicts or avoid hashing.
  • Forgetting that redirects dominate. Optimize and protect the read path; creation can be slower and rate limited.
  • Open redirect and abuse. Shorteners are used to hide phishing links. Validate, scan, and rate limit.
  • Treating 301 as free. It reduces load but removes your ability to count clicks or change the destination.
  • Single points of failure in the id allocator or the cache. The read path should survive either being down.

Practice

How many characters do we need? easy

Hint

Compare the total number of links you expect against 62 to the power of length.

Show solution

Say 100 million links per month for ten years is about 12 billion. 62^6 is about 56.8 billion, which already covers that, and 62^7 gives roughly 3.5 trillion for headroom. Choose 7 so growth, wasted id ranges, and sparse permutations are all comfortable.

Support custom aliases medium

Hint

What database feature guarantees an alias is not taken twice?

Show solution

Insert the alias as the primary key with a unique constraint. If the insert fails, return a conflict error to the caller. Reserve a character pattern or length range for generated codes so a custom alias can never collide with a future generated one.

Make codes unguessable medium

Hint

You want uniqueness of a counter but randomness of appearance.

Show solution

Apply a reversible, keyed permutation to the counter value (for example a few rounds of a Feistel-style mixing of its bits) and base62-encode the result. Uniqueness is preserved because the mapping is one-to-one, and the codes no longer look sequential. Keep the key secret.

Scale reads 10x hard

Hint

Where does the load land first: cache, database, or app tier?

Show solution

Add app servers behind the load balancer (they are stateless), grow and replicate the cache, and add database read replicas. Cache hit rate matters most: the popular links are a small share of all links, so even a modest cache absorbs most reads. Use a CDN or edge caching for the very hottest redirects if you use 301 or can tolerate caching.

Interview questions

  1. How do you generate short codes? Counter plus base62 for guaranteed uniqueness; random with a collision check or a hash with collision handling as alternatives. State the trade-offs, especially guessability.
  2. 301 or 302? 301 is cacheable and cuts load but hides clicks and freezes the target; 302 keeps every click visible and flexible at higher cost.
  3. How do you scale it? Cache the hot read path, replicate the database, shard by code, and allocate ids in ranges.
  4. What are the failure modes? The id allocator, cache, or database being unavailable; handle with replication, id ranges held locally, and serving redirects from cache when the database is slow.

Interviewers look for: a clear estimate showing the system is read-heavy, a collision-free id strategy, and awareness of 301 versus 302 and abuse.

Quick check

Which property makes the counter-plus-base62 approach collision-free?

Finished this lesson?

Further resources

Related lessons