複数台のマシンでの Mio の性能を上げるためにやろうと思う事
たけまるさんに教えていただいた論文 "Load Balancing and Locality in RangeQueriable Data Structures" を読んで Skip Graph のデータの locality を上げて mio を高速化する方法を考えてみる。
前提条件
1 台で起動した場合
bucket は 1 つ(O) で始まる。closed になるまで O に追加する。
closed になったら
- 右側に追加する bucket のキーを範囲指定して(例えば AB - ZZZZZZ) 割り当てる。
- invariant C - O の形にする
これ以降の追加は論文中の invariant 維持方式でメンテナンスしていく。
2 台目以降が合流した場合
1 台目に 2 台目の到着を知らせる。Global な表に各物理ノードが割り当てた bucket などの統計情報を維持する。
invariant 維持のために bucket が必要になったら統計情報から、bucket を割り当てる余裕がありそうな物理ノードを選んで割り当てる。
※割り当てる余裕が同じなら隣の backet と同じ物理ノードに割り当てても良いかも。