Picking IDs at random
Every user, order and file needs an ID that nothing else has. The simple way is a counter: 1, 2, 3. But a counter needs one place that hands out the numbers, and that is awkward when many servers create things at once.
So many systems pick IDs at random instead. Any server can do it without asking anyone. The only risk is two things getting the same ID by chance, a collision.
With a 32-bit ID there are 4,294,967,296 possible values. Four billion. How many users can you give random IDs to before two of them probably match?
Make a guess before you press play.
Start. 4.3B possible 32-bit IDs. Each new user gets one at random. How many users before two of them match?
- Users
- 0
- Pairs of users
- -0
- IDs used
- 0.0%
- Chance of a clash
- 0.0%
About 77,000
The chance of a clash passes 50% at roughly 77,000 users. At that point only 0.0018% of the IDs have been used. By a few hundred thousand users a clash is nearly certain, and the ID space is still almost entirely empty.
Most people guess in the millions or billions. The mistake is a natural one.
It is about pairs, not users
You picture your new ID clashing with the IDs already taken. With 77,000 taken out of four billion, that one new user has only a 1 in 56,000 chance of a clash. That part of the intuition is right.
But the question was not "does the next user clash?". It was "do any two users clash?", and every pair of users is a separate chance.
Example
Counting pairs
10 users make 45 pairs. 1,000 users make 499,500 pairs. 77,000 users make about 3 billion pairs.
Each pair has a 1 in 4.3 billion chance of matching. With 3 billion pairs, a match somewhere is about as likely as not.
The number of pairs grows with the square of the number of users. Ten times the users is a hundred times the pairs. That is why the curve stays flat for so long and then climbs so suddenly.
This is the same effect as the famous birthday paradox: in a room of 23 people, two probably share a birthday.
A rule you can remember
With N possible IDs, expect a collision after about the square root of N.
| ID size | Possible IDs | 50% chance of a clash at about |
|---|---|---|
| 16 bits | 65,536 | 300 |
| 32 bits | 4.3 billion | 77,000 |
| 64 bits | 18 billion billion | 5 billion |
| 122 random bits (a random UUID) | 5 followed by 36 zeros | 2.7 billion billion |
Every extra bit doubles the IDs, but only multiplies the safe number of users by about 1.4. To be safe for twice as many users you need two more bits, not one.
Start. 4.3B possible 32-bit IDs. Each new user gets one at random. How many users before two of them match?
- Users
- 0
- Pairs of users
- -0
- IDs used
- 0.0%
- Chance of a clash
- 0.0%
What to do about it
Work out how many IDs you will ever create
Be generous. Systems live longer than planned.
Square that number
That is roughly how many possible IDs you need for a collision to be a coin flip. You want far more, so that a collision is not a coin flip but a near impossibility.
When in doubt, use 128 bits
A random UUID is the standard choice. You would have to create a billion every second for about 86 years to reach a 50% chance of one collision.
Still let the database enforce it
Put a unique constraint on the ID column. If the unthinkable happens, you get an error instead of two users sharing an account.
Key takeaways
- Random IDs collide far sooner than the size of the ID space suggests.
- A collision needs any two users to match, and the number of pairs grows with the square of the users.
- Rule of thumb: with N possible IDs, expect a collision at around the square root of N.
- 32 bits is safe for tens of thousands of items, not billions.
- Use 128-bit IDs when unsure, and keep a unique constraint as a safety net.