ハクソク

世界を動かす技術を、日本語で。

宇宙論的にユニークなID

96日前原文(jasonfantl.com)

概要

  • 宇宙規模での一意なID割り当て問題 の重要性
  • ランダム方式と決定論的方式 の比較とその限界
  • ID衝突の確率計算 と物理的上限
  • Deweyスキームなど階層型ID割り当て法 の特徴
  • 用途・規模ごとの現実的なID長の選択指針

宇宙規模でのユニークID割り当て問題

  • 人類の拡張 に伴い、全てのデバイス・物体に 一意なID が必須
  • 製造・物流・通信・セキュリティ など、IDの利用範囲の広がり
  • スケール拡大 によるID数の爆発的増加
    • ロボット群、部品、コンテナ等、 兆単位以上 の管理対象

ランダムID方式

  • ランダムな数値 を各デバイスが自律的にIDとして選択
    • 中央管理不要、いつでもどこでも割り当て可能
  • 衝突確率 はIDビット長で制御可能
    • 衝突確率を 事実上ゼロ まで減少可能
  • UUID（122ビット） では、約$2^{61}$個生成で衝突が期待される
  • 宇宙規模 での上限計算
    • 全宇宙を計算機化 した場合、$10^{120}$回のID生成が可能
    • 衝突期待値0.5 のとき、必要なID空間は約$10^{240}$（798ビット）
  • 現実的な上限例
    • 全宇宙の原子数（$10^{80}$） ：532ビット
    • 1gナノボット全宇宙変換（$1.5\times10^{56}$） ：372ビット
    • UUID（122ビット） ：現行標準
  • 真のランダム性 が重要
    • ハードウェア乱数やCSPRNG推奨
    • 既知の疑似乱数初期値や単純パターン のIDは禁止推奨

決定論的ID方式

  • 中央カウンタ方式
    • 一元管理で 連番ID を発行
    • 最小限のID長（対数的増加） を実現
    • アクセス性・地理的制約 が最大の課題
  • 階層型分散方式（Deweyスキーム）
    • 親ID.子カウンタ の形式（例：13.5.3）
    • どのノードも新規ID発行可能、分散性・拡張性
    • ID長は割り当てツリーの形に依存
      • 広く浅いツリー ：対数的成長
      • 細長いチェーン ：線形成長
  • バイナリツリー方式
    • 各ノードが無限にIDを割り当てられる構造
    • 最悪・平均ケースでID長は線形に成長
    • Dewey方式の方が割り当て効率が良い場合が多い

ID方式選択の指針

  • 確率的安全性 で十分な場合
    • ランダムID方式 がシンプルかつ実用的
    • 必要なビット数は 用途・規模に応じて 選択
  • 絶対的な一意性 が必要な場合
    • 決定論的・階層型方式 を採用
    • 分散環境・拡張性 を考慮した設計が重要
  • ID長・生成方式 は システム要件・将来予測 に基づき決定

まとめ

  • IDの一意性確保 は、宇宙規模でも現実的な解決策が存在
  • ランダム方式 は十分なビット数があれば実用上問題なし
  • 決定論的方式 は絶対的保証が必要な場合に有効
  • 用途・規模に適した方式選択 と、 真のランダム性確保 が重要

Hackerたちの意見

ベッキー・チェンバースの素敵な「銀河とその地面」を281ページ過ぎたところだよ。メッセージ暗号化：0 送信元：GCトランジットオーソリティ --- ゴラシステム（パス：487-45411-479-4） 受信先：オーリ・オート・ウルー（パス：5787-598-66） 件名：緊急アップデート このシリーズ大好き！この多種族の宇宙には、中央で合意されたパスアドレスシステムがあるみたいだね。

└

この本の中で、みんなでチーズの概念がどれだけ恐ろしいか話しているシーンが大好き！他の四重奏も素晴らしいけど、2冊目の「閉じられた共通軌道」が個人的にはMVPだね。

└

ヴァーナー・ヴィンジの「深淵の火」をチェックすると、銀河間通信がどのようにラベル付けされるか、ルートなどの面白い例がもっと見られるよ。

すごくいい洞察とビジュアルだね！最小限のランダム識別子を使うアイデアをもとにデータベースを作ったんだけど、それが普遍的なコミュニケーションのための唯一の「ゴールデンディスク」だと思う。大きな基盤モデルの潜在空間の収束特性を除いてはね。科学データ管理や図書館科学のコミュニティではあまり評価されてないのが不思議だし、今必要な大規模な組織の問題も、もっと良い識別子があれば解決できたかもしれない。私にとってテセウスの船の問題は、外部（ランダム/名前付き）識別子と内部（ハッシュ/埋め込み）識別子の違いについてなんだ。 https://triblespace.github.io/triblespace-rs/deep-dive/ident... https://triblespace.github.io/triblespace-rs/deep-dive/tribl...

ちょっと脱線するけど、UUIDが過剰に使われてるケースが多いと思う。人々はそれをデータを保存するために乱用して、実質的に「話すID」や「マルチカラムインデックス」にしてしまってる。

└

ソート可能なキー（例えば挿入順）や何らかのメトリック/記述子が必要な場合を除いて、UUIDが過剰に使われたり不適切になる理由がよくわからないな。

面白い読み物だった！決定論的なスキームの一つの利点は、出所や系譜を含むことだね。歴史をたどって元のID提供者まで「追跡」できる。どれだけの情報があれば、Nノード/オブジェクトのネットワーク上で任意の系譜ツリー/グラフを表現できるのか、ちょっと気になるな。（コメントを考えながら：最悪の場合は線形チェーンだとして、完全な系譜の情報がIDでアクセス可能だと仮定すると、O(N x id_size)になるから、かなり悪いね。でも「最良の場合」（どのノードも根からlog(N)ステップの深さ）だと、global_id_size = log(N) x local_id_sizeが大体の最適限界かな？つまり、global_idのサイズはlog(N)^2として成長するってこと？399ビットの数から、系譜を持つとしたら、global_id_sizeの下限は（400ビット）^2 ≈ 20 kBになるのかな（順序付きローカルIDの系譜情報を持つため、ローカルの共有知識に対してではなく）。

└

BlueSkyのソーシャルネットワークの基盤となるATProtoも似たような感じだね。コンテンツアドレスのDAGを使ってる。各「投稿」にはCIDがあって、これはデータの暗号ハッシュなんだ。投稿の所有権を「証明」するために、木の根ハッシュまで遡れる証人ハッシュが送られるんだよ。根キーで署名されてるから、データが「これがデータだよ、確認したければこれがMSTだよ」って言ってるみたいで面白いね。

└

二つのフレームの仕方があるね。プロヴェナンスはDAGだから、トポロジカルソートで部分順序を無料で得られる。それを互換性のある全順序に拡張できる。ノードのプロヴェナンスはその順序だけだよ。このオブジェクトから最初のNの連続自然数へのマッピングは、最小完全ハッシュ関数でもあって、n log nのオーバーヘッドがあるんだ。系譜を追跡するために木をナビゲートできないけど、等価性は同じ系譜を意味するよ。あるいは、もう少しビットを使って全履歴を追跡することもできるけど、2Nになるかな、もしそれが二分木ならね。実際には、決定論的IDは通常、log nを得るために2^-Nの衝突リスクを受け入れるんだ。

この分析はちょっと公平じゃないね。UUIDスキームを設計する際には局所性（光の速さ）を考慮しているけど、衝突の確率を計算する時には考慮していない。衝突は、生成された後に衝突するUUIDが実際に因果的に接触する場合にのみ重要だから。だから、UUIDツリーを設計する時には局所性を考慮しなきゃいけないし、実際の局所的衝突の確率を計算する時にも考慮しなきゃいけない。だから、バースデーパラドックスの単純な適用は局所性を無視しているから適用できない。実際に必要なランダムUUIDのサイズの公平な計算は、記事が言ってる約800ビットよりずっと小さくなるはず。計算はしてないけど、実際の答えが256ビットを超えるとは思えないな。ここで言いたいのは、HNが大好きだってこと。あんなにオタクっぽくて学究的なコメントが、ちゃんと的を射てる場所はほんとに少ないからね。 :-)

└

時間と場所の両方を考慮しなきゃね。プロトンが崩壊して物質が存在しなくなるまで、あと10^56ナノ秒しかないんだから。

└

定義が変わってきてるのかもしれないけど、私の経験では「on point」ってのは「本当に良い」って意味の賛同を示すことが多いんだよね。だから、あなたが言いたいのは「話題に沿ってる」とかそんな感じかな。ペダンティック万歳。

└

相対論的な速度で動く物体によって生成されたIDも考慮されるのかな？他の惑星に1年かけて旅行して、1万年遅れて到着して、IDの衝突がたくさんあったら大変だよね。

文脈は忘れちゃったけど、先日、TwitterやDiscord、Instagram、Mastodonで使われてるらしいSnowflake IDについても学んだんだ。タイムスタンプ＋ランダムって、IDのサイズを減らしつつ合理的な特性を得るための良いトレードオフになりそうだね。この記事がそこを掘り下げてないのが意外だな（でも、普遍的なスケールでの「タイムスタンプ」はもっと曖昧なんだろうね）。ちょっと思いつきだけど、Snowflakeのタイムスタンプから10ビットを取り戻して、下位32ビットをランダムナンバーに使うのはどうかな。1秒ごとに40億のIDが作れるよ。Tom Scottの動画があって、YouTubeの動画IDは11桁のベース64のランダムナンバーだって説明してるけど、それに関する公式なドキュメントは見当たらないな。最後に、どれだけのIDが利用可能か言ってるけど、バースデーパラドックスによる衝突を考慮してないと思う。

└

これ、他の人が興味あるなら、広く使われてるBSON IDにも似てるね。

└

宇宙全体がタイムスタンプを作成するための単一の時計に合意するのは、めちゃくちゃ難しそうだね。多分不可能？

└

[1]: https://en.wikipedia.org/wiki/Snowflake_ID これって、バージョン1のUUIDと同じ仕組みじゃない？ビット数が半分になってるだけで。128ビットもIDに使いたくなかったんだろうね。

現実からわかることは、人々が複数の匿名IDや自己選択したハンドルを持つことを好むってこと。これが完全に決定論的な生成スキームを無意味にしちゃうんだよね。また、ネットワークルーティングには複数のアドレスを持つオブジェクトが必要なんだ。物理的な側面も面白いよね。量子粒子はファンジビリティが必要だから、原子をドックスするとシステムの挙動が変わっちゃうんだ。

└

現実からわかるのは、人々は複数の匿名IDを持つことを好むってこと。何も「デバイス」から複数のIDをリクエストするのを止めるものはないよね！

最終的には、各惑星がそれぞれのローカルアドレスを持って、空の大きなルーターがNATを行うような感じになるんじゃないかな。各太陽系にはルーターがあって、みたいな。

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

私は宇宙論に関するすべてが大好きなんだけど、いつも矛盾する2つの概念に悩まされてるんだよね（私にとっては）。 - 無限：学校で、私たちの宇宙は無限だって習った。 - でも、こういう上限を持つ計算をよくするよね：10^240。これは大きな数だけど、無限ではないんだよね。10^240+1、10^240+2…だから、1. 無限なら、なんで上限の計算をするの？ 2. 限界があるなら、その外には何があるの？めちゃくちゃパラドックスだよ。