Quorum - 過半数で決定を成立させる仕組み

Quorum（クォーラム、定足数）は、ある操作を成立させるために応答が必要なノードの最小数です。同じ値を複数のノードへ持たせる複製の構成では、全ノードの応答を待たず、この数だけ集まった時点で操作を確定させます。最も広く使われるのは過半数を要求する構成で、N 台のクラスタなら N / 2 + 1 台（小数点以下は切り捨て）の応答で成立します。ここでは、ノードが停止する故障とネットワークが分断される故障を扱い、誤った値を返す故障（ビザンチン障害）は対象外とします。

効いているのは台数そのものではなく、過半数を選ぶと顔ぶれが必ず重なる事です。5 台から 3 台を選び、別の操作がまた 3 台を選ぶと、合わせて 6 台分を選んだ事になります。5 台しか居ないので、どちらの 3 台にも入るノードが 1 台以上残ります。

同時に 2 つの書き込みが走ると、多くのノードは片方しか受け取らず、競合が起きている事に気付けません。2 つとも受け取るのは重なったノードだけで、そこで古い方を断れます。重なりが用意するのは、その判断ができるノードが必ず居るという状況までです。断る規則そのものは別に要ります。

書き込みが成立するまでの流れを以下に示します。

  flowchart LR
    C["クライアント"] -->|"書き込みを要求"| Co["Node 1<br/>調整役"]
    Co --> N2["Node 2"]
    Co --> N3["Node 3"]
    Co --> N4["Node 4"]
    Co --> N5["Node 5"]
    N2 -.->|"受理を応答"| Co
    N3 -.->|"受理を応答"| Co
    Co -->|"自分を含む 3 台で成立"| C

上図の調整役は、クライアントの要求を最初に受けたノードが務めます。複製を持つ 5 台のうちの 1 台なので、N に数えるのは複製の台数だけです。調整役が落ちた場合は、クライアントが別のノードへ送り直します。数えているのは自分を含めた台数で、残る 2 台の応答は待ちません。遅いノードや落ちたノードがクライアントの待ち時間に現れない事が、クォーラムを使う直接の理由です。

なぜ Quorum が必要なのか

成立に必要な応答数は、1 台から N 台までのどこかを選ぶ事になります。N 台にすると、値は必ず全台へ揃うものの、1 台が落ちただけで書き込みが止まります。1 台にすると、応答は速い代わりに、書いた値を持たないノードが残ります。

1 台で成立させる構成の問題は、ネットワークが分断された時に表へ出ます。分断された両側が、それぞれ独立に書き込みを受け付けます。

  sequenceDiagram
    participant C1 as クライアント 1
    participant A as Node A
    participant B as Node B
    participant C2 as クライアント 2
    Note over A,B: ネットワークが分断
    C1->>A: x = 1 を書き込み
    A-->>C1: 成功（1 台で成立）
    C2->>B: x = 2 を書き込み
    B-->>C2: 成功（1 台で成立）
    Note over A,B: 分断が解消
    Note over A,B: x = 1 と x = 2 が<br/>両方残り、どちらが<br/>正しいか決まらない

上図で問題になるのは、分断が解消した後です。どちらのクライアントも成功の応答を受け取っているため、一方を捨てると、成功した筈の更新が消えます。全ノードの応答を待つ構成なら、この状態は起きません。分断中はどちらも全台の応答を集められず、両側とも書き込みを断るためです。ただし、分断が無い平常時でも 1 台の停止で全体が止まるため、複製した意味が薄くなります。

過半数は、1 台と N 台の中間にあたります。互いに素な過半数の集合は同時に 2 つ作れないため、分断中に書き込みが成立するのは多数派だけです。少数派は必要な応答数を集められず、書き込みを断ります。

仕組み

N 台の複製に対して、書き込みに必要な応答数を W、読み取りに必要な応答数を R と書きます。この 2 つには、目的の違う条件が 2 つあります。W + R > N を満たすと、書き込みに参加したノードの集合と、読み取りが応答を集めた集合は、必ず 1 台以上重なります。重なったノードは、最後に成功した書き込みの値を持っています。ただし、集めた R 個の応答のうちどれが最新かを見分ける手段は別に要ります（後述）。

W > N / 2 を満たすと、書き込み同士も必ず重なります。ここで注意が要るのは、重なりが排他を意味しない点です。重なったノードが版の新旧を比べて古い側を断る規則を持って初めて、一方だけが成立します。規則を置かなければ、重なったノードは両方を受理し、2 つの版が残ります。

重なりの様子を以下に示します。

  flowchart TB
    WC["クライアント A<br/>書き込み W=3"] --> N1["Node 1"]
    WC --> N2["Node 2"]
    WC --> N3["Node 3<br/>2 つの集合の重なり"]
    RC["クライアント B<br/>読み取り R=3"] --> N3
    RC --> N4["Node 4"]
    RC --> N5["Node 5"]

上図の Node 3 が重なりです。N は 5、W と R はどちらも 3 なので W + R = 6 となり、N より大きくなります。5 台から 3 台ずつをどう選んでも、共有されるノードが 1 台以上残ります。

読み取りが集めた 3 つの値のうちどれが新しいのかは、値そのものからは分かりません。単調に増える版番号を値へ添えておき、番号の大きい方を新しいと判定します。書き込みが 1 台を必ず経由する構成なら、そのノードが採番すれば番号は 1 本に並びます。複数のノードが並行して書き込みを受け付ける構成では、単一の番号だけでは、並行して起きた 2 つの更新と後から起きた更新を区別できません。区別する必要がある場合は、ノードごとの番号を組にして順序を決めます。

書き込みが W に届かないまま失敗した場合、既に受理したノードの上に値が残ります。クライアントには失敗が返るため、その書き込みは成立していません。後から同じ値が別の経路で広がって成立する場合もあるので、書き込みの失敗は「成立しなかった」ではなく「成立したかどうか分からない」を意味します。クライアントは同じ操作をやり直せるように作る事になります。

W と R の配分

W は書き込みに必要な応答数、R は読み取りに必要な応答数で、この組み合わせは 1 通りではありません。複製が 3 台（N = 3）の場合を以下に示します。

W = R = N / 2 + 1 を選んだ構成を過半数クォーラム（majority quorum）と呼びます。2 つの条件を同時に満たし、読み書きのどちらも同じ台数で済むため、既定の選択になります。読み取りが書き込みより桁違いに多い構成では R を小さく寄せる配分も向いていると考えられます。ただし、その分だけ W が大きくなり、書き込みが少数の障害で止まりやすくなります。

R と W を利用者の設定として外へ出した例に、Amazon が社内向けに作った複製付きの Key-Value ストアである Dynamo（2007 年の論文）があります。Dynamo は R + W > N を満たす設定を quorum-like と呼び、W > N / 2 は要求しません。よく使われる N = 3、R = 2、W = 2 の構成は W > N / 2 を満たします。それでも、同時書き込みで生じた複数の版はどちらも残ります。論文はその版を読み取りの時にクライアントへ全部渡し、併合の判断をアプリケーションへ任せる使い方を挙げています。重なるだけでは片方が消えない例がここにあります。

注意点として、Dynamo が使うのは sloppy quorum と呼ばれる方式です。ノードが落ちている間は本来の N 台以外へ書くため、R + W > N を設定しても、上で説明した重なりは保証されません。

台数と耐えられる障害数

過半数を割った時点で、クラスタは書き込みを止めます。そのため、耐えられる障害数は台数から決まります。f 台の障害に耐えるには 2f + 1 台が要る、と言い換えられます。

2f + 1 という関係は、Majority Quorum のパターン解説に載っています。台数を偶数にしても、耐えられる障害数は 1 台少ない奇数台と変わりません。故障し得るノードだけが増えるため、奇数台で構成します。

上の台数表と、偶数台が損になる話は、KVS（Key-Value Store）である etcd の FAQ に載っているものです。etcd は、複数のノードが同じ値へ合意する処理を Raft というアルゴリズムで実装しており、その合意の成立条件が過半数のクォーラムです。FAQ は、台数を増やすとデータを複製する先が増えて書き込みの性能が落ちるため 7 台以下に収めるよう勧めており、5 台なら 2 台の障害に耐えられて多くの場合はそれで足りる、と書いています。

分断が起きた場合

5 台が 3 台と 2 台へ分断された場合を以下に示します。

  flowchart TB
    subgraph P1["多数派 3 台"]
        A["Node 1"]
        B["Node 2"]
        C["Node 3"]
    end
    subgraph P2["少数派 2 台"]
        D["Node 4"]
        E["Node 5"]
    end
    CA["クライアント A"] --> A
    A -->|"3 台が揃い成功"| CA
    CB["クライアント B"] --> D
    D -->|"2 台しか揃わず失敗"| CB
    P1 -. "通信できない" .- P2

上図で分かれ目になっているのは、要求を受けたノードがどちら側に居るかだけです。少数派へ送ったクライアント B は失敗を受け取り、別のノードへ送り直すまで書き込めません。多数派が残る分かれ方であれば、クラスタ全体としては分断中も書き込みを受け付けられ、値が 2 箇所で別々に進む事はありません。5 台が 2 台・2 台・1 台へ割れた場合は、どこも過半数を作れないので全体が止まります。

少数派が断るのは、過半数を必要とする操作だけです。実装によっては、少数派のノードが単独で読み取りに応答し、古い値を返します。全台へ書いておけば読み取りが 1 台で済むのではないか、と考える方がいるかもしれません。その配分は N = 5、W = 5、R = 1 に相当し、分断されると多数派でも書き込めなくなります。分断中に進み続けるには、W を過半数まで下げる必要があります。

分断が解消すると、少数派は多数派から差分を受け取って追い付きます。追い付かせる処理はクォーラムの外にあり、ログを複製する仕組みや、読み取りの時に古い値を見つけて直す仕組みが担当します。W を過半数に取り、成功を返す前にディスクへ書き終えているなら、少数派で成立した書き込みは無いため、クライアントへ成功を返した更新が失われる事もありません。W が過半数に届かない配分では、少数派でも書き込みが成立するので、この性質は成り立ちません。

利点

• 遅いノードや落ちたノードの応答を待たずに操作を確定できる
• 互いに素な過半数の集合は作れないため、分断中も更新を 1 箇所へ寄せられる
• 台数から耐えられる障害数が決まり、構成を見積もりやすい
• W と R の配分で、書き込みと読み取りのどちらを速くするか選べる

欠点

以下は、少数の障害を待たずに進む事と、更新を 1 箇所へ定める事を優先した結果として現れる制約です。

• 過半数を割ると、生き残ったノードがあっても書き込みを止める
• 台数を偶数にしても耐えられる障害数は増えず、通信量だけが増える
• どの値が新しいのかを判定する版番号を別に用意する必要がある
• 応答の遅いノードは毎回クォーラムから外れ、追い付くまでの間は古い値を持つ
• 拠点をまたぐ構成では、過半数を集めるたびに拠点間の往復の時間が待ち時間へ加わる

適さないケース

• 分断中も両側で書き込みを受け付けたいシステム。CRDT のように後から併合できるデータ型を検討する
• ノードが数百台へ広がる構成。クォーラムを数える対象は数台に絞り、残りは読み取り用の複製に回す
• 複製を持たない単一ノードのシステム
• 書き込みの待ち時間に上限があり、過半数目のノードの応答を待てない場合

CRDT（Conflict-free Replicated Data Type）とは、複数のノードが独立に更新しても、後から併合すれば必ず同じ結果へ収束するように作ったデータ型です。集合への要素の追加やカウンタの増加のように、適用の順序が入れ替わっても結果が変わらない操作だけを提供します。クォーラムが応答数で解いている競合の問題は、データ型の性質で回避されます。

似た仕組みとの比較

成立に必要な応答数の選び方で性質がどう変わるかを以下に示します。

クォーラムは単独で使う仕組みではなく、他の仕組みの土台になります。分かりやすいのが WAL（Write-Ahead Log、書き込み先行ログ）の高位ウォーターマークで、これは記録した変更のうち、どこまでをクライアントへ見せてよいかを示す位置です。

その位置を「過半数のノードへ複製できた所まで」と決める方式は、集合が重なる性質を利用しています。書き込みを受け付ける代表のノードは過半数の票で選ばれ、票を出すのは、自分のログが候補より新しくないノードだけです。確定済みの変更を持つ過半数と、票を出した過半数は必ず重なるため、確定済みの変更を持たないノードは代表になれません。なお、過半数へ複製されたという事実だけでは確定になりません。代表が交代する経路の都合で、確定と扱ってよい条件はもう少し狭くなります。

Lease も同じ性質を利用しています。権利を貸す側のノードを複製する構成では、期限の記録を過半数で揃えておくと、貸す側が落ちても次のノードが既存の期限を引き継げます。