kumofsはなぜ落ちないか

前回は、kumofsはなぜスケールするかということについて紹介しました。その中で最後に、耐障害性もスケーラビリティにとって重要だーと述べました。
そこで今回は、kumofsはなぜ落ちないのか、なぜ耐障害性が高いと言えるのかーということについて紹介したいと思います。

分散システムはテストが難しいことに定評がありますが（たぶん^^;）、その中でも耐障害性の検証は最上級に困難な部類です。
耐障害性は実際のところ、アルゴリズムの設計以前に実装上のバグが大きく影響するので、設計上は耐障害性が高いと言っていても、実際に使ってみると良く止まるという話はありがちな話です。（個人で開発している場合など、開発リソースが小さい場合はなおさら）

そのため耐障害性の高いシステムを実現するためには、実装しやすくバグが入り込みにくい設計も重要かなーと思います（もちろん、アルゴリズムも重要ですが）。

分散システムには複雑な（実装が難しい）アルゴリズムがたくさんありますが、kumofsではかなりシンプルなアルゴリズムだけを採用しています。このため、実装レベルでもそこそこ堅牢になっているハズです。

その実装はソースコードを見ていただくとして^^;　ここでは耐障害性の設計について紹介します。

レプリケーション

まず基本中の基本ですが、kumofsでは1つのデータを3台のサーバにレプリケーションして保存します。
これによってHDDが故障してもデータを保護し、正常な動作も継続させます。

サーバの台数を増やしていくほど、どれか１台のサーバが故障する確率が高くなっていきます。このため1台で構成するシステムと比べても、レプリケーションはさらに重要になります。

障害時の負荷分散

サーバが1台落ちると、落ちたサーバの負荷を他のサーバが肩代わりすることになります。このとき、たった1台のサーバが負荷を肩代わりする設計になっていると、そのサーバの負荷が急に倍増してしまいます：

肩代わりするサーバの負荷があふれてしまうと、一部のデータを取得しにくくなったり、最悪の場合は連鎖的にサーバがダウンしてサービスが停止してしまいます。これでは耐障害性が高いとは言えません。（参考 待ち行列の話：画像配信の負荷分散も比較的簡単？（その1） - 最速配信研究会）

負荷が２倍になっても耐えられるように、通常時には半分以下の負荷しかかからないようにサーバの台数を増やしておく方法もありますが、半分以上のリソースが無駄になってしまうので、効率が良くありません：

そこでkumofsでは、落ちたサーバの分の負荷は全体のサーバ群が分散して肩代わりするようにしています：

それぞれのサーバの負荷に（1/サーバの台数）だけ余裕があれば、1台のサーバが落ちたとしても正常時と同じように動作し続けることができます。

Consistent Hashingと再配置のトラフィック

Consistent Hashingは最近の分散データストアによく使われている基本的な技術で、広く使われているキャッシュサーバであるmemcachedの分散にも使われています。

Consistent Hahsingは元々キャッシュのために作られたアルゴリズムで、サーバの数が頻繁に増減するような環境でも、キャッシュのヒット率を上げることができます。

しかしkumofsはキャッシュではないので、ヒット率は常に100%でないと困ります。このためkumofsは、サーバの数が増減した際にデータを移動（再配置）します。ここでデータの再配置のトラフィック量を削減するために、Consistent Hashingを利用します。

この図は完全ではないですが、イメージはこんな感じです。
剰余を使った分散方法では、サーバを増やしたときに多くのデータを移動させなければなりませんが、Consistent Hashingだと最小限で済みます。

Consistent Hashing + Virtual Node + double-hash-space

以上のようにkumofsの耐障害性は、オリジナルのデータやそのレプリカをどのサーバに保存するかという分散アルゴリズムに大きく依存しています。

このアルゴリズムには、Consistent Hashing と Virtual Node に加えて、double-hash-space（命名は独自）というアルゴリズムを導入しています。このアルゴリズムについてもどこかで紹介したいなーと思います。