by and for engineers

DHT アルゴリズムのKademlia まとめ

DHT: Distributed Hash Table (分散ハッシュテーブル)

ハッシュテーブルを複数のノードで管理するアルゴリズムです。P2Pで良く使われる技術です。

アルゴリズム

  • Chord: 円状スキップリスト
  • CAN: N次元トーラス
  • Kademlia, P-Grid: 2分木
  • Tapestry, Pastry: Plaxtonアルゴリズム

Kademlia

間違いが多々あると思うので，原文を参照してください。

Kademlia: A Peer-to-peer Information System Based on the XOR Metric

Kadmlia 論文のまとめ

  • ノードが機能停止した場合に，自主的にネットワークが回復するためのアルゴリズム
  • ネットワーク内に流れるメッセージを最小限にする。
  • あるノードが1時間後にネットワーク内に存在する確率を1/2と仮定
  • ノードにランダムな ID (160-bit) を振る
  • Key と Node ID は 160bit の数字で管理
  • あるノードから別のノードへの問い合わせは O(log N)
  • 探索範囲は 1/n で減少
  • 近いノードへの探索は密で，遠いノードへの探索ほど疎な探索になる。
  • lookup など通常のメッセージのやり取りでネットワークを維持する事が出来る。
  • ネットワークから離脱する際に特別な処理は必要ない。
  • Node ID と IP:UDP-Port の組み合わせで問い合わせする。
  • ノード間の距離は XOR で定義される。
  • 2分木構造になり，距離の近いノードが同じ枝に存在する可能性が高い。

k-bucket

  • 「自ノードからの距離」が [ 2^i , 2^(i+1) ) のノードのリスト
  • 一つの i につきノードの IP アドレスを最大で k 個保持 (k = 20)
  • k-bucket のノードは古い順に並べる
  • k-bucket が一杯の場合，先頭 (一番古いノード) の生存確認を行う。死んでいたらそのノードを外し，新しいノードを最後尾に追加する。生きていたら，そのノードを最後尾に移動する。(k-bucket への新規追加はしない。)
  • 探索は開始ノードの k-bucket から目的の Key に一番近い Node ID を返す (反復)