2010年05月

ちょっと小旅行に出ている間にアクセスが伸びていて、おかげさまで前回のVoltDBのエントリが大人気だったようだ。まだまだ書き足りない部分がいっぱいあったので、補足する意味も込めて書き足してみたい。それは、H-Storeが従来型RDBMSとどれほど異なったシステムか、ということだ。インターフェースの話や大まかな話はしたが、前提となる部分の話はずいぶん抜けてしまっていた。

NoSQLを超えるSQLデータベース「VoltDB」。Cassnadraとベンチマーク対決!

で、実際にCassandraと比べて検討している

Key-Value Benchmarking

という記事が紹介されていて興味深い。で、なおかつ勝っていると言うから痛快だ。まあ個人的にはこの勝負は高々3ノードしか使っていない時点でスケーラビリティに勝るKVSにずいぶん不利な内容だな、と言わざるを得ない。せいぜい12ノードぐらいでしかテストされていないというVoltDBだから、30ノードならずっと違う結果が出るだろう。しかし、それでも勝ちは勝ちである。そもそも、ある程度のSQLを解するRDBMSなら、あげられた条件ではCassandraに肉薄すらできない。

何故ここまで勝てるのか?と言う話だが、逆に何故今までのDBは遅いのか、と言う話はすでに以下の論文にまとめられている。

http://cs-www.cs.yale.edu/homes/dna/papers/vldb07hstore.pdf

ここでいにしえのSystem Rの以下のような部分に対して批判がされている。

  • ディスク上に配置されることに最適化されたデータ構造
  • (ディスクI/Oの)レイテンシの遅さを補うためのマルチスレッディング
  • 同時実効性制御にロックを使うこと
  • トランザクションログによるリカバリ

ではこれに対するVoltDBというかH-Storeの回答は何だろう?こうだ

  • 最初からオンメモリを前提としたデータ構造
  • ロックフリー化。(ストレージ部分のシングルスレッド実行)
  • ロックを一切用いない追記とシングルスレッドによる同時実行制御
  • UNDOログは追記で不要。REDOは関してはレプリケーションで代用(これは論文に書かれていないが、FAQからそう読める)

このうちいくつか、MVCCやロックフリー化(に近い削減)は、RDBMSの世界ですら珍しくないものだ。逆に無いものから考えると、引き算で答えが出る。

となると答えは簡単だ。オンメモリベースのDBでログを持たないから。

実験したことのある人は多いと思うが、普通のRDBMS,PostgreSQLやMySQLのデータをRAMDISK上においても、極端な性能向上は見られない。少なくとも昔はそうだった。それはロックが多すぎてボトルネックになってしまうからだ。

メモリDBというのは単なるRAMディスクにデータを全部おいたRDBMSではない。いわゆるRDBMSのアルゴリズムは全てディスクベースで構成されている。それはつまり、あらゆるデータはディスクから読み書きされることを前提としていて、メモリはキャッシュとしてしか利用しないと言うことだ。

キャッシュにしか使っていないから、データ構造は全てディスク上に配置されることに最適化されている。B-Treeなどその最たるものだ。オンメモリで良いなら赤黒木なりなんなりもっと楽なアルゴリズムがあるし、メモリポインタをそのまま使うことで一気に単純化可能で、いろんなボトルネックが解消できる。ロックも簡単である。

そして、RethinkDBのエントリでも書いたが、ログをまじめに書かなくていい前提ならディスクI/Oは最小である。となるとWALによるデータ保証をしているCassandraとでは圧倒的な差が出て当然である。

ちなみに、PostgreSQLのコアメンバでEnterpriseDBにいるDave Pageが

Comparing VoltDB to Postgres

でこのVoltDBについて、要を得た比較しているので参考になるだろう。Daveはいくつかの点で、VoltDBがPostgreSQLの代替として使えない、ということを指摘している。コメントで「それはアーキテクチャの問題ではなく機能不足」とされていた部分を除くと

  • 限られた同時実行制御モデル
  • 従来インターフェースとの互換性
  • オンメモリDBであることによって、メモリ不足が深刻な問題になること。

と言ったことがあげられる。ただし、実はVoltDBにおいてはそんなことは設計の時点で折り込み済みである。先の論文で、なんのためにこんなシステムを実装しようとしたかの結論部分を引用しよう。


1. The predicted demise of “one size fits all”
2. The inappropriateness of current relational implementations for any segment of the market
3. The necessity of rethinking both data models and query languages for the specialized engines, which we expect to be dominant in the various vertical markets

そう、もう「1つのエンジンがあらゆるところに使い回される時代は終わった」と言っているのである。RDBMSはその点テクノロジー的な優等生を目指している。いやむしろRDBMSが標準に近いのではなく、標準がRDBMSを元に作られたとまで言ったほうがいいかもしれない。

車にたとえると、VoltDBはTPC-Cのようなトランザクション処理に特化したレースカーである。CassandraのようなKVSも、同様に又違う種類のトランザクションに特化したレースカーである。その点素のRDBMSはどこまで行ってもセダンだ。

だからVoltDBの数字に踊らされる前に、自分たちの使っているトランザクション特性をしかと考えてみてほしい。あなたのシステムが、メモリに収まらないほどのデータを扱わず、OLAP系の複雑なクエリなど知ったことではなく、でもOLTP性能がほしくて、RDBMS並に完璧なデータ完全性が必要ないならこいつは素晴らしいシステムだ。しかしどれかに当てはまらないならゴミだ。それだけのことである。

最近また超並列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はこれに近いデザインになっているだろうというか、他に妥当なデザインが思い浮かばない。正直これ以上デザインを推し進めたとき、どれだけ彼らの特許に引っかかるかと思うと憂鬱になる。

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

今日も突然TwitterでRDBMSとNoSQL周りの会話に若干巻き込まれたわけだけど、実際にどっちが勝つのかの帰結を予測するのは非常に難しい。

NoSQLのスケーラビリティと可用性は大変素晴らしいし、オブジェクト指向言語との相性もO/Rマッピングに比べれば抜群によい。しかし一方で、SQLと言う言語とその実装には癖があるとはいえ、RDBMSで実現できる柔軟性は捨てがたいし、ACIDが保証されているし、既存資産が流用できることも大きい。ポイントはそのACIDがどれだけ重要であるかということと、性能面だろうと思っている。つまりNoSQLでないとコストメリットが出ないほど大規模であればNoSQL優勢、そうでない部分はRDBMSで、ということだ。あまりに普通で失望した、と言われそうだが。

まあそれはおいておいて、最近RDBMSの性能を後押しするだろうと考えられている存在が、マルチコアCPUとSSDである。元々並列処理が多くCPU数の援護を受けやすいと言うメリットがある上、ランダム読み込み=インデックス読みに強く、しかも書き込みパフォーマンスが良好なSSDは、組み合わせるとRDBMSの性能を爆発的に上げる可能性を秘めている。例えば今の数十万円で買えるハードウェア上でRDBMSのTPS性能が10倍になれば、わざわざ一般システムをNoSQL化する必要など無いわけだ。

まあそんな話をつらつらと考えているとタイムリーにもPublickeyで

SSD専用に設計された「ReThinkDB」、ロックもログも使わない新しいリレーショナルデータベースのアーキテクチャ

などという記事が出ている。RethinkDBの話はちらほらと聞こえてきていたけど、ようやくまとまった情報が出てきた感じである。

紹介されているReThinkDBのアーキテクチャはなかなか独創的なようなものに見えるかもしれないが、実は追記型ヒープストレージによってロックを削減する手法は、「トランザクション処理」(通称Gray本)にも載っているぐらい古いもので、今となってはそれほど目新しいものではない。ましてやTime Travel機能など、POSTGRESの時代にもう存在していたものである。むしろ当時理想論過ぎて現実にはどうにもならなかった完全追記を放棄した現代のRDBMS群から見れば、先祖返りと言っても良いぐらいである。

新しいのは完全追記型インデックスを持つ(これは目新しい)ことと、ReThinkDBは「ログがない」と主張しているところだ。しかし実際には、確かにログファイルは個別では存在しないが、ログにあたるものがないわけではなく、redo/undo両方のログにあたるものはヒープが全て統合されていることである。PostgreSQLではundoとヒープが統合されていて、Oracleではロールバックセグメントがundoログに当たるが、いずれもredoログは搭載している。このへんのログの話は「データベースにおけるデータ保護:ログの話」も参照していただけるとわかりやすいだろう。

結局、ロックフリーなキューを使って書き込みスレッドを直列化することによって、完全追記型を可能にしている、ということだろう。個人的にはコミット時ログ強制書き出しをどうやっているかが気になるが、それはあくまでウェイトであってロックじゃないですよ、と言う理解をすればいいのだろうか。

ただ、それが何故SSDに最適化?というと一見ぴんとこないかもしれない。実はその鍵は以下の部分にある。
ReThinkDBでは、データベース自身がログになっているため、ログのための別のディスクを確保する必要もない。ログを書く必要がないため書き込みが50%減少する。

これは実はSSDだけで考えるなら正しいが、本当はWrite Ahead Loggingで要求されている「ログを書き込む50%の同期書き込みとヒープを書き込む50%の非同期書き込み」のうち後者の非同期書き込みを削減しているわけである。

実は、例えば(ランダム同期書き込みしかしなかった)PostgreSQL7.0に比べてログを書く分50%もI/O量が増えたはずの7.1のほうが早かったように、一昔前の常識ではわざわざ無駄に50%の書き込みを増やす以前の状態のほうが早い。それはHDDの場合遅い順に同期ランダム書き込み>同期シーケンシャル>>>非同期と言う特性があって、極論非同期I/Oなど無視してかまわないぐらい負荷が掛かるからだ。しかし、同期書き込みが高速なSSDではそうではなく、この削減はつまり50%の削減として直接響いてくる。ここがこのファイルシステムが「SSD専用」と銘打ったところである。たぶんHDDでは残念な性能しか出ないだろう。

個人的には、追記型はガベージコレクション(PostgreSQL用語で言うところのvacuum)が難しいのだが、そこをどうやっているかも興味がある。Time Travelができるというぐらいなのだから、全くやっていないのだろうか。キャッシュの部分も興味が無くはないが、実際にはロックフリーなバッファキャッシュアルゴリズムはそれなりに出てきているので、それほどのインパクトは感じられない。

30年前、データベースのボトルネックは間違いなくディスクI/Oだった。しかしハードウェア要件が変わり利用法も変わった。そして出てきたシステムがこのような先祖返りだったというのが実に興味深い。というか「HDDに最適化するための今までの手法」を全部取っ払い、マルチコア向けにロックフリーアルゴリズムを駆使した最新の技術で武装した、というのが正しいだろうか。コアが増え、SSDの価格性能比がどんどん落ちている間は、NoSQLが下層まで降りてくるのはまだまだ厳しそう、といえるかもしれない。

書き始めたら自分だけが止まらない「ネイション」シリーズの第5回。思いついた中でL.starが肯定的に考える「ネイション」は全部紹介し終わったと思うので、最後にこれはだめだ、採用したくないなと思っていた重要なものを紹介したい。それは「反○○」である。 これをナショナリズムと呼んで良いかは疑問があるが、実際ナショナリズムのように働くからそのように扱いたい。

このメカニズムはごくシンプルで「○○憎し」がそのまま共有されて共同体の原則になるものである。○○は好きなものを入れていただきたい。代表的なのは「反米」「反日」「反中」などの国家民族に対するもの、「反共」「反資本主義」のようなイデオロギー、「反キリスト」「反イスラム」の宗教、「反民主」「反マスコミ」のような具体的権力に対するもの、いろいろである。

しばしば「共同体は敵がいなければ団結できない」というような言い方がされるが、それがこの「反○○」である。反証は孤立した文化が安定して存在し続けられた例がいくつも簡単に見つかる。鎖国時代の江戸時代にいったいどんな敵がいたのだろうか。むろん理論上は存在しているが、そんなのを民衆が認識できていたとはおよそ考えづらい。このようなケースでは民族、経済、文化などがその共同体全体を支えるだけの十分な力を持っていたためである。ただあまりにも歩みが遅く、一見その進歩や効力が分かりづらいものである。

しかし憎悪は違う。憎悪は明確な感情のため、共有がきわめて簡単である。簡単に燃え上がって、遙かに巨大な勢力に成長する。他のネイションとも補完的に働き、その勢いを増幅する。 欠点はもっと巨大である。中心にあるものが憎悪であるが故に簡単に暴走するのである。近代以降でナショナリズムが最初に現れたのはフランスの市民革命であることはすでに一致を見ているが、そのフランス革命からして、憎悪故の暴走から免れることはできなかった。

例えば「反社畜」と「労道再興」という2つの勢力は、どっちも現在のあまりよろしくない大企業の労働形態の問題について共闘することが可能だ。しかし企業との戦いに勝利したあとはどうなるだろう。「やる気のある人が本当に自発的に死ぬほど働く」という命題で対決することになるだろう。さらに「反権力」も上記2つと共闘が可能であるが、これはもっとやっかいで、勝利した「反社畜」と「労道再興」は、勝利した時点で権力に変わる。一見強力な「反○○連合」は、このようにあっさり瓦解する。

日本でこの種の図式が一番よく見られるのはマスコミで、彼らは(常にではないが)反権力的な行動を取る。だから野党にしろ若手にしろ、権力のまだ無い人なり団体を持ち上げ、上昇するのを助ける。しかしその人なり団体が権力者になるともうそれは反対する相手、権力の対象である。だからあの特有の「持ち上げて落とす」という、一見すると徹底しない奇妙な行動は、反権力という明確な、一貫した行動軸がある。 こんな感じなので、暴走例はあまりにも多いし、それがどれだけの悲劇をもたらしたか説明は必要ないだろう。

そもそも、敵がいなくなるとどうなるか?巨大な敵を倒した連合勢力がその後空中分解した例は反ナポレオンで一致して戦ったヨーロッパにしろ、反ペルシアで戦ったギリシャ連合軍にしろ、歴史の常連である。あるいはその力を維持するために別の敵を探し出す。

長期にわたって成功した文明というのは、どれも成功するだけの要素を多数併せ持っていて、且つ欠点は非常に少なかったはずなのである。それは芸術的とでも言うべき代物であり、偶然だけで作り出せるほど簡単なものではない。簡単に暴走をするような旗印では、そのような微妙な着地点を見いだすための精密さを致命的に欠くのだ。だから長続きもまず期待できない。

我々は、「ナショナリズム」の力を利用するときに、同時にこのような暗黒面とも向き合わないとならないと言うことを心すべきである。L.starがその避け方を教えられるほど良くできた人間だとは全く思わないが、個人的には常に何も「否定」せずに、何かを肯定するだけで正しい道筋を一つ以上示すことができるか、と言うことに指針をおいている。前4回のどれも、その点は注意深く考えたつもりである。

否定と言う行為は駄目だ、という否定行為を行う逆説的なエントリに見えるが、言いたいのは実は「何かを肯定しよう」ということである。他人を否定するのは簡単だし、理由なんていくらでも見つかる。でもそれは罠だ。何かをなしたいと思うなら、それを廃して自分の道を見つけなければならない。失敗しても良い、気付いた時点で戻ればいいのだ。

↑このページのトップヘ