UUIDを重複させるにはどれだけ時間がかかるのか試してみた
絶対に重複しないといわれるUUID
UUIDとはUniversally Unique Identifier の略で、「Universally」つまり将来にわたって重複や偶然の一致が起こらないという前提で使われるIDのことです。
128ビットで表現されるUUIDは2^128通り（Version 4では固定値があるため2^122通り）あり、その膨大なパターンから将来に渡って重複しないとされています。その特性から、ファイルのハッシュ値に使われたり、DBのキーに使われたりしています。重複しないことが約束されているので、大変使い勝手が良いのです。
とはいえ、有限桁数である以上は重複が発生する可能性がごく僅かながら存在します。
では実際に重複させるには、どれだけUUIDを作らないといけないのか試してみます。
まずは計算で目算をつける
x通りのパターンがあるとき、衝突回数がpになるときの試行回数nは以下の式で求められます。
xは2^122なので衝突する確率はかなり低いことが式から分かります。仮にp=0.5にしたい場合、必要な試行回数は2.3×10^18程度となり、だいたい230京回ぐらいです。
めちゃめちゃ低い確率ですが、実際どれだけ信頼できる値なのかピンときません。
京ぐらいならいける気もする…？
実感したければ作ればいい
回数ではピンと来なかったので、重複させるにはどれぐらい時間がかかるかを試してみました。
実際に全桁を一致させるには途方もない時間がかかると思われるので、数桁一致するUUIDを生成するにはどれだけの時間を要するか計測します。ある程度やれば傾向が見えてくるはずです。
コードは例のごとくGoで書きました
こちらがベンチマーク結果です。
$ 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桁以降も同じような所要時間が必要とすると
あまりにも桁数が多くなってしまったので、漢数字で表現してみましたがもっと分からなくなりました。
数千万台のPCがUUIDを作り続けたとしても、数百年は余裕で重複しなさそうです。数年運用していて、UUIDが重複してしまったとしたら、それは運が悪かったとしか言いようがないでしょう。
そもそもの前提が崩れたら重複する
特に触れて来ませんでしたが、ここまでの話はUUIDが一様に生成されることを前提にしています。
UUIDの生成に偏りがあれば、衝突確率はもちろん高くなってしまいます。そして、 UUIDの生成方法の多くは疑似乱数を用いています。
コンピュータの分野において、正確な乱数を作るというのは難しいというよりは不可能といわれています。ミクロな視点でコンピュータは0と1の集合体でしかありません。中途半端な状態を表現するのに適していないのです。
とはいえ、実際にコンピュータ上で検証した結果なので重複はしないと断言してもいいかと思います。
ごく一部のシビアなシステムでは使えませんが、多くのケースにおいてUUIDは活躍してくれるでしょう。
これで今日から安心してUUIDを使えるというものです。
Discussion
面白い記事ありがとうございます。
読んでいて違和感あったところの検算です。私の計算ミスだったらすみません。
またGitHubで編集を提案が404（おそらくprivateリポジトリ?）なのでコメントで失礼します。
kaya さん
ご指摘ありがとうございます
再計算したところ、コメントのとおりでした
急ぎ、修正致します
また、リポジトリをprivateからpublicに変更しました
goのコードを見る限り「ランダムに選んだ２つのUUIDが衝突しているケース」を想定して計算しているようなので、x n p(n) = 1-(1-1/x)^n x = 2^{122} p(n) = 0.5 n \approx 3.6 \times 10^{36}
その場合、