今回から数回にわたり、Kaiという分散Key/Valueストアについて解説させていただきます。

まず、第1回では井上がKaiのコンセプトをご紹介します。次回以降は、Kai開発者の一人である幾田さんがKaiの利用方法について解説します。最終回では、gooホームでKaiを運用している橋本さんから、Kaiの運用方法について紹介していただく予定です。なお、本連載が対象とするKaiのバージョンは0.4です。

Kaiとは

Kaiとは、分散型のKey/Valueストアです。Amazon.comが2007年に発表したDynamoというシステムに触発されて、そのオープンソース版として開発されています。Kaiをバックエンドに据えてWebサイトを構築することで、高いスケーラビリティやアベイラビリティを実現できます。2009年5月には、gooホームのバックエンドに導入され、運用実績も高まってきました。

Kaiは多数のデータを保存するストレージとして様々な用途に使えます。Kaiが参考にしたAmazon Dynamoでは、ショッピングカート、カタログ、セッション情報などを保存しているようです。

Kaiは、2008年5月に開始されたオープンソースプロジェクトで、sourceforge.netにホストされています。現在は主に3人の開発者によって開発が進められています。開発や運用に関する議論はメーリングリスト上で行われています。日本語のメーリングリストもありますので（というか、日本語がメインですが⁠）⁠、興味のある方は気軽に購読してみてください。

• SourceForge.net: Kai

なお、Kaiという名前は、開発者の一人の出身地（甲斐）からとりました。深く考えずに名付けたので、とても検索性が低いです。Kaiに関する情報を検索するときには、erlang, sourceforge, dynamoなどのキーワードと組み合わせてみてください。

Kaiの特徴

Kaiはコンピュータクラスタによって構成されるデータストアです。データ（値）はキーと対応づけられ、複製されてクラスタに保存されます。クライアントからのクエリは、クラスタ内部で分散的に処理されます。

Kaiには次のような特徴があります。それぞれについて説明します。

• memcache APIを備えたKey/Valueストア
• 高いスケーラビリティ（エラスティシティ）による低い運用コスト
• 負荷分散と信頼性
• 高いアベイラビリティ、短い応答時間、それなりの一貫性
• アクターモデルによる並列プログラミング

以下では、6台のクラスタを用いて説明します。説明の便宜上、ノードがリング状に配置されていますが、物理的なネットワークとは関係ありません（リングの意味はConsistent Hashingと一緒に説明します⁠）⁠。

memcache APIを備えたKey/Valueストア

Kaiは、いわゆるKey/Valueストアのひとつです。ところで、最近はKey/Valueストアという言葉をよく耳にしますが、はっきりとした定義を聞いたことはありません。ここでは、ハッシュテーブルの機能を提供するサーバのことを、Key/Valueストアと呼ぶことにします。任意の値（ビット列）をキーに対応づけて保存し、そのキーを指定して値を取り出します。

RDBMSで用いられる関係データモデルと異なり、Key/Valueストアのデータモデルは非常に簡単です。あらゆるデータ（ビット列に変換されていれば、数値や文字列だけでなく、シリアライズされたオブジェクトであってもかまわない）を、正規化などなしにそのまま保存します。そして、使うときにはキーを指定してデータを取得し、必要であればオブジェクトに復元するなどして、利用します。キーには、空白と改行を含まなければ任意の文字列を指定できます。

Kaiのクライアントはmemcache APIによってデータを操作します。つまり、memcacheクライアントを利用できます。ご存じのように、memcachedは非常に多くのWebサイトで利用されているKey/Valueストアで、多くのクライアント実装が存在します。たとえば、Perl、Ruby、Python、PHP、Java、C#、C/C++、そしてErlangなどがあります。テキストベースのプロトコルなので、telnetから操作することもできます。

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is '^]'.
set foo 0 0 3     （保存コマンド）
bar               （データ）
STORED            （結果）
get foo           （取得コマンド）
VALUE foo 0 3     （データ）
bar               （データ）

Kaiは、memcache APIのうち、基本的な操作（執筆時点ではget(s)、set、delete、quit、stats、version）をサポートします。なお、Kaiはキャッシュではなく永続的なストレージなので、memcachedのように期限（expiration time）を指定することはできません（期限には必ず"0"を指定します⁠）⁠。

memcachedの詳細については、過去の連載「memcachedを知り尽くす」を参考にしてください。

高いスケーラビリティ (エラステシティ) による低い運用コスト

Kaiは分散型のデータストアです。いくつかのノード（厳密にはプロセスなのですが、話を簡単にするためにノードと呼びます) からなるクラスタとして動作します。KaiはP2Pアーキテクチャを採用しています。全体を管理するようなマスタノードがいないため、単一故障点がないという特徴があります。また、ノードの追加除去は簡単で、システム停止やデータ再配置を伴わないため、厳密な容量設計や過剰な初期投資なしにシステムを構築し、運用状況の変化に合わせてその規模を柔軟に調整できます。これは、Kaiを利用する最大のメリットといえるでしょう。

また、Kaiクラスタはスケーラブルです。おそらく、うまく運用すれば100台規模まで拡大できるのではないでしょうか（実験では数十台まで確認しています⁠）⁠。一般的にクラスタシステムでは、クラスタを構成するノードリストをノード間で共有しなければなりません。Kaiでは、この共有方法に伝染プロトコル（ゴシッププロトコルとも呼ばれる）を利用しています。

伝染プロトコルは、多くのノードで情報を共有するときによく使われるプロトコルです。それぞれのノードは、定期的にランダムに選んだノードとノードリストを交換します （⁠伝染病をうつす過程を模擬しています⁠）⁠。これだけのシンプルなメカニズムでありながら、情報を指数的な速度で拡散させることができます。また、途中でいくつかのノードに障害が発生しても、すべてのノードに情報を拡散できます。伝染病の広がる速さや、止めることの難しさを想像していただければ、このプロトコルの特性を理解していただけるかと思います。

伝染プロトコルは簡単なわりによくできていますが、無駄が多いことも事実です。このため、1000台を超える規模で動作させることは難しいでしょう。将来的には、Chord などのより洗練された方式を取り入れていく予定です。

負荷分散と信頼性

Kaiでは、ノード間で分担してデータを保存することで、負荷を分散します。また、それぞれのデータは、指定された数だけ複製されます。どのデータ（正確にはキー）がどのノードに管理されているかを決定するためには、キーとノードを対応関係を管理しなければなりません（ノードリストを伝染プロトコルで共有したのは、このためです⁠）⁠。

簡単には、キー（あるいはキーのハッシュ値）の剰余によって対応付けを行う方法が考えられます。たとえば、あるキーのハッシュ値が1234でノード数が10であれば、4番目のノードにデータを管理する、のように対応づけます。しかしこの方法では、ノードの追加除去に伴って、ほとんどすべてのキーの対応関係が変更されてしまいます。その結果、変更後の対応関係に従ってデータを再配置するときに大きな負荷が発生し、システム全体のスループットに悪影響を与えるかもしれません。

Consistent Hashing を利用すると、ノードの追加除去にともなうデータの再配置を、約1/nに削減できます（nはノード数⁠）⁠。参考までに、クラスタを構成するノード数と再配置されるデータの割合をグラフに示します。剰余ではノード数が増えるほど再配置率が高くなってしまいますが、Consistent Hashingでは逆に低く抑えられることがわかります。

Consistent Hashing のアルゴリズムを簡単に説明します。まず、キーとノードに対するハッシュ値を計算し、図のようにリング上に並べます（このリングは計算のための仮想的な存在で、ノードの物理配置とは無関係です⁠）⁠。キーの後方（時計回り）に存在する N 台のノードを、そのキーの担当とします。つまり、キーに対応する値は、その N台のノードに保存されます。

いずれかのノードがダウンすると、リング上で次に位置するノードが、新たにそのキーの担当となります（実際には、伝染プロトコルによってノードのダウンを通知され、担当であることに気付くと、生存しているノードからデータを取得してきます⁠）⁠。このようにして、データごとに一定の複製数が維持されるため、データは高い信頼性で保存されます。なお、複製数はクラスタごとに設定可能です。

Consistent Hashingについてより詳しく知りたい方は、こちらのページを参考にしてください。

高いアベイラビリティ、短い応答時間、それなりの一貫性

Kaiでのデータアクセスは、悪くてもミリ秒のオーダに抑えられます（厳密には、データサイズや設定によりますが⁠）⁠。このような短い応答時間は、後述の並列プログラミングと、Quorum（定足数）と呼ばれるプロトコルによって実現されています。Quorumプロトコルは、複製の一貫性（複製間でバージョンが一致していること）を保証するためにも一役買っています。

Quorumプロトコルに従うと、値を書き込むときに、N台のノードではなく、W（<= N⁠）⁠ 台のノードに書き込めればよいとされます。また、値を読み取るときには、N台のノードのうち、R（<= N）台から読み取れればOK です。N、R、Wは次の不等式を満たすように設定されます。

R + W > N
W > N/2

最初の不等式は、読み取った値のうち少なくともひとつは、直前に成功した書き込み（つまり、最新バージョン）であるということを意味します。ふたつめの不等式は、連続して書き込みを行ったときに、少なくともひとつは直前のバージョンを上書きできる（最新バージョンを置き換えられる）ことを意味します。

例を挙げて説明します。たとえば、N:R:W = 3:2:2とします（これは、Kaiの典型的な設定例です⁠）⁠。Quorumに従うと、担当するN=3台のノードのうち、少なくともW=2台のノードは最新の値を保存していることになります。ここで、3台からR=2台を選んで値を読み取るとします。Quorumにより、どの2台を選んでも、少なくともひとつは最新の値を保持していることが保証されます。よって、バージョンを比較すれば、最新の値を得られます（バージョン比較はクラスタ内で自動的に行われ、クライアントには最新バージョンのみが返されます⁠）⁠。

このようにして、Quorumプロトコルにより複製のバージョン一貫性が維持されます。さらに、もし3台のうち1台が過負荷や障害に見舞われても、2台が正常に動作している限りデータにアクセスできます（アベイラビリティが維持されます⁠）⁠。応答時間が増加することもありません。なお、書き込み失敗により残された古いバージョンは、上述の伝染プロトコルによって、いずれ最新版に置き換えられるようになっています。

ところが、ごく稀に、この一貫性が失われることがあります。ノードリストは伝染プロトコルによって交換されるため、ノードによって異なるリストを持つ時間が生じるためです。つまり、古いノードリストを持っているノードは、Consistent Hashingによって、間違ったN台のノードを選択してしまうかもしれません。すると、Quorumプロトコルが機能しなくなり、古いバージョンを返す可能性がでてきます。しかし、この不一致は、伝染プロトコルによっていずれ解消されます。このように、Kaiではスケーラビリティやアベイラビリティを優先し、バージョンの一貫性をいくらか妥協しています。

アクターモデルによる並列プログラミング

KaiはErlangというプログラミング言語で書かれています。Erlangは並列プログラミングに適していると言われています。KaiはN台のノードにリクエストを転送するときなどに並列処理を必要とするため、Erlangを採用しました。

Erlangでは、一般的にアクターモデルというプログラミングモデルに従ってソフトウェアを設計します。このモデルでは、多くのアクター（プロセス）を起動し、それらを協調させながら処理を進めます。このとき、共有メモリを使うのではなく、メッセージ交換によって情報をやりとりします。共有メモリを安全に使うためには排他制御が必要になりますが、これを間違いなく行うことは極めて難しいです（経験のある方ならわかると思いますが⁠）⁠。アクターモデルに従ってプログラミングを行うと、この問題を簡単に回避できます。また、Erlangのプロセスやメッセージ交換はよく最適化されています。このため、Erlangを使うと、大きなオーバヘッドなしに、簡単かつ安全に並列プログラミングを行えます。

Kaiの公式

最後に、Kaiの特徴を表す公式を紹介します。

Kaiは、Amazonが開発したDynamoというシステムを参考にしています。Dynamoは、高いスケーラビリティやアベイラビリティ、信頼性を実現しています。クライアントは、memcache APIによってデータを操作します。Kaiは、Erlangという並列プログラミングに適した言語によって開発されています。

次回は、Kaiの基本的な使い方を紹介します。