215 lines
8.7 KiB
Markdown
215 lines
8.7 KiB
Markdown
---
|
|
title: "The Birthday Paradox in Software Engineering: UUID v4 Collisions, Hash Collisions & Random Identifiers"
|
|
description: "Mathematical collision probabilities (Birthday Problem) in UUID v4, NanoID, and 32-bit random integers. Includes collision benchmarking code in TypeScript."
|
|
tags: ["math", "javascript", "security", "backend"]
|
|
canonical_url: "https://entscheidomat.com/ratgeber/zufallszahl-zwischen-1-und-10"
|
|
target_keywords: ["zufallszahl generator", "zufallsgenerator", "uuid v4 collision probability", "birthday paradox math", "random id generator"]
|
|
---
|
|
|
|
# The Birthday Paradox in Software Engineering: UUID v4 Collisions, Hash Collisions & Random Identifiers
|
|
|
|
When building databases, microservices, distributed caches, or online tools like a [Zufallsgenerator](https://entscheidomat.com/zufallszahl-generator), developers rely heavily on random unique identifiers.
|
|
|
|
Whether you generate UUID v4 strings, NanoIDs, or 64-bit random integers, a fundamental question always emerges during system scaling: **What is the mathematical probability that two randomly generated IDs will collide?**
|
|
|
|
Many developers assume that because a UUID v4 contains 122 bits of randomness ($2^{122} \approx 5.3 \times 10^{36}$ total unique IDs), collisions are impossible until you generate $10^{36}$ items. This assumption is dangerously false.
|
|
|
|
Due to the **Birthday Paradox**, collision probabilities rise exponentially much faster than human intuition predicts. In this article, we will derive the exact mathematical collision formula, build a collision simulator in TypeScript, compare UUID v4 vs. NanoID vs. 32-bit IDs, and establish best practices for distributed systems.
|
|
|
|
---
|
|
|
|
## 1. The Mathematics of the Birthday Paradox
|
|
|
|
The classic Birthday Paradox asks: *How many randomly chosen people must be in a room before there is a $50\%$ chance that at least two share the exact same birthday?*
|
|
|
|
Intuitively, people guess $\frac{365}{2} \approx 182$ people. The correct mathematical answer is surprisingly small: **just 23 people**.
|
|
|
|
### Deriving the Collision Formula
|
|
Let $d$ be the number of possible outcomes (e.g. $d = 365$ for birthdays, or $d = 2^{122}$ for UUID v4).
|
|
|
|
If we generate $n$ random items, the probability $P(\text{no collision})$ that all $n$ items are strictly unique is:
|
|
|
|
$$P(\text{no collision}) = 1 \times \left(1 - \frac{1}{d}\right) \times \left(1 - \frac{2}{d}\right) \times \dots \times \left(1 - \frac{n - 1}{d}\right) = \frac{d!}{(d - n)! \cdot d^n}$$
|
|
|
|
Using the Taylor series approximation $1 - x \approx e^{-x}$ for small $x$:
|
|
|
|
$$P(\text{no collision}) \approx \prod_{i=0}^{n-1} e^{-i / d} = e^{-\sum_{i=0}^{n-1} i / d} = e^{-\frac{n(n-1)}{2d}}$$
|
|
|
|
Therefore, the probability $p(n)$ of **at least one collision** occurring among $n$ generated items is:
|
|
|
|
$$p(n) = 1 - P(\text{no collision}) \approx 1 - e^{-\frac{n^2}{2d}}$$
|
|
|
|
For very small collision probabilities $p \ll 1$, this simplifies to the famous approximation:
|
|
|
|
$$p(n) \approx \frac{n^2}{2d}$$
|
|
|
|
Notice the $n^2$ term! The number of items $n$ is **squared**, which causes collision risks to skyrocket as dataset size grows.
|
|
|
|
---
|
|
|
|
## 2. Collision Thresholds: 32-bit vs 64-bit vs UUID v4 (122-bit)
|
|
|
|
Using the formula $n \approx \sqrt{2d \cdot p}$, let's calculate how many IDs $n$ you can generate before reaching a **1-in-a-million ($10^{-6}$)** and **$50\%$** collision risk across different ID formats:
|
|
|
|
| ID Type | Total Random Bits | Total Outcomes ($d$) | $n$ for $10^{-6}$ Collision Risk | $n$ for 50% Collision Risk |
|
|
| :--- | :--- | :--- | :--- | :--- |
|
|
| **8-bit Integer** | 8 bits | $256$ | 1 item | **19 items** |
|
|
| **16-bit Integer** | 16 bits | $65,536$ | 1 item | **302 items** |
|
|
| **32-bit Integer** | 32 bits | $4.29 \times 10^9$ | **93 items** | **77,163 items** |
|
|
| **64-bit Integer** | 64 bits | $1.84 \times 10^{19}$ | **6.07 million** | **5.05 billion** |
|
|
| **NanoID (21 chars)** | 126 bits | $8.50 \times 10^{37}$ | **4.12 trillion** | **3.43 sextillion** |
|
|
| **UUID v4** | 122 bits | $5.31 \times 10^{36}$ | **1.03 trillion** | **8.58 quintillion** |
|
|
|
|
### The Critical Takeaway for Developers
|
|
If your backend database uses a 32-bit random integer (`Math.floor(Math.random() * 4294967296)`), **you will hit a 50% chance of a database collision after generating just 77,163 items!**
|
|
|
|
Even at 100 requests per day, a 32-bit random ID scheme will fail within months.
|
|
|
|
---
|
|
|
|
## 3. Empirical Collision Simulator in TypeScript
|
|
|
|
Let's write a TypeScript simulator to empirically measure collision rates for smaller bit sizes (e.g. 16-bit and 32-bit integers) and verify our mathematical formula.
|
|
|
|
```typescript
|
|
export interface CollisionBenchmarkResult {
|
|
totalDrawn: number;
|
|
uniqueCount: number;
|
|
collisions: number;
|
|
firstCollisionAt: number | null;
|
|
theoreticalProb: number;
|
|
}
|
|
|
|
export function runCollisionBenchmark(bitDepth: 16 | 32, drawCount: number): CollisionBenchmarkResult {
|
|
const maxVal = bitDepth === 16 ? 0xFFFF : 0xFFFFFFFF;
|
|
const d = maxVal + 1;
|
|
|
|
const seen = new Set<number>();
|
|
let firstCollisionAt: number | null = null;
|
|
let collisions = 0;
|
|
|
|
const buffer = new Uint32Array(1);
|
|
|
|
for (let i = 1; i <= drawCount; i++) {
|
|
crypto.getRandomValues(buffer);
|
|
const rawVal = bitDepth === 16 ? (buffer[0] & 0xFFFF) : buffer[0];
|
|
|
|
if (seen.has(rawVal)) {
|
|
collisions++;
|
|
if (firstCollisionAt === null) {
|
|
firstCollisionAt = i;
|
|
}
|
|
} else {
|
|
seen.add(rawVal);
|
|
}
|
|
}
|
|
|
|
// Theoretical probability calculation p(n) = 1 - exp(-n^2 / 2d)
|
|
const theoreticalProb = 1 - Math.exp(-Math.pow(drawCount, 2) / (2 * d));
|
|
|
|
return {
|
|
totalDrawn: drawCount,
|
|
uniqueCount: seen.size,
|
|
collisions,
|
|
firstCollisionAt,
|
|
theoreticalProb
|
|
};
|
|
}
|
|
|
|
// Test 16-bit space (d = 65,536) with 500 draws
|
|
const result16 = runCollisionBenchmark(16, 500);
|
|
console.log("--- 16-bit Integer Collision Benchmark (500 Draws) ---");
|
|
console.log(`Total Drawn: ${result16.totalDrawn}`);
|
|
console.log(`Unique Items: ${result16.uniqueCount}`);
|
|
console.log(`Collisions Detected: ${result16.collisions}`);
|
|
console.log(`First Collision Occurred At Item #${result16.firstCollisionAt}`);
|
|
console.log(`Theoretical Probability: ${(result16.theoreticalProb * 100).toFixed(2)}%`);
|
|
```
|
|
|
|
### Typical Simulator Output:
|
|
```text
|
|
--- 16-bit Integer Collision Benchmark (500 Draws) ---
|
|
Total Drawn: 500
|
|
Unique Items: 498
|
|
Collisions Detected: 2
|
|
First Collision Occurred At Item #294
|
|
Theoretical Probability: 85.12%
|
|
```
|
|
|
|
---
|
|
|
|
## 4. UUID v4 Structure and Generation Code
|
|
|
|
A standard UUID v4 string looks like this:
|
|
|
|
```text
|
|
f47ac10b-58cc-4372-a567-0e02b2c3d479
|
|
└────────┘ └──┘ └──┘ └──┘ └──────────┘
|
|
8 hex 4 hex 4hex 4hex 12 hex
|
|
```
|
|
|
|
Out of 128 total bits, 6 bits are fixed (4 bits for version `4`, 2 bits for variant `10`), leaving **122 bits of pure cryptographic entropy**.
|
|
|
|
Here is a zero-dependency TypeScript function to generate UUID v4 compliant strings using Web Crypto API:
|
|
|
|
```typescript
|
|
export function generateUUIDv4(): string {
|
|
const bytes = new Uint8Array(16);
|
|
crypto.getRandomValues(bytes);
|
|
|
|
// Set version to 0100 (v4)
|
|
bytes[6] = (bytes[6] & 0x0f) | 0x40;
|
|
// Set variant to 10xx (RFC 4122)
|
|
bytes[8] = (bytes[8] & 0x3f) | 0x80;
|
|
|
|
const hex = Array.from(bytes, b => b.toString(16).padStart(2, '0')).join('');
|
|
|
|
return [
|
|
hex.substring(0, 8),
|
|
hex.substring(8, 12),
|
|
hex.substring(12, 16),
|
|
hex.substring(16, 20),
|
|
hex.substring(20, 32)
|
|
].join('-');
|
|
}
|
|
```
|
|
|
|
---
|
|
|
|
## Summary & Architectural Rules
|
|
|
|
1. **Never use 32-bit random integers for IDs:** 50% collision chance occurs after only ~77,000 items.
|
|
2. **Use 128-bit UUID v4 or 126-bit NanoID:** Gives you $10^{12}$ (1 trillion) IDs before reaching a tiny $10^{-6}$ collision risk.
|
|
3. **Use Web Crypto API:** Always feed ID generators with `crypto.getRandomValues()` rather than `Math.random()`.
|
|
|
|
Test an online random number generator with customizable ranges on [Entscheidomat Zufallszahl-Generator](https://entscheidomat.com/zufallszahl-generator).
|
|
|
|
---
|
|
|
|
## FAQ (Schema Structured Data)
|
|
|
|
```json
|
|
{
|
|
"@context": "https://schema.org",
|
|
"@type": "FAQPage",
|
|
"mainEntity": [
|
|
{
|
|
"@type": "Question",
|
|
"name": "Can UUID v4 collide?",
|
|
"acceptedAnswer": {
|
|
"@type": "Answer",
|
|
"text": "Yes, mathematically. However, because UUID v4 has 122 random bits, you would need to generate approximately 1.03 trillion UUIDs before reaching even a 1-in-a-million chance of a single collision."
|
|
}
|
|
},
|
|
{
|
|
"@type": "Question",
|
|
"name": "What is the Birthday Paradox in software engineering?",
|
|
"acceptedAnswer": {
|
|
"@type": "Answer",
|
|
"text": "The Birthday Paradox shows that collision probabilities in random hash or ID generators scale quadratically with the number of items generated, p(n) ≈ n^2 / 2d."
|
|
}
|
|
}
|
|
]
|
|
}
|
|
```
|