> [!abstract] 概要(abstract 日本語訳) > 細粒度のレコード指向書き込み前ロギング(ARIES に代表されるもの)は、リレーショナルデータベースの復旧における金字塔とされてきた。本論文では、現代の高スループットトランザクション処理システムにおいて、これがもはやデータベースシステムの最適な復旧方式ではないことを示す。特に、トランザクションスループットが高くなるにつれて、ARIES 方式のロギングが全体的なトランザクション実行時間の中で無視できない割合を占めるようになる。 > > 我々は、データベース上で実行されたトランザクションのみを記録するより軽量で粗粒度なコマンドロギング手法を提案する。この手法はトランザクション整合性のあるチェックポイントから開始し、コマンドログ内のコマンドをまるで新規トランザクションであるかのように再実行することで復旧を行う。細粒度なビフォアイメージ・アフタイメージのロギングオーバーヘッド(CPU の複雑さと大量の I/O の両方)を回避することで、コマンドロギングは実行時に大幅に高いスループットを達成できる。コマンドロギングの復旧時間は ARIES 方式の生理ロギングより長いが、高可用性技術の登場により復旧ノードの停止をマスクできるため、ほとんどのアプリケーションでは復旧速度よりも実行時性能が重要になっている。 > > 我々はメインメモリデータベースシステム(VoltDB)上に TPC-C を実装して提案手法を評価し、コマンドロギングが ARIES 方式の生理ロギングのメインメモリ最適化実装より 1.5× 高いスループットを提供できることを発見した。 ## 論文情報 - **タイトル**: Rethinking Main Memory OLTP Recovery - **著者**: Nirmesh Malviya([[MIT CSAIL]])、Ariel Weisberg([[VoltDB]] Inc.)、Samuel Madden([[MIT CSAIL]])、Michael Stonebraker([[MIT CSAIL]]) - **発表媒体**: IEEE ICDE 2014(International Conference on Data Engineering) - **DOI**: 10.1109/ICDE.2014.6816685 - **URL**: https://ieeexplore.ieee.org/document/6816685 ## 概要 本論文は、メインメモリ OLTP データベースにおける復旧(リカバリ)方式として、ARIES 生理ロギングとコマンドロギングを詳細に比較した実験論文である。実装基盤は [[VoltDB]](H-Store ベースのオープンソースメインメモリ DBMS)で、TPC-C と Voter の 2 ベンチマークを用いて実行時スループット・レイテンシ・ログサイズ・復旧時間を網羅的に測定した。結論として、高スループット OLTP ではコマンドロギングが復旧方式の第一選択であると主張する。 ## 問題設定 **入力**: メインメモリ OLTP データベース(VoltDB)における復旧サブシステムの設計選択肢。 **問い**: 高スループットトランザクション処理(コアあたり 4,000 TPS 超)の環境では、ARIES 生理ロギングとコマンドロギングのいずれが適切か。 **前提条件**: - トランザクションはストアドプロシージャとして事前登録・コンパイルされている - データベースはメインメモリ常駐(インデックスも含む) - トランザクションの実行はパーティション単位で逐次実行(単一スレッド、ロック不要) - 高可用性のためにレプリケーションが利用可能 Shore への段階的除去でロギングが 10–20% のオーバーヘッドを占めることを先行研究([[@2008__SIGMOD__OLTP through the looking glass, and what we found there]])が示しており、スループット向上とともにこの割合が増大することが本研究の動機となっている。 ## 提案手法 ### VoltDB のアーキテクチャ(実装基盤) VoltDB は [[H-Store]] の設計を継承したオープンソースのメインメモリ分散データベースである。テーブルは主キーで水平パーティショニングされ、各パーティションはクラスタノードのメインメモリに常駐する。高可用性のために複数ノードにレプリケーション可能。 実行サイト(execution site)は CPU コアごとに 1 つ設けられ、各パーティションは 1 サイトに割り当てられる。トランザクションはストアドプロシージャとして実行され、各サイトはトランザクションを逐次実行(ロック不要)。グローバルなトランザクション順序はイニシエーターが生成するタイムスタンプベースのトランザクション ID と優先度キューで保証される。 チェックポイントは VoltDB のコピーオンライト(COW)機構によりノンブロッキング・トランザクション整合性のある方式で実施される。スナップショット処理中もトランザクションは継続実行される(追加行はスキップ、削除行はスキャン後に除去、更新行はシャドウテーブルにコピーしてからスナップショットが旧バージョンを読む)。 ### コマンドロギング(提案手法) コマンドロギングは**論理ロギングの極端な形態**であり、物理ロギングおよびレコードレベルの論理ロギングとは異なる。 **ログレコード構造**(Figure 1 より): ``` [check-sum | LSN | record-type | xaction-id | partition-id | xaction-type | params] ``` **書き込み動作**: - シングルパーティショントランザクション: 担当実行サイトが直接ログに書き込む - 分散トランザクション: コーディネータサイト(最低 ID のサイト)のみがログに書き込み、他のサイトは書き込まない - レプリカがある場合: 全レプリカサイトにもトランザクションをログに記録する - イニシエーターのトランザクション順序付けメッセージもログに記録される **同期モードのみ使用**: ACID セマンティクスを保証するために、ログレコードはトランザクションコミット確認前にディスクへ同期書き込みする。 **グループコミット最適化**: 複数トランザクションのログレコードをバッチにまとめてフラッシュし、トランザクションあたりの書き込みコストを削減する(若干のレイテンシ増加と引き換え)。 **非決定的関数への対応**: `date()`・`time()` などの非決定的関数には、タイムスタンプベースのトランザクション ID をシードとして使用し、再実行時の再現性を保証する。 **復旧手順**: 1. ディスク上の最新スナップショットからデータベースをメモリに復元する 2. インデックスをスナップショット復元と並行して再構築する(高速化のため) 3. 共有コマンドログを専用スレッドがチャンクで読み込む 4. スナップショットに反映されていない最初のトランザクションから順に、イニシエーターがトランザクションを対応サイトへディスパッチし、実行サイトで再実行する 5. ログの順序付けメッセージも再実行時にリプレイし、グローバル順序を復元する 復旧は実行サイト数が変化しても対応可能(パーティション数が同じであれば)。 ### ARIES 方式生理ロギング(比較対象) **メインメモリ向け適応**(Figure 2 ログレコード構造): ``` [Record-type | Insert/Update/Delete | Transaction-id | Modified Column List] ``` ディスク版 ARIES との主な差異: - ページ番号・スロット番号による (page#, slot#) RID に代わり、**(table-id, primary-key)** ペアでタプルを識別する - バッファプールが存在しないため、ダーティページテーブルは廃止し、タプルごとのダーティビットで代替する(ただし本実装ではトランザクション整合チェックポイントを採用するためダーティビットも不要) - 仮想メモリアドレスでのタプル識別は再起動時のアドレス不一致のリスクがあり採用しない **最適化群**: - **差分ロギング(Differential Logging)**: 幅広行のテーブルで、変更された列のみビフォア・アフタイメージを記録する。TPC-C では約 5× のログレコードサイズ削減を達成したが、差分ログレコード構築の CPU オーバーヘッドが増加する - **ダーティページ追跡**: トランザクション整合チェックポイントを使用するため、ダーティレコードテーブルは不要 - **ノードごとの共有ログ**: 同一ノードの全実行サイトが共有ログに書き込む(サイト別ログでなく)。これにより復旧時のパーティション-サイトマッピング変更への対応を容易にする - **バッチ書き込み**: 1 トランザクションの全ログレコードをバッファリングしてコミット時にまとめて書き込む - **グループコミット**: コマンドロギングと同一頻度でグループコミットを実施 **復旧手順**: 1. 分析フェーズ: ログリプレイ開始 LSN を特定する 2. Redo フェーズ: 該当 LSN 以降の全ログエントリを順番に再適用する。(table-name, primary-key) でタプルを識別し、シリアライズされたアフタイメージを使って修正する。ログレコードはパーティション間の順序無制限で再適用可能であるため**高度に並列化可能**で、コア数に比例してリニアスケールアップを達成する 3. Undo フェーズ: トランザクション整合チェックポイントを使用するため、クラッシュ時点で未コミットのトランザクションはクラッシュ前のディスク上に存在しない。よって各パーティションでクラッシュ時に実行中だったトランザクション(パーティションあたり最大 1 つ)を Undo するだけでよい。さらにログ末尾のそのトランザクションをリプレイしないことで Undo を回避でき、ログレコードサイズを約 2 分の 1 に削減できる(ビフォアイメージが不要になるため) ## 新規性 **既存手法の課題**: - ARIES 生理ロギングは 1990 年代のディスクベース DBMS 向けに設計されており、ディスクアクセスが支配的なオーバーヘッドの文脈では適切だった - 高スループットメインメモリ OLTP では、1 トランザクションあたりの実際の処理時間が非常に短く(数十〜数百マイクロ秒)、生理ロギングのオーバーヘッド割合が相対的に拡大する - Shore での測定([[@2008__SIGMOD__OLTP through the looking glass, and what we found there]])では、数百 TPS レベルでも 10–20% のオーバーヘッドが確認されており、数千 TPS では比率がさらに大きくなる **本研究の貢献**: - メインメモリ OLTP におけるコマンドロギングと ARIES 生理ロギングを初めて詳細に比較した実験的研究 - コマンドロギングのパフォーマンス差が I/O 量だけでなく CPU コスト(差分ログレコード生成)にも起因することを実証した - ログサイズを人工的に削減した制御実験(TPC-C で生理ロギングの 1%)により、CPU コストが支配的な要因であることを確認した ## 実験設定 **ハードウェア(シングルノード実験)**: - サーバ: Intel Xeon デュアルソケット 2.4GHz 8 コア - メモリ: 24GB RAM - ストレージ: 12TB ハードディスク(バッテリーバックキャッシュ付き) - OS: Ubuntu Server - クライアント: 同一仕様の別マシン(非同期クライアントでリクエスト送信) **ハードウェア(分散トランザクション実験)**: - クラスタ: 4 ノード(1 クライアント + 3 サーバ) - 各ノード: Intel Xeon デュアルソケット 12 コア 2.4GHz、48GB RAM、4TB HDD(バッテリーバック)、Ubuntu Server **実装**: - コマンドロギングと生理ロギングの両方を VoltDB にグループコミット付きで実装 - 同期ロギング(ACID 保証のため fsync 実施) - スナップショット頻度: 180 秒 **ベンチマーク**: - **Voter**: 投票シミュレーション。スキーマ 3 テーブル(contestants・area_code_state・votes)、行幅 20 バイト未満。唯一のトランザクション(`vote`)は votes テーブルへの 1 行インサート。シングルパーティション・非常に単純なトランザクション - **TPC-C**: 9 テーブル(Customer, District, History, Item, New-Order, Order, Order-Line, Stock, Warehouse)、3〜21 列幅、外部キー関係あり。5 種トランザクション(New-Order, Payment, Delivery, Order-Status, Stock-Level)のうち New-Order・Payment・Delivery のみ書き込みを行う。8 ウェアハウス構成(コアあたり 1 ウェアハウス) **実行サイト数**: - Voter: 8 コアマシンで最適 6 サイト - TPC-C: 8 ウェアハウス = 8 サイト(コアあたり 1) ## 実験結果 ### スループット(実行時) **Voter ベンチマーク**(Figure 3): - コマンドロギングと無ロギングは 95K TPS まで飽和しない - 生理ロギングは 80K TPS で飽和(ほぼ同一スループット) - コマンドロギングの最大スループット: 約 95K TPS - 生理ロギングの最大スループット: 約 80K TPS - オーバーヘッド差: Voter では約 1.2× 差(生理ロギングが 15% 低下) **TPC-C ベンチマーク**(Figure 6): - コマンドロギングは無ロギングとほぼ同一スループット - 生理ロギングは他の 2 方式の約 66% のスループット - **コマンドロギングは生理ロギングより約 1.5× 高いスループットを達成する** - 最大値: コマンドロギング約 2M tpmC、生理ロギング約 1.5M tpmC ### レイテンシ **Voter**(Figure 4): 飽和前の 50K TPS 未満では全方式 5–7ms。コマンドロギングは無ロギングとほぼ同一レイテンシ。生理ロギングは 15% 高いレイテンシ。 **TPC-C**(Figure 7): 生理ロギングは約 21K TPS で飽和に達し、全クライアントレートで 45% 以上高いレイテンシを示す。コマンドロギングと無ロギングは 30K TPS 超まで飽和しない。 ### ログサイズ(1 トランザクションあたり) **Voter**: - コマンドロギング: 常に 55 バイト(ストアドプロシージャ名+パラメータ+ヘッダ) - 生理ロギング: 81 バイト(挿入行のアフタイメージ+ヘッダ) **TPC-C**: - コマンドロギング: 50〜170 バイト(Delivery 50、New-Order 170) - 生理ロギング: 70〜240 バイト/レコード(New-Order テーブル 70、Customer テーブル 240) - **TPC-C では生理ロギングがコマンドロギングの約 10× のデータを書き込む**(3 トランザクション種別の平均) ### パフォーマンス差の要因分析(Figure 5 vs Figure 6) TPC-C で生理ロギングのログレコードを人工的に 100 バイトに切り詰めた実験(コマンドロギングの平均に相当、復旧不可能なログ)を実施した結果: - 生理ロギングのスループットはわずか **1% しか改善しない** - したがって**パフォーマンス差はディスク I/O 量だけでなく、差分ログレコード構築の CPU オーバーヘッドにも起因する** CPU オーバーヘッドは、高スループット環境でトランザクション 1 件あたりの実際の処理が数十〜数百マイクロ秒と短くなるとき、相対的に顕著になる。 ### 復旧時間 **Voter**(Figure 5): - コマンドロギング: 約 100K TPS(最大実行時スループットと同等) - 生理ロギング: 約 500K TPS(コマンドロギングの **約 5× 高速**) - 生理ロギングは各トランザクションの変更内容を直接記録するため、読み戻し時はトランザクションロジックを再実行する必要がない **TPC-C**(Figure 8): - コマンドロギング: 約 865K tpmC - 生理ロギング: 約 1.5× 高速(TPC-C の複雑なトランザクションのため差がVoterより縮小) **ログ読み込みオーバーヘッド**: - コマンドロギング: リプレイ時間の 1% 未満(小さなログレコードと相対的に長いリプレイ時間のため) - 生理ロギング: Voter では 30%、TPC-C では 8%(大きなログレコードと速い再実行のため) ### 分散トランザクション実験(Figures 9, 10) TPC-C New-Order でのみ分散トランザクション比率を変化させた実験: **シングルノード・マルチサイト(Figure 9)**: - 0% 分散: コマンドロギング約 2M tpmC、生理ロギング約 1.5M tpmC(1.5× 差) - 50% 分散: 約 1.4× 差まで縮小 - 100% 分散: 3 方式がほぼ同一スループット **3 ウェイレプリケーション・4 ノードクラスタ(Figure 10)**: - 0% 分散: コマンドロギングが約 2× 差(生理ロギング比) - 5% 分散: 1.2× 差に縮小 - 10% 超: 3 方式がほぼ同一 レプリカありの方が分散トランザクションなしの場合でも全トランザクションがマルチサイトになるため、差が閉じる速度が速い。 ## 考察 **コマンドロギングが優位な条件**(Figure 11): - トランザクションが単純(シングルサイト・少数テーブル更新) - コマンドログレコードが小さい(ストアドプロシージャ名+パラメータが小さい) - 1 トランザクションが多数のタプルを更新する(生理ロギングのログ量が増大する) **生理ロギングが優位な条件**: - 分散トランザクション比率が高い(トランザクション長が伸びてロギングが全体に占める割合が低下) - 複雑なトランザクション(長時間実行される場合) - 復旧速度が最優先の場合(SLA が厳格など) **ARIES が過去の金字塔だった理由**: 1980 年代の OLTP スループットは 1 コアあたり数百 TPS 程度で、生理ロギングのオーバーヘッドは相対的に小さかった。現代のメインメモリ OLTP で 4,000 TPS/コア 超を達成すると状況が逆転する。 **高可用性による復旧速度の重要性低下**: 本番 OLTP は通常レプリケーションを用いており、単一ノードの障害は生きているレプリカでサービス継続できる。よって復旧速度よりも実行時パフォーマンスが重要である。 ## 一般化の可能性(セクション VI) コマンドロギングを他のシステムへ適用するために必要な 2 要件: 1. **トランザクション整合性のある出発点**: 復旧はトランザクション整合スナップショットから開始する必要がある。ディスクベース DB では MVCC を使ったリードオンリートランザクションによるスナップショットが実現可能(ただし 2 コピー必要) 2. **シリアル等価なリプレイ順序**: コマンドログのトランザクションをコミット直列順で再実行すると元の実行と等価になる必要がある。S2PL(Strict 2PL)のシステムでは保証される。SSI(Serializable Snapshot Isolation)では保証されない場合がある ## 強み / 弱点・課題 ### 強み - 実装が単純: ログレコードがストアドプロシージャ名とパラメータのみ - 実行時オーバーヘッドがほぼゼロ(コマンドロギングと無ロギングが同等スループット) - ログレコードが小さいため I/O 量も少なく、ディスク書き込みのボトルネックになりにくい - 復旧時のパーティション-サイトマッピング変更に対応可能(実行サイト数が変化しても復旧できる) - VoltDB の既存チェックポイント機構と自然に統合できる ### 弱点・課題 - 復旧時間がトランザクション再実行に依存するため、生理ロギングより 1.5×〜5× 長くなる - ディスクベース DB への適用には「トランザクション整合スナップショット」の確保が難しい(クラッシュ中の部分書き込み問題) - 非ストアドプロシージャ型(アドホック SQL)のシステムへの適用には、SQL クエリをログに書くことが必要で、レコードサイズが増大する - SSI や SI(Snapshot Isolation)など ACID 保証の弱いアイソレーションモデルでは復旧の正確性保証が難しい - 分散トランザクション比率が高いワークロードでは優位性が消失する - VoltDB 実装はストアドプロシージャ専用であるため、一般の DB への適用では実装上の工夫が必要 ## 関連 - [[コマンドロギング]] — 本論文が詳細実装・評価した復旧手法 - [[Write-Ahead Logging (WAL)]] — コマンドロギングも WAL の一形態 - [[ARIES]] — 比較対象の生理ロギング方式 - [[メインメモリデータベース]] — 本論文の応用ドメイン - [[チェックポイント]] — コマンドロギングの出発点として必須 - [[クラッシュリカバリ]] — 本論文の中心テーマ - [[VoltDB]] — 実装・評価基盤 - [[H-Store]] — VoltDB の前身設計 - [[OLTPシステムアーキテクチャ]] — ARIES オーバーヘッドの議論と関連 - [[@2008__SIGMOD__OLTP through the looking glass, and what we found there]] — Shore でのロギングオーバーヘッド定量化の先行研究 ## 出典 - PDF 原本: `.raw/papers/Malviya-et-al.-2014---Rethinking-main-memory-OLTP-recovery.pdf` - 発表: IEEE ICDE 2014、DOI:10.1109/ICDE.2014.6816685