C.A.P.定理

All lectures for JA purposes
レベル 1 , レッスン 885
使用可能

4.1 Brewera に関する一貫性

まず、Eric Brewer はデータベースの専門家ではなく、データベースの専門家であると主張したこともありません。彼は分散システムのコミュニティに属しており、CAP の「定理」が登場する彼の有名な講演は、カンファレンス「分散コンピューティングの原理」で行われました。(ちなみに、10 年後の 2010 年に、彼は再び同じ会議で招待講演を行いました。この講演では、特に、「 ) この領域には、データベースの分野で使用される用語の独自の解釈があります。

特に、「即時整合性」という用語は、データ更新操作が正常に完了したという通知をユーザーがシステムから受け取った後、この操作の結果がすべての観察者に即座に表示されることを意味します。

結果整合性とは、十分な期間にわたって新しいデータ更新操作がシステムに入力されなかった場合、以前のすべてのデータ更新操作の結果が最終的にシステムのすべてのノードに広がり、すべてのレプリカ データが保存されることが期待できることを意味します。一貫性がある (どうやら、これは「すべてのレプリカが同じ状態になる」と理解されるべきです。

この一貫性の感覚を念頭に置くと、Brewer の「定理」は非常に理解可能かつ明白であると考えることができます。共有データを使用する分散システムでは、ネットワークの一貫性、可用性、および分割耐性のいずれか 2 つの特性のみを同時に保証できます。この点に関して、Brewer 氏は、一連の ACID プロパティと彼が提案する BASE プロパティのセット(基本的に利用可能、ソフト状態、最終的な整合性- ほとんどの場合の可用性、不安定な状態、最終的な整合性) を対比しています。しかし、私の意見では、この反対は不当です。前者の場合はトランザクションの論理的特性について、後者の場合は分散システムの物理的特性について話しているからです。

4.2 「定理」の証明

多くの人は、ブリューワーの「定理」が正式に証明されたと信じています。実際、セス・ギルバートとナンシー・リンチによる論文では、「定理」が実際に定理となり証明される文脈において、いくつかの(ほぼ)正式な定義が導入されています。ただし、分散システムのこれら 3 つの特性がどのように決定されるかを見てみましょう。Brewer の「定理」によれば、このうち、同時にサポートできる特性は 2 つだけです。

一貫性はアトミック、または線形化可能な一貫性 (アトミック、または線形化可能な一貫性) と呼ばれ、システムの特性であり、そのすべての個々のデータ オブジェクトはアトミック (線形化可能) です。次に、アトミック オブジェクトは、操作の呼び出しと応答データの受信が即座に行われるように、複数の操作を含むオブジェクトです。オブジェクトは、前の操作が完全に完了するまで、次の操作の呼び出しを受け入れません。操作を受信する順序は、書き込みタイプの操作が実行された後に読み取りタイプの操作が到着した場合、読み取り操作は、この操作またはその後の書き込み操作によって書き込まれた値を返す必要があります。

障害が発生していないノードが受信したすべての要求に応答する必要がある場合、分散システムは常に利用可能です。ネットワーク分割に対するシステムの復元力は、あるノードから別のノードに送信された任意の数のメッセージが失われた場合のシステムの存続可能性の維持としてモデル化されます。

これらの定義に基づいて、ヒルベルトとリンチは次の定理を定式化します (非同期ネットワーク モデルにはクロックが存在せず、ノードは受信したメッセージとローカルの計算にのみ基づいて決定を下す必要があります)。

非同期ネットワーク モデルでは、すべての有効な実行 (メッセージが失われる実行を含む) の可用性とアトミックな一貫性プロパティを保証する読み取り/書き込みデータ オブジェクトを実装することはできません。

この定理は、実際には「矛盾による」方法によって非常に簡単に形式的に証明されます。この記事はさらに次のように結論付けています。

非同期ネットワーク モデルでは、すべての有効な実行に対するアクセシビリティ プロパティと、メッセージが失われない有効な実行に対するアトミックな一貫性を保証する読み取り/書き込みデータ オブジェクトを実装することはできません。

さらに、主定理の真実は部分同期ネットワーク モデルでも証明されます。このモデルでは、各ノードがクロックを持ち、時間は同じ速度で増加しますが、同期されていません。同じ現実の瞬間に異なる時間を表示できます。この場合、同様の結果は得られないことが示されており、したがって、部分同期ネットワークでは、「良好な」特性を備えた分散システムを組織化する可能性がより高くなります。

はい、ある意味では(ブリューワーの意図と必ずしも同じではありませんが)、ギルバートとリンチは、単一の分散システム内でネットワークのアトミックな一貫性、可用性、および分割耐性の特性を同時に保証することは不可能であることを証明したと考えることができます。しかし、これはデータベース トランザクション全般、特に ACID トランザクションとどのような関係があるのでしょうか?

4.3 ACIDトランザクション

Julian Browne が CAP の「定理」の議論に関するメモの中でこのことについて次のように書いています。

ヒルベルトとリンチは証明の中で、一貫性ではなくアトミック性という用語を使用しています。厳密に言えば、ACID の意味での一貫性とは、データベース トランザクションの理想的な特性を指し、データがまったく保持されないことを意味するため、技術的な観点からはより理にかなっています。事前に設定された制限に違反すると、永続的になります。しかし、分散システムの事前に確立された制限が、同じデータ要素に対する複数の異なる値の存在の禁止であると仮定すると、私の意見では、一貫性の抽象化におけるこの欠陥は考慮される可能性があります重要ではありません(さらに、ブリューワーが原子性という用語を使用した場合、AAP 定理が登場しますが、その名前は発音するのが非常に不便です)。

あまり真剣にではなく、正直に書いています。実際、アトミックな一貫性の要件は、ACID の意味でのトランザクションの一貫性の要件と混同すべきではありません。データベースの整合性制約は、いわば論理的なビジネス要件です。これらはアプリケーション ドメイン ロジックから来ています。原子の一貫性の要件は、まったく異なる種類のものです。これは、データベース業界で伝統的に物理的一貫性と呼ばれるカテゴリに分類される実装要件です (たとえば、インデックス変更操作を実行する場合、対応する B+ ツリーのすべてのブロックに有効な値が含まれ、有効な参照によってリンクされている必要があります) )。

そして、データベースコミュニティの代表であるダニエル・アバディとアレクサンダー・トムソンがメモの中で非常に真剣に書いている内容は次のとおりです。

... スケーラブルなトランザクション システムの可用性に対する要件はますます重要になっており、これは通常、ノードの 1 つで障害が発生した場合のリクエストのレプリケーションと自動リダイレクトによって満たされます。したがって、アプリケーション開発者は、ACID システムの一貫性保証 (元々はユーザー定義の不変式のローカル サポートで構成されていた) が拡張されて、強力な一貫性 (常に同じデータのすべてのレプリカが同一のコピーになること) を保証することを期待しています。この場合の一貫性は、CAP/PACELC の意味で暗黙的に示されています。

言い換えれば、Brewer の整合性は ACID の意味での整合性とは何の関係もありませんが、データ レプリケーションを通じて高可用性を提供することに重点を置いたシステムでは、強力なレプリカの整合性を維持することが望ましいということです。これは ACID のプロパティではなく、アプリケーション開発を容易にする超並列 DBMS の技術的 (物理的) 機能です。

Michael Stonebreak 氏によると、高品質な最新の DBMS を構築する鍵は、技術的な妥協点を適切に選択することです。特定のエンジニアリング ソリューションを選択するときは、将来のユーザーの要件、さまざまな障害状況の可能性など、多くの要素を考慮する必要があり、一般的な理論ガイドライン (CAP の「定理」を含む) によって独断的に導かれてはなりません。

Stonebreaker 氏は、トランザクション並列データベース システムの領域では、Brewer の一貫性を放棄して高可用性とネットワーク パーティション トレランスをサポートするのはよくないトレードオフであると考えています。(b) トランザクション型の超並列 DBMS は非常に多数のノードを持つクラスターを必要としないため、ネットワークが分割される状況は起こりそうにありません。(c) システムは、ネットワークの分断のためではなく、たとえば、定期的に発生するソフトウェア エラーの存在によって、簡単に使用できなくなる可能性があります。

したがって、Brewer の「定理」を頻繁に参照する NoSQL 陣営 (NoACID と読みます) の代表者の活発な活動は、ACID トランザクションをサポートする大規模並列トランザクション DBMS の構築が理論的に不可能であることと関係しているのではなく、システムが単純化されているという事実と関係しています。 ACID トランザクションだけでなく、レプリカの整合性もサポートするトランザクションは、より簡単かつ迅速に作成されます。構成が単純であるため、非常に高速なデータ処理が可能であり、アプリケーションによっては、これがデータベース テクノロジに固有のあらゆる利便性よりも重要です。

データベース コミュニティがこの課題にどのように対応しているかを見てみましょう。

コメント
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION