corner2010年05月2010年05月31日VoltDBは何故早いのかは問題ではない。何をするためのシステムなのかが問題だちょっと小旅行に出ている間にアクセスが伸びていて、おかげさまで前回のVoltDBのエントリが大人気だったようだ。書き足りない部分がいっぱいあったので、補足する意味も込めて書き足してみたい。それは、H-Storeが従来型RDBMSとどれほど異なったシステムか、ということだ。インターフェースの話や大まかな話はしたが、前提となる部分の話はずいぶん抜けてしまっていた。NoSQLを超えるSQLデータベース「VoltDB」。Benchmarkingという記事が紹介されていて興味深い。勝っていると言うから痛快だ。個人的にはこの勝負は高々3ノードしか使っていない時点でスケーラビリティに勝るKVSにずいぶん不利な内容だな、と言わざるを得ない。12ノードぐらいでしかテストされていないというVoltDBだから、30ノードならずっと違う結果が出るだろう。それでも勝ちは勝ちである。そもそも、ある程度のSQLを解するRDBMSなら、あげられた条件ではCassandraに肉薄すらできない。ここまで勝てるのか?と言う話だが、逆に何故今までのDBは遅いのか、と言う話はすでに以下の論文にまとめられている。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とでは圧倒的な差が出て当然である。PostgresでこのVoltDBについて、要を得た比較しているので参考になるだろう。Daveはいくつかの点で、VoltDBがPostgreSQLの代替として使えない、ということを指摘している。コメントで「それはアーキテクチャの問題ではなく機能不足」とされていた部分を除くと限られた同時実行制御モデル従来インターフェースとの互換性オンメモリDBであることによって、メモリ不足が深刻な問題になること。言ったことがあげられる。実はVoltDBにおいてはそんなことは設計の時点で折り込み済みである。先の論文で、なんのためにこんなシステムを実装しようとしたかの結論部分を引用しよう。marketsそう、もう「1つのエンジンがあらゆるところに使い回される時代は終わった」と言っているのである。RDBMSはその点テクノロジー的な優等生を目指している。いやむしろRDBMSが標準に近いのではなく、標準がRDBMSを元に作られたとまで言ったほうがいいかもしれない。車にたとえると、VoltDBはTPC-Cのようなトランザクション処理に特化したレースカーである。CassandraのようなKVSも、同様に又違う種類のトランザクションに特化したレースカーである。その点素のRDBMSはどこまで行ってもセダンだ。VoltDBの数字に踊らされる前に、自分たちの使っているトランザクション特性をしかと考えてみてほしい。あなたのシステムが、メモリに収まらないほどのデータを扱わず、OLAP系の複雑なクエリなど知ったことではなく、でもOLTP性能がほしくて、RDBMS並に完璧なデータ完全性が必要ないならこいつは素晴らしいシステムだ。どれかに当てはまらないならゴミだ。それだけのことである。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はこれに近いデザインになっているだろうというか、他に妥当なデザインが思い浮かばない。これ以上デザインを推し進めたとき、どれだけ彼らの特許に引っかかるかと思うと憂鬱になる。ここでのデザインはあくまで自分の訓練向けと思っているし、かなりのボリュームなのでたぶん全部を実装するのは一人では手に余る。それでも時間を見つけてインターフェース起こしたりより詳細な実装に踏み込んだり、という作業はやっている。クエリのフローの流れや、具体的なストレージノードの初期デザインも頭の中にはできているので、とにかくそういうのをメモ代わりにここに残しながら少しづつ完成に近づけていきたい。ないと、とても現状の最先端には追いつけない。ReThinkDBの試みを読み解く今日も突然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本)にも載っているぐらい古いもので、今となってはそれほど目新しいものではない。Travel機能など、POSTGRESの時代にもう存在していたものである。当時理想論過ぎて現実にはどうにもならなかった完全追記を放棄した現代のRDBMS群から見れば、先祖返りと言っても良いぐらいである。新しいのは完全追記型インデックスを持つ(これは目新しい)ことと、ReThinkDBは「ログがない」と主張しているところだ。実際には、確かにログファイルは個別では存在しないが、ログにあたるものがないわけではなく、redo/undo両方のログにあたるものはヒープが全て統合されていることである。PostgreSQLではundoとヒープが統合されていて、Oracleではロールバックセグメントがundoログに当たるが、いずれもredoログは搭載している。このへんのログの話は「データベースにおけるデータ保護:ログの話」も参照していただけるとわかりやすいだろう。結局、ロックフリーなキューを使って書き込みスレッドを直列化することによって、完全追記型を可能にしている、ということだろう。個人的にはコミット時ログ強制書き出しをどうやっているかが気になるが、それはあくまでウェイトであってロックじゃないですよ、と言う理解をすればいいのだろうか。それが何故SSDに最適化?というと一見ぴんとこないかもしれない。実はその鍵は以下の部分にある。ReThinkDBでは、データベース自身がログになっているため、ログのための別のディスクを確保する必要もない。ログを書く必要がないため書き込みが50%減少する。Loggingで要求されている「ログを書き込む50%の同期書き込みとヒープを書き込む50%の非同期書き込み」のうち後者の非同期書き込みを削減しているわけである。実は、例えば(ランダム同期書き込みしかしなかった)PostgreSQL7.0に比べてログを書く分50%もI/O量が増えたはずの7.1のほうが早かったように、一昔前の常識ではわざわざ無駄に50%の書き込みを増やす以前の状態のほうが早い。それはHDDの場合遅い順に同期ランダム書き込み>同期シーケンシャル>>>非同期と言う特性があって、極論非同期I/Oなど無視してかまわないぐらい負荷が掛かるからだ。同期書き込みが高速なSSDではそうではなく、この削減はつまり50%の削減として直接響いてくる。ここがこのファイルシステムが「SSD専用」と銘打ったところである。HDDでは残念な性能しか出ないだろう。個人的には、追記型はガベージコレクション(PostgreSQL用語で言うところのvacuum)が難しいのだが、そこをどうやっているかも興味がある。Travelができるというぐらいなのだから、全くやっていないのだろうか。キャッシュの部分も興味が無くはないが、実際にはロックフリーなバッファキャッシュアルゴリズムはそれなりに出てきているので、それほどのインパクトは感じられない。30年前、データベースのボトルネックは間違いなくディスクI/Oだった。ハードウェア要件が変わり利用法も変わった。出てきたシステムがこのような先祖返りだったというのが実に興味深い。いうか「HDDに最適化するための今までの手法」を全部取っ払い、マルチコア向けにロックフリーアルゴリズムを駆使した最新の技術で武装した、というのが正しいだろうか。コアが増え、SSDの価格性能比がどんどん落ちている間は、NoSQLが下層まで降りてくるのはまだまだ厳しそう、といえるかもしれない。書き始めたら自分だけが止まらない「ネイション」シリーズの第5回。思いついた中でL.starが肯定的に考える「ネイション」は全部紹介し終わったと思うので、最後にこれはだめだ、採用したくないなと思っていた重要なものを紹介したい。それは「反○○」である。これをナショナリズムと呼んで良いかは疑問があるが、実際ナショナリズムのように働くからそのように扱いたい。このメカニズムはごくシンプルで「○○憎し」がそのまま共有されて共同体の原則になるものである。○○は好きなものを入れていただきたい。マスコミ」のような具体的権力に対するもの、いろいろである。「共同体は敵がいなければ団結できない」というような言い方がされるが、それがこの「反○○」である。反証は孤立した文化が安定して存在し続けられた例がいくつも簡単に見つかる。鎖国時代の江戸時代にいったいどんな敵がいたのだろうか。理論上は存在しているが、そんなのを民衆が認識できていたとはおよそ考えづらい。このようなケースでは民族、経済、文化などがその共同体全体を支えるだけの十分な力を持っていたためである。あまりにも歩みが遅く、一見その進歩や効力が分かりづらいものである。憎悪は明確な感情のため、共有がきわめて簡単である。簡単に燃え上がって、遙かに巨大な勢力に成長する。他のネイションとも補完的に働き、その勢いを増幅する。欠点はもっと巨大である。中心にあるものが憎悪であるが故に簡単に暴走するのである。近代以降でナショナリズムが最初に現れたのはフランスの市民革命であることはすでに一致を見ているが、そのフランス革命からして、憎悪故の暴走から免れることはできなかった。「反社畜」と「労道再興」という2つの勢力は、どっちも現在のあまりよろしくない大企業の労働形態の問題について共闘することが可能だ。企業との戦いに勝利したあとはどうなるだろう。「やる気のある人が本当に自発的に死ぬほど働く」という命題で対決することになるだろう。「反権力」も上記2つと共闘が可能であるが、これはもっとやっかいで、勝利した「反社畜」と「労道再興」は、勝利した時点で権力に変わる。強力な「反○○連合」は、このようにあっさり瓦解する。日本でこの種の図式が一番よく見られるのはマスコミで、彼らは(常にではないが)反権力的な行動を取る。野党にしろ若手にしろ、権力のまだ無い人なり団体を持ち上げ、上昇するのを助ける。その人なり団体が権力者になるともうそれは反対する相手、権力の対象である。あの特有の「持ち上げて落とす」という、一見すると徹底しない奇妙な行動は、反権力という明確な、一貫した行動軸がある。こんな感じなので、暴走例はあまりにも多いし、それがどれだけの悲劇をもたらしたか説明は必要ないだろう。そもそも、敵がいなくなるとどうなるか?巨大な敵を倒した連合勢力がその後空中分解した例は反ナポレオンで一致して戦ったヨーロッパにしろ、反ペルシアで戦ったギリシャ連合軍にしろ、歴史の常連である。その力を維持するために別の敵を探し出す。長期にわたって成功した文明というのは、どれも成功するだけの要素を多数併せ持っていて、且つ欠点は非常に少なかったはずなのである。それは芸術的とでも言うべき代物であり、偶然だけで作り出せるほど簡単なものではない。簡単に暴走をするような旗印では、そのような微妙な着地点を見いだすための精密さを致命的に欠くのだ。長続きもまず期待できない。我々は、「ナショナリズム」の力を利用するときに、同時にこのような暗黒面とも向き合わないとならないと言うことを心すべきである。L.starがその避け方を教えられるほど良くできた人間だとは全く思わないが、個人的には常に何も「否定」せずに、何かを肯定するだけで正しい道筋を一つ以上示すことができるか、と言うことに指針をおいている。前4回のどれも、その点は注意深く考えたつもりである。否定と言う行為は駄目だ、という否定行為を行う逆説的なエントリに見えるが、言いたいのは実は「何かを肯定しよう」ということである。他人を否定するのは簡単だし、理由なんていくらでも見つかる。何かをなしたいと思うなら、それを廃して自分の道を見つけなければならない。失敗しても良い、気付いた時点で戻ればいいのだ。「リベラルなのに護憲」?別におかしくなんてありません。「本当の日本のリベラル」こそまず改憲をめざせ帰国しました。