suzuki79のブログスマートフォン用の表示で見るsuzuki79のブログこの広告は、90日以上更新していないブログに表示しています。Kleppmann元の記事は上のリンクよりご覧になれます。本人の許可を得て、翻訳・掲載したものです。翻訳へのフィードバックはコメントよりお願いいたします。Bloodsという優れたブログで、CAP定理を使ってシステムを評価することが推奨されています。多くの人はこのアドバイスを真摯に聞き、自分たちのシステムをCP(ネットワークの分割のもとでは一貫性はあるが可用性がない)、AP(ネットワーク分割のもとでは可用性があるが一貫性がない)、あるいはまれにCA(これの意味するところは「自分はまだ5年前のCodaの投稿を読んでいません」です)と表現するようになりました。Jeffのこれ以外のすべての指摘には賛同しますが、CAP定理に関しては全く賛同はできません。CAP定理は非常に単純化され、広く誤解されすぎて、システムの特徴を表現するのに全く役に立たっていません。そのため、CAP定理を参照している記述は読まないようにして、CAP定理について語ることを止め、この粗悪なものを葬り去るように私はお願いしています。私たちはより正確な用語を用いてトレードオフを論理的に判断するべきです。(もちろん、皮肉にも人々に書くことをやめるように求めているまさにそのトピックについて、ブログを書いていることは承知の上です。少なくともこのブログによって、CAP定理について語っている人を好きになれない理由を人に聞かれたらこのブログのURLを教えてあげることができるようにはなります。)CAPは非常に狭義の定義を使っていますもし、CAPを定理として参照したい場合(データベースの宣伝材料の中の曖昧で大げさなコンセプトとは対照的に)、厳密になる必要があります。数学には厳密性が要求されます。ある証明で使用される意味と全く同じ意味で用語を使用する場合のみ、その証明は成り立ちます。証明というのは非常に特有の定義を使います。CAPの一貫性(Consistency)が実のところ意味するのは線形化可能性(linearizability)です。これは非常に特定の(かつ強い)一貫性の概念になります。付け加えておくと、ACIDのCはconsistencyのことを指しますが、CAPのCとは何の関係もありません。線形化可能性の意味はあとで説明します。CAPの可用性(Availability)は「障害のないデータベースのノードへ送られたリクエストはエラーのないレスポンスを返さなければいけません」と定義されています。あるノードがリクエストを処理することができるというだけでは不十分です。いずれかの障害のないノードはリクエストを処理することができる状態にある必要があります。高い「可用性」のあるとされる多くのシステムは実際のところこの定義でいう可用性を満たしていません。分断耐性(ひどい名前の付け間違いではあります)とはメッセージの遅延や消失があるかもしれない非同期ネットワーク越しにコミュニケーションをすることを基本的には意味しています。インターネットやすべてのデータセンターはこの特性を備えているため、この問題に関して選択の余地はありません。CAP定理は従来のあるシステムを説明しているものではなく、非常に特定のシステムのモデルを説明しているということに気をつける必要があります。CAPのシステムモデルというのはたったひとつの読込-書込レジスタです。CAP定理は複数のオブジェクトに関わるトランザクションについて何も言及していません。してひとつのレジスタに落とし込むことができなければ、その話は定理の範囲外の話になります。CAP定理で唯一考慮されている障害は、ネットワーク分割です。(つまり、ノード自体は起動していますが、ノード間のネットワークが機能していないということです。)このような障害はもちろん発生します、しかし、他の障害も起こりえます。ノードはクラッシュすることもあれば、リブートされることはあります。ディスク容量が足りなくなることもあれば、ソフトウェアのバグに遭遇することもあります。分散システムを構築するにあたり、より広い範囲でトレードオフを考慮する必要があります。CAP定理に集中しすぎるあまり他の重要な問題を無視することにもなりかねません。CAP定理は可用性以上に気にされることが多いレイテンシに関して何の言及もありません。事実、CAPの可用性があるシステムは恣意的にレスポンスが遅いことを許容していて、それにもかかわらず「可用性がある」と言われています。極端なことを言うと、ページの読み込みに2分かかるシステムを可用性があるシステムとユーザは呼ばないでしょう。証明の正確な定義が自身の言葉と合致している場合、CAP定理は適用できます。別の観点で一貫性や可用性という言葉を使っている場合、CAP定理がまだ適用できるという期待はできません。いくつかの言葉を再定義すれば、突然不可能なことが可能になるという意味ではありません。CAP定理を指針として使うことができませんし、自身の観点を正当化するためにCAP定理を使うことはできませんということです。CAP定理が適用できないのであれば、自分自身でトレードオフを考え抜く必要があります。自身の言葉の定義を使って一貫性と可用性について論理的に判断することはできますし、自身の定理を証明することも大歓迎です。自身の定理をCAP定理と呼ぶのはやめましょう、その名前は既に使われているので。線形化可能性(Linearizability)線形化可能性(つまり、CAPの「一貫性」を指します)について馴染みがないかもしれないので、簡単に説明します。正式な定義は全く簡単なものではなりません、しかし、形式ばらずに記述すると、鍵となる考えは以下のようになります。操作Aが成功した後に操作Bが開始された場合、操作Aが完了した状態もしくは最新の状態のシステムを操作Bは見なければなりません。この考え方をより具体的に説明するため、線形化可能でないシステムの例を考えてみます。下記の図を見てください。(まだリリースされていない自分の本からこっそりプレビューしています)この図は、同じ部屋にいるアリスとボブが2014年W杯の決勝戦の結果を携帯電話で見ている状況を表しています。勝敗の結果が発表された直後に、アリスはページを更新し、勝者の発表を見て興奮した様子でボブにそのことを話します。ボブは信じられないと入った様子で彼の携帯電話で再読込ボタンを押します。時差があるデータベースレプリカの方へ彼のリクエストは行ってしまい、試合がまだ続けられていると携帯電話に表示されます。アリスとボブが再読込を同じ時間にした場合、2つの問い合わせの結果が違うとしてもそれほど驚かないでしょう。その理由はサーバで処理される正確な時刻を彼らは知らないからです。アリスから勝敗結果を聞いた後にボブは再読込ボタンを押したため(問い合わせが開始されたため)、アリスと同じ結果が返ってくることを期待します。彼が古い問い合わせ結果を見たという事実は、線形化可能性に違反しています。アリスのリクエストの直後にボブのリクエストがされたこと(つまりこれらのリクエストは同時実行ではないことです)を知ることができるというのは、別のコミュニケーショチャネルを通してアリスの問い合わせ結果についてボブが聞いたという事実があることで成り立ちます。あなたがデータベースを構築しているなら、クライアントがどんな別チャネルを持っているかということは知ることができません。そのため、線形化可能なセマンティック(CAPの一貫性)をデータベースで提供したい場合、複数の場所にデータのコピー(レプリカ、キャッシュ)がある場合でもあたかもひとつのデータコピーしかないように振る舞わせる必要があります。これは非常にコストが高くつく保証を提供することになります。多くの調整を必要とするからです。コンピュータのCPUでさえ、ローカルRAMへのアクセスは線形化可能性を提供していません。現代のCPUでは、線形化可能性を得るために明示的にメモリバリア命令を使用する必要があります。線形化可能性を提供できているかのテストさえもやりにくいです。CAPの可用性ネットワーク分割が起きた場合に線形化可能性か可用性のどちらかを諦めなければいけないことについて、少し話しましょう。2つのデータセンターにデータベースのレプリカがあるとしましょう。正確なレプリカ方法は今は問題にしません。レプリカ方法は、シングルリーダー(マスタ/スレイブ)、マルチリーダー(マスタ/マスタ)、クオラムベースレプリカ(Dynamo形式)のどれでも構いません。レプリケーションの仕様は、ひとつのデータセンターに書き込まれたデータはどんなときでも他のデータセンターへも書き込まれる必要があるというものです。クライアントはひとつのデータセンターにしか接続しないものと仮定して、2つのデータセンター間にネットワークリンクが存在している必要があり、レプリケーションする際はそれ越しに行います。ネットワークリンクが切断された場合、つまりこれはネットワーク分割を意味していますが、何が起きるでしょう。2つのうちから1つを選ぶべきなのは明らかです。アプリケーションが動き続けられるようにデータベースへ書き込みを許しています、そうすることで双方のデータセンターで完全に利用可能な状態にします。レプリケーションのリンクが切断されている限り、一方のデータセンターに書き込まれたいかなる変更は、もう一方のデータセンターに現れることはありません。2へ接続していることになります)。線形化可能性を失いたくない場合、リーダーと呼ばれるであろう1つのデータセンターへ書き込みも読み込みも行うようにする必要があります。一方のデータセンターでは、ネットワーク分割が直り、データベースが再び同期できるようになるまでデータベースは書き込みと読み込みを受け付けることを止める必要があります。なると、リーダーでないデータベースは障害があるわけでないにも関わらず、リクエストの処理は行えません。CAPの可用性は満たせません。(ところで、これが本質的にはCAP定理の証明になります。この例では2つのデータセンターを使用していますが1つのデータセンターの中でのネットワーク障害と同様に適用することができます。2つのデータセンターとしたほうが簡単だと思っただけです。)選択肢2において、概念的な「利用不可能」な状況においては、片方のデータセンターで幸運にもリクエストが処理されるということは特筆すべきことです。そのため、もしシステムが線形化可能性を選択したとしても、ネットワーク分割が自動的にアプリケーションが停止するということにはなりません。リーダーのデータセンターへすべてのクライアントの接続先を変えることができるとすると、クライアントは事実上ダウンタイムに直面することはありません。実際の可用性は全くCAPの可用性とは対応していません。アプリケーションの可用性はおそらく何かしらのSLAで測定されるでしょう(例えば、99.9%の適切なリクエストは1秒以内に成功応答ををします。)、しかし、CAPの可用性のあるシステムとCAPの可用性のないシステムのどちらでもそのようなSLAを満たすことができます。実際には、複数のデータセンターをもつシステムはたいてい非同期のレプリケーションを行うように設計されます、そのため線形化可能性は提供されません。その選択をするのは広範なネットワークにおけるレイテンシがたいてい理由となります。データセンターに耐性を持たせたいためでもなく、ネットワーク障害のためでもありません。多くのシステムは線形化可能でもなければCAPの可用性でもありませんCAP定理の一貫性と可用性の厳しい定義のもとで、どうシステムを評価することができるのでしょうか。多くのリレーショナルデータベースでは標準的なレプリケーション方法であるシングルリーダー方式でのレプリカデータベースを例にとってみます。この設定では、もしリーダーとクライアントが分断された場合、データベースへの書き込みはできません。フォロワー(読み込み専用のレプリカ)から読み込みはできたとしても、書き込みができないという事実はシングルリーダーのセットアップではCAPの可用性は満たせないことを意味します。このような設定は「高可用性」としてよく宣伝されていることは忘れてください。シングルリーダーのレプリケーションはCAPの可用性がないとして、そのことでCPとなるのでしょうか。早まらないでください。フォロワーからの読み込みをアプリケーションができて、かつレプリケーションが非同期な場合(多くのデータベースでは初期設定です)、フォロワーはそこから読み込みをしたときリーダーより少し遅れているかもしれません。その場合、読み込みは線形化可能ではないでしょう。CAPの一貫性はありません。スナップショット分離/MVCCを提供するデータベースは意図的に線形化可能性ではありません。線形化可能性を強制するとデータベースが提供可能な同時実行のレベルを下げるからです。PostgresSQLのSSIは直列化可能性を提供しますが、線形化可能性は提供していませんし、Oracleはどちらも提供していません。あるデータベースがACIDとされているからといって、CAP定理の一貫性を満たすことにはなりません。そのため、これらのシステムはCAPの一貫性もなければ、CAPの可用性もありません。CPでもAPでもなくただのPです、それが意味することがどんなことであろうも。(そうです、「3つのうち2つ」という言い方は、3つのうち1でもいいですし、3つのうち何も選ばないということも可能です。)NOSQLはどうでしょうか。MongoDBを例にとってみましょう。シャードごとに1つのリーダーがいます(または、スプリットブレインモードに陥らなければ、少なくともそういうことになっています)。いうことは、さきほどの議論よりCAPの可用性ではありません。高い一貫性の設定をしたとしても線形化可能な読み込みができないことをKyleが最近示しました。そのため、CAPの一貫性もありません。Dynamoから派生したRial、Cassandra、Voldemortは高い可用性に最適化されたためよくAPと呼ばれていますがどうでしょうか。読み込みも書き込みも1つのレプリカ(R=W=1)でよければ、本当にCAP-可用性になります。クォーラムの書き込みと読み込み(R+W>N)を求めていて、ネットワーク分割がある場合、分割された少数派側へ接続したクライアントはクォーラムへ到達できません。そのため、クォーラム操作はCAPの可用性を満たしません(少数派側に追加レプリカをデータベースがセットアップするまでの、少なくとも一時的にはです)。時々クォーラムの読み込みと書き込みは線形化可能性を保証していると主張している人を見かけるかもしれません。それに頼るのは賢明ではありません。スロッピークォーラムとリードリペアのささいな機能の組み合わせで厄介な滅多に発生しない問題を引き起こします。削除したデータが復活する、レプリカの値の数が元々のWより下回る(クォーラムの条件に違反します)、レプリカノードの数が元々のNより上回る(これもまたクォーラムの条件に違反します)といったようなことがあります。これらすべてが線形化可能性でない結果につながります。これらのシステムは悪いシステムではありません。どんな時でもプロダクション環境でちゃんと使えています。今のところ厳密にAPやCPに分類することができていません。その理由は、特別な操作や設定に依存するためであったり、あるいはシステムがCAP定理の厳しい一貫性や可用性の定義をどちらも満たすことができないからです。ケーススタディ:ZooKeeperZooKeeperはどうでしょうか。合意アルゴリズムを使用しているので、一般的には可用性より一貫性を選択している明確なケースと見なされるでしょう(つまりCPシステムということです)。ZooKeeperのドキュメントを見ると、デフォルトでは線形化可能な読み込みを提供していないことを非常に明確に述べています。各クライアントはサーバノードのどれか1つに接続します、そして、たとえ他のノードがより最新の書き込みがされていても読み込みを行う際にはその接続したノードのデータのみを見に行きます。クォーラムで読み込む、もしくはすべての読み込みをリーダーへ接続するより高速に読み込みは行えます。ZooKeeperはデフォルトでCAP定理の一貫性の定義を満たしていないことになります。読み込みに先立ってsyncコマンドを実行することで、ZooKeeperでの読み込みを線形化可能にすることができます。パフォーマンス上のペナルティを伴うため、それはデフォルト設定ではありません。syncコマンドを実行することはしますが、普通は常に行うことはしません。ZooKeeperの可用性はどうでしょうか。合意に至るため、つまりは書き込みを処理するためにはZKはクォーラムの多数派を必要とします。多数派側ノードと少数派側ノードで分割された場合、多数派側は機能し続けますが、少数派側ノードはたとえノードが起動していても書き込み処理が行えません。それゆえ、ZKでの書き込みはネットワーク分割状況ではCAPの可用性はありません(多数派側では書き込みの処理を続けることができているにもかかわらず)。面白いことに、ZooKeeperの3.4.0では読み込み専用モードが追加されました。これにより、ネットワーク分割された少数派側のノードが読み込みリクエストを処理を続けられるようになりました。クォーラムが必要なくなりました!読み込み専用モードはCAPの可用性にあたります。まとめると、ZooKeeperのデフォルトではCAPの一貫性(CP)やCAPの可用性(AP)どちらでもなく、ただのPです。お望みであればsyncを実行してCPにすることができます、さらには正しい設定をすれば(書き込みではなく)読み込みにおいて実際にAPにすることもできます。これは苛立たしいです。デフォルトで線形化可能性がないことだけで、ZooKeeperを一貫性がないと呼ぶのはその特徴を本当にひどく誤って表現しています。ZooKeeperは実際に優れたレベルの一貫性を提供しています!因果一貫性の継続した保証と組み合わせてアトミックブロードキャスト機能(これは合意アルゴリズムに還元されます)を提供しています。この因果一貫性は自分の書き込みを読み込むこと、モノトニックな読み込み、一貫したプリフィックス読み込みを合わせたものより強力なものです。このドキュメントでは連続一貫性を提供していると書いていますが、これは自身を低めに評価しています。ZooKeeperの保証は連続一貫性よりはるかに強力なものだからです。ZooKeeperが示したように、パーティション分割があるもとでCAP一貫性とCAP可用性のどちらもない、さらにパーティション分割されていない状況でさえ線形化可能でないのがデフォルトというシステムは非常に合理的です。frameworkでPC/ELがそれにあたるのかもしれません、しかしCAP以上にはっきりしたものは何も見つけられませんでした。)CP/AP:誤った二分法1つのデータストアさえ明確にAPやCPに分類することさえできなかったという事実は私たちに何かを教えてくれているはずです。この定理はシステムを表現するための適切なラベルでは全くなかったということです。APやCPのカゴへデータベースを置くことをやめるべきと私は思います。ひとつのソフトウェアの中でさえ、異なる一貫性の特性がある多様な操作を行えるからです。CAP定理の定義下で多くのシステムは一貫性もなければ可用性もありません。システムをPと人が呼んでいることは聞いたことがありません。ひどいシステムのように見えるからでしょう。そのシステムはひどいわけではありません、もしかしてそれは完璧に合理的な設計をされているかもしれませんし、ただCP/APのカゴに合っていないだけです。ソフトウェアはきっちり2つのかごのどちらかに合わないのにも関わらず、とにかくソフトウェアを2つのかごの一方へ無理やり入れようとしています。なると、どんな意味が合うにせよ「一貫性」や「可用性」の意味を変更することは避けられません。不幸にも、言葉の意味を変更すると、CAP定理はもうはや適用することはできません。それゆえ、CP/APの区別は完全に無意味なものになります。2つのかごの1つにシステムを入れることで非常に多くの事柄が失われてしまいます。フォールトトレランス、レイテンシ、プログラミングモデルの簡潔さ、操作性など多くの考慮すべきことがあります。そのことが分散システムの設計の糧になるのです。1ビットの情報にこの事柄をエンコードするのは全く不可能です。ZooKeeperがAPの読み込み専用モードにも関わらず、このモードはそれでも書き込みされた情報の全順序を提供します。これはRiakやCassandraのようなAPのシステムより非常に強力な保証になります。そのため、同じかごにこれらのシステムを投げ込むのはばかげています。Brewerでさえ、CAPはミスリーディングで単純化しすぎていると認めています。2000年、それは分散データシステムのトレードオフについての議論を始めるためのものでした。非常に役に立ちました。それは新たなに発見された公式となるように作られたものでもなければ、データシステムの厳格な分類スキーマになるためでもありませんでした。15年経過して、私たちは様々な一貫性モデルとフォールトトレランスモデルを持つはるかに強力で広範なツールを選ぶことができます。CAPはすでにその目的を果たしています、ですので今こそ前進するときです。自分自身で考えられるようになろうCPとAPがシステムを表現することや評価することに適していないとすると、代わりに何を使うべきなのでしょうか。ひとつの正しい答えはないと思います。多くの人はこれらの問題に対して熱心に考え、問題を理解するための用語やモデルを提案してきました。それらの考えを学ぶために、この分野の文献をより深く探る必要があるでしょう。Terryの論文が最初に取り掛かるものとしてはいいでしょう。その論文で彼は野球の例を使って結果整合性の様々な異なるレベルを説明しています。(私みたいに)アメリカ人でもなく野球について全く知らなくても非常に読みやすく明快な論文です。Bailisとその他の人によって研究されています。Kingsburyが好んで紹介する一貫性レベルの階層の意味について説明しています。)これらを読んだら、この分野の文献のより深いところへ潜る準備ができているでしょう。この投稿を通して多くの論文へのリンクを散らしています。多くの専門家は既にあなたのために多くの事を解決しています。最後の手段として、元の論文に立ち向かえない場合、私の本を読むことをお勧めします。この本では、親しみやすい方法で最も重要な考え方をまとめています。(ご覧の通り、この投稿がセールストークにならないようにとても努力しました。Reedの本が良いでしょう。学ぶ方法はどれであれ、好奇心をもって辛抱強くなることをお勧めします。これはそれほど簡単なことではありません。それに見合う価値はあります、なぜならトレードオフについて判断し、自身の特別なアプリケーションにどんなアーキテクチャが最適か答えを出せるようになるからです。何をするにせよ、CPとAPについて語るのは止めて下さい、本当に何の意味もありません。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。