UUIDじゃ物足りない？宇宙規模で絶対に重複しない「Cosmologically Unique ID」の世界

UUID（Universally Unique Identifier）のさらに上を行く、宇宙規模で一意性が保証される「Cosmologically Unique ID」という概念についてのトピックです。究極の識別子を求めるエンジニアに向けた、一意性の極致に関する議論を指しています。

ベッキー・チェンバースの素敵な小説『銀河、そしてその地上の光（the galaxy, and the ground within）』の281ページを読み終えたところなんだけど、こんなメッセージヘッダーがあるんだ。

  受信メッセージ
  暗号化：0
  送信元：GC交通局 --- ゴラ系（パス：487-45411-479-4）
  送信先：オーリ・オ・ウル（パス：5787-598-66）
  件名：緊急アップデート

いやあ、このシリーズ最高だわ。この多種族宇宙には、中央で合意されたパスアドレッシングシステムがあるみたいだね。

素晴らしい洞察と可視化だね！自分も「妥当な範囲で最小のランダムな識別子を使う」というアイデアを中心にデータベースを構築しているよ。それがユニバーサルな通信における唯一の『ゴールデンレコード』だと思っているから。大規模な身体性基礎モデルを備えた潜在空間の収束特性でもあれば別だけど。科学データ管理や図書館学のコミュニティで、この価値が過小評価されているのは不思議だね。今、巨大な組織が必要としている問題の多くは、より優れた識別子があれば解決できたはず。自分にとって『テセウスの船』の問いは、外的な（ランダム/名前付き）識別子 vs 内的な（ハッシュ/埋め込み）識別子の問題なんだ。

この分析はちょっとフェアじゃないかな。UUIDスキームを設計する際には局所性（つまり光速）を考慮しているのに、衝突確率の計算ではそれを無視している。衝突が問題になるのは、生成されたUUID同士が、生成後に実際に因果的な接触を持った場合だけだよね。だからUUIDのツリー構造を設計するときに局所性を考慮するのと同じで、実際の衝突確率を計算するときもそれを考慮に入れる必要がある。誕生日パラドックスをそのまま適用するのは、局所性を無視しているから不適切なんだ。ちゃんとランダムUUIDの必要サイズを計算すれば、記事にある約800ビットよりずっと小さくなるはず。計算したわけじゃないけど、実際は256ビットもあれば十分なんじゃないかな。（こういうオタクっぽくて細かい指摘がちゃんと通じるHN、大好きだよ）

文脈は忘れちゃったけど、先日TwitterやDiscord、Instagram、Mastodonで使われているSnowflake IDについて学んだよ。タイムスタンプ＋ランダムの組み合わせは、IDサイズを抑えつつ妥当な特性を得られる良いトレードオフに思えるけど、記事で触れられていないのが意外だった（まあ「タイムスタンプ」は宇宙規模だとかなり曖昧なものになるんだろうけど）。ちょっとした思いつきだけど、Snowflakeのタイムスタンプから10ビット回収して、下位32ビットを乱数に使えば、毎秒40億個のIDを発行できるし、価値があるんじゃないかな。あと、トム・スコットがYouTubeの動画IDを11桁のBase64乱数だと解説している動画があるけど、公式のドキュメントは見当たらない。彼は利用可能なID数については言及しているけど、誕生日パラドックスによる衝突までは考慮してないと思う。

アドレス可能な対象の総数をもっと現実的に見積もるなら、何かをアドレス可能にするためには、そのアドレスが少なくとも一度はどこかに保存される必要があることを考慮すべきだね。もし1ビットの情報を保存するのに少なくともNpb個の粒子が必要なら、アドレスのビット数が増えるにつれて、アドレス可能な対象の数は減っていくはず。アドレス可能な対象の数をNthgとして、1アドレスあたりの平均ビット数がNb = f(Nthg)で増えると仮定しよう。そうすると、アドレス可能な対象の最大数は、Nthg = Np / (Npb * f(Nthg))を満たす数になる。ここでNpは宇宙の全粒子数だよ。

分散型の世界から一言。これらのID割り当てや親ノードの選択には、元記事では議論されていない『敵対的/協力的』なダイナミクスがあるんだ。少数の協力的なノードに新しいIDを割り当てさせることで、増加を線形未満に抑えられる可能性もあると思う。逆に、IDを割り当てる権利を持つことは強力な力になる。バランスを考えると、正解はゼロ知識証明（ZK）を使った検証可能なランダム関数（例えば日点ベースの変換と『公平な』ランダム選択の証明の組み合わせ）のようなものだろうね。その場合、800ビットもあれば十分すぎるほどだと思う。エポックベースの可変長にすることもできて、例えば今後10億年くらいはID空間の1/256だけを使う（最初のビットを0に強制する）とかね。

衝突を避けるためのエントロピー源としてCSPRNG（暗号論的擬似乱数生成器）を指定するのは正しくないな。CSPRNGは次の数字の予測を困難にする（AESを破るレベルの難易度にする）だけで、エントロピーを追加するわけじゃない。それに、ユニークなシードを与えないと同じ数字を出力してしまう。著者が、たった一台のマシンで宇宙規模のリストを一度に生成することを提案しているなら別だけど。あと、全部1とか全部0のIDを『禁止』するのはナンセンスだね。正しく生成しているなら、それらも他の数字と同じように有効でユニークなんだから。まあ、設定可能なビットが全部1のUUIDを引いちゃったら、宝くじでも買いに行くことを勧めるけど。

明らかな解決策は、IPアドレスのようなシステムだよね。すべてのシステムが「宇宙.銀河.領域.星系」みたいなアドレスを持って、その星系内を論理的な方法で細分化していく。そうすれば、宇宙船でもデータでも特定のシステムに論理的なルートで送れるようになる。各システムがアドレスの割り当て方法を決めればいい。ほとんどのシステムには誰もいないだろうから、NASAやレジストラのような機関がブロックを割り当てて、惑星のような大きなものにアドレスを振るだけでいいんだ。

この分析に隠された実用的な結論：人間スケールにおいて、本当のトレードオフは「一意性 vs 衝突リスク」ではなく、「一意性 vs 可読性」なんだよね。純粋なランダムIDは理論的には最適だけど、運用上は最悪だ。午前3時に何かが壊れたとき、そのIDがどこから来たのかを「ささやいて」ほしいだろ？だからULIDはタイムスタンプを埋め込むし、DNSは階層構造だし、gitのハッシュはコンテンツアドレス指定なんだ。衝突確率のわずかな増加と引き換えに、デバッグのしやすさを手に入れているわけ。決定論的なスキームが最悪ケースで線形増加を超えられないという記事の証明はエレガントだけど、人間が関わるスケールでは関係ない。生成するのはせいぜい10の12乗個であって、10の120乗個じゃないからね。面白い設計領域はその中間にある。一意性のためのランダムさと、人間のための構造を兼ね備えた場所だよ。

PostgreSQLの世界では、新しいプロジェクトだとuuid_generate_v7()（タイムスタンプ順）がデフォルトの選択肢になりつつあるね。ソート可能であることはB-treeインデックスのパフォーマンスにおいてゲームチェンジャーだよ。実質タダで時系列順に並べられるからね。実用的なメリットとしては、主キーを見るだけでレコードがいつ作成されたか大体わかるし、新規インサートが近くに集まるからインデックスがキャッシュに残りやすい。それに、カラムを追加しなくても作成時間で範囲クエリが打てるようになるんだ。