時空に拡張されるCAP定理:落ちず、速く、確実なサーバをどう作るのか?

Top / テクニカルノート / 時空に拡張されるCAP定理:落ちず、速く、確実なサーバをどう作るのか?

クラウドシステム上に限らず、サーバを作る時、次の2つはどちらも「大切だ」と思うことでしょう。

  1. サーバの可用性(落ちないサーバであること)、レスポンス(速いサーバであること)
  2. サーバの一貫性(書いたデータが消えないということ)

しかし分散システムにおいては、実際は「どちらか1つを優先するしかない」というのが、定理上の真理です。

どういうことなのでしょうか?


データの一貫性を過度に重視することが可用性を低下させている

データストアをどのように設計するか?

分散システムを構築するにあたり、「データストアをどのように設計するか」は重要なテーマのひとつです。

残念ながら機械である以上サーバーはいつかは必ず壊れます。複数台のサーバーで構成されているシステムの内で、たった1台のサーバが故障するだけでサービス停止が発生したり(可用性の低下)、データが壊れること(一貫性の低下)によりサービス終了するわけにはいきません。

そこで、データは複数箇所に保存(分散システム)するべきだと考えられます。

しかし、複数のサーバーで共通のデータを持たねばならない場合、次の3つの望まれる性質のうち、2つしか同時に満たすことができません。これを『CAP定理』といいます。

 

CAP
C:Consistency(一貫性)
すべてのサーバーで統一された最新データを持っていること。
A:Availability(可用性)
そのデータの更新に対する高可用性。つまり、常に動いているということ。
P:Partition-tolerance(分断に対する許容)
サーバー同士が分断する状態がありえる、または分断が起きてしまった=許容された状態
※日本では一般に分断耐性と翻訳されることが多くありますが、分断耐性という言葉による混乱が多々見られるので、本ドキュメントでは「tolerance」を「許容」と訳しています。

簡単に説明するため、2つのサーバーに同じデータを保存したい場合を考えます。CAP定理では、『P-A』『P-C』『A-C』の3つのパターンのみが達成可能です。

P-A
サーバーに分断が発生したとき(P=分断が起きてしまった)、可用性(A)を考えて片方のサーバーにだけ書き込みをしてしまうと、2つのサーバーでは同じデータを持つことができません。そこで一貫性(C)が失われます。
P-C
同様にサーバーに分断が発生したとき(P=分断が起きてしまった)、一貫性(C)を考えて2つのサーバーで同じデータにするには、システムを一時停止するしかありません。つまり可用性(A)が失われます。
A-C
分断されていない状態(Pが起きていない)ときのみ、一貫性(C)も可用性(A)も得ることができます。
 

二つのサーバーでCAP定理を考える

例えば、遠隔の拠点(例として2つのデータセンター)にそれぞれサーバーが設置されている分散システムで、データの出し入れなどの協調動作する場合、短時間といえどこれらのサーバー間の通信が分断されることを避けることはできません。したがってシステムの全体設計として、分断(Partition)が起きることを許容(Tolerance)しなければならず、『P』は必須となります。CAP定理に従うと、結果として残りは『A』または『C』のどちらかを選ぶしかありません。

視点を変えて、近距離に設置したの二つのサーバーではどうでしょうか?

『P』を選ぶ必要がない、すなわち分断は必ず起きないと保証されるとき、『A』と『C』は同時に成立するように見えます。データの一貫性が保たれ可用性もある(動作が継続する)。これは理想的なシステムと考えられそうです。

そこで、ミラー化されたストレージサーバー・システムを想像してみましょう。ミラー化されたストレージサーバーでは、一方のストレージサーバーがダウンしてももう一方のストレージサーバーのみで動作を継続するため、一見するとデータ一貫性も可用性も保たれているように見えます。

 

xentec1-2.jpg

具体的に想像するため、ストレージサーバー『1号機』と『2号機』があり、同じデータを書き込むリクエストがあったと仮定します。

システムは『1号機』と『2号機』の両方に書き込み要求をし、その書き込みが完了したという「完了報告」(一般にAcknowledge/アクノリッジといいます)をもらってから、ようやく次のデータの読み書きに移ることができます。

こうしなければ一貫性(C)を保つことができません。

 
xen

ここでもし、『1号機』はすぐに書き込みを完了したが、『2号機』の書き込みが遅れた場合はどうなるでしょうか? 

この場合、『1号機』だけが最新の状態になり、『2号機』はどうなっているのかわかりません。つまりこの瞬間においては分断が発生(P)しているのです。

 

『A』『C』のどちらかを選ばなければならない

あなたがプログラマーだったとしたら、一方のストレージ応答が遅れた場合の処理をどう書きますか? おそらく、できることは、次のどちらかか、両方の組み合わせしかないでしょう。

  • 『応答を待ち続ける』
    • この場合は、データの一貫性(C)を保つことを重視していることになります。ただし、『2号機』の書き込み完了を待つ間(Δt)、そのシステムは停止することになるため可用性(A)を失います。
  • 『応答を待たずに進む』
    • この場合は、『1号機』だけで動作を継続することから可用性(A)を重視していることになります。ただし、『1号機』と『2号機』のデータ整合性が崩れるため、一貫性(C)を失います。

つまり、近距離の二つのサーバーであったとしても、プログラマーは分断が発生する前提で『A』『C』のどちらかを選ばなくてはなりません。

※この文書でのΔtは、ある時間t1から、ある時間t2までの間の、一定の時間Δt=t2-t1を意味しています。ここでは、とある一定の時間だと考えれば良いでしょう。

一貫性を保つことで可用性の低下(レスポンス性の低下)が発生する

実際のストレージシステムにおいては、この遅延時間『Δt』はしばしば発生しています。たとえ同じハードウェア・同じソフトウェアのストレージシステムを用いたとしても必ず発生します。上の例では、『2号機』の書き込み遅延が終了するまでの時間(Δt)が分断が発生(P)している時間になります。

これはCAP定理自体を、マクロな時間軸の設計視点から、一定の短い時間(Δt)を考慮したミクロな時間軸の設計視点へ概念を拡張しなくてはならないことを意味しています。ほぼすべての分散システムにおいて、Δtのようなごく短時間の間に、分断『P』が発生したり消滅したりしているのです。したがって、分散システム上で処理を記述するプログラマーは、必ずどこかで『A』と『C』のどちらかを選ぶ必要があります。

現実的なミラーストレージをミクロ的な視点から見ると、書き込み遅延により分断が発生(P)した場合、基本的にはタイムアウトが発生するまでは書き込み完了を待ち続けます。すなわち待つ(停止する)ことでΔtの間の可用性(A)を捨て、一貫性(C)を保つのです。この「Δtの間待つ」という行為が多数発生しているシステムは、マクロ的な視点からは「全体的に遅いシステム」に見えることになります。

なお、タイムアウトが発生してしまった場合は、そのタイムアウトが発生した片系のシステムを切り離します。それにより一貫性(C)が捨てられ、可用性(A)が選択されて動作を継続します。

さて、多くの3-Tier型クラウドシステムでは、ハイパーバイザー層で共有ストレージ(SANストレージ)を利用し、この層で一貫性(C)を担保しようとします。ストレージは、複数のハイパーバイザーから届く様々なリクエストを、一貫性を保ちつつ処理するため、大小様々な遅延を発生させています。

これにより一貫性は保たれますが、マクロの視点からは上述のとおり「全体的に遅いシステム」に見えます。一貫性を重視しすぎることで、可用性の低下(レスポンス性の低下)が発生してしまうのです。

つまり「データ書き込みに安全性があるストレージは遅い」ことになります。

コラム

ミラーストレージのような分散システムでは、片系ストレージでタイムアウトが発生することにより、その切り離しが発生します。このとき、一貫性(C)が失われ、代わりに可用性(A)を選択することになります。タイムアウトにより『P-C』のシステムが『P-A』のシステムへと入れ替わるのです。

これをマクロ視点から見た場合、仮にタイムアウトまでの時間を無視できるのであれば、ミラー化された冗長ストレージシステムは一貫性(C)ではなく、可用性(A)を重視したシステムといえます。

実際には、片系が切り離されデグレードとなった状態で、一端、分散システムから単一系になります。再度、リカバリー(リビルド、リシルバーなど)処理が完了すると、元の冗長された分散システムへと戻ります。

このようにCAP定理は、Δtの長さによって、短い時間の単位で考えるミクロな視点と、全体を見たマクロな視点のどちらでも考えなくてはなりません。


レスポンスの速いサーバ(可用性の高いサーバ)はどう作るのか?

ここまで述べたことから、ある一定の時間Δt内に応答を返す必要があるならば、ある段階で「一貫性(C)を捨て、可用性(A)を重視する」しかないことがわかります。「高レスポンス」とはいうのは、「ある一定の十分に短い時間Δt内に、システムが応答すること」とも定義できます。これまでの例からわかるとおり、時間軸にCAP定理を拡張するならば、可用性と高レスポンスとは同義です。したがって高レスポンスのサーバを作る為には、データ一貫性をある程度捨てなくてはならないことを意味します。

今まで上げたとおり「データ一貫性(C)はどの程度必要か?」を考える必要があります。

そこで今度は時間軸ではなく、空間(エリア)をイメージします。

一般に、書き込んだデータを失う(一貫性を失う)ことは、大問題です。しかし、サービスを役割ごとに分割することで、「あるサーバーにはデータ一貫性が必要」だが「あるサーバーは数時間に一度の更新しか発生しない」など、様々な種類に分けることができます。これが「空間(=エリア)でわけていく」ということです。

例えば、データ更新がない・または少ないウェブサーバーやアプリケーションサーバーであれば、あらかじめ同じデータを持つサーバーを複数用意することで、1台のサーバーがダウンしてもサービスを継続することができ、可用性が担保されています。。

また一方、この状態は同じデータが何らかの枠組みで全てのサーバに保存済みであるなら、一貫性が保たれています。

つまり、一貫性も可用性も確保出来ています。なぜ2つとも満たされているのでしょう?それは、この時間のみこれらのサーバの間は数理的に(データ的に)分断されていない為なのです。

同じシステムにおいても、ある時間、ある空間においてだけ、C-A-Pの選択状況が異なることを意味しているのです。

 

xentec3.jpg

一般的なウェブサービスでは、コンテンツの更新頻度と参照頻度を比べた場合、参照頻度がずっと高いはずです。データ更新用サーバーと参照用サーバーを分け、更新用サーバーで更新されたコンテンツを参照用サーバーにコピーするような仕組みを用意することができるのであれば、更新用サーバーは一貫性を重視し、参照用サーバーは可用性を重視することで一貫性と可用性のベストバランスを実現できるでしょう。

※その場合、更新用サーバーから参照用サーバーへとコピーする時間を考慮する必要があります。コピーする時間(Δt)は、更新用サーバーと参照用サーバーのコンテンツに差異がある状態のため、人によってアクセスするサーバがことなり、異なるデータをみる、つまり一貫性が失われることを許容しなければなりません。これが許容できないならば、同期が終わるまでサーバを一時的に停止するしかありません(可用性が失われる)。

 

このように、サービスを構成するサーバー空間を決め、「一貫性が必要なもの」と「可用性を重視・高レスポンス性が必要なもの」にそれぞれ分離することで、エンドユーザーが感じる快適さを大きく向上することができます。言い方を換えると、エンドユーザーからのアクセスが、一貫性が必要なサーバーにアクセスしなければ、サーバーのレスポンスは向上し、快適なサービスができあがるのです。


時間と空間の両方で狭域化する!

可用性、つまり、落ちないこと、レスポンスが良いサーバを作ることは、サーバエンジニアの極みです。

どのようにそういうサーバを作れば良いのでしょうか?

それは時空を支配して分割していくのです。時間Δtをなるべく小さくし、空間を分割して広域から狭域へと狭めていく。

一貫性の必要な部分を時空でミクロにして狭域にすればするほど、マクロな視点では高レスポンスなのにデータが安全なシステムが生まれていきます。

システムにもよりますが、多くのシステムでは、可用性より一貫性が必要なサーバーは、全体の中の一部です。一貫性が必要な時間的尺度Δtも、異なります。

にもかかわらず、システム全てに影響するインフラ層、「クラウドを構成するシステム」内で、常に一貫性を担保するということは、もっとも広域なところでCAP定理の範疇を決めていることになります。これはもっとも非効率で、お金のかかることではあります。

そのためには、自分が利用しているクラウドサービスが、データ一貫性をどのような設計思想で考えられているのか?を、考慮しなくてはなりません。データ一貫性を重視するストレージシステムへの書き込みは、そうでないストレージに比べると遅く、また容量単価も高価になりがちだからです。

例えば、当社のプライベートクラウドの場合、次の様な性質を持ちます

当社サービス名優先要件設計思想
High Response Private Cloud独立性/可用性相互のハイパバイザ間に関連は持たず、短い間隔のバックアップのみ取得される。メインデータとバックアップとの間は非同期の分散システムなので、可用性が重視されているとも言える。
VMware Private Cloud一貫性冗長ストレージを持つストレージファブリックを用い、データ一貫性を重視
Solaris SPARC Private Cloud一貫性最重要視ミッションクリティカルなシステム向けにデータ一貫性に主眼をおいた設計。常に複数のストレージシステムにダブル・ライトされるため、データ書き込みの応答速度は下がるが、一貫性を保つ

下に行くほど、一貫性重視になる為、レスポンス速度は遅くなります。仮想サーバのデータは比較的守られやすい構造になるため、業務システムにおけるシステムの一貫性をクラウドインフラに任せざるを得ないならば、VMware Private Cloudは向いていますが、ストレージコストは高めです。

一方、なるべく狭域で一貫性を実現するならば、High Response Private Cloudの上に、そのサービスだけ一貫性を持つ仕組みを作ることもできます。High Response Private Cloudは、局所的でそれぞれのハイパバイザ間の関連を持たず、独立された実装のためにストレージは高速です。

これには、たとえばデータベースであれば、レプリケーションやクラスター機能を利用します。

これを異なるハイパバイザの仮想マシンの上で行えば、そのデータベースだけ複数のハードウェアに分散して格納することになります。(仮想化システム全体で一貫性を担保する事に比べて、)この場合の書き込み応答は、マスターとスレーブの2台のハードウェアに書き込みを行った後にレスポンスを返すことになるため、若干の遅れだけですみます。

また、データベースだけでなく、分散ストレージ・分散KVS等のシステムを利用し、複数のハイパーバイザーの上に適度にデータストアを分散・保存する方法もあります。これら分散型のものは、一貫性を逆に持たず、可用性だけを求めるケースもありますから、それぞれのサービスにより、一貫性をアルゴリズムの面で管理したり別の物で保つ必要があります。

参考として、ミドルウェアで行う分散技術には次の様なものがあります。

  • MySQL
    • グループレプリケーション
  • PostgreSQL
    • レプリケーション
  • Hadoop
  • redis
  • DNS
  • LDAP

これらの分散技術は、それぞれ異なる思想を持って作られているため、それぞれ特徴にあった物を選ぶ必要があります。

それぞれの特性を良く理解し、どの仕組みがどのレベル、どの単位での一貫性を持つのかを押さえておく必要があります。


サーバーはいつか必ずダウンする

残念ながら、サーバーはいつかダウンします。そしてダウンしないシステムを構築する銀の弾もありません。

サービスの可用性(≒レスポンス速度)とデータの一貫性は、システムにおいては二律背反で、理想的にはどちらも重視したい事柄です。しかし、現実的には2つが天秤に乗せられている以上、その天秤に全てのシステムを乗せるのではなく、時空を支配し、時間軸でも空間軸でも、なるべく狭域で優先事項を切り替えることで、矛盾する目的は、「なんとなく」達成できるようになるでしょう。

システムにおいては、この「なんとなく」が、とても大切なのです。

 

本記事の関連サービス

 

Private CloudPrivate Cloud
NetworkNetwork
OtherOther