Every new link, post or order needs a name nothing else has. On one server that's a counter. On many servers at once, handing out names without two of them ever picking the same one is a design decision of its own.

Why it's hard

One app server can count: 1, 2, 3. A dozen app servers can't each count on their own, or two of them will both hand out 1. They need either one shared source of numbers, or a way to pick names that can't collide without asking anyone.

Every replica mints codes at once. None may ever repeat.

A database's auto-increment column is the shared-source answer: it works, but every new row then waits on the one machine that holds the counter, and a database spread over many machines has no single counter at all.

Four strategies

Base62 writes a number with the digits, lowercase and uppercase letters, 62 symbols in all. Each character multiplies the space by 62: 6 characters give 57 billion codes, 7 give 3.5 trillion. For a link shortener, short codes are the product, so the strategy's length matters as much as its speed.

A central counter

A counter service gives the shortest codes and never collides. The price is that every write calls it. As writes approach what it can hand out each second, calls wait longer, and if it goes down, nothing new can be created at all.

The usual fix keeps the counter but calls it less: each app server takes a range of numbers at a time (say 1 000), and hands them out locally. The counter sees one call per thousand writes. The cost is gaps: a server that crashes with half a range unused leaves those numbers behind forever, which is harmless for links. How big should a range be?

Snowflake IDs

A Snowflake ID (named after Twitter's generator) packs three fields into 64 bits (63 of them are used, plus an unused sign bit):

Two machines can't collide because their machine numbers differ, and one machine can't collide with itself because time and the sequence only move forward. A machine that uses up all 4 096 sequence numbers within one millisecond waits for the next millisecond. IDs come out roughly in time order, so new rows land at the end of a table sorted by ID, and you can sort by ID instead of by date. No call to a shared service is needed per ID. The catches: machine numbers have to be assigned once, usually from a config file or a small shared service at startup, and a clock that jumps backwards must make the generator wait.

Try the clock yourself: one machine's clock steps back, and the generator either trusts it or waits.

Hashing the URL

Hash the long URL and keep the first 7 characters. The same URL always gets the same code, which deduplicates for free, and no service has to be called. But cut-short hashes collide: two different URLs can share a prefix. So you insert each new code into a column the database keeps unique: it rejects a code that is already taken. On a rejection, first read the row that holds the code: if it's the same long URL, someone already shortened it, and you reuse its code. Only a different URL means a real clash, and then you try again with a salt added. Checking first ("is this code taken?") and then inserting isn't enough, because two servers can both check, both see the code free, and both insert it. As the table fills, clashes get more common.

Choosing

In the wild

The ideas in this chapter, and where you'll meet them in real systems and interviews:

Your practice

ink.ly launches next week, and a partner wants to import its links on day one: thousands of new short codes a second, from every app server at once. Codes have to stay short, so UUIDs are out. Pick how codes are minted so creating a link stays fast during the import.