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

Quorum（クォーラム、定足数）は、ある操作を成立させるために応答が必要なノードの最小数です。同じ値を複数のノードに持たせる複製の構成では、全ノードの応答を待たず、この数だけ集まった時点で操作を確定させます。最も広く使われるのは過半数を要求する構成で、N 台のクラスタなら N / 2 + 1 台（小数点以下は切り捨て）の応答で成立します。

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

  %%{init: {"theme":"base","themeVariables":{"primaryColor":"#eaf1f5","primaryTextColor":"#28343b","primaryBorderColor":"#9cabb5","lineColor":"#596b76","textColor":"#28343b","actorBkg":"#eaf1f5","actorBorder":"#9cabb5","actorTextColor":"#28343b","actorLineColor":"#9cabb5","signalColor":"#596b76","signalTextColor":"#28343b","noteBkgColor":"#f7f1e5","noteBorderColor":"#c5b99b","noteTextColor":"#403c32","activationBkgColor":"#edf3ef","activationBorderColor":"#9aafa1"}}}%%
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
    classDef default fill:#eaf1f5,stroke:#9cabb5,color:#28343b;

上記の図の調整役は、クライアントの要求を最初に受けたノードが務めます。調整役も複製を持つ 5 台の 1 台で、N はこの 5 台です。調整役は自分を含めて 3 台を数えた時点で成立とし、残る 2 台の応答は待ちません。遅いノードや落ちたノードがクライアントの待ち時間に響かないことが、クォーラムを使う直接の理由です。

以下は、5 台のうち書き込みが応答を集める W 台と、読み取りが応答を集める R 台の集合を並べた図です。

上記の図の左側のように W と R の合計が N を超えると、2 つの集合は必ず重なります。右側のように N 以下なら、重ならない選び方が残ります。

本記事では、クォーラムで複製の読み書きを成立させる方法を説明します。具体的には、次の疑問に答えていきます。

• なぜ全台でも 1 台でもなく、過半数を選ぶのか。
• 読み書きに参加するノードの集合や、書き込み同士の集合を重ねるには、どのような条件が必要か。
• 3 台の複製で、W と R をどう配分するのか。
• 集めた値の新旧を見誤ると、何が失われるのか。
• 何台あれば何台の障害に耐えられ、分断が起きると何が起きるのか。

前提として、故障はノードの停止とネットワークの分断だけを考えます。誤った値を返す故障（ビザンチン障害）には触れません。

Quorum が必要な理由

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

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

  %%{init: {"theme":"base","themeVariables":{"primaryColor":"#eaf1f5","primaryTextColor":"#28343b","primaryBorderColor":"#9cabb5","lineColor":"#596b76","textColor":"#28343b","actorBkg":"#eaf1f5","actorBorder":"#9cabb5","actorTextColor":"#28343b","actorLineColor":"#9cabb5","signalColor":"#596b76","signalTextColor":"#28343b","noteBkgColor":"#f7f1e5","noteBorderColor":"#c5b99b","noteTextColor":"#403c32","activationBkgColor":"#edf3ef","activationBorderColor":"#9aafa1"}}}%%
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 台と N 台の中間です。重ならない過半数の集合は同時に 2 つ作れないため、分断中に書き込みが成立するのは多数派だけです。少数派は必要な応答数を集められず、書き込みを断ります。

集合を重ねる 2 つの条件

過半数のノードを選んだ 2 つの集合には、必ず共通のノードが含まれます。ある操作が 5 台から 3 台を選び、別の操作も 3 台を選ぶと、合わせて 6 台分を選んだことになります。5 台しか居ないので、どちらの 3 台にも入るノードが必ず 1 台以上あります。

N 台の複製に対して、書き込みに必要な応答数を W、読み取りに必要な応答数を R と書きます。W と R の選び方には、目的の違う条件が 2 つあります。

読み書きの応答数をこの 2 つで重ねる考え方は、Gifford 氏の 1979 年の論文（Weighted Voting for Replicated Data）に遡ります。

W + R > N を満たすと、書き込みに参加したノードの集合と、読み取りが応答を集めた集合は、必ず 1 台以上重なります。保証されるのは、読み取りが応答を集めたノードに、その書き込みを受理したノードが含まれることまでです。重なったノードがどの値を返すか、集めた R 個の応答のうちどれを最新とするかは、バージョンの付け方と読み取り側の選び方で決まります（後述）。

W > N / 2 を満たすと、書き込み同士も、必ず 1 台以上のノードで重なります。ただし、保証されるのは両方の書き込みを見るノードが必ず居ることまでです。そのノードが両方を受け付ければ、2 つのバージョンがどちらも残ります。

例えば、各値にバージョン番号を添えておき、書き込みが元にした番号と手元の番号が一致する時だけ受け付ける規則（compare-and-set）を置けば、同じバージョンを元に作った書き込みのうち成立するのは最大 1 つです。

冒頭の図の左側が、5 台で W と R を 3 台ずつにした場合です。重なりは Node 3 です。N は 5、W と R はどちらも 3 なので W + R = 6 となり、N を 1 台分超えます。

W と R の配分

複製が 3 台（N = 3）の場合に、W + R > N を満たす最小の組み合わせは以下の通りです。

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

止まりやすさの差を二項分布で計算しました。各ノードが互いに独立に確率 p で落ちているとし、k 台の応答が必要な操作が成立しない確率を求めます。障害が同時に起きやすい構成（同じラックや電源を共有する場合）では、この計算より悪くなります。

def available(n, k, p):
    """Probability that at least k of n replicas are up."""
    return sum(comb(n, i) * (1 - p) ** i * p ** (n - i) for i in range(k, n + 1))

以下は p = 0.01 の時の出力の抜粋で、全体は availability_output.txt にあります。

p = 0.01
config         write unavail  read unavail
N=3 W=1 R=3        1.000e-06     2.970e-02
N=3 W=2 R=2        2.980e-04     2.980e-04
N=3 W=3 R=1        2.970e-02     1.000e-06
N=5 W=3 R=3        9.851e-06     9.851e-06

p = 0.01 では、W = 1 と R = 3 の組は書き込みが止まる確率こそ 100 万分の 1 ですが、読み取りは約 3% の確率で止まり、過半数の 2 台の約 100 倍です。読み書きの両方を使うなら、弱い方の操作で比べると過半数が有利になります。

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 の各ノードは断る規則を持たずに両方を受け付けるため、同時書き込みで生じた複数のバージョンはどちらも残ります。書き込み同士の集合が重なっても、片方が断られるとは限らない例です。残ったバージョンは読み取りの時にクライアントへ全部渡し、アプリケーションが併合します。

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

新しい値の見分け方

読み取りの結果は、次の 3 つを分けて考えます。

読み取りが集めた R 個の値のうちどれが新しいのかは、値そのものからは分かりません。単調に増えるバージョン番号を値に添えておき、番号の大きい方を新しいと判定します。書き込みが 1 台を必ず経由する構成なら、そのノードが採番すれば番号は 1 本に並びます。

複数のノードが並行して書き込みを受け付ける構成では、単一の番号だけでは、並行して起きた 2 つの更新と後から起きた更新を区別できません。区別する必要がある場合は、vector clock（ノードごとの更新回数の組）を保持し、一方の更新が他方を因果的に含むか、互いに無関係かを判定します。

例えば、{A:2, B:1} と {A:1, B:2} はどちらも相手を含まないので無関係で、{A:2, B:2} は両方を含むので後の更新です。無関係な更新どうしの優先順位までは決まらないため、別に競合解決の規則が必要です。

書き込みが W に届かないまま失敗しても、失敗の応答が示すのは「W 個の成功を観測できなかった」ことだけです。既に受理したノードには、値が残ることがあります。

例えば N=3、W=2 で Node 1 だけが永続化した直後に通信が切れれば、クライアントは失敗を受けても Node 1 には値が残ります。read repair（読み取りの時に古い複製を見つけて直す処理）や、ノード間のバックグラウンドの同期がその値を広げる実装もあります。その値を捨てる実装もあります。

したがって失敗応答だけから「書き込みは成立しなかった」と決めず、操作 ID と冪等性を用意して再試行または状態確認をできるようにします。

失敗した書き込みが、成功した書き込みを消すこともあります。2013 年に Kyle Kingsbury 氏は、故障を注入して DB（データベース）の正しさを調べる Jepsen で、Dynamo に倣った Key-Value ストアの Riak を調べました。

sloppy quorum を使わず R と W を過半数にした設定でも、分断を起こしながら 1 つのキーに数を書き足すと、成功を返した 1,971 件の書き込みのうち 1,807 件（約 92%）が失われました。

少数派で失敗した書き込みは一部のノードに残り、read repair で広がりました。この設定の Riak は、競合したバージョンのうちタイムスタンプの大きい方だけを残すので、失敗した側の書き込みが多数派の成功した書き込みを上書きしました。

タイムスタンプは時計の値で、前述のバージョン番号と違って更新の前後関係を表しません。併合を後述の CRDT に任せた同じ検査では、2,000 件の書き込みが全て残りました。

台数と耐えられる障害数

過半数を割った時点で、クラスタは書き込みを止めます。そのため、f 台の障害に耐えるには、f 台が落ちても過半数が残る 2f + 1 台が必要です。

台数を偶数にしても、耐えられる障害数は 1 台少ない奇数台の場合と変わりません。故障し得るノードだけが増えるため、奇数台で構成します（2f + 1 の関係は Majority Quorum のパターン解説、表と偶数台の話は Key-Value ストアである etcd の FAQ を元にしています）。

etcd の FAQ は、台数を増やすと複製先が増えて書き込みの性能が落ちるため 7 台以下に収めるよう勧め、多くの場合は 2 台の障害に耐える 5 台で足りるとしています。

分断が起きた場合

例えば、5 台が 3 台と 2 台に分断されると、以下のようになります。

  %%{init: {"theme":"base","themeVariables":{"primaryColor":"#eaf1f5","primaryTextColor":"#28343b","primaryBorderColor":"#9cabb5","lineColor":"#596b76","textColor":"#28343b","actorBkg":"#eaf1f5","actorBorder":"#9cabb5","actorTextColor":"#28343b","actorLineColor":"#9cabb5","signalColor":"#596b76","signalTextColor":"#28343b","noteBkgColor":"#f7f1e5","noteBorderColor":"#c5b99b","noteTextColor":"#403c32","activationBkgColor":"#edf3ef","activationBorderColor":"#9aafa1"}}}%%
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
    classDef default fill:#eaf1f5,stroke:#9cabb5,color:#28343b;

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

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

分断が解消すると、少数派は多数派から差分を受け取って追い付きます。追い付かせる処理はクォーラムの外にあり、ログを複製する仕組みや read repair が担当します。

W を過半数に取り、成功を返す前にディスクに書き終えていても、成功を返した更新が分断の後も残るとは限りません。書き込みを受け付けるノード（リーダー）を選び直す時や追い付かせる時に、その更新を持たないノードの内容で上書きすれば失われます。

Raft（etcd などが使う合意アルゴリズム）では、リーダーを選ぶ票を出せるのは自分のログ（受け付けた更新の記録）が候補より新しくないノードだけで、前のリーダーが作った更新は過半数に複製されただけでは確定と扱いません。この 2 つの条件があると、確定した更新を持たないノードはリーダーに選ばれません（Leader and Followers）。

利点

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

欠点

弱点は、過半数を集められない時と、集めるまでの待ち時間に出ます。

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

適さないケース

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

CRDT は、複数のノードが独立に更新しても、後から併合すれば必ず同じ結果に収束するように作ったデータ型です。操作を送る型では並行な操作が順序によらず同じ結果になるように、状態を送る型では併合が順序・重複に影響されないように設計します。Preguiça らの概説にあるとおり、要素を削除できる OR-Set や、最後の書き込みを残す LWW-Register もあり、操作は追加や増加に限りません。