2008年のSIGMODに掲載された論文。 “The VoltDB Main Memory DBMS"でこの論文が「伝統的なDBMSアーキテクチャでは必要な処理(トランザクション処理など)は実質10%程度しか行われておらず、90%は他の処理によるオーバヘッド」としているとあり、タイトルも面白そうだったので読んでみた。
※ 参考論文の注釈(リンクつけてない)と図表の番号は論文中のものと同じにしてある。
簡単なまとめ
OLTP向けのDBMSの特徴であるロギング、ロック、ラッチ、バッファマネージャの処理を取り除いて多少の最適化を行ったところ、修正を加えたTPC-Cのベンチマークで20倍高速になった。 この内訳を分析し、今後のOLTPエンジンの実装について並行処理・マルチコアサポート・レプリケーションマネジメント・一貫性などについて議論する。
背景
最近の一般的なOLTP向けDBMSには標準で以下のような特徴を持っている。
- テーブルストレージのための様々なon-disk用データ構造
- ロックベースの並行処理による並行クエリ処理
- ログベースのリカバリ
- 効率的なバッファマネージャ
しかしこれらの特徴は1970~1980年に開発されたもので、この当時のOLTP向けDBMSはメモリの数倍の容量だった。
今では状況は大きく異なっている。 第一に、OLTPは非常に高速で、トランザクションはms単位で計測される。また、メモリは数千ドルで購入可能で、OLTPのデータはメモリに収まることが多い。 第二に、インターネットの進化に伴って、いくつかのドメインで様々なDBライクなストレージが必要になっており、これらでは全てのDBMSの特徴が必要でないこともある。
このような状況に置いて、OLTPシステムをメインメモリに最適化することは良いアイディアだが、いくつかの他の選択肢も考えられる。
- ログレスDB
- リカバリが不要であったり、クラスタの他のノードからリカバリできるもの
- ex) Harp[LG+91], Harbor[LM06], C-Store[SAB+05]
- シングルスレッドDB
- マルチスレッドかはディスクへのアクセスのレイテンシを軽減するために重要だったが、メモリを前提にすると必要ないこともある。
- マルチプロセッサの対応は必要だが、仮想化技術によって1コアを独立した処理ノードとすることも大きなオーバヘッド無しでできるようになってきている。[BDR97]
- トランザクションレスDB
- トランザクションサポートは多くのシステムで必要ない。
- 特に分散インターネットアプリケーション(distributed Internet applications)では結果整合性(eventual consistency)が"transsactional consistency"よりしばしば好まれる。[Bre00, DHJ+07]
このような提案を実現したDBを構築した例もあるが、これらの設定の違いが実際にどれほどの違いを生むのだろうか。
これが、この論文の中心的な疑問である。
実験環境・計測内容
ロギング、ロック、ラッチ、バッファマネージングにどれくらいのオーバヘッドがあるかを調査するために以下の環境を用いている。また、一部実験のための最適化を行っている。
Shore
DBMSとしてShoreを用いている。
Shore(Scalable Heterogeneous Object Repository)はWisconsin大学で、1990年の初期に開発されたもので、ファイルシステムとobject-oriented DBの技術によって設計された、型付けされた持続性のあるオブジェクトシステム(typed persistent object system)らしい。
このShoreのストレージマネージャー部分は最近のDBMSの特徴である、並行処理や2フェーズコミットを用いたACID特性によるリカバリ、WALなどの特性を備えていて、これらはJim Grayのトランザクション処理[GR93]を参考にして、ARISE論文[MHL+92,Moh89,ML89]をもとにして実装されている。
（ACIDとかWALとかの主要の部分はPostgreSQLと同じ感じなんだろうなーくらいに理解した。論文中の3.1にアーキテクチャーの説明もある）
Shoreの最適化
Shoreの最適化として削った機能について説明する。 表1に最近のOLTPシステムの特徴と、DBMSにおいて取り除ける機能のまとめを示す。
削除した処理の内容と図7における表示名。
- Remove logging
- ディスクへの書き込み要求の削除(図7における"disk log")
- 書き込むログの準備処理、書き込み処理(図7における"main log")
- Log Sequence Number(LSN)の処理(図7における"LSN")
- Remove locking
- ロックマネージャがすぐに要求を許可する返り値を返すように変更
- Remove latching
- 全てのmutexリクエストが条件を満たしているという返り値を返すように変更
- Remove buffer manager calls
- Miscellaneous optimization
修正TPC-C
TPC-Cは販売システムにおける地区ごとの倉庫の在庫管理を含めた会計処理を元にしたベンチマーク。
この処理には
- 注文(New Order transsaction)
- 支払いの記録(Payment)
- 配送の注文
- 注文の確認
- 倉庫の在庫レベルの監視
の5つのトランザクションが含まれている。
この処理時間の内90%の時間を最初の2つのトランザクションに使っており、実験の影響を正確に知るためにこのベンチマークを簡易化し、この2つに若干の修正を加えて、この2つの処理のみを実行するベンチマークで実験を行っている。
実験端末
single-core Pentium 4, 3.2GHz, 1MB L2 cache, ハイパースレッディングoff, 1GBのRAM上のLinux 2.6で実験。
標準ユーティリティのiostatを使って(ログマネージャの出力を除く)ディスクアクティビティがないことを確認し、実験。
計測方法
iostatでハードディスクへのアクセスがないことを確認した上で、修正TPC-Cのベンチマークを40000トランザクション実行する。
ほとんどのグラフでは、このときのCPUパフォーマンスカウンタによるCPUの命令数(CPU instruction counts)を計測した結果を示す。（全体の実行時間やCPUサイクル数はハードやコンパイラの性能による影響を受けやすいため）
実験結果(OLTP処理のオーバヘッド)
最適化を施したことでメモリに収まり、ディスクアクセスを行わなくなった状態で、全11個の最適化による高速化への影響を図5~7に示す。 図5, 6はPayment, New Orderそれぞれのトランザクションにおける結果、図7はNew Orderのトランザクション処理におけるより詳細な最適化処理ごとの結果。
↓図5, 図6
↓図7
図の細かい点については図を見てわかる程度の説明しかないので省略。
最適化前の、メモリに乗り切り、ログマネージャ以外はdiskにI/Oをしない状態での
New OrderとPaymentで半々のベンチマークでは、平均で1.6 ms/xaction(640 xaction/s)だったのに対し、全ての最適化を行った後では80 μs/xaction(12,700 xaction/s)となり全体で20倍の高速化に成功した。
しかし、個々の修正には大きな改善はなく、buffer managerを最後に取り去る前の段階では3倍程度の高速化にしかならず、buffer managerをとって一気に20倍の高速化ができた。
命令数とCPUサイクル数
PaymentとNew Orderによるトランザクションの命令数とサイクル数を図8に示す。
↓図8
CPUキャッシュミス、パイプライン、命令分岐などによって、実行時間やサイクル数は変動してしまうため、命令数とサイクル数の整合性は期待していない。
たとえば、著者らのカーネルコードの処理とLoggingの処理はサイクル数の割合が大きくなっているが、これはカーネルは分岐予測の量がおおく、ほとんどが関数呼び出しであること、Loggingはメモリの容量作成を頻繁に行うためである。
将来のOLTPエンジンについての議論
- Concurrency Control
- Multi-core Support
- Replication Management
- 多くのDBMSではレプリケーションはログを創出することによるactive-passiveスキーマになっているが、これはいくつかの点で欠点があrう
- 2フェーズコミットが行われていないとリモートとプライマリで一貫性が保てていない
- フェイルオーバが即座に出来ない
- ログの可用性を短波する必要があり、今回の実験では20%の処理分に相当する
- これらはリモートでのトランザクションの実行よりもログを送るほうが高速であるという前提に基づいているが、メモリ上で行うことを前提とすればその限りではない。
- そのため、全てのレプリカをactiveな状態にし、同時にトランザクションを実行することで、可用性を担保し、瞬時のフェイルオーバが可能になる構成ができる。このためには2フェーズコミットをする必要があるが、それは第二の大きなレイテンシとなりうるので、おそらくタイムスタンプの順にトランザクションを処理することでこれを回避できるだろう。
- 多くのDBMSではレプリケーションはログを創出することによるactive-passiveスキーマになっているが、これはいくつかの点で欠点があrう
- Weak consistency
- 完全な高可用性を求めるためにWANを超えてレプリケートを行うこともあるが、そのコストを払うよりはこれまで同様に結果整合性(“eventual consistency”)に留めることで十分だろう
- Cache-conscious B-trees
- 今回の実験ではShoreのB-treeを"cache-conscious"フォーマット[RR99,RR00]に変更することはしなかった。こうした最適化を行うことでさらなる高速化wお行うことができるだろう
結論
近年のデータベースシステムにおいてどういった処理で時間を費やしているのかを理解することをモチベーションにShoreのパフォーマンスを測定した。
この結果、修正TPC-Cにおいて20倍の高速化を達成し、バッファマネジメントとロックの操作が最もオーバーヘッドになっていることがわかった。
これらの結果から、個々の要素を取り除くことでは大きなパフォーマンスの改善は見込めないが、ここで述べた全ての処理の要素(ロギング、ロック、ラッチ、btree、バッファマネージャ)をなくすことで非常に大きな性能改善を達成できることがわかった。
感想
HA化の説明があまりされていなくて、クラスタ内の他のノードから復元するとか言っている(recovery is implemented by copying state from other nodes in the network)けど、この辺の具体的な機構については説明がなかった気がする。
ShoreとかしらないからPostgreSQLとかMySQLで実験した結果も見てみたい。
10年の論文なのでここでreferされている論文を更に遡るのはやめた。 (関連研究の項目も完全に飛ばした) ARISEのあたりとかトランザクション処理の知識をちゃんと勉強したことがなくて、PostgreSQLの本で知ったロギング、レプリケーションの仕組みを想像しながら読んでいた。ジム・グレイの本読むのはまたにするとして、ARISEの論文は目を通しても良さそう。
