技術的概要

本ドキュメントでは、BusTub オープンソースデータベースシステムに対して、トランザクション処理機能を付加する開発要件について解説します。主な焦点は ロックマネージャー (Lock Manager) の構築と、それを利用した並行クエリ実行のサポートです。これにより、複数のトランザクションが同時にデータベースを操作する際の整合性が保証されます。

ロックマネージャーのアーキテクチャ

データベース内でデータのアクセスを制御するために、システム全体にわたって一意なロックマネージャーが必要となります。これはバッファプールマネージャーのような単一グローバルインスタンスとして動作します。事務処理ユニットは特定のデータ項目（テーブルまたはレコード）にアクセス・更新を行う際、必ず先に LM へロックを要求する必要があります。LM は以下の判断を下すロジックを実装します：

• 該当するトランザクションへロックの授与
• 他トランザクションとの競合による待機ブロック
• 回復不能な競合発生時のトランザクション中止

実装には、以下の主要なロックモードに対応する必要があります：

• Intention-Shared (IS)
• Intention-Exclusive (IX)
• Shared (S)
• Exclusive (X)
• Shared-Intention-Exclusive など、階層的なロック構造

隔離レベルの実装要件

トランザクションごとに異なる隔离性（Isolation Level）をサポートし、適切なロックの付与や解放が行われることを確認してください。transaction.h に定義されたメタ情報に基づき、以下のレベルを実装します：

• READ_UNCOMMITTED
• READ_COMMITTED
• REPEATABLE_READ

隔離レベルに応じ、ロックの期間と粒度が決定されます。例えば、特定の隔離レベルではロック解除のタイミングが遅れ、より長期間の排他管理が必要です。エラーが発生した場合（ロック獲得不可など）、内部例外として処理され、TransactionManager によってトランザクション状態が ABORTED へ遷移し、変更されたデータがロールバックされます。

実装タスク詳解

フェーズ 1: ロックマネージャー核心実装

このフェーズでは、主に concurrency/lock_manager.cpp および関連ヘッダーファイルにて以下のメソッドのロジックを作成します。既存の API とメンバ変数を参照し、指定された仕様を満たすクラス設計を行ってください。

• LockTable(Transaction*, LockMode, TableOID): テーブルレベルのロック取得
• UnlockTable(Transaction*, TableOID): テーブルレベルのロック解放
• LockRow(Transaction*, LockMode, TableOID, RID): 特定レコード（RID）に対するロック取得
• UnlockRow(Transaction*, TableOID, RID): 特定レコードのロック解放

実装時の重要なポイント：

• 各関数の事前条件を確認し、失敗時の挙動（ABORT）を実装する。
• トランザクションの状態管理（GROWING 状態から SHRINKING 状態への遷移など）を追跡する。
• 利用者がロックを保持している履歴を維持し、コミットまたはアボート時に一括解放可能にする必要がある。
• std::condition_variable を使用して、ロック待ち中のスレッド間での効率的な通知機構を実現する。

フェーズ 2: デッドロック検出アルゴリズム

システム稼働中に、複数のトランザクションが相互にロックを待ち続けるデッドロックを防止するため、バックグラウンドスレッドによる定期検出ループを実装します。

必要なグラフ API 機能は以下の通りです：

• AddEdge(txn_id_t t1, txn_id_t t2): トランザクション t1 が t2 に待機中であることを示すエッジを追加。
• RemoveEdge(txn_id_t t1, txn_id_t t2): 上記エッジを削除。
• HasCycle(txn_id_t& txn_id): 深さ優先探索 (DFS) によりサイクルを検出。存在する場合、最も若い（最後に生成された）トランザクション ID を出力し true を返す。
• GetEdgeList(): 現在の waits-for グラフのエッジリストを取得し、テスト用ベンチマークを提供。

アルゴリズムの方針：

1. 検出スレッド起動時は都度グラフを再構築すること。
2. 探索順序の決定性は必須であるため、未探索ノード選定時にはトランザクション ID が最小のものを選択し、隣接ノードも昇順で処理する。
3. サイクル発見時、該当箇所の最も新しいトランザクションをターゲットとし、アボート処理をトリガーする。
4. アボート済みのトランザクションについては、その後のグラフ構築では含めないこと。

フェーズ 3: クエリエクスュータとの連携

クエリ実行プロセス（Executor）において、実際のデータ操作前にロック獲得を試みる実装を行います。対象となるコンポーネントは以下です：

• seq_scan_executor.cpp
• insert_executor.cpp
• delete_executor.cpp

重要な要件として、ロック取得に失敗した場合（例：タイムアウトやデッドロック候補）は ExecutionException を投げて強制的に中止させる必要があります。また、中途半端な状態でコミットされないよう、トランザクション内の変更履歴（Write Set）を管理し、TransactionManager::Abort 呼び出し時にインデックスおよびテーブルの修正をすべて取り消す仕組みを整備してください。

パフォーマンス検証：Terrier ベンチマーク

実装の堅牢性と性能を評価するための基準テストが用意されています。このテストでは、高頻度の読み書き操作を含むワークロードが複数のスレッドから並列に発行されます。

シナリオ設定：

CREATE TABLE assets(asset_id INTEGER PRIMARY KEY, owner_id INTEGER);
-- トランザクション A: アセット所有者の確認と引き渡し処理
SELECT owner_id FROM assets WHERE asset_id = X;
DELETE FROM assets WHERE asset_id = X;
INSERT INTO assets(asset_id, owner_id) VALUES (Y, owner_id);

この環境下で、30 秒間の連続実行中に、以下を満たすことが求められます：

1. データの不整合（二重売却等）が発生しないこと。
2. システムクラッシュや永久死鎖（Hang）が発生しないこと。
3. 規定の QPS（Queries Per Second）閾値を超えて処理可能なこと。

QPS カルキュレーション式は 0.8 * update_qps + 0.2 * count_qps で算出されます。

最適化戦略（オプション）

ベンチマークスコア向上のため、以下の技術を適用できます。

• Predicate Pushdown: SeqScan の段階でフィルタリングを行い、不要なレコードへのロック試行を減らす。
• UpdateExecutor 導入: インラインでの更新処理を実装し、オーバーヘッドを削減する。
• インデックス活用: 検索条件に応じて IndexScan を使用し、RID エスケープによるアクセス効率を改善する。

テストと提出手順

ローカル環境での検証コマンドは以下の通りです。

cd build
make lock_manager_test
make deadlock_detection_test
./test/lock_manager_test
./test/deadlock_detection_test

最終提出前のチェックリストとフォーマット調整は以下のステップで行います。

make format
make check-lint
make check-clang-tidy-p4
make submit-p4