# OLTP through the looking glass, and what we found there > [!abstract] 概要（abstract 日本語訳） > オンライントランザクション処理（OLTP）データベースには、ディスク常駐 B-tree およびヒープファイル・ロックベースの並行性制御・マルチスレッド対応といった、1970 年代後半のコンピュータ技術に最適化された機能群が含まれている。現代のプロセッサ・メモリ・ネットワークの進歩により、今日のコンピュータは 30 年前とは大きく異なり、多くの OLTP データベースは主記憶に収まるようになり、大部分の OLTP トランザクションはミリ秒以下で処理できる。それにもかかわらず、データベースのアーキテクチャはほとんど変化していない。この観察に基づき、近年のハードウェアの動向を活用して構築できる従来型データベースシステムのいくつかの興味深いバリアントを検討し、TPC-C のサブセットを実行するトランザクション処理データベースシステム（Shore）の主要コンポーネントの詳細な命令レベルの分解を通じて、その性能を推測する。単に Shore をプロファイリングするのではなく、すべての機能除去や最適化の後に（より高速な）動作するシステムが完全にワークロードを実行できるよう、段階的に Shore を改変した。全体として、総性能差約 20 倍を説明するオーバーヘッドと最適化を特定した。また、現代の（メモリ常駐）データベースシステムには単一の「高い杭」が存在するのではなく、ログ記録・ラッチ・ロック・B-tree・バッファ管理操作に相当な時間が費やされていることを示す。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | OLTP through the looking glass, and what we found there | | 著者 | [[Stavros Harizopoulos]]（HP Labs）、[[Daniel J. Abadi]]（Yale University）、[[Samuel Madden]]（MIT）、[[Michael Stonebraker]]（MIT） | | 発表 | SIGMOD 2008（ACM SIGMOD International Conference on Management of Data）、バンクーバー、2008年6月9〜12日 | | DOI | [10.1145/1376616.1376713](https://dl.acm.org/doi/10.1145/1376616.1376713) | | 実装コード | http://db.cs.yale.edu/hstore/ | | 関連先行論文 | [[@2007__VLDB__The End of an Architectural Era (It's Time for a Complete Rewrite)]] | ## 概要 1970 年代設計の RDBMS アーキテクチャが現代のハードウェア環境で抱えるオーバーヘッドを、Shore RDBMS を用いた命令レベルのプロファイリングで定量化した論文である。バッファマネージャ・ロック・ログ・ラッチの 4 コンポーネントを 1 つずつ段階的に除去・計測することで、TPC-C スループットを 20 倍改善し、各コンポーネントの寄与率を精密に特定した。測定結果を踏まえ、並行性制御・マルチコア対応・レプリケーション・弱整合性・キャッシュ最適化 B-tree という 5 つの設計方向を考察する。 ## 問題設定 ### 背景 1970 年代に設計された RDBMS の標準機能群（ディスクベース B-tree・ヒープファイル・2 相ロック・WAL・バッファマネージャ）は、当時のハードウェア制約（主記憶は小さく・ディスク I/O がボトルネック・計算コストが高い）に最適化されている。しかし現代では: - 数 GB の主記憶を備えた数千ドルのサーバが容易に入手でき、多くの OLTP データベースは主記憶に収まる - 数百 GB の集約主記憶を持つコモディティ PC クラスタが利用できる - OLTP トランザクションの計算時間はマイクロ秒オーダーに短縮された - ビジネスが OLTP とデータウェアハウスに分化し、長時間分析クエリは OLTP 以外で処理されるようになった ### 代替アーキテクチャの可能性 本論文は以下の代替アーキテクチャを定量的に評価する枠組みを提供する: - **ログレスアーキテクチャ**: 他サイトへの複製によりリカバリを代替する - **単一スレッドアーキテクチャ**: ディスク待機がなく短命トランザクションのみなら、マルチスレッドの必要性がない - **トランザクションレスアーキテクチャ**: 結果整合性のみでよいアプリケーション向け ### 先行研究との関係 [[@2007__VLDB__The End of an Architectural Era (It's Time for a Complete Rewrite)]] の著者グループと重複しており、本論文はそこで前提とされた Shore の性能測定を詳細に公開したものである。2007 年論文が H-Store アーキテクチャの提案を主目的とするのに対し、本論文は測定方法論と定量的内訳の厳密な提示を主目的とする。 ## 提案手法（方法論） ### Shore RDBMS の概要 Shore（Scalable Heterogeneous Object Repository）は University of Wisconsin が 1990 年代初頭に開発した永続オブジェクトシステムである。本論文では Shore Storage Manager（SSM 5.0、2007 年時点の Linux x86 版）を対象とする。構成は以下のとおり（Figure 2 参照）: - **トランザクションマネージャ**: BEGIN/COMMIT/ABORT の管理 - **ロックマネージャ**: 2 相ロック（レコード→ページ→ストア→ボリュームの階層ロック）、デッドロック検出なし（アプリ側でデッドロック回避を保証） - **ログマネージャ**: WAL（Write-Ahead Logging）。LSN（ログシーケンス番号）でページとログを関連付け - **バッファマネージャ**: ページを fix/unpin メソッドで管理。ラッチで fix メソッドへのアクセスを保護 - **ラッチ**: B-tree ノード・バッファプールのメタデータ等の共有データ構造を保護する軽量ミューテックス Shore はユーザレベルのノンプリエンプティブスレッドを使用するため、マルチコアを直接活用できない。そのため本論文の実験はすべて**シングルスレッド動作**で行い、マルチスレッドのオーバーヘッドは含まない。 ### 段階的改変の順序 4 コンポーネントの除去順序はコードの依存関係で制約される。実際の除去順は以下のとおり（Table 1 参照）: 1. ロギングの除去（3 段階: ディスク I/O 停止 → ログレコード生成停止 → LSN 処理停止） 2. ロックの除去（ロックマネージャのメソッドを即時成功返却に置換） 3. ラッチの除去（ミューテックスを即時成功返却に置換、B-tree メソッドをラッチなし版に書き換え） 4. バッファマネージャ呼び出しの除去（新規レコードを malloc で直接確保。ページインターフェースは薄い層として残存） 追加の任意最適化（除去の順序に依存しない）: - B-tree キー評価ロジックの手動最適化（整数キーの共通ケースを特化） - ディレクトリルックアップのキャッシュ化 - ページサイズを 8KB から 32KB に拡大（B-tree 深さを削減） - トランザクション管理のセッション統合（BEGIN/COMMIT のオーバーヘッド削減） ### 計測方法 - **主指標**: CPU 命令数（PAPI ライブラリで CPU パフォーマンスカウンタを取得） - 命令数は総実行コードパス長を代表し、ディスク I/O の有無に依存しない決定論的な指標である - **補助指標**: CPU サイクル数（マイクロアーキテクチャの効率差を反映） - Shore への呼び出しごとに計測し、40,000 トランザクションの平均を報告 ## 新規性 - **コンポーネント単位の段階的分解**: 従来の性能研究は完全な DBMS をプロファイリングするか、完全な代替システムと比較するかのどちらかだった。本論文は毎ステップ動作する改変済み Shore を維持しながら個別コンポーネントを除去し、各コンポーネントの寄与を正確に切り出した - **命令レベルの定量的内訳**: バッファマネージャが最大の寄与因子だが、単一の支配的ボトルネックが存在しないこと（「no single high pole in the tent」）を命令数の観点から初めて厳密に示した - **「単一除去では不十分」の定量化**: バッファマネージャのみ除去で約 30% 改善、ロックのみ除去で約 25% 改善と、個別除去の効果が限定的であることを実測した。20 倍の改善には全コンポーネントの同時除去が必要 - **サイクル数と命令数の乖離の分析**: ログ記録はサイクル数比率が命令数比率より大きく（メモリアクセス多発）、B-tree 最適化は逆にサイクル数削減が命令数削減より小さいことを示した（Figure 8） ## 実験設定 - **ハードウェア**: Intel Pentium 4 シングルコア 3.2GHz、L2 キャッシュ 1MB、ハイパースレッディング無効、RAM 1GB、Linux 2.6、gcc 3.4.4 -O2 - **データベース**: Shore SSM 5.0、データベース全体を主記憶にプリロード（ディスクフラッシュなし） - **ワークロード**: TPC-C の 2 トランザクション（New Order + Payment の 50-50 ミックス）。倉庫数 5、データベースサイズ約 500MB（1 倉庫 = 約 100MB） - **測定規模**: 40,000 トランザクション実行の平均値を報告 - **比較対象**: 「最適カーネル」—手作りのメモリ常駐 B-tree パッケージ上に構築した最小オーバーヘッドカーネル TPC-C の変更点（再現性確保のため）: - New Order の品目数を常に 10 に固定（元は 5〜15 のランダム） - 常にローカル倉庫から供給（元は 10% がリモート倉庫からのアクセス） - Payment は常に顧客 ID でルックアップ（元はランダムで名前/ID） ## 実験結果 ### スループット改善（Section 4.3.1） | 状態 | TPS | 備考 | |---|---|---| | 元 Shore（ログあり・DB メモリ常駐） | 640 | ディスクへのログ書き込みあり | | Shore（ログフラッシュなし・DB メモリ常駐） | 1,700 | ログバッファサイズを拡大して書き込み抑制 | | 全コンポーネント除去後の Shore カーネル | 12,700 | 約 80 µs/トランザクション | | 最適カーネル（手作り B-tree・最小オーバーヘッド） | 46,500 | 約 22 µs/トランザクション | 元 Shore → 全除去後で**約 20 倍**の改善。Shore カーネルと最適カーネルの差（約 3.7 倍）は Shore のコールスタック深さと残存するトランザクション管理・バッファプール呼び出しに起因する。 ### Payment トランザクションの命令数内訳（Figure 5） Payment は begin→3 × Btree ルックアップ→3 × pin/unpin→3 × レコード更新→1 × レコード生成→commit で構成（合計約 180K 命令）: | コンポーネント | 命令数の削減率 | 主な影響操作 | |---|---|---| | Btree キー評価最適化 | 10.1% | Btree ルックアップ全体 | | ロギング除去 | 17.7% | commit・update（ログレコード生成箇所） | | ロック除去 | 25.2% | pin/unpin・ルックアップ・commit（ロック取得・解放箇所） | | ラッチ除去 | 12.6% | create record・Btree ルックアップ（共有データ構造へのアクセス箇所） | | バッファマネージャ除去 | 29.8% | create record・Btree ルックアップ・update（全体に広範な影響） | | 残余オーバーヘッド | 4.7% | Shore のコールスタック深さ等 | 全 6 コンポーネントがそれぞれ 18,000 命令以上を占め、単一の支配的ボトルネックは存在しない。 ### New Order トランザクションの命令数内訳（Figure 6・Figure 7） New Order は Payment の約 10 倍の命令数（約 1.73M 命令）。13 × Btree 挿入・12 × レコード生成・11 × レコード更新・23 × pin/unpin・23 × Btree ルックアップで構成: | コンポーネント | 命令数の削減率 | |---|---| | Btree キー評価最適化 | 16.2% | | ロギング除去 | 11.9% | | ロック除去 | 16.3% | | ラッチ除去 | 14.2% | | バッファマネージャ除去 | 34.6% | | 残余オーバーヘッド | 6.8% | Payment と比べると、Btree 挿入が多いため Btree 最適化の効果が相対的に大きい。バッファマネージャの寄与は依然として最大で、ページサイズを 8KB から 32KB に拡大するだけで約 14% の命令削減が得られることも判明した（B-tree 深さ削減・ページ確保頻度低下による）。 ### 命令数とサイクル数の比較（Figure 8） New Order でのサイクル比 vs 命令比の主な乖離: - **ログ記録**: サイクル比 > 命令比（ログレコード生成でメモリを多数触るためキャッシュミスが発生） - **B-tree 最適化**: サイクル比 < 命令比（除去するコードは主にオフセット計算でキャッシュミスが少ない） - **残余カーネル**: サイクル比 > 命令比（関数呼び出しが多くパイプライン的に重い） - **ロック・バッファマネージャ**: サイクル比 ≈ 命令比 ## 考察（将来の OLTP エンジンへの示唆） ### 並行性制御（Section 5.1） 動的ロック（2 相ロック）がサイクルの約 19% を占める。主記憶常駐ワークロードでは 1980 年代のシミュレーション研究（ディスクストール前提）は不適切であり、楽観的並行性制御が支配的な選択肢になる可能性がある。アプリケーションの可換性やトランザクション 1 件ずつの実行で並行性制御を無効化できるシナリオでは大きな利得がある。 ### マルチコア対応（Section 5.2） ラッチがサイクルの約 10% を占め、マルチスレッド化には障壁となる。選択肢は 3 つ: 1. トランザクショナルメモリ技術の成熟を待つ 2. OS/DBMS レベルの仮想化で各コアを単一スレッドマシンとして見せる 3. クエリ内並列性を活用（OLTP トランザクションでは限定的） ### レプリケーション管理（Section 5.3） 従来のアクティブ-パッシブ方式（ログシッピング）は: (1) レプリカへのトランザクション整合性読み出しが困難、(2) フェイルオーバが即時でない、(3) ログ維持コストが約 20% のサイクルを消費、という 3 つの欠点がある。主記憶 DBMS ではトランザクション実行が 1 ミリ秒以下になるため、ログを転送してロールフォワードするコストとトランザクションロジックを直接実行するコストが拮抗し、アクティブ-アクティブ方式が合理的になる可能性がある。 ### 弱整合性（Section 5.4） 結果整合性（eventual consistency）は一般ワークロードでは不整合の伝播リスクがあるが、特定のワークロード（書き込みが可換・読み取り後書き込みの依存がない等）では成立しうる。ロックとログを除去したメモリ常駐システムは非常に高性能になりうる。 ### キャッシュ最適化 B-tree（Section 5.5） 他のコンポーネントが残っている状態では、B-tree のキャッシュ最適化は副次的な効果しかない。すべてのコンポーネントを除去した最小カーネルになって初めて、B-tree のキャッシュミスが次のボトルネックになりうる。また、ハッシュテーブルなど他の索引構造がこの環境では B-tree より優れる可能性がある。 ## 強み - Shore の実際のコードを改変して毎ステップ動作するシステムを維持するアプローチは、他の DBMS との比較より信頼性が高い（実装差による偽のボトルネックを排除できる） - PAPI による命令数計測は再現性が高く、SIGMOD の再現性評価委員会による検証を受けている - 個別コンポーネントの除去効果と全コンポーネント除去の組み合わせ効果を、同一システム上で連続的に計測した点が稀少 ## 弱点・課題 - 実験がシングルコア Pentium 4（2008 年時点でもすでに旧式）で行われており、マルチコア・マルチソケットの効果を評価していない - TPC-C のうち New Order と Payment の 2 種のみを対象とし、Delivery・Order-Status・Stock-Level（I/O が少なく分析的な傾向が強い）を除外している - Shore はラッチコードとスレッドコードが密結合であるため、ラッチ除去のコストが他のコンポーネントと分離しにくい - 最適カーネルは Shore とは別物であり、Shore の「stripped down 版」として連続的に計測できていない（約 4 倍の残余差の説明が不完全） - 2008 年時点でクラウドコンピューティングは論考の対象外 ## 関連 - [[@2007__VLDB__The End of an Architectural Era (It's Time for a Complete Rewrite)]] — 同著者グループによる、本論文の測定に基づく H-Store アーキテクチャ提案論文 - [[OLTPシステムアーキテクチャ]] — 本論文が分解・定量化した OLTP コンポーネント群の概念ページ - [[メインメモリデータベース]] — 本論文が想定する主記憶常駐 DBMS の概念ページ - [[結果整合性]] — Section 5.4 で言及される弱整合性の選択肢 - [[Michael Stonebraker]] — 共著者（MIT CSAIL） - [[Samuel Madden]] — 共著者（MIT CSAIL） - [[Daniel J. Abadi]] — 共著者（Yale University） - [[Stavros Harizopoulos]] — 筆頭著者（HP Labs） ## 出典 - [OLTP through the looking glass, and what we found there](https://dl.acm.org/doi/10.1145/1376616.1376713), SIGMOD 2008