論文：Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems

この記事は、Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systemsという論文からのメモです。この論文は、2015年に発表されました。

シリーズ：DuckDBが採択した論文

このシリーズは、DuckDBが採用した論文を読んだ際のメモをまとめたものです。

• ベクターベースのクエリエンジン
• 高速でSerializableなMVCC: 本記事
• Join順序の最適化 （近日公開）
• サブクエリ展開（近日公開）

主な内容

この論文は、データベースの並行処理制御についてのもので、主なMVCCがスナップショット分離レベル(SI)を提供する中、シリアライザビリティを提供しつつ、オーバーヘッドとロックが少ないマルチバージョン並行性制御(MVCC)の実装を提案しています。

アプローチとしては、トランザクションがデータを読み取る際にはスナップショットを使用するが、コミット時間軸で競合をチェックすることでシリアライザブルな分離レベルを提供するというものです。

DB分離レベル: スナップショット vs シリアライザブル

スナップショット分離レベルとシリアライザブル分離レベルを比較した記事はこちら。

あとDuckDBはこの論文のコンセプトをもとにMVCCを実装しているのは見られるのですが、シリアライザブルな分離レベルのコントロールは実装されてない気がします。確証を取るには至っていないのですが現時点のコードとGitHubのイシューで見る限りスナップショット分離レベルを提供してるっぽいです。まあOLAPなのでそれで十分なんだろうと思います。

バージョンのストレージと位置

• 従来のMVCC: あちこちに存在するバージョン

  • 古いバージョンは破棄されず保持され、バックグラウンドプロセスによってクリーンアップされる。

  • DBMSのストレージは動的に割り当てられるため、書き込みのタイミングによって保存位置やページがバラバラになってしまう。

  • 並行トランザクション間のデータ競合を最小限に抑えるため、新しいバージョンを異なるページに作成するよう実装されることがある。

  • リカバリのためにログが記録された後でバージョンが作成されるが、新しいバージョンは通常リカバリの際に元のバージョンを保持できるように、別のストレージ場所に作成される実装がされることがある。

  • 利用可能なストレージの隙間をシステムが利用するため、データが時間とともに断片化され、バージョンが異なる場所に分散されることがある。

• 提案されたMVCC: 中央集約型バージョン管理

  最新のデータはin-place（同じエントリ）に上書きされ、以前のバージョン（before-image）は巻き戻し用バッファに保管されます。

  • DB全体に分散された複数のバージョンを管理する複雑さを軽減。

  • 各コミットが成功するたびに、このコミット時間より前の不要なバージョンがクリーンアップされる。

  • キャッシュに適した形式でパフォーマンスを向上させる。

直接言及があるわけではないが、この「あちこちに存在するバージョン」というのはPostgreSQLがいい例な気がします。

PostgreSQLは簡潔さや確実なデータ保存を優先するため、永続するデータのストレージに多数のバージョンを保存する設計がされています。この設計判断によってVACUUMが必要になったり、ある程度サイズの大きいテーブルからレコードの正確な数を数えるのが物凄くコストの高いオペレーションになってしまいます。なのでトランザクションのバージョンをデータのストレージではない所に保存するのはそういった副作用がないので理にかなっている気はします。

ロックの削減

• 従来のMVCC:

  • 他のトランザクションが更新しないよう行ロックが起きることがある。

  • バージョンの可視性を制御するために、ロックや類似のメカニズムが使用されることがある。

  • 安定したデータを得るために、バージョンリストが読み取り中にロックされることがある。

• 提案されたMVCC:

  バージョンの追加は巻き戻し用バッファ内のみで完結する。

  • 精密なロック: 更新される局所的な領域のみ。

    変更は小さく特定のメモリ領域に限定される。

    • ロック保持時間の短縮。

    • 他のトランザクションは巻き戻し用バッファの別の部分を読み取ったり更新したりすることができる。

よりセレクティブなチェック

• 従来のMVCC:

  • コミット済みトランザクションだけでなく、コミットされていないトランザクションもチェックされることがある。

  • 保守的なアプローチでは、変更だけでなく、読み取りもチェックされることがあります。これは、write skew anomalyのようなシナリオに対応するため。

  • read-writeやwrite-write、さらにはread-readのようなすべての競合タイプがチェックされることがある。

  • 競合トランザクションのチェックはグローバルレベルで行われることがあり、これによりグローバルロックが発生することがある。

• 提案されたMVCC:

  • 進行中のトランザクションの読み取りに影響を与える可能性のある、コミット済みのトランザクションのみをチェックする。

  • コミット時に初めて主な競合検出を、より限定された範囲で行う。

効率的な検証と競合解決

• 従来のMVCC:

  • シリアライザビリティを確保するためにグローバルロックが必要になることがある。

  • タイムスタンプの利用:

    • タイムスタンプの一意性を確保するためにアトミック操作が必要となり、待ち時間が発生する可能性がある。

    • 比較プロセスが複雑になることがあり、システムは他の多数のトランザクションのタイムスタンプに対して読み取りおよび書き込み操作を検証する必要がある。

    • タイムスタンプを持つトランザクションがまだコミットされていない場合、それより後のタイムスタンプを持つトランザクションが待機を強いられることがあり、遅延が起きることがある。

    • ロールバックは、却下されたトランザクションによって行われたすべての変更を元に戻し、以前の状態を復元し、場合によってはトランザクションを再開始する必要がある。

• 提案されたMVCC:

  • コミット完了時のタイムスタンプのみで競合をチェックすることでシリアライザビリティを検証する。

  • 巻き戻し用ログ内のバージョンは変更部分（デルタ）のみのバージョンチェーン。

  • 巻き戻し用ログ内のバージョンはIDとタイムスタンプでインデックスされる。

  • 迅速なシリアライザビリティのために、トランスアクションのPredicate（述語）をログに記録し、新たなトランスアクションの衝突検証に使用する。

ベンチマーク

• TPC-C: 注文クエリの書き込み中心のベンチマーク（読み取りトランザクション8%、書き込みトランザクション92%）

  • 提案されたMVCC:

    • 100,000 TPS (1秒あたりのトランザクション数)

    • 単一バージョン並行制御と比較して約20%のパフォーマンスコスト

    • 最大20コアまでリニアにスケールするが、それ以上ではグローバル同期を減らす必要がある。Siloはこれを実装してる。

  • 2PL (two-phase locking) in HyPer: 5倍遅い

  • 従来のMVCC: 50,000 TPS

• TATP: ポイントアクセスおよびレコード全体更新のベンチマーク（読み取りトランザクション80%、書き込みトランザクション20%）、通信アプリをシミュレート。

  • 提案されたMVCC: 407,564 TPSは、単一バージョン制御と比較して最小限のオーバーヘッドで、従来のMVCCを上回る。

  • 単一バージョン制御: 421,940 TPS

  • 従来のMVCC: 340,715 TPS