Hatena::ブログ(Diary)

satosystemsの日記 このページをアンテナに追加 RSSフィード

2014-01-23

[] UUID の重複する可能性

UUID Wikipedia 日本語版によると

UUIDは、分散システム上でどこかが統制を取らずとも、一意に特定可能な識別子の作成を目的としており、UUIDは重複や偶然の一致が起こりえないと確信して用いることができる。

UUID - Wikipedia

という。しかしながら、高々 122 ビットで表される数値*1である以上、生成し続ければ確実に重複する。

では、それがどれぐらいの確率なのか。

その説明は UUID Wikipedia 英語版に記載されている。英語だったり数式があったりしてわかりづらいが、説明の一部を訳してみたので、重複しない感が多少は分かるかと思う。


例 1
  • 1 兆個 UUID を生成
  • 生成した UUID が重複する確率より、隕石が頭に降ってくる確率のほうが高い
例 2
  • 100 年間、毎秒 10 億の UUID を生成し続ける
  • その後、UUID をひとつ生成
  • 生成した UUID が過去のものと一致する確率は約 50%
例 3*2
  • 地球上のすべての人に 6 億ずつ UUID を配布
  • その後、UUID をひとつ生成
  • 生成した UUID が誰かのものと一致する確率は約 50%

要するにだ、420000 京の UUID があって、ようやく重複率が 50% だということはだ、重複を考慮しなくても良いということで、重複した場合の心配をするぐらいなら、別のテストケースを追加しなよ、ということだ。


ちなみに僕は、C ヘッダのインクルードガードに UUID を使っている。よくある #ifndef HOGE_H__ とかだと偶然重複しそうじゃない?

*1:5316911983139663491615228241121378304

*2:なんか、例 2 と例 3 が同じ確率というのがびっくり。感覚的に 100 年間の UUID の生成数の方が圧倒的に多いように思えるんだけど・・・、計算してみたら実は逆だったというのにびっくりした。例 2: 3153600000000000000 個 = 60 × 60 × 24 × 365 × 100 × 1000000000、例 3: 4200000000000000000 個 = 600000000 個 × 7000000000 億人

tbrooktbrook 2017/01/22 21:04 420京では? 自分が何か勘違いしてるのかな

タカべぇ〜タカべぇ〜 2017/01/29 01:15 例2、3は全然参考にならない気がする。。
前提の段階で重複が発生しないのかが不明確だし、既に50%の確率になってたら使い物にならないと思った。二人に一人が重複になるのだから。
仮に1%だったとしてもダメだと思う。
だから前提の時点で破綻してる。。。

主さんに言うことじゃないですが。。

通りすがりの選任通りすがりの選任 2017/02/14 10:27 タカべぇ〜さん
なぜ50%かが分からないようなので解説します。
確率はシステムや人間の主観により閾値がバラバラで絶対の基準値はありません。
あるのは以下の3分類です。
1.0%
2.100%
3.0%より大きく100%未満

論理上『異なる2値が重複する確率』は0%でも100%でもありませんので、確率としては必ず上記3.となります。(数は無限なので0%も100%も有り得ません)
そして、前述の通り3の分類の『どの値が適切か?』はシステムや主観により異なります。
SLA上0.00001%でも不十分な契約もあれば、99%でも問題ない場合もあります。
タカべぇ〜さんの"主観"では1%でも重複は『ダメ』とお考えのようですが、それはあくまで個人の考えであり、論理的な判定基準ではありません。

ではなぜ50%で算出するのでしょうか?

答えは単純であり、は0%〜100%の中間値だからです。

例2、3が『なぜ1%の値にせずわざわざ50%で算出しているのか?』考えれば分かるかと思います。
"6億ずつ配布"という値を"6000万ずつ配布"に変えれば確率は5%になります。
600万に変えれば0.5%になります。
わざわざ中間値の50%に併せて"6億"という前提を算出しているだけなのです。
ご理解いただけたでしょうか?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト

コメントを書くには、なぞなぞ認証に回答する必要があります。

トラックバック - http://d.hatena.ne.jp/satosystems/20140123/1390460471
リンク元
Connection: close