体系ガイド · 基礎から応用へ

クォーラムの交差と障害許容

五台の読書き集合を列挙し、交差の計算と、版の選択・保存・分断・構成変更に必要な規則を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 集合の交差と値の保証を分ける
  2. 五台から三台を選ぶ計算をする
  3. 交差しても最初の応答は古い場合がある
  4. 停止と分断で進める側を求める
  5. 台数変更は別のプロトコルで扱う
  6. 模型で検査できる範囲を決める
  7. 修復の役割と完了の条件を区別する
  8. 境界の等号を試す課題と解答
  9. この記事をロゲイアに質問する理解を確かめる

集合の交差と値の保証を分ける

五台A、B、C、D、Eへ同じキーを複製する構成を考えます。書込みでW台、読取りでR台の応答を待つとき、R+W>Nなら、固定したN台の中から選ぶ二つの集合は交差します。N=5、R=3、W=3なら、最低一台を共有します。これは集合の性質です。共通の一台がどの版を返すか、いつ保存を確定したか、複数の書込みをどう並べるかは、この不等式だけでは決まりません。前提は複製と整合性の総論です。

このガイドでは、書込み集合と読取り集合を紙に描き、交差から得られることと、追加のプロトコルが必要なことを分けます。クォーラムという名前を付ければ、任意の読み書きが最新値を返すという説明はしません。Raftなどの合意プロトコルも多数の交差を使いますが、ログの新しさ、任期、投票、確定の規則と組み合わせています。単なる台数の計算を、それらの規則の代わりに使わないでください。

五台から三台を選ぶ計算をする

書込み集合を{A,B,C}、読取り集合を{C,D,E}にすると、共通はCです。二集合が交わらないなら3+3=6台が必要ですが、全体は5台なので不可能です。一般に共通部分の最小値はR+W−Nで、この場合は1です。R=2、W=3なら和は5で、{A,B,C}と{D,E}が交わらない反例を作れます。大なりと以上を取り違えず、R+W=Nでは交差を保証しないことを確認しましょう。

書込み同士も交差させたいなら2W>Nという別の条件を見ます。N=5、W=3なら二つの書込み集合も最低一台を共有します。ただし共通ノードが二つの並行書込みを両方受付けるなら、交差だけで一つへ決まるとは言えません。投票で同じ任期に一票だけという規則など、共通ノードが何を許すかが重要です。値の保存を行うクォーラムと、候補者へ投票するクォーラムは、同じ集合計算を使えても操作の意味が違います。

NRW最低の読書き交差
5331台
5230台
5151台

交差しても最初の応答は古い場合がある

版2の値newをA、B、Cへ所定の耐久性で保存し、三台の確認を待って書込みが完了したとします。DとEは版1のoldです。その後、読取りをD、A、Eへ送り、Dの応答が最初に返る履歴を考えます。三台の集合は書込み集合とAで交わりますが、最初に届いたoldをそのまま返せば古い値です。三台へ送っただけで、R=3の意味を満たしたとは限りません。応答の収集と、集めた版からの選択を規則として定めます。

単純な一書込みの模型なら、三台の応答を集め、比較可能な版を使って新しい値を選ぶことでAの版2を見つけられます。しかし同時に二人が版2を作る場合や、途中で失敗した書込みを読んだ場合には、版番号の割当てや読取りの修復など追加の問題が残ります。時刻の大きい値を選ぶだけでは、時計のずれも関係します。最大値を取る一行のコードだけを、線形化可能性の全体の実装と呼ばないでください。

停止と分断で進める側を求める

固定の五台で三台の応答が必要なら、任意の二台が停止しても、残る三台と通信できれば件数の条件を満たせます。三台停止すると二台しか残らず、同じ条件の書込みは完了できません。ただし「三台生きている」と「その三台が互いに、また呼出し元と通信できる」は違います。ネットワークが{A,B,C}と{D,E}へ分かれたら、単純な多数側の方式では前者だけが三台の集合を作れます。少数側へ更新を受付けさせるなら別の整合性の契約が必要です。

各側が自由に相手の代わりのノードを使う構成では、固定の五台から三台という前提が崩れる場合があります。Dynamoなどで使う方式を読むときは、誰を正規の複製先とし、障害時に代替をどのように扱うかを確認します。sloppy quorumのような名前だけから、元の固定集合の交差を適用しません。また三台の読取りが可能でも、必要な版が全て同じ耐久性で残っているかは別です。故障モデル、メンバー集合、応答の意味を同時に指定します。

台数変更は別のプロトコルで扱う

旧集合{A,B,C,D,E}と新集合{F,G,H,I,J}で、それぞれ三台を選んでも、旧と新の集合は交わりません。各集合の中でR+W>5を満たすだけでは、移行中に同じ履歴を保てません。メンバー変更は、古い構成と新しい構成をどうつなぎ、どの時点で新しい構成だけへ切り替えるかを別に定めます。Raftの構成変更のように複数構成の多数を使う手順は、そのための規則です。単に台数を足してNを書き換える操作として説明しないでください。

データを分割するshardingとも区別します。あるキーの複製集合が五台なのか、全体のサーバーが五台なのかでNの意味が変わります。別シャードにある同じ件数の台を数えても、一つのキーの読書き集合の交差には使えません。大きなシステムの配置図では、まず対象のキーと、そのキーに責任を持つメンバーを囲みます。分割のガイドへ進むときも、配置を変えることと複製の合意を取ることを別の軸として残します。

模型で検査できる範囲を決める

付属実験は五台から三台を選ぶ全組合せを列挙し、共通部分が一台以上あることをassertします。停止して残る台数、三対二の分断、古い最初の応答の反例も同じ入力で検査します。これは決定的な集合と版の模型で、実ネットワークやRaftの実装を障害注入して試したものではありません。模型で集合の計算が通ったことを、ログの永続化や選挙の安全性の実証へ広げないでください。何をassertしたかが検証の境界です。

本物の保存系を評価するなら、成功応答の前に何が保存されるか、再起動で残る状態、応答を失った書込み、並行書込み、構成変更を含む履歴を確認します。停止と通信の切断を分け、読取り結果が要求する整合性モデルを満たすかを判定します。クォーラムの条件は、その検査の前提を整理する道具です。強い読み書きが不要な場面では、可用性や遅延と交換して弱い契約を選ぶこともできます。その場合も「最新」の曖昧な表現を避け、利用者が見得る結果を具体的に示します。

修復の役割と完了の条件を区別する

読取りで古い版と新しい版が見つかったとき、古い複製を更新するread repairは、後の読取りで値が揃いやすくなる手段です。しかし修復を後で行う予定があるからと、今の呼出しで最初の古い応答を最新として返してよいとは言えません。返す値を決める規則と、複製を揃える後続作業は別です。修復自身の応答が失われた場合も、どの状態を成功と呼ぶかを確認します。

また、三台のうち二台が保存、一台が受信だけで応答したなら、同じW=3という表記でも再起動後の前提が違います。強い保証を必要とする評価では、件数だけでなく各応答の耐久性を検査します。固定の集合と比較できる版、保存の完了、応答の収集、選択を同じ履歴へ置いた後で、採用プロトコルが要求する追加の手順を確認します。

保存の確認が弱い場合、再起動後に交差したノードから必要な版を得られない履歴も考えます。集合へ含まれたという事実だけで値が残るとは言えません。対象の保存系で成功応答の前に何を保証するかを、設定まで含めて確認します。

境界の等号を試す課題と解答

課題はN=5、R=2、W=3で、必ず新しい書込み集合へ読取り集合が交わるかです。解答は交わるとは限らず、{A,B,C}と{D,E}が反例です。Rを3へ変えると交差は保証できますが、値の選択や保存の条件は依然として必要です。次にN=5、R=1、W=5なら交差はありますが、一台でも到達できなければ書込みを完了できないという交換条件を説明します。読書きの件数を動かすことは、保証だけでなく完了できる条件も変えます。

追加課題は、版2をA、B、Cへ保存した後、D、A、Eの応答でDが最初なら何を返すべきかです。単純模型の解答は、R=3の収集規則と版の比較を守り、最初のoldだけで返さないことです。それでも全ての並行履歴の線形化可能性を証明したとは言えません。集合、保存、収集、選択の四つへ判断を分けられれば到達点です。続く分散トランザクションでは、複数の資源の確定へ問いを広げます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 18

学習コースから次を選ぶ