Clever Geek Handbook

UUIDの生成方法



プロジェクトですでにUUIDを使用していて、それらが一意であると考えている可能性があります。同じ値が発生する可能性はごくわずかであるため、実装の主な側面を見て、UUIDが実際に一意である理由を見てみましょう。



UUIDの最新の実装は、これらの識別子を生成するための5つの異なるアプローチを説明しているRFC4122までさかのぼることができます。それぞれについて説明し、バージョン1とバージョン4の実装について説明します。



理論



UUID（普遍的に一意のIDentifier）は、要素の一意の識別子としてソフトウェア開発で使用される128ビットの番号です。その古典的なテキスト表現は、ハイフンで8-4-4-4-12パターンの5つのグループに分けられた一連の32個の16進文字です。



例えば： 



3422b448-2460-4fd2-9183-8000de6f8343


UUID実装情報は、この一見ランダムな文字シーケンスに埋め込まれています。 



xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx


位置MとNの値は、それぞれUUIDのバージョンとバリアントを定義します。



バージョン



バージョン番号は、位置Mの最上位4ビットで識別されます。現在、次のバージョンが存在します。





オプション



このフィールドは、UUIDに埋め込まれた情報のテンプレートを定義します。UUID内の他のすべてのビットの解釈は、バリアントの値によって異なります。



位置Nの最初の1〜3の最上位ビットによって決定します。





今日、オプション1が最も頻繁に使用され、MSB0equals1とMSB1equalsです0。ワイルドカードを指定されたことが、この手段-選択されたビット-唯一の可能な値は8、9、AまたはB。



メモ：



1 0 0 0 = 8

1 0 0 1 = 9

1 0 1 0 = A

1 0 1 1 = B


したがって、位置Nにそのような値を持つUUIDが表示された場合、これはオプション1の識別子です。



バージョン1（時間+一意またはランダムなホストID）



この場合、UUIDは次のように生成されます。UUIDを生成するデバイスの識別プロパティが現在の時刻に追加されます。ほとんどの場合、これはMACアドレス（ノードIDとも呼ばれます）です。



識別子は、48ビットのMACアドレス、60ビットのタイムスタンプ、14ビットの「一意の」クロックシーケンス、およびバージョンとバリアントのUUID用に予約された6ビットを連結することによって取得されます。



クロックシーケンスは、クロックが変更されるたびにインクリメントされる値です。


このバージョンで使用されるタイムスタンプは、グレゴリアンカレンダーが作成された日付である1582年10月15日からの100ナノ秒間隔の数です。



エポックが始まって以来、Unixシステムの時代に精通しているかもしれません。それはちょうど別の種類のデイゼロです。ある時間的表現を別の時間的表現に変換するのに役立つサービスがWeb上にあるので、そこで止まらないでください。


この実装は非常に単純で信頼性が高いように見えますが、識別子が生成されるマシンのMACアドレスを使用すると、この方法をユニバーサルと見なすことはできません。特に安全性が主な基準である場合。したがって、一部の実装では、ノード識別子の代わりに、暗号で保護されたランダム番号ジェネレータから取得した6つのランダムバイトが使用されます。



UUIDバージョン1の構築は次のようになります。



  1. 現在のUTCタイムスタンプの最下位32ビットが取得されます。これは、UUID [ TimeLow]の最初の4バイト（8つの16進文字）になります。
  2. 現在のUTCタイムスタンプの中央の16ビットが取得されます。これは次の2バイト（4つの16進文字）[ TimeMid]になります。
  3. 次の2バイト（4つの16進文字）は、UUIDバージョンの4ビットを現在のUTCタイムスタンプの残りの12 MSB（合計60ビット）と連結します[ TimeHighAndVersion]。
  4. 次の1〜3ビットは、UUIDバージョンバリアントを定義します。残りのビットには、この実装に少しランダム性を追加するクロックシーケンスが含まれています。これにより、複数のUUIDジェネレーターが同じシステムで実行されている場合の衝突が回避されます。システムクロックがジェネレーターに戻されるか、時間の変更が遅くなります[ ClockSequenceHiAndRes && ClockSequenceLow]。
  5. 最後の6バイト（12の16進文字、48ビット）は「ノードID」であり、通常はジェネレーターのMACアドレスです[ NodeID]。


バージョン1のUUIDは、連結を使用して生成されます。 



TimeLow + TimeMid + TimeHighAndVersion + (ClockSequenceHiAndRes && ClockSequenceLow) + NodeID


この実装はクロックに依存するため、エッジの状況を処理する必要があります。まず、システム間の相関を最小限に抑えるために、デフォルトでは、クロックシーケンスはランダムな数値と見なされます。これは、システムのライフサイクル全体で1回だけ実行されます。これにより、最初のクロックシーケンスがノードIDから完全に独立しているため、システム間で伝送できるノードIDをサポートするという追加の利点が得られます。



クロックシーケンスを使用する主な目的は、方程式にランダム性を追加することであることを忘れないでください。クロックシーケンスビットは、タイムスタンプを拡張し、プロセッサクロックが変更される前でも複数のUUIDが生成される状況に対応するのに役立ちます。このようにして、クロックが後退したとき（デバイスがオフのとき）またはノード識別子が変更されたときに同じ識別子を作成することを回避します。クロックがセットバックされているか、セットバックされている可能性があり（たとえば、システムのシャットダウン中）、UUIDジェネレーターが、指定されたクロック値よりも遅いタイムスタンプで識別子が生成されたことを確認できない場合は、クロックシーケンスを変更する必要があります。以前の値がわかっている場合は、単純に増やすことができます。それ以外の場合は、ランダムに設定するか、高品質のPRNGを使用して設定する必要があります。



バージョン2（分散コンピューティング環境のセキュリティ）



このバージョンと以前のバージョンの主な違いは、クロックシーケンスの最下位ビットの形式での「ランダム性」の代わりに、システムの識別子特性がここで使用されることです。多くの場合、これは現在のユーザーのIDです。バージョン2はあまり使用されておらず、バージョン1とほとんど変わらないので、次に進みましょう。



バージョン3（名前+ MD5ハッシュ）



命名または命名情報に一意の識別子が必要な場合は、通常、UUIDバージョン3またはバージョン5が使用され



、「名前付き」エンティティ（サイト、DNS、プレーンテキストなど）をUUID値にエンコードします。最も重要なことは、同じ名前名またはテキストに対して同じUUIDが生成されることです。



名前付け自体はUUIDであることに注意してください。 



let namespace = “digitalbunker.dev”
let namespaceUUID = UUID3(.DNS, namespace)

// Ex: 
UUID3(namespaceUUID, “/category/things-you-should-know-1/”) 
4896c91b-9e61-3129-87b6-8aa299028058

UUID3(namespaceUUID, “/category/things-you-should-know-2/”) 
29be0ee3-fe77-331e-a1bf-9494ec18c0ba

UUID3(namespaceUUID, “/category/things-you-should-know-3/”) 
33b06619-1ee7-3db5-827d-0dc85df1f759


この実装では、UUIDネームスペースは、入力名と連結されたバイトの文字列に変換され、MD5でハッシュされ、UUIDの128ビットになります。次に、バージョンとバージョン情報を正確に再現するために一部のビットを書き直し、残りはそのままにします。



名前付けも入力名もUUIDに基づいて計算できないことを理解することが重要です。これは元に戻せない操作です。唯一の例外は、値の1つ（名前空間またはテキスト）が攻撃者にすでに知られている場合のブルートフォースです。



同じ入力で、バージョン3および5の生成されたUUIDは決定論的です。



バージョン4（PRNG）



最も単純な実装。



6ビットはバージョンとバリアント用に予約されていますが、まだ122ビットが残っています。このバージョンは、単に128のランダムビットを生成し、そのうちの6つをバージョンおよびバージョンデータに置き換えます。



このようなUUIDは、PRNG（疑似乱数ジェネレーター）の品質に完全に依存しています。アルゴリズムが単純すぎる場合、または初期値がない場合は、識別子が繰り返される可能性が高くなります。



最新の言語では、UUIDバージョン4が最も頻繁に使用されます。



その実装は非常に簡単です。



  1. 128個のランダムビットを生成します。
  2. 正しいバージョンとバージョン情報でいくつかのビットを書き直してください：



    1. 7番目のビットと0x0FANDを取り、高ニブルをクリアします。次に、0x40ORを使用してバージョン4を割り当てます。
    2. 次に、9番目のバイトを取得し、cに対して0x3FAND演算を実行し、cに対して0x80OR演算を実行します。
  3. 128ビットを16進数に変換し、ハイフンを挿入します。


バージョン5（名前+ SHA-1-ハッシュ）



バージョン3との唯一の違いは、MD5の代わりにSHA-1ハッシュアルゴリズムを使用することです。このバージョンは、3番目のバージョンよりも優先されます（SHA-1> MD5）。



練習



UUIDの重要な利点の1つは、その一意性が中央の承認機関や異なるシステム間の調整に依存しないことです。近い将来、他の誰もこの値を生成しないという自信を持って、誰でもUUIDを作成できます。



これにより、1つのデータベースで異なる参加者によって作成された識別子を組み合わせたり、無視できる衝突確率でデータベース間で識別子を移動したりできます。



UUIDは、データベースのプライマリキー、アップロードされたファイルの一意の名前、任意のWebソースの一意の名前として使用できます。それらを生成するために中央の承認機関は必要ありません。しかし、これは両刃のソリューションです。コントローラがないため、生成されたUUIDを追跡することはできません。



対処する必要のある欠点がさらにいくつかあります。固有のランダム性はセキュリティを向上させますが、デバッグをより困難にします。また、状況によってはUUIDが冗長になる場合があります。合計サイズが128ビット未満のデータを一意に識別するために128ビットを使用することは意味がないとしましょう。



独自性



十分な時間があれば、値を繰り返すことができるように見えるかもしれません。特にバージョン4の場合。しかし実際にはそうではありません。 100年間で毎秒10億のUUIDを生成する場合、値の1つが繰り返される可能性は約50％になります。これは、PRNGが十分な量のエントロピー（真のランダム性）を提供するという事実を考慮したものです。そうでない場合、ダブルの確率が高くなります。より具体的な例：10兆のUUIDを生成した場合、2つの同一の値が表示される確率は0.00000006％です。



また、バージョン1の場合、クロックは3603でのみゼロにリセットされます。したがって、1583年までサービスを実行し続ける予定がない場合は、安全です。



ただし、ダブルが出現する可能性は残っており、一部のシステムではこれを考慮に入れようとします。ただし、ほとんどの場合、UUIDは完全に一意であると見なすことができます。さらに証拠が必要な場合は、実際の衝突確率を簡単に視覚化できます。


More articles:


All Articles