複数台のマシンでの Mio の性能を上げるためにやろうと思う事

たけまるさんに教えていただいた論文 "Load Balancing and Locality in RangeQueriable Data Structures" を読んで Skip Graph のデータの locality を上げて mio を高速化する方法を考えてみる。

前提条件

  • bucket に特定の key 範囲のデータをまとめる
  • bucket サイズは静的に決める(起動時のパラメータで指定)
  • Max Level も静的に決める(bucket 数は少ないので Level が効き具合は小さい)
  • key はアルファベットの文字列とする a-Z 。

1 台で起動した場合

bucket は 1 つ(O) で始まる。closed になるまで O に追加する。
closed になったら

  • 右側に追加する bucket のキーを範囲指定して(例えば AB - ZZZZZZ) 割り当てる。
  • invariant C - O の形にする

これ以降の追加は論文中の invariant 維持方式でメンテナンスしていく。

2 台目以降が合流した場合

1 台目に 2 台目の到着を知らせる。Global な表に各物理ノードが割り当てた bucket などの統計情報を維持する。
invariant 維持のために bucket が必要になったら統計情報から、bucket を割り当てる余裕がありそうな物理ノードを選んで割り当てる。
※割り当てる余裕が同じなら隣の backet と同じ物理ノードに割り当てても良いかも。

実装に関するメモ

  • bucket 内部の実装は CouchDB の B-tree か、最初は list で。
  • Skip Graph の insert/delete は頻繁には起きなくなるので global lock でも十分かもしれない
  • bucket 内の操作は関連する bucket を lock 。
  • bucket が移動する事はないので bucket = ローカルプロセスとする
  • Global な表は(menesia の memory copy table)を使う

パフォーマンス

  • range search 以外は ETS でさくっと value を返してしまう方がスループットがあがりそう。必要があればやる。