8. Project: Enlace's `short_code` generator

Description

The moment has come to bring the module's seven lessons together into a component that actually runs. In this project you'll implement Enlace's short_code generator end to end: the Link record (lesson 2), the store as a dictionary (lesson 3), the base62_encode/base62_decode conversion (lesson 6), the chosen generation strategy (lessons 5 and 7), and the expires_at handling (lesson 2). It's not a whiteboard exercise: it's Python code you run, whose output you verify, and that produces unique short_codes at scale.

The deliverable has three parts, like a real design doc: (1) the executable code of the complete id_generator (shorten and resolve), (2) the real output —the base62 round-trip, a batch of unique codes, and the resolutions of a live link, a nonexistent one, and an expired one—, and (3) the written justification of why you chose that generation strategy, with its conditions. By the end you'll have a code generator that works and that you'd know how to defend in a system-design interview or a design review.

Connection to the module: this is M3's capstone. It uses the record from lesson 2, the "it's a dictionary" from lesson 3, the three strategies from lessons 4 and 5, the base62 from lesson 6, and the decision from lesson 7 —all at once— to produce an artifact. And it's the bridge to M4: when you have the generator running and the db full of Links, the immediate question will be "how do I serve the ~4,000 reads/s of resolve without melting the database?" —and that's exactly module 4's cache—.

The project brief

You're the engineer in charge of Enlace's identifier generation. The team asks you for a component that manufactures unique short_codes, stores them with their Link, and resolves them —respecting the expiration—. These are the input data, fixed (the anchor numbers of the whole guide):

And these are the decisions you make (the design levers): which generation strategy you use (hash, counter + base62, or random + verification), how you guarantee the 7 characters, how you handle the collision, and how you treat the expiration. The project consists of choosing each one, implementing it, running it, and justifying the choice.

A guide for the decision, revisiting lesson 7: for this project you'll build the global counter + base62 —the strategy that by construction doesn't collide (lesson 5)—, because it's the one you can own entirely and verify without depending on retry probabilities. You add an offset so the codes are born with 7 characters and a defensive verification against the db. In the written justification you'll acknowledge the honest trade-off: random + unique index (lesson 7) is just as defensible and avoids the single coordination point from day one; we choose the counter here for its guaranteed zero-collisions and for how instructive it is to have it complete. Both are defended with numbers.

The project steps

Before seeing the reference solution, here's the process. Do it yourself first; the complete solution is after, in a collapsible block, so you can compare.

Step 1 — base62_encode/base62_decode and the anchor

Implement the two conversions from lesson 6 (divmod against the base, with the n == 0 case and the remainder reversal). Verify two things by running: the round-trip base62_decode(base62_encode(n)) == n for many n, and that 62⁷ = 3,521,614,606,208 covers the 6 billion with less than 0.2% used. It's the generator's foundation and its checksum.

Step 2 — The Link record and the db as a dictionary

Model the Link from lesson 2 (short_code, long_url, created_at, expires_at, clicks) —a dataclass is enough— and the db as a dict of short_code → Link, which is "the dictionary" from lesson 3. The dict's key is the short_code, just like the primary key of the links table.

Step 3 — The id_generator: counter + offset + base62 + verification

Build the IdGenerator from lesson 5: a monotonic counter that only goes up, an offset of 62⁶ so the first code has 7 characters, and base62_encode to convert the number into a code. Add the defensive verification: even though the counter guarantees uniqueness, check that the code isn't already in the db before returning it (an extra belt that also lets you migrate to random + verification by changing one line).

Step 4 — shorten, resolve and the expiration

Wrap everything in shorten(long_url, ttl_seconds=None) (creates the Link, stores it, returns the code) and resolve(short_code) (looks up in the db; returns None if it doesn't exist —404— or if expires_at has passed —410—; if it's alive, increments clicks and returns the long_url). The expires_at handling is the detail lesson 2 promised and that you implement here.

Acceptance criteria

Your delivery is complete when the generator meets, and you demonstrate it with the run output:

• Runs without errors with standard Python 3, no external dependencies.
• base62 reversible: the round-trip base62_decode(base62_encode(n)) == n gives True over a wide range of n.
• Anchor verified: the code prints 62⁷ = 3,521,614,606,208 and the fraction used by the 5-year demand (< 0.2%).
• 7-character codes: every generated short_code is exactly 7 (thanks to the offset).
• Uniqueness at scale: generating 100,000 codes produces 100,000 distinct values (zero collisions).
• resolve correct in the three cases: live link → returns the long_url (and raises clicks); nonexistent → None; expired → None.
• Written justification: a paragraph naming the chosen strategy, its two costs (guessable, coordination) with their mitigation, and what would change the decision.

Reference solution

It's not the only correct answer —random + unique index is also defensible (lesson 7)—, but it's a solid implementation of the counter + base62 with each piece justified. Try yours before opening this.

# enlace_id_generator.py — Enlace's short_code generator, executable.
from dataclasses import dataclass
from datetime import datetime, timedelta, timezone

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)   # 62


# --- Step 1: base62 (lesson 6) ---
def base62_encode(n: int) -> str:
    if n < 0:
        raise ValueError("n must be >= 0")
    if n == 0:
        return ALPHABET[0]                 # edge case: 0 -> '0'
    chars = []
    while n > 0:
        n, rem = divmod(n, BASE)           # quotient and remainder by 62
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))        # the remainders come out backwards


def base62_decode(s: str) -> int:
    n = 0
    for ch in s:
        n = n * BASE + ALPHABET.index(ch)  # 'shift' and add
    return n


# --- Step 2: the Link record and the db as a dictionary (lessons 2 and 3) ---
@dataclass
class Link:
    short_code: str
    long_url: str
    created_at: datetime
    expires_at: datetime | None = None     # NULL = doesn't expire
    clicks: int = 0


# --- Step 3: the id_generator (lesson 5) ---
class IdGenerator:
    """Global counter + base62, with offset to be born with 7 chars
    and defensive collision verification against the db."""
    OFFSET = 62 ** 6                        # 56,800,235,584 -> first code '1000000'

    def __init__(self, db: dict):
        self.db = db
        self.counter = 0                    # monotonic counter, only goes up

    def next_code(self) -> str:
        while True:
            self.counter += 1
            code = base62_encode(self.OFFSET + self.counter)
            if code not in self.db:         # the counter already guarantees uniqueness;
                return code                 # the verification is an extra belt


# --- Step 4: shorten / resolve with expiration (lessons 1, 2 and 5) ---
class Enlace:
    def __init__(self):
        self.db: dict[str, Link] = {}       # short_code -> Link (the dictionary)
        self.id_gen = IdGenerator(self.db)

    def shorten(self, long_url: str, ttl_seconds: int | None = None) -> str:
        code = self.id_gen.next_code()
        now = datetime.now(timezone.utc)
        expires = now + timedelta(seconds=ttl_seconds) if ttl_seconds is not None else None
        self.db[code] = Link(code, long_url, now, expires)
        return code

    def resolve(self, code: str) -> str | None:
        link = self.db.get(code)
        if link is None:
            return None                                  # 404: doesn't exist
        if link.expires_at is not None and link.expires_at < datetime.now(timezone.utc):
            return None                                  # 410: expired
        link.clicks += 1
        return link.long_url


# ---------- The deliverable: run everything and verify ----------
# 1) base62 round-trip and the 62^7 anchor
ok = all(base62_decode(base62_encode(n)) == n for n in range(0, 200_001))
print("round-trip base62_decode(base62_encode(n)) == n, n in [0,200000]:", ok)
print("62**7 =", f"{62**7:,}", " (code space, 7 chars)")
demand = 100_000_000 * 12 * 5
print("demand 5 years =", f"{demand:,}", " -> used:", f"{demand/62**7:.4%}")
print()

# 2) a batch of unique short_codes
enlace = Enlace()
urls = [f"https://example.com/article/{i}" for i in range(1, 9)]
codes = [enlace.shorten(u) for u in urls]
print("shorten() over 8 URLs:")
for u, c in zip(urls, codes):
    print(f"  {c}  <-  {u}")
print("unique codes:", len(set(codes)) == len(codes), f"({len(set(codes))}/{len(codes)})")
print()

# 3) scale: 100k codes without a single collision
big = Enlace()
n = 100_000
for i in range(n):
    big.shorten(f"https://example.com/{i}")
print(f"shorten() over {n:,} URLs -> unique codes:",
      len(big.db) == n, f"({len(big.db):,}/{n:,})")
print()

# 4) resolve(): existing, nonexistent and expired
code0 = codes[0]
print("resolve(existing)    ->", enlace.resolve(code0))
print("resolve(nonexistent) ->", enlace.resolve("zzzzzzz"))
expired = enlace.shorten("https://example.com/one-day-promo", ttl_seconds=-1)
print(f"resolve(expired {expired}) ->", enlace.resolve(expired))
print("clicks of the first link after 1 resolve:", enlace.db[code0].clicks)

round-trip base62_decode(base62_encode(n)) == n, n in [0,200000]: True
62**7 = 3,521,614,606,208  (code space, 7 chars)
demand 5 years = 6,000,000,000  -> used: 0.1704%

shorten() over 8 URLs:
  1000001  <-  https://example.com/article/1
  1000002  <-  https://example.com/article/2
  1000003  <-  https://example.com/article/3
  1000004  <-  https://example.com/article/4
  1000005  <-  https://example.com/article/5
  1000006  <-  https://example.com/article/6
  1000007  <-  https://example.com/article/7
  1000008  <-  https://example.com/article/8
unique codes: True (8/8)

shorten() over 100,000 URLs -> unique codes: True (100,000/100,000)

resolve(existing)    -> https://example.com/article/1
resolve(nonexistent) -> None
resolve(expired 1000009) -> None
clicks of the first link after 1 resolve: 1

Extensions (optional, to go further)

If you want to take the project beyond the minimum criteria, two extensions that connect with the rest of the guide:

• Permute the counter to kill the enumeration. Right now 1000001, 1000002, 1000003 are guessable. Add a bijective permutation of the counter before base62_encode (for example, multiply by an integer coprime with the space size and take the modulo, or a small Feistel-type scheme) so that consecutive counters give codes that don't resemble each other —without losing the uniqueness—. Verify it still doesn't collide over 100,000 codes.
• Switch to random + verification in one line. Replace the body of next_code with "generate 7 random characters; if it's not in the db, return it; if it is, retry". Since the db is already the uniqueness arbiter, the rest of the system doesn't notice. Measure how many retries you did (it'll be almost zero while the db is little filled) and compare it with the 0.17% theoretical from lesson 5.

Common mistakes

Encoding the raw counter and exposing one-character codes. What happens: someone starts the counter at 0 with no offset, and the first links are enla.ce/1, enla.ce/2. Besides screaming "new service with three links", they're trivially enumerable and clash with reserved routes. Why it happens: the counter is encoded without thinking about how the first codes look. How to detect it: if your first short_code is 1 or 2 characters, you're missing the offset. How to fix it: start at a high offset (62⁶) so they're born with 7 characters, as in the solution. And if the service is public, permute as well so they aren't consecutive.

Forgetting the expiration check in resolve. What happens: resolve returns the long_url of a link whose expires_at has passed, and Enlace redirects to a destination that should be dead (an expired promotion, an already-used single-use link). Why it happens: resolve is implemented as a simple db.get(code) and the expires_at field is ignored. How to detect it: create a link with ttl_seconds=-1 (already expired) and check that resolve returns None; if it returns the URL, you're missing the check. How to fix it: before returning, verify if link.expires_at is not None and link.expires_at < now: return None. The NULL of expires_at means "doesn't expire" (lesson 2), so it's only compared when it isn't None.

Trusting the counter and removing the verification "because it never collides". What happens: someone reasons "the counter guarantees uniqueness, the verification is unnecessary" and deletes it —and then, when migrating to random, or when restarting the counter from a badly restored value, collisions appear without a safety net—. Why it happens: it's optimized by removing a cheap belt. How to detect it: if your next_code doesn't consult the db before returning, you depend 100% on the counter never repeating —which is true until the day you restore an old backup and the counter goes backwards—. How to fix it: leave the defensive verification (if code not in self.db); it costs a trivial query and protects you against badly restored counters and against a future change of strategy. It's the same unique index you already have from having short_code as the key.

Exercises

Exercise 1 — Verify the seven characters. Modify the deliverable to assert that every generated code is exactly 7 characters, instead of just looking at it. Write the check over the 100,000 codes and say which counter value would be the first to produce an 8-character code (hint: what's the smallest n with base62_encode(n) of 8 chars?).

big = Enlace()
for i in range(100_000):
    big.shorten(f"https://example.com/{i}")
all_7 = all(len(c) == 7 for c in big.db)
print("all are 7 chars:", all_7)               # True
print("first 8-char code at n =", f"{62**7:,}")  # 3,521,614,606,208

Exercise 2 — Migrate to random + verification and count the retries. Replace next_code with the random strategy (7 random characters, verify against the db, retry if it clashes). Generate 100,000 codes, count how many retries you did in total, and compare with what the formula N_taken / 62⁷ from lesson 5 predicts.

import random

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def random_code():
    return "".join(random.choice(ALPHABET) for _ in range(7))

db = {}
retries = 0
for i in range(100_000):
    code = random_code()
    while code in db:              # verification + retry
        retries += 1
        code = random_code()
    db[code] = f"https://example.com/{i}"

print("codes generated:", len(db))       # 100,000
print("total retries:", retries)         # ~1 or 2 (almost always 0)

Exercise 3 — Defend your design against three objections. A colleague questions your generator (counter + base62 with offset and verification). Answer each objection in a couple of sentences, with what you learned in the module. (a) "The counter is a single point of failure, it's a bad idea." (b) "The codes are consecutive, anyone enumerates the database." (c) "Verifying against the db on each write is a waste, the counter already doesn't collide."

Summary and next step

In this project you built Enlace's short_code generator end to end and ran it. You implemented base62_encode/base62_decode (lesson 6) and verified the round-trip True and the 62⁷ = 3,521,614,606,208 anchor (< 0.2% used in 5 years); you modeled the Link and the db as a dictionary (lessons 2 and 3); you built the IdGenerator with counter + 62⁶ offset + defensive verification (lesson 5); and you wrapped everything in shorten/resolve with the expires_at handling (the three paths: alive, nonexistent, expired). The real output confirmed each acceptance criterion: 7-character codes, 100,000 unique without a collision, and correct resolve. And you wrote the justification —the chosen strategy, its two costs with their mitigation, and what would change it—, which is what separates a generator that runs from an engineering decision.

Before moving on you should be able to: implement the complete id_generator from memory, with base62, offset, and verification; explain why the counter never collides and what its two costs are; handle expires_at in resolve; and defend your strategy with its conditions (public vs internal, recoverable IDs, write growth).

With this you close module 3. You have the data model (Link), the store (dictionary / key-value or SQL with a unique index), and the code generator —the algorithmic heart of a shortener— resolved and running. What comes next is the problem that appears the moment the db fills up and the reads arrive: at 4,000 resolutions per second, going to the database on each one is expensive and slow. In module 4 you'll put a cache in front of the read path —cache-aside, hit ratio, the formula L = h·L_cache + (1−h)·L_db, the 80/20 rule of the working set— to absorb the hottest part of those reads. The generator fills the db; the cache protects it from the reads. That's the next link.

Resources

• Redis documentation — the INCR command — the real atomic counter that would implement this project's "ticket dispenser" in production. Seeing that it's a single atomic operation explains why at 40 writes/sec the single counter is enough, and why it guarantees two writes never receive the same number.
• PostgreSQL documentation — "Sequences" (CREATE SEQUENCE, nextval) — the relational alternative to the counter: a sequence that hands out monotonic numbers, with its UNIQUE constraint on short_code acting as verification. It's the "in the database" version of the generator you built in memory.
• Instagram Engineering — "Sharding & IDs at Instagram" (Snowflake-type scheme) — how a real system generates unique IDs without a single central counter, combining timestamp, shard id, and a local sequence. It's the concrete preview of how module 5 resolves the single coordination point that your counter-based generator drags.
• The System Design Primer — URL shortener design — a second voice on the complete design of the code generator and its place in the system, useful for contrasting your implementation with the canonical reference before moving on to the cache.