UUIDは本当に被らないのか──衝突確率を計算する
UUID v4は122ビットの乱数で作られ、10億個を作っても同じ値が出る確率は約1,060京分の1です。誕生日問題の近似式で、何個作れば衝突が現実になるのかを計算し、確率の前提が崩れる場面と、RFC 9562の記述、バージョンごとの違いを整理します。
この記事のポイント
- 122ビットの乱数。10億個作っても衝突は約1,060京分の1
- 確率は乱数が良質な前提。保証ではなく、手作りの乱数は危ない
- 「UUID・ULIDを整える」で暗号乱数のUUID v4を作れる
- Q.
- UUIDは本当に被らないの？
- A.
- 絶対に被らないとは言えませんが、UUID v4は実用上ほぼ被りません。122ビットの乱数なので、10億個を作っても同じ値が出る確率は約1,060京分の1です。衝突の確率が半分に達するのは、約2.7×10^18個を作ったときです。
UUIDは「世界中で重複しない番号」と説明されますが、実際には乱数なので、同じ値が出る可能性はゼロではありません。ゼロではないなら、どのくらいの確率なのか。この記事では、UUID v4の衝突確率を計算します。
結論を先に書きます。UUID v4は122ビットの乱数です。10億個を作っても、そのなかに同じ値が含まれる確率は約1,060京分の1（約9.4×10^-20）です。
UUID v4の122ビットとは
UUIDは128ビットの値です。RFC 9562（2024年5月）では、UUID v4は真の乱数または疑似乱数から作る方式と定められています。128ビットのうち、バージョンを示す4ビットと、バリアントを示す2ビットの合計6ビットは固定です。残りの128−6＝122ビットが乱数になります。
次の例は、RFC 9562の付録A.3にあるUUID v4のテスト値です。
919108f7-52d1-4320-9bac-f847db4148a83つ目のグループの先頭が「4」で、これがバージョンです。4つ目のグループの先頭「9」は、バリアントを示す上位2ビットが「10」になる値（8・9・a・bのどれか）の1つです。この2つの位置は、UUID v4ではいつも決まった形になります。
乱数の組み合わせの数は、2の122乗です。これは約5.3×10^36にあたる、非常に大きな数です。
衝突確率の計算：誕生日問題の近似
n個のUUIDを作ったとき、そのなかに同じ値が1組でもある確率は、誕生日問題と同じ形の近似で求められます。
- n個から2つを選ぶ組み合わせは、n×(n−1)÷2通りです
- どの組も、同じ値になる確率は、2の122乗分の1です
- 確率が小さいときは、衝突の確率はおよそ n×(n−1)÷(2×2^122) です
この式を、Pythonで計算してみます。
import math
N = 2 ** 122
def p(n):
return -math.expm1(-n * (n - 1) / (2 * N))
print(p(10**9)) # 9.4e-20結果は次のとおりです。
| 作ったUUIDの数 | 衝突の確率 | 逆数 |
|---|---|---|
| 10億個 | 約9.4×10^-20 | 約1,060京分の1 |
| 1兆個 | 約9.4×10^-14 | 約10.6兆分の1 |
| 1,000兆個 | 約9.4×10^-8 | 約1,060万分の1 |
個数が1,000倍になると、確率は100万倍になります。確率が個数の2乗で増えるためです。
半分の確率に達するのは何個か
衝突の確率が50%になるのは、約2.7×10^18個です。式で書くと、n＝√(2×2^122×ln2)で、2.7×10^18はこの値です。毎秒10億個のUUIDを作り続けても、約86年かかります。
毎秒10億個を1年間作り続けた場合を計算すると、作る個数は約3.15×10^16個です。このときの衝突の確率は約9.35×10^-5（約0.0094%）で、約1万700分の1です。
比較のために、約43億個（2の32乗）を作った場合も計算します。2の32乗個を作ると、確率は2の−59乗にあたる約1.7×10^-18で、約58京分の1です。アプリのユーザーIDや注文IDとして使う程度の数であれば、衝突を心配する場面はまずありません。
この確率が成り立たない場面
ここまでの数字は、乱数が十分に良質で、122ビットを全部使っているという前提の計算です。RFC 9562は、暗号論的に安全な乱数生成器（CSPRNG）を使うことを推奨しています。次のような場合は、計算どおりの確率になりません。
- 乱数の質が悪い。 時刻だけを種にした手作りの乱数や、乱数の種が同じ状態で動く複数のプロセスは、同じ値を出しやすくなります。RFC 9562も、プロセスを分岐（fork）したときに乱数生成器の状態を種からやり直すよう注意を促しています。
- ビット数が減っている。 UUID v4の一部だけを切り出して短くして使うと、確率は大きく悪化します。たとえば、下位32ビットだけを使えば、2の32乗（約43億）通りで、約7万7千個を作ると衝突の確率が半分に達します。
- UUID v7を使っている。 v7は先頭の48ビットが時刻で、乱数は74ビットです。同じミリ秒に作られたもの同士でしか衝突しないので、時刻が違えば被りません。ただし同じミリ秒に1,000個を作ると、そのなかでの衝突の確率は約2.6×10^-17です。
RFC 9562は、衝突したときの影響の大きさを考えて版を選ぶよう述べています。ログの重複程度で済むなら、UUIDの乱数で十分です。人命に関わる用途のように、失敗が許されない場面では、できるだけ高い衝突耐性を求めるように書かれています。また、世界での唯一性は、共有された仕組みなしには保証できないとも書かれています。
バージョンごとに、被らない理由が違う
UUIDにはバージョンがあり、RFC 9562では次のように整理されています。どの版かは、3つ目のグループの先頭の文字でわかります。
| バージョン | 何で作るか | 被らない理由 |
|---|---|---|
| v1 | グレゴリオ暦の時刻 | 時刻と機器の識別情報の組み合わせ |
| v3 | 名前をMD5でハッシュ | 同じ名前からは同じ値ができる（乱数ではない） |
| v4 | 乱数（122ビット） | 乱数の組み合わせの多さ |
| v5 | 名前をSHA-1でハッシュ | 同じ名前からは同じ値ができる（乱数ではない） |
| v6 | v1の並べ替え版 | 時刻順に並ぶようにしたv1 |
| v7 | Unix時刻（ミリ秒）＋乱数 | 時刻が違えば被らない。乱数は74ビット |
v3とv5は、同じ名前からは必ず同じUUIDができる仕組みなので、「被る」ことが仕様です。ここで計算した衝突確率が当てはまるのは、乱数で作るv4と、v7の乱数部分です。
データベースの主キーに使うなら、時刻順に並ぶv7を選ぶ理由があります。RFC 9562は、v4のように時刻順でないUUIDはデータベースの索引の局所性が低いと述べています。これは被りにくさとは別の話題です。
実際にUUID v4を作って確かめる
「UUID・ULIDを整える」は、ブラウザの暗号乱数でUUID v4を1〜100個まとめて作ります。ハイフンの有無、大文字、波括弧の形式にも切り替えられ、貼り付けた文字列がUUIDやULIDとして正しい形かも確かめられます。入力も結果も端末の外には出ません。
衝突の確率は、乱数が良質ならほぼゼロですが、保証ではありません。データベースの主キーなどに使うときは、重複したときにエラーで気づける仕組み（一意制約）も併用しておくのが、実務での基本です。
