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

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

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

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も検討の余地があります。

著者プロフィール

幾田雅仁(いくたまさひと)

酪農,ゴルフのキャディさん,某大手パソコン通信の下請け,某大手ポータルサイトなどを経て,決済代行を生業とする株式会社ゼロに入社。

p2p?なにそれ?美味しいの?の状態で,Erlang 分散処理勉強会に参加し,Kai のプレゼンを見て感銘を受け,無理矢理開発に参加し,現在に至る。