Mímisbrunnr知恵の泉

← 分散システム 一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：レプリケーション方式（同期／非同期・リーダー／リーダーレス）　|　関連：Paxos・PACELC・結果整合性

要点（BLUF）

問題設定 ── 全部に書かず最新を読みたい

全複製に同期書き込みすると遅く、1台でも落ちると書けない。逆に1台だけ書くと速いが、別の1台から読むと古い。「いくつ書き、いくつ読めば、最新が保証されるか」——この最小の重なりを与えるのがクォーラムです。

モデル ── 重なりの条件

N 個の複製に対し、書き込みは W 個、読み取りは R 個に問い合わせる。鳩の巣原理から：

R+W>N  ⟹  (任意の読み集合)∩(任意の書き集合)≠∅R + W > N \;\Longrightarrow\; (\text{任意の読み集合}) \cap (\text{任意の書き集合}) \neq \varnothing

重なったノードは直近の書き込みを持つので、読み手はそれを（バージョン比較で）最新と判定できます。さらに書き込み同士の衝突を防ぐには：

W>N2W > \frac{N}{2}

（2つの書きクォーラムが必ず重なり、順序が一意化される。これは合意の過半数と同じ発想——Paxos）。

flowchart LR
    W["書きクォーラム W個"] -->|"R+W>N なら"| OV["必ず共有ノードあり"]
    R["読みクォーラム R個"] -->|"R+W>N なら"| OV
    OV --> LATEST["共有ノードが最新値を持つ -> 最新を読める"]

具体例 ── 境界条件を全数検証（実機）

ラボ 06-02_quorum.py（N=5）。全ての読み×書きクォーラムの組合せで最悪の重なりを調べ、R+W>N と「必ず最新を読める」が一致するか確認：

 R  W  R+W  最悪の重なり  最新を必ず読める?
  4  1   5        0           NG   (R+W>N: False, 一致:True)
  5  1   6        1           OK   (R+W>N: True, 一致:True)
  3  2   5        0           NG   (R+W>N: False, 一致:True)
  4  2   6        1           OK   (R+W>N: True, 一致:True)
  3  3   6        1           OK   (R+W>N: True, 一致:True)

R=3, W=3 (R+W=6): 最悪の重なり=1 -> 強い読み取り保証
R=2, W=3 (R+W=5): 最悪の重なり=0 -> 古い値を読みうる
R=2, W=2 (R+W=4): 最悪の重なり=0 -> 古い値を読みうる

R+W=N=5（境界）では最悪の重なりが0＝交わらない選び方があり古い値を読みうる。R+W=6>5 で初めて最悪でも1重なる。全組合せで「R+W>N ⇔ 必ず最新が読める」が完全一致しました（鳩の巣原理の確認）。

設計のつまみ ── R と W の選び方

設定（N=5）特徴
W=5, R=1書きが重い・読みが速い（読み多用システム）
W=1, R=5書きが速い・読みが重い（書き多用・即時応答書き込み）
W=3, R=3バランス（過半数同士、強い読み取り）
W=2, R=2（R+W≤N）高可用・低遅延だが結果整合（古い値あり、PACELC・結果整合性）

Dynamo系（Cassandra等）は R・W をリクエスト単位で選べ、R+W>N にすれば強い読み取り、R+W≤N にすれば速さ優先、と動的に取引できます。

正しさの観点 ── 安全性と可用性

なぜ分散だと難しいか（直観）

「最新を読む」を全複製確認なしに保証するのが難所。クォーラムは「全部は確認しないが、必ず1つは最新と重なる」を鳩の巣原理で作る、巧妙だが単純な仕掛け。重なりが0になる境界（R+W=N）を1つ超えるだけで保証が生まれる/消える、という鋭さがポイントです。

⚠️ よくある誤解・落とし穴

対応ラボ

distributed-systems-study/labs/06-02_quorum.py（N=5 で全クォーラム組合せを網羅し、R+W>N と最新読み取り保証の同値を確認済み）。

関連

← 第6章 レプリケーションとパーティショニング 目次