UUIDが(確認すらしなくても)ほとんど衝突しない理由

標準的なランダムUUIDは、次に使える識別子を割り当てる中央機関も、既に使用中の識別子のリストと照合するチェックも一切ない状態で、まったく調整されていない任意の数のシステムによって、それぞれ独立に生成されます。それにもかかわらず、衝突は実務上、決して起こらないものとして扱われています。これは調整ではなく確率だけに完全に依存した、本当に大胆な主張であり、なぜそれが成り立つのかを理解するには、はるかに有名なあるパズル — 一つの部屋に何人集まれば、そのうちの2人が誕生日を共有する可能性が高くなるか — を説明するのと同じ、直感に反する数学の一片が必要になります。

古典的な誕生日のパラドックスは、一つの部屋に何人集まれば、そのうちの2人が誕生日を共有する確率が50パーセントを超えるかを問うもので、その答え — 365通りの誕生日に対してわずか23人 — はほとんどの人を驚かせます。直感的には365に近い数字を予想してしまうからです。本当の答えがこれほど小さくなる理由は、関係する比較が「特定の誰かが自分と誕生日を共有しているか」ではなく、「部屋にいるすべてのペアのうち、いずれかのペアが誕生日を共有しているか」だからです。可能なペアの数は人数よりもはるかに速く増えていきます。23人であれば、すでに253通りの異なるペアが存在し、それぞれが独立した一致のチャンスとなるからです。この正確な数学的パターン — 比較の機会の数が2次関数的に増える一方で、要素の数は線形にしか増えない — は誕生日問題と呼ばれ、固定された空間から取り出されたランダムな値を重複についてチェックするあらゆる状況に直接当てはまります。UUIDもまさにその一例です。

標準的なランダムUUID(バージョン4)は、122ビット分の本当にランダムなビットからなる空間から値を取り出します。128ビットの合計のうち、ごく一部はバージョンを識別するために形式の仕様そのものによって固定されています。つまり、可能な値の総数は2の122乗であり、これはほとんど理解不能なほど巨大な数です。365日の例で使ったのと同じ誕生日のパラドックスの推論を、このはるかに大きな空間にスケールアップして当てはめると、衝突が起こりやすくなる点が求まります。おおよそ270京個(2.7×10¹⁸個)のUUIDを生成して初めて、いずれか2つが衝突する確率が50パーセント前後まで上昇します。規模感を掴むために言えば、これは地球上のすべての浜辺にある砂粒の推定数よりも多いUUIDの数です。一つのシステム、あるいは組み合わせた非常に多くのシステムが、現実的などんな速度でUUIDを生成し続けたとしても、その閾値に近づくまでには宇宙の年齢をはるかに超える時間がかかります。これこそが、実務上UUIDの衝突をチェックする必要がないものとして扱うことの、実際の数学的根拠です。

UUIDバージョン7は、より最近になって、おおよそ時系列順にソートされる識別子を生成する目的で標準化されたもので、バージョン4のように値全体をランダムなデータで埋める代わりに、識別子の先頭ビットにミリ秒精度のタイムスタンプを配置することでそれを実現しています。値の一部が今やランダムではなく予測可能になっているのだから、衝突耐性の保証が弱まるのではないかと思われるかもしれません。しかし残りのビットは以前とまったく同じ量の、本当にランダムなデータで埋められ続けており、まったく同じミリ秒内に生成された2つのUUIDでさえ、衝突するにはランダムな残りの部分がぴったり一致する必要があるため、現実的などんな生成速度においても、実用上の衝突耐性はバージョン4と同程度のまま保たれます。v7が実際に変えているのは、まったく別の無関係な性質 — ソート順序 — であって、ここで論じている衝突の数学にはまったく手を触れていません。この2つは概念として分けて考える価値があります。一意性はランダムな空間の純粋な広さから来るものであり、ソート可能性はタイムスタンプが値の中のどこに位置するかから来るものです。

衝突確率が、見せかけだけでなく本当に無視できるほど小さいため、システムは完全に独立して一意な識別子を生成できます。ネットワーク接続なしにオフラインで動作するモバイルアプリ、ミリ秒単位で起動して消えるサーバーレス関数、同時に実行される数千の並列マイクロサービスインスタンスなど、互いにまったく調整することなく、すでに発行された識別子を追跡する中央のレジストリも持たないまま、それでも「この中のどの2つの識別子も決して衝突しない」という、数学的に裏付けられた期待を持つことができます。これはまさに、共有の調整機関がすべてを遅くすることなしには、中央発行の連番識別子が決して提供できなかった性質であり、どんな調整の手順も追いつけないような速度で識別子を必要とする分散システムにおいて、ランダムなUUIDが既定の選択になった理由のすべてです。