アルゴリズム練習: Chord
分散システムを自分で設計・実装できるようになりたいので基本的な分散アルゴリズムを勉強したり実際に書いてみることにした。 教科書に従って書いていて、用語などの前提には触れずメモを残すだけなので読むの辛いと思う。
tl;dr
DHT(Distributed Hash Table)を実現する代表的なアルゴリズムであるChordを実装してみた。
DHTっていうのは構造化オーバーレイネットワークの1つで多数の分散したノード上にハッシュテーブル(set, get)を提供するシステムを指す。 Chordはそのようなサービスを提供するアルゴリズムの1つで、ノードのアドレスとデータのキーを同一のS1集合へ射影することで資源探索を行う。 またノード数Nに対してリソース提供ノードを確定するのに必要なノード数をO(logN) にするように経路表を維持している。
とりあえず実装したのはRendezvous, Location, Routingのロジック部分で実際の通信やKVSサービスは実装してない。 簡単なコードのテストは書いたが複雑な部分はシナリオを通過したノードがどのようにつながっているかdot形式で出力して可視化した。 論文の他に教科書(Distributed Computing)も参考にした。 詳しい解説スライドも読みました。
感想
Chordはよくあるアルゴリズムだし古いとか枯れているとか言われるのだけど実際に手を動かして書いてみると苦労する。 自分の実装力の低さを感じた。
論文や教科書のシナリオが正しいか確認したくシナリオを組んでイベントを逐次発生させシステム全体の検証やテストを書いていたが、 その最中に無限ループが起きたりして悩んでしまった。 大抵は論文や教科書の疑似コードで省略された前提を粗末に扱った結果のバグでした。 分散システムを考えるにあたりSPINモデル検査器を使えることは武器になる気がしたので試してみたいと思った。
資料には目を通しておきたい。
教科書で簡略化されているまま素朴に書いたけど改善してまともに動くようにしたいと思った。
- predecessorを利用して資源探索を最適化したい
- 経路表(finger table)に自分自身が含まれない事を保証させたい
- 経路表(finger table)とSuccessorsの重複を省きたい
- 柔軟な経路表とよばれる手法を実装してみたい
- ノード障害にsuccessor側の修正も対応させたい
- Locationに使っているハッシュ関数を整理したい
- キーを論理的なリングへ射影して資源探索するが判定関数を簡潔にしたい
- ノード間通信を実装
- 他のオーバーレイも書く
- ベンチマークとったりシミュレーションできるフレームワークを作りたい
- VirtualNode対応(VNF-Chord実装)
- この工夫を読んで思ったのだけどデータセンタ(DC)内のノードをvirtualNodeとしてDCをノードって捉えて更正するとDC間ルーティングが減る?
- DHTをサービス(KVS)とKey Based Routingに分離する捉え方があるのでKBRを独立させたい
- KBRの上でDHT,DHT(3冗長化),time-series DB, P2PSIP, 処理エンジン(Luaデプロイ実行)などの何かを乗っけて共存させる
資料集
今後は感想で書いた改善案を目指しながら下の資料を読み進める。