Short Code Generator

Any system that needs to generate unique identifiers at scale runs into the same fundamental tension: uniqueness requires knowing what already exists, but knowing what already exists requires coordination, and coordination is expensive.

In a URL shortener at 1,000 writes per second, the naive approach is obvious — generate a random 7-character string, check the database to see if it exists, and retry if it does. This works fine at low volume. At 1,000 writes/sec across multiple web servers, it breaks in several ways simultaneously.

First, every write now requires a round-trip database read before it can complete. The write path goes from "generate → insert" to "generate → read → if collision: generate → read again → insert." Under load, this adds latency to every single URL creation.

Second, there is a race condition at the heart of it. Server A generates code "abc1234" and checks the database — it is not there. Server B generates the same code "abc1234" and checks the database — it is not there either. Both servers now try to insert. One wins; the other gets a constraint violation and has to retry. At 1,000 writes/sec across multiple servers, collision handling under concurrency is not a theoretical concern — it is a regular occurrence.

Third, retry loops under high collision probability compound the problem. As the database fills up, collision probability grows. Even a small retry rate multiplied across 1,000 writes/sec generates meaningfully higher database load than expected.

Before going deep on each approach, it helps to see how they compare on the dimensions that matter most. Each approach makes a different tradeoff between simplicity, uniqueness guarantee, hot-path latency, and coordination overhead.

The most intuitive approach: take the long URL, run it through a hash function (MD5, SHA-256), take the first 7 characters of the base62 output, and use that as the short code. If it collides with an existing code, append a salt — the user ID, a counter, a timestamp — and try again.

The appeal of hashing is that the same long URL always produces the same prefix. This means you get natural deduplication — two requests to shorten the same URL will produce the same hash prefix, and you can return the existing code without creating a new one. At low volume, this works elegantly.

The insight behind region prefix is elegant: if you can guarantee that no two servers ever produce the same prefix, you do not need to coordinate at all. Server US-1 generates codes starting with "u1", Server EU-1 generates codes starting with "e1". Two servers cannot collide if their codes are structurally distinct.

This completely eliminates the hot-path database read. A server generates a code locally in microseconds, inserts it, done. No coordination, no retry, no race condition. At pure write throughput, this is the fastest possible approach. The problem is what it costs.

The core insight of the pool approach is: move code generation entirely off the hot path. Instead of generating a code when a write request arrives, generate codes in advance and store them in a pool. When a write arrives, the web server claims the next available code from the pool. The pool stays full because a background service — the nanny — continuously refills it.

This separates two concerns that the hash approach conflated: generating unique codes (now done offline by the nanny, never blocking a user request) and assigning codes to URLs (now done on the hot path via an atomic database claim). The web server never generates a code — it only claims one that has already been guaranteed unique.

At higher scale — 100,000+ writes per second, or a globally distributed deployment — the pool table itself becomes a bottleneck. Every write does an atomic DELETE on a shared table. A dedicated token service solves this by decentralizing code generation entirely.

Instead of all web servers competing for rows in a shared pool table, each server gets a pre-allocated range of IDs from the token service. Within its range, the server generates codes locally with zero coordination. When the range is exhausted, the server requests a new range — one network call per 1,000 codes instead of one per write.

Twitter's Snowflake is the canonical implementation: a 64-bit integer encoding a timestamp, datacenter ID, machine ID, and sequence number. Each server generates IDs entirely locally. Global uniqueness is guaranteed by the combination of time and machine identity — no central counter, no coordination at all.

The nanny service is deceptively simple. Its entire job is to keep the code pool full. It runs as a singleton background job, wakes up on a schedule, checks the pool size, and generates new codes if the pool is below threshold. The simplicity is intentional — a service with one clear responsibility is easy to reason about, monitor, and debug.

Pool target: 10,000 codes. At 1,000 writes/sec, this is 10 seconds of write capacity. If the nanny runs every few seconds and takes a moment to generate codes, there is still plenty of buffer before the pool drains. If the pool target were only 1,000 codes (one second), a single nanny hiccup could drain the pool before it responds. 10,000 is conservative but the cost is negligible — the pool table at 10,000 entries of 10 bytes each is 100KB.

Refill threshold: 5,000 codes (50% capacity). The nanny does not wait until the pool is empty before refilling — that would leave no margin for error. Refilling at 50% means the remaining 5,000 codes provide approximately 5 seconds of additional runway even if the nanny takes longer than usual. This "buffer within a buffer" is what makes the system robust to nanny delays without requiring a high-frequency polling loop.

// runs every N seconds
pool_size = SELECT COUNT(*) FROM code_pool

if pool_size < REFILL_THRESHOLD (5,000) {
  to_generate = TARGET_SIZE (10,000) - pool_size

  for i in range(to_generate) {
    code = random_base62(length=7)
    INSERT INTO code_pool (code)
    ON CONFLICT DO NOTHING  // safety net for duplicates
  }
}

The pool table has a UNIQUE constraint on the code column. At a pool size of 10,000 against a space of 3.5 trillion possible Base62 strings, the probability of a duplicate is approximately 0.0000003% — effectively zero. But production systems should never rely on probability when a deterministic check is cheap. The constraint catches the one-in-a-billion case, silently drops the duplicate (ON CONFLICT DO NOTHING), and the loop continues. No crash, no alert, no retry storm.

Without reclamation, the code pool has a slow leak. Codes claimed for URLs that nobody ever clicks again are permanently consumed. At 1,000 writes/sec, approximately 86 million codes are claimed every day. Over time, even a 3.5 trillion code space shrinks. The reclamation service prevents this while solving a practical problem: codes from abandoned or deleted URLs should eventually be reusable.

The instinct when reclaiming a code is to delete the record entirely. But hard deletion has a dangerous consequence: if the short code is immediately reassigned to a new long URL, anyone who had cached or bookmarked the old short link would silently land on completely different content. This is a terrible user experience and a potential security issue.

Soft deletion — setting state = DELETED while keeping the record — means an expired link shows a clear "this URL has expired" page rather than silently redirecting to something unrelated. The record is also preserved for audit: if someone reports a link behaved unexpectedly, you have the full history of what the code pointed to and when it changed.

The reclamation service waits one additional month after the INACTIVE state is set before moving to SOFT DELETED. This handles a real pattern: content that has a traffic lull but is not actually dead. A seasonal campaign that goes quiet in January might spike again in March. A blog post with irregular traffic should not lose its code during a quiet period. The 3-month inactivity window plus 1-month grace period gives 4 total months — long enough to correctly identify genuinely inactive URLs while preserving those with irregular but real traffic.

The pre-generated pool approach as described is solid for TinyURL at its stated scale. But it has known gaps that become important at higher scale or in more complex deployments. These are left open intentionally — they require research and benchmarking rather than speculation.

The code generation problem — unique short identifiers at scale without coordination overhead — appears in many system designs. Each system has slightly different constraints but the core tradeoffs are the same.