今更CAP定理で分散データストアの勉強を始めてみた

長くなったので三行でまとめると

  • CAP 定理を素人なりに調べてみた
  • 分散データストアを CAP 定理で俯瞰してみた
  • どのデータストア使うかの決定因子は CAP 定理的な視点の方がインタフェースとかより先

異論は認めるというか、専門知識ゼロなのでもっと正しい理解があればぜひ教えてくださいませ。

はじめに

僕は MySQL 厨なんですが、最近はやれ「MongoDB がいい」だの「HBase 最高」だのとよく聞きます。これら多種多様なデータストアを語る上で、「RDBMS VS NoSQL」みたいに問い合わせ言語の方式やデータ保存形式の違いで語るのは宗教論かなぁと僕は思ってます。単体プロセスのデータストアとしての特徴とか性能とかは正直なんでもいいかなぁと。

思うに、本質的に重要なのは MySQL の master-slave&sharding という Web で今までスタンダードに使われてきた分散データストアのアーキテクチャに対して、多様なアーキテクチャが提案され実際に使われ始めてきたという事だと思います。事実、最近出てくるデータストアのほとんどはプロセス単体での利用形式よりも、多数のノードに分散して保存することを最初から想定して作られています。

この視点で言えば、それぞれの方式に一長一短があり、それぞれに違ったトレードオフの解決を行っているので、すべてのパターンに置いて優っている様なものは存在しません。残念ながらここは MySQL 厨とはいえ認めざるを得ない。

という感じにようやく最近思ってきたので、いくつかのデータストアを調べてみようと思いました。ただ、漠然と特徴とか調べても、「で、MySQL と何が違うの？」ってところが「NoSQL である」くらいしか分からなくて意味が無い。そんな折に CAP 定理というものがあるということを知りました。

CAP 定理

CAP 定理とは分散データストアに関するとある定理で、その最初の理解としては下に一部引用している文書がとても有益です。ちなみにこの文書は Julian Browne さんの原著を結城浩さんが翻訳されているものです。

彼の主張によると、ある三つのシステム要件が存在し、 その三つの要件は分散環境にアプリケーションを置こうとすると特別な関係を持つ。 (彼はウェブに焦点を置いて話をしたけれど、 複数の事業所や国をまたぐ今日の企業ビジネスにも同じことが言える。 そこにはデータセンターや LAN, WAN があるからだ。)

三つの要件とは 一貫性(Consistency)、可用性(Availability)、 分割耐性(Partition Tolerance) のことで、 ブリュワーの定理の別名 … CAP … はここから来ている。

BrewersCapTheorem – ブリュワーの CAP 定理

正直論文とか苦手でアカデミックなことはさっぱりなんですが、Wikipedia を見るに

ノード間のデータ複製において、同時に次の 3 つの保証を提供することはできない

CAP 定理 – Wikipedia

となっていて、つまり、「Consistency」「Availability」「Partition Tolerance」の 3 つをすべて保証するようなデータストアは存在しないという事のようです。この定理の証明的なものは先の Browne さんの記事の中の図で解説されてる部分がとても分かりやすい。MySQL の言葉で語ればこんな感じ。

  • 構成

    1. N1(master)から N2(slave)へレプリケーションされているとき
    2. N1 で V0 -> V1 に UPDATE される
    3. それが N2 に伝えられて、V0 -> V1 に UPDATE されて整合性が取れる

  • もし 2.と 3.の間でネットワークが分断されると(レプリが切れると)

    • N2 には更新が到達しないので、N2 は古い V0 を返し続ける
    • →Consistency が崩れた状態

という感じで、MySQL の master-slave 構成というのは Partition Tolerance を保証するために実は Consistency を捨てている様です。

ところが、CAP 定理の実例を見てみると、RDBMS は「CA 型」、つまり Partition Tolerance を保証していないタイプに分類されている事がほとんどです。Wikipedia もそうだし、下記のエントリの図でもそうなっています。

でも P を保証しないってどういう意味でしょう？さっき見たように MySQL はネットワーク分断しても動いてるんですけど？

CAP 定理の本当の使いどころ

どうにもこの「RDBMS = CA 型」というのが気に食わなくて色々と調べてまわっていたら、しっくりくるエントリがありました。英語なんですが、難しくないので読んでみるといいと思います、僕ですら雰囲気は読めたんですから:)

This is why defining P as ‘allowing partitioned groups to remain available’ is misleading – machine failures are partitions, almost tautologously, and by definition cannot be available while they are failed.

CAP Confusion: Problems with ‘partition tolerance’ | Apache Hadoop for the Enterprise | Cloudera

このブログの要点は、そもそも分散データストアの設計が選ぶべきは「CA か CP か AP か」ではなくて「C か A か」だということです。ネットワーク分断というのは、クラスタがネットワーク障害によって分断されるという意味ではなくて、単にノード間で通信できなくなるような状況を指しているわけです。そしてそういう状況は別にネットワークの問題だけじゃなくて、ノード障害(例えばマスター障害とか)でも起こり得る。そういう場面で、C と A は両立できないというのが CAP 定理の示すところなんじゃないかなーと考えると色々と腑に落ちてきました。

この定義なら色んなデータストアを、ネットワーク分断時に Consistency を取っている(復旧まで利用不可能になってでも一貫性を維持する)＝ C 型か、Availability を取っている(極端な例ではスプレットブレインの様に一貫性が崩れてでも利用可能である状態を維持する)＝ A 型かで分類すれば良さそうです。

ただ、「ネットワーク分断」と一口に言っても、色んな種類があります。端的には、あるノード(ここでは SQL 等の問い合わせを受ける側)が、1. クライアント(ここでは App サーバ等 SQL などを投げる側)からも到達できないような状態 と、2. クライアントは到達できるがノード間通信(MySQL のレプリケーションなど)が分断している状態 の 2 種類が考えられます。

また、ノードにいくつかの役割がある場合(MySQL の master-slave や HBase の master-RS など)、どの役割のノードが障害になったのかでも挙動が異なると思います。

というわけで、上記分類を行っていくつかのの分散データストアシステムが C 型なのか A 型なのかを俯瞰してみましょう。

とは言ったものの、正直 MySQL と memcached 以外触ったことないので、資料ベースで調べた結果になります。これからそれぞれこの理解が正しいのかは時間見つけて検証するつもりではありますが、識者の方がいらっしゃれば間違い指摘してもらえると大変助かります＞＜

CAP 定理によるデータストアのまともな俯瞰

表をブログにべた書きしても良かったんですが、修正していくので履歴とか diff が見れたほうがいいと思って github にしてみました。なんとなく。

とりあえずリンク先で見てもらう感じでお願いします。

俯瞰してみて思ったこと

MySQL の master-slave&sharding 方式はキモイ。MySQL はトランザクションがあるから一貫性最強だとか言うけど、sharding 環境においては完全なトランザクションは(XA 使えばできるのかもしれないけど)ほぼ不可能なわけで、だから最近の分散データストアは強力なトランザクション(複数レコードのアトミックな更新やロールバックなど)はそもそも実装してない様に思われます。むしろ、分散データストアでの更新とはそういうもんだ(複数レコードではシーケンシャルな一貫性は無いもの)と思うことで設計・実装をしやすくしてる気がします。

あと、Availability を取るというのは相当キモイなぁと思いました。要はスプリットブレインを許容するということなのかなと思いますが、スプリットブレインは MySQL を運用してる自分としては絶対に起こしたくない状況だと思ってます。何故なら完全な復旧が相当に難しいから。スプリットブレインになるくらいならちょっとの間利用不可能であっても短時間で一貫性を持ったまま復旧させるというのが、まさに MHA が実現した所でもあります。なので、HBase の様に Consistency を取るというアーキテクチャの方が MySQL 厨にはとてもすんなり受け入れられます。Facebook が HBase を選んだというのも納得いきます。

一時的に繋がらない状況をエンドユーザに見せたくなければ、アプリケーションで工夫することもできるでしょう。書き込みはキューに入れてしばらくお待ち下さいと返したり、読み込みはキャッシュしておいた古いものを返すとか。

というわけで、ざっと調べてみて思った大事なこととしては、どういうデータストアを選ぶかという時に、「JSON がそのまま入れられるから使いやすい」みたいな視点だけでは Web の様に分散することが最初からわかっているシステムでは通用しなくて、アプリケーションの設計段階から、ネットワーク分断時に C を取るのか A を取るのか、捨てた方を復旧させるならどうやってやるのか、ということを統合的に考えてどういうデータストアを使うかを選ぶべきだと思いました。もちろんアプリケーションの設計をどうするかも強く相関しますので、みんなでちゃんと話合って決めることだと思います。

おわりに

そろそろ勉強始めないとなーということで手始めに有名な定理から勉強始めてみました。アカデミックな知識とかクソくらえ、現場の何が分かるとか正直思ってましたすいませんすいません。改めて色々と整理して理解することができた/これからもできそうなので大変助かりました。

とりあえずこの視点を元に、色んな分散データストアを個人的に検証してみようかと思っている次第ではありますが果たしてそんな時間が取れるのかは甚だ疑問であります。

長文失礼致しました。 ツッコミ歓迎いたします。

その他参考資料

Many Thanks :)