ブリュワーの CAP 定理
2009 年 1 月 11 日 Julian Browne 著
1976 年 6 月 4 日の金曜日、 メインホールから離れた小さな二階の部屋で、 セックス・ピストルズ は最初の演奏を終えた。 マンチェスター、フリートレードホール でのことだった。 その場に実際に観客として誰が居合せたかについては混乱がある。それは、 ちょうど 6 週間後あった別のコンサートのせいも少しはあるんだけれど、 何といっても、そのギグが西洋の音楽文化を永遠に変えてしまったと、されているからだ。 あまりに象徴的かつ衝撃的なその登場は、デイヴィッド・ノランに一冊の本を書かせた。 その書籍 "I Swear I Was There: The Gig That Changed the World" は、自分達がそこにいたのだという観客の主張を検証しているだけの本である。 なぜなら、6 月 4 日は一般にパンクロック発祥の日とされているからだ。 (少なくともイギリスでは。 公式には 1974 年前半にラモーンズがこのムーヴメントをおこした功績をもっている。 指摘をくれた Charlie Dellocona に感謝。)
これ以前 (実際には 1971 年ごろから) も、 パンクの原型となるようなバンドは、 ニューヨーク・ドールズや ヴェルヴェット・アンダーグラウンドなどいくつもあった。 けれどこれをワンセットにしたのがセックス・ピストルズだった。 音楽の伝説に革命がおこり、 バズコックスのドライブするギター、 ザ・スミスの悲しげな歌声、 ザ・フォールのエクレクティックなシンコペーション、 ジョイ・ディヴィジョンとシンプリー・レッドの沸き起こる威風といったものに 閃きをもたらしたのだ。(これが全てではないとおもう。)
2000 年 7 月 19 日の水曜日、ポップカルチャーではないものの、 四半世紀前の音楽業界にセックスピストルズが与えたのと同じくらいの衝撃が、 インターネット規模のビジネスに走った。 ACM の Principles of Distributed Computing (PODC) シンポジウムで、 エリック・ブリュワーが あの基調講演を行ったのだ。
彼らの作品で、セックス・ピストルズはまったく何事にも制約されることのない凶暴さを アートスクールの構造主義よりも重視し、 スリーコードと、語るべき言葉を持つ誰もがバンドを始められるのだと伝えた。 エリック・ブリュワーは、後にブリュワー予想として知られる考えの中で、 アプリケーションがウェブに移行するのに従い、 開発者は一貫性に気を揉むのはやめようと語った。 ウェブ上の新しい分散アプリケーションには高い可用性が求められており、 そこでデータの一貫性を保証するのはいずれにせよ無理な話だから、 三台のサーバ(three servers)と、ユーザ体験への審美眼を持つ誰もが インターネット規模のビジネスを始られるのだと伝えた。 ブリュワーの戒律には、(当時からあるものと後から現れたものを合わせると、) Amazon、 EBay、 Twitter のような会社が従っている。
二年後、MIT の セス・ギルバートと ナンシー・リンチがブリュワー予想の正しさを 形式的に証明し、 ブリュワーの定理が生まれた。
ブリュワーの定理とは、つまるところどんなものなのだろう？ なぜそれが 1976 年マンチェスターののパンク生誕に匹敵するのだろうか。
2000 年にあったブリュワーの講演は、 彼が UC バークレイ時代に研究していた理論面での成果と、 Inktomi 運営から得た洞察を元にしている。 ブリュワーやその他の研究者は、講演の数年前から 高いスケーラビリティを持つシステムでを作るためのトレードオフの判断について議論を重ねており、 (1997 年の "Cluster-Based Scalable Network Services" や 1999 年の "Harvest、yield、and scalable tolerant systems") プレゼンテーションの内容は特段新しいものではなかった。 また多くの研究がそうであるように、こうした成果も他の多くの賢人たちの肩に乗っている。 (ブリュワーもきっとそう言うと思う。)
彼の主張によると、ある三つのシステム要件が存在し、 その三つの要件は分散環境にアプリケーションを置こうとすると特別な関係を持つ。 (彼はウェブに焦点を置いて話をしたけれど、 複数の事業所や国をまたぐ今日の企業ビジネスにも同じことが言える。 そこにはデータセンターや LAN, WAN があるからだ。)
三つの要件とは 一貫性(Consistency)、可用性(Availability)、 分割耐性(Partition Tolerance) のことで、 ブリュワーの定理の別名 ... CAP ... はここから来ている。
要件を日常的な意味でとらえるために、簡単な例を使ってみよう: あなたは明日から始まる長い長い休暇で、 トルストイの 戦争と平和を一冊読もうとしている。 お気に入りのウェブ書店には一冊だけ在庫があった。 出発前に届くかをちょっと調べて確認し、あなたはそれをカートに入れる。 他にもいくつか入用なものがあるのを思いだしたあなたは、サイトをちょっとぶらつく。 (オンラインで一つだけものを買う人がいるだろうか？荷物の箱は一杯にしないとね。) あなたが日焼け止めローションのカスタマーレビューを読んでいる間に、 誰か、この国のどこかにいる誰かがサイトにやってきて、例の一冊をカートに入れて、 さっさと支払いを進めてしまった。 (その人は足の長さが揃わずガタつくテーブルを直そうと急いでいたのだ。)
一貫性のあるサービスでは、操作は完了するか、一切何もしないかの、どちらかだ。 ギルバートとリンチは、一貫性ではなく原子性(atomic)という語を証明の中で使っている。 理論的な文脈では原子性という方が要領を得ている。 というのも細かい話をすると、一貫性(Consistent) は データベーストランザクションの望ましい性質をあらわす ACID の C に使われており、 これはあるデータが事前に与えられた制約を破った状態で残らないことを意味している。 ところが CAP の C を分散システムでの事前の制約とみなし、 同じデータをあらわす複数の値を許さないことにすると、抽象化が漏れて紛らわしいことになる。 (それに、もしブリュワーが原子性(atomic)という語を使っていたら AAP 定理になる。 こんなのを発音しようとしたら皆が病人みたいになってしまう。)
本を買う例でいうなら、本はカートに入れられるか、入れるのに失敗するかでなければいけない。 あるいは買うか、買わないかだ。 半分だけカートに入れたり、半分だけ買ったりすることはできない。 本が一冊なら買って翌日に受けとるのは一人だけ。 もし二人の客が注文プロセスの最後に辿りつける(支払いができる)なら、 在庫とシステムの一貫性が問題になる。この例では大した問題にはならないかもしれない... 誰かが退屈な余暇を過ごす羽目になったり、スープを皿からこぼすだけだ..。が、 規模が大きくなり幾千もの不一致がおこると金銭的な意味を持ってくる。 (たとえば金融の取り引きで、売買の記録が意図したとおりにならないなど。) これは大問題だ。
データベースを活用すれば一貫性の問題は解決できるだろう。 本を注文した、そのしかるべき時に戦争と平和の在庫数が一つ減じられ、 他の顧客が買おうとしたときに棚が空なら注文プロセスは警告をだし、注文できない旨を知らせる。 つまり、最初の操作は完了し、次の操作は何もしない。
こうした用途にデータベースはとても役立つ。データベースは ACID 特性に注力しており、 一貫性(Consistency)、そして分離 (Isolation) を実現してくれる。 おかげで顧客 1 は本の在庫を一冊減らし、同時にカートの本を一冊増やせる。途中の状態は顧客 2 から分離されている。 顧客 2 はデータストアに一貫性が戻るまで数百ミリ秒待つ。
可用性は字句通りの意味だ。サービスは用を足せなければいけない。 (上で示したように操作を完了するか、何もしないかというような。) 本を買ったら反応が欲しいだろう。 ウェブサイトが落ちてますというブラウザのメッセージは見たくない。 ギルバートとリンチは CAP 定理の証明の中で良い指摘をしている。 可用性はどうしても必要な時に限って損なわれる... つまりサイトは混雑している時ほど落ちる。なぜなら混雑しているからだと。 動いているけれどアクセスされないサービスは、誰にも有り難くない。
アリケーションとデータベースが同じマシンで動いているなら、 (スケールの問題を無視し、コードが正しいとすると) そのサーバの処理は原子性を持つように振る舞う。 つまり使えるか使えないかのどちらかになっている。 (クラッシュしていたら使えない。ただしクラッシュしてもデータの整合性は損なわない。)
データやロジックを異なるノードに振り分けだすと、分割がおこる危険がうまれる。 分割はたとえば、ネットワークのケーブルが切られ、 ノード A とノード B で通信ができなくなると起こる。 ウェブのもたらしたような分散機能を使っていると、一時的な分割は比較的よく起こる。 そして既に述べたように、 グローバル企業なら社内で複数のデータセンタをまたぐことも珍しくない。
セスとリンチは分割耐性を以下のように定義している:
全面的なネットワーク故障を除く故障が間違った結果を起こしてはならない。
そしてブリュワーのコメントを持ち出してこう言う。 単一ノードの分割はサーバのクラッシュに等しい。何もそのノードに繋がっていないなら、 それは無いも同然である。
アプリケーションをスケールすると CAP 定理が意味を持ちはじめる。 トランザクションの量が少ないうちは、 データベースが一貫性を保つための小さな遅延が 全体の性能やユーザ体験を目に見えて損ねることはない。 そうした場面で行う負荷分散は、システム管理の事情によるものだろう。
しかしシステムでの活動が増えるにつれ、こうしたスループットの際どい部分が 性能改善を妨げエラーを引き起こすようになる。 ウェブページからのレスポンスが返るまで待たなければいけなかったり、 クレジットカートの詳細を入力したら "HTTP 500 java.lang.schrodinger.purchasingerror" とレスポンスされ、変なものを買っていないか、何も買えなかったのか、 エラーはトランザクションと関係がないのか、などと悩む羽目になる。どうしたものか。 ユーザは買い物を続けないだろうし、他の店に流れるだろう。銀行に電話もすると思う。
いずれにせよこれはビジネスにとって良い話ではない。 Amazon はレスポンス時間が 1/10 秒余計にかかると 1% の売り上げを逃すと主張している。 Google は 1/2 秒の遅延増加がトラフィックを 1/5 も下げるという。
スケーラビリティについては以前少し書いたから、それを全て繰り返すことはしない。 二点だけ: 一点目は、スケールの問題に対処するのはアーキテクチャ上の関心事かもしれないが、 最初の議論はアーキテクチャ上のものではないということ。それはビジネス上の意思決定だ。 現在のシステム利用量を考えるとあれやこれやのアプローチは報われないという話を 技術者から聞くのは飽き飽きする。 彼らは正しいというわけではないけれど、間違っているというのでもない。 ただ、最初からスケールを制限するのは暗に収益上の判断をしている。 これはビジネス上の分析をする時点ではっきりさせておくべきことだ。
二点目は、アプリケーションをスケールさせる良い方法を議論しだすと、 世間は大きく二つの派閥、データベース派と非データベース派にわかれるということ。
データベース派は、当然データベースの技術を好む スケールの問題も楽観的ロックや シャード化(sharding)といった切り口で考え、 データベースが思考の中心にある。
非データベース派はできるだけデータをデータベース環境の外に置いて (リレーショナルな世界を避けて) スケールの問題に対処しようとする。
公平を期すために言っておくと、 前者の派閥は後者の派閥と同じように CAP 定理を受けとめてはいない。 (CAP 定理に言及することはあるにせよ。.) これは無理もない。もし一貫性、可用性、分割耐性のどれか一つを諦めるとしたら、 多くの人は一貫性を諦めるだろう。ところがこれは データベースの存在意義なのだ。 一貫性を諦める理屈は、おそらくこんなところだ: 可用性と分割耐性は収益源たるアプリケーションを生かすために必要だけど、 一貫性の破れはうまい設計で乗り切れそうな感じがする。
他の多くの情報技術がそうであるように、これは黒白はっきりできる問題ではない。 エリック・ブリュワーは、PODC 講演のスライドの 13 枚目で ACID と、 定式化はされていない ACID の片割れ BASE を比べながらこう言った: "これは連続しているのです" 。 もしこの話題に興味がある人は(今日の本題と少しずれるけれど), Haifeng Yu と Amin Vahdat による次の論文 "Design and Evaluation of a Continuous Consistency Model for Replicated Services" から読み始めると良いだろう。 CAP を、データベースは死んだ、と解釈していはいけない。
スケールに対する答えとして両陣営が合意しているのは分散並列であり、 かつて考えられていたようなスーパーコンピュータではない。 90 年代中盤、Netwok of Workstationsプロジェクトに エリック・ブリュワーが及ぼした影響は、 CAP 定理剥き出しのアーキテクチャに帰着した。 彼は Inktomi とインターネット・バブルと題した別の講演で、 いつだって答えは処理の並列化だと述べている:
処理を並列化しなかったら、問題を妥当な時間で解くことはどうしたってできない。 何だってそうだ。大きな仕事があって、その仕事のために沢山の人がいるような。 たとえば橋を作るのに沢山の建築業者がいるなら、それも並列処理だ。 だから問題の多くは結局「どうやって並列処理をインターネットと組合せるか」なのだ。
これから単純化した証明を図解してみたい。私は図解した方がずっと理解がしやすかった。 論文に沿って話したいから、ギルバートとリンチの論文に出てくる用語をそのまま使う。
上の図はネットワーク上にある二つのノード N1 と N2 を表している。 これら二つは共有のデータの値 V0 を共有している。 N1 上で動いているアルゴリズム A は安全でバグがなく、予測可能で堅牢だとする。 N2 では同様のアルゴリズム B が動いている。 この証明では、A が新い値 V を書き、B は V の値を読む。
問題のない快晴のシナリオは以下のようになる: (1) まず A が新しい値 V (ここでは V1 と呼ぶ)を書く (2) メッセージ (M) を N1 から N2 に送る。このメッセージは N2 にある V のコピーを更新する。 (3) これで B が V を読み込むと V1 を返すようになる。
もしネットワークが分割されると(そして N1 から N2 へのメッセージが届かなくなると) N は (3) の時点で一貫性のない V の値を返すことになる。
これはまったく当たり前に思えるだろう。 これが数百のトランザクションにスケールアップすると大きな問題になる M が非同期メッセージだとしたら、 N1 は N2 がメッセージを受け取ったか否かを知ることができない。 M が届くと保証されていても、 N1 は分割や N2 の故障などの出来事で遅延がおきたかどうかを 知ることはできない。M を同期で送っても事態は良くならない。 それは N1 の A の書き込みと N1 から N2 の更新イベントをアトミックな操作にするというだけで、 先の遅延の問題は相変わらず残る(かもっと悪くなる)。 またギルバートとリンチはこれに少しバリエーションを加え、 各ノードが順序つきクロックを持つ半同期モデル(partially-synchronous model)であっても 原子性は保証されないことを証明している。
つまり CAP 定理が言わんとしているのはこういうことだ。 もし A と B に高可用性を与えたいなら(遅延を最小にしたいなら)、 かつ N1 から Nn (n は数百数千かもしれない) までにネットワーク分割耐性 (メッセージの紛失、信頼性のないメッセージ、ハートドウェア停電、プロセスの故障への耐性) 与えたいなら、 あるノードが V の値を V0 だと思っているときに、 別のノードが V の値を V1 だと思う場面があるかもしれない。 (戦争と平和は品切れかもしれない。)
私達は、70年代初頭のプログレッシブ・ロックのような、 全てが構造化され、一貫し、調和のとれた状態を本当に好ましいと思っている。 しかし私達が直面しているのは、いくらかパンクっぽいアナーキーだ。 それにほんとのところ、パンクは婆さまを怖がらせるかもしれないけれど、 一度それを知ってしまえばオーケーになる。どちらも一緒にとてもうまく動く。
トランザクションの立場からもざっと考えてみよう。
あるトランザクション a を実行しようとするとき (ひとまとまりの作業を永続的なデータ要素 V に対して行うとき)、 a1 はを書き込み操作、その後に行なわれる a2 を読み込み操作としよう。 ローカルのシステムなら、これはデータベースとちょっとしたロックで簡単に実現できる。 a2 でおこる読み込み操作は、 a1 が無事完了するまで隔離(isolate)しておくことができる。 しかし N1 と N2 が登場する分散モデルでは、中間の同期メッセージもちゃんと終わることを 心配しなければいけない。自分で a2 のおこるタイミングを制御しない限り、 それが a1 から書いたのと同じ値を読むことは保証できない。 制御のための全ての方法(ブロッキング、隔離、集権型管理 など) は a1(A) や a2(B) の分割耐性か可用性に影響してしまう。
CAP が提起する問題を扱ういくつかの選択肢がある。 次のいくつかは明らかなものだ:
分割を起こさずに運用をしたいなら、それを止める必要がある。 そのために、(トランザクションに関係する)全てを一つのマシン、 またはアトミックな故障の単位(ラックなど)に入れるのも手だ。 部分的な故障も起こりうるから、これでも 100% は保証できない。 しかし分割のような副作用は起こりにくくなるだろう。 もちろん、スケーリングには深刻な制限がある。
分解耐性諦め路線がコインの表なら、これはコインの裏になる。 分割が発生したら、影響をうけるサービスはデータの一貫性がもどるまで待つ。 結果としてその間はサービスを利用できなくなる。 複数ノードをまたいてこの制御をするのはとても複雑だ。 再復帰するノードには行儀よくオンラインに戻るロジックがいる。
あるいは、ワーナー・ヴォーゲルスが提案するように、 物事が "結果整合性" を持つのを受けいれてもいい。 ヴォーゲルスの記事は良く書けており、一読に値する。 この記事は、私がここで書くより詳しく運用固有の問題に踏み込んでいる。
一貫性の乱れの大半は、考えているより大した手間なく扱うことができる。 (つまり何だかんだで継続的な一貫性は必要ないかもしれない。) 本を注文する先の例でいうと、もし二つの注文を受けとったら、 二番目の注文は入荷待ちになるだけだ。 顧客がそう知らされるなら(しょっちゅう起こるわけではないのだから) 皆はそこそこハッピーだろう。
結果整合性の考えは BASE (Basically Available, Soft-state, Eventually consistent) という名で 援護射撃されている。若干ぎこちない略語だが、便利ではある。 EBay のダン・プリチェットによる説明がうまい。
atomikos の CTO ガイ・パードンは "A CAP Solution - Proving Brewer Wrong" という記事で、 一貫性、可用性、分割耐性をもつアーキテクチャの取り組みを提案している。 ただし、若干気を使うところは残る。 (三つの特性を同じ瞬間に満たすことはできないのには特に注意。)
この分野で正反対の見方をするガイの雄弁な語りは一読に値する。
一貫性、可用性、分割耐性のうち二つだけしか保証できないのは事実であり、 それは地球上で成功しているウェブサイトの大半が証明している。 もし彼らがそれで上手くやっているなら、 同じトレードオフを企業システムの日々の設計で考慮しない理由はない。 もしビジネスをスケールしないことがはっきりしているなら、単純で良い方法が使える。 しかし議論をしてみる価値はある。
今日の Amazon や EBay がスケーラビリティの問題を持っていないとはとても思えない。 彼らは問題を抱えており、今はそれを扱う道具を持っているのだとおもう。だから自由にその話ができる。 彼らがいま(現状のサイズを踏まえた上で)行っているスケーリングは、 どれも同じとは言えないものだろう。一度スケールしたなら、 問題は運用保守、監視、更新したソフトウェアの公開、などに移っていく。 手強い問題だが、流れこむ収益の川を抱えるならきっと持っていて損はない。
計算機科学からの更にいくつかのスライド。ヴァージニアのジョジ・メイソン大学による、 分散ソフトウェアシステムと特に CAP 定理、ACID と BASE のイデオギー的衝突について
