Windowsでレジストリなどを見ると、16進数を並べて波括弧で括った「GUID」（Globally Unique IDentifier）を見かけたことがあるだろう。

{f494760f-6668-4c35-952e-24635890c549}

GUIDは、128ビット（=16バイト）の整数値で、オブジェクトなどを識別する識別子（ID）として利用されている。識別子として有効な桁数は122ビットで、組み合わせとしては2の122乗、約5.3E+36で、日本式に書けば5.3澗と大きいために、ちゃんとした乱数で生成すると、システムの寿命の間には衝突しない数値として利用できる。どのぐらいかというと、衝突する確率が1%になるのに1秒間に1千万個のGUIDを生成させても1000年ぐらいかかる。1%の確率で衝突するのに必要な個数は3×10の17乗個（30京個）である。なので、たかだか数百万個ぐらい生成しても衝突する確率はゼロに近いまま。

なぜ、GUIDを使うのかというと、番号割り当てを集中管理しないで済ませたいからだ。他人が生成したものと衝突する確率がほとんどゼロなので、そのままインターネットでもユニークな数として利用できる。

GUIDは、Microsoftの用語だが、IETFのRFCにより定義されたUUID（Universally Unique IDentifier。RFC 4122。2025年）がある。混乱を防ぐため、これをRFC4122 UUIDと表記する。現在Microsoftで使われているGUIDは、このRFC4122 UUIDの一部である。というのもRFC 4122の策定にはMicrosoftも関わっているからだ。少なくとも現時点では、GUIDはRFC4122 UUIDであると言ってもよいわけだ。

GUIDやUUIDの始まりは、1980年台に遡る。当時存在したApollo Computer社（1989年にHP社に買収。以下Apollo社と略記）のDomainワークステーションのOS“AEGIS”（のちにDOMAIN/OSという名前になる）でLAN内でもユニークになるオブジェクトの識別子として64ビットの“UID”（Unique ID）が使われていた。これは、生成したときの時間と、個々のワークステーションに組み込まれたユニークな識別子（ノードID。ROMに記録されていた）を組み合わせたもの。

1980年台にUnix業界が揉めたとき（このあたりに関しては、過去記事「窓辺の小石(142) Unix in the Windows Machine」を参照してほしい）にできたOSF（Open Software Foundation）が、分散処理システム（DCE。Distributed Computing Environment）の開発に乗り出し、技術提案を募集した。そこに応募したのがApollo社だった。

同社の提案は、DCE/RPC（/Remote Procedure Call）のベースとなった。この提案ではUIDは128ビットに拡張されてUUID（Universally Unique IDentifier）と呼ばれており、それがDEC/RPCに入ったようだ。

マイクロソフトは、DEC/RPCの初期バージョンをWindows NTに移植。これはMS-RPCと呼ばれ、Windows NTの初期ドメインシステムに使われた。このときDCE/RPCのUUIDがWindowsに入ることになったわけだが、Microsoftは、これをGUIDと呼んだ。初期に使われたGUIDは、DCE/RPCのUUIDとは少し異なるものだったようだ。というのはRFC 4122 UUIDには「Microsoft Corporation backward compatibility」と、説明されるバリアント（後述）があるからだ。

こうして、GUIDは、Windowsのあちこちで使われるようになる。1992年のCOM（OLE2）ではオブジェクト（コンポーネント）の識別子として採用された。レジストリでよくみかけるGUIDは、COMの識別子であることが多い。

さて、GUIDやUUIDの中にはバリアントという情報があり、これがUUIDの形式を決めている。バリアントは可変長の情報で、RFC 4122 UUID（および現在のGUID）は2ビットを使う。このバリアントでは、さらに「バージョン番号」と呼ばれる情報として4ビットを使い生成方法を区別している。このため、割り当てに使えるビット数としては122ビットになる。

2の122乗個から乱数で1つを選んだとして、それが偶然、他のUUIDと一致する確率を計算するのには、「誕生日問題」と呼ばれる計算を使う。学校のクラスで誕生日が同じ人が1組以上存在するには、クラスに何人がいればいよいか（あるいはn人の中に誕生日が同じ人が存在する確率）を計算する方法だ。生成したUUIDが衝突する確率は、誕生日の数に相当するものをUUIDの数である2の122個として、衝突するのに必要なクラスの人数を計算する（図01)。

図01: UUIDの衝突確率や1%の確率で衝突が始まるまでの時間を求めてみた

今回のタイトルネタは、アーサー・C・クラークの「90億の神の御名」（The Nine Billion Names of God,1954）である。コンピュータを使って神の名となるアルファベットの組み合わせを出力する話。また、「誕生日」というキーワードからは、アーシュラ・K・ル＝グウィンの「世界の誕生日」（The Birthday of the World。同名の短編集が邦訳されている）もある。