UUIDの衝突確率を計算する - 誕生日問題で考える

「UUIDは本当に重複しないのか」「UUIDの衝突事例はあるのか」と疑問に思うことがあります。 UUID v4の衝突確率はゼロではありませんが、正しく生成されていれば現実的な規模では天文学的に低い値です。この記事ではUUIDが重複する可能性を、 誕生日問題（Birthday Problem）の考え方と具体的な計算で解説します。

UUID v4 collisions are theoretically possible but astronomically unlikely. This guide derives the collision formula from the birthday problem, calculates practical probabilities, and explains why faulty random number generators matter more than the theoretical keyspace.

UUID v4は122ビットがランダム

UUIDは128ビットですが、UUID v4では6ビットがバージョンとバリアントの識別に固定されます。 ランダムに使えるのは残りの122ビットで、理論上の組み合わせ数は次のとおりです。

M = 2^122
  = 5,316,911,983,139,663,491,615,228,241,121,378,304
  ≈ 5.32 × 10^36 通り

特定の2個が一致する確率は1 / 2^122ですが、多数生成時のUUID衝突確率は この値だけでは求められません。

誕生日問題：重要なのはペアの数

N人いる部屋で同じ誕生日のペアが生まれる確率と同じ理屈で、N個のUUIDにはN × (N - 1) / 2組のペアがあります。生成数とともに比較対象が二次関数的に 増えるため、組み合わせ数そのものではなくペア数から考えます。

Nが十分大きいとき、少なくとも1回衝突する確率pは次の式で近似できます。

p ≈ 1 - e^(-N^2 / (2 * 2^122))

より厳密にはN^2をN × (N - 1)に置き換えます。 この式は衝突しない確率を近似し、1から引いています。

具体的なUUID衝突確率

50%の確率で衝突が起きる生成数はsqrt(2 × 2^122 × ln 2)、すなわち約2.71 × 10¹⁸個です。これは約27.1億×10億個に相当し、 概数として「約26億×10億個」と紹介されることもあります。

実務では理論値より生成品質に注意する

数百万〜数十億個程度ではUUID v4の衝突確率は実質無視できます。現実のUUID衝突事例を 調べる際は、偶然の一致より、疑似乱数生成器（PRNG）の実装バグ、弱い乱数源、 seedの使い回し、VM複製後の同一状態、UUIDの切り詰めや保存時の変換を先に疑うべきです。

// ブラウザ / Node.js: 実行環境の暗号学的乱数源を使う
const id = crypto.randomUUID();

// Math.random()を連結してUUIDらしい文字列を自作しない
console.log(id);

理論計算は各UUIDが一様かつ独立に生成されることが前提です。PRNGやseedに問題があれば 前提が崩れます。DBにもUNIQUE制約を設定して重複を検出しましょう。

UUID v7の衝突確率

UUID v7はタイムスタンプと74ビット程度のランダム部分を持ち、v4よりランダムビット数が 少なくなります。同一ミリ秒内に大量生成する場合は2^74通りの誕生日問題となり、 v4より衝突確率がわずかに高くなる可能性があります。ただし通常の生成速度では極めて低い値です。

時系列ソートやDB性能を含む選び方はUUID v4とv7の違いで詳しく解説しています。

他のID方式との比較

UUID v4・v7・ULID・Nano IDはいずれも「十分にランダムなら衝突しない」という確率的な保証に依存します。 一方Snowflake IDのような方式は、タイムスタンプ・マシンID・連番を組み合わせることで、乱数に頼らず 構造的に一意性を保証します。ソート性が必要ならULID/UUID v7、既存システムとの親和性ならUUID v4、 分散システムでの決定的な一意性を求めるならSnowflake系ID、という選び方になります。

生成速度から衝突確率を実感する

本記事の50%衝突確率に達する生成数(約2.71 × 10¹⁸個)を、具体的な生成速度に当てはめると 規模感がつかみやすくなります。

仮に毎秒10億個(10^9個/秒)のUUID v4を休みなく生成し続けた場合:
2.71 × 10^18 個 ÷ 10^9 個/秒 = 2.71 × 10^9 秒 ≈ 約86年

つまり「世界中で毎秒10億個」という非現実的なペースで生成し続けても、
50%の確率で1件でも衝突するまでに約86年かかる計算になる。

実際のシステムで毎秒10億個ものUUIDを生成するケースはまず存在しません。理論上の衝突確率は 実務上ほぼ無視してよい水準であり、前述の通り本当に注意すべきなのは乱数生成器の品質です。

まとめ

UUID v4には2¹²²通りの候補があり、50%の衝突確率に達するには約2.71 × 10¹⁸個が必要です。実務では乱数生成器とseedの品質、保存スキーマ、 UNIQUE制約の確認が重要です。

English summary

UUID v4 has 122 random bits because six bits identify its version and variant. The birthday-problem approximation is p ≈ 1 - e^(-N^2 / (2 * 2^122)), and a 50% collision probability requires about 2.71 × 10¹⁸UUIDs. Practical collision risk is negligible; broken PRNGs, reused seeds, truncation, and storage bugs are more credible. UUID v7 has about 74 random bits, so its same-millisecond probability is slightly higher than v4's.