UUIDとは？「バージョンの確認方法」や「衝突確率」などを解説！

この記事では『UUID』について、

  • UUIDとは
  • UUIDのバージョン
  • UUIDの衝突確率(重複する確率)

などを分かりやすく説明するように心掛けています。ご参考になれば幸いです。

UUIDとは

UUIDはUniversally Unique Identifierの略で、意訳すると「世界中で重複のないユニークなID」です。

UUIDは128ビットの数値であり、この数値を16進数表記するのが一般的です。16進数表記する際には、先頭から4ビットごとに16進数の値(0～F)に変換し、一般的には「8桁-4桁-4桁-4桁-12桁(XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX)」の形式で表現します。UUIDの例として、「7598AD26-AC12-43CB-1501-A94946170BB8」といった形のIDが考えられます。

補足

  • UUIDは「ユーユーアイディー」と読みます。
  • UUIDが重複する確率はほぼゼロに等しく、一意である可能性が高いです(後ほど、UUIDが重複する確率について説明します)。

UUIDのバージョン

UUIDには、生成方法によって5つのバージョンが存在します。各バージョンには独自の特徴があり、用途に応じて選ぶことができます。多くの場合、ランダム生成のバージョン4が使用されます。

UUIDのバージョン

  • バージョン1(時刻とMACアドレスに基づく)
    • 生成時刻とMACアドレスを組み合わせてUUIDを生成します。
    • MACアドレスの情報を含むため、プライバシーの懸念から現代のアプリケーションでの使用は推奨されていません。
  • バージョン2(DCE Securityに基づく)
    • MACアドレスと生成時刻に加えて、POSIXのユーザーIDやグループIDの情報を追加してUUIDを生成します。
    • 主にDCE(Distributed Computing Environment)のセキュリティ上の要求から生まれました。
  • バージョン3(名前ベースのMD5ハッシュ)
    • 名前空間(例: URL, オブジェクト識別子, DNS名)と名前(文字列)からMD5ハッシュを用いてUUIDを生成します。
    • MD5は古いハッシュ関数であるため、バージョン3の使用は推奨されていません。
  • バージョン4(乱数に基づく)
    • 乱数に基づいてUUIDを生成します。
    • 最も広く使用されており、特定の情報に依存せずランダムに生成されるため、衝突のリスクが非常に低いです。
  • バージョン5(名前ベースのSHA-1ハッシュ)
    • 名前空間(例: URL, オブジェクト識別子, DNS名)と名前(文字列)からSHA-1ハッシュを用いてUUIDを生成します。
    • バージョン3のような名前ベースのUUIDの生成方法を安全なハッシュ関数であるSHA-1を使用して改良したものです。

また、UUIDを見るとバージョンが分かります。以下の赤字の箇所(UUIDの13番目の文字)がバージョン番号です。

UUIDの形式

XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX

例えば、「7598AD26-AC12-43CB-1501-A94946170BB8」のUUIDの場合、13番目の文字は「4」なので、このUUIDのバージョンは4です。

UUIDの衝突確率(重複する確率)

UUIDは「世界中で重複のないユニークなID」と説明しましたが、UUIDは基本的にはランダムな値なので、重複する可能性はゼロではありません(限りなくゼロに近い)。

以下に、UUIDの衝突確率を示す極端な事例を紹介します。

UUIDの衝突確率を示す極端な事例

  • 約86年間、毎秒10億個のUUIDを生成し続ける(その期間で生成されるUUIDの総数は約270京個)
  • その後、1つのUUIDを生成する
  • その生成したUUID が過去のUUIDと衝突する確率が50％

このような極端なシチュエーションは現実的でないことから、日常的な使用においてはUUIDの衝突はほとんど考えられないと言えます。

UUIDの衝突確率(重複する確率)の計算

UUIDの衝突確率の計算には、一般的に「誕生日の逆説(誕生日のパラドックス)」に基づくアプローチが用いられます。このアプローチに基づくと、UUIDの衝突確率\(p\)は以下のように近似的に計算できます。

\begin{eqnarray}
p{\;}{\approx}{\;}1-e^{-\frac{n^2}{2m}}
\end{eqnarray}
・\(p\)：衝突確率
・\(n\)：生成するUUIDの数
・\(m\)：UUIDの全通り
・\(e\)：自然対数の底(約2.71828)

128ビットで表現できるUUIDの全通りmは「2128」通りあります(バージョン4のUUIDは、6ビットがバージョン情報として固定されているため、実際のランダムなビット数は122ビットとなります。したがって、UUIDの全通りmは「2122」通りとなります)。

ここでは、バージョン4を想定して、mに「2122」を代入し、nに「270京(2.7×1018)」を代入すると、以下に示すように、衝突確率が約50％になります。

\begin{eqnarray}
p{\;}{\approx}{\;}1-e^{-\frac{(2.7×10^{18})^2}{2×2^{122}}}{\;}{\approx}{\;}50{\mathrm{[{\%}]}}
\end{eqnarray}

本記事のまとめ

この記事では『UUID』について、以下の内容を説明しました。

  • UUIDとは
  • UUIDのバージョン
  • UUIDの衝突確率(重複する確率)

お読み頂きありがとうございました。