- RedisやMemcachedのようなオンメモリでデータを保持するデータストアを実現する
- データの他ノードによる中継などによってNAT越え（要は複数の異なるネットワークにノードが存在する場合）することまで考えると、実装がかなり複雑になることが予想されるため、今回は単一ネットワーク内に全ノードがいて、それらのノード間で直接通信が可能であることを前提とする
- 各ノードは構成されたKVSへアクセスするための put, get, delete をREST API として提供する
- 今回はパフォーマンスに重きを置かないこともあり、ストアできるデータはJSON形式として解釈可能なものに限定する（Valueの部分）
- Keyの部分はそれほど大きくなることを想定せず、API呼び出し時のURLの部分に含める
- KVSへのアクセスとは別に、DHTを構成するための通信も、（ひとまずは）REST APIとして定義し、ノード間のやり取りはそれを用いて行うものとする（いちいちソケットプログラミングするのは面倒なので・・）。コネクションを継続的に張り続けておかないと実装が複雑化するといったことが判明した場合は、見直しを行う
- 分散ハッシュテーブル（Distributed Hash Table, DHT）の技術を用いて、中央サーバ無しで動作するものとする
- DHTのアルゴリズム（プロトコル）としては一番ポピュラーな "Chord" を採用する
- 参考にする資料・ウェブサイト
- Chordネットワークの利用方法
- Chordネットワーク
- ChordネットワークはあくまでデータのIDから「担当ノード」のアドレスを得るための一種の名前解決の仕組みとして利用する
- put, get, delete のいずれも、「担当ノード」とそのアドレスが判明してから、直接当該ノードに対して該当する操作を依頼する形とする
- 広域分散のネットワークを構築する場合は、ルーティングや経路表の作成にあたって、NAT内に存在するノードへ対応するための考慮を加えなければならないと思われるが、それに加えて、UPnPを用いて、各ノードのデーモンがNATに穴を空けてグローバルIPでアクセス可能となるように振舞うことで、ネットワーク全体でグローバルIPでアクセス可能なノードの割合を増やさないと成立しないであろうと思われる
- Chordネットワーク
- 実装にあたって
- VIOSP04のスライドのP9に記述されている疑似コードであるが、ノード空間が6ビットより大きかったら再帰、もしくはループを用いた呼び出しがどこかに必要となると思われる
- 一例としては、一番上の n.find_successor という関数を、n' を更新しながら回るwhileループにて、n'.find_predecessor が対象とするIDをsuccessorList内に含むpredecessor（n'）まで到達して、そのn'から探している「担当ノード」の情報（とその後ろに位置する、successorListに含まれるノードの情報）を返してもらえるまで続ける
- ネットワークのstabilizeが局所的に完了していない状態で、かつ、運悪く所望のデータを保持するノードが発見できなかった場合はエラーを返せば・・・よいか
- データのIDを担当するはずのノード、もしくはその後続のノード群全てがデータを保持していない場合
- 通信回りでのトラブルを考慮しない場合に、ネットワークの規模や、下層の実ネットワークの速度、各ノード処理時間を考慮した上で、探索に要する最悪時間が大体求まり、その時間以内にデータを得られないことが必ず判明するのかは現状不明（そうでない場合、つまり、探索処理におけるノード遷移が滅茶苦茶になり、いつになっても終了しないというケースが存在する場合、タイムアウトの処理も加える必要がある）
- まずは、単純化のためにpredicessorもsuccessorも1ノードのみとする
- データのレプリケーションは別途行うとして、新規にノードがjoinしてきたとしても、successorが ln(全ノード数) 程度あれば、データを新たな担当ノードに委譲せずとも、担当ノードが持っていない場合に順にsuccessorにgetをかけていけば良いのかもしれない
- 委譲をするということであれば、定期的に自身の保持しているデータのうち担当外のものを、担当ノードを探索して、putするということをすれば良さそうだが、ある程度の個数があった場合、同一のノードに渡すものはまとめて渡すといったことが効率よくできるよう、データを保持しておくデータストアのデータ構造は考えておかなければならないだろう
- 今回はひとまずノードの離脱が起きないという前提で実装を行うが、一通り動くものができたら、離脱が起きた場合のシーケンスについても考える必要がある。具体的には経路表に入っていたノードにアクセスできなかった場合にどうするか、を考えることが主となるはず。あとはデータのレプリケーション処理の追加が必要だろう
- ストアしたデータはオンメモリだけで保持し、ストレージへの永続化はひとまず考えない
- ストレージへの永続化はしないが、DHTのアドレス空間上での隣接ノード等を相手方としたデータのレプリケーションは実装する。これにより、全ノードないし 多数のノードを一斉に落とすといったことをしなければ、データは失われないようになる（はず）
- 実装にはRust言語を用い、REST API実装のフレームワークや、極めて一般的な処理を担うライブラリを除き、フルスクラッチで実装する
- Chordアルゴリズムの理解とそれに基づく設計の検証のため、簡易的な、Chordネットワークのシミュレータを Python（今のところの第一候補）を用いて作成する予定
- 実システムを今回初めてまともに利用するRust言語で書いている中で、Chordの実装方法の誤りによる想定しない動作が発生した場合、デバッグのコストが非常に大きくなることが予想されるため