ではMulti-Raftを実装したライブラリを開発中だという話をした。 通常、Raftというのは1つのクラスタについて定義される。 Multi-Raftというのはこれをシャーディングし、 例えばキーについて[a,b)の範囲はシャード1、[b,c)の範囲はシャード2といった具合に 分散させることである。
上ではキーを辞書順範囲によって区分することを考えたため、26個しかシャードは作らなくて済むが、 ハッシュ値を利用してシャードを作った場合にはこの数は任意に増やすことが出来る。 当然、シャード数が多ければ多いほど多くのリクエストを同時に処理することが出来るし、 また分散ストレージを作るのであれば容量の面でもスケールしやすくなる。
シャード数は最低でも1000、出来れば1万、10万くらいまでは増やせるといい。
しかし、シャードを増やすことは実装上のチャレンジがある。 メジャーなものとして以下の２つが認識されている。
- 大量のリクエストを同時に処理するためには、組み込みストレージがこれらの書き込みを効率よく処理する必要がある。
- シャードを増やした場合、各クラスタ内でのRPC、特にハートビートがネットワークを圧迫する。
おれの開発しているlolraft は、これらの問題に対して２つの最適化を行った。
１つ目の問題に対しては、ストレージはノード内で単一として、 各シャードからのライトは一旦バッファリングし、１つのトランザクションとしてまとめ書きすることにした。 バッファリングの実装によっては、レイテンシが異常に伸びたり あるいはバッファがメモリを圧迫するということがあり得るが、 おれの実装ではこれらの問題をほぼ解消している。 ストレージとしては検討の結果、redbを使うことにした。
２つ目の問題に対しては、これも同様の発想であるが、 ノード間のハートビートを相乗りすることによってRPC自体を削減する。 この効果は数理的に計算出来るが、シャード数が1000近くになると100倍程度の削減効果が得られる。 詳しい計算方法はリポジトリのドキュメントに書いてあるから、興味があったら読んでほしい。
さて、ここまでやってlolraftではざっくりシャード数1000ならば動くようになった。 今は10000を目指して最適化を考えているが容易ではない。
その理由は、これはlolraftのアーキテクチャ特有の問題なのかも知れないが、 大量のタスクが定期実行を繰り返しながら進行していくというモデルであり、 その数はシャード数に比例することが問題となっている。 これら大量のタスクはTokioランタイムで実行されるが、 大量のタスクがキューに先行して突っ込まれているためにハートビートや書き込みリクエストの レイテンシが増大してしまう場合がある。 これによってクラスタが不安定になる。 特にハートビートが遅れることは致命的で、その度に 選挙が行われてしまい、クラスタは応答不能になる。
小さなプログラムを書いて実験した結果、タスク数が10万くらいまでならば スケジューリングのオーバーヘッドは無視出来るレベルだが、 実際のプログラムではそれらのタスクが全く空というわけではないため、 このようなことが起こる。
これに対するアイデアは、ハートビートなどクラスタの安定化に必要なものについては 特権を与えて優先処理させることだが、いまいち良い方法はわかっていない。 Tokioの思想として、タスクのpriorityを与えることは出来ないようである。 いや、出来ますという人がいたら教えてください。