kumofs MessagePack Partty!.org festivoice.net
2010-02-09
■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（命名は独自）というアルゴリズムを導入しています。このアルゴリズムについてもどこかで紹介したいなーと思います。
2010-01-26
■kumofsはなぜスケールするか
先日、分散Key-valueストア kumofs を公開しました。
多く方から反響とフィードバックをいただいています。ありがとうございます。
今回は、kumofs はなぜスケールするのか、なぜスケールすると言えるのかーということについて紹介したいと思います。
ところでスケーラビリティとは何か？
スケーラビリティとは、利用者や仕事の増大に適応できる能力・度合い とされています（端的！）*1 。Scalability を日本語にすると、拡張性 と訳されるようです。
ただ一口でスケーラビリティと言っても、様々な側面があります。ITシステムでは主には処理性能と運用に関することを指す場合が多いと思いますが*2、その中にも様々な側面があります。
なぜスケーラビリティが必要か
スケーラビリティは システムなどが持つべき望ましい特性 であって、高いに越したことはありません。しかし、高いスケーラビリティはタダで実現できるものでもないので、スケーラビリティが「どのくらい」必要なのか、ということも考えておく必要があります。
高いスケーラビリティが必要になる理由には、例えば以下のようなものがあると思います：
- 負荷がとても高くなる
- システムの負荷が高いとき、「チューニング」によって耐えられることもありますが、それでも負荷が10倍や20倍になったら耐えられません。チューニングでは早く限界に達してしまうため、チューニングのスケーラビリティはそれほど高くないと言えます。より高い負荷に耐えられる能力 が重要になります。
- 最初は負荷が低い
- 最初はデータが少なかったり、ユーザーが少なかったりします。最初から大規模なシステムを導入すると、無駄にコストがかかってしまいます。初期投資を抑えるためには、小規模でも高速に動作する能力 が重要です。
- 負荷の予測が難しい
- システムにかかる負荷を事前に予測するのは、かなり難しい問題です。特に、不特定多数のユーザーからアクセスされるサービスだと大変です。必要になったときに すばやく性能を追加できる能力 が重要です。
- 稼働中に拡張が必要になる
- いつ負荷が上がってくるかというと、システムが稼働している間に負荷が上がってきます。性能を追加できるのも重要ですが、その間にシステムが止まるのは困ります。できるだけサービスの動作を妨げずに性能を追加できる能力 が重要です。
- 規模に比例しない運用コスト
- スケーラビリティを制約する原因は、ソフトウェアだけではありません。100台のサーバを管理するのに、1台のサーバを管理するのに必要な手間の100倍の手間かかっていたら、１人では到底管理できません。100人集めると100倍仕事ができるほど人間のスケーラビリティは高くないようなので（笑）、そのうちに運用コストの方がボトルネックになってきます。小さい運用コストで大規模化できる能力 が重要になります。
ここで挙げた能力は、どれもスケーラビリティの種類の１つだと言えます。どの能力を欠いていても、システムの拡張性を制限してしまう可能性があります。
性能以外のスケーラビリティは見落とされがちだと思いますが、運用や人間のスケーラビリティも無視できない要素だと思います。
kumofsのスケーラビリティ
kumofsは、先に挙げた能力がどれも高くなるように設計しています。
性能
kumofsは、サーバを追加するとほぼ線形に性能が向上していきます。今のところ、60台まではスムーズに性能が向上していくことを確認しています（これ以上は試したことがありません^^;）。
このスケーラビリティを得るためにkumofsでは、データを保存する担当のサーバを決める方法に、ハッシュ関数を使っています。データを保存したり取り出したりするときには、キーにハッシュ関数を適用して得られた値から、どのサーバが担当するかを計算します。
データを分散させる別の方法には、「範囲」を使う方法があります。例えばユーザーIDが0〜100のデータはサーバAに、ユーザーIDが101〜200のデータはサーバBに、といった具合で分散させます。
この「範囲」を使う方法だと、データの傾向に偏りがあったときに、負荷も偏ってしまうことがあります。例えば先のユーザーIDの例で、ユーザIDが0のデータに対するアクセスが多かったり、ユーザIDが0のデータが多かったりすると、サーバAの負荷がサーバBより高くなってしまいます。
負荷が偏ると、サーバBより先にサーバAがボトルネックなってしまったりするため、性能が伸びにくくなり、スケーラビリティが悪くなります。
小規模〜大規模
kumofsは、最小では2台で運用でき、2台でも十分に高い性能を発揮します。（一応1台でも構築できますが、耐障害性がないのでオススメしません）
以下のグラフは、1台で運用したときのkumofsの性能と、キャッシュサーバのmemcachedの性能を比較したものです。kumofsはサーバの台数が少なくても、memcachedにも劣らない速度で効率よく動作します。
動的な拡張
kumofsは、システムを動かしたままサーバを追加することができます。サーバを追加すると自動的にデータが再分配されるので、新しいサーバを接続したら、すぐに性能を向上させることができます。
これを実現するために、double-hash-space と命名したアルゴリズムを実装しています。新しいサーバを追加してデータを再分配している最中でも、読み書きを正常通りに行えるようにする仕組みです。double-hash-spaceについては紹介済みだったと思ったら、ブログではまだ書いていなかったので、また今度紹介したいと思います。
サービスの運用を妨げないインフラの拡張
kumofsは、サーバを追加しても、追加している作業中でも、kumofsを利用しているアプリケーションには一切影響しないように設計しています。アプリケーションを再起動したり再設定することなく、いつでもサーバを追加できます。
これには kumo-gateway が大きな役割を果たしています。kumofs-gatewayは、アプリケーションからのI/O要求をkumo-serverに転送するプログラムで、memcachedプロトコル（のサブセット）を実装しています。このkumo-gatewayをアプリケーションを動かすホスト上で起動しておくと、アプリケーションからは「localhostで動いているmemcachedサーバー」のように見えます。これはkumo-serverをいくら追加しても変わりません。つまり、kumo-gatewayは、アプリケーションからサーバの構成を隠蔽しています。
サーバの追加中でもkumo-gatewayが隠蔽してくれるので、アプリケーションには一切影響を与えずに、いつでもサーバを追加することができます。
運用
kumofsには、kumoctl（構成を取得・変更する）やkumotop（負荷をモニタリングする）といった管理ツールを用意しています。これらの管理ツールはどれも、多くのサーバを一括して扱えるように実装しています。サーバの台数が10台になっても20台になっても操作方法が変わらないので、規模が大きくなっても運用の手間が増えません。
kumotopを使うと、↓このように複数のサーバの負荷を同時に監視することができます。
スケーラビリティと耐障害性
スケーラビリティと耐障害性は切り離せない問題です。
サーバの台数を増やしていくほど、どれか１台のサーバが故障する確率が高くなっていきます。サーバの台数が多くなると、毎日どこかのサーバが故障するような状態に近づいていきます。このため、レプリケーションなどの耐障害性を高める機能を追加しないと、まともに動き続けられなくなってしまいます。
kumofsは、レプリケーションやConsistent Hashing、Virtual Nodeなどを使って、サーバが故障してもアプリケーションには影響しないようにしています。
kumofsの耐障害性については、また今度詳しく紹介したいと思います（たぶん^^;）。『雲の世界の向こうをつかむ クラウドの技術』
2010-01-20
■kumofsのリリースを更新しました
kumofs-0.3.1 と、msgpack-0.4.1 をリリースしました。
msgpack-0.4.1
CentOS 5など*1で kumofs を ./configure したときに Can't find msgpack library と表示されて止まってしまう問題を、検出できるようにしました。
これは MessagePack の方に原因があり、コンパイル先のCPUアーキテクチャが、アトミックなインクリメントやデクリメントをサポートしていないほど古いIntelアーキテクチャ（=i386）だったときに、不完全なバイナリになっていました。
msgpack-0.4.1では、これを ./configure するときに検出して、エラーメッセージを出して停止するようにしました。エラーメッセージが出たら、./configure に CFLAGS="-march=i686" CXXFLAGS="-march=i686" フラグを追加してください。
それから、strict-aliasing rule の問題があったのを修正しました。参考文献： strict aliasing rule
kumofs-0.3.1
kumofs-0.3.1は、FreeBSDでコンパイルできるようになりました。Jun Kuriyama@FreeBSD.org さんにパッチを送っていただきました。ありがとうございます！
それから、msgpackc ライブラリをリンクするようにしました。これで -Wl,--as-needed の問題は解決したと思いますが…どうでしょう？ kumofsのGentoo用パッケージを速攻で作った
kumofsのインストール
kumohashの表示は、0がオリジナルデータが保存されるサーバーで、1と2はレプリカが保存されるサーバーになります。
*1：gcc-4.1で、uname -a | grep i386 が表示される環境など
2010-01-18
■分散Key-Valueストア「kumofs」を公開しました！
分散Key-Valueストア kumofs を、本日オープンソースソフトウェアとしてリリースしました！
kumofsとは？
kumofs（クモエフエス）は、実用性を重視した分散データストアです。レプリケーション機能を備え、一部のサーバーに障害が発生しても動作し続けます。単体でも高い性能を持ちながら、サーバーを追加することで読み・書き両方の性能が向上する特徴を持ち、低コストで極めて高速なストレージシステムを構築・運用できます。
kumofsの大きな特徴は、システムの構成の簡単に変更できる点です。システムを止めることなく、簡単な手順でサーバーを追加したり復旧したりできます。アプリケーションには一切影響を与えません。
またkumofsは、広く利用されている分散キャッシュシステムの「memcached」と互換性のあるプロトコルを実装しています。多くのプログラミング言語向けに提供されているクライアントライブラリを使って、簡単にアプリケーションから利用することができます。
今日発売の『Software Design』では、kumofsのアーキテクチャや使い方について紹介しました。
kumofs は、サーバーの「数」を増やし ていくことで性能を高めていく、いわゆる「スケール アウト」が可能なシステムです。
もちろん、単に数を集めるだけでは役に立ちません。 サーバー同士が相互に通信しながら、連携して動作する必要があります。
そこで本章では、kumofsではどのようにして高いスケーラビリティを実現しているのかについて解説します。
このほかに Software Design 2月号では、kumofs以外のKey-Value Storeの特性や、技術的に突っ込んだ内容も分かりやすくまとめられているので、オススメです。mixiやGREEなど、実際のWebサービスでのKey-Value Storeの運用事例も紹介されています。
kumofsのアーキテクチャ
kumofsは、サーバー同士が直接通信士合うP2P型のモデルに加えて、全体を統括する管理サーバーを組み合わせた、ハイブリッド型の設計を採用しています。kumofsのクラスタは、以下の３種類のプログラムで構成されます：
- kumo-manager
- 全体の統括を行う管理サーバー。２台で冗長化構成をとることが可能。
- kumo-server
- 実際にデータを保存するサーバー。レプリケーションも行う。
- kumo-gateway
- アプリケーションとkumo-serverの間を取り持つプログラム。アプリケーションを動かすサーバー上で１つずつ動かしておく。
kumo-gatewayは、memcachedと互換性のあるプロトコルを実装しています。このためアプリケーションからは「localhostで動作しているmemcachedサーバー」のように見えます。
これはサーバーの構成をいくら変更しても変わらないので、kumofsをアプリケーションから分離して管理やすくなります。
管理ツール
kumofsには上記の３つのプログラムの他に、クラスタの構成を操作したり、状態を監視したりするツールが含まれています。
サーバーの台数が増えても管理の手間が増えないように、サーバーの管理は管理サーバーを介して一括して行えるようになっています。
- kumoctl
- クラスタ全体の構成を変更したり、状態を取得したりするツール。データのバックアップを作成するときにも使う。
- kumostat
- サーバー１台１台の状態を取得するツール。様々な統計情報や保存されているデータの件数などを取得できる。
- kumotop
- topコマンドのように、すべてのサーバーの状態をリアルタイムで監視できるツール。
kumotopを使うと、↓このように負荷をモニタリングできます。
6台のサーバーを使ってkumofsのクラスタを構築して、それぞれサーバーでベンチマークツールを実行したものです。「QPS」の欄を合計すると、全体で65万request/secくらいのスループットが出ていること分かります。
kumofsの導入と検証
kumofsの最新のリリースは、ここからダウンロードできます：ダウンロード
詳しい使い方は、kumofs のドキュメント を参照してください。インストール方法やチュートリアル、障害時の対処方法などを記載しています。
kumofsに関する情報
kumofsに関する情報は、このブログで随時お知らせしていく予定です。
kumofsのプロジェクトサイトはgithubにあります：kumofs＠github
最新の情報を得るには、Twitter（@frsyukiや#kumofs）が一番早いかもしれません。（ハッシュタグは #kumofs でいきましょう！）
2010-01-17
■kumofs関連資料まとめ
- 2008-08-16 バイナリシリアライズ形式「MessagePack」 ノード間の通信プロトコルに利用しているMessagePackについて
- Protocol Buffersは遅い GoogleのProtocol BuffersとMessagePackの性能比較
- 2009-02-20 Key-Value Store 勉強会
- Key-Value Store 勉強会を開催しました。 - moratorium
- 「キー・バリュー型データストア」開発者が大集合した夜 - ITpro
- Key Value Store勉強会に行ってきました by kumofsのひと
- 発表資料 kumofsの設計と、再配置アルゴリズムの解説（ちょっと古い）
- マルチコア時代の高並列性IOアーキテクチャ Wavy kumofsが採用しているI/Oアーキテクチャについて
- 2009-06-11 Interop 2009 クラウドコンピューティングコンペティション
- memcachedを超える成果も、Interopで若手技術者がクラウドを支える技術を競う - ITpro
- 第１回クラウドコンピューティングコンペティション結果 - Geekなページ
- Interopクラウドコン優勝は「えとらぼ」分散key-valueストレージ kumofs
- 発表資料（PDF） kumofsの特徴と性能について
- 発表資料（クリックで進む動画） うにうに動く
- ポスター 短くまとめた概要
- パンフレット kumofsの分散アルゴリズム（Consistent Hashing + double-hash-space）について
- 2009-11-05 『雲の世界の向こうをつかむ クラウドの技術』
- 2009-11-19 Shibuya Perl Mongersテクニカルトーク#12 NoSQL特集
- 2010-01-18 『Software Design 2010年2月号』 〜ほんとうに知りたいあなたのための〜 key-valueストア講座
- 2010-01-18 分散Key-Valueストア「kumofs」を公開しました！ kumofs公開
- 2010-01-18 kumofs での Data::Model の使い方 - YappoLogs 「Data::Model から kumofs を実際にどうつかっているかを紹介しようかとおもいます」
- 2010-01-18 kumofsを使う - さくらインターネット創業日記 「kumofsの詳細については、さくらインターネット研究所に任せることにして、今回は一般にソースが公開されたこともあるので個人的にインストールした際のログを紹介します」
- 2010-01-18 kumofsの死活監視はこんな感じでNagiosでやってます - (ひ)メモ 「kumofsをサービスで使いたい人の一助になればと思い、ぼくが実際に行っている kumofs の監視について紹介したいと思います」
- 2010-01-26 kumofsはなぜスケールするか
こんな感じのパッチでいかがでしょうか。
http://gist.github.com/281788
http://git.sourceforge.jp/view?p=msgpack/msgpack.git;a=commit;h=5abc9ef916c67314d1406509a5102fb29c6111a3