tknuth/entscheidomat

Fork 0

Files

knuthtimo-lab 529a95cba2 SEO blogpost

2026-08-05 19:33:11 +02:00

8.7 KiB

Raw Permalink Blame History

title, description, tags, canonical_url, target_keywords

title

description

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

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:

--- 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:

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:

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

Never use 32-bit random integers for IDs: 50% collision chance occurs after only ~77,000 items.
Use 128-bit UUID v4 or 126-bit NanoID: Gives you 10^{12} (1 trillion) IDs before reaching a tiny 10^{-6} collision risk.
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.

FAQ (Schema Structured Data)

{
  "@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."
      }
    }
  ]
}

8.7 KiB Raw Permalink Blame History