# 結果整合性 ## 定義 結果整合性（eventual consistency）は、分散データストアにおいて、すべての更新が最終的にすべてのレプリカに到達することを保証する整合性モデルである。強い整合性（strong consistency）とは異なり、ある時点での読み取りが最新の書き込みを反映していない可能性を許容する代わりに、高い可用性を実現する。[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]] において、[[Dynamo]] の中核設計哲学として位置づけられた。ネットワーク障害の可能性がある環境では、強い整合性と高い可用性を同時に達成できないという原理（CAP 定理として知られる）に基づき、Dynamo は可用性を優先して整合性を緩和する選択をした。 更新の伝播は非同期に行われ、並行更新やネットワーク分断により同一オブジェクトの複数バージョンが共存する場合がある。Dynamo ではベクタクロック（vector clocks）によってバージョン間の因果関係を追跡し、因果的に先行するバージョンは自動的に破棄する（構文的調整）。因果関係のない並行分岐はクライアントに返却し、アプリケーション固有のロジック（意味的調整）で解決させる。ショッピングカートの例では、分岐バージョンの「マージ」により「カートへの追加」操作が決して失われないことを保証する。 ## 横断的知見 - 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]]）。 ## 未解決の問い - 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 型結果整合性の継承とタイムスタンプベース衝突解決への変更） - 概念: [[一貫性ハッシュ法]]（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]]（ベクタクロック排除、タイムスタンプ方式、クォーラム読み書き、データセンタ対応レプリケーション）