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

第3回Kaiの詳細(1) ─Kaiの要であるクラスタを極める

前回Kai のインストールと基本的な使い方を説明しましたので、今回は、Kai最大の特徴であるクラスタついて詳しく説明します。

なお、前回同様、本連載が対象とするKaiのバージョンは0.4、ErlangのバージョンはR13Bです。

データの保存・取得とリクエストの転送

memcachedでは、クライアントがデータの場所を決定します。このため、クライアントは、クラスタを構成するすべてのmemcachedノードを把握していなければなりませんでした。

一方Kaiでは、ノードがデータの場所を決定し、クライアントからのリクエストを適切なノードに転送します。クライアントは、すべてのノードを把握する必要がありませんし、L4ロードバランサで機械的に負荷分散することもできます。また、クラスタへノードが追加されても、クライアントのノード一覧を修正する必要がありません。

では、前回、構築した3ノード構成のクラスタへデータを保存・取得をする事で、リクエストの転送を試してみます。

次のようなPerl Scriptを用意し、kai_test_cluster.plという名前で保存してください。

リスト1 kai_test_cluster.pl
#!/usr/bin/env perl

use strict;
use warnings;

use Test::More tests => 3;
use Cache::Memcached;

my $set_only_mem = Cache::Memcached->new({
    servers => [map {'127.0.0.1:1121' . $_} (1..3)],
});

$set_only_mem->set(foo => 'bar', 0,); # Consistent Hashing により一つのノードを選択し、データを保存する

for (1..3) {
    my $get_only_mem = Cache::Memcached->new({
        servers => ['127.0.0.1:1121' . $_],
    });
    is $get_only_mem->get('foo'), 'bar'; # 全てのノードから同じ値が取得できる
}

memcachedと異なり、保存リクエストを送るノードと、取得リクエストを送るノードは、異なっていても構いません。前述の通り、クラスタ内で適切なノードに転送されます。

では、実行してみます。

$ perl /path/to/cluster_test.pl
1..3
ok 1
ok 2
ok 3

このような実行結果となれば、リクエストの転送が正常に行えています。

ノードの追加・除去による自動データ再配置

memcachedでは、ノードを追加・除去するとキャッシュミスが発生します。その場合、クライアントはデータをデータベースから再取得して、新しいデータ配置に従って保存し直します。

一方Kaiでは、データの永続性を保証するために、ノードの追加・除去を検知して、データを自動的に再配置します。クライアントは、除去されたノードへのアクセスを停止する以外に、何もすることはありません。もちろん、新たに追加されたノードからも、過去に保存したデータを取得できます。

では、先ほどのクラスタへ新たなノードを追加し、それらのノードから先ほど保存したデータが取得できるか試してみます。

まず始めに、kai4.configという設定ファイルを作成してください。

$ /path/to/make_kai_config.sh 4

続けて、新しいノードを起動します。

$ /path/to/start_kai.sh kai4

次に、新しいノードをクラスタへ参加させます。

$ /path/to/remsh.sh kai1
Erlang R13B (erts-5.7.1) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
(kai1@centos)1> kai_rpc:check_node({{127,0,0,1}, 11011}, {{127,0,0,1}, 11014}).     % (a)
ok
(kai1@centos)2> kai_rpc:check_node({{127,0,0,1}, 11014}, {{127,0,0,1}, 11011}).     % (b)
ok
(kai1@centos)3>                  <- 作業が終わったので、local shell に切り替える
User switch command
 --> s
 --> c
Eshell V5.7.1  (abort with ^G)
(kai_controller@centos)1> q().
ok

前回は、説明を簡略化するため、クラスタ構成時のノード間通信の説明を省きました。しかし、クラスタを運用する際に必要となる知識であるため、ここで説明します。

まず (a) で、既にクラスタに参加しているノードkai1に、新たなノードkai4を確認しろと指示しています。すると、kai1はkai4へnode_listリクエストを送信します。

node_listリクエストを受信したノードは、送信元ノードに対して、自身を含む、自身が持つノードの一覧を返します。kai4は、自分自身の情報しか持たないため、kai1にはkai4の情報のみ返します図1 矢印1⁠。

各ノードは定期的に、ランダムに選んだノードとノード一覧を交換しているため、kai1が取得した情報はすぐにkai2、kai3へと伝わります図1 矢印2⁠。

最後に (b) で、kai4にkai1を確認しろと指示しています。すると、kai4はkai1にnode_listリクエストを送り、kai1からkai1、kai2、kai3の情報を受け取り図1 矢印3⁠、クラスタが完成します。

図1 クラスタ {kai1、kai2、kai3} にノードkai4を追加する例
図1 クラスタ {kai1、kai2、kai3} にノードkai4を追加する例

それでは、次のようなPerl Scriptを用意し、kai_test_cluster_get4.plという名前で保存してください。

リスト2 kai_test_cluster_get4.pl
#!/usr/bin/env perl

use strict;
use warnings;

use Test::More tests => 1;
use Cache::Memcached;

my $mem = Cache::Memcached->new({
    servers => ['127.0.0.1:11214'],
});

is $mem->get('foo'), 'bar';

用意したPerl Scriptを実行し、データを取得してください。

$ perl /path/to/kai_test_cluster_get4.pl
1..1
ok 1

このような実行結果となれば、クラスタへ新規に追加したノードから、データの取得が正常に行えています。

では、クラスタへ更にノードを複数追加し、古いノードを停止した後に、データが失われていないか試してみます。

まず始めに、追加するノードの設定ファイルを作成し、ノードを起動してください。

$ /path/to/make_kai_config.sh 5 6
$ /path/to/start_kai.sh kai5 kai6

次に、クラスタに新しいノードを参加させます。

$ /path/to/remsh.sh kai1
Erlang R13B (erts-5.7.1) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
(kai1@centos)1> kai_rpc:check_node({{127,0,0,1}, 11014}, {{127,0,0,1}, 11015}).    % (c)
ok
(kai1@centos)2> kai_rpc:check_node({{127,0,0,1}, 11015}, {{127,0,0,1}, 11016}).    % (d)
ok
(kai1@centos)3> kai_rpc:check_node({{127,0,0,1}, 11016}, {{127,0,0,1}, 11014}).    % (e)
ok
(kai1@centos)4> 
User switch command
 --> q

基本的には、kai4をクラスタへ追加した場合と理屈は同じですが、少し複雑であるため、補足説明します。

(c) で、kai4にkai5を教える事で図2 矢印1⁠、kai5の情報は、kai4からクラスタ全体へ伝わります図2 矢印2⁠。

(d) で、kai5にkai6を教える事で図2 矢印3⁠、kai6の情報は、kai5からクラスタ全体へ伝わります図2 矢印4⁠。

(e) で、kai6にkai4を教える事で図2 矢印5⁠、kai6はkai4からクラスタ全体の情報を受け取り、kai5もkai6からクラスタ全体の情報を受け取ります図2 矢印6⁠。

図2 クラスタ {kai1、kai2、kai3、kai4} にノード {kai5、kai6} を追加する例
図2 クラスタ {kai1、kai2、kai3、kai4} にノード {kai5、kai6} を追加する例

これで、クラスタを構成するノード数は、6個となりました。なお、クラスタを構成する手順は、0.4以降のバージョンで簡略化される予定です。

クラスタが3個のノードで構成されていた頃から、データを一度も保存していませんが、前述の通り、全てのノードからデータを取得する事ができるか試してみましょう。

次のようなPerl Scriptを用意し、kai_test_cluster_get456.plという名前で保存してください。

リスト3 kai_test_cluster_get456.pl
#!/usr/bin/env perl

use strict;
use warnings;

use Test::More tests => 3;
use Cache::Memcached;

for (4..6) {
    my $mem = Cache::Memcached->new({
        servers => ['127.0.0.1:1121' . $_],
    });
    is $mem->get('foo'), 'bar';
}

用意したPerl Scriptを実行し、クラスタへ新規に追加したノードからデータを取得してください。

$ perl /path/to/kai_test_cluster_get456.pl
1..3
ok 1
ok 2
ok 3

このような実行結果となれば、クラスタへ新たに追加したノードからデータの取得が正常に行えています。

では、古いノードを停止します。それぞれのデータはN=3個ずつ複製されていますので(設定ファイルのnを参照⁠⁠、当たり前ですが、3個以上のノードをほぼ同時に停止すると一部のデータが失われる可能性があります。

ここでは、少し時間をずらしながら3個のノードを順に停止してみます。

$ /path/to/remsh.sh kai1
Erlang R13B (erts-5.7.1) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
(kai1@centos)1> q().
ok
(kai1@centos)2>
User switch command
 --> r kai2@centos                    <- r で別のリモートシェルに切り替える
 --> c
Eshell V5.7.1  (abort with ^G)
(kai2@centos)1> q().               <- データの再配置が終わるまで、数秒待ってから停止
ok
(kai2@centos)2>
User switch command
 --> r kai3@mbp
 --> c
Eshell V5.7.1  (abort with ^G)
(kai3@centos)1> q().
ok
(kai3@centos)2>    
User switch command
 --> q

これで、初期にデータを保持していた古いノードは全て停止し、クラスタを構成するノードは、新たに追加した3個のノードとなりました。

では、先ほど用意したPerl Scriptを実行し、各ノードからデータを取得してください。

$ perl /path/to/kai_test_cluster_get456.pl
1..3
ok 1
ok 2
ok 3

このような実行結果となれば、ノード間のデータ再配置が正常に行われています。Kaiのクラスタでは、ノードの追加・除去にかかわらずデータが永続化されている事がお解り頂けたでしょうか?

Quorum(定足数)ベースプロトコル

本連載では "Quorum" という言葉を何度か用いましたが、ここで詳しく説明します。

なお、Quorumアルゴリズムはクラスタ内部で実行されるため、単にKaiを利用するだけであれば、このアルゴリズムを理解する必要はありません。ただし、サービスに合わせてKaiをチューニングする際には、Quorumの理解が必須となります(設定ファイル中のn、r、wのことです⁠⁠。

Quorumを一言で説明すると、⁠データはN個に複製されるが、取得はN個中R個からのみ成功すればよく、同様に保存はN個中W個に成功すればよい」というアルゴリズムの事です。

なお、保存する際には、データにバージョン番号を付加し、取得する際には、取得したデータの中から最新バージョンを選択して返します。

Kaiは、データを担当するN個のノードに対して一斉にリクエストを送信し、取得であればR個、保存であればW個のレスポンスを受信した時点で、残りのレスポンスを待たずにクライアントへレスポンスを返します。

実際のサービス運用でQuorumの設定値を決定する際は、以下の事を念頭に入れてください。

Quorum考慮する内容
N常にデータの複製をN個、クラスタ内に保持する事を保証するため、ノードが停止すると別のノードが複製を保持するノードとして選択され、データの再配置が行なわれます。
ただし、複製を保持するN個のノードが「ほぼ同時に停止」するとデータは失われます。
大きな値を設定すると、障害耐性は向上しますが「W + R > N」条件により、W、R共に大きな値を設定する必要があります。
R大きな値を設定すると、データ取得のレスポンス速度は低下しますが、⁠W + R > N」条件により、Wを小さな値に設定できます。
逆に、小さな値を設定すると、データ取得のレスポンス速度は向上しますが、Wに大きな値を設定する必要があります。
W大きな値を設定すると、データ保存の応答速度は低下しますが、⁠W + R > N」条件により、Rを小さな値に設定できます。
逆に、小さな値を設定すると、データ保存の応答速度は向上しますが、Rに大きな値を設定する必要があります。
また、⁠W > N/2」条件を満たす必要があります。

表中にあるQuorumの条件「W + R > N」は、Write/Read Conflictを防ぎ、⁠W > N/2」は、Write/Write Conflictを防ぎます。

Write/Read ConflictとWrite/Write Conflictの意味は、以下のQuorumの例と共に説明します。

例えば、N:R:W = 3:2:2である場合、Quorumの条件を満たしているため、Conflictは発生しません。

以下の図は、9個のノードで構成されたクラスタから、データの複製を持つノードとして {D, E, F} が選択され、2個のノード {D, E} に保存を行った例ですが、取得のために2個のノードを、どのような組み合わせで選択したとしても、最低1個のノードは、最新のデータを保持しているので、期待されたデータを正常に取得する事ができます。

図3 Quorum N:R:W = 3:2:2 の例(Conflict無し)
図3 Quorum N:R:

N:R:W = 3:1:3である場合も、Quorumの条件を満たしているため、Conflictは発生しません。この場合、保存するためには、全ノードの合意が必要ですが、取得するためには、1個のノードの合意だけで済むため、更新頻度が低く、参照頻度が高い場合に有利な設定となります。

図4 Quorum N:R:W = 3:1:3 の例(Conflict無し)
図4 Quorum N:R:

N:R:W = 3:1:2である場合、⁠W + R > N」を満たしていないため、Write/Read Conflictが発生します。以下の図は、2個のノード {D, E} に保存を行なった例ですが、ノードFから取得を行うと、期待されたデータを取得する事に失敗します。

図5 Quorum N:R:W = 3:1:2 の例(Write/Read Conflict有り)
図5 Quorum N:R:

N:R:W = 3:3:1である場合、⁠W > N/2」を満たしていないため、Write/Write Conflictが発生します。以下の図は、ノードDに保存を行った後、更にノードFに保存を行った例ですが、この時点で既に、同じキーであるにも関わらず因果関係のない異なる2つのデータがクラスタ内に存在しているため、取得を行った際には、2つの値を取得する事になります。

ただし、最終的にデータはN個に複製されるため、ノードDに保存した直後に、ノードFに保存しなければ、Write/Write Conflictは発生しません。このような設定はKaiのサポート外であるため、避けるべきです。

なお、Write/Write Conflictが発生すると、取得時に複数の値がクライアントへ戻されるので、新たに正しい値を保存する事で修正する必要があります。詳しい説明は後で述べます。

図6 Quorum N:R:W = 3:1:3 の例(Write/Read Conflict有り)
図6 Quorum N:R:

KaiのQuorumのデフォルト値は、N:R:W = 3:2:2が設定されています。これには、以下の理由があります。

  1. データの喪失を避けるため、複数のノードにデータの複製を保持する(N > 1)
  2. 書き込みのレスポンス速度を向上させる(N > W)
  3. 読み込みのレスポンス速度を向上させる(N > R)
  4. (1の条件⁠⁠ - ⁠3の条件)を満たす最小のN(N = 3)

なお、Dynamoの論文の中に、Amazonでは基本的にDynamoをN:R:W = 3:2:2で運用しているという一文があります。

何か特別な事情が無い限りは、Quorumの設定値としてN:R:W = 3:2:2を推奨します。ただし、保存よりも取得がパフォーマンスの重要な要素であるならばN:R:W = 3:1:3も検討の余地があります。

Write/Write Conflictについての蛇足

前述の通り、Quorumに不適切な値を設定するなどにより、Write/Write Conflictが発生します。その際、Kaiは、memcachedプロトコルではサポートしきれいない振る舞いをする事があります。

ここで述べる事は、実サービス環境では考慮する必要がほとんど無いため、Kaiの内部動作に興味のある方のみお読み頂いても構いません。

では、Write/Write Conflictを意図的に発生させ、実際にどのような値が戻るか試してみましょう。

何らかの理由によりクラスタが分裂している際に、それぞれのサブクラスタに対してデータを保存すると、Write/Write Conflictが発生するので、それを利用します。

まず始めに、次のような設定ファイルを作成し、それぞれ、kai_wwc1.config、kai_wwc2.config、kai_wwc3.config という名前で保存してください。

リスト4 kai_wwc1.config
[{kai, [
    {rpc_port, 11011},
    {rpc_max_processes, 30},
    {memcache_port, 11211},
    {memcache_max_processes, 10},
    {max_connections, 32},
    {n, 3},
    {r, 3},
    {w, 1},
    {number_of_buckets, 1024},
    {number_of_virtual_nodes, 128},
    {store, ets},
]}].
リスト5 kai_wwc2.config
[{kai, [
    {rpc_port, 11012},
    {rpc_max_processes, 30},
    {memcache_port, 11212},
    {memcache_max_processes, 10},
    {max_connections, 32},
    {n, 3},
    {r, 3},
    {w, 1},
    {number_of_buckets, 1024},
    {number_of_virtual_nodes, 128},
    {store, ets},
]}].
リスト6 kai_wwc3.config
[{kai, [
    {rpc_port, 11013},
    {rpc_max_processes, 30},
    {memcache_port, 11213},
    {memcache_max_processes, 10},
    {max_connections, 32},
    {n, 3},
    {r, 3},
    {w, 1},
    {number_of_buckets, 1024},
    {number_of_virtual_nodes, 128},
    {store, ets},
]}].

N:R:W = 3:3:1であるため、⁠W > N/2」を満たしていない点に注目してください。

次に、ノードを起動します。

$ /path/to/start_kai.sh kai_wwc1 kai_wwc2 kai_wwc3

次のようなPerl Scriptを用意し、kai_test_wwc_set.plという名前で保存してください。

リスト7 kai_test_wwc_set.pl
#!/usr/bin/env perl

use strict;
use warnings;

use Cache::Memcached;

for (1..3) {
     my $mem = Cache::Memcached->new({
        servers => ['127.0.0.1:1121' . $_],
    });
    $mem->set(foo => 'bar' . $_, 0,);
}

W=1であるため、クラスタを構築する前に、データを保存する事ができてしまいます。用意したPerl Scriptを実行し、各ノードにデータを保存してください。

$ perl /path/to/kai_test_wwc_set.pl

これで、各ノードに同じキーでありながら異なる値を持つデータが保存されている状態となりました。

次に、クラスタを構築します。

$ /path/to/remsh.sh kai1_wwc1
Erlang R13B (erts-5.7.1) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
(kai1_wwc1@centos)1> kai_rpc:check_node({{127,0,0,1}, 11011}, {{127,0,0,1}, 11012}).
ok
(kai1_wwc1@centos)2> kai_rpc:check_node({{127,0,0,1}, 11012}, {{127,0,0,1}, 11013}).
ok
(kai1_wwc1@centos)3> kai_rpc:check_node({{127,0,0,1}, 11013}, {{127,0,0,1}, 11011}).
ok
(kai1_wwc1@centos)4>
User switch command
 --> q

では、データを取得します。ここでは、実際にどのようなデータが戻るか確認するため、 Telnetを使用します。

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is '^]'.
get foo
VALUE foo 0 4
bar1
VALUE foo 0 4
bar2
VALUE foo 0 4
bar3
END
quit
Connection closed by foreign host.

ご覧の通り、KaiではWrite/Write Conflictが発生すると、全ての値を返します。これは、Write/Write Conflictはクライアントで解決するというDynamo の思想を反映した振る舞いです。

ここでは、保存した順番に値が並んでいますが、実際の並び順は、始めの値が自ノードに保存されている値、以降は、レスポンスが早い順であるため、同じノードに接続したとしても、常に同じ並び順で値が返される保証はありません。

一般的なmemcachedクライアントは、データ取得時に複数の値が戻る事を想定していないため、一つの値しか取得する事ができず、基本的には、どの値が戻るか解りません。

前述の通り、Kaiでは、クライアントで全ての値を比較検討し、正しい値を再び保存する事でWrite/Write Conflictを解消する事を期待しているのですが、既存のmemcachedクライアントを使用すると、全ての値を比較検討する事ができません。

よって、実サービス環境では、Write/Write Conflictを発生させない事が非常に重要です。Quorumの設定値は慎重に検討し、サブクラスタへのデータ保存を絶対に行わないようにしてください。

以下は、筆者が動作確認を行ったライブラリの一覧です。

言語クライアントバージョン実装戻り値
PerlCache::Memcached1.26Pure Perl最後の値
 Cache::Memcached::Fast0.14XS(独自実装)最初の値
 Cache::Memcached::libmemcached0.02009libmemcached最後の値
Rubymemcache-client1.7.2Pure Ruby最後の値
 Ruby-MemCache0.0.1Pure Ruby最後の値
Pythonpython-memcached1.44Pure Python最初の値

PerlのCache::Memcached、Pythonのpython-memcachedは、始めに返された値を、その他は最後に返された値を取得するという結果になりました。また、python-memcachedのみ、続けて他のデータを取得できませんでした。

リスト8 kai_test_wwc_get.py
#!/usr/bin/env python

import memcache

mc = memcache.Client(['127.0.0.1:11211'])
print mc.get('foo')

mc.set('foo_py', 'baz')
print mc.get('foo_py')
$ /path/to/kai_test_wwc_get.py
bar1
bar3        <- foo_py を取得しているにも関わらず、foo の値を取得している

意図的に発生させなければ、よほどの事が無い限りWrite/Write Conflictは発生しないので、実サービス環境でpython-memcachedを利用しても差し支えありません。

ただ、念には念を入れて、クライアントを選考する際にWrite/Write Conflictを意図的に発生させ、動作検証する事も無価値ではありません。

Write/Write Conflictをmemcachedのプロトコルだけでは解決できないという問題は、Kai開発者の間で活発な議論が続いており、0.4以降のバージョンで解決される予定です。もし、対処方法にご興味がおありでしたら、KaiのMLなどでご意見を頂ければ幸いです。

おすすめ記事

記事・ニュース一覧