GUIDの衝突は可能ですか？

https://stackoverflow.com/questions/184869

06-07-2019
|

質問

私は、関連付けられているアプリを使用する各ユーザーのGUIDを使用するSQL Server 2000のデータベースで作業しています。どういうわけか、2人のユーザーが同じGUIDになりました。マイクロソフトはアルゴリズムを使用して、衝突を引き起こす可能性が非常に低いランダムなGUIDを生成することを知っていますが、衝突はまだ可能ですか？

解決

基本的に、いいえ。誰かがあなたのデータベースをいじりに行ったと思います。使用しているバージョンGUIDに応じて、値は一意（バージョン1 GUIDなど）、または一意で予測不可能（バージョン4 GUIDなど）のいずれかです。 SQL ServerのNEWID（）関数の実装は128ビットの乱数を使用しているように見えるため、衝突は発生しません。

1％の衝突の可能性のために、 2,600,000,000,000,000,000 のGUIDを生成する必要があります。

他のヒント

基本的には不可能です！、可能性は天文学的に低いです。

しかし...私が知っている世界で唯一の人は、 GUIDコリジョンを1回持っていました（はい！）。

そして、私はそれを確信しています、そしてそれは間違いではなかった。

Pocket PCで実行されていた小さなアプリケーションで、操作が終了したときに、GUIDが生成されたコマンドを発行する必要がありました。サーバーで実行された後のコマンドは、実行日とともにサーバーのコマンドテーブルに保存されました。デバッグのある日、モジュールコマンドを（新しく生成されたGUIDを添付して）発行しましたが、何も起こりませんでした。（同じGUIDを使用して、操作の開始時にGUIDが1回だけ生成されたため）再度実行しましたが、コマンドが実行されない理由を最終的に見つけようとして、コマンドテーブルをチェックしました。現在のGUIDと同じGUIDが3週間前に挿入されました。これを信じていなかったので、2週間のバックアップからデータベースを復元しましたが、GUIDはそこにありました。コードをチェックすると、新しいGUIDは疑いなく新たに生成されました。 Pow guidの衝突は1回だけ発生しましたが、代わりに宝くじで勝ったことを願っています。チャンスはもっと大きいです:)。

編集：この問題が発生する可能性を大幅に高める要因がいくつかあります。アプリケーションはPocketPCエミュレーターで実行されていたため、エミュレーターには状態保存機能があります。つまり、状態がローカルタイムに復元されるたびにも復元され、GUIDは内部タイマーに基づいています....また、コンパクトフレームワークのGUID生成アルゴリズムは、たとえばCOMのものよりも完全ではない可能性があります...

これらは理論的には可能ですが、3.4E38の可能性のある数値を使用すると、1年に数十兆のGUIDを作成した場合、1つの重複が発生する可能性は0.00000000006（ソース）。

2人のユーザーが同じGUIDになった場合、データがコピーまたは共有される原因となっているプログラムにバグがあると思います。

まず、2つのGUIDの衝突の可能性を見てみましょう。他の回答が述べているように、誕生日パラドックスのため、2 ^ 128分の1（10 ^ 38）ではありません。つまり、2つのGUIDが50％の確率で衝突する場合、確率は実際には2 ^ 64分の1（10 ^ 19）であり、はるかに小さくなります。ただし、これは依然として非常に大きい数値であるため、妥当な数のGUIDを使用していると仮定した場合の衝突の可能性は低いです。

また、多くの人が信じているように、GUIDにはタイムスタンプまたはMACアドレスが含まれていないことにも注意してください。これはv1 GUIDには当てはまりましたが、現在はv4 GUIDが使用されています。これは単なる擬似乱数ですこれは、衝突が時間と機械に固有のものではなくなったため、衝突の可能性がほぼ間違いなく高いことを意味します。

つまり、答えはイエスです。衝突は可能です。しかし、それらはほとんどありません。

編集：2 ^ 64と言うように修正

2つのランダムなGUIDが衝突する可能性（10 ^ 38に1回）は、破損したTCP / IPパケットを検出しない可能性（10 ^ 10に1回）よりも低くなります。 http：//wwwse.inf.tu-dresden .de / data / courses / SE1 / SE1-2004-lec12.pdf 、11ページ。これは、ディスクドライブ、CDドライブなどにも当てはまります。

GUIDは統計的に一意であり、dbから読み取るデータは統計的にのみ正しいです。

Occamのカミソリは、この場合の良いガイドと考えています。 GUIDが衝突する可能性は非常に低いです。バグがあるか、誰かがあなたのデータをいじっている可能性が高いです。

Wikipediaのグローバルに一意の識別子の記事を参照してください。 GUIDを生成するにはいくつかの方法があります。どうやら、古い（？）方法ではMacアドレス、非常に短いユニットまでのタイムスタンプ、一意のカウンター（同じコンピューターで高速世代を管理するため）を使用していたため、それらを複製することはほとんど不可能です。しかし、これらのGUIDはユーザーの追跡に使用できるため削除されました...

Microsoftが使用している新しいアルゴリズムについてはわかりません（この記事では、GUIDのシーケンスは予測可能で、タイムスタンプを使用しないように見えると述べていますか？ >

現在、GUIDは、名前によってグローバルに一意になるように慎重に設計されているため、不可能または非常に低い確率でリスクが発生する可能性があります。私は他の場所を見ます。

重複したMACアドレスを持つイーサネットカードを備えた2台のWin95マシンは、特にビルの電源が切れ、両方がまったく同時に起動する場合など、厳重に制御された条件下で重複したGUIDを発行します。

GUIDは魔法であり、一意であることが保証されているという気持ちの良い答えを知っていますが、実際には、ほとんどのGUIDは121ビットの乱数です（ビットの7つは書式設定に無駄になっています）。大きな乱数を使用することに不安を感じる場合は、GUIDを使用することに不安を感じるべきではありません。

GUIDの生成に使用されるコードにバグがありますか？はい、もちろん可能です。しかし、答えはコンパイラのバグの場合と同じです-あなた自身のコードはバグがある可能性が高いので、最初にそこを見てください。

もちろんその可能性....可能性はありますか？可能性は低いですが、可能です。

同じマシンがすべてのGUID（サーバー）を生成していることを忘れないでください。マシン固有の情報に基づくものは失われます。

にやにや笑い、次のスクリプトを試してみてください...（SQL 2005で動作しますが、2000についてはわかりません）

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

これを繰り返し実行すると（1秒未満かかります）、非常に短い時間差があっても、最初の選択からかなり広い範囲が生成されます。これまでのところ、2番目の選択では何も生成されていません。

ユーザーがネットワークカードを搭載した別のマシンを使用している場合は不可能です。そうでない場合でも、非常にわずかな理論上のリスクです。

個人的には、GUIDの衝突ではなくバグの可能性が高いため、他の場所を探します...

もちろん、GUIDを少し削って短くすることはありません。

確かにそれは可能であり、おそらくそうです。各GUIDが可能な数字空間のランダムな部分にあるわけではありません。 2つのスレッドが同時に1つのスレッドを生成しようとした場合、何らかのセマフォを備えた中央集中型のGUID関数がなければ、同じ値になります。

「私はネットワーキングの人ではないので、これを前書きします。したがって、完全に一貫性のない文章を作成することがあります。」。

イリノイ州立大学で働いていたとき、私たちは2台のDellデスクトップを異なる時間に注文しました。最初の1つをネットワークに配置しましたが、2つ目をネットワークに配置しようとすると、クレイジーなエラーが発生し始めました。多くのトラブルシューティングを行った結果、両方のマシンが同じGUIDを生成していることがわかりました（正確には何のためかはわかりませんが、ネットワーク上で両方とも使用できなくなりました）。デルは実際に両方のマシンを不良品として交換しました。

GUIDの衝突は、SQL Serverの NEWID（）関数のようなものを介して生成する場合に発生する可能性はほとんどありません（もちろん、他の回答が強調しているように）。彼らが指摘していないことの1つは、実際に野生のブラウザでJavaScriptでGUIDを生成している場合、衝突に遭遇する可能性が非常に高いということです。異なるブラウザーのRNGに問題がある場合があるだけでなく、Googleスパイダーがそのような関数の結果をキャッシュしているように見える問題に遭遇し、同じGUIDをシステムに繰り返し渡すことになりました。

詳細については、さまざまな回答を参照してください：

JavaScriptでUUIDを生成する際の衝突？

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow