分散ハッシュテーブル
概要
分散ハッシュテーブル(Distributed Hash Table:DHT)
ハッシュテーブルを複数のノードで管理する方法
Key-Value型
P2Pシステムで効率的なオブジェクト発見(データ探索)ができる方法
単一Keyから高速にデータの探索ができる
多くは$ O(\log{N})
メリット
負荷の軽減ができる
P2Pで高速な探索ができる
データ数が増えてもスケールできる
単一の検索機構が存在しないため機能不全に陥らない
仕組み
データのファイル名のハッシュ値をキー情報としてデータの格納先を検索する
データを保存するノードの場所情報（IPアドレスなど）のハッシュ値をキーとしてデータの検索時に役立てる
簡単なイメージとしては以下
検索したいデータファイル名のハッシュ値でクエリを投げる
そのクエリを受け取ったノードが探索をする
IPアドレスのハッシュ値が、クエリの値に近いノードにクエリを飛ばす
ただし、どのような探索を行うかは、プロトコルによって千差万別なので、細かい仕組みその実装によること
クエリを受けたノードがデータを返す
詳細
DHTの実現に重要な要素
1. キーとノードのマッピング
2. ノードがもつ経路表の設計
1. キーとノードのマッピング
全てのキーはどこかのノードに責任がある
全てのキーは必ずどこかのノードにマッピングされる
ノードの離脱・加入に対応して即座にマッピング更新を行う
一貫性を維持するため
consistent hashing(コンシステントハッシュ法)を用いる
https://gyazo.com/9e195a4a83ff4f520f3f4b85f4123cd8
キーとノードを同一の値域にマッピングする方法
SHA-1やMD5などがハッシュ関数として用いられる
キーに対応したノードは、その値域上で最も近い値をもつものにする（図の(b)）
ノードの加入と離脱の影響は近隣ノードのみに抑えられる（図の(c)）
距離の計算方法は様々な方法がある
Pastry, Tapestyは共通プレフィクスの長さ
CANは異なるビットの数
どんな距離設計をするかでDHTの仕組みは大きく変わる
2. ノードがもつ経路表の設計
キーがマップされているノードを探すための仕組み
目的のノードを見つけるためには、各ノードがある程度他のノードを知っている必要がある
経路表をもつことで実現
どのノードに問い合わせると、結果に近づくかが記述してある
経路表の構成方法
超立体型
バタフライネットワーク型
Pastry, Tapestry, Kademliaはツリー型
DHTシステムによって大きく変わる
代表的なアルゴリズム
CAN(2001)
N次トーラス
Tapestry, Pastry(2001)
Plaxton
二分木
リング状
Koorde(2004)
Chordの改良
Broose(2004)
KoordeとKademliaの改良
Skip Graph(2003)
DHTではないが、似たようなもの
応用例
ファイル共有ソフトで使用されている
BitTorrent
アルゴリズムはKademlia
プロトコルはKhashmir
BitComet
アルゴリズムはKademlia
プロトコルはBitTorrent互換
Vuze
アルゴリズムはKademlia
プロトコルは独自実装
LimeWire
アルゴリズムはKademlia
プロトコルはMojitoDHT
実装
libtorrent
C++/Python ライブラリ
Kademlia
BitTorrentプロトコルの実装に使用できる
OpenChord
Java で作られたプログラム
Chord
Overlay Weaver
Java で作られたツールキット
Chord, Kademlia, Koorde, Pastry, and Tapestry
実装まとめ
首藤一幸
参考文献
公式
論文
DHT : Pure Peer-to-Peerシステムのための基盤技術
筑波大学 阿部洋丈
DHTシステムの仕組みと性能と課題について
ライブドア 駒井秀一
スライド
分散ハッシュテーブル(DHT)
アライブドア 伊勢幸一
Web
分散ハッシュテーブル
Wikipedia