SD12.1 · LESSON 1 OF 6

A URL shortener

Produce an end-to-end design whose data paths, capacities and failure behavior satisfy explicit requirements.

THE IDEA

A URL shortener

Design decisions first: how keys are allocated, how uniqueness is guaranteed, what a redirect does (302 for a live link, 404 for an unknown key, 410 for an expired one) and whether links expire. Random keys need collision handling: 62⁷ is about 3.5 trillion, but a million links in a 62⁶ space already produce around 9 colliding pairs. The size of a key space is not proof that generated keys are unique, so the insert must check and retry, never overwrite.

key length (characters)6links created1,000,000

key space = 62^6 = 56,800,235,584 random keys: about n² / (2N) = 8.803 colliding pairs among 1,000,000 links collisions are likely: detect them and draw again; never overwrite an existing link redirect rules: unknown key → 404, expired link → 410, live link → 302

Change the key length and the number of links.

Predict first. Does a large random ID space eliminate the need to detect collisions?

Chapter context

A case study integrates choices into one coherent system. Start with a small requirement set, trace the important operations, calculate the dominant costs and stress the design with a failure before adding components.

TRY IT YOURSELF

Part 1. Do it hands-on

Size the key space and estimate collisions by hand, then build a shortener with collision retry and expiry.

key length (characters)6links created1,000,000

62⁷ 62⁶ colliding pairs, 10⁶ keys in 62⁶ a big space removes collision checks? (yes/no)

To do: Keys of 7 characters from 62 symbols (a–z, A–Z, 0–9). Size of the key space (62⁷)?
To do: With 6 characters (62⁶)?
To do: Birthday estimate: n random keys in a space of N produce about n²/(2N) colliding pairs. For n = 1,000,000 keys and N = 62⁶ (1 decimal)?
To do: Does a large random ID space eliminate the need to detect collisions? Type yes or no

Part 2. Do it in code

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" (PROVIDED, 62 symbols).
encode(n, length): the base-62 form of n padded with "0" to `length` characters; ValueError if n does not fit or is negative.
keyspace(length): 62 ** length.
expected_collision_pairs(n, space): n² / (2 · space).
class Shortener(gen, max_tries=5): self.urls is a dict key → (url, expires_at or None). create(url, now, ttl=None): call gen() for a candidate key until one is NOT already in use (at most max_tries candidates, then RuntimeError); store it with the expiry now + ttl (or None) and return the key.
resolve(key, now): (302, url) for a live key, (404, None) for an unknown key, (410, None) for an expired one (now >= expires_at).

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n, length):
    pass

def keyspace(length):
    pass

def expected_collision_pairs(n, space):
    pass

class Shortener:
    def __init__(self, gen, max_tries=5):
        self.gen = gen
        self.max_tries = max_tries
        self.urls = {}

    def create(self, url, now, ttl=None):
        pass

    def resolve(self, key, now):
        pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does a large random ID space eliminate the need to detect collisions?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For first-completion XP, define a unique logical event key such as (user_id, lesson_id, reward_version). Under a fixed reward r, $XP=r\times$ count(distinct eligible event keys). The deduplication record and awarded effect must share an atomic durable boundary in a real implementation.

Worked example

One hundred learners complete the same lesson, and every completion request is retried once. There are 200 deliveries but only 100 distinct learner-lesson events. At 20 XP per first completion, the correct total is 2000 XP, not 4000. The Python example models the invariant without pretending to implement distributed persistence.

Reference code

The following example uses the Python standard library and does not call a remote service.

deliveries=[]
for user in range(100):
    deliveries.extend([(user,'lesson-1','reward-v1')]*2)
unique=set(deliveries)
assert len(deliveries) == 200
assert len(unique) == 100
assert 20*len(unique) == 2000
assert 20*len(deliveries) == 4000

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A keyspace count does not prove collision freedom. Delivery and reading are different product events. Deduplication must cover both durable event identity and the actual effect.