Project #4 - Concurrency Control

Do not post your project on a public GitHub repository.

Overview

This project is all about adding support for transactions in BusTub! To achieve this, you will add a lock manager to your system in your database system and then use it to support concurrent query execution. The lock manager is responsible for keeping track locks on both tables and tuples in five different 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 is comprised of the following three tasks:

This is a single-person project that will be completed individually (i.e., no groups).

  • Release Date: Nov 15, 2022
  • Due Date: Dec 11, 2022 @ 11:59pm

Project Specification

Like the previous projects, we are providing you with stub classes that contain the API that you need to implement. You should not modify the signatures for the pre-defined functions in these classes. If you do this, it will break the test code that we will use to grade your assignment, and you will end up getting no credit for the project. If a class already contains certain member variables, you should not remove them. But you may add private helper functions/member variables to these classes in order to correctly realize the functionality.

The correctness of this project depends on the correctness of your implementation of previous projects; we will not provide solutions or binary files aside from the B+ Tree wrapper from Project #3.

Task #1 - Lock Manager

To ensure correct interleaving of transactions' operations, the DBMS will use 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 then issue lock requests to the LM before they are allowed to access a data item. The LM will either grant the lock to the calling transaction, block that transaction, or abort it.

In your implementation, there will be a global LM for the entire system (similar to your buffer pool manager). The TableHeap and Executor classes will use your LM to acquire locks on tuple records (by record id RID) whenever a transaction wants to access/modify a tuple.

This task requires you to implement a table-level and tuple-level LM that supports the three common isolation levels: READ_UNCOMMITED, READ_COMMITTED, and REPEATABLE_READ. The Lock Manager should grant or release locks according to a transaction's isolation level. Please refer to the lecture slides for a refresher on isolation levels.

In the repository, we are providing you with 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 failed lock operation should lead to an ABORTED transaction state (implicit abort) and throw an exception. The transaction manager (include/concurrency/transaction_manager.h) would further catch this exception and rollback write operations executed by the transaction.

We recommend you to read this article to refresh your C++ concurrency knowledge. More detailed documentation is available here.

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 will need to implement the following functions:

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

The specific locking mechanism taken by the lock manager depends on the transaction isolation level, whether it is a table-level or tuple-level lock, and the type of lock involved. You should first take a look at the transaction.h and lock_manager.h to become familiar with the API and member variables we provide. Then, carefully read through [LOCK_NOTE], [UNLOCK_NOTE], and individual function specs in lock_manager.h to understand the expected behavior for your LM.

We also recommend to review the isolation level and hierarchical locking concepts since the implementation of these functions shall be compatible with the isolation level of the transaction that is making the lock/unlock requests. You have the freedom of adding any necessary data structures in lock_manager.h. You should consult with Chapters 15.1-15.2 in the textbook and isolation level concepts covered in lectures to make sure your implementation satisfies the requirement.

HINTS

  • While your Lock Manager needs to use deadlock detection, we recommend testing and verifying the correctness of your lock manager implementation first without any deadlock handling before adding detection mechanisms.
  • You will need some way to keep track of which transactions are waiting on a lock. Take a look at LockRequestQueue class in lock_manager.h
  • When do you need to upgrade a lock? What operations on the LockRequestQueue is needed when you need to update a table/tuple lock?
  • You will need some way to notify transactions that are waiting when they may be up to grab the lock. We recommend using std::condition_variable provided as part of LockRequestQueue.
  • You should maintain the state of a transaction. For example, the states of transaction may be changed from GROWING phase to SHRINKING phase due to unlock operation (Hint: Look at the methods in transaction.h)
  • You should also keep track of locks acquired by a transaction using *_lock_set_ so that when the TransactionManager wants to commit/abort a transaction, the LM can release them properly.
  • Setting a transaction's state to ABORTED implicitly aborts it, but it is not explicitly aborted until TransactionManager::Abort is called. You should read through this function and 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 the background to abort blocking transactions.

More precisely, this means that a background thread should periodically build a waits-for graph on the fly and break any cycles.

REQUIREMENTS

The graph API you must implement and use for your cycle detection along with testing is the following:

  • AddEdge(txn_id_t t1, txn_id_t t2): Adds an edge in your graph from t1 to 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 the Depth First Search (DFS) algorithm. 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 logic in here.

How you choose to implement the graph is up to you as long as your implementation supports the above API. Those functions are what we will use to test your code.

NOTES

  • Your background thread should build the graph on the fly every time it wakes up. You should not be maintaining a graph, it should be built and destroyed every time the thread wakes up.
  • Your DFS Cycle detection algorithm must be deterministic. In order to do achieve this, you must always choose to explore the lowest transaction id first. This means when choosing which unexplored node to run DFS from, always choose the node with the lowest transaction id. This also means when exploring neighbors, explore them in sorted order from lowest to highest.
  • When you find a cycle, you should abort the youngest transaction to break the cycle by setting that transactions state to ABORTED.
  • When your detection thread wakes up, it is responsible for breaking 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. We have added a static method Transaction* GetTransaction(txn_id_t txn_id) to let you do that.
  • You can use std::this_thread::sleep_for to order threads to write test cases. You can also tweak CYCLE_DETECTION_INTERVAL in common/config.h in your test cases.

HINTS

  • Remember that a waits for graph is a directed graph.
  • A waits for graph draws edges when a transaction is waiting for another transaction. Remember that if multiple transactions hold a lock on the same object, a single transaction may be waiting on multiple transactions.
  • When a transaction is aborted, make sure to set the transaction's state to ABORTED. The transaction manager will 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.

Task #3 - Concurrent Query Execution

During concurrent query execution, executors are required to lock/unlock tuples appropriately to achieve the isolation level specified in the corresponding transaction. To simplify this task, you can ignore concurrent index execution and just focus on table tuples.

You will need to 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. Although there is no requirement of concurrent index execution, we still need to undo all previous write operations on both table tuples and indexes appropriately on transaction abort. To achieve this, you will need to maintain the write sets in transactions, which is required by the Abort() method of transaction manager. When the executor fails to acquire a lock, you should throw a ExecutionException so that the execution engine will tell the user that the query failed and should be aborted.

You should not assume that a transaction only consists of 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.

More specifically, you will need to add support for concurrent query execution in the following executors:

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

In this task, you are also required to pass Terrier Benchmark without segfault and deadlocks.

Terrier Benchmark

In a galaxy far, far away, there is a planet. On the planet live Jack Russell terriers in a highly-civilized society. There is an increasing popularity of NFTs (non-fungible token). One day the terriers decide to find some database system to track their NFTs, and BusTub is one of the candidate system.

Each terrier has a unique ID. Each NFT also 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 transaction at 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

Here is a list of recommended optimizations:

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

Implement UpdateExecutor: You can implement UpdateExecutor 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 exchaging 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 specified optimizations.

Instructions

Setting Up Your Development Environment

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

You must pull the latest changes on our BusTub repo for test files and other supplementary files we have provided for you. Run `git pull`.

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
make deadlock_detection_test
make transaction_test
./test/lock_manager_test
./test/deadlock_detection_test
./test/transaction_test

Important: These tests are only a subset of the all 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.

Development Hints

Instead of using printf statements for debugging, use the LOG_* macros for logging information like this:

LOG_INFO("# Leaf Page: %s", leaf_page->ToString().c_str());
LOG_DEBUG("Fetching page %d", page_id);

To enable logging in your project, you will need to reconfigure it like this:

cd build
cmake -DCMAKE_BUILD_TYPE=DEBUG ..
make

The different logging levels are defined in src/include/common/logger.h. After enabling logging, the logging level defaults to LOG_LEVEL_INFO. Any logging method with a level that is equal to or higher than LOG_LEVEL_INFO (e.g., LOG_INFO, LOG_WARN, LOG_ERROR) will emit logging information.

Use assert to force check the correctness of your implementation.

Please post all of your questions about this project on Piazza. Do not email the TAs directly with questions. The instructor and TAs will not debug your code. Particularly with this project, we will not debug deadlocks.

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.

Late Policy

See the late policy in the syllabus.

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

Collaboration Policy

  • Every student has to work individually on this assignment.
  • Students are allowed to discuss high-level details about the project with others.
  • Students are not allowed to copy the contents of a white-board after a group meeting with other students.
  • Students are not allowed to copy the solutions from another colleague.

WARNING: All of the code for this project must be your own. You may not copy source code from other students or other sources that you find on the web. Plagiarism will not be tolerated. See CMU's Policy on Academic Integrity for additional information.