The shape
You need identifiers that do three things at once. Short, because a human may type or share them. Unique, with no chance of a clash. And unguessable, so that holding one tells you nothing about the others.
The obvious approach is to generate a random code and then check whether it is taken. The better approach is to take a counter, which is already unique, and pass it through a reversible function that scrambles it. Because the function is reversible, or bijective, distinct inputs always produce distinct outputs, so uniqueness is inherited from the counter and never has to be checked.
A short link is where most people meet this, and the pattern is much broader than that. Some examples:
- Invoice and order numbers. Sequential numbering tells any customer who buys from you twice how much you sold in between.
- Invite and referral codes. Short enough to read out over the phone, and worthless if they can be guessed in bulk.
- Object identifiers in public APIs. An exposed auto-increment key is an invitation to walk through everyone else's records.
- Coupon codes minted in batches. A uniqueness check per code turns a single job into 1 million round trips.
All four need the same three things, and all four get built the first way, with randomness and a check. That check is where the costs are.
The four costs of checking for collisions
It needs a round trip that can fail. Every identifier now depends on a uniqueness check against a data store, so minting is only as available, and only as fast, as that data store. You cannot mint one offline, in a test, or during an incident.
Its failure rate grows with your data. Early on, when almost every code is still free, the check passes every single time and looks like a formality you could have skipped. What ends that is the birthday paradox, the same counting argument that makes two people in a room of 23 likely to share a birthday. The first clash lands at roughly the square root of the space, which here is about 2.1 million identifiers. From there, the more identifiers you have already handed out, the more often the check comes back telling you the code is taken. The retry loop that never fired once in year one starts firing in year three.
Its worst case has no bound. The loop runs until a code comes back free, so nothing in the design gives you a number for how long minting takes. It shows up in the tail rather than the average: the mean stays close to one attempt long after the p99 has become two, then three. No code changed, and the call got slower.
It wastes the space. At 1 billion identifiers, six characters over a 64-symbol alphabet gives you 69 billion slots, and a counter through a permutation fills them one at a time with nothing to check. A random code at six characters is colliding on one attempt in 69 by the billionth identifier, and climbing, so you go to seven characters instead. Every identifier you ever issue is one character longer than the arithmetic needed.
7-character identifiers over a 64-symbol alphabet space 64^7 = 4.4 x 10^12 Why 64, when the encoding step names base62? Only because 64 is a power of two, which keeps the arithmetic readable. Base62 gives 3.5 x 10^12 slots instead, a fifth fewer, and changes none of the conclusions below. A fresh random code collides only if it lands on one you have already issued, so its odds are just how much of the space is taken. Say 1 billion codes are already out there: space taken 1B / 4.4 x 10^12 = 0.023% collision odds for the next random code = 1 in 4,400 The same sum at every stage of the system's life: codes already issued space taken odds the next one collides ────────────────────────────────────────────────────────────── 1M 0.00002% 1 in 4,400,000 100M 0.002% 1 in 44,000 1B 0.023% 1 in 4,400 100B 2.3% 1 in 44 1T 22.7% 1 in 4.4 Take the last row, where 22.7% of the space is gone. Every retry draws a brand new random code, so the odds reset on each attempt: 22.7% of them collide, no matter how many you have already tried. You need a third round trip only if the first two both collided, which is why the numbers below multiply. first attempt works 1 - 0.227 = 77.3% of mints needs 2 or more 0.227 = 22.7% of mints needs 3 or more 0.227 x 0.227 = 5.2% of mints needs 4 or more 0.227 x 0.227 x 0.227 = 1.2% of mints ────────────────────────────────────────────────────────────── average round trips 1 / (1 - 0.227) = 1.3 per mint An average of 1.3 round trips never looks alarming on a dashboard. Roughly 1 mint in 80 needs four or more, and that is the one somebody is sitting and waiting for.
The mechanism
Three steps. The counter and the encoding are ordinary engineering choices. Get the permutation wrong and the identifiers are still unique and no longer unguessable.
1. A counter. Any monotonic source of distinct integers. A database sequence, a Redis counter, or blocks of a few thousand handed out to each instance so that minting is local and the coordination is rare.
2. A keyed permutation. A function that takes a number in the counter's range and returns a different number in that same range, reversibly, under a secret key. Use format-preserving encryption. FF1 is the standard algorithm. The range has to be exactly the space your encoding renders, 64^7 and no more, or the output will not fit in seven characters. When the range is not a power of two, FF1 encrypts a result again whenever it lands outside the range, and repeats until it lands inside. Three things matter: it is bijective, it is keyed, and the key is a secret you can rotate behind a version prefix.
3. An encoding. Render the scrambled number in whatever alphabet you want people to see. Base62, base58 if you care about ambiguous characters, or a custom alphabet that avoids vowels so the output cannot spell anything unfortunate.
A counter through a permutation cannot collide at all, because distinct inputs cannot share an output, and that is as true of the 4.4 trillionth identifier as of the first. No collisions means nothing to check, nothing to check means no retries, and no retries means no tail latency. Minting costs one permutation, every time.
Reversibility, and the leak that comes with it
Because the permutation is reversible, your service can take any identifier and recover the counter value that produced it. That is useful when somebody hands you a code and you want to know whether it is real before you go looking for it. The counter only ever goes up, so you always know the highest value you have handed out, which is your high water mark. Decode the code you were given. If the number that comes out sits above the mark, that code was never issued and you can reject it without touching the data store. If it sits below, the code might be real, and now you go and look.
The same check leaks. Decoding maps identifiers onto counter values one to one, so a random guess decodes to a random counter value. Throw 100,000 random codes at the check and count how many come back as "could exist" rather than "definitely not". That fraction is your high water mark divided by the size of the space, and nobody needed the key to measure it. The fix is to compare against the high water mark rounded up to a coarse boundary, the next 100 million rather than the exact number. Then what the count measures is which 100 million you are in, not how many you have issued.
There is a worse version of the same leak, and you get it by not using this pattern at all: publishing the counter directly. /invoices/1041 tells any customer your invoice volume on the spot, and two readings a month apart tell them your growth rate. Scrambling the counter is what keeps a public identifier from doubling as a business metric.
How to tell you have this problem
You are about to write a retry loop around a uniqueness check. It usually appears three lines into the first draft of the mint function. If the loop is there because the identifier has to be short enough for a human to handle, this pattern is what you want instead.
Your identifier length was chosen to make collisions rare, not to hold your data. Work out how many identifiers you will ever issue, then how many your current length can hold. If the length holds 1,000 times more than you will ever need, those extra characters are buying a low collision rate and nothing else. The permutation gives you that for free.
Your public URLs contain a number that goes up. /orders/58201 is the counter, published. Anyone who places two orders knows how many you took in between.
The metric that settles it: count how often the uniqueness check comes back taken, by month, and plot it against identifiers issued. A flat line at zero means you have time. A line that has started to lift is the retry loop starting to fire, and it will not go back down.
What it costs
The key is now a secret with a lifecycle. It belongs in a key management service or a secrets manager, AWS KMS or Vault, rather than in application config, and it has to be rotatable. Rotating it means new identifiers come from a new key while every old identifier must still decode, so the identifier needs a way to say which key made it. A version prefix, or a reserved range, decided at the start rather than retrofitted.
The counter is a coordination point, and a single hot one. Handing out blocks of a few thousand makes minting local and the coordination rare, at the cost of gaps in the sequence when an instance dies holding a partly used block. The gaps are harmless, because nothing in the design reads the counter as a count of anything. Say so before you are asked, because somebody will notice them.
This gives you unguessable, not authorised. An identifier nobody can predict is still not access control, and confusing the two is the most common way this pattern gets misused. If the resource behind it is sensitive, it needs a permission check no matter how good the identifier is.
Where it shows up in the course
| article | the form it takes there |
|---|---|
| media keys that must be unguessable, since holding the URL is what grants access to a public image | |
| URL Shortener | generating short codes without a uniqueness check, and the existence check that reversibility enables |
Getting it wrong
Using an operation that is reversible without the key. XOR, multiply, rotate. Bijective and therefore unique, and consecutive identifiers still sit next to each other.
Rolling your own permutation. This is not the place to be creative. Use FF1.
Forgetting key versioning. Rotation is impossible after the fact if identifiers carry no indication of which key produced them.
Comparing the decoded value against an exact high water mark. It turns the existence check into a public estimate of how much you have issued. Round it up to something coarse.
Treating an unguessable identifier as authorisation. It is not one. Check permissions on the resource.
Reaching for it when you do not need short. If the identifier is never seen by a human, a random 128-bit value has no collision problem to manage, and none of this buys you anything.