# 結果整合性 ## 定義 結果整合性（eventual consistency）は、分散データストアにおいて、すべての更新が最終的にすべてのレプリカに到達することを保証する整合性モデルである。強い整合性（strong consistency）とは異なり、ある時点での読み取りが最新の書き込みを反映していない可能性を許容する代わりに、高い可用性を実現する。[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]] において、[[Dynamo]] の中核設計哲学として位置づけられた。ネットワーク障害の可能性がある環境では、強い整合性と高い可用性を同時に達成できないという原理（CAP 定理として知られる）に基づき、Dynamo は可用性を優先して整合性を緩和する選択をした。 更新の伝播は非同期に行われ、並行更新やネットワーク分断により同一オブジェクトの複数バージョンが共存する場合がある。Dynamo ではベクタクロック（vector clocks）によってバージョン間の因果関係を追跡し、因果的に先行するバージョンは自動的に破棄する（構文的調整）。因果関係のない並行分岐はクライアントに返却し、アプリケーション固有のロジック（意味的調整）で解決させる。ショッピングカートの例では、分岐バージョンの「マージ」により「カートへの追加」操作が決して失われないことを保証する。 ## 横断的知見 - **Session Consistency はクライアント間でトークンを共有しないと Eventual Consistency と同等になる**: Azure CosmosDB の Session Consistency はドキュメントで推奨される設定だが、「セッショントークンを共有するクライアント間でのみ同期」という制約がある。Work Dispatcher が書き込んだ直後に別クライアント（Worker）がトークンなしで読み取ると「キーが見つからない」エラーが発生した。この挙動がパフォーマンス最適化による「too fast」な処理で初めて顕在化し、28 日間のインシデントとなった。「ドキュメント推奨の設定を正しく理解しないと、Eventual Consistency と変わらない動作を招く」という実例（Source: [[@2023__SREcon23Americas__Turning an Incident Report into a Design Issue with TLA+]]）。 - **キャッシュ層における「ベストエフォート結果整合性」**: Facebook memcache は古いデータを読む確率を「調整可能なパラメータ」として明示的に位置付け、完全整合性よりも性能・可用性を最優先にする。Dynamo/Cassandra が永続ストアの整合性を論じるのに対し、memcache はキャッシュ層(非永続)の整合性のため、データ損失は許容しつつキャッシュ無効化の遅延のみを課題とする。リージョン内では mcsqueal(DB コミットログ駆動)で 1 秒以内に 4 ナインの無効化信頼性を達成。リージョン間ではレプリケーション遅延に起因する stale read を remote marker で緩和する。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) - Dynamo と Cassandra はともに結果整合性を採用するが、衝突解決の機構が根本的に異なる。Dynamo はベクタクロックにより因果関係を追跡し、クライアント側での意味的調整を可能にする。一方 Cassandra はベクタクロックを排除し、タイムスタンプ（last-write-wins）で衝突を解決する。Dynamo の方式は「書き込み前に読み取りが必要」という制約を生み、高書き込みスループット環境では制約となった。Cassandra はこの制約を取り除くことで Inbox Search（1 日数十億書き込み）の要件を満たしたが、同時書き込み時の意味論がタイムスタンプ精度に依存するトレードオフを受け入れている（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]）。 - 両システムはクォーラムベースの読み書きを採用するが、クォーラムの粒度が異なる。Dynamo は R + W > N を推奨して整合性を調整可能にしている。Cassandra も同様のクォーラム方式を採用するが、加えてデータセンタ対応レプリケーションポリシー（ラック対応、データセンタ対応）を提供し、地理分散環境での整合性と可用性のトレードオフをより細かく制御できる（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]）。 ## 未解決の問い - CosmosDB の Session Consistency は「ドキュメント推奨だが扱いが難しい」とされる（[[@2023__SREcon23Americas__Turning an Incident Report into a Design Issue with TLA+]] p.12）。クライアント間でセッショントークンを明示的に引き渡すパターンは SDK レベルでどの程度サポートされているか。また、実際のクラウドアプリケーションでこのパターンを誤用しているケースの頻度はどの程度か。 - Dynamo の本番データでは 99.94% のリクエストが単一バージョンのみを返しており、実際の不整合発生は極めて稀である。しかし残り 0.06% のケースにおける意味的調整のコスト（開発者負担・データ品質への影響）は定量化されているか。 - ベクタクロックの切り捨て（閾値超過時に最古エントリを除去）が調整の正確性に与える影響は「本番で問題にならなかった」と報告されるが、ワークロード特性が変化した場合にも成立するか。理論的な安全性の保証はあるか。 - Dynamo は「常に書き込み可能」を優先したが、金融取引や在庫管理など厳密な整合性が必要な領域では、結果整合性と強い整合性のハイブリッドアプローチ（例: Spanner の外部整合性）がどのように使い分けられているか。 - [[James Hamilton]] の[[インターネットスケールサービス設計]]における「障害前提設計」原則と、Dynamo の結果整合性設計は、ステートフルサービスにおける可用性と整合性のトレードオフをどのように分担しているか。 - Cassandra がベクタクロックを排除しタイムスタンプ（last-write-wins）に切り替えた判断は、書き込みスループットと衝突解決の正確性のトレードオフである。NTP のクロック同期精度がミリ秒オーダーの環境で、同一キーへの近接書き込みがどの程度のデータ損失リスクを生むか、本番ワークロードでの定量評価はあるか。 ## 関連 - ソース: [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]（Dynamo の設計哲学と本番検証）/ [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（Dynamo 型結果整合性の継承とタイムスタンプベース衝突解決への変更）/ [[@2013__NSDI__Scaling Memcache at Facebook]]（キャッシュ層でのベストエフォート結果整合性・remote marker・mcsqueal） - 概念: [[一貫性ハッシュ法]]（Dynamo のパーティショニング基盤）/ [[インターネットスケールサービス設計]]（障害前提設計の上位原則）/ [[ゴシッププロトコル]] / [[LSMツリー]] / [[分散キャッシュ]] - エンティティ: [[Dynamo]] / [[Amazon]] / [[Werner Vogels]] / [[Apache Cassandra]] / [[Facebook]] - 関連 MOC: [[分散システム - MOC]]（存在する場合） ## 出典 - [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]（結果整合性の定義、ベクタクロックによるバージョン管理、本番での分岐率データ） - [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（ベクタクロック排除、タイムスタンプ方式、クォーラム読み書き、データセンタ対応レプリケーション） - [[@2013__NSDI__Scaling Memcache at Facebook]]（キャッシュ層のベストエフォート結果整合性・mcsqueal 無効化・remote marker・30 日間の削除パイプライン信頼性計測）