Lesson 9.2• 10 min read

Short links: Base62, MD5 and a key service

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, Σ\Sigmawhat its symbols mean, holds 26 lowercase letters, 26 capitals and 10 digits:

∣Σ∣=26+26+10=62|\Sigma| = 26 + 26 + 10 = 62what its symbols mean
Length kkwhat its symbols mean Keys (62k62^k) Lasts, at 10 million new links a month
5 916,132,832916{,}132{,}832 about 7.6 years
6 56,800,235,58456{,}800{,}235{,}584 about 470 years
7 3,521,614,606,2083{,}521{,}614{,}606{,}208 about 29,000 years
8 218,340,105,584,896218{,}340{,}105{,}584{,}896 about 1.8 million years

The primer takes 7 characters: 62762^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)O(k)what its symbols mean time for kk digits. With the alphabet 0-9a-zA-Z, 125,937,421125{,}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) / 62762^7. Even after all 360 million shortlinks:

360×1063.52×1012≈1.0×10−4\frac{360 \times 10^6}{3.52 \times 10^{12}} \approx 1.0 \times 10^{-4}

That is about one try in 10,000. Summed over all nnwhat its symbols mean = 360 million inserts, the expected number of retries is n(n−1)2⋅627≈18,400\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 62762^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.

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.
Key database: 24 available, 0 used, 0 lostDatabase round trips: 0 for 0 shortlinks
App server 1
no keys in memory
App server 2
no keys in memory
App server 3
no keys in memory
Each server takes keys from the key service in batches of 3 and hands them out from memory.
Clients1× instanceLoad balancer2× instancesWrite servers (keys inmemory)2× instancesKey generationservice2× instancesKey database(available and usedkeys)2× instancesPastes database2× instancesClients1× instanceLoad balancer2× instancesWrite servers (keys inmemory)2× instancesKey generationservice2× instancesKey database(available and usedkeys)2× instancesPastes database2× instances
Figure 2

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×101262^7 \approx 3.5 \times 10^{12} 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.
Sources3