Loading article…
データベース理論におけるCAP定理は、コンピュータ科学者のエリック・ブリューワーにちなんでブリューワーの定理とも呼ばれ、分散データストアは次の3つの保証のうち2つしか提供できないと述べています。 [1] [2] [3]
- 一貫性
- すべての読み取りは最新の書き込みまたはエラーを受け取ります。CAP定理で定義されている一貫性は、ACID データベーストランザクションで保証される一貫性とはまったく異なることに注意してください。[4]
- 可用性
- システム内の障害のないノードが受信したすべてのリクエストは、必ず応答を返す必要があります。これは、ギルバートとリンチによって定義されたCAP定理における可用性の定義です。[1] CAP定理で定義された可用性は、ソフトウェアアーキテクチャにおける高可用性 とは異なることに注意してください。[5]
- パーティション耐性
- ノード間のネットワークによって任意の数のメッセージがドロップ（または遅延）されても、システムは動作し続けます。
ネットワーク パーティション障害が発生した場合、次のいずれかを実行するかどうかを決定する必要があります。
- 操作をキャンセルして可用性を低下させるが、一貫性を確保する
- 操作を続行して可用性を提供しますが、不整合のリスクがあります。これは必ずしもシステムがユーザーにとって高い可用性を持つことを意味するわけではないことに注意してください。 [6]
したがって、ネットワーク パーティションがある場合は、一貫性と可用性のどちらかを選択する必要があります。
説明
ネットワーク障害から安全な分散システムは存在しないため、ネットワーク分割は一般的に許容されなければなりません。[7] [8]分割が存在する場合、一貫性と可用性の2つの選択肢が残ります。可用性よりも一貫性を選択した場合、ネットワーク分割のために特定の情報が最新であることを保証できない場合、システムはエラーまたはタイムアウトを返します。一貫性よりも可用性を選択した場合、システムは常にクエリを処理し、ネットワーク分割のために最新であることを保証できない場合でも、利用可能な最新バージョンの情報を返すように努めます。
パーティションがない場合、可用性と一貫性の両方を満たすことができます。[9]
RDBMSなどの従来のACID保証を念頭に設計されたデータベースシステムは可用性よりも一貫性を選択しますが、たとえばNoSQL運動で一般的なBASE哲学に基づいて設計されたシステムは一貫性よりも可用性を選択します。[10]
一部のクラウド サービスでは、強力な一貫性を選択していますが、世界規模のプライベート ファイバー ネットワークと GPS クロック同期を使用して、ネットワーク分割の頻度を最小限に抑えています[引用が必要]。最後に、一貫性のあるシェアード ナッシング アーキテクチャでは、クエリ対象のノードが所有するデータの可用性を維持するために地理的なシャーディングなどの手法を使用することがありますが、ネットワーク分割中に任意の要求が利用できないようにする必要があります[引用が必要]。
歴史
カリフォルニア大学バークレー校のコンピュータ科学者エリック・ブリューワーによると、この定理は1998年秋に初めて登場しました。[10]これは1999年にCAP原理として発表され、[11] 2000年に分散コンピューティングの原理に関するシンポジウム（PODC）でブリューワーによって予想として発表されました。 [12] 2002年に、MITのセス・ギルバートとナンシー・リンチはブリューワーの予想の正式な証明を発表し、それを定理にしました。[1]
2012年にブリューワーは、よく使われる「3つのうち2つ」という概念が、システム設計者がパーティションが存在する場合にのみ一貫性や可用性を犠牲にする必要があるため、やや誤解を招く可能性があることを含め、彼の立場のいくつかを明確にしました。パーティション管理と回復の技術は存在します。ブリューワーはまた、CAP定理で使用される一貫性の定義がACIDで使用される定義とは異なることにも言及しました。[10] [13]
分散システムにおける一貫性と可用性のトレードオフを述べた同様の定理は、1996年にバーマンとフリードマンによって発表されました。[14]バーマンとフリードマンの結果は、この下限を非可換操作に制限しました。
2010 年に導入されたPACELC 定理[ 9]は、パーティショニングがない場合でも、レイテンシと一貫性の間に別のトレードオフがあることを述べて CAP を基盤としています。PACELC とは、パーティション (P) が発生した場合、トレードオフは可用性 (A) と一貫性 (C) の間で行われ、それ以外の場合 (E) は、トレードオフはレイテンシ (L) と一貫性 (C) の間で行われることを意味します。Marc Brooker などの一部の専門家は、CAP 定理は、モノのインターネット(IoT) やモバイル アプリケーションに関連する環境など、断続的に接続される環境に特に関連していると主張しています。これらのコンテキストでは、停電などの困難な物理的条件や、エレベーターなどの限られたスペースに入るときに、デバイスがパーティション化される可能性があります。クラウド アプリケーションなどの分散システムでは、より包括的で、ネットワーク パーティションがない場合でもレイテンシや一貫性などのトレードオフを考慮したPACELC 定理を使用する方が適切です。 [15]
参照
- 分散コンピューティングの誤解
- ラムダアーキテクチャ（ソリューション）
- PACELC定理
- Paxos（コンピュータサイエンス）
- Raft（コンピュータサイエンス）
- ズーコの三角形
- 矛盾した三位一体
- トリレンマ
参考文献
- ^ abc Gilbert, Seth; Lynch, Nancy (2002). 「Brewer の予想と一貫性があり、利用可能で、パーティション耐性のある Web サービスの実現可能性」ACM SIGACT ニュース33 ( 2). Association for Computing Machinery (ACM): 51–59. doi :10.1145/564585.564601. ISSN 0163-5700. S2CID 15892169.
- ^ 「Brewer の CAP 定理」julianbrowne.com . 2009-01-11.
- ^ 「分散システムにおけるブリューワーズCAP定理」royans.net . 2010-02-14.
- ^ Liochon, Nicolas. 「CAP と ACID の紛らわしい文言」。This long run 。2019 年2 月 1 日閲覧。
- ^ ファウラー、アダム (2015)。NoSQL For Dummies。For Dummies。ISBN 978-8126554904。
- ^ ファウラー、アダム (2015)。NoSQL For Dummies。For Dummies。ISBN 978-8126554904。
- ^ Kleppmann, Martin (2015-09-18). CAP定理の批判（レポート）. Apollo - ケンブリッジ大学リポジトリ. arXiv : 1509.05393 . Bibcode :2015arXiv150905393K. doi :10.17863/CAM.13083. S2CID 1991487. 2019年11月24日閲覧。
- ^ Martin, Kleppmann. 「データベースを CP または AP と呼ぶのはやめてください」。Martin Kleppmann のブログ。2019年11 月 24 日閲覧。
- ^ ab Abadi, Daniel (2010-04-23). 「DBMS Musings: CAP の問題と、Yahoo のあまり知られていない NoSQL システム」。DBMS Musings 。2018-01-23に閲覧。
- ^ abc Brewer, Eric (2012). 「CAP 12年後: 「ルール」はどのように変化したか」. Computer . 45 (2). 電気電子技術者協会 (IEEE): 23–29. doi :10.1109/mc.2012.37. ISSN 0018-9162. S2CID 890105.
- ^ Armando Fox、Eric Brewer (1999)。Harvest 、Yield、およびスケーラブルなトレラントシステム。Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99)。IEEE CS。pp. 174–178。doi :10.1109/HOTOS.1999.798396。
- ^ Eric Brewer. 「堅牢な分散システムに向けて」(PDF)。
- ^ カーペンター、ジェフ、ヒューイット、エベン（2016年7月）。カサンドラ：決定版ガイド（第2版）。オライリーメディア。ISBN 97814919336572012 年 2 月、
Eric Brewer は CAP 定理に関する最新の見解を発表しました ... Brewer は現在、「3 分の 2」の公理はやや誤解を招くものであると述べています。彼は、設計者はパーティションが存在する場合にのみ一貫性または可用性を犠牲にする必要があること、およびパーティション回復技術の進歩により設計者は一貫性と可用性の両方を高いレベルで実現できるようになったことを指摘しています。
- ^ Ken Birman、Roy Friedman (1996 年 4 月)。「分散システムにおける一貫性と可用性のトレード」。hdl :1813/7235。
- ^ データ集約型アプリケーションの設計: 信頼性、拡張性、保守性に優れたシステムを支える重要なアイデア。O'Reilly Media。ISBN 978-1449373320。