← 分散システム 一覧

🎓 レベル：発展　|　重要度：B（重要）

📎 前提：CAP定理　|　関連：クォーラム（R+W>N）・ベクトル時計

要点（BLUF）

• PACELCはCAPの拡張：「分断時（P）は A か C、平時（Else）は L（レイテンシ）か C（一貫性）」。CAPが語らない平常運転のトレードオフを捉える。
• 分散DBは PACELC で分類できる：Dynamo/Cassandra＝PA/EL（分断時可用・平時低遅延優先）、Spanner＝PC/EC（常に一貫性優先）。
• 結果整合性は「更新が止めばいつか全複製が一致」。収束を作る機構は読み修復・反エントロピー（ゴシップ・反エントロピー・故障検出（SWIM））・CRDT。並行衝突の検出には ベクトル時計。

問題設定 ── 分断は稀、でも遅延は常にある

CAP（CAP定理）は「分断時」しか語りません。だが分断は稀で、システムが実際に毎日払っているコストは平時のレイテンシです。「強一貫を保つために毎回リモート確認する→遅い」という日常の取引を、CAPは取りこぼす。これを補うのがPACELCです。

モデル ── PACELC の読み方

flowchart TB
    ST{"今ネットワークは?"} -->|"分断あり P"| PAC{"A か C"}
    ST -->|"平常 E"| ELC{"L か C"}
    PAC --> PA["A：応答優先（古い値も）"]
    PAC --> PC["C：整合優先（応答断つ）"]
    ELC --> EL["L：低遅延優先（近い複製で応答）"]
    ELC --> EC["C：整合優先（毎回同期・合意）"]

仕組み ── 結果整合性はどう収束するか

弱い一貫（EL側）でも、放置で永久にズレるわけではありません。収束を作る3機構：

• 読み修復（read-repair）：読み取り時に複数複製を比較し、古いものを最新でその場で直す。
• 反エントロピー（anti-entropy）：バックグラウンドで複製同士が差分を交換し揃える。多くはゴシップで実装（ゴシップ・反エントロピー・故障検出（SWIM））。Merkle木で差分を効率検出。
• ヒンテッドハンドオフ（hinted handoff）：書き込み先が一時ダウン中、別ノードが代理保管し、復帰後に引き渡す。

衝突（並行更新）が起きたら検出して解決します：

• 検出：ベクトル時計／版数ベクトルで「因果か並行か」を判定。
• 解決：**LWW（last-writer-wins、タイムスタンプ勝ち）**は単純だが書き込みを失う。マージ（集合の和など）は失わない。CRDT（Conflict-free Replicated Data Type）は、和集合・増加カウンタのようにマージが数学的に必ず収束するよう設計されたデータ型で、調整なしに結果整合を保証する。

正しさの観点 ── 収束（convergence）の保証

結果整合性の安全性は「更新が停止すれば、全複製が同一状態に収束する」こと。CRDTはこれを結合律・可換律・冪等律を満たすマージ関数で保証する（順序や重複に依存せず同じ結果に至る）。活性は「反エントロピーが回り続ければ収束は有限時間で起こる」こと。LWWは収束するが書き込み損失という別の正しさ問題を抱える点に注意。

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

「いつか揃う」の”いつか”を短くするほどコスト（同期・帯域）が増え、長く許すほど古い値の窓が広がる。収束速度と平時コストの綱引きです。さらに「揃える」には衝突解決が要り、それには因果の判定（ベクトル時計）という別の難しさが乗る。弱い一貫性は「楽」ではなく「別の難しさへの移動」です。

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

• 「結果整合性は放っておけば揃う」→ 読み修復・反エントロピーという能動的な機構があって初めて収束する。
• 「LWWで衝突解決すれば安全」→ 並行書き込みの片方を静かに失う。失えないデータには不可。
• 「PACELCはCAPの言い換え」→ CAPに無い平時（E）の軸を足したのが本質。日常コストを語れる。
• 「CRDTは万能」→ 表現できるデータ型に制約（カウンタ・集合・レジスタ等）。任意の不変条件（残高は非負）は保てない。

対応ラボ

なし（概念回）。収束のつまみ（R・W）の定量効果は クォーラム（R+W>N）、ゴシップ収束は ゴシップ・反エントロピー・故障検出（SWIM） のラボで実証します。

関連

• 出発点の不可能性は CAP定理
• 収束を運ぶ機構は ゴシップ・反エントロピー・故障検出（SWIM）
• 衝突検出の理論は ベクトル時計

← 第4章 一貫性モデル 目次