The Short URL Generator

In one line: this is the design's central component, and its structure — two independent parts with orthogonal jobs — is what makes the rest of the system simple.

The two parts

The short URL generator consists of two main parts:

• A sequencer to generate unique IDs
• A Base-58 encoder to enhance the readability of the short URL

Our sequencer generates a unique 64-bit numeric ID (base-10). To create a more readable URL, we use a Base-58 encoder to convert this numeric ID into an alphanumeric string.

Two orthogonal jobs, and the separation is what removes collision handling

Each component solves exactly one problem, and neither knows about the other's:

The crucial property is that base-58 encoding is a bijection — a one-to-one, reversible mapping. Distinct integers always produce distinct strings, and every string maps back to exactly one integer.

So uniqueness is inherited. The chapter states it plainly: "We ask the sequencer for a unique ID and by the definition of our sequencer's design, there will never be duplication. We then encode those IDs, which also ensures no duplication."

That eliminates something every naive design needs. Compare hashing the long URL and truncating:

HASH-BASED:   hash(long_url) -> take first 7 chars -> CHECK for collision
                                                   -> on collision, retry with a salt
SEQUENCER:    next_id() -> encode -> DONE

The hash approach needs a database read on every write to detect collisions, and the collision rate climbs as the table fills — the birthday problem, arriving faster than intuition suggests.

The sequencer approach needs no read at all. The ID is unique because of how it was allocated, not because anyone checked.

Deriving uniqueness from allocation rather than from checking removes a read, a retry loop, and a failure mode that gets worse as you grow.

Why not just hash the URL? The question an interviewer will ask

It is the obvious alternative, and there are three reasons the design rejects it — worth having ready.

Collisions are inevitable and get worse. A 7-character base-58 output has 58⁷ ≈ 2.2 trillion values. Storing 12 billion means collisions long before you fill it, by the birthday bound. Every collision needs detection and a retry.

Hashing is deterministic, which sounds good and is not. The same long URL always produces the same short URL — which does give free deduplication. But it also means anyone can verify whether a URL has been shortened by computing the hash themselves, which leaks information about private links. Lesson 2's unpredictability requirement rules it out.

You cannot support custom aliases cleanly. Lesson 11's mechanism decodes a custom alias back to an integer and marks that ID used. With a hash there is no integer to mark — the custom alias and the hash space are unrelated, so you would need a separate uniqueness mechanism for each.

The one genuine advantage of hashing — automatic deduplication of identical long URLs — the design recovers differently, by looking up the long URL before generating. Lesson 11 covers it.

Hashing gives you deduplication and costs you unpredictability, collision-freedom, and custom aliases. A sequencer gives you all three and costs you a lookup for deduplication.

The sequencer must not hand out IDs in order — and that is stated late

The generator as described produces "a unique 64-bit numeric ID." Lesson 2's unpredictability requirement says sequential IDs are a security risk.

The chapter's resolution appears only in its evaluation section, much later:

The sequencer assigns ranges of unique IDs to different servers. If a server issued IDs sequentially, the resulting short URLs would be predictable. To avoid this, the server selects an ID at random from its assigned range for each new URL.

So the mechanism is range allocation plus random selection within the range, and it has a cost the chapter does not mention: a server must now track which IDs in its range it has already used.

With sequential issuance you store one number — the next ID. With random selection you store a set, and Lesson 11's used/unused lists are exactly that machinery, pushed into the database for durability.

That is a real trade:

SEQUENTIAL: state = one counter        predictable
RANDOM:     state = a set of used IDs  unpredictable, and needs persistence

And Lesson 10 shows random selection still does not deliver unpredictability at this scale, for a reason unrelated to ordering. Worth flagging now: randomizing the order of allocation does not make a dense space sparse.

The encoder is a pure function, and that is worth exploiting

Notice what the base-58 encoder needs: nothing. No database, no state, no coordination. Give it an integer, get a string.

Three consequences worth naming:

It can run anywhere. In the application server, in a library, at the edge. There is no reason for it to be a network hop.

It is trivially testable. Lessons 7 and 8 show the round-trip, and a pure bijection is exactly the kind of thing you can test exhaustively over a sample.

It never fails. No timeouts, no retries, no partial states. The only failure mode in the whole generator lives in the sequencer.

So when the chapter draws the generator as a component, the useful reading is that the sequencer is a service and the encoder is a function. Treating them as one box hides that one of them has an availability story and the other cannot fail.

The counter is usually the right default, and the reason is that it moves uniqueness from something you check to something you cannot violate. Whichever you pick, keep a unique constraint on the short-code column as the final guarantee — the database is the only component that can enforce it under concurrency.

Next: why base 58 rather than base 64.