クラウド上のリレーショナルデータベースはなぜ難しいのか？ BASEとCAP定理について

2009年3月16日

今週18日からマイクロソフトがラスベガスで「MIX09」を開催します。Windows 7やWindows Azureが発表された昨年秋のPDC（Professional Developers Conference）とは異なり、MIXはWebデザイナーとWebデベロッパー向けのイベントです。

ところで、デザイナーとデベロッパー向けのイベントといえばアドビシステムズのイベントが有名。その名称はたしか「MAX」ですよね......。

さて。MIX09ではWindows Azureの料金体系の発表があるかもしれないといわれています。もし発表されれば、IT系メディアのヘッドラインを飾ることでしょう。

僕が注目しているのは、先日「マイクロソフトがクラウドでリーダーシップを握る可能性が高まる」で書いた、SQL Server完全互換の「SQL Data Services」（SDS）についての具体的な内容の発表です。

ところで、なぜクラウド上でリレーショナルデータベースの実装は難しいのでしょう？ネット上で調べていたらとても興味深い資料を見つけたので、自分のメモとしての意味も込めて今日はそれを紹介します。

その資料とは、UC Berkleyの教授でinktomi社のチーフサイエンティストでもあったEric Brewer氏の資料「Towards Robust Distributed Systems（PDF）」です。

かいつまんで見てみましょう。

リレーショナルデータベースは、「ACID」と呼ばれる特性を備えています。ACIDとはトランザクションに対する以下の4要件の頭文字を指します。

A：Atomic（原子性）
C：Consistency（一貫性）
I：Isolation（独立性）
D：Durability（永続性）

ところが、分散システムでACIDのCとIを実現しようとすると、それと引き替えに可用性や品質、性能が損なわれるというのです。

Eric Brewer氏はACIDと対照的に、可用性や性能を重視した特性を持つ分散システムの特性を「BASE」という頭文字で表しました。これは、以下の頭文字です（カッコ内は意訳です）。

BA：Basically Available（可用性が基本）
S：Soft-state（厳密でない状態遷移）
E：Eventual Consistency（結果として整合性がとれる）

ACIDとBASEの特徴の比較

そしてEric Brewer氏は分散システムにおける「CAP定理」を提唱しました。CAP定理とは、分散システムにおいて次の3つの要素のうち2つしか同時に満たすことはできない、という定理です。

C：Consistency（一貫性）
A：Availability（可用性）
P：Tolerance to network Paritions（ネットワーク分断への耐性）

CAP定理。一貫性、可用性、ネットワークの分断への耐性のうち同時に2つしか満たすことはできない

このBASEとCAP定理について、山本陽平氏のブログyohei-y:weblog: CAP と BASE について調べたことで、歴史的な経緯が非常に詳しく解説されています。多くの論文へのリンクもあるので、興味がある方はぜひリンクをたどってみることをおすすめします（山本氏はRESTの第一人者でもありますね）。僕もこの記事で今回の資料を知りました。

また、日本語訳されている論文EventuallyConsistent - 結果整合性もあります。

Eric Brewer氏の資料では、P（ネットワーク分断への耐性）を犠牲にしたシステムの例としてクラスタ上のデータベースを、A（可用性）を犠牲にしたシステムの例として分散データベースを、C（一貫性）を犠牲にしたシステムの例としてDNSを挙げています。

追記（2009/3/26）：下記の部分は正確ではなかったので取り消します。リレーショナルデータベースのデータ整合性と、CAPのデータ一貫性は異なる概念でした（参照：yohei-y:weblog: CAPのCとACIDのC）。

さて、CAP定理が正しい場合（正しいと証明されているそうなのですが）、可用性とネットワーク分断への耐性（クラウド内の）が重要視されているクラウドでは、データの一貫性を重視するリレーショナルデータベースを実装しようとすると、クラウドの特徴である可用性などが犠牲になってしまいます。

~~これがクラウド上でクラウドの特性を生かしながらリレーショナルデータベースを実装することの難しさを表しているわけです。~~

逆に、クラウド上の特性を生かしたキー・バリュー型のデータベースは、たしかに一貫性は重視していません。例えばグーグルの検索順位の変更が行われるとき、変更された情報はゆっくりとグーグルの巨大なデータベースの中を伝播していくことが知られています。完全に伝播し終わるまでデータベースの中でのデータの一貫性は崩れていますが、検索エンジンというアプリケーションにおいて、この一貫性はそれほど大事なことではありません。

もちろん、こうしたCAP間のトレードオフは工夫である程度補うことができます。例えばネットワーク分断への耐性を犠牲にするなら、ネットワークを冗長化することでシステムトータルでの耐性を高められるでしょう。こうした工夫が、クラウドごとの特徴、クラウド上のアプリケーションの特徴を形作ることになるのだと思います。

マイクロソフトはいろんな工夫をしてSQL ServerをWindows Azureのうえに実装してくると思います。クラウドにフルスペックの商用リレーショナルデータベースを実装する最初の試みですので、オラクルもIBMもきっと注目しているでしょう。僕も彼らのチャレンジを楽しみに待っていたいと思います。