CAP定理の図示された証明

BY admin
|

CAP定理は、分散システムにおける基本定理であり、任意の分散システムは以下の3つの性質のうち最大2つを持つことができると述べている。

  • 一貫性
  • 可用性
  • パーティション許容値

このガイドでは、ギルバートとリンチの仕様とキャップ定理の証明を写真付きで要約します！

キャップ定理とは何ですか？

CAP定理は、分散システムが同時に一貫性があり、利用可能であり、分割耐性があることはできないと述べています。 十分に単純に聞こえますが、一貫性があるとはどういう意味ですか？ 利用可能ですか？ パーティショントレラント？ 一体、あなたは分散システムによって正確に何を意味していますか？

このセクションでは、単純な分散システムを紹介し、そのシステムが利用可能で、一貫性があり、パーティション耐性があることの意味を説明します。 システムと3つの特性の正式な説明については、Gilbert and Lynchの論文を参照してください。

分散システム

非常に単純な分散システムを考えてみましょう。 私たちのシステムは、two G_1.とG G_2serversの2つのサーバーで構成されています。 これらのサーバーは両方とも同じ変数v v.を追跡しており、その値は最初はinitially v_0.です。 $G_1.とG G_2.は互いに通信でき、外部クライアントと通信することもできます。 ここでは、私たちのシステムがどのように見えるかです。

クライアントは、任意のサーバーからの書き込みと読み取りを要求できます。 サーバーは要求を受信すると、必要な計算を実行してからクライアントに応答します。 たとえば、ここでは書き込みがどのように見えるかです。

そして、ここでは読み取りがどのように見えるかです。

システムが確立されたので、システムが一貫性があり、利用可能で、パーティション耐性があることが何を意味するのかを見てみましょう。

一貫性

GilbertとLynchが一貫性をどのように記述しているかは次のとおりです。

書き込み操作の完了後に開始される読み取り操作は、その値、または後の書き込み操作の結果を返す必要があります

一貫性のあるシステムでは、ク

一貫性のないシステムの例を次に示します。

お客様に書き込み$v_1るときは、$$G_1$と$G_1$認識し、その時、から読み取$G_2$、行動の便が良いことから、無効なデータ:$v_0$.

一方、ここでは一貫性のあるシステムの例です。

このシステムでは、client G_1clientはクライアントに確認応答を送信する前にその値をG G_2.に複製します。 このように、クライアントの読み込み$G_2$、行動の便が良いことから、最新のもので価値の$v$:$v_1$.

可用性

GilbertとLynchが可用性をどのように説明しているかは次のとおりです。

システム内の障害のないノードによって受信されたすべての要求は、応答

使用可能なシステムでは、クライアントがサーバーに要求を送信し、サーバーがクラッ サーバーはクライアントの要求を無視することはできません。

パーティションの許容値

GilbertとLynchがパーティションを記述する方法は次のとおりです。

ネットワークは、あるノードから別のノードに送信された任意の多くのメッセージを失うことが許可されます

これは、another G_1.とone G_2oneが互いに送信するメッ すべてのメッセージが削除されていた場合、システムは次のようになります。

このシステムは，パーティショントレラントであるためには，任意のネットワークパーティションにもかかわらず正しく機能する必要がある。

証明

一貫性、可用性、および分割許容度の概念を知ったので、システムは3つすべてを同時に持つことができないことを証明できます。

矛盾を仮定すると、一貫性があり、利用可能で、パーティション耐性のあるシステムが存在すると仮定します。 私達が最初にすることは私達のシステムを分けることである。 このように見えます。

次に、client v_1.をG G_1.に書き込むようにクライアントに要求します。 私たちのシステムは利用可能なので、G G_1.は応答する必要があります。 しかし、ネットワークは分割されているので、G G_1.はそのデータをG G_2.に複製することはできません。 GilbertとLynchはこの実行段階をexecution\alpha_1.と呼んでいます。

次に、クライアントにread G_2.への読み取り要求を発行させます。 ここでも、私たちのシステムが利用可能なので、G G_2.は応答する必要があります。 そして、ネットワークは分割されているので、G G_2.はG G_1.からその値を更新することはできません。 それはreturns v_0.を返します。 GilbertとLynchはこの実行段階をexecution\alpha_2.と呼んでいます。

$G_2$を返しま$v_0$社のクライアントのクライアントがすでに書き$v_1るときは、$$G_1$. これは矛盾しています。

私たちは、一貫性のある、利用可能な、パーティショントレラントなシステムが存在すると仮定しましたが、システムが矛盾して動作するようなシステ したがって、そのようなシステムは存在しない。