Short links: Base62, MD5 and a key service

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.

The primer takes 7 characters: $62^7$ "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)$ 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 MD5 hash 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.

url = base_encode(md5(ip_address + timestamp))[:URL_LENGTH]

How often is there a duplicate? A new random 7-character key collides with an existing one with probability (keys in use) / $62^7$. Even after all 360 million shortlinks:

That is about one try in 10,000. Summed over all 360 million inserts, the expected number of retries is $\frac{n(n-1)}{2 \cdot 62^7} \approx 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 $62^7$ 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.