RDBMSのようでRDBMSではない新システム最近また超並列DBのデザインを進めたりRethinkDBの話を書いてみたりとまたRDBMSづいているが、そんなことをしているうちに世の中では実際に並列DBが登場してしまった。Stonebraker博士。最近何やっているのかと思ったらいつの間にやらH-Storeなる新型のストレージに携わっていて、それがいつの間にかSQL機能をもってVoltDBというプロダクトとしてやってきた。40年近く業界の第一線にいることになる。「NoSQL」を上回る性能を目指す次世代型高速SQLデータベース「VoltDB」登場などという記事を見てびっくりした次第だ。NoSQL並の性能とRDBMS並のACID準拠、そしてSQL構文が使えるという、これまた夢のようなシステムである。これがいわゆる狭義のRDBMSというか、我々が考えるOracleやMySQLのようなシステムを想像してとっかかると、全然違うものである。持ってH-Store自体、従来のRDBMSの持つ欠点というか、時代に即した設計に改めるためにかなりドラスティックな変革をしたシステムである。現物を見たことはなかったが、ここに来てVoltDBが出てきたことで拝めることになった。それについては論文を見るのが早い。SystemこいつはOLTPに特化したシステムで、最初の記事で圧倒的に早いと言われていたのはおそらく論文にも出てくるTPC-Cである。主記憶を主に使うオンメモリDBに近いタイプだろうと推測する。書き込みの高速化はsharding、そしてレプリケーションを使うのは前回のエントリでも言ったとおり常套手段である。ユニークなのはパーティショニングされているテーブルと、パーティショニングされていず、全部のサーバにレプリケートされている読み込み専用のテーブルの2種類があることだ。後者はマスタ等に利用する考えだろう。独特なのが利用モデルで、VoltDBではテーブル、その設定、そしてJavaとSQLで書かれたストアドプロシージャを「ビルド」して「アプリケーション」を作る。少なくとも現状では、データベースは静的なシステムであり、オンザフライでの頻繁な変更をあまり考慮していない。トランザクションモデルは驚くほど異なっている。もって全てのトランザクションはストアドプロシージャとして登録されなければならず、インタラクティブなものは事実上ありえない点が新しい。そのため、JDBCやODBCのような汎用インターフェースをサポートしない(できない)VoltDBのFAQにもその旨が書かれている。アドホックにSQLが書けないわけではない。一応ソースコードも軽く眺めてみた。軽くなので正確なことは分からないが、エンジン部分はC++でかかれており、ここにストレージ用のコードやExecutorのコードがある。フロントエンドはJavaで書かれていて、こっちにPlannerがあるのが興味深い。Joinなどの特殊なJOIN機構が無いのも興味深いが、これはOLTP用としては重要ではない判断だろうか。Java側には設定等のためかHSQLDBも入っている。これは実際、確かにSQLを受け付けるとはいえ、現実にはかなり異なったシステムだと言っていいだろう。スレッドモデルの考え方など、他にもずいぶん独特な部分がたくさんあるが、もう少しちゃんと読み込んでからそこは書いていきたい。いえるのは、今までのやり方は通用しないと言うことだ。それは悪いことに見えるかもしれないが、代償として得られる性能は圧倒的であることは強調しておきたい。SQL実装の扱いやすいが性能に差し障る部分が削られていることが、性能を印象的なものにしている。BigTableあたりから始まって、データストアの性能改善の動きが激しく、まだしばらくは続きそうだ。一段落したときにどんなシステムが勝ち残るか、いったいどれだけのことができるようになっているか、そしてユーザはどのようにその恩恵を受けられるのか?いろいろ興味深い種は尽きない。その中でL.starはどういう役割を果たすべきか?ちゃんと考えておかないとなぁ。L.star的デザイン(1)にてある程度の考察をしているRDBMSのデザイン。kumoFSどうだろうとか寄り道しつつ、自分なりの次のステージまで煮詰めることができたので、それについてメモとして書き留めたい。標準的なストレージしか持たないサーバ群を使う。単純CRUDクエリのスケールアウト。読み書き両方JOIN構文のサポート。JOINして集計できる1つのクエリ内部を複数サーバに分割させることによる性能向上。スケールアウトというわけではないが。無茶な要求と思うが、ここまでサポートできるとデザイン上で納得できれば悪くなかろう。現実に実装する場合には、随所で発生するボトルネックとの戦いになるだろうし。前回は「ストレージノード」と「クエリ実行ノード」の2種類に分けたが、今回はここをより深く切り分けて、実際どのように並列化可能か、というのを取り上げたい。読み込みI/Oをレプリケーションで、書き込みはパーティショニングで分散するRAIO1+0構成のストレージノードストレージノードは、RDBMSの従来のボトルネックであったディスクI/Oを司るところだから大切にしたいところである。ここをどうやって構成するか、というのは最近もはや定番構成ができつつある。書き込みI/Oを分割するためにShardingする。後にこれをレプリケーションすることによって可用性と読み込みの分散の両方をはかるやりかたである。以下に構成例を図で示す。これは詰まるところディスクで言うところのRAID1+0構成になる。逆の0+1(先に複製、あとでsharding)という構成とどっちがありかというのは難しいが、分割したものは全てそろっていないといけないこと、複製は全てそろっている必要はないことから、先に分割するのが順当に思われる。次に実際にここからデータを読み込んだ後、結合とかソートとか集約演算をする、クエリ実行ノードの話に移る。RDBMSにおけるクエリ実行プランには、実は2種類の分割が可能である。一つは各クエリオペレータは、基本的に上流から来たデータを下流に流す構造なので、これは垂直分割可能である。データを読むノードと、それを加工するノードは別にすることが可能である。クエリ実行ノードは、複数のクエリオペレータノードに分割可能である。理論上は分割可能だが、別ノードやプロセスに置くとプロセス間通信が発生する。これをできるだけ最小化するまた、ソートや集約については水平分割も可能である。ソートの場合マージソートにより分割可能である。マージソートは外部記憶を使うこともできるので分散の必要はないが、ネットワーク越しにすることでこの外部記憶用ディスクへのI/Oも負荷分散可能である。JOINに関しては、巨大なテーブル同士でまともな性能が出るのはマージジョイン以外あり得ず、そのため必要なのはソートなので、ここがあれば大丈夫である。以下に具体的に2テーブルのJOINをするときのフロー例を示す。この例では各テーブルが5つにshardingされているとし、おのおの前処理として集約とソートしつつ、最後にJOINして合計21ノードで処理をしている。ここでは「ノード」としたが、物理的に別ノードである必要はない。いうわけで、ここでは4種類の並列可能性を抽出してみた。接続ごとの並列実行これら全てを組み合わせたシステムが実は案外多くないことに注意する必要があるだろう。クエリベースのレプリケーションは上記のうち2と5だけしか使わない。Postgres-XCは1も備えるが、現状3を備えないためにノードをまたがったテーブルのJOINができない。世の多くのKVSは1,2,5についてはほぼ完璧である。3,4については無いに等しいか、SQLより簡素化したもの(例えばMapReduce)しか備えない。3,4に強いのは実はOLAP系のツールで、RDBMSより圧倒的に強い。これらを加味すると、1-5を全て備えるために必要なのは、KVSのような1,2に強いストレージモデルにしつつ、なおかつその上にOLAP系ツールに近いSQLインターフェースを配置する必要がある。exadataはこれに近いデザインになっているだろうというか、他に妥当なデザインが思い浮かばない。これ以上デザインを推し進めたとき、どれだけ彼らの特許に引っかかるかと思うと憂鬱になる。ここでのデザインはあくまで自分の訓練向けと思っているし、かなりのボリュームなのでたぶん全部を実装するのは一人では手に余る。それでも時間を見つけてインターフェース起こしたりより詳細な実装に踏み込んだり、という作業はやっている。クエリのフローの流れや、具体的なストレージノードの初期デザインも頭の中にはできているので、とにかくそういうのをメモ代わりにここに残しながら少しづつ完成に近づけていきたい。ないと、とても現状の最先端には追いつけない。前回にも書いたとおりRDBMSの重要な部分にACIDのサポートがあるが、このうちAID、つまり原子性(トランザクションのロールバック・コミットは不可分)、分離性(他のトランザクションの影響を受けない)、耐久性(一旦commitしたトランザクションは意地でも消えない)の3つをサポートするためには重要な、ログの話をしよう。この3つをサポートすると言うことは以下の3つの機能を持つことに等しいと言える。トランザクションを完全にロールバックするために、以前のバージョンに戻すことが出来ること。トランザクション実行中のデータが見えないように工夫できること。トランザクションのコミット時には、完全にデータが書き込みできるていること。「ディスク書き込み途中にクラッシュしても」というのを満たすのは結構難しい。そこで、実現のためには実行前と実行後のデータをログとして残しておく、と言うのが有効になる。Loggingと呼ばれ、強力なデータ保護を行うためのシステムでは不可欠な仕組みである。保管しているログは、クラッシュ時の復旧に、以下のように使われる。ログをトランザクションの始めから終わりまで読む全部そろっていて、そのトランザクションがコミットされていれば、ログの「実行後」のデータを書き込む全部そろっていないか、トランザクションがロールバックしていれば、ログの「実行前」のデータを書き込んで戻すログがトランザクションの耐久性を保証するため、ログは常に完全に書き込めていなければならない。ログが書き込めていることで、実際に全体の再構成が可能になる。一般にはディスクの同期書き込みを使う。ここでポイントになるのは「同期」というところで、いわゆるHDDの同期書き込みはすこぶる遅い。そのために、大量のデータを書き込むと遅くなると言うのはつねにRDBMSの泣き所である。いえ、常にあらゆるデータを同期書き込みするよりコストは低いため、WALを使うことは性能上有利である。ここまでは教科書に書いてある話であるが、ここからがL.star的解釈の始まりである。ポイントは、「実行前のデータ(UNDO用)」「実行後のデータ(REDO用)」を一体どこに保存するのか?というのが、その後のRDBMSの実装を理解するためのポイントだと思っている。教科書通りの実装では、REDO/UNDOともログファイル上にある。新しいデータは、常に古いデータを上書きする形で記述する。トランザクションの整合性を持つためにはただしくロックを取得して、書き込み中のデータや新しすぎるデータを読まない必要がある。データファイルには常に最新のデータのみが格納されるため、データファイル量が一定になり、大変扱いやすいものである。多数のロックが発生しうることは、マルチプロセッサ環境ではあまりよろしくない。PostgreSQLを初めとする追記型ストレージは、つねに実行前のバージョンを削除「しない」ため、そのままこれを実行前データ格納用のログとして使うことが出来る。MVCCと相性が非常に良く、ロックの削減に役立つ。持っているトランザクションログは、REDOログだけを記録する。シンプルでスペックも素晴らしい。旧バージョンの削除という大問題がある。ロールバックについては最も簡単である。ロールバックセグメント方式というのは追記型に工夫を加え、古いバージョンを全てロールバックセグメントに移動させる。ロールバックセグメントにはUNDO用のログが用意され、通常MVCCとからめて利用できる。検索可能なUNDOログである。ログは分けられているため旧バージョンの削除が容易であるが、旧バージョンと新バージョンの移動という、ロールバックセグメントの管理自体が面倒である。シャドウページングと呼ばれるアルゴリズムは、WALを使わずにデータ保護を行おうというものである。いや、むしろデータファイルが無くてログだけが存在すると考えた方が良い。常にデータは追記書き込みされ、commit時点で最新バージョンを参照するように変更される。内部的にはログなので、例えばバックアップを残すことも容易である。完全な追記でもないかぎりファイルにおける論理的な位置と物理的な位置が一切一致しない。スペック的にはいたれりつくせりのように見えるが、今の所まだまだ確立途中であり、ファイルシステムなどで上手に使われている一方でRDBMS内部でこのようなストレージは使われていないのでは無かろうか。最後にいくつかあったものを個人的な視点から項目にまとめて表にしてみた。「リベラルなのに護憲」?別におかしくなんてありません。「本当の日本のリベラル」こそまず改憲をめざせ帰国しました。