クォーラムと読み書き整合性（R+W>N）

クォーラムとは何を保証する仕組みか

Dynamo 系の分散データストア（Amazon Dynamo, Apache Cassandra, Riak, ScyllaDB など）は、各キーを N 台 のノードに複製します。この複製集合を preference list と呼び、コンシステントハッシュ法でキーの担当ノードから時計回りに N 台を選ぶのが定石です。問題は「N 台すべての応答を待つと1台でも落ちれば操作が失敗する」点で、これでは可用性を稼ぐための複製が逆に可用性を下げてしまいます。

そこで導入されるのが クォーラム（quorum、定足数） です。すべてを待つ代わりに、書き込みは W 台、読み取りは R 台 の応答が揃った時点で成功とみなします。N より少ない台数で確定できるため、一部のノードが落ちても操作を続行できます。鍵になるのが次の不等式です。

R + W > N   … 読み集合と書き込み集合が必ず重なる（強整合の十分条件）
W > N/2     … 書き込み同士が必ず重なる（書き込みの直列化に必要）

なぜ R+W>N で最新値が読めるのか

原理は鳩の巣原理そのものです。ある書き込みは N 台のうち W 台に記録されます。続く読み取りは N 台のうち R 台に問い合わせます。R + W > N であれば、読み取りが触れる R 台と、最新の書き込みが触れた W 台は、台数の合計が N を超えるため 必ず1台以上で重複 します。その重複したノードは最新値を持っているので、読み取りは最新の書き込みを少なくとも1つは観測できます。

具体例を見ます。N=3 のとき、W=2, R=2 なら 2+2=4 > 3 で重なりが保証されます。書き込みは2台で確定できるので1台落ちても書け、読み取りも2台でよいので1台落ちても読めます。整合性と可用性のバランスが良く、これが Dynamo 系の最も一般的な既定値です。

N・R・W は可用性と整合性の調整つまみ

R と W は固定値ではなく、クエリごとに指定できる調整パラメータです。同じデータストアでも、操作の性質に応じて整合性レベルを変えられます。

ここから読み取れる原理は次の通りです。W を大きくするほど書き込みは「多くの複製に行き渡ってから成功」となり整合性は上がるが、待つ台数が増えるため書き込みの可用性とレイテンシは悪化します。R を大きくするほど読み取りは新しい値を取りこぼしにくくなるが、同様に読み取り可用性が下がります。そして R+W>N を割ると（例 W=1, R=1）、読み集合と書き込み集合が重ならないケースが生じ、古い値を読む可能性が出てきます。これが結果整合性の領域です。

バージョン管理：ベクタークロックと衝突

複製がズレた状態で、どの値が新しいかをどう判定するのでしょうか。単純な物理時刻（ウォールクロック）は、ノード間の時計ずれで前後が逆転し得るため信頼できません。Dynamo はこれに ベクタークロック（version vector） を用います。

ベクタークロックは [(ノードID, カウンタ), ...] の組で、各ノードが自分の更新ごとにカウンタを増やします。2つのバージョン A と B を比べ、A のすべての要素が B 以上（かつ少なくとも1つは真に大きい）なら「A は B の子孫（A が新しい）」と判定でき、因果関係を保ったまま新旧を順序付けられます。

書き込み1（ノードSx）: D1 [(Sx,1)]
書き込み2（ノードSx）: D2 [(Sx,2)]            ← D1 を上書き（祖先関係）
分断中に別経路で更新:  D3 [(Sx,2),(Sy,1)]      ← D2 から分岐
                       D4 [(Sx,2),(Sz,1)]      ← D2 から分岐
D3 と D4 は互いに祖先でない ＝ 衝突（並行更新）

どちらも相手の祖先でない場合、それは並行して起きた衝突です。Dynamo はこれを自動で潰さず、両方の値（兄弟、siblings）を保持して読み取り時にアプリへ返し、アプリ側のマージ（例：買い物カゴなら和集合）に委ねます。一方 Cassandra は実装を簡素化するため last-write-wins（タイムスタンプが新しい方を採用）を採り、衝突を自動解決する代わりに更新を失う可能性を受け入れています。設計思想の違いです。

読み修復とヒンテッドハンドオフ：ズレを収束させる

クォーラムは「読めた瞬間に最新を含む」ことは保証しますが、遅れている複製を放置すれば差は広がる一方です。Dynamo 系はズレを能動的に埋める2つの仕組みを持ちます。

読み修復（read repair） は、読み取りのついでに修復する仕組みです。R 台から値を集めた際にバージョンの食い違いを検出したら、最新値を遅れていたノードへ非同期に書き戻します。読まれるキーほど自然に修復されるため、ホットなデータは速く収束します。逆に読まれないキーは修復が走らないため、これを補うのが定期的に全複製を突き合わせる**反エントロピー（anti-entropy）**で、差分検出には Merkle ツリー（ハッシュ木）が使われます。

ヒンテッドハンドオフ（hinted handoff） は、一時的なノード障害を吸収する仕組みです。書き込み時に本来の担当ノードが落ちていると、別の生存ノードがその書き込みを「これは本来 Sx 宛て」というヒント付きで肩代わりして預かります。Sx が復帰すると、預かっていたノードがヒントをたどって書き込みを転送し、預かりぶんを削除します。これにより、一時障害中も書き込み可用性を保ったまま、復帰後に整合性を回復できます。

まとめ