NoSQL、CAP定理、BASE、Eventual Consistencyについて深く考えてみた

最近はNoSQLなどといって分散データベースがやたらに流行です。私もDynamoDBを使ってみようと思って色々調べているところですが、学べば学ぶほど奥が深くて恐ろしくなってきます。

まず第一に言っておきますが、現在のところ、いわゆるKey-value store型のNoSQLのメリットは「書き込みのスケーラビリティ」であって、それ以外には大きなメリットはありません。

DynamoDBの場合は「管理不要」「高信頼性」というおまけが付きますので、また話は少し別ですけどね。

他のオープンソース製品を自分のサーバーにインストールするのであれば、RDBMSほどこなれていないNoSQLを運用するのは大変な苦痛と危険が伴うでしょうね。前の記事にも書いたように分散システムを運用するというのは困難かつ苦痛を伴う仕事ですから。

ですから、すさまじい数のアクセスがあるようなシステムでなければ、NoSQLを選択する意味はないでしょう。

データベースに関しては、高いサーバーを買ってなんとかなるなら、高いサーバーを買ってPostgreSQLでも動かしているほうがトータルではずっと安くあがると思いますよ。Xeonを80コア積んだHP DL980にFusion-IOを突っ込んでも1500万円あればおつりが来る時代ですからね。


さて、ここから先はだいぶ込み入った技術の話をします。私も専門家ではなく、Amazon Dynamo[1]の論文を読んだ程度で話をしています。間違っているところがあればご容赦を。

最近喧伝されているBrewerのCAP定理[2]という理論がありますが、一貫性(Consistency)、可用性(Availability)、ネットワーク分断耐性(Partition tolerance)の3つのうち2つまでしか同時に得ることができないという話です。

このPartition toleranceを誤って「分散」と捉えて、「クラウドでは分散は必須なのだから一貫性か可用性のどちらかを犠牲にするしかない」と言っている人たちがいます[3][4]。これは大きな間違いです。分断耐性とは、ネットワークが分断した場合にも動作できるかどうかという話であり、現実にネットワーク分断など滅多に発生しない以上、一貫性も可用性も問題なく確保できます。

ネットワークが分断した場合でもアクセスできるという特性は、DNSやCDNや巨大P2Pネットワークなどには必要な特性かもしれませんが、通常のシステムには不要と言えます。また、これはキャッシュやデータ伝搬の仕組みを使えばアプリケーション側で実装できます。従って、この定理は分散データベースとは何の関係もありません。

BASEはここでACIDと対比されていますが、このBASEもどちらかといえば、データベースのスケーラビリティの話というよりはキャッシュなどアプリケーションよりの話に思います。

この古い学会発表をもとに現代のNoSQLを語るのは、はっきり言って無意味ですし、有害だと思いますね。


NoSQLがしばしばconsistencyを犠牲にするのは決してCAP定理のためではなく、スケーラビリティを確保するためであると考えて良いでしょう。

DynamoDBではconsistent readをサポートしていますが、その場合、(Dynamoと同じquorumによる実装なら)特定の条件下では無限のスケーラビリティが失われるはずです。

Dynamoは、ハッシュキーによってデータを格納するノードを変えていますが、このとき同じハッシュキーに読み書きが集中したとしても、consistencyを犠牲にすれば、ノード数に比例した性能を得ることができます。なぜなら、その場合は同じハッシュキーのデータを格納するNノードのうち1ノードだけに書いたり読んだりすれば良いからです。

また、読み書きのどちらか一方がヘビーな場合にはconsistentでもスケールすることができます。書き込みヘビーなら、書き込みは1ノードに行い、読み込みは全ノードに行えば、読み込みがスケールしない代わりにconsistentです。読み込みヘビーならその逆ですね。

それに対して、consistentに読み書きの双方を行う場合には、最低でもNノードの過半数にたいして書き込みと読み込みを行わねばならず、ノード数に比例したスケーラビリティが得られないことになります。

そこでeventual consistencyという話がでてくるのであり、CAP定理とは何の関係もない話なのです。ハッシュキーが十分に分散していればconsistentでもスケーラブルで可用性ある分散データベースが作れるはずです。


しかしこのように一つの値についてconsistencyが確保されたとしても、残念ながらACIDが実現されるわけではありません。なぜならCAP定理やDynamoDBの言うconsistencyというのは、ACIDのconsistencyとはレベルが違うからです。前者は、最後に完了した書き込みのデータが常に読み出されるというだけの話です。後者では、複数のレコードやテーブルやインデックスにまたがる一貫性が必要です。

(ここから先は適当な推測で書いてます)

ACIDを実装するためには、基本的には、トランザクションマネージャが全てのトランザクションを受け付けて、順番を管理して、順番が入れ子になった書き込みなどが起きないように管理する必要があります。これはスケーラビリティを大きく損なう事態です。ですので、NoSQLではACIDを実装することは本質的価値を損なってしまうのです。

一貫性のある書き込みができなければ、データベース全体として不整合な状態が生まれてしまうこともあります。インデックスを管理するためにもatomicな書き込みが不可欠です。

NoSQLでSQLがサポートされないのは、実装の複雑さもさることながら、整合性のあるクエリを行うためにはスケーラビリティが犠牲になることが理由の一つかもしれませんね。

(適当な推測おわり)

システムのうち、80%くらいの動作は不整合性を許容できるかもしれませんが、残りの20%ではどうしても整合性が必要です。そのときにはアプリケーション側で排他制御や整合性の管理を行う必要がでてきます。それではアプリケーションの開発効率を著しく下げてしまいます。

それが、NoSQLは特別にアクセスの多い場合だけ有効であり、普通のシステムで使うことはあり得ないという理由です。


ということで私はNoSQL全般には懐疑的なのですが、Amazon DynamoDBのように管理負担を軽減してくれるものであれば、もう少し広い利用価値があるような気がします。

実用になるプログラムを書こうとすると、どうしてもデータベースを扱う必要性がでてきますが、RDBMSを使うのは初心者や趣味プログラマ等には重荷であり、小さなプログラムを書くモチベーションを下げています。

DynamoDBを使うことで、もうちょい簡単にシステムが作れるようにならないかな、と思って少しアイデアを温めています。

NoSQL Distilledという新刊や、牛の本などの名著を読みながら、もっと勉強していこうと思います。

[1] Dynamo: Amazon’s Highly Available Key-value Store, Giuseppe DeCandia, et al.
[2] Towards Robust Distributed Systems, Eric A. Brewer
[3] Cloudの技術的特徴について --- ScalabilityとAvailability ---, 丸山不二夫 
[4] 結果整合性（Eventual Consistency）についての分かりやすいプレゼン資料 － Publickey