asmsuechan’s blog

Main Memory Database Systems: An Overview

Database Systems 論文

読んだ論文

Garcia-Molina, et al., Main Memory Database Systems: An Overview, in IEEE Trans. on Knowl. and Data Eng., 1992

この論文をざっくりまとめます。

要約

インメモリデータベース(MMDB)はデータをメインメモリに保存するデータベースのことである。MMDBは従来のデータベース(DRDB)と比べて高速に処理を行うことができるが(本当か?)、(xxxという欠点がある) この論文では、MMDBが動く仕組みと実際に開発されてきたMMDBの紹介を説明している。

1. INTRODUCTION

メインメモリデータベース(MMDB)はメインメモリにデータを保存するデータベースで、従来のデータベース(DRDB)はディスクにデータを保存するものである。しかし、MMDBはバックアップとしてデータをディスクに保存し、DRDBはキャッシュとしてメインメモリにデータを保存する。このようにMMDBもDRDBもメインメモリとディスクの両方を使う。

MMDBは近年(つっても1992年当時のこと)の半導体メモリチップの低価格化と集積度の向上により実用化されたもので、デッドライン時間が決まっているリアルタイムシステムにおいて効果的に使うことができる。

この論文ではMMDBにおいてメインメモリと磁気ディスクの差による影響に関して論じた。

以下の3つの質問と答えは、MMDBに関してよくある疑問である。

(1) データベースの全体ががメインメモリに収まると考えるのは合理的なことなのですか？

Yes

でも、衛星の画像データみたいな大きなデータだとメインメモリに格納しきれなくなってしまうだろうから、大きなデータと小さなデータは分けて管理する。

データにはよく使われるHotなデータとあまり使われないColdなデータがあって、Hotなデータをメインメモリに格納するようにしてColdなデータをディスクに格納するようにする。この時、MMDBとDRDBの2種類でデータが管理される。

(2) MMDBとめっちゃ大きなキャッシュをメインメモリに持つDRDBはどう違うのですか？

asmsuechan: これは私も真っ先に感じた疑問だからここに答えがあってよかった

まずインデックス構造が問題で、DRDBにおいてメインメモリの中に全てのデータがあったとしてもディスク用の設計が使われてしまう。さらに、データを使用するアプリケーションはデータがディスクに存在するかのようにバッファマネージャーを使うのでこうなるとあまりメリットはなくなる。

でも、良いDBMSはデータがメインメモリに保存されているかのように振る舞うようになるはずなので、将来的にはMMDBとDRDBの違いはなくなると思う。

(3) メインメモリは何か特別なハードウェアによって不揮発で信頼できるものになるのか？

これにはyesともnoとも答えられなくて、MMDBの設計によるとしか答えられない。なぜなら無停電装置を導入したりエラー検出をしっかりしたり冗長性を高めたりしても、それはメインメモリが落ちる確率を下げるだけでどんなに頑張っても0%にはならないから。だからバックアップは必ず必要になる。

2. メモリ常駐データの衝撃

この章ではDBMSにおいて重要ないくつかのコンポーネントにおいてメモリ常駐に関する事柄を説明する。

A. 並行実行の制御

DBの、トランザクションを並行実行する場合におけるデータのロックを制御する仕組みについて。

まず、データがメモリに常駐していてデータの競合が小さいならばロックの粒度を小さくしてもこの利点はないので、ロックの粒度をフィールドやレコードなどの小さい単位からリレーションなどの大きな単位にして良い。

最悪DB全体で1つの単位としてもよくて、実際これの研究も行われていた。これはトランザクションが直列実行されることになる。この場合ロック処理において、セット/リリースやデッドロックへの対処などの制御処理をほぼ無視できるのでトランザクションの直列実行は望ましい。

なお、実際のロック処理(排他ロック)は、2ビットでオブジェクトがロックされているかの情報をそのオブジェクトにトランザクション待ちが発生しているかどうかを表して実現する。

asmsuechan: このセクション、プロセスの並列処理周りの知識がないとちょっと難しい

B. コミット処理

処理の失敗に備えるために、トランザクションのログを取る必要がある。このログはディスクに保存しなければならないので、この保存処理がボトルネックになってスループットを下げてしまうことがある。

ディスクを使うDBでも同じ問題は起きるけど、MMDBではここが唯一ディスクを操作する操作だからよりシビアになってしまう。

今まで研究されてきている、この問題を解決するいくつかの手法を紹介する。

stable メインメモリにログを保存する
特別なプロセスやプロセッサを使ってstable メインメモリからディスクにデータを保存するようにする。いわゆるキューイングかな。
precommitするようにする
group commitという手法を使う。
これはページがいっぱいになるまでログを溜めた後にまとめてディスクに保存する手法のことである。

C. アクセス手法

MMDBに置いて、B-Treeはあまり有用ではない。それはB-Treeのハッシュの仕組みが領域を大きく消費するからだ。

メインメモリにあるデータへアクセスするには、B-Treeのようにデータをインデックスに保存する必要がない。これは、メインメモリはディスクに比べてアクセス速度が速くポインタでも十分なスピードでデータを見つけることができるからだ。

このことより、インデックス中の可変長のフィールドに関する問題を解決したり、ポインターのサイズがデータより小さい場合は容量を削減したりできる。

D. データ表現

リレーションはデータのポインターのタプルとして表現される。ポインタによりスペースの効率利用が可能で、さらに可変長データの表現が容易になる。

E. クエリ処理

上でも述べたように、データのポインターでリレーションが表現できるなら、リレーション関連の処理が効率よく実行できる。

ここで一番重要なのは、「データがメモリにあるからクエリの速度を上げることができるようなコンパクトなデータ構造が可能である」ということである。

F. リカバリ

揮発性のメモリから不揮発性のメモリにデータをバックアップすることは必須である。

バックアップからデータをリカバリすることで大事なのは、(1) バックアップを最新に保つ処理と(2) 失敗から復旧する処理である。

以前Commitの部分で述べたように、DBに何か問題があったとき、ログからデータを復旧する。

チェックポインティングはなるべくトランザクションの処理を邪魔してはいけないが、どうしてもロックなどの処理が発生する。その代償として動機を行わないfuzzy dumpingが知られている。

G. パフォーマンス

メインメモリデータベースのパフォーマンスはだいたい処理時間に依存する。

H. APIと保護

DRDBに置いて、DBMSとアプリケーションのデータの受け渡しはプライベートバッファを会して行われている。これに対してMMDBではオブジェクトが直接メモリアドレスで参照される。

プライベートバッファをなくしてトランザクション時にオブジェクトに直接アクセスするようにすると、トランザクションがシンプルな場合にはトランザクションにかかる時間のほとんどがビット(?)をメモリからバッファにコピーする時間に費やされることになる。

しかしデータに直接アクセスするときには、DBMSが認知していないデータを変更できてしまうためにこの変更をDBMSが検知できずにログに書かれないという問題がある。

I. データクラスタリングとマイグレーション

DRDBではデータオブジェクトはまとまって保存されたりクラスタ化されたりする。

asmsuechan: 空間的局所性やな

MMDBのデータはDRDBのデータと違って分散しているので、このデータをディスクに移すときどのように、またどこに保存するかという問題が発生する。

この解決方法には様々あって、ユーザーがデータの移動(migration)時にどうクラスタリングするかを手動で設定する方法から、アクセスパターンから自動でクラスタを決定する方法まである。

ここで私たちが言いたいのは、データの移動と動的クラスタリングはMMDBの要素であるということである。

3. システム事例

この章では、今まで理論の設計や実装がされてきたインメモリデータベースに関して述べる

A. OBE

OBEはIBMとOffice-By-Exampleの合同チームが開発したプロジェクトであり、IBM 370アーキテクチャの上で実行される。このDBはアドホッククエリの処理に重点が置かれている。

データ表現としてOBEではポインタが多用されていて、リレーションはタプルのリンク付きリストとして’保存される。

ジョインはネストされたループ(nested-loop)で実行され、インデックスはジョインの実行時にその場で作られる。

B-G

下書き保存し忘れて消えた、後ほど復旧。

結論

5分より短い間隔でアクセスされるデータはメモリに置くべきであるという調査がある。これは、データへのアクセスにかかる金銭的なコストから計算したものである。しかし一番大事なのは、メモリの値段が下がるにつれてこの時間も長くなるということだ。

まとめ

この論文はインメモリデータベースの基礎中の基礎を分かりやすく説明してくれているので、かなりしっかり読んでしっかり訳しました。

でも具体例のところは話が古くて正直あまりピンと来なかったところが結構あったのでもっと勉強せねばって気持ちです・・・