Generating Short Codes

Here are the requirements for short codes again:

All: unique.
t.co: short, at about 2,000 new links per second.
Drive: hard to guess.
O’Reilly: easy to type, with no characters that look alike.

To generate a code, we have to decide two things. First, we decide which characters a code may use. That sets how long a code must be. Then we decide which code a new link gets. Whether codes are unique, and whether someone can guess them, depends on that second choice.

The characters in a code

A code goes in a URL path, so it should use only characters that are safe in a URL. Digits and letters are safe. Many other characters, such as /, ?, and #, have a meaning in a URL, so they cannot appear in a code without being escaped.

The more characters we allow, the shorter a code can be. With only the 10 digits, a 7-character code allows $1 0^{7}$ , or 10 million, codes. t.co creates that many links in about an hour. With the digits, the lowercase letters, and the uppercase letters, we have 62 characters.

We can treat a code as a number written with these 62 characters as its digits. This is called base62. In a decimal number, each position holds one of 10 values. In base62, each position holds one of 62. For example, 125 is $2 \times 62 + 1$ . So in base62, 125 is written 21.

You may have seen base64. It adds + and /, and / separates the parts of a URL path, so base64 does not fit here.

A code of length $n$ allows $6 2^{n}$ different codes:

Length	Codes
5	About 900 million
7	About 3.5 trillion
10	About $8 \times 1 0^{17}$

t.co creates 200 million links a day. That is about 73 billion a year. At that rate, 7-character codes last about 48 years: 3.5 trillion divided by 73 billion is about 48.

Four ways to generate a code

Base62 is how we write a code. We still have to pick which code a new link gets. Earlier, we compared ways to create unique IDs across shards: a central counter, a range per shard, UUIDs, and Snowflake IDs. Here are four ways to pick the code for a new link. Each one produces a number. We write that number in base62.

A counter, with a range of numbers for each API instance. Each API instance receives its own range of numbers, and it counts through that range. When it uses up its range, it requests another one from the counter server. So there is one request per range, not one per code. The codes are short and unique. But they are easy to guess. An API instance counts through its range, so the code it gives the next link is the next number. In base62, the number after x7Kp2Qa is x7Kp2Qb. Someone who receives the short link short.example/x7Kp2Qa can try x7Kp2Qb and will probably reach the link created right after it. A script can try the codes in order and visit every link.

With Shopend, we gave each shard its own range. That does not work here. The code is the shard key, so the code must exist before we know its shard. That is why each API instance gets the range instead.

A random code. We generate a random code, and we insert it only if no link uses that code yet. If one does, we generate another code and try again. Random codes are hard to guess. Since we shard by code, checking whether a code is in use is one lookup on one shard. Checking and then inserting as two separate steps is not enough. Suppose two API instances generate the same code at the same moment. Both check, both find the code unused, and both insert. Now two links have the same code. So the database must check and insert in one step: it inserts the link only if no link has that code yet, and otherwise the insert fails. This is the same idea as the conditional update for the blue mug’s stock.

A hash of the long URL. We apply a hash function to the long URL, write the result in base62, and keep the first few characters as the code. A hash function always gives the same result for the same input. So when a long URL is shortened again, it gets the same code. This also helps when a shorten request is retried. Suppose X’s servers send a shorten request, and the request times out after we have already stored the link. X’s servers send the same request again. With a counter or a random code, the second request gets a new code, and the long URL now has two links. With a hash, the second request gets the same code. We find the link already stored under that code and return it. Because we keep only a few characters, two different URLs can end up with the same code. So before we insert a link, we still check whether the code is already in use, as with a random code.

A Snowflake ID. Each API instance creates IDs without contacting another server for each ID. But a Snowflake ID is 64 bits, which is a number up to about $1.8 \times 1 0^{19}$ . Writing that in base62 takes 11 characters. For t.co, 7 characters already allow 3.5 trillion codes, enough for about 48 years. So with a Snowflake ID, every link would be 4 characters longer than it needs to be.

Choosing for each variant

t.co: a counter, with a range for each API instance. Codes are 7 characters, and there is no request to the counter server for each link. Guessable codes are acceptable, because most t.co links appear in public posts. X wraps the links in direct messages too, so a guessed code could reveal a URL sent privately. A design that protects those links would give them random codes, as Drive does.

Drive: random codes of 10 characters, and we rate-limit misses. Over 5 years, Drive creates about 90 billion links. There are about $8 \times 1 0^{17}$ codes of 10 characters, so a random guess finds a link about once in 9 million tries. With misses rate-limited, guessing is not practical. Microsoft Forms’ short links also use 10 characters.

O’Reilly: a counter in its one database, written with 32 characters. The alphabet is the digits and the lowercase letters, without 0, o, 1, and l. Lowercase only means readers do not have to get the case right. Codes are 5 characters. That allows $3 2^{5}$ , or about 33 million, codes. At 73,000 links a year, that lasts for centuries.