イノベーション エンジニアブログ


株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます!


このエントリーをはてなブックマークに追加

CAP定理とCloud Spannerについて

はじめに

どうも、bigenです。

以前弊社のKTNさんがCloud Spannerについてとりあげ、
「水平スケーリング可能なRDB!?なにそれすごい!!」という記事を書いていました。
(詳しくはこちら→ お試し Cloud Spanner

その最後に、Googleさんがブログで
「Google SpannerはCPシステムだけどCAと思ってくれて構わないよ」
という謎な見解を発表していたことが書かれていました。

新人エンジニアな僕はそもそもCAP定理というものも知らなかったので本当に謎でしかなかったのですが、
せっかくなので調べてみました。
せっかくついでに僕の理解を図解と共にメモしておきます。

なお、調べるにあたって下記のサイトがめちゃくちゃ参考になりました。

12年後のCAP定理: "法則"はどのように変わったか
https://www.infoq.com/jp/articles/cap-twelve-years-later-how-the-rules-have-changed
CAP定理を見直す。“CAPの3つから2つを選ぶ”という説明はミスリーディングだった
http://www.publickey1.jp/blog/13/capcap32.html

CAP定理

CAP定理(またはブリュワーの定理)とは、

データを保持するサーバが複数繋がったネットワークがあった時、
Consistancy, Availability,Partition-toleranceの3つの性能(CAP)を同時に成立させることはできない

という定理です。
CAPはそれぞれなにかというと、

  • Consistancy(一貫性) : どのサーバから読み取りを行っても、常に最新の書き込みデータorエラーが返ってくる性質(古いデータが返ってくることはない)

  • Availability(可用性) : 故障していない全てのサーバは全てのサービスを提供できる性質

  • Partition-tolerance(分断耐性) : ネットワークが完全に2つのグループに分かれてしまい、互いのグループが通信できないようなネットワーク障害(分断という)が発生しても、サービスが継続して利用できる性質

ということのようです。

どういう意味なのか、図解していこうかと思います。

CA型

まず、一貫性と可用性が成立しているようなネットワーク(CA型)を考えてみましょう。

1.jpg

単純なケースとしてサーバーは2台で、サービスとして変数X(例えばある商品の在庫とか、誰かの貯金残高とか。)を管理しているとしましょう。
この時、一貫性と可用性の性質から、server1からでもserver2からでも、Xは常に書き込みも読み取りもできて、最新のデータを提供できる必要があります。

これを実現する一番古典的なやり方.は、server1でXが更新された時、そのことをserver2に知らせ、server2で管理している変数Xも更新する(上手参照)方法です。
厳密には①と③がほぼ同時に行われるような工夫(トランザクション)が必要です。

この時、server1とserver2の通信は必須であり、ネットワークが分断されたまま一貫性と可用性が成立するサービスを提供することは不可能となります。
つまり、分断耐性の性質は成立できません。

CP型

次に、一貫性と分断耐性が成立しているようなネットワーク(CP型)を考えてみましょう。

2.jpg

分断耐性の性質から、ネットワークが分断されている時でも、何らかのサービスを提供している必要があります。
この時、たとえばserver1でXが更新された時、もう片方のserver2ではそのことを知る術はないため、
一貫性を成立させるためには常にエラーを返し続けることになります。
(一貫性はエラーを返すのはOK。古い情報を誤って渡さなければよい。)

しかしこれは、サービスの一部の機能が利用できない状態になっており、可用性は成立できません。

AP型

最後に、可用性と分断耐性が成立しているようなネットワーク(AP型)を考えてみましょう。

3.jpg

可用性と分断耐性を成立させようとすると、ネットワークが分断されていても、
全てのデータの読み取りや書き込みができる必要があります。

しかし、分断状態ではserver1とserver2は最新のデータを共有できませんので、
一貫性は成立できません。


実際にはもっと厳密な定義と証明があるようですが、定理が言いたいことは十分伝わるかと思います。

Cloud SpannerはCA?CP?

定理を提唱したブリュワー氏によると、このような100%のCPやCAが求められるケースは少なく、
CAP定理を楯に性能限界を議論するのは時代にそぐわないようです。

つまり、例えば完全なCPシステムにしてしまわなくても、
99.9%の一貫性と99.9%の可用性を担保するといったように、少し性能をゆるめることで
擬似的に3つの性質を成立しているかのように振る舞うことは可能だということです。

あるいは別のアプローチとして、Googleが主張する「本当はCPだけど、CAと思っていいよ」といっているのは、次のような内容です。

分断耐性というのは、「万が一分断が起きた時、サービスできるよ」という性質なわけですが、
そもそもネットワークをとてつもなく冗長化して分断が起きないようにしておけば、
その性質がもとめられるシーンは少なくなります。

とはいえ分断したらシステムがダウンしてしまうわけにはいかないので、
いざっていう時はCPとして振る舞うのですが、
分断が起きていない間は一貫性と可用性を常に担保でき、CAとして振る舞えるし、
それはサービス全体の99.9999%の時間をしめるよ、というのがGoogleの主張です。

CPシステムである以上は100%の可用性は成立しないけど、99.9999%可用性があるなら、
それはもはやCAシステム(あるいはCAPシステム?)と呼んでいいだろうということです。

おわりに

冒頭で紹介した記事の中にかかれているのですが、
ブリュワー氏がそもそもこの定理を提唱した際には100%の性能限界について論じることより、
「 全てのネットワーク(あるいはDB)構成者は一貫性と可用性の間で常にトレードオフを意識しなければならない」
ということを言いたかったそうです。

今後ネットワークパフォーマンスを考える際には、ちゃんと意識していこうと思いました。