分散ストレージSorockの安定化処理について

この前、Sorockという分散オブジェクトストアを開発し始めたことを話した。このSorockというのは、おれの出身校である麻布学園の創始者江原素六（そろく）に由来することを話した。

今日はその進捗となる。この3週間の間に、大きく2つの実装を行った。 1つは障害検知であり、もう1つは原理の変更である。

難しさの根源

まず、イレージャコードを使ったスケールアウト型の分散ストレージの何が難しいかというと、それはノード障害と、クラスタの変更である。クラスタの変更は、ノード障害によっても引き起こされる。

仮にクラスタが安定していて、ノード障害が一切起こらないとすると、あるいはこれに、クラスタが単調に成長していくだけという制約を付け加えたとしても、実装は非常に簡単になる。

しかしこれは現実的な仮定ではない。実際にはノードは障害を起こすし、ノードを意図的に削除することもある。

Sorockは非常にシンプルなインターフェイスを持つ。 Create K Vは、Kに紐付いたVという値を保存する。ここでVは例えば1MBのデータだとする。 Kとクラスタの情報から、担当ノードの集合が計算出来る。仮に(n,k)=(8,4)のイレージャコードを想定すると、担当ノードを8個選ぶことになる。そして、パリティを含めた250KBのピースを8つの担当ノードに分散することになる。 Read Kは、Kとクラスタ情報から担当ノードを計算し、それらから4つのピースが得られた場合に、元のデータを復元する。

では、担当ノードに選ばれなかったノードは、Kについて知り得るかというと、 Sorockでは「一切知り得ない」というスタンスをとっている。これは、スケールアウトさせるためである。ノードが、全キーの集合について知ることは、その部分がボトルネックとなり、スケールアウトを妨げる。これは、まず知るためのストレージ容量の問題があり、当然、知った上で全キーに対して何かしら処理をすることは、それ自体がスケールしない。つまり、Sorockは、各Kについて独立したストレージのオーバーレイとして表現されていることになる。

ある時、Kの担当ノードのうち、あるノードがミサイルによって爆撃された場合はどうなるだろうか？これは現代においてはさして奇抜なシナリオではない。答えは簡単で、他の担当ノードはそのノードが破壊されたことを知り得ないし、ということはクラスタの中のどのノードも、そのノードが破壊されたことを知り得ない。もし知ろうとすれば、やはりその部分がボトルネックとなる。

つまり、難しさの根源は、お互いのことは何も知らないし、ふんわりとKというキーが保存されているだけなのに、あるピースが消失した時にどうやってそれを復元するかという点にあることになる。なぜならば、ピースを復元出来なければ、やがてピースが消失し、確実にデータロストするからである。（ドキュメントでは、このデータロストに関する数学も行ったので、興味がある人は見てほしい。その数学を元にして、何時間に一回データが復元されれば良いかを計算するプログラムも書いた）

障害検知

唯一知る方法は、障害検知によってノード障害を検知出来た場合だけである。それによって、そのノードがクラスタから除外される。

しかし、この障害検知が暴走し、あらゆるノードをダウン判定するとたちまちピースは全消滅してしまうことになる。従って、false positiveはなるべく少ない方がよいのだが、これに対しては天下り的に On Scalable and Efficient Distributed Failure Detectors に準じた実装を行った。

実装は独立したTonicのサービスとして実装され、他のTonicサービスの上にスタックすることで機能追加出来るライブラリとして実装することが出来た。

v0.0.2では、この障害検知を主に実装した。

安定化とは

新しいクラスタについては、やはり担当ノードが計算出来る。その担当ノードは、元の担当ノードとは変わることがある。

この時まず、古い担当は、自身のピースを新しい担当に所有権移譲することになる。これはsend-piece someというRPCで実装される。

これの他に、Kの存在を知っているノードは、ピースを持っているべきノードに対して send-piece noneというRPCを送り、「お前はそのピースを持っている必要がある」ことを教えることにした。このRPCを受け取ったノードは、そのピースを持っていないならばどうにかして、そのピースを復元する。（ほとんどの場合は、メッセージを受け取るだけで何も起こらない）言い換えるとこれは、削除されたノードが自身のピースをsend-piece someによって送った状況を、他のノードによって再現しているようなことである。比喩的にいえば、生き残ったみんなの力によって、削除された幽霊を召喚しているようなイメージである。

これら2つのRPCによって、ピースをあるべきノードに持たせる行為を「安定化」と呼ぶ。これも比喩的にいえば、ピースが球で、クラスタの状態が地面の歪みだとする場合、球がエネルギー準位の低いところに移動するようなイメージである。

Sorockでは事実上、このsend-piece none RPCによるネットワーク容量の専有がボトルネックとなるが、非常に小さなメッセージであるため、現実的にはあり得ないという計算が立つ。

ある連続した2世代の新旧2つのクラスタを比較したとき、何が削除されたかを知ることは可能であり、それを利用した方がより効率的な実装が出来ると思うかも知れない。実際におれも最初はそのように実装したが、これはうまく行かないことが後にわかった。このように歴史を一つずつたどるような実装は、クラスタ変更のスキップが出来なくなるというデメリットがあり、これが致命的であると判断したのだ。自分の知りうる中でもっとも最新世代のクラスタ以外は全部ゴミとして扱えることは、ノード障害が連続的に起こる可能性を考えると、とても捨てることが出来ない性質であるといえる。

安定化を主役とする

ここまでで、SorockはCreateとReadというオペレーションが出来、常に新しいクラスタの状態に追従するように安定化という処理を行うことがわかった。

ふつうの発想をすると、表の処理であるCreateを主役として、安定化というバックグラウンド処理を裏方のように捉えるだろう。

しかしこの考えではうまく行かないことがわかったため、おれは逆に考え、安定化を主役とすることにし、 Createによるピースの分散はたかだか最適化に過ぎないという立場をとることにした。

つまり、原理主義的なSorockは、 Createを受け取ったノードはまず、自身にすべてのピースを保存する。それらのピースは当然、今現在のクラスタでは各々担当ノードがあるから、安定化によって正しい位置に移譲されるはずである。この考えはDynamoのSloppy Quorum（送り先がダウンしてるなら、とりあえず適当なやつに送っておく）を参考にした。この世界では、Createが計算した担当ノードにピースをばらまくことは、安定化の結果を先取りするだけの最適化に過ぎないことになる。

v0.0.3では、この「安定化が主役だ」という思想を元に実装を変更し、その前提を元にして、メッセージをキューイングしてその中で同一メッセージの重複排除を行うなどの最適化を行った。

実装にはnorpcを使ってメッセージパッシングを主体とした設計を採用していて、サービスの関係は以下のようになっている。 Sorockの開発は、norpcの評価も目的に含むのだが、理論的にどうかは不明として、自身の主観としては、開発がしやすいという感想を持っている。

実装が気になる人は見てみてほしい。そして気に入ったらいいねとチャンネル登録をよろしくお願いします。（Youtuber風）

https://github.com/akiradeveloper/sorock/tree/v0.0.3

次は永続化だ

現在、PieceStoreと呼ばれる、ピースを保存するストレージの抽象は、たった一つ、テスト用のメモリ実装のみを持つ。

v0.0.4では、これに対して永続化をサポートする実装を行う予定だ。実装を進めた結果、PieceStoreのAPIはsqliteでもっともきれいに実装出来そうなので、まずはここからやってみようと思っている。そこまで行けば、あとは今まで作ったものをくっつけてdockerイメージを作って一段落となる。

ユースケース？

Sorockは、ノリで作っているだけなので特にユースケースを考えていないし、使うことを前提に作っていない。例えば、致命的だとヒステリックにならないでほしいのだが、KVペアの上書きは出来ない。

そんなSorockだが、どんな用途があるかと考えてみると、まず素直には、分散ファイルシステムなどのブロックデータを保存するストレージとしては使えそうではある。例えば、ブロックデータに対してハッシュ値をキーとして保存する。ファイルがどのようなブロックデータを持つかは、別にイレージャコードする必要もないので、 TiKVなど別の分散ストレージを使うとかが考えられる。

もう1つぼんやりと頭の中にあるのは、ログとか計算機実験の出力だ。例えばログでいえば、キーを1,2,3と連番をつけて保存していく。読む書きをするときはリクエストを均等に散らせば、スループットもスケールアウトするだろう。ノードに処理機能fを持たせて、書いたVに対してf(V)をリード出来るようにすれば、分散検索なども出来るようになるかも知れない。

こんなユースケースはどうかなというのがあれば、メールででも教えてほしい。