結果整合性

結果整合性（英: Eventual Consistency）とは、分散コンピューティングにおいて高可用性を実現するために用いられる整合性モデル（一貫性モデル）であり、あるデータ項目に新たな更新が行われなかった場合、最終的に（結果的に）その項目へのすべてのアクセスが最後に更新された値を返すことを非公式に保証するものである[1]。結果整合性は楽観的レプリケーション[2]とも呼ばれ、分散システムに広く導入されており、その起源は初期のモバイルコンピューティングプロジェクトにある[3]。結果一貫性を達成したシステムは、しばしば「収束した」または「レプリカ収束を達成した」と言われる[4]。結果一貫性は弱い保証であり、線形性のようなより強いモデルのほとんどは、最終的に一貫性を持つことは自明だが、単に結果一貫性を持つシステムは、通常、これらのより強い制約を満たさない。

結果一貫性のあるサービスは、伝統的なACID（Atomicity, Consistency, Isolation, Durability）保証とは対照的に、BASE（Basically Available, Soft state, Eventual consistency）セマンティクスを提供するものとして分類されることが多い[5][6]。化学ではBASE（塩基）はACID（酸）の反対語であり、頭文字を覚えるのに役立つ[7]。同資料によると、BASEの各用語の大まかな定義は以下の通りである。

  • 基本的に利用可能：基本的な読み書き操作は可能な限り利用可能（データベースクラスタの全ノードを使用）だが、いかなる種類の一貫性保証もない（競合が調整された後に書き込みが持続しない可能性や、読み込みが最新の書き込みを取得しない可能性がある）。
  • ソフトステート：一貫性が保証されていないため、ある程度の時間が経過しても、状態がまだ収束していない可能性があるため、ある程度の確率でしか状態を知ることができない。
  • 最終的に（結果的に）一貫性がある：システムが機能していて、ある入力セットの後に十分な時間待つことができれば、結果的にデータベースの状態を知ることができ、それ以降の読み取りは期待に沿ったものになる。

結果一貫性は、分散ソフトウェアアプリケーションの複雑さを増大させると批判されることがある[8]。これは結果一貫性が純粋にライブネス保証（読み込んだデータが最終的に同じ値を返す）であり、安全性を保証していないことが一因である。結果一貫性を持つシステムは、収束する前に任意の値を返す可能性がある。

結果整合性はACID特性と同様にデータベースにおける一貫性モデルであるBASE特性における最も重要な考え方の一つである。結果整合性（Eventual Consistency）は、既存のRDBMSにおける悲観的ロックのような、厳密な一貫性を要求する考え方とは全く相反する考え方である。例えば、インターネットのDNS、NTPプロトコル、GPSなどのように、即座にデータが反映されることを前提としていないが、問題なく成立している事例は数多く存在する。

このように、結果整合性（Eventual Consistency）は、結果的に一貫性が保たれればよいという考え方に基づいている。NoSQLに代表されるデータストアでは、この考え方を取り入れることで、容易にスケールアウトを実現できるようにしている。結果整合性（Eventual Consistency）の実現には、P2Pのアーキテクチャーを導入した、様々な分散相互排他アルゴリズムが採用されている。

コンフリクト(不一致)の解決

レプリカを確実に収束させるためには、システムは分散したデータの複数のコピー間の差異を調整する必要がある。これには2つの部分がある。

  • サーバー間でデータのバージョンやアップデートを交換すること（しばしばアンチエントロピーとして知られている[9]）、および
  • 並行して更新が行われた場合に、適切な最終状態を選択すること（リコンシリエーションと呼ばれる）。

リコンシリエーションに最も適したアプローチは、アプリケーションによって異なる。一般的には「最後に書いた者が勝つ」[1]という方式や、ユーザーが指定したコンフリクトハンドラーを起動[4]する方法がある。更新の並行性を検出するために、タイムスタンプやベクタークロックがよく使われる。「最後に書いた者が勝つ」が受け入れられない状況では「最初に書いた者が勝つ」を使うことがある[10]。

同時（並行）書き込みのリコンシリエーションは、次の読み取りの前に行われなければならず、次のような異なるタイミングでスケジューリングすることができる[3][11]。

  • 読み取りの修復：読み取りが不整合を発見したときに修正が行われる。これにより読み取り動作が遅くなる。
  • 書き込み修復：書き込み時に不整合が発見された場合に修正が行われるため，書き込み動作が遅くなる。
  • 非同期リペア：訂正は、読み取りまたは書き込み操作の一部ではない。

強い結果一貫性

結果整合性が単なるライブネス保証（更新はいずれ観測される）であるのに対し、強い結果整合性（SEC）は、同じ（順序付けられていない）更新セットを受け取った2つのノードが同じ状態になるという安全保証を追加する。さらにシステムが単調であれば、アプリケーションがロールバックすることはない。SECを確保するための一般的なアプローチとして、コンフリクトフリーの複製されたデータ型がある[12]。

脚注

  1. ^ a b Vogels, W. (2009). “Eventually consistent”. Communications of the ACM 52: 40–44. doi:10.1145/1435417.1435432. 
  2. ^ Vogels, W. (2008). “Eventually Consistent”. Queue 6 (6): 14–19. doi:10.1145/1466443.1466448. 
  3. ^ a b Terry, D. B.; Theimer, M. M.; Petersen, K.; Demers, A. J.; Spreitzer, M. J.; Hauser, C. H. (1995). “Managing update conflicts in Bayou, a weakly connected replicated storage system”. Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95. pp. 172. doi:10.1145/224056.224070. ISBN 978-0897917155 
  4. ^ a b Petersen, K.; Spreitzer, M. J.; Terry, D. B.; Theimer, M. M.; Demers, A. J. (1997). “Flexible update propagation for weakly consistent replication”. ACM SIGOPS Operating Systems Review 31 (5): 288. doi:10.1145/269005.266711. 
  5. ^ Pritchett, D. (2008). “Base: An Acid Alternative”. Queue 6 (3): 48–55. doi:10.1145/1394127.1394128. 
  6. ^ Bailis, P.; Ghodsi, A. (2013). “Eventual Consistency Today: Limitations, Extensions, and Beyond”. Queue 11 (3): 20. doi:10.1145/2460276.2462076. 
  7. ^ “ACID vs. BASE: The Shifting pH of Database Transaction Processing”. DATAVERSITY. DATAVERSITY Education, LLC (March 2012). 29 August 2019閲覧。
  8. ^ HYaniv Pessach (2013), Distributed Storage (Distributed Storage: Concepts, Algorithms, and Implementations ed.), Amazon, OL 25423189M, "Systems using Eventual Consistency result in decreased system load and increased system availability but result in increased cognitive complexity for users and developers" 
  9. ^ Demers, A.; Greene, D.; Hauser, C.; Irish, W.; Larson, J. (1987). “Epidemic algorithms for replicated database maintenance”. Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. pp. 1. doi:10.1145/41840.41841. ISBN 978-0-89791-239-6 
  10. ^ Rockford Lhotka. "Concurrency techniques". 2003.
  11. ^ Olivier Mallassi (2010年6月9日). “Let's play with Cassandra… (Part 1/3)”. http://blog.octo.com/en/:+ OCTO Talks!. 2011年3月23日閲覧。 “Of course, at a given time, chances are high that each node has its own version of the data. Conflict resolution is made during the read requests (called read-repair) and the current version of Cassandra does not provide a Vector Clock conflict resolution mechanisms [sic] (should be available in the version 0.7). Conflict resolution is so based on timestamp (the one set when you insert the row or the column): the higher timestamp win[s] and the node you are reading the data [from] is responsible for that. This is an important point because the timestamp is specified by the client, at the moment the column is inserted. Thus, all Cassandra clients’ [sic] need to be synchronized...”
  12. ^ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (2011-10-10). “Conflict-free replicated data types”. SSS'11 Proceedings of the 13th International Conference on Stabilization, Safety, and the Security of Distributed Systems (Springer-Verlag Berlin, Heidelberg): 386–400. 

関連項目