2016-02-10

分散データベースというのは、それ単体でもとても難しい、データベースと、分散システム双方の技術の粋を結集して実現されるアプリケーションだ。これをサービスといったり、ミドルウェアといったりする場合もあるが、今回は技術を応用してつくったものという意図でアプリケーションと位置づけることにする。まあ古くて新しい問題で、死屍累々の世界でありながら、それでいて金の鉱脈でもある世界だ。イカのようなトピックを概説していくことで、近年の流れをメモしておきたい。

Pre-cloud era: クラウド以前の時代
BigTable, DynamoとCAP定理
MegaStore
研究: Calvin
Jepsen: できたら☎してよ〜
Coordination free database
Spanner: 何でもできるよ！！
Kudu+Impala
Next?

クラウド以前の時代

System RとかいわゆるRDBMSがあって、いろんな分散データベースがあった（らしい）。分散といってもふたつの目的があって、ひとつは耐障害性。もうひとつはスケーラビリティなんだけど、前者は必須要件でもあるわけ（メディア故障でデータが消えたら意味ない）だし枯れた実装もいくつかでてきた（CAP定理の範囲内で）。後者はまあぶっちゃけそんなに必要なかったり、テーブル分割なりスケールアップなりでみんなしのいできた。

今でもそうかもしれないけど、データベースといえばACIDでトランザクションがないと意味がないという考えがあって、分散トランザクションの難しさもあって、そこまで研究は進んでいなかった。まあ皆さん知ってる歴史だと思う。

BigTableとDynamo

BigTable *1 の登場は、 MapReduceとGFSの登場ほどのインパクトはすぐにはなかったが、Dynamo *2 の登場とあわせてジワジワとみんなを驚かせることになる。この2つは、まあよく知られている通り、いわゆるデータの整合性保証が不要で、ダウンタイムやスケールアウトの方が重要なユースケースが存在することが分かって、世間にインパクトを与えた。それまで「トラザクションがなきゃDBMSとしては認められない」と鼻高々だったDBの研究コミュニティが驚きひれ伏したわけだ。

注意しておきたいのは、BigTableとDynamoが切り捨てた整合性はそれぞれ別のものであるということだ。前者の整合性は、いわゆる伝統的なACIDの定義の中での整合性で、複数レコードや複数テーブル間の制約に関する整合性だ。もちろんインデックスも含む。
後者の整合性はそれ以前の話で、CAP定理の定義 *3 の中での整合性である。こちらはAtomic Objectと定理中で定義されているもの（NoSQLだとひとつのキーと値のペアだったり、いわゆるタプルのことだったりする）についてで、要は複製どうしの整合性についての話だ。

データモデルについても両者は新しい。どちらもリレーショナルモデルではなく独自のデータモデルだ。前者はいわゆるカラム指向ストアに分類されるが、それは「カラムを無限に追加できる」という意味であって、垂直分割したから高速だとかそういう話は本質ではない。正規化なんてまあ夢のまた夢であるし、結合とかその手のリレーショナル演算はあまり現実的じゃない。Dynamoはまあ…その…シンプルですわね、よいねえという。

このあと市井に出てくる分散データベースのほぼ全ての要素技術は、このBigTableとDynamoが持っている機能、データモデル、性質の組み合わせで説明できる。

MegaStore (とDynamoDB）

HadoopとかHBaseなんかが出てきて数年経って「やっぱりトランザクションもSQLも使えないのつらいわー」というのが世間のおおまかな合意になってきたころに登場したのがMegaStore *4 と DynamoDB *5 だ。
MegaStoreは、複数Row間のアトミックな更新ができるようになっていた。DynamoDBは中で使われている技術の詳細が明らかになっていない。しかしながら、まったく根拠がない謎の伝聞によると、BigTableは1DC内くらいの規模でしかスケールアウトしないしMegaStoreは遅いと言われていたし、DynamoDBは「EBSを使っていないから速いんだ」と言われていたようだ。つまりものすごい新技術が使われているわけではなく実装と運用を頑張っていたのだろうと想像される。

その頃アカデミックでは…

もちろんアカデミックは一歩先行く世界なので泥臭いところには拘泥しないが、いわゆる新しいワークロードが出てきたことで、まあ分散したデータベースは当たり前になってきて、研究としてのインパクトは少なくなった。いろんな技術が提案されたけど、実世界のワークロードで試されたものは少なくて実用化されて残ったものはほとんどなかった。Calvin *6はその中のひとつで、トランザクションはやはり難しいことが分かる *7。

というか、20世紀の時点で研究だけがかなり先行していて、できることはやり尽くされていたと思う。たとえば2PCとPaxosが本質的には同じで、前者は後者の特殊ケースであることが示されていて *8 、アカデミックとしては耐える時代だったなと今になって思う。

分散システムの難しさ

分散データベースのトランザクションの難しさは（分散トランザクションではない）、分散システムの本質的な非同期性と故障の存在にあるけど、その正しさを検証する方法がない難しさも大きい。フォーマルな検証であればいくつか技術があるらしい。SPINとか、TLA+ *9とか。のだけど、これの問題は、フォーマルな記述と、実装の泥臭いところまで含めてギャップが出ることを防げないところにある。形式的な定義から実装を吐くようなコンパイラ的なものがあればよいとは思うけど、それはまだちゃんと実用化されていない。TLA+は発展版として IronFleet *10 が登場したらしいので要チェックやで。

21世紀になってからようやく現実的なツールがいくつか登場してきた。最初はJepsen *11 だ。これは主にデータベースのレプリケーションの正しさをテストするためのツールだ。 iptables を使ってネットワーク分断を人為的に起こしながらデータの正しさを検証していくことができる。実際に多くのデータベースがこれでテストされ、いくつかクリティカルなバグが見つかった。初期のJepsenが強かったのは主にCausalityのチェックで、Causal Consistencyや、CAS的な「書いたはずのデータが暗黙に上書きされて消えてないか」のチェックだった。いまのJepsenはさらに改良されていて、CAS的なAPIがないデータベースでもデータの変遷可能性を観測されたデータから組み合わせ計算して推測し、ありえない変遷を辿った場合にはレプリケーションが壊れていると断定することがでｄきる。

Coordination Avoidance

この「一回読んだデータを邪魔されることなく正しく更新する」がSerealizabilityの根本でもあるわけだが、邪魔とはまあつまり、他にデータを読んだり書いたりしたヤツがいたかどうかである。他にデータを書いたヤツがいたら、最初に読んだデータは間違っていたことになるわけで、もうトランザクションの正統性を保証できないからアボートするしかない。これをサボると、パフォーマンスが得られるかわりに、いわゆるRDBMSにおけるAnomalyが発生する。他の誰にもデータを変更させないようにするには、ロックを使う。で、この「邪魔が入るかどうか」を保証するためには、ロックなり、誰かが読んだ証拠なりの情報を正しく全ノードで共有する必要がある。これが協調動作（Coordination）というわけだ。

これは、これまでのふつうのRDBMSだと簡単だった。ロックがある。コンピュータの中にはクロックがあるし、ユニークで単調増加なIDを発行するためのアトミックなインクリメント命令はCPUがサポートしている。RDBMSはロックをどうやって作ったり設計するか、どうやってIDを使ってトランザクションを並べるかが歴史だったわけだが、分散システムの世界ではそもそもロックを作れないし、ユニークで単調増加なIDやタイムスタンプを作ることもできない（できなくはないが、非常に難しいしめんどくさい、レッドオーシャン）。その難しさは、分散システムの本質的な性質に由来する。非同期性と故障だ。もちろん前提とするモデル次第なんだけど、いわゆる典型的なデータセンターではこれは現実に起こってる *12ので、単純化するのは難しい。時計も信用できない *13 のでIDを生成することもできない。で、これが難しくて研究者たちはずっと成果が出せずにいた。

で、この難しいをやらなくてもいいんじゃね？といったのがPeter Bailisだ *14。実世界のワークロードを分析してみて、概念を整備して、なんとかなるんじゃねという主張である。この論文は実装の詳細があまり載っていないのでどこまで実用的かはちょっと微妙ではある。

Spanner

で、それを力技でやったのがSpannerである *15。SpannerはDC間のレプリケーションと、ある区切られた論理的な範囲（Dictionary）でのCoordinator選出にPaxosを使った。このDictionary間の整合性はTrueTimeと2PCで保証する。このTrueTimeがSpannerのすごいところで、なんとGPSと原子時計を使ってDC間で整合性のあるタイムスタンプを作ってしまった。これによって、複数DC間でもそこそこのレイテンシでトランザクションできて、なおかつとてもスケールアウトするデータベースも作ってしまったのである。ちなみに、その上で動作するF1 *16 というSQL処理系も作ってしまった。

インデックスすら作れなかった分散DBがついにここまで来たのである。

Kudu

とはいえTrueTimeとか、DC間高速ネットワークなんかを作ってしまえるのはGoogleだけだ。実装が公開されるわけもない。そこで…というわけではないが関係あるのがKuduだ *17。もともとHDFSとHBaseのユースケースの間を埋めるのが目的だが、なかではHybridTime *18 という技術が使われている... といっても、 0.7.0 時点ではこれを使ったトランザクションができるようになったわけではない。まだこれからやるっぽい。これがあれば、どうもトランザクション間の依存グラフをある時間幅の外で作れるらしいのだがその方法が私にはちょっと自明ではない。果たしてどうなることやら。ともかく、これが最初に登場した可能性ありそうな実装なわけで、他に挙げるものが今のところないわけだ。

ちなみにKuduもSQLの処理系は含まれていなくて、ImpalaというMPPエンジンを上に乗せて使うのが主なユースケースのようだ。