Base62 encoding, hashing with a duplicate check, counters, and a key generation service that hands out keys in batches.
What you will learn
Encode a number in Base62, and see why 7 characters are enough.
Work out how often a random link collides with an existing one.
Compare hashing, counters and a key generation service for making links.
Base62
A shortlink should be short and safe to put in a URL without escaping. The primer's choice is Base62, the characters [a-zA-Z0-9], which "works well for urls, eliminating the need for escaping special characters". Base64 adds + and /, which cause problems in URLs.
Its alphabet, Σwhat its symbols mean, holds 26 lowercase letters, 26 capitals and 10 digits:
∣Σ∣=26+26+10=62what its symbols mean
Length kwhat its symbols mean
Keys (62k)
Lasts, at 10 million new links a month
5
916,132,832
about 7.6 years
6
56,800,235,584
about 470 years
7
3,521,614,606,208
about 29,000 years
8
218,340,105,584,896
about 1.8 million years
The primer takes 7 characters: 627 "should be sufficient to handle our constraint of 360 million shortlinks in 3 years". It is nearly 10,000 times that number. The spare room matters most for random keys, because it keeps collisions rare (below).
Encoding a number is repeated division by 62, which runs in O(k)what its symbols mean time for k digits. With the alphabet 0-9a-zA-Z, 125,937,421 encodes as 8wq4J. The visual shows each step.
Approach 1: hash, encode and truncate (the primer's design)
The primer generates a URL like this:
Take the MD5hash of the user's IP address plus a timestamp, or of randomly generated data. MD5 produces a 128-bit value and is uniformly distributed.
Base62-encode it and keep the first 7 characters.
Check the database for a duplicate. If one exists, generate another URL.
How often is there a duplicate? A new random 7-character key collides with an existing one with probability (keys in use) / 627. Even after all 360 million shortlinks:
3.52×1012360×106≈1.0×10−4
That is about one try in 10,000. Summed over all nwhat its symbols mean = 360 million inserts, the expected number of retries is 2⋅627n(n−1)≈18,400. Making shortlink the primary key, as the primer does, means the database itself rejects a duplicate. So the server can simply insert and, on a duplicate-key error, try another key. No separate lookup is needed.
The real weaknesses lie elsewhere. Two requests from the same IP address in the same timestamp produce the same hash, which is why the primer mentions hashing random data instead. And the collision rate rises as the key space fills.
Approach 2: a counter encoded in Base62
Encode a unique number instead of a hash: an auto-increment column, or a distributed ID generator. Uniqueness is then guaranteed without retries.
The costs:
Guessable keys. Consecutive numbers give consecutive shortlinks, so anyone can enumerate every paste by counting. Pastes meant to be unlisted need unguessable keys.
Coordination. A single auto-increment counter is one database every write must reach. Twitter's Snowflake avoids that by composing a 64-bit ID from a 41-bit millisecond timestamp, a 10-bit machine ID and a 12-bit sequence number. Its IDs are "roughly time ordered", and any 64-bit ID needs up to 11 Base62 characters, not 7.
Approach 3: a key generation service (KGS)
A separate service generates random keys ahead of time and stores them in a database of unused keys. When an application server needs keys, it takes a batch in one step: it marks them as handed out, so no other server can receive them. It then assigns them from memory, one per new paste, with no database round trip until the batch runs out.
CREATE TABLE available_keys (short_key CHAR(7) PRIMARY KEY);
CREATE TABLE used_keys (short_key CHAR(7) PRIMARY KEY);
-- Handing out a batch moves keys from available_keys to used_keys in one transaction.
Trade-offs:
Crashes waste keys, but never duplicate them. If a server dies, the keys in its memory are lost. They were already marked as handed out, so they are never reissued. With 627 keys, losing a few thousand is negligible.
The KGS becomes a dependency. It needs a replica, or a large enough buffer on each server, so that a KGS outage does not stop new pastes.
Keys are random. Unlike counters, they cannot be enumerated.
This approach is not in the primer; it is a common extension of its design. The primer's hash-and-check approach is simpler and, as computed above, rarely needs a retry at this scale.
Generating shortlinks
Base62 encoding, how often random keys collide, and a key generation service that hands out keys in batches.
Base62: 8wq4J
125937421 mod 62 = 45 → J2031248 mod 62 = 4 → 432762 mod 62 = 26 → q528 mod 62 = 32 → w8 mod 62 = 8 → 8
A new key collides with probability 0.010%, about 1 in 9,782. Inserting all 360 million one by one would have needed about 18,401 retries. With the shortlink as primary key, a duplicate insert fails and the server simply tries another key.
A key generation service: write servers take random keys from it in batches and hand them out from memory.
Follow a new paste. The load balancer sends it to a write server, which takes the next key from the batch it holds in memory and saves the paste under it, with no trip to the key service. Only when its batch runs out does it ask the key generation service for another, which moves a batch from the available keys to the used keys in one transaction, so no other server can get them. The service generates random keys ahead of time and keeps them in its key database. It runs on two servers, so that its outage does not stop new pastes.
Clients: 1 × Users
Load balancer: 2 × Load balancer
Write servers (keys in memory): 2 × App server
Key generation service: 2 × App server
Key database (available and used keys): 2 × Relational database
Pastes database: 2 × Relational database
Clients sends requests to Load balancer
Load balancer sends requests to Write servers (keys in memory)
Write servers (keys in memory) sends requests to Key generation service
Key generation service sends requests to Key database (available and used keys)
Write servers (keys in memory) sends requests to Pastes database
Key takeaways
Base62 needs no escaping in URLs, and 627≈3.5×1012 is nearly 10,000 times the 360 million links needed.
Even after all 360 million links exist, a new random key collides about once in 10,000 tries; with the link as primary key, the database rejects duplicates and the server retries.
A counter never collides but makes links guessable and needs coordination (or a Snowflake-style ID).
A key generation service hands out random keys in batches; a crash wastes keys but never duplicates them, and the service must not become a single point of failure.