要約

  • CANはキーをハッシュし、多次元の論理的な直交座標空間の一点へ写像する。原論文は、この空間が物理的な座標系とは無関係だと明記している。
  • 点を含む領域をノードが「所有する」とは、その時点で格納と経路制御を担当するという意味である。参加、離脱、障害によって担当は移る。
  • 現在の領域担当者へ到達できたことは、現在のオーバーレイ状態についての証拠にすぎない。実在場所、鮮度、著者、権限、安全性、恒久的な所有を単独では証明しない。

どこにもない点

A Scalable Content-Addressable Networkには、発明の意味を決める短い断り書きがある。CANの空間は、d次元のトーラスとして構成された論理的な直交座標系であり、物理的な座標系とは何の関係もない。

均一なハッシュ関数がキーを点Pへ写す。座標空間全体は動的に領域へ分割され、Pを含む領域のノードがキーと値の組を保持する。検索時には同じキーから同じ点を求め、そこへ向けてメッセージを転送する。

この座標はデータが世界のどこにあるかを表さない。国、ASN、IPアドレス、ラック、遅延のどれも符号化していない。現在の参加者と分割状態のもとで、誰がこの点を処理するかを決めるだけである。

2001年のSIGCOMM論文は、Sylvia Ratnasamy、Paul Francis、Mark Handley、Richard Karp、Scott Shenkerの共著だ。本稿はRatnasamyを人物として扱うが、CANを一人の発明にはしない。通常の検索と領域分割を中央調整者に依存させず、ハッシュ表に近い機能を分散して提供することが共同の提案だった。

「所有」は、その時点の担当だった

論文は各ノードが一つの領域を“owns”と書く。プロトコル上の意味は、その領域へ写された組を保存し、隣接領域の状態を持ち、問い合わせに応答するか次へ送ることだ。データの財産権は移らない。値を誰が作ったか、正しいか、利用を許されているかも、この言葉からは分からない。

経路制御に必要なのは近傍情報である。領域同士が接していれば、そのノード同士は隣接ノードになる。メッセージは宛先座標に最も近い隣接ノードへ渡される。均等分割を仮定すると、ノード当たりの近傍は2d、平均経路長は(d/4)(n^(1/d))となる。

小さな状態だけで進めることが、拡張性の源だった。同時に、証拠の範囲もそこまでである。CANの一ホップは論理空間での前進であり、IPの一ホップではない。座標上の隣人が、基盤ネットワークでは遠く離れていることも論文は指摘している。

参加は、近くの境界だけを引き直した

新しいノードはまずブートストラップ先を見つけ、ランダムな点を選ぶ。JOIN要求は、その点を現在担当するノードまで運ばれる。受信側は自分の領域を半分に分け、一方を残し、もう一方と対応するキー・値を新規ノードへ渡す。周辺のノードは近傍表を更新する。

世界全体の台帳を書き換えるのではなく、参加に必要な部分だけが変わる。次の境界は将来の参加や離脱と、そのとき観測できる状態によって決まる。将来の決定を局所に残す設計が、動く仕組みとして現れている。

分割前にノードAが担当した座標を、分割後はBが担当することがある。データが地理的に別の緯度へ移ったのでも、著者が変わったのでもない。保存し応答する責任の割り当てが変わっただけだ。

計画的な離脱なら、領域とキー・値データベースを隣接ノードへ引き渡せる。形が合えば結合し、合わなければ一つのノードが一時的に複数領域を管理する。「この点はBのものだ」という記録には、時刻、参加状態、分割または引き渡しの証跡が欠かせない。

地図の穴が埋まっても、値は戻らない

予期しない障害では、二種類の復旧が分かれる。隣接ノードが故障領域を引き受ければ、座標空間の被覆は回復する。しかし、故障ノードが保持していたキーと値は、データ保持者が再度投入するまで失われたままだと論文は述べる。

経路が直っても、内容は欠けている場合がある。「全座標に担当者がいる」ことだけを監視すれば、トポロジーの復旧をデータ継続性と誤認する。

近傍情報はソフトステートで、即時更新と定期更新によって維持された。隣り合う複数ノードが同時に落ちると、周囲に食い違う見え方が生じ得る。そこで範囲を広げながら探索し、必要な近傍を再発見する。完全な中央地図の命令ではなく、観測可能な局所動作の連鎖が回復を生む。

論文は複数の「reality」も検討した。同じキーを独立した複数の座標空間へ置き、複製を持たせる考えだ。複製は一つの障害への耐性を高めるが、どのコピーが原本か、正しいか、許可されたものかを決めない。配置と更新の証拠はrealityごとに要る。

検索は証明書ではない

CANのインターフェースは簡潔だからこそ、役割を重ねて見やすい。キーの発行者、現在の格納ノード、中継ノード、物理ホストの運営者、業務判断を認める主体は、それぞれ別であり得る。

オーバーレイが答えるのは限定された問いだ。このハッシュ、この分割、この近傍状態なら、どの領域が点を担当し、そのノードが何を返すか。著者を証明するには署名などが要る。鮮度には版、時刻、有効期限が要る。返された値を権限へ変えるには、別の方針が要る。

著者たちは安全性の空白を隠していない。扱ったのは拡張可能な経路制御と索引であり、サービス妨害攻撃に耐える安全なCANは今後の課題とされた。悪意あるノードはクライアント、サーバー、ルーターのいずれにもなれる。中央索引をなくすことと、信頼判断をなくすことは同じではない。

共通仕様を小さく保つ意味がここにある。ハッシュ、領域、近傍、貪欲転送は調整の土台になる。署名、認可、版管理、競合処理、保存、救済は、それを決める主体が見える層に置くべきだ。「検索成功」にすべてを暗黙に含めれば、仕組みは完成するのではなく、監査できなくなる。

地図の遺産は、境界を守ることにある

Berkeleyは現在、Sylvia Ratnasamyをネットワーク化されたシステムの設計と実装を研究する計算機科学教授として紹介している。2026年1月には、ネットワークとネットワークシステムへの貢献により2025年のACM Fellowsに選ばれたと発表し、CANを中央レジストリなしでデータを見つける画期的な研究として挙げた。

ただし、評価が証拠の範囲を広げるわけではない。原論文は主にシミュレーションで性質を示し、展開上の選択と攻撃耐性を未解決として残した。後世のP2PやクラウドがすべてCANから派生したとも証明していない。

残る教訓はもっと正確だ。分散システムは、論理地図を地理に見せかけずに協調できる。現在の保管者を指名しても、所有者に仕立てる必要はない。経路を直しても、内容が戻ったふりをしなくてよい。いつ、どの分割のもとで、誰が何を担当したか。その証跡を残すことが、地図を地図の役割にとどめる。

出典