CAP定理の神話

はじめに

私は長い間CAP定理に関する神話について書きたいと思っていましたが、どういうわけか誰もがそれを手に入れることができませんでした。 しかし、 別の作品を読んだ後、彼は頭をつかんで、すべてを棚に置いて、脳に調和のとれた絵が現れるようにしました。

記事が感情の嵐を引き起こすイベントは非常にまれです。 チェーンレプリケーションについて読んだときにこれが初めて発生しました。 彼らは、これが強力なアプローチであり、これが一貫性のあるレプリケーションで起こり得る最高のアプローチであると私に納得させようとしました。 なぜこれがうまく機能しないのかについては議論しませんが、単にChain Replicationメタデータ管理の記事から引用するだけです：

スプリットブレイン管理は厄介な問題です。 ここで紹介する方法は、語用論に基づいたものです。 動作しない場合、深刻な心配はありません。Machiの最初の深刻なユースケースはすべてAPモードのみを必要とするためです。 最終的に「Riak Ensembleを使用」または「ZooKeeperを使用」にフォールバックする場合、おそらくそれで十分です。

私の自由な言い換えでは、これは次のようなことを意味します。「ここには特定のアルゴリズムがあります。正しく機能するかどうかはわかりません。はい、私たちにとっては重要ではありません。」 少なくとも正直なところ、著者のおかげで多くの時間を節約できました。

そして、ここで、 Spanner、TrueTime、およびCAP Theoremの記事が目を引きます。 概念と知識を備えた、終わりに近い棚で分析します。 その前に、CAP定理に関連する最も一般的な神話を分析します。

神話1：Aはアクセシビリティを意味する

Aはもちろん、アクセシビリティという言葉から来ました。 しかし、アクセシビリティとは何ですか？ どんな種類？

異なるコンテキストでの可用性は、異なることを意味します。 そして、ここでは、使用される少なくとも2つの異なるコンテキストを区別する必要があります。

1. 実際のサービスの可用性。 この可用性はパーセンテージで表されます。1年間の合計ダウンタイムが測定され、割合がパーセンテージで表され、長時間の可用性の可能性を示します。
2. CAP定理のモデルのフレームワーク内での可用性。

CAP定理は、用語「総可用性」に最も意味が近い概念を使用します。

分散システムを継続的に使用可能にするには、システム内の障害のないノードが受信したすべての要求が応答する必要があります。

これは、おおよそ次のことを意味します。「システム内の障害のあるノードはすべて、要求に応答する必要があります。」 この定義には、強調したい点がいくつかあります。

1. 「泣き叫ぶ。」 倒れたノードが何らかの方法で応答できないことは明らかです。 ただし、キャッチは、すべてのノードが落ちた場合、定義の観点から、そのようなサービスを利用できることです。 原則として、クライアントが応答を受信する必要があるという事実を追加することにより、定義を修正できます。
2. 「答える必要があります。」 定理は、正確な時期を言っていません。 彼女は時間パラメータにまったく興味がありません。 ノードが即座に応答できないことは明らかです。 それができない場合は、一度答えれば十分です。

ユーザーの観点から見ると、100個のノードがあり、99個が落ち、残りのノードが1時間あたり1つのリクエストの速度で応答し続ける場合、そのようなサービスはアクセス可能とは言えません（これはコンテキスト1です）。 ただし、CAP定理の観点からは、ここですべてが問題なく、そのようなシステムが利用可能になります（コンテキスト2）。

したがって、Aは一般に受け入れられている意味ではアクセシビリティではなく、いわゆる完全なアクセシビリティであり、ユーザーはまったく興味を持たない可能性があります。

神話2：Pはネットワークの復元力を表す

このような定義は、ほぼすべての記事に記載されています。 ここで何が間違っているのかを理解するには、別の角度から問題を見る必要があります。

任意のメッセージングシステムを使用します。 システムのオブジェクトであるアクター間でのメッセージの送信方法を検討してください。 これらのメッセージは、別のアクターに届く場合と届かない場合があります。 そして、ここでは2つのケースを区別する必要があります：

1. システムでは、メッセージが失われると状況は不可能です。
2. システムでは、メッセージが失われた場合に状況が発生する可能性があります。

このリストは網羅的であると推測するのは簡単です。 この時点で、各項目がシステムのプロパティを説明していることに注意する価値があります。 つまり アルゴリズムにも到達していません。 これは、広範囲にわたる結果をもたらします。

メッセージが失われることのない最初のケースを考慮すると、このような状況では、 ネットワークの分離はまったく不可能です。 実際、各アクターからの各メッセージは損失なく到達できるため、 ネットワークの分離について話す意味はありません。 2番目のケースでは、逆のことが言えます。損失のため、セグメント全体が別のセグメントから分離される可能性があります。 アクターのグループ間の接続が失われました。 この場合、彼らはネットワーク分離が起こったと言います 。

俳優のグループが互いに隔離される可能性の特性は、パラグラフ2の直接的な結果であることに注意する必要があります。

実際のネットワークで作業する場合、ご想像のとおり、2番目のポイントに該当します。 同時に、私たちはまだアルゴリズムについて考え始めておらず、アクターのグループ間の接続性を分離して失う能力をすでに持っています。 P-これは、システムで分割が可能なことです。 そして、これはアルゴリズムの特性ではなく、アルゴリズムが機能するシステムの特性です。

メッセージが失われた場合にネットワークの分離を考慮することが重要なのはなぜですか？ 残りの問題はそれほど多くのトラブルや問題を引き起こさないため、どれだけシステムが独立した部分に分割されるのか。

この神話を締めくくるために、ブログAphyr：Percona XtraDB Clusterから引用します。

パーティショントレランスでは、要求を処理するためにすべてのノードがまだ利用可能である必要はありません。 パーティションが発生する可能性があることを意味します。 一般的なIPネットワークに展開する場合、パーティションが発生します。 これらの環境でのパーティション許容値はオプションではありません。

したがって、実際の信頼性の低いネットワークで動作するシステムを検討する場合、ネットワーク接続障害は例外的な状況ではなく、対処する必要があるものです。 また、このコンテキストの文字Pは、ネットワーク接続違反が発生する可能性があることを意味するだけです。

神話3：ACシステムは存在しない

前の神話から、ACシステムは存在しないという感覚を感じるかもしれません。なぜなら、 データを送信できる信頼できるネットワークはありません。 すぐに、冗長コンポーネントを含むスキームを提案してみてください。 ただし、回線でのパケット損失の確率が0より大きい場合、チャネルをどのように追加しても、数学的な考慮から純粋に確率を0にすることはできません。 その場合、上記のように、ネットワークが分割される可能性があります。

しかし、CAPはネットワークに接続されたシステムのみを記述すると誰が言ったのでしょうか？ CAPは、非常に幅広いクラスのタスクに適用できる理論モデルです。 たとえば、マルチコアプロセッサを使用できます。

1. 各コアは個別のアクターです。
2. アクター（カーネル）はメッセージ（情報）を交換します。

CAP定理について説明するにはこれで十分です。

最初に説明しましょうA.カーネルは利用可能ですか？ もちろん、はい、いつでもコアにアクセスして、メモリから必要なデータを取得できます。

Pはどうですか？ プロセッサは、必要に応じてデータが問題なく別のコアに転送されることを保証します。 何らかの理由でこれが発生しない場合、そのようなプロセッサは欠陥があると見なされます。 したがって、文字Pが欠落しています。

一貫性の問題も次のように対処されます。 メモリモデルは、このようなシステムの最高レベルの一貫性である順次一貫性を定義します。 同時に、MESIやMOESIなどのキャッシュコヒーレンスプロトコルは、通常、プロセッサ内に実装されるため、一定レベルの一貫性が保証されます。

したがって、最新のプロセッサは、コア間のメッセージ配信が保証されたACシステムです。

神話4：Cは一貫性を意味する

Cは間違いなく一貫性を意味します。 しかし、一貫性とは何ですか？ 結局のところ、最終的な一貫性は一貫性でもあり、非常に弱いだけです。 それはどういう意味ですか？ 一貫性のモデルは数多くあります。記事「 非トランザクション分散ストレージシステムの一貫性」の図をご覧ください。

そして、これは分散型の非トランザクションシステムについてです！ 考慮事項にトランザクション性を追加すると 、開始することなくすぐにソートするという考えを埋めることができます。

CAP定理に関する元の記事では、線形化可能性についてあらゆるところに言及しました。 線形化可能性の本質は、要するに次のとおりです。 アクションが発生した場合（問題ではなく、読み取り、書き込み、または混合アクション（複数可））、このアクションの結果は、回答を受け取った直後に利用可能になります。

論理的な問題が発生します：他の一貫性モデルについてはどうですか？ それらはCAP定理に適合していますか？

そして、頭の中で完全な混乱を始めます。 一部の人々は、モデルが線形化可能性について証明されているため、線形化可能性に対して厳密かつ排他的に適用されるべきだと考えています。 弱い整合性モデルはもはやこの定理に該当しないと考える人もいます。 さらに、議論の本質を理解していない人もいます。

この質問に答えるために、記事Highly Available Transactionsから抜粋した素晴らしい写真を考えてください。

彼女は何について話しているのですか？ CAP定理のフレームワーク内で機能する、いわゆるアクセス不能モデルは赤でマークされています。 つまり 同時に、AとPに同時に到達することは不可能です。 ただし、多くのタスクに対して十分なレベルの一貫性を備えた他のモデルがありますが、それでもAPと同時に実行でき、CAPシステムを割引なしで受信できます。 典型的な例： Read Committed （RC）とMonotonic Atomic View （MAV）はCAPの3文字すべてに同時に準拠しており、そのようなモデルを一貫性のないものと呼ぶことは困難です。 CAP定理に違反するこのような整合性モデルは、高可用性モデルと呼ばれます。

したがって、一貫性について言えば、 使用不可モデルと呼ばれる一貫性モデルの幅広いグループを念頭に置いています 。

神話5：CPシステムは高可用性ではない

前の段落の後、この文は非常に論理的に見えますが、根本的に間違っています。 Aはナイン内のアクセシビリティではなく、完全なアクセシビリティを意味することを思い出させてください。 CPシステムの可用性を高めることは可能ですか？

ここでは、モデルと鉄を分離する必要があります。 理論と現実。

モデルのフレームワークで最初に推論してみましょう。 CAP定理のフレームワーク内のアクセシビリティとは、完全なアクセシビリティ、つまり 生きているノードは応答する必要があります。 しかし、なぜこれが必要なのですか？ 結局のところ、クライアントのロジックをまったく異なる方法で書くことができます。 異なるデータセンターに3つのノードがあるとします。 2ノードのクォーラムを記述しますが、1ノードはシステム全体の生存性と一貫性を失うことなく横たわります。 そして、常に2つのノードから読み取ります。 さらに、一方のノードが横たわっている場合、もう一方のノードが正しい答えを出します。 2つの異なる回答があれば、最新の回答を選択できます。 したがって、このシステムで1つのノードのみがいつでも動作不能になることが保証されている場合、クライアントの観点からは、システムは読み取りと書き込みの両方で完全に100％アクセス可能になります。 さらに、それは一貫しています。

実際には、1つではなく2つ以上のノードが横になる確率は常にゼロではありません。 これは簡単に確認できます。なぜなら 1つのノードが落ちる可能性がゼロでない場合、別のノードが落ちる可能性はゼロではありません。 さらに、転倒は最悪の事態ではありません。 機器の故障に加えて、接続が失われる可能性もあります。 トランク機器を含むさまざまなネットワーク機器の障害。 このすべての確率がゼロ以外であることを思い出す価値はないと思います。 これらの確率はすべて加算され、ごく少数の、場合によっては非常に小さい数の9を与えます。 ノードの予約が大きいほど、9の数が多くなることは明らかです。 そして、私はまだプログラマーがエラーを引き起こす可能性がゼロ以外で書いているプログラム自体を考慮していません...

つまり 理論的には、正しく記述されたクライアントは100％のアクセシビリティを達成できると考えていますが、実際には常により少ない数です。 すべての科学は、可能な限り多くの9を達成することです。 そして、この側面では、CAP定理はまったく役に立ちません。 彼女は何か他のことを話しているからです。

したがって、高可用性という考えは、Aではないということとまったく矛盾していません。つまり、CPの可用性が高いということです。

神話6：CPシステムはパフォーマンスが低く、待ち時間が長く、拡張性がよくありません。

明らかに、一貫性のレベルが高いほど、システムの生産性は低下します。 問題は、パフォーマンスの低下がどれだけあるか、そしてそれが私たちのプロセスにとって重要かどうかに関して生じます。

厳密な整合性またはStrong-1SR （最高レベルの整合性）でさえ、リアルタイムシステムで使用できることがわかりました 。 私はこの事実の実験的証拠を持っていますが、ここではそれを支持するいくつかの実際的な議論をします。

アイデアは、多くの独立したフェールオーバーエンティティを使用することです。 それらはどこででも実行でき、並行して動作し、実際にはクラスターのサイズによって数が制限されます。 これらのエンティティの上にトランザクション層が作成され、これらのエンティティの作業がリンクされます。 これが、 Spannerや他の多くのシステムの仕組みです。 したがって、スケーラビリティとパフォーマンスが実現されます。

神話7：APシステムは拡張性が高いため使いやすい

APを搭載したシステムでは、スケーリングが容易になりますが、理論上のみです。 現実には、とにかく、ある程度、一貫性の問題を解決する必要があります。 そのようなシステムに基づいてクライアントコードを記述することは非常に簡単なタスクであり、時には達成できないことさえあることを実践は示しています。 その理由は、システムがデータの一貫した保存のための基本的な保証を提供しない場合、その後の処理は非常に魅力的なシャレードに変わります：操作が適用されましたか？ ユーザーに表示されますか？ 彼らは何を見ますか？ データの一貫したスライスを取得できますか？ 異なるクライアントは同じデータセットを見るでしょうか？ など

つまり このようなシステムの作成は比較的単純ですが、その使用の複雑さは何倍にもなります。

記事の解析

それでは、記事Spanner、TrueTime＆The CAP Theoremの分析を開始します。 最初から始めましょう：

CAP定理[Bre12]は、次の3つの望ましい特性のうち2つしか持つことができないと述べています。

• C：一貫性。この議論のシリアライズ可能性と考えることができます。
• A：読み取りと更新の両方で100％の可用性。
• P：ネットワークパーティションに対する耐性。

最初に注意する必要があるのは、2012年5月付けの「12年後のCAP：「ルール」の変更」というタイトルの[Bre12]リンクです。 元の記事へのリンクを選択しなかった理由は不明です。 さらに、この記事はCAP定理に関する議論であり、定理自体の結論に関するものではありません。

すでに説明したC、A、Pの文字については、やめません。 次：

パーティションが避けられないと考えると、分散システムは一貫性（AP）または可用性（CP）のいずれかを失うように準備する必要があります。

最初の部分は、私たちの議論の枠組みでは非常に理にかなっていますが、APとCPの後、奇妙なことが続きます 突然その選択をしたくないことが判明しました。 なぜそのような選択をしたくないのかについては、記事には書かれていません。 しかし、その後、正しい言葉が書かれています：

実際の定理は約100％の可用性ですが、ここでの興味深い議論は現実的な高可用性に伴うトレードオフについてです。

ここでやめて、Spannerは可用性が99.9 ...％のCPシステムであると言って、これに終止符を打つことができるように思えます。 しかし、いや、著者は続けて、彼はサブタイトルを書きます：

Spannerは、一貫性があり利用可能であると主張しています。

Spannerは、一貫性と可用性が高いと主張しています。これは、パーティションがないことを意味し、そのため多くは懐疑的です。

上で示したように、いわゆる高可用性はAを意味するものではありません。さらに、Pが存在しないことを意味するものではありません。 エラーメッセージから多くの面白い判断が推測されます。 ユーザーは単語からPをまったく必要としないため、著者はシステムをCとAに同時にしたいのです。 新しい概念、 つまりCAが導入されました。 作者は概念をいじり、定義なしに新しい概念を発明し始めたようです。 古いものはそのような素晴らしいシステムを説明していませんでした。

続きを読む：

Spannerの多数の内部ユーザーに基づいて、Spannerの可用性が高いと想定していることがわかります。

フレーズ自体は素晴らしいです。 内部ユーザーが「非常にアクセスしやすいと想定している」と言うと、ここからシステム自体について何かがすぐにわかります。 ユーザーが「はい、可用性が高い」と言って、その場で彼らが想定していることについて話すといいでしょう。

以下は魅力的です：

Spannerの停止の主な原因がパーティションではない場合、CAはある意味でより正確です。

つまり ネットワーク接続の違反に関係しない障害がある場合、そのようなシステムはある意味でより正確に（！）CAと呼ばれるべきです。 つまり 他の障害の確率が接続性の故障よりも大きい場合、Pはそうではありません。 この意味で、このフレーズを理解する価値はありますか？

以下は、グラフでサポートされた信頼性の高いシステムを構築したマーケティング上の考えです。 最終的に、CAの単語セットの意味を明らかにする定義が少し下になります。

... CAを効果的に主張するには、システムが相対的な確率のこの状態にある必要があります。

1. 少なくとも、実際には非常に高い可用性を備えている必要があります（そのため、ユーザーは例外を無視できます）。
2. これはパーティションに関するものであるため、パーティションによる停止の割合も低くする必要があります。

Spannerは両方を満たします。

つまり システムは以下を行う必要があります。

1. 実際には高可用性があり、ユーザーは例外を無視できます。
2. ネットワーク分離の可能性は他の問題よりも少ないはずです。

: high availability ? 5 ? 6 ? 9? , . " " , , .

, , CAP . , . , . .

. , , , "What happens during a Partition".

:

Spanner reasonably claims to be an “effectively CA” system despite operating over a wide area, as it is always consistent and achieves greater than 5 9s availability.

, , — X, X. , ? CAP . . , , , P, 2 , .. . CP — .

Even then outages will occur, in which case Spanner chooses consistency over availability.

CA: , .. , CA. , CA. .

: CAP

, , , . , — .

, . , , , CAP . . .

, , , .

おわりに

, CAP . , . AP CP.

, , . , . , :

The CAP Theorem, in this light, is simply one example of the fundamental fact that you cannot achieve both safety and liveness in an unreliable distributed system.

つまり CAP — , .

• C:
• A:
• P:

, YT