カテゴリ: DB

最近また超並列DBのデザインを進めたりRethinkDBの話を書いてみたりとまたRDBMSづいているが、そんなことをしているうちに世の中では実際に並列DBが登場してしまった。

INGRES,POSTGRES,Illustra(と、誰も知らないMariposa)と、RDBMSの世界で革新的な仕事をしているMichael Stonebraker博士。最近何やっているのかと思ったらいつの間にやらH-Storeなる新型のストレージに携わっていて、それがいつの間にかSQL機能をもってVoltDBというプロダクトとしてやってきた。かれこれ40年近く業界の第一線にいることになる。

「NoSQL」を上回る性能を目指す次世代型高速SQLデータベース「VoltDB」登場

などという記事を見てびっくりした次第だ。NoSQL並の性能とRDBMS並のACID準拠、そしてSQL構文が使えるという、これまた夢のようなシステムである。

しかし、これがいわゆる狭義のRDBMSというか、我々が考えるOracleやMySQLのようなシステムを想像してとっかかると、全然違うものである。全くとんでもない代物である。

まず持ってH-Store自体、従来のRDBMSの持つ欠点というか、時代に即した設計に改めるためにかなりドラスティックな変革をしたシステムである。当然現物を見たことはなかったが、ここに来てVoltDBが出てきたことで拝めることになった。

それについては論文を見るのが早い。

HStore:A HighPerformance, Distributed Main Memory Transaction Processing System

こいつはOLTPに特化したシステムで、最初の記事で圧倒的に早いと言われていたのはおそらく論文にも出てくるTPC-Cである。主記憶を主に使うオンメモリDBに近いタイプだろうと推測する。書き込みの高速化はsharding、そしてレプリケーションを使うのは前回のエントリでも言ったとおり常套手段である。

ユニークなのはパーティショニングされているテーブルと、パーティショニングされていず、全部のサーバにレプリケートされている読み込み専用のテーブルの2種類があることだ。後者はマスタ等に利用する考えだろう。

そして独特なのが利用モデルで、VoltDBではテーブル、その設定、そしてJavaとSQLで書かれたストアドプロシージャを「ビルド」して「アプリケーション」を作る。つまり少なくとも現状では、データベースは静的なシステムであり、オンザフライでの頻繁な変更をあまり考慮していない。少なくともALTER TABLEはない。

また、トランザクションモデルは驚くほど異なっている。まずもって全てのトランザクションはストアドプロシージャとして登録されなければならず、インタラクティブなものは事実上ありえない点が新しい。そのため、JDBCやODBCのような汎用インターフェースをサポートしない(できない)VoltDBのFAQにもその旨が書かれている。なお、アドホックにSQLが書けないわけではない。しかし非推奨だ。

一応ソースコードも軽く眺めてみた。軽くなので正確なことは分からないが、エンジン部分はC++でかかれており、ここにストレージ用のコードやExecutorのコードがある。またフロントエンドはJavaで書かれていて、こっちにPlannerがあるのが興味深い。またMerge Joinなどの特殊なJOIN機構が無いのも興味深いが、これはOLTP用としては重要ではない判断だろうか。Java側には設定等のためかHSQLDBも入っている。実に興味深い。

これは実際、確かにSQLを受け付けるとはいえ、現実にはかなり異なったシステムだと言っていいだろう。スレッドモデルの考え方など、他にもずいぶん独特な部分がたくさんあるが、もう少しちゃんと読み込んでからそこは書いていきたい。しかしいえるのは、今までのやり方は通用しないと言うことだ。それは悪いことに見えるかもしれないが、代償として得られる性能は圧倒的であることは強調しておきたい。SQL実装の扱いやすいが性能に差し障る部分が削られていることが、性能を印象的なものにしている。

BigTableあたりから始まって、データストアの性能改善の動きが激しく、まだしばらくは続きそうだ。一段落したときにどんなシステムが勝ち残るか、いったいどれだけのことができるようになっているか、そしてユーザはどのようにその恩恵を受けられるのか?いろいろ興味深い種は尽きない。その中でL.starはどういう役割を果たすべきか?ちゃんと考えておかないとなぁ。

前回、と言ってもずいぶん前になるが

超並列RDBMSは成立するか – L.star的デザイン(1)

にてある程度の考察をしているRDBMSのデザイン。kumoFSどうだろうとか寄り道しつつ、自分なりの次のステージまで煮詰めることができたので、それについてメモとして書き留めたい。

まず目標として掲げるのは、

  • 標準的なストレージしか持たないサーバ群を使う。
  • 単純CRUDクエリのスケールアウト。読み書き両方
  • JOIN構文のサポート。特に1TB程度の複数テーブルをINNER JOINして集計できる
  • 1つのクエリ内部を複数サーバに分割させることによる性能向上。スケールアウトというわけではないが。

というところである。かなり無茶な要求と思うが、ここまでサポートできるとデザイン上で納得できれば悪くなかろう。現実に実装する場合には、随所で発生するボトルネックとの戦いになるだろうし。前回は「ストレージノード」と「クエリ実行ノード」の2種類に分けたが、今回はここをより深く切り分けて、実際どのように並列化可能か、というのを取り上げたい。

読み込みI/Oをレプリケーションで、書き込みはパーティショニングで分散するRAIO1+0構成のストレージノード

ストレージノードは、RDBMSの従来のボトルネックであったディスクI/Oを司るところだから大切にしたいところである。しかし、ここをどうやって構成するか、というのは最近もはや定番構成ができつつある。まず書き込みI/Oを分割するためにShardingする。後にこれをレプリケーションすることによって可用性と読み込みの分散の両方をはかるやりかたである。以下に構成例を図で示す。

image

これは詰まるところディスクで言うところのRAID1+0構成になる。逆の0+1(先に複製、あとでsharding)という構成とどっちがありかというのは難しいが、分割したものは全てそろっていないといけないこと、複製は全てそろっている必要はないことから、先に分割するのが順当に思われる。

実行プランの垂直・水平分割

次に実際にここからデータを読み込んだ後、結合とかソートとか集約演算をする、クエリ実行ノードの話に移る。RDBMSにおけるクエリ実行プランには、実は2種類の分割が可能である。一つは各クエリオペレータは、基本的に上流から来たデータを下流に流す構造なので、これは垂直分割可能である。例えばデータを読むノードと、それを加工するノードは別にすることが可能である。つまりクエリ実行ノードは、複数のクエリオペレータノードに分割可能である。

ただし理論上は分割可能だが、別ノードやプロセスに置くとプロセス間通信が発生する。これをできるだけ最小化する

また、ソートや集約については水平分割も可能である。例えばソートの場合マージソートにより分割可能である。マージソートは外部記憶を使うこともできるので分散の必要はないが、ネットワーク越しにすることでこの外部記憶用ディスクへのI/Oも負荷分散可能である。JOINに関しては、巨大なテーブル同士でまともな性能が出るのはマージジョイン以外あり得ず、そのため必要なのはソートなので、ここがあれば大丈夫である。

以下に具体的に2テーブルのJOINをするときのフロー例を示す。この例では各テーブルが5つにshardingされているとし、おのおの前処理として集約とソートしつつ、最後にJOINして合計21ノードで処理をしている。ここでは「ノード」としたが、物理的に別ノードである必要はない。

image

というわけで、ここでは4種類の並列可能性を抽出してみた。これにごくごく当たり前のものを加えると

  1. Shardingによる読み書きI/Oの分散
  2. レプリケーションによる読みI/Oの分散および可用性向上
  3. 実行プランの垂直分割
  4. クエリオペレータの並列実行
  5. 接続ごとの並列実行

これら全てを組み合わせたシステムが実は案外多くないことに注意する必要があるだろう。クエリベースのレプリケーションは上記のうち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インターフェースを配置する必要がある。ただ、推測でしかないがSalesforceの内部、Azure向けSQL Server、そしてOracle exadataはこれに近いデザインになっているだろうというか、他に妥当なデザインが思い浮かばない。正直これ以上デザインを推し進めたとき、どれだけ彼らの特許に引っかかるかと思うと憂鬱になる。

まあここでのデザインはあくまで自分の訓練向けと思っているし、かなりのボリュームなのでたぶん全部を実装するのは一人では手に余る。まあそれでも時間を見つけてインターフェース起こしたりより詳細な実装に踏み込んだり、という作業はやっている。例えばクエリのフローの流れや、具体的なストレージノードの初期デザインも頭の中にはできているので、とにかくそういうのをメモ代わりにここに残しながら少しづつ完成に近づけていきたい。でないと、とても現状の最先端には追いつけない。

前回にも書いたとおりRDBMSの重要な部分にACIDのサポートがあるが、このうちAID、つまり原子性(トランザクションのロールバック・コミットは不可分)、分離性(他のトランザクションの影響を受けない)、耐久性(一旦commitしたトランザクションは意地でも消えない)の3つをサポートするためには重要な、ログの話をしよう。

まず、この3つをサポートすると言うことは以下の3つの機能を持つことに等しいと言える。

  1. トランザクションを完全にロールバックするために、以前のバージョンに戻すことが出来ること。

  2. トランザクション実行中のデータが見えないように工夫できること。

  3. トランザクションのコミット時には、完全にデータが書き込みできるていること。


ただし、「ディスク書き込み途中にクラッシュしても」というのを満たすのは結構難しい。そこで、実現のためには実行前と実行後のデータをログとして残しておく、と言うのが有効になる。この手法はWrite Ahead Loggingと呼ばれ、強力なデータ保護を行うためのシステムでは不可欠な仕組みである。保管しているログは、クラッシュ時の復旧に、以下のように使われる。

  • ログをトランザクションの始めから終わりまで読む

  • 全部そろっていて、そのトランザクションがコミットされていれば、ログの「実行後」のデータを書き込む

  • 全部そろっていないか、トランザクションがロールバックしていれば、ログの「実行前」のデータを書き込んで戻す


ログがトランザクションの耐久性を保証するため、ログは常に完全に書き込めていなければならない。しかし、ログが書き込めていることで、実際に全体の再構成が可能になる。一般にはディスクの同期書き込みを使う。

ここでポイントになるのは「同期」というところで、いわゆるHDDの同期書き込みはすこぶる遅い。そのために、大量のデータを書き込むと遅くなると言うのはつねにRDBMSの泣き所である。とはいえ、常にあらゆるデータを同期書き込みするよりコストは低いため、WALを使うことは性能上有利である。

まあここまでは教科書に書いてある話であるが、ここからがL.star的解釈の始まりである。ポイントは、「実行前のデータ(UNDO用)」「実行後のデータ(REDO用)」を一体どこに保存するのか?というのが、その後のRDBMSの実装を理解するためのポイントだと思っている。

  • 教科書通りの実装では、REDO/UNDOともログファイル上にある。新しいデータは、常に古いデータを上書きする形で記述する。トランザクションの整合性を持つためにはただしくロックを取得して、書き込み中のデータや新しすぎるデータを読まない必要がある。が、データファイルには常に最新のデータのみが格納されるため、データファイル量が一定になり、大変扱いやすいものである。しかし、多数のロックが発生しうることは、マルチプロセッサ環境ではあまりよろしくない。

  • PostgreSQLを初めとする追記型ストレージは、つねに実行前のバージョンを削除「しない」ため、そのままこれを実行前データ格納用のログとして使うことが出来る。また、MVCCと相性が非常に良く、ロックの削減に役立つ。持っているトランザクションログは、REDOログだけを記録する。
    きわめてシンプルでスペックも素晴らしい。しかし、旧バージョンの削除という大問題がある。 しかし、ロールバックについては最も簡単である。

  • ロールバックセグメント方式というのは追記型に工夫を加え、古いバージョンを全てロールバックセグメントに移動させる。ロールバックセグメントにはUNDO用のログが用意され、通常MVCCとからめて利用できる。つまり検索可能なUNDOログである。ログは分けられているため旧バージョンの削除が容易であるが、旧バージョンと新バージョンの移動という、ロールバックセグメントの管理自体が面倒である。

  • シャドウページングと呼ばれるアルゴリズムは、WALを使わずにデータ保護を行おうというものである。いや、むしろデータファイルが無くてログだけが存在すると考えた方が良い。常にデータは追記書き込みされ、commit時点で最新バージョンを参照するように変更される。内部的にはログなので、例えばバックアップを残すことも容易である。しかし、完全な追記でもないかぎりファイルにおける論理的な位置と物理的な位置が一切一致しない。
    スペック的にはいたれりつくせりのように見えるが、今の所まだまだ確立途中であり、ファイルシステムなどで上手に使われている一方でRDBMS内部でこのようなストレージは使われていないのでは無かろうか。


最後にいくつかあったものを個人的な視点から項目にまとめて表にしてみた。















































































項目 上書き型 追記型 ロールバックセグメント型 シャドウページング
UNDOログ ログ データファイル ロールバックセグメント データファイル
REDOログ ログ ログ ログ データファイル
読み<->書きロック競合処理 行ロック なし(MVCC) なし(MVCC) なし(MVCC)
書き-書き競合 行ロック 行ロック 行ロック 行ロック
コミット時処理 ほぼ無し ほぼ無し ほぼ無し ほぼ無し
ロールバック処理 UNDO ほぼ無し UNDO ほぼ無し
1KB上書き時
データ書き込み量
2KB同期
1KB非同期
1KB同期
1KB非同期
1KB同期
1KB同期?
1KB非同期
1KB同期
上記ロールバック時書き戻し量 1KB非同期 無し 1KB非同期 無し
上記上書き時データ増加量 0 1KBデータファイルに 1KBロールバックセグメントに 1KB
増加データ管理 必要なし データファイルのパージ ロールバックセグメントによる データファイルのパージ

↑このページのトップヘ