GUID は 100% の確率で一意ですか?

https://stackoverflow.com/questions/39771

09-06-2019
|

質問

複数のスレッドにわたって一意性が維持されますか?

解決

生成された各GUIDは一意であることが保証されていませんが、一意のキーの総数（2¹²⁸ または3.4×10³⁸）非常に大きいため、同じ数が2回生成される可能性は非常に少ないです。たとえば、約5×10を含む観察可能な宇宙を考えてみましょう²²出演者;その後、すべての星には6.8×10があります¹⁵ 普遍的に一意の GUID。

からウィキペディア.

これらは、(.NET の) GUID の作成方法と、適切な状況で同じ GUID を取得する方法についての優れた記事です。

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-three/

他のヒント

簡単な答えは「はい」です。

レイモンド・チェンはこう書きました素晴らしい記事 GUID と GUID の部分文字列が存在する理由ないユニークであることが保証されています。この記事では、GUID の生成方法と、GUID が一意性を確保するために使用されるデータについて、ある程度詳しく説明しています。なぜ彼らです：-）

同じ GUID 値が怖い場合は、それらを 2 つ並べて配置してください。

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

あまりにも偏執的な場合は、3 つ入れてください。

余談ですが、私は Windows XP でボリューム GUID をいじっていました。これは、3 つのディスクと 14 のボリュームを含む、非常にわかりにくいパーティションレイアウトです。

\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
                                     | | | | |
                                     | | | | +-- 6f = o
                                     | | | +---- 69 = i
                                     | | +------ 72 = r
                                     | +-------- 61 = a
                                     +---------- 6d = m

これは GUID が非常に似ているということではなく、すべての GUID に文字列「mario」が含まれているという事実です。それは偶然ですか、それともこの背後に説明がありますか?

今、いつパート 4 をグーグルで検索する GUID では、ボリューム GUID を持つ約 125,000 件のヒットが見つかりました。

結論： ボリューム GUID に関しては、他の GUID ほど一意ではありません。

はい、GUID は常に一意である必要があります。これはハードウェアと時間の両方に基づいており、一意であることを確認するためにいくつかの追加ビットが加えられています。最終的に 2 つの同一のものが得られることは理論的には可能だと思いますが、現実のシナリオではその可能性は非常に低いです。

Raymond Chen による Guids に関する素晴らしい記事は次のとおりです。

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

そんなことはあってはならないのです。ただし、.NET の負荷が高い場合、重複した GUID を取得する可能性があります。2 つの異なる SQL サーバーを使用する 2 つの異なる Web サーバーがあります。データをマージしようとすると、1,500 万の GUID と 7 つの重複があることがわかりました。

GUID は統計的に一意です。2 つの異なるクライアントが同じ Guid を生成する確率は、極めて小さいです (Guid 生成コードにバグがないことを前提としています)。宇宙線のせいでプロセッサーが故障して、今日は 2+2=5 と判断されるのではないかと心配するほうがよいでしょう。

新しい GUID を割り当てる複数のスレッドは一意の値を取得しますが、呼び出している関数がスレッドセーフであることを確認する必要があります。これはどの環境ですか？

Eric Lippert は、GUID に関する非常に興味深い一連の記事を執筆しています。

注文中です 2³⁰ 世界のパーソナルコンピューター（そしてもちろん、多くのハンドヘルドデバイスまたはコンピューティングパワーのレベルが多いが、それらを無視できる）非PCコンピューティングデバイスが多数あります）。世界のすべてのPCをGUIDを生成するタスクに置いたと仮定しましょう。それぞれが、たとえば 2 つ生成できる場合²⁰ わずか2秒後に1秒あたりのガイド⁷² 秒 -- 150兆年 -- を持っています。 すごく高い 特定のGUIDとの衝突を生成する可能性。そして、衝突の可能性はわずか30兆年後にかなり良いものになります。

理論的には、いいえ、それらは一意ではありません。同一の guid を何度も生成することが可能です。ただし、それが発生する可能性は非常に低いため、それらは独自のものであると想定できます。

以前に読んだことがありますが、その可能性は非常に低いため、サーバーの自然発火やコード内のその他のバグなど、別のことを強調する必要があります。つまり、それが一意であると仮定し、重複を「キャッチ」するためのコードを組み込まないでください。より発生する可能性の高いことに時間を費やしてください。 何でも それ以外）。

私試みをしました私のブログの読者 (技術者以外の家族) に GUID の有用性を説明するためです。そこから (Wikipedia 経由)、重複した GUID が生成される確率は次のようになります。

1/2^128
340人に1件（心配しないでください、undecillionはクイズに載っていません）
1 in 3.4 × 10^38
340,000,000,000,000,000,000,000,000,000,000,000,000 分の 1

それが起こる確率の実際の計算については誰も言及していないようです。

まず、128 ビット空間全体を使用できると仮定します (Guid v4 は 122 ビットのみを使用します)。

重複が得られない一般的な確率は、 n ピックは次のとおりです。

(1-1/2¹²⁸)(1-2/2¹²⁸)...(1-(n-1)/2¹²⁸)

なぜなら 2¹²⁸ よりもはるかに大きいです n, 、これは次のように近似できます。

(1-1/2¹²⁸)^n(n-1)/2

そして、私たちは推測できるので、 n は 0 よりもはるかに大きいため、次のように近似できます。

(1-1/2¹²⁸)^{n^2/2}

これで、これを「許容可能な」確率、たとえば 1% とみなすことができます。

(1-1/2¹²⁸)^{n^2/2} = 0.01

私たちが解決するもの n そして以下を取得します:

n = sqrt(2* log 0.01 / log (1-1/2¹²⁸))

Wolfram Alphaはどれになるのか 5.598318 × 10¹⁹

この数字を視野に入れるために、それぞれ 4 コア CPU を搭載し、4Ghz を実行し、GUID の生成に 10,000 サイクルを費やし、他には何も行わない 10,000 台のマシンを考えてみましょう。その後、複製が生成されるまでに最大 111 年かかります。

から http://www.guidgenerator.com/online-guid-generator.aspx

GUIDとは何ですか?

GUID (または UUID) は、「Globally Unique Identifier」(または「Universally Unique Identifier」) の頭字語です。これは、リソースを識別するために使用される 128 ビットの整数です。GUID という用語は通常、Microsoft テクノロジを扱う開発者によって使用されますが、UUID はそれ以外のあらゆる場所で使用されます。

GUID はどのくらいユニークですか?

128 ビットは十分な大きさであり、生成アルゴリズムは十分にユニークであるため、1 年間に 1 秒あたり 1,000,000,000 個の GUID が生成されたとしても、重複の確率はわずか 50% になります。あるいは、地球上のすべての人間が 6 億の GUID を生成したとしても、重複する確率は 50% しかありません。

MSDN:

新しい GUID の値がすべて 0 であるか、他の GUID と等しい可能性は非常に低いです。

システムクロックが適切に設定されており、ラップアラウンドしていない場合、および NIC に独自の MAC がある場合 (つまり、カスタム MAC を設定していません)、NIC ベンダーは MAC をリサイクルしていません (これは想定されていませんが、実際に行われることが知られています)。システムの GUID 生成機能が適切に実装されていれば、システムは MAC をリサイクルします。重複した GUID を生成しないでください。

GUID を生成する地球上の全員がこれらのルールに従っている場合、GUID は世界的に一意になります。

実際には、ルールを破る人の数は少なく、その GUID が「逃げる」可能性は低いです。統計的には紛争は起こりそうにありません。

GUID の重複が発生しました。

私は Neat Receipts デスクトップスキャナーを使用していますが、これには独自のデータベースソフトウェアが付属しています。このソフトウェアにはクラウドへの同期機能があり、同期時にエラーが発生し続けました。ログをざっと調べてみると、素晴らしい一文が見つかりました。

"エラー":[{"コード":1,"メッセージ":"creator_guid:すでに取られている」、「GUID」：「C83E5734-D77A-4B09-B8C1-9623CAC7B167 "}]}

私は少し信じられませんでしたが、確かに、ローカルのneatworksデータベースへの方法を見つけて、そのGUIDを含むレコードを削除したところ、エラーは発生しなくなりました。

したがって、事例証拠を使ってあなたの質問に答えるには、「いいえ」です。重複も可能です。しかし、それが起こった理由は偶然によるものではなく、何らかの形で標準的な慣行が遵守されていなかったことが原因である可能性があります。（私が運に恵まれていないだけです）しかし、そうとも言い切れません。それは私のソフトウェアではありません。

彼らのカスタマーサポートは非常に丁寧で親切でしたが、3 時間以上電話で話し合っても解決策が見つからなかったため、これまでこの問題に遭遇したことがなかったのでしょう。(FWIW、私は Neat に非常に感銘を受けており、この不具合はどんなにイライラさせられたとしても、彼らの製品に対する私の意見を変えることはありませんでした。)

GUID は 100% の確率で一意ですか?

生成方法はいくつかあるため、保証はできません。ただし、同一の 2 つの GUID が作成される確率を計算してみると、次のようなアイデアが得られます。GUID は 128 ビットなので、2 つあります。¹²⁸ 個別の GUID – 多くの 既知の宇宙にある星の数よりも多いのです。読むウィキペディアの記事詳細については。

GUID アルゴリズムは通常、v4 GUID 仕様に従って実装されます。これは本質的に擬似ランダム文字列です。残念ながら、これらは次のカテゴリーに分類されます。 「ユニークではない可能性が高い」, 、ウィキペディアより（なぜこれほど多くの人がこの部分を無視するのかわかりません）：「...他の GUID バージョンには、保証された一意性からおそらく非一意性まで、異なる一意性のプロパティと確率があります。」

V8 の JavaScript の擬似ランダムプロパティ Math.random() は一意性が非常に高く、わずか数千回の反復後に衝突が発生することがよくありますが、原因は V8 だけではありません。私は、v4 GUID の PHP 実装と Ruby 実装の両方を使用した実際の GUID の衝突を確認しました。

ID 生成を複数のクライアントやサーバーのクラスターにまたがって拡張することがますます一般的になっているため、エントロピーが大きな打撃を受けます。ID の生成に同じランダムシードが使用される可能性が高まります (時間がランダムシードとして使用されることがよくあります)。擬似ランダムジェネレータで)、GUID の衝突は「一意ではない可能性が高い」から「多くの問題を引き起こす可能性が非常に高い」までエスカレートします。

この問題を解決するために、私は安全に拡張でき、衝突に対するより良い保証を提供できる ID アルゴリズムの作成に着手しました。これは、タイムスタンプ、メモリ内のクライアントカウンタ、クライアントフィンガープリント、およびランダムな文字を使用して行われます。要素を組み合わせると、追加の複雑さが生まれ、多数のホストにわたってスケールした場合でも、衝突に対して特に耐性があります。

http://usecuid.org/

私は、マルチスレッド/マルチプロセスの単体テスト中に GUID が一意ではないことを経験しました (それも?)。これは、他のすべての条件が等しい場合、擬似ランダムジェネレータの同一のシード（またはシードの欠如）に関係があると思います。一意のファイル名を生成するために使用していました。OS のほうがその点でははるかに優れていることがわかりました :)

トローリング警告

GUID が 100% 一意であるかどうかを尋ねます。それは、一意である必要がある GUID の数によって異なります。GUID の数が無限に近づくと、GUID が重複する確率は 100% に近づきます。

より一般的な意味では、これは「誕生日問題」または「誕生日のパラドックス」として知られています。Wikipedia には非常に詳しい概要が記載されています。ウィキペディア - 誕生日の問題

非常に大まかに言うと、プールサイズの平方根は、重複の可能性が 50% であると予想できるおおよその近似値です。この記事には、2^128 の行を含む、プールサイズとさまざまな確率の確率テーブルが含まれています。したがって、衝突の確率が 1% の場合、2.6*10^18 の 128 ビット数値がランダムに選択されると予想されます。50% の確率には 2.2*10^19 のピックが必要ですが、SQRT(2^128) は 1.8*10^19 です。

もちろん、これは本当にランダムなプロセスの理想的なケースにすぎません。他の人が述べたように、多くのことがそれに基づいています ランダム 側面 - ジェネレーターとシードはどれほど優れているのでしょうか?このプロセスを支援する何らかのハードウェアサポートがあり、なりすましや仮想化が可能であることを除けば、より防弾性が高いとよいでしょう。おそらくそれが MAC アドレス/タイムスタンプが組み込まれなくなった理由ではないかと思います。

の答え 「GUID は 100% 一意ですか?」 単純に "いいえ" .

GUID を 100% 一意にしたい場合は、次の手順を実行します。
1. GUIDを生成する
2. 一意性を探しているテーブル列にその GUID が存在するかどうかを確認してください
3. 存在する場合はステップ 1 に進み、そうでない場合はステップ 4
4. この GUID を一意として使用します。

最も難しい部分は、重複した GUID を生成することではありません。

最も難しい部分は、生成されたものをすべて保存し、実際に複製されているかどうかを確認するデータベースを設計することです。

WIKIより:

たとえば、少なくとも 1 回の衝突が 50% の確率で発生するために生成する必要があるランダムなバージョン 4 UUID の数は、次のように計算すると 2.71 京です。

ここに画像の説明を入力してください

この数は、約 85 年間で 1 秒あたり 10 億の UUID を生成することに相当し、これだけの数の UUID を含むファイルは、UUID あたり 16 バイトで約 45 エクサバイトになり、現在存在する最大のデータベースよりも何倍も大きくなります。数百ペタバイトのオーダー

GUID は Global Unique Identifier の略です

簡単に言うと:（ヒントは名前にあります）

詳細に：GUID は一意になるように設計されています。これらは、コンピュータのクロックとコンピュータ自体に基づくランダムな方法を使用して計算されます。同じマシン上で同じミリ秒で多数の GUID を作成している場合、それらが一致する可能性がありますが、ほとんどすべての通常の操作では、それらは一意であると見なされます。

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

所属していません StackOverflow