Project #4 - Concurrency Control

Overview

In this project, you will add support for transactions in BusTub by adding a lock manager and then using it for concurrent query execution. The lock manager will support table locks and tuple locks in five lock modes: intention-shared, intention-exclusive, shared-intention-exclusive, shared, and exclusive. The lock manager will process lock requests from transactions, grant locks to transactions, and check if locks are released appropriately based on the transaction's isolation level.

The project consists of three tasks:

This project must be completed individually (i.e., no groups). Before starting, run git pull public master to pull the latest code from the public BusTub repo.

Project Specification

Like previous projects, we provide stub classes that define the API you must implement. Do not modify the signatures of the predefined functions or remove predefined member variables in these classes; if you do, our test code will not work and you will receive no credit for the project. You may add private helper functions and member variables to these classes as needed.

The correctness of this project depends on the correctness of your implementation of previous projects. We do not provide solutions or binary files except for the B+ Tree wrapper that we provided in Project #3.

Task #1 - Lock Manager

To ensure correct interleaving of transactions' operations, the DBMS uses a lock manager (LM) to control when transactions are allowed to access data items. The basic idea of a LM is that it maintains an internal data structure about the locks currently held by active transactions. Transactions issue lock requests to the LM before they access data items, and the LM will either grant the lock, block the transaction until the lock is available, or abort the transaction.

In your implementation, there will be a global LM for the BusTub system. The TableHeap and Executor classes will use your LM to acquire locks on tuple records (by record id RID) when a transaction attempts to access or modify a tuple.

Your LM must implement hierarchical table-level and tuple-level intention locks (described above) and three isolation levels: READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ. The LM should grant or release locks according to a transaction's isolation level.

We provide a Transaction context handle (include/concurrency/transaction.h) with an isolation level attribute (i.e., READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ) and information about its acquired locks. The LM will need to check the isolation level of transaction and expose correct behavior on lock/unlock requests. Any invalid lock operation should lead to an ABORTED transaction state (implicit abort) and throw an exception. A failed lock attempt (such as for a deadlock) does not result in an exception, but the LM should return false for the lock request.

REQUIREMENTS

The only file you need to modify for this task is the LockManager class (concurrency/lock_manager.cpp and include/concurrency/lock_manager.h). You must implement the following functions:

  • LockTable(Transaction, LockMode, TableOID)
  • UnlockTable(Transction, TableOID)
  • LockRow(Transaction, LockMode, TableOID, RID)
  • UnlockRow(Transaction, TableOID, RID, force)

The LM's specific locking mechanism depends on the transaction isolation level, whether it is a table-level or tuple-level lock, and the type of lock involved. Make sure you are familiar with the Transaction class's API and member variables, defined in transaction.h and lock_manager.h Then, carefully read through [LOCK_NOTE], [UNLOCK_NOTE], and the LM's functions' specifications (in lock_manager.h).

The UnlockRow has a force parameter because executor implementations might need to determine whether a tuple is accessible before deciding whether to include it. If force is set to true, the operation bypasses all 2PL checks as if the tuple is not locked.

For UnlockRow, we have a force parameter, because in the executor implementation, we might need to peek whether a tuple is accessible by a transaction before deciding whether to scan this tuple to parent executors. If force is set to true, this operation bypasses all 2PL checks as if the tuple is never locked by the transaction.

HINTS

  • We recommend that you successfully implement and thoroughly test your Lock Manager without deadlock detection before attempting to add any functionality related to deadlock handling.
  • You will need some way to keep track of which transactions are waiting on a lock. Take a look at the LockRequestQueue class in lock_manager.h.
  • Think carefully about when do you need to upgrade a lock, and about what operations on the LockRequestQueue is needed when you need to update a table/tuple lock.
  • You will need some way to notify waiting transactions when a lock is available. We recommend using std::condition_variable provided as part of LockRequestQueue.
  • The lock manager should update the state of transactions as needed. For example, the state of a transaction may be changed from GROWING to SHRINKING by an unlock operation. See the methods in transaction.h
  • You should keep track of the locks acquired by a transaction using *_lock_set_ so that the TransactionManager can release locks appropriately when it commits or aborts a transaction.
  • Setting a transaction's state to ABORTED implicitly aborts it, but it is not explicitly aborted until TransactionManager::Abort is called. You should read this function and the provided tests to understand what it does and how your lock manager is used in the abort process.

Task #2 - Deadlock Detection

Your lock manager should run deadlock detection in a background thread, periodically building a waits-for graph and abort transactions as needed to eliminate deadlocks.

REQUIREMENTS

You must implement and use the following graph API for cycle detection:

  • AddEdge(txn_id_t t1, txn_id_t t2): Adds an edge in your graph from `t1` to `t2`, representing that `t1` is waiting for `t2`. If the edge already exists, you don't have to do anything.
  • RemoveEdge(txn_id_t t1, txn_id_t t2): Removes edge `t1` to `t2` from your graph. If no such edge exists, you don't have to do anything.
  • HasCycle(txn_id_t& txn_id): Looks for a cycle by using depth-first search (DFS). If it finds a cycle, HasCycle should store the transaction id of the youngest transaction in the cycle in txn_id and return true. Your function should return the first cycle it finds. If your graph has no cycles, HasCycle should return false.
  • GetEdgeList(): Returns a list of tuples representing the edges in your graph. We will use this to test correctness of your graph. A pair `(t1,t2)` corresponds to an edge from `t1` to `t2`.
  • RunCycleDetection(): Contains skeleton code for running cycle detection in the background. You should implement your cycle detection algorithm here.

You may implement the graph however you want, as long as you support the above API. We will use that API to test your implementation.

You may need to access the status of a transaction from the member variable txn_manager_. If txn_manager_ is set to nullptr, StartDeadlockDetection will not be called, and you do not need to detect deadlocks.

NOTES

  • Your background thread should build the waits-for graph every time it wakes up. You should not maintain the waits-for graph over time; it should be built and destroyed every time the deadlock detection thread wakes up.
  • Your cycle detection algorithm must be deterministic. To achieve this, you should always explore the lowest transaction id first, by starting the depth-first search from the node with lowest transaction id and exploring neighbors in order (by transaction id) when searching from a node.
  • When you find a cycle, abort the youngest transaction to break the cycle by setting that transaction's state to ABORTED.
  • When your detection thread wakes up, it must break all cycles that exist. If you follow the above requirements, you will always find the cycles in a deterministic order. This also means that, when you are building your graph, you should not add nodes for aborted transactions or draw edges to aborted transactions.
  • Your background cycle detection algorithm may need to get a pointer to a transaction using a txn_id. There is a member variable `txn_manager_` in lock manager, and Transaction* GetTransaction(txn_id_t txn_id) enables you do that.

HINTS

  • Remember that the waits-for graph is a directed graph, with an edge for each transaction waiting for another transaction. Because multiple transactions may share a lock on the same object, a single transaction may be waiting for multiple transactions.
  • When a transaction is aborted, set the transaction's state to ABORTED. The transaction manager should then take care of the explicit abort and rollback changes.
  • A transaction waiting for a lock may be aborted by the background cycle detection thread. You must have a way to notify waiting transactions that they've been aborted.
  • You can use std::this_thread::sleep_for to help write test cases, to cause threads to wake up in a pre-defined order. You can also tweak CYCLE_DETECTION_INTERVAL in common/config.h in your test cases.

Task #3 - Concurrent Query Execution

To support concurrent query execution, executors must lock and unlock tables and tuples as needed to achieve the isolation level specified in the transaction. To simplify this task, you can ignore concurrent index execution and just focus on data stored in heap files.

You must update the Next() methods of some executors (sequential scan, insert, and delete) implemented in Project 3. Note that transactions should abort when lock/unlock fails. If a transaction aborts, you will need to undo its previous write operations; to achieve this, you will need to maintain the write set in each transaction, which is used by the Abort() method of the transaction manager. If the executor fails to acquire a lock, you should throw an ExecutionException so that the execution engine will tell the user that the query failed.

You should not assume that a transaction only consists of just one query. Specifically, this means a tuple might be accessed by different queries more than once in a transaction. Think about how you should handle this under different isolation levels.

To complete this task, you must add support for concurrent query execution in the following executors and the transaction manager:

  • src/execution/seq_scan_executor.cpp
  • src/execution/insert_executor.cpp
  • src/execution/delete_executor.cpp
  • src/concurrency/transaction_manager.cpp

You must pass all tests and produce correct results for the Terrier Benchmark (see below) without segfaults and deadlocks. You do not need to handle concurrency for indexes or the update executor, except for the leaderboard tests.

NOTES

Isolation Level

  • A transaction should hold X locks for all write operations until it commit or aborts, regardless of its isolation level.
  • For REPEATABLE_READ, a transaction should take and hold S locks for all read operations until it commits or aborts.
  • For READ_COMMITTED, a transaction should take S locks for all read operations, but can release them immediately.
  • For READ_UNCOMMITTED, a transaction does not need to take any S locks for read operations.

SeqScan Executor

  • In Init, take a table lock. Get an iterator by using MakeEagerIterator instead of MakeIterator. (MakeIterator is introduced to avoid the Halloween problem in Project 3's UpdateExecutor, but you do not need it now.)
  • In Next:
    1. Get the current position of the table iterator.
    2. Lock the tuple as needed for the isolation level.
    3. Fetch the tuple. Check tuple meta, and if you have implemented filter pushdown to scan, check the predicate.
    4. If the tuple should not be read by this transaction, force unlock the row. Otherwise, unlock the row as needed for the isolation level.
    5. If the current operation is delete (by checking executor context IsDelete(), which will be set to true for DELETE and UPDATE), you should assume all tuples scanned will be deleted, and you should take X locks on the table and tuple as necessary in step 2.

Insert Executor

  • In Init, take a table lock.
  • In Next, pass the lock manager, transaction object, and table id to InsertTuple so as to insert and lock a tuple atomically. Be sure that you maintain the write set as needed.

Delete Executor

  • If you have implemented SeqScanExecutor correctly based on IsDelete() in executor context, you do not need to take any any locks in this executor.
  • Be sure that you maintain the write set in Next.

Transaction Manager

  • In Commit, you generally do not need to do anything except release all the locks.
  • In Abort, you should revert all changes of this transaction based on its write set.

Terrier Benchmark

In a galaxy far, far away, there is a planet on which Jack Russell terriers live in a highly-civilized society. We say that the society is highly civilized, except that NFTs (non-fungible token) are becoming increasingly popular. One day, the terriers decide to find a database system to track their NFTs, and BusTub is one of their candidate systems.

Each terrier and each NFT has a unique ID. The terriers first create an NFT table, which records which terrier each NFT belongs to:

CREATE TABLE nft(id INT, terrier INT);
INSERT INTO nft VALUES (0, 0), (1, 1), ...;

Then they run transactions at the REPEATABLE_READ isolation level to exchange NFTs. There will be multiple terriers running transactions at the same time, in multiple threads.

-- begin txn1
SELECT * FROM nft WHERE id = <nft_id>; -- record the terrier_id
DELETE FROM nft WHERE id = <nft_id>;
-- end txn1

-- begin txn2
INSERT INTO nft VALUES (<nft_id>, <terrier_id>)
-- end txn2

In the exchange process, they want to know how many NFTs each terrier owns.

SELECT count(*) FROM nft WHERE terrier = <terrier_id>;

You will need to ensure BusTub does not crash or deadlock while producing the correct result during the benchmark process for 30 seconds, so that the terriers do not lose track of their NFTs.

You can run the Terrier benchmark using the following command:

make -j`nproc` terrier-bench
./bin/bustub-terrier-bench --duration 30000

Leaderboard Task (Optional)

Terriers measure database performance by throughput -- counting how many transactions are processed within a given amount of time. In the leaderboard task, you will need to optimize BusTub to process NFT exchanges efficiently.

The terrier benchmark will start 2 threads to exchange NFTs and start 2 other threads to count how many NFTs each terrier owns. The final QPS (query per second) is computed as:

0.8 * update_qps + 0.2 * count_qps

make -j`nproc` terrier-bench
./bin/bustub-terrier-bench --duration 30000 --nft 10000

Here is a list of recommended optimizations:

Predicate pushdown to SeqScan: You can implement a predicate filter in SeqScanExecutor so that you lock fewer tuples when doing SeqScan. You can enable MergeFilterScan optimizer rule merge_filter_scan.cpp and implement this optimization.

Implement In-Place UpdateExecutor: You can improve your UpdateExecutor implementation so that tuples can be updated in-place and will probably be more efficient. Modify terrier_benchmark_config.h to instruct Terriers to use UPDATE for exchanging NFTs.

Use Index: You can create an index over the NFT table, and then push the predicate down to IndexScanExecutor to do index lookup. For example, if we have an index over NFT's id column, the SELECT * FROM nft WHERE id = 1 can actually be done like (1) extract id = 1 predicate and (2) directly call GetValue(1) over the index, instead of doing a full index scan or table scan. You will need to update index scan plan to facilitate this optimization. Modify terrier_benchmark_config.h to instruct Terriers to create an index before exchanging NFTs.

Note: You do not need to make your optimization perfect. For example, if you want to implement index lookup + update executor, you only need to consider the case for the terrier benchmark: the index only contains a fixed amount of items and the RID never changes.

Note: The terrier benchmark will run in debug mode without index creation and without update executor first, and then run in release mode with your preferred optimizations.

Instructions

Setting Up Your Development Environment

See the Project #0 instructions on how to create your private repository and setup your development environment.

Testing

You can test the individual components of this assignment using our testing framework. We use GTest for unit test cases. You can compile and run each test individually from the command-line:

cd build
make lock_manager_test -j`nproc`
make deadlock_detection_test -j`nproc`
make txn_integration_test -j`nproc`
./test/lock_manager_test
./test/deadlock_detection_test
./test/txn_integration_test

Important: These tests are only a subset of the tests that we will use to evaluate and grade your project. You should write additional test cases on your own to check the complete functionality of your implementation.

Memory Leaks

For this project, we use LLVM Address Sanitizer (ASAN) and Leak Sanitizer (LSAN) to check for memory errors. To enable ASAN and LSAN, configure CMake in debug mode and run tests as you normally would. If there is memory error, you will see a memory error report. Note that macOS only supports address sanitizer without leak sanitizer.

In some cases, address sanitizer might affect the usability of the debugger. In this case, you might need to disable all sanitizers by configuring the CMake project with:

$ cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..

Development Hints

You can use BUSTUB_ASSERT for assertions in debug mode. Note that the statements within BUSTUB_ASSERT will NOT be executed in release mode. If you have something to assert in all cases, use BUSTUB_ENSURE instead.

We encourage you to use a graphical debugger to debug your project if you are having problems.

If you are having compilation problems, running make clean does not completely reset the compilation process. You will need to delete your build directory and run cmake .. again before you rerun make.

Grading Rubric

Each project submission will be graded based on the following criteria:

  1. Does the submission successfully execute all of the test cases and produce the correct answer?
  2. Does the submission execute without any memory leaks?

Note that we will use additional test cases that are more complex and go beyond the sample test cases that we provide you.

Submission

After completing the assignment, you can submit your implementation to Gradescope for evaluation.

Running make submit-p4 in your build/ directory will generate a zip archive called project4-submission.zip under your project root directory that you can submit to Gradescope.

Remember to resolve all style issues before submitting:

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