Pointer Walk

Random ID Collisions

Four billion possible IDs, and the odds of a clash pass 50% at about 77,000 users.

Data StructuresIntermediate7 min read

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.

Random 32-bit IDsInteractive
0501000115.7k231.5kuserschance of a clash (%)50% at 77,163 users

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 sizePossible IDs50% chance of a clash at about
16 bits65,536300
32 bits4.3 billion77,000
64 bits18 billion billion5 billion
122 random bits (a random UUID)5 followed by 36 zeros2.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.

Random 32-bit IDsInteractive
ID size
0501000115.7k231.5kuserschance of a clash (%)50% at 77,163 users

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

  1. Work out how many IDs you will ever create

    Be generous. Systems live longer than planned.

  2. 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.

  3. 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.

  4. 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress