概念・定理図鑑 · 基礎から応用へ

クォーラム:応答集合の交わりと保証を分ける

レプリカ数と読み書きの応答数を集合で計算し、交差だけでは最新値の読み取りを証明できない理由を学ぶ。

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

更新日

この記事の目次
  1. 応答数ではなく集合を考える
  2. 五台から三台を選ぶ例
  3. 交われば線形化可能とは限らない
  4. 合意の多数派とも役割を分ける
  5. 交差する集合を列挙して確かめる
  6. 台数と故障領域を切り分ける
  7. この記事をロゲイアに質問する理解を確かめる

応答数ではなく集合を考える

クォーラムは、ある操作を進めるために必要とする参加者の集合や、その成立条件を表します。説明用に固定されたN台のレプリカを考え、書き込みがW台、読み取りがR台の応答を待つとします。R+WがNより大きければ、この同じ母集団から選ぶ読み取り集合と書き込み集合は少なくとも一台で重なります。これは集合の大きさについての事実であり、個々の応答が最新か、同時に起きた書き込みをどう扱うかはまだ説明していません。

集合の交差は、障害が起きないときだけ使う便利な数合わせではありません。ある書き込みを成功とした参加者と、その後に結果を読む参加者が完全に別々になることを防ぐための条件です。ただし交点のノードが、受け取ったデータをどこまで保存してから応答するかも重要です。メモリに受け取っただけの応答を数えるのか、永続化した応答を数えるのかで、クラッシュ後に使える情報は変わります。

五台から三台を選ぶ例

N=5、W=3、R=3とします。書き込みの応答がA、B、Cで、後の読み取りの応答がC、D、EならCが共通です。R=2なら、D、Eだけが応答して以前の書き込み集合と交わらない場合があります。三台ずつの多数派なら交差する一方、三台に到達できない側はその条件で操作を完了できません。分断中にも必ず両側が進めるという意味ではありません。数字の比較では、応答を待つ操作、集合の母集団、書き込みが完了した時点を必ずそろえます。

交点が少なくとも一台あることは、すべての読み取り応答が新しい値であることを意味しません。A、B、Cへ版7を書き、C、D、Eから読むなら、Cだけが版7を返してDとEは版6を返す状況も考えられます。読み取り側が三つの応答の多数決で値を選べば、版6を選んでしまいます。必要なのは、応答数だけでなく、版を比較して採用する規則です。単純な値の多数決と、版付きの読み取りを区別します。

交われば線形化可能とは限らない

交点で新しい版を見つけるには、応答したノードがどの版を保持し、読み取りがその版をどう選ぶかという規約が必要です。古い書き込みが後から届く場合や、同時に複数の更新が始まる場合もあります。バージョンの順序付け、書き込みの途中失敗、読み取りでの修復、再構成を含めたプロトコルを検討します。R+W>Nだけから線形化可能性を結論するのは不十分です。また、任意の代替ノードへ書くsloppy quorumでは、固定した同じレプリカ集合という計算の前提が崩れる場合があります。

読み取りが一番大きな版を選ぶ方式でも、途中で失敗した書き込みをどう扱うかは残ります。あるノードだけが新しい版を受け取り、書き手が成功に必要な数へ届かなかった場合、その版が後の読み取りに現れる可能性があります。読み取り修復や書き戻しを含む手順によって、後続の観測が逆戻りしないようにする設計もあります。保証を説明するときは、成功した書き込みだけでなく、不完全な操作を含む実行履歴を考えます。

合意の多数派とも役割を分ける

Raftなどの合意アルゴリズムでも多数派の交差は重要ですが、任期、ログ、投票の規則が安全性を支えます。多数派という単語だけを共通にして、読み書き型の保存システムと同じ保証を仮定してはいけません。運用では故障した台数だけでなく、到達可能な参加者、応答期限、保存先の故障領域を確認します。同じ電源や拠点に属する三台は、独立した三つの故障領域とは限りません。要求する整合性と可用性を文章で定め、その条件をクォーラム設定とプロトコル全体で満たせるかを判断します。

構成変更では、旧構成と新構成で別々に多数派を数えるだけでは、互いに交差しない決定集合ができる場合があります。例えば旧5台と新5台がほとんど別の参加者なら、それぞれ3台へ書いても共通点を持たないことがあります。参加者を変更する手順は、固定集合の式とは別に確認します。また地理的な分散は故障領域を分ける助けになりますが、応答を待つ経路の遅延も変えます。参加者数と配置の両方を設計します。

交差する集合を列挙して確かめる

5台A、B、C、D、Eから3台を選ぶ組み合わせは10通りです。どの二組を選んでも共通の参加者が一台以上あります。二組が全く別なら6台必要になり、母集団の5台を超えるからです。読み取り2台と書き込み3台なら、例えばD、EとA、B、Cは分かれます。式ではR+W=Nの等号なので、交差は強制されません。ここから、R+W>Nの不等号が厳密であることを確認できます。ただし、これは集合に関する検算です。ノードの返した版、応答時の保存状態、クライアントの読取り手順までは列挙していません。少数の集合をPythonなどで全列挙する試験は、設定の数え間違いを見つける助けになりますが、システム全体の整合性を証明した試験として報告しません。

台数と故障領域を切り分ける

5台のうち3台の応答を必要とする構成は、到達可能な参加者が3台残る間は、その台数条件を満たせます。しかし3台が同じ電源や同じネットワーク装置に依存していれば、一つの設備故障で条件を失う場合があります。さらに、残った3台へ到達できても、遅延が要求の期限を超えるなら、利用者の操作は時間内に終わりません。台数上の許容障害数、故障の相関、通信の到達性、応答期限を別々に記録します。読み取り数を減らすと、待つ応答が減る代わりに、どの書き込み集合との交差を要求するかも変わります。設定変更では、速さだけを測って安全性の前提を置き去りにせず、要求する保証と具体的なプロトコルの条件を合わせて確認します。

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

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

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

学習コースから次を選ぶ