十分大きな乱数をユニークな識別子として使うのがなぜ安全なのか｜Rui Ueyama

いろいろなソフトウェアで、大きいランダムな値をユニークな値とみなすということが行われている。例えばユニークな識別子としてよく使われるUUIDはただの122ビットの乱数だ。gitもSHA-1ハッシュ値が160ビットの乱数のように扱えることを期待して、それをユニークな識別子として使っていた。実際にはランダムな2つの値が同じになる確率はゼロではないのに、なぜこれが安全なやり方だと言えるのだろうか？ それについてちょっと説明してみよう。 あるシステムが、乱数で生成された識別子の衝突のなさに依存しているとして、仮に衝突が発生した場合、相当悪い結果、例えば復旧不可能な形でデータベースが壊れてしまうとしよう。これはどれくらい危険なのだろうか？ 数学の問題で、学校のクラスの中で同じ誕生日の人が1組以上いる可能性は思ったより高いという話を聞いたことがあると思う。あるランダムに生成された値が衝突する確率という

[heniha]

十分だからなのでは（国語

[maninthemiddle]

この習慣が定着する以前はユニーク性を担保したidを払い出し管理する機構を作って糞真面目に対応するのがスタンダードだった時代もあったけど、とてもコストが高かった。この記事のような認識が定着して呪いが解けた

[n_231]

プロジェクトのメンバー全員が別々の原因で明日死亡する可能性の方が高いというアレ。しかしサンプル数が兆を超えるオーダーで本当に擬似乱数が機能するのかというと……

[otchy210]

ある程度予測可能である事を許容するなら、例えばシステムID→アプリID→インスタンスID→タイムスタンプ→乱数、を連結してユニークにすることで、ID に復号可能な情報を持たせられて良い。というか弊社がそれ。

[unagiga]

この口がキンタマに見える猫のブログはよく興味深いことを書いているように思う（専門外）

[uasi]

追記：修正された／記事は UUID (v4) を128ビットの乱数としているが、実際には固定値が6ビットあるから乱数部分は122ビット。100兆個生成すると10億分の1の確率で衝突する。

[altar]

分散システムだと中央集権的な衝突検出ができないから、この命題を信じ切れるかどうかがよりクリティカルな時代であるとは言える。

[anoworl]

擬似乱数なので乱数の生成方法によるし、生成方法に脆弱性があった（推測が可能もしくは充分なエントロピーを持っていない）という問題はよく見る気がする

[mattn]

言葉のマジック

[sgo2]

ハッシュテーブルとか見れば分かるけど、衝突が発生すること自体は対策可能な問題。問題なのは衝突が検出できない可能性の方だけど…まあ杞憂だよねと。

[fai_fx]

乱数の総数より、シードの総数が少ない方が問題だったりね。

[youichirou]

ビット数としては十分でも、そのシステムが生成する乱数がへっぽこ打ったらというしんぱいはついてまわるかも。

[masaru_b_cl]

まず衝突しないけど、したら再生成するようにすれば多い日も安心

[Nkzn]

このIDが衝突するくらいならそれより先にこの会議室に隕石落ちてきますよって言ってるのにゼロではないからと採用しなかった人に会ったことあるなあ・・・

[vvakame]

僕びびりなので…

[massa142]

それが本当にランダムなら / “乱数のビット数が十分に大きくて、それが本当にランダムなら、衝突の可能性を心配するのは天が落ちてくるのを替わりに心配したほうがマシなくらい杞憂なのだ”

[Nyoho]

ただ十分と唱えるだけでなくちゃんと桁数を計算して初めて順当な推論だとわかることだね。

[frkw2004]

スーパーコンピューター「京」が10PFLOPオーダーの計算力だから、１エクサバイトのデータを扱うのに1000秒(=数10分)のオーダーで間に合いそう。計算力はムーアの法則で向上してるから杞憂かどうかは判定できない。

[zyzy]

みんな大好き乱数問題。疑似乱数だとどうしても信じきれない所はあるよね。

[katow]

みんな似たようなプラスアルファ解決も考えていて自分と変わらないのだなとほっこり。

[richard_raw]

825兆個生成しても衝突する確率は10億分の一と。

[UDONCHAN]

そうだね

[hasegawatomoki]

誰かが重複が無いことを保証しない限り、自分でUUID生成したら重複している可能性は捨てたくない。チェック結果重複してたら再生成などのリカバリをしないで die(); する、という解決はバランス良くて好き。

[rjge]

“128ビット乱数を825兆個生成したとき、衝突している乱数が10億分の1の確率で存在するということになる。825兆個の128ビット乱数というのはそれを保存するだけでディスクが1.3エクサバイト必要になる”

[ghostbass]

825兆のコミットログなんて見たくもない(そこじゃない

[anosuteki]

マーフィーの法則で、10億年に1度起こることは来週の火曜日に起こるってばっちゃが

[Kil]

ま、「隕石が来年地球にぶつかる」くらいのことが、TOTOBIGでは起こったりしてますけどね。「それが本当にランダムなら」

[teracy_junk]

『乱数のビット数が十分に大きくて、それが本当にランダムなら、衝突の可能性を心配するのは天が落ちてくるのを替わりに心配したほうがマシなくらい杞憂なのだ』

[qtamaki]

原因はリスクゼロ信仰

[mohno]

そこを心配してる人ってどれくらいいるんだろう、という気はするけどね。「衝突の可能性を心配するのは天が落ちてくるのを替わりに心配したほうがマシ」←いや、普通にバグが起きる可能性を心配しろとw

[dgen]

隕石は年を単位にしているが世界中のＰＣをハックしてトライすれば単位は極端に小さくなる。マイニングなんて公にそんなことしてるでしょ。

[dora04]

確実な乱数が得られることで、昨今問題となる抽選やガチャの確率の偶発性を担保できると思うんだけど、「ホントに乱数で計算したの？」と言われる透明性が課題だよなぁ、って。

[tsekine]

"825兆個の128ビット乱数というのはそれを保存するだけでディスクが1.3エクサバイト必要になるという、とても大きな数だ" uniquenessという観点と、今後のストレージの増加を考えると 1.3 EB ってそこまで大きくないでしょ

[chinpokomon_master]

UUIDは128ビットではないというクソリプを考えたが既にしてる人がいた。まあ、知ってると思うよ。

[you21979]

ビットコインのアドレスの話や

[habarhaba]

素人考えでタイムスタンプを加えたらもっと衝突しないかもと、思ったけどそれが古いUUIDだった

[himask6996]

「本当にランダム」？？？

[nakayuki805]

この前にユニークID生成を実装したときはunixtime+ミリ秒+乱数(少なめ)にした(同時刻という条件なら更に被りにくいだろうから)

[turanukimaru]

10億に反応している人がいるが重要なのは825兆個生成、つまり使い切れないというほう。なに疑似乱数とはいってもTOTOよりはまともな実装してるよ多分http://nlab.itmedia.co.jp/nl/articles/1702/20/news104.html