Project Proposal for 15-618 CMU Fall 2019
Paulina Davison (pldaviso) & Shrey Bagroy (sbagroy)
We will implement 3-4 methods to improve performance of concurrent sequential scans, which scan a table in-order, for the terrier database. These methods include designing a latch-free implementation, using a concurrent data structure, and storing a static copy of the table to minimize read and write conflicts from separate threads. We will analyze system usage, performance improvement, and scalability on test workloads.
The Terrier Database is designed to support fully autonomous optimization of hybrid workloads. It is an in-memory, column-store database. That it is an in-memory database means that there will be minimal memory access response time in contrast to the larger latency of disk memory databases. That it is a column-store database means that the same attributes of multiple tuples are stored contiguously. They are stored in what are called blocks. In the terrier database design, each block is 1 MB and all attributes of a single tuple are always stored in the same block. Multiple blocks in a doubly linked list form a data table.
The parts of the system we will be most interacting with are the scan and insert functions. The scan function implements a sequential scan of data, meaning that a thread reads contiguous data from as many of the blocks as it needs to. The insert function inserts new tuples in free slots in the blocks. The ordering of the tuples does not matter so different threads will insert into different blocks, allocating a new block and appending it to the list if needed.
In the scan function, there are two places that locks are being used (in databases they are called latches - please overlook this throughout the proposal - the implementation uses spin locks). Both are for iterators. The first is in a function called end() that is used to update the pointer to the last block of the linked list. The end pointer will either point to the last partially filled block in the list or the nullptr at the end of the list, if the last block is full.
A lock is taken in the end function to make sure that the end pointer is not being updated by multiple threads simultaneously. The overloaded operator ++ also takes a lock. This operator is responsible for moving a pointer to the next tuple in a block or, if at the end of a block, the next block.
In the scan function there is a pointer defined as start_pos, which points to an attribute in the block. There is a while loop that supports the start_pos pointer in moving through each of the tuple attributes in the blocks. In this while loop predicate, the end function is being called to determine that the start_pos pointer is still in scope. In the while loop before the next loop is run, the ++ operator is called on the start_pos pointer to move it to the next tuple. This means that locks are taken twice in every while loop iteration. In addition, since both of these locks are being updated at the tuple-level, not the block-level, they are being acquired more often than is necessary.
The primary challenge involved with this project is being able to implement/improve parallelism while ensuring that the end-to-end functionality of the entire system is untouched. There is a current implementation of the insert function that has good multi-threaded performance. Changing the implementation of the scan function may require us to change the implementation of the insert function. In this situation, we want to ensure that the insert function’s correctness and performance is upheld while improving the scan function’s performance.
As described earlier, terrier is a database under active development by multiple researchers at the DB lab at CMU. The entire codebase is large, however, we will only be dealing with a small subset of the codebase. This scenario is very similar to what we would encounter in the industry, where we would be building a small part of the system and, yet, we would want to be able to apply concepts from this class to it. As a result, our top priority is not just improving performance, but also ensuring that we maintain end-to-end correctness and/or don’t break other parts of the system.
Our primary task involves improving the efficiency of parallel scans (read/writes) in the database. The current implementation involves a high synchronization cost which would drastically affect the parallelization potential. There is also a potential for a large amount of false sharing since we’re concurrently trying to access the same entries in the database.
We will be contributing to the terrier database: https://github.com/cmu-db/terrier. The current implementation of sequential scan and insert are defined in /src/storage/data_table.cpp as functions Scan and Insert. Unit tests are defined in /test/data_table_test.cpp and /test/data_table_concurrent_test.cpp. Benchmark tests are defined in /benchmark/storage/data_table_benchmark.cpp. We will be developing on our personal computers and running the benchmarks on the Gates Cluster machines. As of this time, we have not identified any books or papers to use as a reference.
Since we are contributing to an existing, ongoing project, we are using the hardware (multi-core CPU) and programming language (C++) used by the project.