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

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

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

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

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

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

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

図2 伝染プロトコルの動作例(node2の障害を検出し,ノード間で共有している)

図2 伝染プロトコルの動作例(node2の障害を検出し,ノード間で共有している)

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

負荷分散と信頼性

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

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

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

図3 剰余とConsistent Hashingによる,再配置されるデータの割合

図3 剰余とConsistent Hashingによる,再配置されるデータの割合

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

図4 Consistent Hashingの例(N=3⁠⁠。keyの担当ノードは,リング上で後方に位置するnode2,node5,node4となる

図4 Consistent Hashingの例(

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

図5 Consistent Hashingの例(node2障害時の動作⁠⁠。障害に伴い,リング上で次に位置する node6が新たにkeyを担当する

図5 Consistent Hashingの例(node2障害時の動作)

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

著者プロフィール

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

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