Rust製分散KVS開発におけるシミュレータでの事前検証を含めたTODO（完了済み含）

distributed_kvs_development_todo.txt

% 分散KVSシミュレータ（Chordシミュレータ） & 分散KVS（Rust製の実システム）
理想的（いくらか恣意的）なノードの振る舞いを前提とした条件下で、put と get が DHT の枠組みで動作するところまで
シミュレーションが行えた後の記録。
以下より前の消化済みTODOは記録していなかったか、コード中のTODOコメントですましていた。

● joinとstabilizeとputとsuccessorを辿っていくget（実装する）を並行に動かしたときにワークするか確認
・【完】joinとstabilize_successorとstabilize_ftableを並列にに実行させる形で最初からノードを追加していく

・【完】getは見つからなかった場合にsuccessorを一定数辿るようにする（※）。
　これはつまり、ノード間でノード情報をやりとりする際に、実システムでも、アドレスだけでなくsuccessorの情報を併せて
　やりとりしなければいけないことを意味するはず。具体的には経路表全体で、エントリにはノードのID、アドレスに加えて、
　そのノードのsuccessorのアドレスが含まれなければならないことになる
　（現在のシミュレータ実装では、インチキで既にそうなってしまっている）

・【完】1ノードについて一気にfinger tableの全エントリを更新するのではなく、1エントリずつ更新するように変更する
　　　　　　（更新するインデックスは下から順で同じにしてしまうが、これは実システムでの実装との乖離はないと思われる）

・【完】join時にsuccessorに設定したノードからデータの委譲を受けるようにする
　- 誤って、担当範囲でないデータを返してしまうとデータの一貫性に問題が出る場合がありそうなので、
　　委譲を依頼されたノードハッシュに保持されているKeyを数値として判定して、依頼してきたノードの
　　IDから自身のIDに位置するデータは取り除いて、残りを渡すようにする

・【完】finger tableのstabilize処理バッチの指定を2回から1回に減らしてもNOT_FOUNDは出なくなるか確認
　=> 1回、NOT_FOUNDが出てしまったので、2回のままにしておくことにした

・【完】他のノードのnode_infoを保持する場合、参照ではなくディープコピーを取得してそれを保持する
　　　　　　ようにすること（address, node_id, born_id, successorだけコピーすればよいはず。
　　　　　　ただし、純粋にディープコピーするとエンドレスになってしまうため、そこの考慮は行って、
　　　　　　実システムと齟齬が生じないようにする）
　　- 【完】deepcopyを行うためのメソッドを実装する
　　- 【おおむね完】実装したメソッドを利用する必要のある個所を対処
　　　（その時点での最新の内容を参照しなければならない場合は、ChordNodeオブジェクトから
　　　　辿らないといけない点に注意）
　　　=> 対応し、問題なく動作することが確認できたが、修正漏れがないかコードレビューが必要
　　　　=> コードレビューも完

・【完】新規ノードは全エントリが埋まるまでは、ルーティングに関わってはダメなのでは？、というあたりの確認
（いや、少なくともsuccessorが担当でない限り、successorには送るはずなので、IDがさかのぼってしまうということはない？
　しかし、successor含めて一つもエントリが埋まってないケースもあったかも？で、その場合は自身を返してしまって、
　IDが進まなかったとして、old_ndashが返ってしまったりする？？？が、他のノードが新規ノードをまだほとんど認識していない
　状況で、他ノードのルーティングテーブルに入るケースってどんな時だ？）
　=> この修正でNOT_FOUNDが出なくなったっぽい（確率が減っただけかもしれないが）

・【完】finger tableのstabilize処理バッチの指定数を2回から1回に減らしても問題ないか確認
　=> 問題無かった
・【完】successorのstabilize処理バッチの指定数も20回からどこまで減らして問題ないか確認
　=> joinの間隔を3秒に1ノードから、1秒に1ノードに増やすと、10回に減らすとだめだったので、20回でキープすることにした。

・【完】global_getでNOT_FOUNDとなった場合に、少し時間を置いてリトライする処理を入れる
 => getを繰り返すスレッドで、前回失敗していた場合は同一ノードで同じデータの取得を試みるようにして、ひとまずの対応とした

・【完】join時にstabilize_sucessorを実行し、successorが知っていた情報からpredecessorが自身に設定された場合は
　　　　predecessorにもstabilize_successorを実行させることで、可能な限りjoinしたノードと前後のノードを見た時に
　　　　predecessor -> <- self -> <- successor という紐づけがその時点で完結するようにした
　　　　=> successorを探しに行く形でのNOT_FOUNDも1秒間隔でのjoin, put, get を 6分間実行するケースでも起きなくなった

・【完】データの委譲を行う際に元のノードがコピーを持たないようにしたらどうなるか確認
　=> 取得に失敗することは6分間の実行で250回程度getして、2回発生したが、retryではどちらも取得に成功した。

・【完】join時、put時、get時に適切な担当ノードが見つからなかった場合に一定時間待ってリトライする処理の実装
　（これまでに試したパラメータでは発生してないようなので、実装は結構面倒そうだし後回しでも良いかな・・・）
※まったく見当はずれのIDのノードにputされていた場合はsuccessorを辿っても見つからないだろうが、joinは、適切なノードを
　successorにする形で行われ、その際にjoinしたノードの前にいるノードのsuccessorが更新されることはないため、stabilize_ftableで
　successorでのチェーンに参加できていないノードがfinger tableに入ることはなく、結果的にputを行うための探索でそのネットワーク
　への参加が中途半端な状態のノードが返ることもない、はず。ただし、join時のsuccessorに設定すべきノードの探索が失敗した場合は
　どうなるかよくわからないし、失敗することが今の実装をいじった場合に無視できない頻度で発生し得るのかもわからない。とりあえず、
　joinで適切なsuccessorが見つからなかった場合、少し時間を空けてからリトライする処理を入れる必要がありそう
　↑joinで適切なsuccessorが見つからないケースは、ひとまず皆、並行に実行するように実装した場合で、発生しなかった
　　(join, put and get が 1秒間隔、stabilize処理がsleep無しというパラメータの場合）

・【完】ソースの規模が大きくなってきたので分割する？

●ノード離脱が存在する場合を考慮した設計・実装
・【ひとまず完】successorを複数化する場合の、経路表で保持する必要のある情報の確認、stabilize_successrおよびstabilize_ftableの処理の確認
　- 【完】経路表で保持する必要のある情報の確認
　　=> 今までsuccessorのIDとIPアドレスのペアを一つだけ保持していたが、それをリストの形で複数持つ。
　　　　理論的には log(ノード数) （底は多分2）あれば、半分のノードがダウンしても大丈夫らしいが、そんな
　　　　状況までは想定しないので、なんとなくSuccessorListは3ノードあれば、300ノードぐらいなら十分では？
　　　　的な感じで感覚的には考えている。
　- 【完】stabilize_successrおよびstabilize_ftableの処理の確認
　　=> 現在のstabilize_successorはうまいこと拡張して、各ノードは自身のsuccessorListをメンテナンスするようにする。
　　　　stabilize_ftableは、新たに設定するノードがダウンしていた場合は次のエントリへ移ってしまえばよい（=continueする）　
      /*
　　　　stablize_ftableはこれまで通り、エントリを埋めていく処理を行うが、そこで格納する情報が、従来エントリには他の
　　　　ノードから得た単ノードの情報（IDとIPアドレスのペア）であったところが、そのノードとやりとりを行うようにし、
　　　　そのノードの情報に加えて、最新のsuccessorListを取得して格納する。（そのノードの情報を教えてくれたノードも
　　　　当該ノードのsuccessorListを持っていると思われるが、最新の情報ではないので、直接取得しての更新をおこなわなければ、
　　　　いつになっても系全体として最新化が行われなくなるはず）
      */
・【ひとまず完】putした場合のデータのレプリケーション
　=> 完璧とは言えないが、以下ぐらいで良いはず
　　　1. 主担当のノードがputのリクエストを受信
　　　2. succesorListのノードに受信したデータを送信してレプリカのデータを一時的に保持しておくよう要求（更新の場合もあるだろうが、扱いとしては同じ）
　　　3. succesorListのノードの全てから準備完了の通知を受ける
　　　4. putの発行元に反映完了のレスポンスを返す
　　　5a. レスポンスがエラーとならずに返せた場合、主担当のノードはローカルのデータストアに、
　　　　　リクエストされた情報を反映させ、successorListのノードに一時的に保持しておくよう要求したデータをコミットするよう通知する
　　　5b. レスポンスがエラーとなった場合、主担当のノードはローカルのデータストアは更新せず、
　　　　　successorListのノードには、一時的に保持しておくよう要求したデータを破棄するよう通知する
　　　※データのIDを知ったノードはsuccessorListのノードも含め、当該IDのデータをRWロックする
・【ひとまず完？】その他、ノードダウンしていた場合全般の異常系
　- 内部での通信もひとまずRESTで行うつもりなので、コネクションが張れなかったらノードダウンと判断し、対象ノードの
　  successorListの頭から順に代わりの役割を担ってもらう形で依頼すればよいはず。
　  ただし、find_predecessorメソッド（が対応する処理）では、データIDを飛び越えてしまっていた場合、既存のロジックと
　  だとうまくいかない可能性があるため、そこの考慮は必要だろう。
・【ひとまず完】独自定義のクラスについても正しく型チェックさせる方法を調べる（今は良く分からずにいい加減に済ましているので・・・）
　　　　　　　　あとは、ちゃんと動作しているのに、mypyでの型チェックで一つエラーが出て、それを消せないのが気持ち悪いので。
・【完】sussessor_infoの拡張（finger_tableはまだ）
・【設計完】生死チェックを行うのは直接のsuccessorのみにして、それ以降の2ノードの情報は直接のsuccessorからもらう？
　　　　　　とかで良い？もし死んでたら、successorのsuccessorを、新たなsuccessorに設定して、新たなsuccessorにcheck_predecessorを
　　　　　　実行させて、新たなsuccessorから2ノードの情報をもらう。
・【設計完】ルーティング時などにノードが死んでいたとしても、successorに代替させるだけにとどめて、経路表の
　　　　　　更新はstabilize_xxx で行われる形にするのが筋が良い気がする。
・【完】finger_tableの拡張（最低限）
・【完了】check_connectivity時に predecessorのチェーンと、successorのチェーンに全てのノードが含まれているかチェック
　　　　　　し、含まれていなければ例外を上げるようにする（2ノードの時点から行っても問題ないはず？）
・【完】ノードダウンしていた場合の例外処理の整理（同一のメソッドで共通化できないか？）
　=> 共通化するほどのコードをexcept節に書くことはなさそう。もっと大枠での共通化は
　　　不可能。

・【ひとまず完】他のノードと連携してデータの整合性をとる処理において、クリティカルセクションがある場合、
　　　　　　　　どうやって、それらのノード群全体で排他をとるか？？？そんな必要のある処理は存在しない？とか考える
　- 単純には各ノードに他のリクエストが来ても待たせておくようロックを行うAPIを定義しておくという
　　方法が考えられるが、ロックをとったノードがダウンした場合の考慮が面倒
　- join時 => 不要
　- レプリケーションデータを複数ノードに配っている最中 
　　=> あるkeyに対するレプリケートデータの更新が異なるノードから来ることは無いはずなので不要

　- 【完】stabilize_successorの処理フローを考える
　　[基本的な考え方]
　　　downしているノードが見つかった場合のネットワークの修復処理はここに集約するのがシンプルと思われる。
　　　それ以外のオペレーションでダウンノードが見つかった場合は失敗として、リトライなりさせるのがシンプルかと

・【一旦完】拡張版のstabilize_successorを実装する
　（successor_info_listを規定数埋めるようにする。ノードダウン検出時の考慮もここで行う）
　　★注: ノードダウンが存在する場合の挙動は未確認★

・【完】finger_tableの拡張をなかったものとして元に戻す
/* 実際、意味無かったっぽいので、複数保持しないように戻した
メモ: 今の設計だと、finger_tableの各エントリに複数ノードの情報を保持している意味がないのでは？
　　　そもそも、インデックス0以外を readで参照するコードが存在しないし。
   　　あとは、ルーティングがノードダウンで失敗した場合に、リトライさせたところで、途中で経由するノードの
　　　finger_tableの情報にすぐにノードダウンの事実が反映されるかは怪しいので、finger_tableの各エントリを
　　　拡張した点を活用して、リトライを可能な限り避けるように修正した方がいいのでは？
　　　（ただ、古い情報を保持している箇所が増えるために、正しい担当ノードに到達しないケースが増える可能性
　　　　はありそうな気がする）
*/

-------
【完】join（リトライ）、put（リトライ）、stabilize_fingertable（スキップ）、ルーティング時（ちょっと頑張る）、の最低限の例外処理を書く

メモ:
getのスレッドだけ止めてやれば、putでのレプリケーションあたりのこみいったところを実装しなくても、
join, put, stabilize_fingertable, ルーティング時、の例外処理だけ書くのみで、最低限のノードdown時のテストはできる気がする。
（データのロストが起きていても、getをかけていなければエラーとして現れることはないので）

・【完】ルーティング時（at closest_preceding_finger）にダウンしたノードに遭遇したら、continueして、そのエントリ
　　　　を返すことをあきらめて、それより遠いノード群のサーチを継続するようにすればよいはず
　　　　/* 一つ前のn_dashに、ダウンしたノードまで
　　　　いかない範囲で近づいたノードを返してもらうようにすればいい気がする。*/

・【完】stabilize_fingertableの例外処理の実装
　->  ルーティングの中でノードダウンに遭遇した場合は大体はfind_successorの中で吸収される。
　　　find_successorが例外をraiseしたら、吸収しきれなかったことを意味するので、その回はあきらめる。
　　　更新しようとしていたエントリはfind_successorが投げる例外からは特定はできないが、基本的には
　　　ノードダウンの場合しか raise されないはずなので、更新対象としていたエントリはNoneを埋めておく

・【完】global_getの例外処理の実装（リトライ）
・【完】ノードをダウンさせるスレッドとその先で呼ばれる処理を書く
　　　　　　（リトライ対象の処理が存在する間はリトライ時に利用するノードがダウンしていた場合に面倒なので
　　　　　　　ダウンさせる処理は中断する）
・【完】put時の例外処理（リトライ）

・【作業中】join時の例外処理（リトライ）
　-> 仲介ノードはダウンしていないことが保証されているものとする。仲介ノードが探索したノードが
　　　ダウンしていた場合は、仲介ノードと途中まで作成したNodeInfoをNodeInfoのstaticなフィールドに置いて
　　　おいて、次の機会にその情報を使ってリトライ
　　- 【完】joinメソッド側
　　- 【完】add_new_nodeメソッド側
---------

・【完】join時にsuccessorListを埋める（stabilize_successorを呼び出せばいいだけ？）

・【完】getを行うスレッドをコメントアウトで止めて、ノードダウンを定期的に発生させるスレッドを有効にした上で
　　　　join、put、stabilizeだけ実行した場合に、ちゃんと動くか確認してみる
　　　　=> 想定外のエラーなどが発生することなく、ちゃんと動く状態にできた

※1
レプリケートを受けているデータにはマスターの情報を紐づけておく形にして、そのデータに対するgetを
受けた場合、マスターの生死チェックを行い、ダウンしていたら、以後は自身が新たなマスターであることを
示すよう、保持しているデータの管理情報を書き換えたり、後続のレプリカを持っているであろうノードに
通知したり、レプリカを持つノードを増やすといった処理をする必要がある。
このような設計にすれば、stabilize_successorなどで担当範囲の変更の通知などを明に行う必要はないはず？
（join時に、担当範囲の変更によってデータの委譲を行う場合と異なり、ノードダウンの場合は旧担当と
　新担当を考えた場合に、旧担当はダウンしているので、ネットワーク全体の経路情報の更新のタイミング
　の問題で旧担当にデータを取得しに行くノードが現れても、取得は失敗してリトライとなるので、join時の
　ような処理をstabilizeのタイミングで行う必要はなく、新たに担当となるノードに取得が要求された時点
　でよろしくロール変更やレプリカの適切な配置は行われる。ただし、新担当に取得リクエストが行くまで
　レプリカを保有しているノード数が減った状態となるという点は、設計のシンプル化のトレードオフとして
　生じるはず）

・【作業中】put時のレプリケーションの実装
　- 【ひとまず完？】設計
　　　　　　　・関連処理の実行契機
　　　　　　　　- 1. データがputされた時（putされたデータをsuccessorList内のノードにも渡しておく必要あり）
　　　　　　　　- 2. レプリカを持つ非マスターが、get要求を受けた時に、要求データがレプリカであった時（あれ
　　　　　　　　　　これよろしくした上で、自身が新たなマスターになる必要があると判断した場合は適宜、必要な
　　　　　　　　　　処理を行う。※1）
　　　　　　　　- 3. join時（predecessorからレプリケートデータを受け取る必要あり。predecessorは新たなsuccesor
　　　　　　　　　　がsuccessorListに加わることではじき出されるノードがいた場合、そのノードにレプリカを削除する
　　　　　　　　　　よう通知し削除させる必要あり。successorは自身が担当でなくなるデータを委譲するとともに、
　　　　　　　　　　successorListの全ノードに縮小される担当範囲を通知し、該当範囲のデータを持っていたら削除させる。
　　　　　　　　　　また、successorからは当該ノードが保持する全てのレプリカデータを受け取る）
　　　　　　　　- 4. stabilize_successorを実行した際に、内部関数であるstabilize_successor_innerを呼び出すが、その中で
　　　　　　　　　　未認識のノードを発見し、当該ノードをsuccessor[0]に設定した時。
　　　　　　　　　　join時とほぼ同様に、新たなsuccessor[0]にレプリカを渡し、successorListから溢れたノードにレプリカ
　　　　　　　　　　を削除させる必要あり。（規定数のノードが埋まった状態になる処理になっているか確認しておくこと）
　　　　　　　・各ノードにおける保持データと管理情報の構造モデリング
　　　　　　　　- 一つのdictに保持データは全て格納するが、valueは、データ自体のvalueとマスターのNodeInfoへの参照
　　　　　　　　　の2つとする
　　　　　　　　- マスターごとにまとめて保持データを処理する場合の効率化のために、keyをマスターのIDの文字列表現、
　　　　　　　　　valueを保持データのIDとしたdictを別途用意する）
　　　　　　　　- マスターのNodeInfoはリストとして保持しておく（マスターの切り替わりが生じた場合
　　　　　　　　　NodeInfoのnode_idとaddress_strは書き換えが生じる。これによりデータを保持している
　　　　　　　　　dict内の各要素の紐づけを一つづつ更新する必要は無くなる。要素が取り除かれるのは、
　　　　　　　　　join時に、自身がレプリカの配置ノードから外れた場合のみのはず）

　 -【完】successor_info_list の インデックス0にinsertでなしに、直接値を入れてしまっていて、それだと問題の
　　　　  あるコードがあれば修正する

　 -【完】実装にあたってコードの追加が必要な部分にスケルトンなりTODOコメントなりを記述する
 　-【作業中】実装（まずは簡易実装とするため、無くても最低限の動作確認が可能な設計の部分は除く）
      -【完】データと管理情報のフィールドの追加
　　-【完】肥大化したChordNodeクラスを複数クラスに分割するリファクタリングとその状態での既存動作の確認
　　-【完】契機1（put）に関して
　　　-【完】putの対応
　　　-【完】receive_replica と そこから先の対応
　　-【完】契機2（get時の特殊ケース）に関して
　　　-【完】getの対応
　　　-【完】notify_master_node_changeの実装
　　-【完】契機3（join時）に関して
　　　- 【完】delegate_my_tantou_dataとその先
　　　- 【完】join
　　　- 【完】pass_tantou_data_for_replication
　　　- 【完】pass_all_replica
　　　- 【完】check_replication_redunduncy
　　- 【完】契機4（stabilize_successor）に関して
　　　- 【完】TODOコメント1
　　　- 【完】TODOコメント2
　　　　-【ひとまず完】 stabilize_successor
　　　　-【ひとまず完】この時点でdown nodeが発生しない場合の既存動作が正常に動くか確認
　　　　-【完】stabilize_successor_inner がレプリケーションの整合性を正しくとるかレビュー
　　　　　　　　　（put時の不足レプリカの配布の存在も合わせて考えた上で）
　　　　　　-【一応完】以下以外
　　　　　　-【完】ダウンノードが連続して存在した場合にレプリカ配置の整合性は崩れないか
　　　　　　-【完】 successorListから溢れるノードが存在した場合に、そのノードが持っていたレプリカについてのケアは
　　　　　　　　　　いずれかのノードのstabilize_successorもしくはstabilize_successor_innerによって行われるか、
　　　　　　　　　　そもそも必要か

・【完】
　　putを受けたノードに、データIDが自身の担当範囲かチェックさせる処理が必要では？
　　（例えば、predecessorかそれより前のノードが担当のはずのデータがputされてきたら、predecessor
　　　の生死をチェックして、生きていれば、少なくとも自身が担当であることは無いので、エラーを返す、など。
　　　とか考えたが、整合性が崩れるリスクを最小限とするため、predecessor_infoがNoneの時、担当範囲でない時
　　　はエラーを返すようにした）

・【不要】レプリカの存在を踏まえたget処理
　↑stabilizeで担当ノードの情報がよろしく更新されれば、既存のリトライ処理でカバーできる

・【完】getを含めたノードダウンが発生する状況での動作確認
　ただし、finger_tableのエントリが同じノードで埋まっていて、そのノードがダウンしている
　というログが結構見られるので、ノードダウン直面時のfinger_tableの更新周りの実装が良くない（≒適切でない）可能性
　はあるかもしれない。

// 「ノード離脱が存在する場合を考慮した設計・実装」 については以上で完了

・【完: 以下の記述通りの仕様で良いことにする】
　JSON（value）の扱いとかなんかしないとダメなのだろうか？
　=> 文字列だけ扱えるという仕様で、JSONで扱いたければ、JSONとして有効なものをValueにするのはユーザの責任と
　　　すれば良い。JSONのフォーマットもユーザが好きに決めれば良い。
　　　いやしかし、エラーコードとか渡す場合を考えると、そうも言ってられないか・・・。
　　　put, get, delete で { data: 文字列かJSオブジェクト, resp_code: 文字列} を返す、ぐらいは決めておくか。

↓一定時間を空けてノードを追加していく想定なので不要（しかし、ダウンノードがメンテ後に再joinする場合は想定必要か・・・？）
・【不要】高頻度で並列joinが起こる場合でも問題なく動作するか確認 

・【作業中？】join以外のオペレーションが複数ノードで並列に動作する状態になった場合に
　問題なく動作するか確認する？
　- 【完】ロックの粒度をChordNodeオブジェクトの単位にすればよい？
　　↑joinを考えないとすると、ノードダウン検出時にsuccessorListやpredecessorの書き換えが生じる
　　　場合の経路表（委譲やレプリカ配布に関連するデータもかな・・・）と、putやdelete時の更新中のkey
　　　ぐらいのもののような気がしてきた（putとdeleteだけ複数リクエストの処理を同時に行えないように
　　　すればいいのかな）。
　  しかし、そのロックの取得・解放のコードを書くのはどの程度のコストでできるだろうか。
　　（アノテーションなどで何とかできたりする？）
　  あとは、デッドロックなどを回避できる形で実装できるだろうか。
　  なんか、検証しなくても良いかという気もしてきていたが、実システムでもノード単位のロック
　  が存在したとすると、デッドロックが生じ得るのでは？？？（例えばリクエスト元とリクエスト先がそれぞれ
　　自身をロックした場合、リクエスト先が巡り巡ってリクエスト元にリクエストしようとしたらデッドロックになる
　　ような）
　　ロックしないといけない対象のデータを絞ればなんとかなる？？？（で、リクエストは同時に複数受けられるように
　　する）
　　ロックされてないとまずいケースを列挙して、そこから逆算で必要なロック単位を決めるのが良さそう。
　　あとはクリティカルセクションとなる区間（他ノードにアクセスする場合どうするかという話はありそうだが・・・）
　　製品作るわけではないので、経路表の整合性が崩れて、Chordネットワークがまともに機能しなくなることさえ避けられれば
　　十分な気がしてきた。
　-【完】successor_node_listとpredecessor_infoにwriteアクセスするメソッドにはトランザクション処理とする形で
　　　　 writeロックを取得する必要がある旨、それら（ロックは各々に用意）にreadアクセスし、かつロックが必要な
　　　　 箇所にはreadロックを取得する必要がある旨をTODOメモとして記述
　-【完】global_getとglobal_putのリトライ時にリトライを開始したスレッドは、自身でその情報を保持し、クラス変数に
　　　　設定されているものはクリアするようにする（複数スレッドでputとgetを動作させることを可能とするため）
　　　　という実装を行うようTODOコメントを記述する
　- 【完】put, get, stabilize の操作を複数スレッドで並列に動作させるようにするための修正箇所にTODOコメントを記述
　- 【完】joinとstabilize処理をノード毎のロックを取得する形にした上で並列に動作させた場合にデッドロックが起きそうか
　　　　  コード上から確認する（動かせば分かるという話もあるが、タイミング問題なので、コード上から確認できる
　　　　  ならそちらの方が望ましい）
　　- 検出済み1: joinで、P <- N (P=Predecessor, N=joinしたNode) とアクセスしているタイミングで、stabilize_successor
　　　　　　　　 の延長の処理で N -> some S (N=stabilizeしているNode, some S = NのsuccessorList内のノードのいずれか)
　　　　　　　　 という処理が走ると、お互い呼び出し元のロックを持った状態で、そのノードは他方の呼び出し先のノードである
　　　　　　　　 場合があるため、その条件が揃うと双方ともに呼び出し先のロックがとれずにデッドロックする
　　- 検出済み2: check_replication_redunduncyでsuccessor_info_list内のノードの余剰ノードにメソッド呼び出しを行うが、
　　　　　　　　それがstabilizeメソッドを呼び出して、stabilize処理を開始したノードであった場合にデッドロックする
　　- 検出済み3: 2つのstabilize処理が別ノードで走った際に、stabilize処理を開始したノードが互いのsuccessorListに入っていた
　　　　　　　　場合。ノードA, B がいた時に簡易的には A -> B , B -> A とロックを取得しようとしてデッドロックする
　　　　　　　　（ネットワーク上のノード数が少なく、2者のsuccessorListだけで全周をカバーしてしまうようなケースに
　　　　　　　　　生じうる）
　-【完】successorListに自ノードが入っているとstabilize処理でデッドロックが起きる可能性があるので、successorListにエントリを
　  　　   追加する際に念のため自ノードでないかチェックする処理を加える
　-【完】RWロックとロック取得のタイムアウトがPythonの標準ライブラリで実装できるか調べる
　　　　=> RWロックはできないので、readerwriterlockなるpipモジュールを導入することにした。なお、PyPyでもインストールできたので多分動く
　-【完】ひとまず、現在のロック機構を標準ライブラリのものから、readerwriterlockモジュールのものに変えて動作するか確認して
　　　　  みる
　　　　=> 動作したが、re-entrantなロックには対応しないらしいので採用を見送り
　-【完】ロックがタイムアウトした場合オペレーションを失敗させなければならない箇所にはその旨
　 　　　 コメントを追加する
　-【完】join, put, get のロックの粒度を変更するようTODOコメントの箇所の実装を行い、既存のロック処理を取り除き、
　　　　 新たな粒度のロックを用いるよう書き換える（ひとまずタイムアウトは無しで実装）。ロックに用いるクラスは
　　　　 LockクラスからRLockクラスに変更
　- 【完】既存動作のリグレッションテスト（バグったようなので修正が必要）
　　　　  joinしている途中のノードを get_node_by_addressでとりにいってしまう状況が発生していた
　　　　  ためにKeyErrorが起きていたようなので、put, get, join時の最初の問い合わせノードにそのような
　　　　  ノードが選ばれないようにし、例外が発生した場合は適切に対処するよう、KeyErrorを、発生個所で、
　　　　  TargetNodeIsNotFoundExceptionとまとめた新たな例外としてInternalControlFlowExceptionを作成し、
　　　　  従来KeyErrorを素通ししてしまっていたルートに当該例外をcatchする処理を記述した。
　- 【完】stabilize処理の中でロックの取得が一定時間（30秒とかでいいかな・・・）かかっても行えなかった場合、メソッド呼び出し
　　　　  をエラーで返すなどして、複数ノードにまたがっているであろうオペレーション全体を失敗させる（デッドロックを解消するため）
　- 【完】既存動作のリグレッションテスト
　　=> やはり、データストアで保持しているデータやその管理用のメタデータについても排他制御をしないといけないことが分かった
　- 【作業中】各ノードのデータストアで保持しているデータやその管理用のメタデータについての排他制御を実装
　　- 【完】実装する
　　- 【完】既存動作のリグレッションテスト
　　　　　　=> ロックの粒度を小さくしたことでNOT_FOUNDが頻繁に出るようになった（killスレッドを停止させていても）
　- 【完】stabilizeスレッドの処理に1ms程度のsleepを挟んだらどうなるのか試してみる
　　=> NOT_FOUNDが更に出やすくなってしまって、使い物にならない感じになった
　- 【作業中】ロックの粒度を小さくしたことでNOT_FOUNDが出やすくなってしまった原因を探る（ひとまずkillスレッドは止めておく）
　　- 【完】successsorがデータを持っていて、本来返しても良い状況（masterである）にもかかわらず返せないといったことになって
　  　　　　いないか確認する
　　　　　　=> なっていなかった
　　-【ひとまず完】そもそもなぜそのような状況が生じるのかを整理する。
　　　=> joinでデータを委譲中にgetがかかっているという話と、何かの設計ミスかバグで的外れなところにデータがある場合があるか。
　　　　　後者が起きているとすれば、その原因重要なのであるが・・・
　　-【完】前にノードがjoinしてきた際の委譲が終わった後に、古い担当ノードがputを受け付けてしまうと、そのデータは誤った
　　　　　　　ノードが保持し続ける（そしてリクエストされても本来のマスターが生きている限りエラーを返す）状態になるが、
　　　　　　　そのようなタイミングはあるか？
　　　　　　　=> joinメソッド中でのデータ委譲処理のタイミングが既存のものだと、元の担当ノードが本来は既に担当範囲ではない
　　　　　　　　　（しかし通知を受けていないのでそれを知らない）タイミングで、自身の担当データとしてputを受け付けてしまい、
　　　　　　　　　委譲されるデータにはそれが含まれないというタイミングが生じるようなので修正してみた。
　　　　　　　　   https://github.com/ryogrid/rust_dkvs/commit/deff17ac1306d98648dab27b8ca83967f04283bc
　　-【完】join時にデータを委譲する側が持ち続けておかないとならないデータを削除してしまっていたようなので修正。
　　　　　　　 また、委譲するデータにレプリカも含んでしまっているようだったので修正。
　　　　　　　 しかし、そのようにすると、委譲用のメソッド内の del文でエラーとなる。
　　　　　　　 https://github.com/ryogrid/rust_dkvs/commit/3e87e24a58f6b3b6b4dcfdd186f35792560f5c47
　　　　　　　 stored_dataのキーが示すdata_id と value である KeyValue オブジェクトが 示す data_id に不整合が生じていると思われる。
　　　　　　　　=> もろもろ修正したら NOT_FOUND出なくなった 
　-【ひとまず完】killスレッドを有効にするとNOT_FOUNDのまま最後まで見つからないglobal_getが起きてしまう問題の調査・修正
　　-【完】joinメソッド中のデータの委譲の処理と、前後のノードのものを含む経路情報の更新処理の実行順序を入れ替えてみた
　　　　　 => 症状に変化無し
　　-【完】joinメソッドから（要はChordNodeのコンストラクタから開始されるjon処理全部）、レプリカに関する処理など、joinメソッド中
　　　　　 で必ずしも行わなくて構わない処理を分割して、all_node_dictに追加されてから、実行されるようにした。
　　　　　 また、joinメソッド内でstabilize_successorを呼び出しているのが微妙な感じだったので、それを呼び出さずにsuccessor_info_list
　　　　　 を埋められるように書き換えた。
　　　　　=> 症状に変化無し
　　-【完】killした時にkillしたノードが持っていたデータIDをログにダンプさせる処理を追加する
　　-【完】join時のデータの委譲と、レプリカの配布周りのコードを確認し、ちょっとこれは良くないかも？的なところを修正した
　　-【ある程度完】データのマスターがどのノードにあって、レプリカがどのノードにあるかというのをメソッド呼び出し一つで出力できる
　　　　　　　 ような仕組みを作り込む？ それか、まず、レプリケーションデータが確かに配られているとして、そのデータの配置
　　　　　　　 （オブジェクトとしての実体は別のものになったりするので面倒だが）の推移をトラッキングできるようにする？
　　　　　　　　↑どのノードがマスターノードかまでは分かるようになっていない
　　　- 【完】killする際にノードのロックをとるようにするとどうなるか試す
　　　　=> 意味無し
　　　- 【完】まずはリトライが一定回数以上続いた時に、global_getで取得しようとしているデータを持っているノードのリストを得られる
　　　　　　　ようにする（gvalモジュール内にデータIDをキー、NodeInfoのリストをValueとする連想配列を用意して、data_storeにデータを
　　　　　　　追加・削除する共通メソッドで、連想配列の記録を更新するようにすればよい）
　　　　　　=> ダウンしたノードのデータがsuccessorListに入っていない程度に離れたノードに一つだけ残った状態になっているようだという
　　　　　　　　ことが分かった。他のglobal_getの出力を見るに、ダウンしたノードのデータ以外のレプリカについては問題はなさそう。
　　　- 【いくらかやった】レプリカに関する処理のロギング用メソッドを用意する。記録する内容は、
　　　　　　　　　　16進表現のデータID、処理が行われたメソッド（可能であればマクロ的なものでよろしく与えられるようにしたい）、処理の内容の共通文字列、
　　　　　　　　　　処理が行われたノードの一連の情報1、処理が行われたノードの一連の情報2（オプショナル、移動と分かる時は元と先を指定できるように利用する）
　　　　　　　　　　マスターかレプリカか（オプショナル、呼び出し箇所で判断がつく場合は与える）
　　　　　　　　　　の5つで、出力先はstdoutとファイルをハードコードで切り替えられるようにしておく。
　　　　　　　　　　処理内容の種類は、DIRECT_STORE、DIRECT_REMOVE ←これらの2種だけ実装した
　　　　　　　　　　　　　　　　　　　↑これらはdata_storeフィールドに直接アクセスする場合、もしくはstore_new_dataメソッドなどのアクセサメソッドの
　　　　　　　　　　　　　　　　　　　　呼び出しにおいてのみ使用
　　　　　　　　　　　　　　　　　　　STORE、REMOVE、MOVE
　　　　　　　　　　　　　　　　　　　↑それ以外 
　　　　　　　　　　　　　　　　　　（順序の入れ替わりが起きないよう、毎呼び出しでflushする）← 後で取り除いた
　　-【完】stabilize_successor_innerの怪しい箇所を修正
　　　　=> 症状に変化無し
　　-【完】試しに、check_replication_redunduncyの呼び出しをコメントアウトしてみる
　　　  => レプリカは当然ながらネットワーク上に増えてしまったが、症状自体は発生しなくなった。ただし、根本原因の解消にはなっていないと思われる。
　　　　　 なお、レプリカがネットワーク上に増えてしまうことは、ムダにメモリを消費する以外では無害である認識（実質的に不整合は引き起こさない
　　　　　 はずなので）
　　　　　https://github.com/ryogrid/rust_dkvs/commit/22570384d5c7678850621f6dcd7a277af19fb4b9
　　-【完】predecessor_info と successor_info_listの内容をstabilize_successor_innerとstabilize_finger_tableの呼び出しの頭で出力するように
　　　　　 して、観察する
　　　- 【完】NodeInfoクラスに文字列表現される場合の出力を定義する
　　　- 【完】デバッグプリント用メソッドの作成と、呼び出しの追加
　　　- 【ひとまず完】ログ調査
　　-【完】 successorListの状態がおかしくなる状態が観察されたが一時的なものなようなので、そのせいでstabilize_successorで自ノードが
　　  　　　返ってきて、successor_info_listを埋める処理が中断してリストの長さが短くなっていたところを無視して、自身の元々のsuccesor_info_list
　　  　　　の情報を参照して、埋める処理を継続してしまってよいのでは、ということでそのように修正して、実行してみる
　　-【やめた】デバッグ用に、定期的に本来、自身が担当ではないデータを持っていることがないかチェックするコードを入れてみる
　　　- そのようなノードが存在するようであれば、試しにそのデータを本来の持ち主にglobal_putするようにしたらどうなるか試してみる。
　　　（同じキーで新たなデータがput済みであった場合、古いデータで更新してしまうことになるので、厳密にはタイムスタンプなどを
　　　　導入しなければならないし、一時的に同じキーに対応するデータが2つに分岐し、それぞれが更新されていた可能性も考えられる。
　　　　その場合、一時的に、他方に行われた更新が無視されていた状態が発生していた可能性もまた考えられ、タイムスタンプで最新の
　　　　データを残すことはできても、過去に不正な動作をしていた可能性についてはどうしようもない。このようなケースも結果整合性
　　　　という整合性のレベルは守られていると言ってよいのかは不明）
　 【完】
　　今起きている問題がバグなのか、設計の不備なのか、設計上発生せざるをえないものなのかは判断が
　　つかないが、各ノード上のデータに"マスター"か"レプリカ"か、という区別をつけている点が問題を
　　複雑にしている要因のように思える。
　　　stabilizeが適切に行われていれば（successorListの中のノードが自身をsuccessorListの中に持っている
　　といった状況は一時的に発生しているようだが）、predecessorのIDと自身のIDを見ることで担当範囲
　　かは分かるので、持っているデータがマスターかレプリカかを知らなくともget時の対応は問題なく行える
　　はずだし、put時も同様。（ネットワークが十分に安定している前提。ノードダウンやjoinは起きるにしても
　　それほど高頻度に起きることは考えにくいので問題ないはず。特にjoinは運用でコントロールできる）
　　　従って、以下のように設計を変更する。
　　---
　　-【完】データの保持は単純にデータIDをキー、データIDとストアされた値をvalueとして持つデータオブジェクトを値
　　  　　　　　とするdictのみとする（valueにデータIDを含めるのは、既存処理からの修正を少なくするため）
　　-【完】putは predecessorと自身のIDから、担当範囲であった場合のみ受け付け、それ以外はエラーを返す
　　-【完】getは predecessorと自身のIDから、担当範囲であった場合のみ受け付け、それ以外は定められたエラー文字列を返す
　　-【完】check_replication_redunduncyはメソッド名を変更し、successor_info_listの要素数を調整する処理のみ
　　　　　 とし、レプリカの削除は行わない
　　-【多分完】データの委譲、join時やput時のレプリカの配布は従来通り行うが、notify_master_node_changeは利用できなくなる
　　　　　　　（ダウンノードの代わりにmasterノードになる場合に利用されていたが、データにマスターの情報を紐づけなくなった
　　　　　　　　ので、呼び出す必要はなくなる）
　　-【完】システム側都合でのデータの削除は行わない。その結果、レプリカがネットワーク上に必要以上に存在することになる
　　　　　 が、successor_info_listの規定長より十分に大きいノード数がネットワークに存在すれば、データの一貫性に問題は発生
　　　　　 しないと考えている（まったく的外れのところにputしにいったりgetしにいったりすることはないようなので）。
　　　　　 ムダにデータ領域を消費してしまう点にはひとまず目をつむる
　　-【完】デバッグ用に保持しているデータを用いてglobal_getで取得されたデータがネットワーク上で最も最近putされたデータと
　　　　　一致しているかを確認するコードを入れて、データの一貫性が崩れていないかは検証する
　　---
　　-【完】上記の設計変更を行ったものの現象が変化なかったため、stabilize_successorをするたびに、そのノードの担当データ全ての
　　　　  レプリカをsuccessor_info_list内のノードに配る修正を入れた（無理やりどうにかしようとしている感はある・・・）
　　-【完】ID空間上の距離関数であるcalc_distance_between_nodes_left_mawari と
　　　　　 calc_distance_between_nodes_right_mawariがバグっていることに気づいたので修正（根本的なところなのでこれで
　　　　　 不具合が解消することを期待）
　　　　　=> ダメ
　　-【作業中】前項の修正を入れたことで現象が発生しなくなるか動作確認
　　　=> ダメ
　　- 【完】アレコレ修正を試した
　　=> ダメ
　　[現状の整理]
　　===
　　global_getで見つからないデータが発生して、リトライを繰り返してもダメ、という現象が発生している。
　　もろもろ修正などを繰り返して観測した結果を踏まえると現状、以下の2つのいずれかが原因の可能性が有力と思われる
　
　　・join時のデータの委譲に失敗することがある（なお、委譲の処理においてsuccessor-0 の情報を除いて、経路表の情報は関係ない。
　　　とすると、発見したノードがダウンしていた場合にリトライが行われたというケースが怪しそう）
　　・joinとkillの処理がかみ合うことで、経路表が一時的におかしな状態になっているノード群が発生し、その状態でglobal_putが
　　　行われた場合に、見当はずれの場所（見当はずれのノードIDを持つノード）にputしてしまう
　
　　なお、この２つは独立した話と考えられるので、一方だけが存在するのではなく、2つ両方が存在する可能性がある。従って、
　　現象が発生した場合にも、その原因はこの2つのいずれのどちらが原因であるか区別して考えないといけない可能性がある。
　　====
　　-【完】Chordの本来のお作法に従わずに、join時にpredecessorを設定していた箇所を、設定しないように修正
　　　=> ダメ。ただ基本動作は問題なく動作していたので修正自体は残す
　　- 【完】global_getをかけたデータが見つからなかった場合、global_get内でprecessorとsuccessorを辿ってリカバーを試みているが、
　　　　　　現状の実装だと、持っていないかと確認されたノードは自身の担当範囲でないためデータを返さないので、返すようにし、返された
　　　　　　場合は global_get内で本来の担当ノードにstoreさせるよう修正
　　　　　   https://github.com/ryogrid/rust_dkvs/commit/6dcf298c24c9b95dcfa3bddeb23945603c99bfe9
　　 　　　　=> 現象は発生しなくなった!（ただ、元々の担当ノードがデータを持っていない状態が発生している現象を握りつぶすような
　　　　　　　　解決法となっているため、元の現象については後で深追いしないといけないと思われる）
　　-【完】kill時に対象ノードの全てのロックをとるようにしているコードをコメントアウトしても、現象は変わらず再現しないか、確認
　　-【完】件の現象の発生の回避につながるかと思い、stabilize処理の先頭で対象ノードが持っている担当データを全てsuccessor_info_list内の
　　 　　　ノードにレプリケートするという非効率な処理があるため、それを取り除いても問題なく動作するか確認
　　-【完】4h以上のランニングテスト
　　　　　=> 結局、件の現象が発生してしまった・・・
　　-【完】putとgetのインターバルを500msから50msと小さくし、一定のノード数が参加してChordネットワークが安定した状態
　　　　　 になったあとの、joinとkillのインターバルを20secから120secに大きくして試してみた（joinとkillが想定する運用からして
　　　　　　あまりに頻度が高すぎるし、それではネットワークを安定化させるためのstabilize処理が間に合わないのでは、という仮定の検証）
　　　　 => 一度は長時間のランニングでも件の現象は再現しなかったが、2度目で再現してしまった
　　-【ひとまず完】もう、しょうがないので、ランニングを行いながら、実システムとの齟齬や、件の現象の発生確率で妥協できるラインを
　　　　　　　 　　決めることにする。（その状態のコードをベースに、各オペレーションの複数スレッド化時の検証も進めるという方針）

/* stabilizeのみ複数スレッド化することにしたので不要になった
　-リトライ処理のための情報を格納しているクラス変数をリスト形式にして複数保持できるようにする
　　- 実装
　　- リトライ処理のために設定されるデータでも排他制御を行うようにする
　- 既存動作のリグレッションテスト
*/
　-【完】同時に走るスレッド数を各々10程度まで増やす（stabilize）。
　-【完】getで値が取得できるか、デッドロックが発生しないか、データの整合性が崩れていないか、を確認する
   　-【完】ログ出力量をフラグで減らせるようにしたり、ノードの増加上限数を設定可能とし、putとgetのインターバルもより小さくし
　  　　　　　  その条件でデッドロックが発生しないか長時間のランニングテストを行う
　-【完】NodeIsDownedExceptiopn, InternalControlFlowException, AppropriateNodeNotFoundException の raise と except を
　  　　　を整理する。AppropriateNodeNotFoundExceptionはノリで作って使ってしまったが、不要だし、exceptするコードがやや
　  　　　こしくなるので良くない。ただ、修正は慎重に行う必要がありそう。

●【完】Deleteの実装 ←テストはしていない
Chordネットワークのルーティング動作の検証自体は put と get でおおむね問題ないが、deleteはデータの
一貫性を考慮すると単純に削除するのではなく、value を "THIS_KEY_IS_DELETED" などの文字列で保持しておく
などしないと、探索が失敗した場合と区別がつかない。レプリケートしていた場合の考慮も必要なのでそこらへんは
シミュレータの時点で仕様記述的な意味でも実装しておきたい。
↑ "THIS_KEY_IS_DELETED" というような文字列をglobal_putしておいて、global_getで取得された値が同文字列
　の場合はエラーにすれば良いだけ。

●【作業中】実システムに落とし込める形にリファクタリング（ノードオブジェクトやノード情報オブジェクトへの
　　　　　　フィールドアクセスを駆使して情報を取得したり更新したりするのはNG）
・【完】まずはTODOコメントなどを用いてリストアップ
　- 【完】ひととおりのリストアップ
　- 【完】他ノードのメソッドの呼び出しのTODOコメントに呼び出しているメソッド名を含めるようにする
・【完】他ノードのフィールドにreadアクセスしているコードを実システムに落とす際にどうすべきか考える
・【完】他ノードのフィールドにwriteアクセスしているコードを実システムに落とす際にどうすべきか考える
　（joinのセカンドノードのルートの一か所にまとまっているので、その単位で専用のAPIとしてしまうのもアリかもしれない）
・【完】他ノードのロックを直接とっているコードを実システムに落とす際にどうすべきか考える 
　　　（少数ではある。メソッド全体を書き換えた方が良い気がする）
　　　　=> 書き換えた
・ 【完】実システムで既に自身のロックを取得済みの場合の、自身のAPI呼び出しをどう扱うか考える（そもそも、1プロセスで実装していた場合、
　　　　 自分自身にソケットでリクエストするということはできないはずなので、相手が自分の場合はメソッド呼び出しで済ます、
　　　　といった分岐が必要か？）
　　　　=> 自分自身と分かっている時はrpc用のメソッドを呼ばないようにしたし、仮にrpc用メソッドを呼び出したオブジェクトが
　　　　　　selfだった場合はラッパーでどうにかする方向でfix
・【完】上記で考えた場所のできるところから修正していく
　　　　　　新たな作業ブランチ: refactor-for-real-system-210304
　- 【完】ChordNodeを返すメソッドが同時にNodeInfoも返すようにすれば他ノードのフィールドへのreadアクセスは解消できそう
　　　　　　　(get_node_by_address, find_successor, closest_preceding_finger）
　 　　　　　あとは、メソッドの引数としてChordNodeを引き回している場合も、同様、かな。
　　　=> 却下
　- 【完】他ノードのフィールドへの直接のreadアクセスを行っている箇所を必要な対処ごとに整理
　- 【完】RPC呼び出しに相当する他ノードのメソッド呼び出しをRPCに置き換える予定のラッパーメソッド
　　　　  の呼び出しに置き換える（ラッパーメソッドも定義する）
　- 【ひとまず完】ノード外に公開するメソッドをノード内から直接呼び出している実装がマズイ感じするので、対処する
　- 【完】同一ノード内で引き回すChordNodeオブジェクトとは？何に置き換えればよい？とか考える
　　　　=> そのノードが提供するRPCを透過的に呼び出せ、ノードに関する情報にreadアクセスできるプロキシオブジェクト
　　　　　　的なものという位置づけとすることにした（あくまで他ノードに対応するものの場合）
・【完】GILの存在しない、真っ当なスレッドになった場合に追加で考慮しなければならない
　　　　　　点を洗い出して実装（gvalモジュール内のオブジェクトへのアクセスがアトミックになるように
　　　　　　しないとならないかも、など）
・【完】シミュレータで行えていた例外機構を用いた例外状態のハンドリングを、ノードを跨いでも伝播できるような仕組みを考えて
　　　　　　シミュレータの状態でも実装しておきたい（Pythonの例外機構による例外はノードを跨いでは伝播しないように書き換える
　　　　　　必要あり）
　　　　　　=> そもそも、Rustには例外機構がないので、returnコードでエラーを呼び出し元に伝えていくコードに書き換えて置く必要がありそう
　- 【完】例外を投げる可能性あるメソッドにTODOコメントをつけて一覧できるようにしてみる
　　- 【完】AppropriateNodeNotFoundExceptionをraiseしている箇所とその先のチェック
　　- 【完】ChorUtil#is_node_alive, get_node_by_address由来のもの
　　- 【完】NodeIsDownedExceptionをraiseしている箇所とその先のチェック
　　- 【完】InternalControlFlowExceptionをraiseしている箇所とその先のチェック
　　- 【完】発生元から伝播していく場合のルートをGraphvizで可視化してみる
　　- 【完】現在のシミュレータの実装、各種パラメータ、実行シナリオにおいて、規定数のノードが安定状態になったあと
　　  　　　の1ノードあたりのstabilize処理はどの程度の時間間隔で動作しているのか確認する（finger table, successorの
　　  　　　ものそれぞれについて）。全ノードについて処理を行うメソッドの開始のログをgrepしてそれらの間の経過時間を
　　　　　　規定ノード数で割れば推定値としては十分のはず。（多量の排他制御により想定よりずっと頻度が小さい可能性
　　　　　　もあるかもしれない）
　　　　------------------------------------------------------------------------------------
	do_stabilize_once_at_alll_nodeメソッドは約4分ごとにコールされていた
	・前提: 存在するノードは100ノード（実際は違うが大局的にはそう）
	・同メソッドの一回のコールでsuccessorの方は20バッチ、ftableの方は2バッチ実行されている
　　　　 https://github.com/ryogrid/rust_dkvs/commit/4a156ee7db3d804b52854f1fc2c9662654f01e35
　　　　 stdout_greped_do_stabilize_once_at_all_node_0_0418_16xx.txt

	successor -> 240 / (100 * 20) = 0.12
	つまり、少なくとも1ノードあたり約120ms間隔で実行されている
	ftable -> 240 / (100 * 2) = 1.20
	つまり、少なくとも1ノードあたり 約1200ms間隔で実行されている

	考察:
	・少なくとも、ftableの方は頻度少なすぎるのでは？
　　　　----------------------------------------------------------------------------------
　　-【完】RustのResult型を用いたエラーハンドリングへの書き換えが用意となるよう、同じ型を模したクラス
　　  　　　　　を用意して書き換える方法を考える（RPC呼び出しの部分は別途考える必要があるが）
　　-【完】上項で考えた内容に基づいて書き換えを行う
　　-【完】100ノード、50ノード規模でのノードkillありでの動作確認（20分程度のランニング）
　　-【作業中】ノードkill時に対象ノードのロックをとるのをやめた場合にどうなるか確認
    　　　　　（対象ノードのメソッド実行中にkill状態になることが発生する）
/*
・RESTインタフェースを想定した場合global_xxxの返り値はラッパーなどを介するにしてもHTTP層より情報量の多い
　エラーコードが返せるようにしておく必要がある
*/

・【ひとまず完】Rustで少なくともリエントラント、できればそれに加えてRWロックが可能なロックライブラリがあるか調べて
　　　　　　　　おく（標準ライブラリで用意されていればベスト）
・【ひとまず完】現在のPython製シミュレータでのロックの保持セクションをコールグラフと照らし合わせて整理する
・【ひとまず完】Pythonでのシミュレータの時点でリエントラントなロックを利用しない実装にできないか検討し、可能そうであれば
　　　　　　実装する（Rustだとロックが所有権だなんだと結びついているようで面倒なことになりそうなので。あとは、現在の
　　　　　　Python製シミュレータも細粒度でロックをとり過ぎてパフォーマンスが出ていないように見受けられるため）
　　　　　　- 基本的に各ノードの処理の起点はgrpcかRESTのエンドポイントなので、そこで必要なロックをとって終わりまで持ち
　　　　　　  続ければよいはず
　　　　　　- ただし、自ノードのエンドポイントを呼び出すケースが現在の実装では存在するため、callerのノードIDを引数に加えて
　　　　　　  calee側のChrodNodeオブジェクトのノードIDと一致していたら、どうこうする、といったケアは必要になるはず（例えば
　　　　　　  ロックをとらないようにする、など）
　　　　　　- 【作業中】reentrantなロックを利用したまま、エンドポイントとなる場所で全てのロックをとって、他の箇所でのロック取得を取り除いた
　　　　　　  　　　　　らどうなるか見てみる（reentrantなロックを用いたままにするのは、自分のエンドポイントを叩いてしまう場合が存在し得るため。
　　　　　　　　　　　　ただ、本当は想定内のもの以外で呼び出しがあった場合はエラーで落とすとかした方がいいのかもしれない）
　　=> 結論としてはある程度試してみたが無理だった（設計を大きく見直すとかすれば別かもしれないが）

●【ひとまず完】シミュレータのRustでの再実装（Rustでの実システムの実装に向けて）
・【ひとまず完】段階的な実装
　-【完】Rustで書かれたある程度の規模のプログラムを読んで実践的な書き方を学ぶ
　-【完】Rustの仕様を踏まえたデータモデリングを完了させる（検証も行った上で）
　　-【完】全クラスのひとまずのstruct定義を実装した（そのままでいけるかは不明。クラス変数の対応はまだ途中）
　　-【完】クラス変数を持っていたクラスの対応
　　-【完】各structのコンストラクタの実装
　　　　　　 https://www.utam0k.jp/blog/2018/05/28/rust_std_default/
　　　　　　 https://doc.rust-lang.org/std/default/trait.Default.html
　　-【完】ランダムにノード情報をラップしたArcなMutexを返す get_a_random_nodeの実装
　　　- 【完】ある程度データモデリングが問題ないか確認できる程度の最低限の動作テストを行う
　　　　- 【完】一部のrouterモジュールのメソッドの実装
　　　　- 【完】ChordNodeのフィールドに定義されているクラスのメソッドは必ず、RcRmRs<ChordNode>型の第一引数を
　　　　　　　   とるようにする
　　　　- 【完】検証用コードの実装と、それが動作することの確認よる検証
　-【完】chord_utilのメソッド群の実装（join処理を動かすところまでに必要なものだけ）
　-【ひとまず完】Chordネットワークの構築が行われる状態までの実装 （レプリカ関連は後回しにする）
　　-【一応完】routerモジュールのメソッド群の実装（結合テスト的なことまではできていない）
　　-【一応完】finger tableのstabilize処理の実装（結合テスト的なことまではできていない）
　　-【一応完】ChordNodeの正式なコンストラクタの実装（結合テスト的なことまではできていない）
　　- 【完】join処理の実装（失敗した場合のリトライは後回し、データのputとgetも後での実装なので
　　　　　　　  データの委譲も後回し）
　　-【完】シミュレータの根っこのところの各スレッドを動作させるあたりの実装（必要なところだけ実装）
　　　↑この時点で、ネットワーク自体の構築ができていないので意味のない結果とはなるが、複数スレッドが並行動作
　　　　してノードが滅茶苦茶な接続関係を持ちつつも増えていき、finger_tableが構築されていくという、複数の別種の
　　　　処理が並行に動作する動作がデッドロックや実行時のpanicなどなく継続するかが確認できる。結果として、
　　　　マルチスレッドなRustプログラムの基本的な実装方法に誤りがないかの動作は確認できるはず（ロック回りや、
　　　　Arc型の扱い、Arc型オブジェクトのborrow、borrow_mutした場合の挙動の認識が正しいか、等）
　　-【完】successorのstabilize処理の実装
　　　=> successorを辿ってのcheck_nodes_connectivityでは正しく環が構成されていることが確認された!
　- 【断念】全データに対して最初に各スレッドがロックをとったままという形を脱した実装に修正しての動作確認
　　- 【完】各スレッドの頭でとった全データに対するロック（gval::global_datas）を解放するようにしてみる
　　- 【完】動作確認
　　　=> 速攻でデッドロックしたので全データロックするように戻した
　　- 【作業中】全データロックを行わずに動作するように修正する
　　　- ↑ひとまず、各ChordNodeのフィールドに対応したミューテックス用ダミー変数を同クラスに追加して
　　　　それによってクリティカルセクションを構成するようにしてみる
　　　　とる順番は、NodeInfoの -> DataStoreの -> TaskQueue の。
　　　　タイムアウトは設定しないでやってみる。
　　　　=> いろいろ頑張ってみたが無理。シミュレータだからこそ無理な感じがする。
　　-【キャンセル】stabilize_successorを複数スレッドで行うよう拡張
　　　　　　　　　（デッドロックする可能性があるのはこれらの間とjoinとの間なので複数スレッド化しての確認をしておきたい）
　　　　　　　　　- 動作確認
　　-【断念】ここでデッドロックが起こるようであれば、クリティカルセクションである区間の整理と、各々のクリティカル
　　  　　　　セクションでロック状態を維持しなければならないデータの整理（ロックの細粒度化のため）を行い修正
　　　　　　（クリティカルセクション内で他ノードのロックを間接的にとってしまうようなRPC呼び出しを行うこと自体が
　　　　　　本来やるべきではない実装？？？）
　　-【キャンセル】上項の対策でもデッドロックするようであれば、デッドロックが発生しうるオペレーションのルートでだけ
　　　　　　　　　  ロック取得時にタイムアウトを設定（根っこで行うだけで済むのが望ましい）
------
・実装関連のアイデア
　- 参照系のオペレーションではオペレーションの開始地点でChordNodeオブジェクトのディープコピーを
　   作成して、引き回す形にすればロック不要で、更新系のオペレーションの邪魔をしなくて良い？
　 （is_aliveフラグをどうにかする必要はあるが）
　- シミュレータでkill処理を実装する場合
　　=> killされたノードが完全に処理を行わなくなった後にis_aliveフラグが落ちるようにすれば中途半端に動き続けるという動作は避けられる？
------

●【完】Rustで実装したシミュレータを実システムに落とし込む - 名前解決システムとして -
・【ひとまず完】実システム化するにあたってのデータモデルの再設計
　以下を守ればデッドロックは起きない
　　（複数データをロックしておかなければならないようなクリティカルセクションは構成できないが、今回はそれで
　　　も問題ない、はず）
　　- 複数のロックを同時に持たない（基本的にメソッド呼び出しする際も持っているロックは手放す？）
　　- ロックを持った状態でRPC呼び出しをしない
　　- 無理ならメソッドの先頭でコピーを作って、それを触るようにする？
・【完】実システム用のディレクトリを作成してコードをコピー
・【完】ノード間のREST RPC呼び出し実装のプロトタイプ作成
・【完】複数プロセスの起動と終了、データのput・get・アドレス解決のリクエストを行うツールの基本部分の作成・動作検証（動作確認に必須）
　- 【完】KVSプログラム側のコマンドライン引数仕様も要検討
・【完】RPC部分以外の実装を終える（データ構造の変更への対応が主、なはず）
・【完】32bit整数（unsigned）に収まる出力なハッシュ関数の実装。なければ、128bit対応が必要
　（前に見つけたChordのRust実装のリポジトリを参考にすれば128bit対応のやり方は一応分かる
　　Rust標準のハッシュ関数が64bitで値を返すのでその下位32bitをとる、というのでよさそう）
・【完】ノード間でのメソッド呼び出しと外部インタフェースのRPC化
　- RPCの呼び出し側の実装
　　- endpointsモジュールに現在呼び出しているRPC名にcallとでも加えた名前のものを定義してREST
　　  APIの呼び出し処理を記述
　　　- 呼び出し先が自ノードであった場合の対処
　　- 現在のRPC呼び出しを上記の呼び出し側用関数の呼び出しに置き換える
　- RPCの受け側の実装
・【完】RESTインタフェースを用いてChordネットワークが正しく構築されているかチェック
　- 【完】このためにノード情報（successorとnode_idが分かればよい）を得るREST API を用意する必要がありそう
　　（CLIツールから叩く。ノード間で利用するAPIで適当なものがあればそれを流用してもよいが）
　- 3ノードで動作確認
　- CLIツール側のチェック処理の実装（返された値をJSONのオブジェクトとして扱えるようにした方が良さそう）
・【完】システムのユーザに対してのRESTインタフェースの用意
　（指定したパーセンテージに対応するノードの情報を返すとか？ポート番号をアドレス情報代わりとして）
・【完】100プロセスぐらい立ち上げようとすると途中で起動したプロセスが死んでいったりするので、
　　　　原因を究明。40プロセスぐらいなら大丈夫みたい。
　　　　RPCのタイムアウトが原因だとすれば、stabilize処理の頻度が大きすぎるというのはあるのかも
　　　　しれないが、10秒に設定してそれでもタイムアウトするというのは考えにくい。
　　　　=> RPCの受け口となるRocketが起動する前に次のノードがjoinしに行くのが原因だったようである。
　　　　　　なので、join時のtyukai nodeを first nodeに固定し、タイムアウトを100秒に伸ばした。
　　　　　　join間の時間も2秒から3秒に伸ばした。
　　　-【完】execする時に1つのファイルに append でリダイレクトさせる形で起動させられないか調べる
　　　　　　=> 無理だったので、プロセスごとにborn_idをサフィックスい持つテキストファイルに書き出されるようにした
・【完】ノードダウン対応
　- successorが死んでいた場合（RPCが通信エラーになった場合全般をケアしないといけない気がする）にpanicせずに、
　　ハンドリングできるようにする
　　- finger tableの適当な当たりのインデックスのノードをsuccessorにすれば多分いける）

●Rustで実装したシミュレータを実システムに落とし込む - 分散KVSとして -
・【完】データベース層の実装（耐故障性は後回し）
　　- 各処理の実装
　　　- put処理の実装（失敗した場合のリトライは後回し）
　　　- get処理の実装（失敗した場合のリトライは後回し）
・【完】RESTインタフェースの実装
　- システム外のノードがRESTで呼び出すglobal_xxxメソッドはラッパーメソッドを呼び出させ、上の方で定めたJSONのフォーマットで
　　返すようにする。
　　なお、global_put（KVSへRESTでputアクセスした際の返り値）の際にユーザがPOSTで与えるデータは特に規定しない。
　　最終的に文字列として受信できれば、JSONでもいいし、何でもいい。base64エンコードされていても、いなくてもどちらも対応する。
・【完】後回しにしていた処理の実装（1: 耐故障性対応のベース）
　-【完】レプリカ周りの実装（委譲処理以外）
　　-【完】レプリカは元のキー文字列に数字を結合したもののハッシュをIDとして
　　　一定数をネットワーク内にばらまく形にする（更新は全てのIDに対してかけて、取得はいずれかが取得できれば良い、とする）
　　　（この場合、ばらまくのはglobal_putのリクエストを受けたノード、という形になるはず）
　　　　=> マスターとレプリカの区別がなくなる
　　　　　=> 委譲処理はばらまく数を多めに設定していれば不要になるはず
　　　　　　（厳密にはした方が良いのだろうが、構築時にノードが全て揃ってから使い始める前提ならjoinはノードダウン同様、それほど発生しないと想定できる）
　　　　　　=> 取得時に2ノード目以降へのトライの場合、データを返した側は、そのデータを
　　　　　　　　他のレプリカを持っているはずのノードにブロードキャストする、とでもすればよいか？←★ほぼ同時にputが起きていた場合に上書きしてしまうリスクあり★
　　　　　　　　（レプリカ番号0番、つまり一応のマスター的なノード以外がレプリカを配れると、更新が同じタイミングで
　　　　　　　　　発生した時に一貫性の問題が出るか・・・。そいつにputの依頼をかけるようにすればいい？）
　　　　 => ★委譲処理をするにしても、get時にレプリカを配りなおすにしても、各データに正確なタイムスタンプがつけられている前提が
　　　　　　 あれば、同時にputが起きていた際に上書きしてしまうリスクはどうにかなる。タイムスタンプはglobal_putのリクエストを受けた
　　　　　　 ノードがばらまき始めた時刻、でよさげ。putリクエストでばらまかれた場合もほぼ同時にglobal_putが発行された場合（同一ノードでも
　　　　　　 複数ノードでも）を考慮してタイムスタンプはチェックした方がよさげ。
　　　　　　 ということは、委譲処理やget処理時にばらまく際はputに引数を加えて区別できるようにしないといけなそう★
　　　　　　　↑データがストアされている時点でglobal_putされた時点のタイムスタンプを持っていれば区別は不要な感
　　-【完】successorは1ノードのままで、死んでいたらfinger tableから適当にノードを引っ張ってくるか、finger talbeから
　　　　　ピックアップしたいくつかのノード情報以外を初期化して、join処理からやり直す、というのでもありな気がする。
　　　　　とか思ったが、ノードの位置を変えたら、元の位置でpredecessorであったノードが同じ状態になってしまうな・・・。
　　　　　finger table内の適当なノードにfind_successorをかけて、新たなsuccessorを見つけるというのが良いかー
　-【完】finger_tableにあるノード情報を使うのではなく、successorをちゃんと複数にする（現状、successorを更新できていないノードがいるので）
・【完】後回しにしていた処理の実装（2: 耐故障性対応以外）
　-【失敗しないので不要と判断】リトライ処理各種（ここまでは失敗したらそのままエラーをクライアントに返してしまう）
・後回しにしていた処理の実装（3: 耐故障性対応残り）
　-【作業中】データの委譲処理（レプリカを再度ブロードキャストして、自分の持っているデータは削除する、という形で済ます？）
　　※レプリカをブロードキャストするような実装をする場合、タイムスタンプを導入しないと、直前のタイミングで発生したputによる更新を
　　　上書きしてしまう可能性が高くなるので注意
　　-【不要だった】join後のデータの委譲処理周り
　　-【不要だった】stabilize_successorで新たなsuccessorを知り、successorに設定した場合の委譲処理
   -【下げるのはダメくさい】stabilize処理の頻度をどの程度まで落としても問題ないか確認して反映
　-【完】20ノード起動時に1/4程度のノードを落としただけでも、global_getでNOT_FOUNDなデータが出てしまう現象が
　　　　　　正常か調査
　　　　　（50個ぐらい試すとざっくり6個ぐらいは出る）
　　　=> putする時のブロードキャストで、同一ノードに連続でputしようとしたら、どうにかする仕組みを入れて
　　　　　レプリカが必ず規定数ある状態にする？（今の実装だとIDをずらしてfind_successorしても同一ノードが現れる場合が
　　　　　あるはずで、その際はレプリカはネットワーク上に規定数存在しない状態となっているはず。ずらすID幅をID空間を
　　　　　割り切れない値に設定して、何周かしてもうまいことズレるようにする？）
　　　　=> put と get の時のID指定がレプリカノードの担当ノードとズレていたためにエラーとなって不正な挙動が発生していた
　　　　　　ということだった
　-【完】check_predecessor で既にpredecessorが設定されていたが更新した場合の委譲処理
　　　　　=> ロジックがそもそもバグっていた
　-【後回し】ノードが死んだ時にレプリカを増やす処理（2番目以降のレプリカを持つノードががgetリクエストを受けた場合、
　　 　　　　必要なはず）
　　※タイムスタンプを（略）
・【完】処理の高速化（追加要件）
　-【完】ノード間通信のgrpc化
　　- 【完】サーバ側のエンドポイントを1つ実装
　　- 【完】クライアント側のコードを1つ実装
　　- 【完】サーバ側のエンドポイントのコードでArMu型でラップして管理している自ノードに関するいくつかの
　　　　　　Mutableなオブジェクトに触れるようにする
　　- 【完】全てのRPCをgRPCに置き換える
　　　-【ひとまず対処できた】謎のソケットエラーの原因を調査する ←★リトライ数は要検討か
　　　　-【完】 自ノードへのRPC呼び出しはローカル呼出しとなるよう全ての箇所を修正する
　　　　-【完】件のエラーが発生した際に一定回数リトライする
　　　　　　　=> これによって謎のソケットエラー問題はひとまずなんとかなった
　　　- 【ひとまず完】ノードダウン対応
　　　　-【完】ひとまずの対処
　　　　　一部で "Error" のメッセージ（どこかで自前で返していたはず）が返ってきたが
　　　　  値を1つputして、10ノードのうち2ノードをダウンさせたところ、生存している8ノードのうち7ノードではgetできた。
　　　　　一部のノードで取得できなかったのはリトライカウントを3（1秒スリープ挟んで）としているところが原因？
　　　　　あとなぜか殺したノードのstdoutX.txtが出力されない
　　　　- 【未解決】getできなかったノードが発生した原因の調査
　　　- 【作業中】REST版に入れて効果のあった一部RPCでやりとりするデータをNodeInfoSummary型にする修正をgRPC版（プーリング無し）
　　　　　　　　　にマージするも動いていない件を調査・対処して動くようにする
　　　　　　　　　（dkvs-grpc-with-tonic-avoid-self-call ブランチ。なお、finger_tableのNoneをほぼ空のNodeInfo型詰める対処でどうにかしている
　　　　　　　　　　ところもどうにかしないと速度向上は見込めない気がする）
　　- 【保留】コネクションプールを実装する（前と同じ方式でgRPCのクライアントオブジェクトを使いまわせばいい？）
　　　　=> なんかうまくいかなかったし、壁が高そうなので一旦サスペンド。プールするのはCliantオブジェクトではなく
　　　　　　tonicのChannelオブジェクトにしないとダメそう。
　　-【完】Golang製CLIツールで、RESTの時と同様にいくつかの操作をgRPC経由で行えるようにする。
　　-【ほぼ完】1ノードがコケたら他のノードも巻き込んで死ぬ原因を調査して修正する（何版だっけ？）
　　-【中止】tokioによる非同期プログラミングを導入したところRocketフレームワークが使えなくなってしまったので、
　　  　　　　代替を探して、導入し、外部向けのRESTインタフェースを実装し直す

・【作業中】ランニングテスト（基本、CLIツールの実装）
　-【RESTで実施済】 全ノード並列 x 各ノードについても並列 で getリクエストを出してみてどの程度のスループットが出るか確認（CLIツールに対応する
　　　　　　　　　　オペレーションの実装が必要。REST版ならRESTで、gRPCのインタフェースしかまだ無い版ならgRPCでglobal_get呼び出しは実装）
　- 【作業中】一貫性がどの程度守れるか複数ノードでのput、getのランニングをCLIツールから行う
　- kill処理用関数の追加
　- ノードを構築時以降に追加する関数の追加
　- データの整合性を確認するロジックの実装（複数ノードからのglobal_getリクエストを行うようにしなければいけないかもしれない）
　- kill処理とjoin処理を行いながらputとgetを行い整合性が崩れていないか、確認するランニングテストのオペレーションの実装
　- （本格的な）ランニングテストの実施
　　- 疑似的に通信遅延を入れた場合も試す
　　（RPCのハンドラ関数の先頭のsleep -> リクエストの遅延、ハンドラ関数の終わりのsleep -> レスポンスの遅延、とすれば良さそう）

・後回しにしていた処理の実装（4:データの整合性関連）
　- global_putを受け付けた時刻をシステム上更新が発生した時刻と定義し、その時刻のタイムスタンプをデータに持たせる
　  ことで、若干前に発行された更新のレプリカへの反映が遅延したとしても、それによるデータの上書きが発生しないようにする

・ 各プロセスのログを1つにまとめたい（必要そうなら）
　（全て結合して時系列で sort コマンドを呼ぶスクリプトでも書けば良いいのだろうか・・・。それともsyslogdのようなものを用意するか）