分散Key/Valueストア,Kaiを使ってみよう!

第1回  Kaiとは? ─Kaiのコンセプトとメカニズム

この記事を読むのに必要な時間:およそ 4 分

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

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台が正常に動作している限りデータにアクセスできます(アベイラビリティが維持されます⁠⁠。応答時間が増加することもありません。なお,書き込み失敗により残された古いバージョンは,上述の伝染プロトコルによって,いずれ最新版に置き換えられるようになっています。

図6 Quorumプロトコルの動作例(N:R:W = 3:2:2⁠⁠。クライアントからのリクエストはN=3台のノードに転送され,R/W=2台からの応答でクライアントに返る

図6 Quorumプロトコルの動作例(N:R:

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

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

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

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

Kaiの公式

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

図7 Kaiの公式

図7 Kaiの公式

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

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

著者プロフィール

井上武(いのうえたける)

NTT 未来ねっと研究所 研究主任。オーバレイマルチキャスト,分散データベース,RESTful Web サービスなど,大規模分散システムの研究に幅広く従事。