今更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 :)