従来のデータベースをメモリに載せるだけではだめなのか？ インメモリとカラム型データベースの可能性を調べる（その2）

現代のサーバは1台で複数のプロセッサを備え、数百ギガバイトから数テラバイトのメインメモリを搭載可能です。これは多くの企業で利用されているデータベースがそのままメモリに載るほどの容量です。

大量のメモリを搭載したサーバを用いれば、Oracle DatabaseやSQL ServerやDB2など従来のディスクベースのデータベースでも、データベースをまるごとメインメモリのバッファキャッシュに載せることができます。そうすればディスクアクセスのボトルネックは事実上ほとんどなくせるため、高速なデータベースアクセスが実現します。

だとしたら、データベースをすべてメモリに載せる機能を備えたインメモリデータベースを、わざわざ使う必要はあるのでしょうか？

この疑問は、以前の記事「キャッシュの大きいRDB vs インメモリデータベース、性能がどれだけ違うのか調べてみると」で触れているので、まずはその記事を振り返ります。

メモリ上にデータがあっても、インメモリデータベースは1000倍速い

従来のデータベースとインメモリデータベースの違いは、従来のディスクベースのデータベースであるOracle Databaseと、インメモリデータベースのTimesTenという2つの製品を提供している日本オラクルが用意してくれていました。

少し前のインタビューですが、2008年7月28日付けのThinkITの記事「第3回 性能検証！インメモリDB」で、インメモリデータベースのTimesTenはディスクベースのデータベースに比べて1000倍高速であると、次のように説明しています。

1行の検索であれば数マイクロ秒、1行の更新であっても数十マイクロ秒もかかりません。ディスク型RDBMSではどんなにチューニングしたとしてもミリ秒が限界と言われていますので、TimesTenのレスポンスタイムがけた違いに速いことがわかります。

1マイクロ秒とは100万分の1秒、1ミリ秒は1000分の1秒です。同じようにメモリ上にデータベースがある状態で、インメモリデータベースは従来のディスクベースのデータベースよりも1000倍速くレスポンスを返す、ということになります。

メモリに最適化されたデータ構造とアルゴリズム

この違いはどこから生じてくるのでしょうか？ 日本オラクルが公開している「Oracle TimesTen製品とテクノロジー ホワイトペーパー」では、インメモリデータベースではメモリ上のデータアクセスに最適化されたデータ構造とアルゴリズムを採用していることが理由だと説明しています。

RDBMSで実行されるほとんどの操作は、「データは主にディスクに存在する」という仮定のもとに行われます。最適化のアルゴリズム、バッファ・プールの管理、索引を利用した検索方法は、この基本的な仮定を重視します。

一方、Oracle TimesTenではデータはメイン・メモリーにあるため、データに対してより直接的なルートをとることができ、コード・パスが短くなり、アルゴリズムも構造も簡潔になります。

一般にディスクベースのリレーショナルデータベースでは、インデックスのデータ構造にB+ツリー構造を採用していることがよく知られています。しかしB+ツリーはディスクに最適化されたデータ構造であり、インメモリデータベースではもっとメモリに最適化されたデータ構造とアルゴリズムが採用されているとのこと。

B+ツリーの構造での目的は主に、データ・ファイルの索引付けの検索に必要なディスクI/Oの回数を削減することです。（略）この構造は、データと索引のファイルがディスク上にある場合は有効ですが、データがメモリーにある場合は適していません。データがメモリーに保持されると、索引付けのスキームの目的は、I/Oの削減ではなくCPUサイクルの削減になります。（略）

Oracle TimesTenでは、処理を表す図は簡単です。Tツリーは、メイン・メモリーのアクセスに対して最適化されています。Tツリーは、サイズとアルゴリズムの両面で、B+ツリーに比べ低コストな索引エントリを備えています。

インメモリデータベースではCPUキャッシュに最適化

インメモリデータベースであるSAP HANAのアーキテクチャでも、メモリに最適化されたデータ構造が採用されています。HANAのアーキテクチャ（正確にはHANAの前身となるSanssouciDBのアーキテクチャ）を解説した書籍「In-Memory Data Management」によると、HANAの内部で行指向のデータベース処理（HANAには行指向のエンジンと列指向のエンジンの2つを備えている、詳しくは後述）を行っている部分では、B+ツリーよりもインメモリ処理に優れたCSB+ツリー（Cache Sensitive B+-Trees）を採用しているとのこと。

In comparison to the traditional B+tree, the keys on each node are stored sequentially in memory to eliminate pointers to find the next key. The size of the node lists is aligned to the size of the cache line to avoid unnecessary cache misses. As a result the search performance of a CSB+tree is better than the B+tree due to its better memory structure.（53p）

（CSB+ツリーは）既存のB+ツリーに比べて、各ノードのキーは次のキーを指すポインタを省略するため、連続してメモリに格納されている。不必要なキャッシュミスを回避できるよう、ノードリストのサイズはキャッシュラインに揃えられている。結果、よりよいメモリ構造のおかげで、CSB+ツリーの検索性能はB+ツリーより優れている。

CSB+ツリーについては、論文「Making B+-Trees Cache Conscious in Main Memory」で詳しく解説されていますが、従来のB+ツリーをインメモリ処理向けに改変し、特にCPUのL1、L2キャッシュの利用効率を高めてアクセス速度を向上させたものです。

最適化のレベルが、ディスクやOS vs メモリやCPU

一般にディスクベースのリレーショナルデータベースでは、性能向上のためにハードディスクやOSのI/Oが最適化されるように、ブロックサイズと呼ばれるデータの管理単位を決めます。メモリ上に設定されたバッファキャッシュもこのブロックサイズ単位で管理されており、バッファキャッシュ内のデータへのアクセスは管理テーブル内のポインタをたどって行われることになります。

一方でインメモリデータベースでは前述のCSB+ツリーの解説でも分かるとおり、CPUのキャッシュサイズやメモリアドレスに対するアラインメントに焦点を当てて、CPUがより高速にメモリ上のデータにアクセスできることに最適化されたデータ管理単位やデータ構造が決められます（ちなみにHANAはインテルのXeonプロセッサに最適化されています）。

つまりインメモリデータベースとディスクベースのデータベースでは、最適化のレベルが桁違いなのです。これが、メモリ上にデータベースを置いたとしても、従来のデータベースとインメモリデータベースでは性能に1000倍もの大きな開きがある理由につながっています。

≫次の記事「インメモリデータベースでサーバが落ちたらデータはどうなる？ インメモリとカラム型データベースの可能性を調べる（その3）」に続きます。

インメモリとカラム型データベースの可能性を調べる

• インメモリデータベース、カラム型データベースは使い物になるのか？ インメモリとカラム型データベースの可能性を調べる（その1）
• 従来のデータベースをメモリに載せるだけではだめなのか？ インメモリとカラム型データベースの可能性を調べる（その2）
• インメモリデータベースでサーバが落ちたらデータはどうなる？ インメモリとカラム型データベースの可能性を調べる（その3）
• カラム型データベースはなぜ集計処理が高速で、トランザクションが苦手なのか。インメモリとカラム型データベースの可能性を調べる（その4）
• カラム型データベースでトランザクション処理を実現するカラクリとは？ インメモリとカラム型データベースの可能性を調べる（その5）