2009年4月16日木曜日

Flash-Based DBMSの最前線

フラッシュメモリーを使ったSolid State Drive (SSD)の容量が160GBに到達し、市場価格も下がってきたことにより、ハードディスクの代替品としてSSDを使う用途がいよいよ現実味を帯びてきました。低容量のものなら既にiPodやデジカメ用のメディアなど身の回りにも普及しており、市場ではすでに「破壊的イノベーション(「イノベーションのジレンマ―技術革新が巨大企業を滅ぼすとき」より)」が起こっているといえます。(HDD搭載のWalkmanとか既に滅んでいる例もあるし。。。)

では、SSDの登場によってデータベースシステム(DBMS)の実装はどう変わるのか?2009年4月現在の最新論文リストPFIの太田君が紹介してくれたの
で、データベース国際会議の最高峰であるSIGMOD, VLDB, ICDEや、DaMoNワークショップ(新しいハードウェアに特化したDBの研究会)の論文を中心に紹介します。こういうのは速さが勝負なので、まとめて午前中に読んでみました。

まず前提知識として、SSDの特徴は、Sequential Read(連続したブロックを読む)、Random Read(ランダムな位置のブロックを読む)の性能が従来のハードディスク(HDD)に比べて2~10倍以上、製品によっては100倍以上速いこと。

ちなみに、IntelのX25M(80GB/160GB)では、それぞれの操作で最大:
Sequential Read: 250MB/s,   Sequential Write: 70MB/s
Random Read:  35000 IO/s,  Random Write: 3300 IO/s 
一方、Seagateの7,200RPMのHDDでは、
Sequential Read: 120MB/s,  Sequential Write: 120MB/s
Random Read:  100 IO/s,  Random Write: 110 IO/s

このデータだけみると、Sequential Wite以外すべての面においてSSDがHDDを上回っていますが(Intel X25Eにおいては、Sequential Writeが170MB/sになって完全にHDD上回っています)、これはハイエンド製品のデータで、巷に出回っている1~2万円台の低価格SSDはRandom WriteがHDDより遅いのが普通です。(とある32GB SSDでは、Random Read: 3100 IO/sに対し、Random Write: 25 IO/s だとか。HDDよりrandom writeが遅いです)。

SSDの特徴をまとめると
  • read/writeのパフォーマンスが全体的に向上 (1)
  • random read/random writeのパフォーマンスに差があること (2)
  • random writeがHDDより遅いことがある (3)
このうち(1), (2)はHDDより性能が上がるだけなら、既存のDBMSがそのまま速くなって嬉しい。これは、kazuhookuさんのエントリ「 SSD がコモディティになっても状況はかわらない」にあるとおり。ただし、2008年前半は、Random WriteがHDDより速いIntel X25シリーズが出ていなかったので、(3)が深刻な問題でした。そして、実は、今出ている論文というのはこの製品が出る前の研究であるので、(3)の問題を真面目に扱っています。(国際学会の論文というのは、最先端から半年~1年遅れで出てくるものだということは踏まえておいてください。研究の最前線は常に研究者の頭の中です。)

それゆえ残念なことに、今普及している低価格のSSDには効果がありそうだけれど、今後は不要になりそうなアプローチの論文というのもあります:
  • S. W. Lee, and B. Moon. Design of Flash-Based DBMS: An In-Page Logging Approach. SIGMOD 2007. [pdf] (SSDのrandom writeが遅いので、データページ内にログも配置するとDBMSが速くなるという研究)
  • Y. Li, B. He, Q. Luo and K. Yi. Tree Indexing on Flash Disks. ICDE 2009. [pdf]  (Random writeが遅いSSD対策として、B+-treeに独自のページレイアウトをmergeして、insertionの性能を上げた研究。Random Writeが遅いSSDで実験しているから速い結果がでているけれど、IntelのX25シリーズを使ったり、key値だけでなくclustered-indexを使った場合や、ロック処理までちゃんと実装したら、実際のinsertion, throughputの性能差はほとんどないと思われる。)
これらのアプローチはもはや時代遅れに思えてきます。一方、(3)が問題だった製品を使っているにも関わらず、SSDのDBMSにおけるメリットを適格に示している論文は、Samsungのチームが関わっている以下の研究:
  • B. Moon, C. Park, S. W. Lee. A Case for Flash Memory SSD in Enterprise Database Applications. SIGMOD 2008. [pdf]  (SSDを使うと、更新の時系列に沿ってバージョン番号が付けられたrecord chainの探索(MVCCで使う)が速くなり、大規模データの問い合わせに必要な、external merge sort, hash joinの性能(ともにrandom readが多発)が高速化されることを検証した論文)
上の論文の実験でも同じシステム構成を用いているのですが、HDDとSSDを組み合わせて使うアプローチを提示しているのがこれ:
  • I. Koltsidas, and S. D. Viglas. Flashing Up the Storage Layer. VLDB 2008. [pdf] (これもまだ(3)が問題だった当時の話なのですが、状況によってディスクページの保存先をSSD, HDDと切り替えるアルゴリズムを提案しています)
SSDの価格が十分に下がるまでは、このように、random readを速くしたいときはSSD、大きなデータをとりあえず置いておきたいときや、sequential writeでもいいという場合はHDDという素直なアプローチも悪くないと思います。

「5分間ルール」から20年

1987年にJim Gray(Jim Grayに関してはこちらのエントリの最後で紹介しています)が、「5分間ルール」と称して、性能やそれに応じたストレージ価格コストを考えると「5分以内にアクセスされるデータ(4KB程度)はメモリに置いておくべきだ」という提案をしました。その10年後は、HDDのアクセススピード向上は比較的緩やかだったのに対し、ディスクの容量がメモリに比べて急激に上昇し価格は下がる、という状況が相まって、「5分間ルール(10年後)」は維持されていました。

20年後、SSDが登場して、「5分間ルール」はどうなったのか?というのが次の論文:
  • G. Graefe. The Five-Minute Rule Twenty Years Later, and How Flash Memory Changes the Rules. DaMoN 2007. [pdf
結論を言うと、「5分間ルール」はSSDに関してはそのまま。ただし、HDDに関しては256KBまでページサイズ(B+-treeのリーフなど)を増やした方が検索性能が良くなっている。SSDだと、従来通り2KB~4KBくらい小さなページサイズが速い。従って、HDDとSSDを共に使う場合、それぞれで最適なページサイズの不均衡があるので、先の'Flashing Up The Storage Layer'のような工夫が必要になるよ、という話。SSDを、メモリバッファの拡張としてとらえるか、HDDの拡張として使うかで、アプリケーションや、最適なアルゴリズムも変わることが示唆されており、SSDの利用価値がどこにありそうかを検討するブレインストーミング用の論文として便利だと思います。ちなみに、2種類のページサイズを使い分けるB-Treeは、すでに考案されている(SB-Treeというらしい)ので、こういうったものを実装してみるのも手。

ただ、「B木 - naoyaのはてなダイアリー」で触れられているようなSSDがB+-Treeを駆逐するイノベーションというのはどうも感じられていません。そもそも、B+-treeの構造と、バッファ管理、ログ、ロックやスナップショットなどのトランザクション管理は今でも十分切り離せてなくて、B+-tree以外の索引構造もいままでいろいろ研究されてきましたが(R-treeとか)、検索専用には使われても、更新用途にはどれも生き残っていません。(トランザクション管理の難しさについては、こちらを参照してください:Leo's Chronicle: Top 5 Database Research Topics in 2008

率直なDB研究者としての意見は、
DB研究者って、どうもSSDにはまだ悲観的な気がしているのだけれど、ここで、破壊的イノベーションが起こってあたふたしたりするのだろうか 
http://twitter.com/taroleo/status/1506861323
という消極的なものですが、本当は、あたふたするような事態があった方が、研究テーマが増えて面白くなるので、非常に期待はしています。破壊的イノベーション(適用分野、マーケットががらりと変わってしまうような発明)は、アプリケーションの変化に起因するものだとも思います。SSDの真の価値は、既存のDBMSが進化していく方向にではなく、まったく新しい用途のDBMSを作り得る点と考えると、今後SSDの動向を追うのが楽しくなるのではないでしょうか。

関連

1 件のコメント:

Mikiya Okuno さんのコメント...

こんにちは。興味深く拝見させて頂きました。

SSDの今後の展開は楽しみですよね。SSDによって、エレベーターシークのような最適化は間違いなく不要になるので、データベースの最適化ロジックは別の方向がもっと発達するんじゃないかというのが個人的な見解です。これまでDBの研究はシークのオーバーヘッドを如何に軽減するか?なんていう研究が多かったですから。

ただし、高価なディスクアレイ装置を使えば、これまでもシークタイムの問題から解放されていました。性能だけを見ると、SSDはディスクアレイ装置に近いと思います。なので、SSDがDBの世界を変える(既存のDBを駆逐する)というよりは、ディスクアレイ装置を駆逐するのではないかと思いますがいかがでしょうか。

半導体の容量は倍々で増えていきますから、一年後にはHDDが陳腐化しているような気がします。数年後には、大容量化するためにRAIDが必要だということも少なくなってくるのではないかと思います。

License

Creative Commons LicenseLeo's Chronicle by Taro L. Saito is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.1 Japan License.