How do you size collision risk for randomly generated 64-bit identifiers?
answer
- collisions are a pair property
- risk grows with n squared
- trouble near the square root of N
- n squared over 2N
- count entropy bits, not field width
basics
~20 sUse the birthday bound, not 1/N per identifier. With n values drawn uniformly from N possibilities, collision probability is roughly n^2/(2N), reaching 50% near 1.18 x sqrt(N) - about 5 billion values for 64 bits.
solid answer
~40 sThe mistake is estimating risk per identifier as `n/N`. A collision is a property of a *pair*, so the count that matters is `C(n,2)`, which is roughly `n^2/2`. That gives the birthday bound: `P(collision) is approximately 1 - exp(-n^2/(2N))`, and for small risk simply `n^2/(2N)`. With 64-bit values, `N = 2^64 = 1.84 x 10^19`. A billion identifiers gives `10^18/(3.69 x 10^19) = 2.7 percent` - a real risk, not a rounding error - while a million gives about `2.7 x 10^-8`. Move to 128 bits and a billion identifiers gives about `1.5 x 10^-21`. Two consequences to state: doubling the number of identifiers **quadruples** the risk, and adding bits helps enormously because `N` doubles per bit while the tolerable count only grows as `sqrt(N)`.
go deeper
Be ready to recall that random identifiers can collide and that the chance depends on how many you generate, not just on how wide the field is. Knowing the phrase 'birthday bound' and that risk grows faster than linearly is enough here.
Explain where n^2/(2N) comes from by counting pairs, and carry out the arithmetic for a concrete case such as a billion 64-bit values. Expect to be asked how many bits you would add to reach a target risk.
Show the full decision: lifetime count, entropy bits rather than field width, computed probability, and what a collision would actually cost the system. Naming the ways a generator loses entropy is what marks real experience here.
Own the tradeoff between random and allocated identifiers - unguessability and independent generation against guaranteed uniqueness and coordination cost - and set the organisational risk tolerance explicitly rather than defaulting to whatever width is conventional.
## The wrong model and the right one The instinctive estimate is "each new identifier has an `n/N` chance of hitting something already issued, so the risk is tiny". That is the per-identifier view, and it under-states the aggregate badly. A collision is a property of a **pair** of identifiers. With `n` identifiers there are `C(n,2) = n(n-1)/2` pairs, roughly `n^2/2`, and each pair collides with probability `1/N` if the generator is uniform. The expected number of colliding pairs is therefore about `n^2/(2N)`, and while that expectation is small it is also a very good estimate of the probability that at least one collision exists. ## The birthday bound This is the birthday problem with 365 replaced by `N`: ``` P(at least one collision) is approximately 1 - exp(-n(n-1)/(2N)) ``` Two regimes matter in practice. **Small-risk regime** (`n` far below `sqrt(N)`): the exponential linearises and ``` P(collision) is approximately n^2/(2N) ``` **Crossover**: `P = 0.5` at ``` n is approximately 1.1774 x sqrt(N) ``` The headline is that trouble arrives near `sqrt(N)`, not near `N`. That factor is the entire point: an identifier space is effectively **half as many bits** as it looks, for collision purposes. ## Numbers for 64 and 128 bits `2^64 = 1.845 x 10^19`, so `sqrt(N) = 2^32 = 4.29 x 10^9`. | Identifiers issued | 64-bit collision probability | |---|---| | 1 million | about 2.7 x 10^-8 | | 100 million | about 2.7 x 10^-4 | | 1 billion | about 2.7 percent | | 5 billion | about 50 percent | At 128 bits, `N = 3.40 x 10^38`, and a billion identifiers gives `10^18/(6.81 x 10^38) = 1.5 x 10^-21` - below the rate at which hardware silently corrupts data, which is the honest benchmark for "negligible". The 64-bit row at a billion is the one that changes decisions. A billion rows is an ordinary table size, and a 2.7 percent chance of a duplicate primary key over the life of the system is not a risk most teams would knowingly accept. ## The scaling rules worth memorising - **Doubling `n` quadruples the risk.** The `n^2` term dominates, so a system that grows 10x sees 100x the collision probability. - **Each extra bit halves the risk.** `N` doubles, and `n^2/(2N)` halves. - **Tolerable `n` grows only as `sqrt(N)`.** To support 1000x more identifiers at the same risk you need 1,000,000x the space, which is 20 more bits. ## Entropy is what counts, not width The analysis assumes `n` values drawn **uniformly and independently** from `N`. Anything that reduces real entropy shrinks the effective `N`, and because risk scales as `1/N` the damage is exponential in the bits lost. A generator that is 64 bits wide but delivers only 48 bits of entropy raises `n^2/(2N)` by `2^16 = 65,536`. Seeding from a low-resolution clock, reusing a seed across processes that start simultaneously, or deriving identifiers from a small input space are the usual culprits. When estimating, use bits of entropy, never field width. The same caution applies to identifiers with structure - a timestamp prefix plus a random suffix has only as much collision resistance as the random suffix, within the window in which the prefix is constant. ## Turning the estimate into a decision 1. **Estimate the lifetime count `n`**, generously - the count you will reach, not today's. 2. **Use bits of entropy** to get `N`. 3. **Compute `n^2/(2N)`.** If that exceeds your tolerance, add bits; there is rarely a cheaper fix. 4. **Decide what a collision costs.** Silent data corruption and a rejected insert are different outcomes. A uniqueness constraint in storage does not remove the collision - it converts a silent overwrite into a visible failure, which is a large improvement, but you still need a retry path and an estimate of how often it fires. 5. **Consider whether randomness is needed at all.** A centrally allocated sequence has no collision risk; randomness buys unguessability and independent generation, and it is worth being explicit about which of those you are paying for. ## Common mistakes 1. **Using `n/N`** instead of `n^2/(2N)` - typically off by many orders of magnitude. 2. **Treating 64 bits as automatically safe** without computing anything. 3. **Saying collisions are impossible because the values are random** - randomness is what makes them possible, and merely improbable. 4. **Confusing field width with entropy.** 5. **Ignoring that `n` is a lifetime total**, including deleted rows if their identifiers must stay unique. ## The compact answer "Birthday bound: risk is about `n^2/(2N)`, hits 50 percent near `sqrt(N)`. For 64 bits that is 5 billion values, and a billion values already carries about a 2.7 percent chance. Use entropy bits, not field width, and remember that doubling the count quadruples the risk."
- You use 128-bit random identifiers and expect a trillion of them - is collision a real concern?No. With N = 2^128 = 3.4 x 10^38 and n = 10^12, the estimate n^2/(2N) is 10^24/(6.8 x 10^38), about 1.5 x 10^-15. That is far below the rate of undetected hardware and storage errors in the same system, so collision is not the binding risk and adding bits would buy nothing measurable.
- What happens if the generator delivers fewer bits of entropy than the field width suggests?The effective N shrinks and risk scales as 1/N, so the damage is exponential in the bits lost. A 64-bit field carrying only 48 bits of real entropy raises the collision probability by 2^16, about 65,000 times. Low-resolution clock seeds, seeds shared across simultaneously started processes, and identifiers derived from small inputs are the usual causes.
- Does a uniqueness constraint in storage remove the need for this analysis?No, it changes the failure mode. Without it a collision silently overwrites or merges records; with it the write fails loudly, which is far better. You still need the estimate to know how often that failure will fire, and you still need a defined retry path. A constraint converts a correctness risk into an availability risk rather than eliminating it.
- Why does doubling the number of identifiers quadruple the collision probability?Because the risk tracks the number of pairs, C(n,2), which is about n^2/2. Doubling n roughly quadruples the pair count, and each pair carries the same 1/N chance of matching. The same quadratic is why growth forecasts matter more than current volume when sizing an identifier space.
saying these in an interview costs you the question
- Estimates risk as n/N instead of n squared over 2N
- Assumes 64 bits is always enough without computing
- Says collisions cannot happen because values are random
- Uses field width rather than bits of entropy
- Uses current row count instead of lifetime total