👻

UUIDを重複させるにはどれだけ時間がかかるのか試してみた

commits2 min read 3

絶対に重複しないといわれるUUID

UUIDとはUniversally Unique Identifier の略で、「Universally」つまり将来にわたって重複や偶然の一致が起こらないという前提で使われるIDのことです。

128ビットで表現されるUUIDは2^128通り(Version 4では固定値があるため2^122通り)あり、その膨大なパターンから将来に渡って重複しないとされています。その特性から、ファイルのハッシュ値に使われたり、DBのキーに使われたりしています。重複しないことが約束されているので、大変使い勝手が良いのです。

とはいえ、有限桁数である以上は重複が発生する可能性がごく僅かながら存在します。
では実際に重複させるには、どれだけUUIDを作らないといけないのか試してみます。

まずは計算で目算をつける

x通りのパターンがあるとき、衝突回数がpになるときの試行回数nは以下の式で求められます。

p(n) \approx 1 - e^{-\frac{n^2}{2\cdot2^x}}

xは2^122なので衝突する確率はかなり低いことが式から分かります。仮にp=0.5にしたい場合、必要な試行回数は2.3×10^18程度となり、だいたい230京回ぐらいです。

めちゃめちゃ低い確率ですが、実際どれだけ信頼できる値なのかピンときません。
京ぐらいならいける気もする…?

実感したければ作ればいい

回数ではピンと来なかったので、重複させるにはどれぐらい時間がかかるかを試してみました。

実際に全桁を一致させるには途方もない時間がかかると思われるので、数桁一致するUUIDを生成するにはどれだけの時間を要するか計測します。ある程度やれば傾向が見えてくるはずです。

コードは例のごとくGoで書きました

https://github.com/kiyocy24/uuid-sim

こちらがベンチマーク結果です。

$ go test -bench . -benchmem -benchtime 10s
goos: windows
goarch: amd64
pkg: github.com/kiyocy24/uuid-sim/sim
cpu: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
BenchmarkSim_Run1-4      1891098              6321 ns/op
BenchmarkSim_Run2-4       121977             99498 ns/op
BenchmarkSim_Run3-4         7462           1584629 ns/op
BenchmarkSim_Run4-4          496          26347940 ns/op
BenchmarkSim_Run5-4           26         544971615 ns/op
BenchmarkSim_Run6-4           44        4905786670 ns/op
PASS
ok      github.com/kiyocy24/uuid-sim/sim        289.807s

おなじみのGo Benchmarkを使いました。一致させる桁数(10進数)を1~6で変化させて、それぞれどれだけ時間がかかるかを調べました。単位がnsなので分かりづらいですね。

図にしてみます。

縦の目盛りからわかるように対数グラフです。基数を10としているので、1目盛り上がるごとに数値は10倍です。サンプル数が少ないですが、概ね線形に所要時間が増加しているように見えます。

6桁で4.9sほどかかっていて、UUIDの全桁数は32桁です。
7桁以降も同じような所要時間が必要とすると

4.9 \times 10^{32 - 6}秒 = 4.90 \times 10^{26}秒 \\ \approx 5.67 \times 10^{21} 日 \\ \approx 1.55 \times 10^{19} 年 \\ \approx 1550 京年

あまりにも桁数が多くなってしまったので、漢数字で表現してみましたがもっと分からなくなりました。
数千万台のPCがUUIDを作り続けたとしても、数百年は余裕で重複しなさそうです。数年運用していて、UUIDが重複してしまったとしたら、それは運が悪かったとしか言いようがないでしょう。

そもそもの前提が崩れたら重複する

特に触れて来ませんでしたが、ここまでの話はUUIDが一様に生成されることを前提にしています。
UUIDの生成に偏りがあれば、衝突確率はもちろん高くなってしまいます。そして、 UUIDの生成方法の多くは疑似乱数を用いています。

コンピュータの分野において、正確な乱数を作るというのは難しいというよりは不可能といわれています。ミクロな視点でコンピュータは0と1の集合体でしかありません。中途半端な状態を表現するのに適していないのです。

とはいえ、実際にコンピュータ上で検証した結果なので重複はしないと断言してもいいかと思います。
ごく一部のシビアなシステムでは使えませんが、多くのケースにおいてUUIDは活躍してくれるでしょう。

これで今日から安心してUUIDを使えるというものです。

参考リンク

GitHubで編集を提案

Discussion

面白い記事ありがとうございます。

読んでいて違和感あったところの検算です。私の計算ミスだったらすみません。
またGitHubで編集を提案が404(おそらくprivateリポジトリ?)なのでコメントで失礼します。

4.90×10^{26}秒
≈ 5.67×10^{21}日
≈ 1.55×10^{19}年
= 1550京年

kaya さん

ご指摘ありがとうございます
再計算したところ、コメントのとおりでした
急ぎ、修正致します

また、リポジトリをprivateからpublicに変更しました

goのコードを見る限り「ランダムに選んだ2つのUUIDが衝突しているケース」を想定して計算しているようなので、 x パターンの集合に対して試行回数 n で一度でも衝突が発生する確率は p(n) = 1-(1-1/x)^n となりますね。
その場合、 x = 2^{122} とすると p(n) = 0.5 となるのは n \approx 3.6 \times 10^{36} であるため、試行回数はもっと必要ですね。

ログインするとコメントできます