Fast Databases with Fast Durability and Recovery Through Multicore Parallelism (SiloR)

OSDI 2014（2014） · 論文 · zheng2014silor

📅 この論文を見た日

初回 2026-09-22 ／ 最終 2026-09-22 ／ 計 1 回更新

少 多

AI解説

実装: SiloR（Silo データベースの上に構築）。https://github.com/stephentu/silo（Silo 本体、著者による公開実装） 情報源: OSDI 2014 論文本文（全14頁、付録含む）を精読して記述。本文に書かれていない事項は書いていない。

一言で

マルチコアのインメモリデータベース Silo に、ロギング・チェックポイント・リカバリを追加した SiloR。ログ生成、チェックポイント生成、リカバリのすべてでマルチコア並列性を徹底的に活用し、通常実行のスループットをほとんど落とさずに、43.2GBのキーバリューデータベースを106秒、70GB超のTPC-Cデータベースを211秒で復旧できることを示す。

背景・問題

現代のマルチコア・インメモリデータベースは1秒あたり数百万から数千万件のトランザクションを処理できるが、クラッシュや電源障害からの頑健性が弱点になりうる。レプリケーションはある拠点を別の拠点で代替させられるが、相関障害（複数拠点が同時に影響を受ける障害）に耐えるにはレプリケートされたデータベースでも永続ストレージへの書き込みが必要であり、永続化と復旧の両方の性能が問題になる。

ロギングやチェックポイントのような耐障害機構は、素朴に実装すると実行を大きく遅くする。1秒あたり数千万件の小さなトランザクションをさばく高速なインメモリデータベースは、値かオペレーションのいずれをログしても毎分50GBを超えるログデータを生成しうる。これはトランザクションレートとログサイズの両面で、それまでのインメモリデータベース永続化研究で報告された値より数桁大きい。ログをディスクやフラッシュへ書くこと自体はログ書き込みが逐次的なので理論上は速いが、逐次的なログ再生は現代のマルチコアマシンでは速くない。チェックポイントも、ログを無限に伸ばさないために必要だが、データベース全体を走査する必要があり、データ移動とキャッシュ汚染によって並行するトランザクション性能を落としうる。単一コアでの数ギガバイト規模のデータベース復旧は90分を超えることがあり、レプリケートされたシステムでもこれは長い。

著者らの目標は、トランザクションスループットへの犠牲を比較的低く抑えた完全な永続性を持ち、かつレプリケーションなしで数分以内にトランザクション一貫性のある状態へ復旧できるインメモリデータベースを作ることだった。

提案手法

Silo のエポック機構

Silo は楽観的並行性制御（OCC）の一種を使い、トランザクションID（TID）を中心に直列化する。古典的な OCC はコミットするトランザクションの TID を大域カウンタのインクリメントで得るが、現代のマルチコアハードウェアでは大域カウンタが性能を制約する競合の原因になりうる。Silo はこの競合を、TID に埋め込まれたエポックという時間区間で解消する。大域エポック番号 E は全スレッドから見え、指定されたスレッドが40ミリ秒ごとにこれを進める。新しい TID は、(a) read-set 内のどの TID よりも大きく、(b) そのワーカーが最後にコミットした TID よりも大きく、(c) エポック E に属する、という条件で決まる。

ここで根本的な問題が生じる。並行するトランザクション T1、T2 で T1 が読んだキーを T2 が後で上書きする場合（反依存、anti-dependency）、T1 は T2 より前に順序付けられねばならないが、Silo の TID にはこの依存を伝える通信が一切なく、TID(T1) > TID(T2) となりうる。つまり TID 順にコミット済みトランザクションを再生すると、間違ったデータベース状態を復旧しかねない。エポックはこの正しい再生の鍵になる。x86-64 のような TSO（total-store-order）アーキテクチャでは、指定スレッドによる E の更新は全ワーカーに同時に見えるため、ワーカーが直列化点でエポックを読む限り、異なるエポックを持つ TID の順序は常に直列順序と両立する。エポックはさらに一種のグループコミットを提供し、SiloR はエポック単位で永続化と復旧を行う。

ロギング — value logging と epoch ベースの group commit

SiloR ではトランザクションを実行するワーカーと、ロギング・チェックポイント・その他の維持作業だけを担うロガースレッドとに責任が分かれる。ワーカーはコミット時にログレコード（コミットした TID と、そのトランザクションが変更した全レコードのテーブル・キー・値情報）を生成し、専用バッファプールから取ったメモリバッファへディスク形式で格納する。バッファが満杯になるかエポック境界に達すると、ワーカーは共有メモリキュー経由でそのバッファをロガーへ渡す。

SiloR はvalue logging（オペレーションログではなく値そのものをログする）を選ぶ。これは復旧の並列性を優先した設計判断である。value logging は並列に再生しやすい——同じキーへの複数の変更があっても、最大の TID を持つエントリだけが勝てばよい。これは TID が依存関係（書き込みの順序）を反映しており、かつエポック単位で復旧するため反依存が問題にならないために成り立つ。対照的にオペレーションログは、元の直列順序で再生する必要があり並列化しにくいうえ、反依存を守るために read-set（キーとTID）までログする必要が生じる。

ワーカーは1つのロガーへ、ロガーは1つのディスクへという構成を取り、コア・ピニングでロガーとそのワーカー群が同じソケット上で動くようにすることでリモートメモリアクセスを避ける。ログバッファは512KBで、ロガーはバッファが埋まるかエポックが変わるたびに（どちらか早い方で）ワーカーへ返す。

pepoch — 永続エポックの計算

各ログファイルはどのエポックの記録を含むか以外の追加情報を持たず、複数ロガーが独立に別ディスクへ書くため、単一のログだけでは復旧に十分な情報にならない。そこで専用のロガースレッドが pepoch ファイルへ現在の永続エポックを維持する。この計算は次の手順で行われる。

  1. 各ワーカー w は自分の現在のエポック e_w を公表し、これ以降にロガーへ送る全てのトランザクションのエポックが e_w 以上であることを保証する。ログバッファをロガーへフラッシュした後、e_w ← E に更新する。
  2. 各ロガー l はワーカーからログバッファを読み、ログファイルへ書く。
  3. 各ロガーは定期的に書き込みを永続化することを決め、そのとき自分の担当ワーカー群の e_w の最小値と、まだ書かれていないログバッファのエポック番号の最小値を取り、これをそのロガーの現在のエポック e_l とする。ロガーはその後、全ての書き込みをディスクへ同期する。
  4. この同期が完了すると、ロガーは e_l を公表する。これは、このロガーのワーカー群についてエポック < e_l の全トランザクションが永続化されたことを保証する。
  5. 専用のロガースレッドが定期的に、全ロガーにわたる min{e_l} − 1 として永続エポック e_p を計算し、pepoch ファイルへ書いてディスクへ同期する。
  6. pepoch が永続化されると、専用のロガースレッドは e_p を大域変数へ公表する。この時点で、エポック ≤ e_p の全トランザクションが永続化されたことになり、ワーカーはその結果をクライアントへ返せる。

このプロトコルはグループコミットの一形態を提供するが、トランザクションコミットのクリティカルパスに（ログファイル用とpepoch用の）2回の fsync を含むという欠点があり、レイテンシをいくらか増やす。

チェックポイント — inconsistent（fuzzy）チェックポイント

チェックポイントはチェックポインタスレッドが書き、ディスク1台につき1スレッドを割り当てる。データベースは n 個のディスクの数だけスライスに分割され、各チェックポインタがおよそ 1/n を担当する。OCC はコミット時に変更を反映するため、チェックポインタが見る全てのレコードはコミット済みであり、これはARIES 流の undo ログと redo ログの両方が不要で、ログには引き続き “redo” レコードだけを含めればよいことを意味する。ただし並行するトランザクションはチェックポインタとレコード単位のロック以外で協調しないため、あるトランザクションの複数の変更をチェックポインタが全て見る保証はない。この結果 SiloR のチェックポイントはinconsistent（fuzzy）になる——直列順序上のある一点でのデータベースの一貫したスナップショットとは限らない。一貫したスナップショットへ復旧するには、常にチェックポイントの復元とログの再生の両方が必要になる。

inconsistent チェックポイントを選んだ理由は、一貫したチェックポイントよりメモリ使用の点でコストが低いからである。一貫したチェックポイントを取ろうとすると、書き込みに数十秒かかる間データベース全体が書き換えられうるため、スナップショットを保持するメモリコストと、新しい更新を（上書きではなく）新規に割り当てたレコードへ格納するコストがかかり、通常実行時のスループットを10%程度落とすことが分かった。

重要な最適化として、チェックポインタはエポック ≥ e_l（チェックポイント開始エポック）で現在のエポックを持つレコードをスキップする。inconsistent チェックポイントを e_l から始めた以上、常にログを e_l から再生する必要があるため、その後ログで再生されるレコードをチェックポイントへ書く必要はない。この最適化によりチェックポイントサイズは20%以上削減される。

リカバリ — チェックポイント復元と並列ログ再生

チェックポイントは n × m 個のスレッド（n はディスク数、m はディスクあたりのファイル数）で並列に復元される。各スレッドは1つのディスクから読み、キー・値・TID の三つ組を対応するインデックス木へ挿入する。

チェックポイント復元後、ログ復旧に移る。ログファイルは実行時に整理されておらず、様々なインデックス木への変更が入り混じっているが、value logging はログをどの順序で処理しても同じ結果になるという性質を持つ。あるキーへの複数の変更があっても、最大の TID を持つエントリだけが結果に反映されればよいためである。マネージャスレッドはまず pepoch ファイルを読んで e_p を得て、e_p より後のエポックを持つ記録は無視する（グループコミットが完了していないエポックを処理すると、直列順序の prefix に対応しないデータベースになりかねないため）。各ディスクについて g = ⌈N/n⌉ 個のログプロセッサスレッドを起動し（N はコア数）、まだ処理されていないファイルのうち最新のものから逆順に処理する。値ログの再生順序は結果に影響しないが、キーが複数回書き換えられている場合、逆順（新しいファイルから）に処理する方が、木の現在値がログレコードより新しいために上書きが不要になるケースが増え、CPU を効率よく使えるとしている。

実験・結果

評価環境は4基の8コア Intel Xeon E7-4830（合計32物理コア）、256GB DRAM、3台の Fusion ioDrive2 フラッシュドライブと1台の RAID-5 ディスクアレイ。比較対象は SiloR（フル機能）、LogSilo（ロギングのみ、チェックポイントなし）、MemSilo（永続化なしの Silo 本体）。

SiloRのスループットとレイテンシ（灰色部分はチェックポイント実行中）。LogSilo・MemSiloと比べてもチェックポイント中の落ち込みは小さい

Figure 1: Throughput and latency of SiloR, and throughput of LogSilo and MemSilo, on our modified YCSB benchmark.

fsyncの頻度によるバースト性の違い。(a)1回だけのfsyncと(b)sleep挿入は激しいバーストを示すが、(c)SiloRの定期的なfsyncはほぼバーストを解消する

Figure 4: Importance of regular disk synchronization.

関連研究との関係（メモ）

Q&A

（自分がAIに実際に質問したことだけをQ/A形式で残す。まだなし。）

自分のコメント

（ここは自分で都度書く欄。）