Proposal: Lock-free Extendible Hash Table in Database Management System
Proposal: Lock-free Extendible Hash Table in Database Management System
URL:
https://www.andrew.cmu.edu/user/yicheng4/posts/lock_free_eth/
SUMMARY:
The project involves implementing a lock-free extendible hash table (ETH) as a key feature. This ETH will be integrated into Bustub, an experimental database management system that’s publicly available. The goal is to enhance Bustub’s functionality and efficiency with the introduction of this advanced hash table mechanism.
BACKGROUND:
An extendible hash table (ETH) is a type of dynamic hash table with a unique approach to handling increases in the number of items stored. It’s a form of hashing that can dynamically adjust to accommodate more data, unlike traditional hash tables which have a fixed size. It consists of a directory that points to buckets. Each bucket can store multiple entries. The hash function generates an index based on the key. However, instead of using the entire hash value, it uses a certain number of bits (the “global depth”) to index into the directory. Each bucket has a local depth, indicating the number of bits of the hash used to determine its entries. The global depth reflects the depth used for the whole table. When a bucket overflows, it splits, and the local depth increases. If two buckets become underutilized, they can merge, decreasing their local depth. By splitting buckets, extendible hashing efficiently manages collisions and overflows.
A Database Management System (DBMS) is a software system designed to store, retrieve, and manage data in databases. It serves as an interface between the database and the users or the application programs, ensuring that the data is consistently organized and remains easily accessible.
Extendible hash tables are particularly useful in databases for handling large and growing datasets efficiently. As databases grow, extendible hashing allows for dynamic scaling without significant rehashing or downtime. The dynamic nature of extendible hashing helps in evenly distributing data across buckets, which is essential for load balancing in databases. By minimizing the number of disk accesses required for searches, updates, and insertions, extendible hash tables enhance overall database performance. They offer more flexibility compared to static hash tables, especially in databases where the volume and frequency of data insertion can vary greatly.
In a lock-free environment, multiple threads can access the hash table simultaneously without significant locking overhead. This is particularly beneficial for high-throughput databases where multiple transactions or operations are occurring at once. Parallelism ensures that these operations can be processed simultaneously, reducing wait times and increasing the overall efficiency of data retrieval and updates.
THE CHALLENGE:
Lock-free implementation of the ETH is hard. The main issue arises when the table needs to be resized. This process involves moving multiple items from the “old” buckets to the “new” ones. Achieving atomicity in a single Compare-And-Swap (CAS) operation is difficult. Atomicity is required to move an item from one linked list to another without losing it. However, a single CAS operation appears insufficient for this task.
Without atomic operations, there’s a risk of losing elements during the transfer. To prevent this, elements might need to be duplicated, which leads to the complexity of managing these replications.
Lock-free methods that provide the necessary broader atomicity require processes to assist others in completing their operations. This “helping” mechanism is intricate. Also, “Helping” other processes necessitates storing state information and continuously monitoring the progress of these processes. This requirement can lead to redundancy and overhead.
Using ETH on Databases is also hard. DBMS often run in environments where garbage collection is not as efficient, such as in certain languages or systems. Lock-free structures can exacerbate memory usage issues due to the need to keep old versions of data structures or due to delayed garbage collection. Also, DBMS gains control of memory at Page granularity, meaning it won’t follow systems’ memory controls and would increase our work for cache coherence.
RESOURCES:
We will use our own laptops for development as C++ is widely supported. We might want to use PSC for benchmarking as it has more cores. We are using Bustub(https://github.com/cmu-db/bustub) as the starter point of the extendible hash table.
Referred paper: Ori Shalev and Nir Shavit. 2006. Split-ordered lists: Lock-free extensible hash tables. J. ACM 53, 3 (May 2006), 379–405. https://doi.org/10.1145/1147954.1147958
Development Machines:
Personal laptops equipped with suitable specifications for C++ development.
Operating Systems: MacOS
Hardware Specifications: 2.2 GHz 6-Core Intel Core i7
Benchmarking and Performance Testing:
Access to the Pittsburgh Supercomputing Center (PSC) for high-performance benchmarking with more cores. It’ll be on a Linux machine. So that we can evaluate the scalability and performance under various core counts and load conditions.
Development Environment:
Programming Language: C++.
Version Control: Github (https://github.com/yicheng4/lock_free_htable_bustub) It’s currently private due to Database course restrictions, but will be made public later.
Code Base and Starter Kit:
Primary Code Base:
Bustub (https://github.com/cmu-db/bustub): An educational database management system from Carnegie Mellon University, serving as the foundational code base for our extendible hash table implementation.
Reference Materials:
Primary Literature:
Ori Shalev and Nir Shavit’s paper on lock-free extensible hash tables (Shalev, O., & Shavit, N. (2006). Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM, 53(3), 379-405. https://doi.org/10.1145/1147954.1147958).
Purpose: To guide the theoretical and practical aspects of our implementation.
Supplementary Materials:
15445 Database system course at CMU. (https://15445.courses.cs.cmu.edu/fall2023)
Book:
Silberschatz, A., Korth, H. F., & Sudarshan, S. (2020). Database System Concepts (7th ed.). McGraw-Hill.
GOALS AND DELIVERABLES:
Primary Goals (Plan to Achieve):
Implementation of a Lock-Free Extendible Hash Table:
Develop a fully functional lock-free extendible hash table in C++, based on the principles outlined in the Shalev and Shavit paper. The chosen starter code (Bustub) and the theoretical foundation provided by the reference paper give us a solid base for implementation.
Performance Benchmarking:
Conduct comprehensive benchmark tests using both personal laptops and the Pittsburgh Supercomputing Center resources. We need to assess the hash table’s performance, scalability, and efficiency under various conditions.
Access to high-performance computing resources and robust testing tools supports our ability to achieve meaningful performance metrics.
System Integration and Testing:
Integrate the lock-free extendible hash table into the BusTub database management system.
Conduct thorough testing to ensure stability and reliability within the DBMS context.
Secondary Goals (Hope to Achieve):
Performance Optimization:
Aim to achieve a significant speedup compared to the starter code.
Based on preliminary research and understanding of lock-free structures, such optimizations seem achievable, especially with efficient memory management and parallelization strategies.
Additional Features:
If ahead of schedule, explore the addition of advanced features such as dynamic resizing based on load or enhanced garbage collection techniques. We may also want to consider how to optimize the resizing of memory, DBMS might need to handle the memory of pages, and this would introduce some coherence issues.
Contingency Goals (If Work Progresses More Slowly):
Basic Lock-Free Hash Table:
We need to at least have a lock-free hash table, though it might not be extendible though.
Limited Scope Benchmarking:
If full-scale benchmarking is not feasible, conduct a more limited set of tests to demonstrate basic performance improvements and scalability.
Demonstration at the Poster Session:
Interactive Demo:
Present an interactive demonstration of the hash table integrated within the Bustub environment. We will use a laptop to do this. We also need to show the hash table handling various types of loads and transactions in real-time.
Performance Metrics Display:
Exhibit graphs and charts showcasing the performance benchmarks, comparing our implementation with the baseline.
Feature Highlights:
If advanced features are implemented, demonstrate these specifically, illustrating the benefits they bring to the hash table’s performance and efficiency.
PLATFORM CHOICE:
We will choose C++ as a lock-free programming language.
C++ is renowned for its high performance, a critical factor in parallel computing where efficiency is paramount. It provides close-to-hardware level control, allowing developers to optimize their code for maximum performance.
Lock-free programming is a concurrency control method that avoids locking objects as a means to manage access by multiple threads. C++ offers robust support for atomic operations and memory models that are essential for implementing lock-free algorithms. This support is crucial for developing highly concurrent, scalable systems without the overhead and complexity of traditional locking mechanisms.
C++ comes with a rich Standard Template Library that includes a range of data structures and algorithms. While not all STL components are lock-free, they provide a solid foundation for building complex lock-free structures and algorithms.
In lock-free programming, precise control over memory allocation and deallocation is often necessary to avoid issues like the ABA problem. C++ gives developers explicit control over memory management, which is crucial for implementing effective lock-free data structures.
We will build upon Bustub (https://github.com/cmu-db/bustub) , an experimental database management system given its robustness and testing code provided for those functions.
SCHEDULE:
- Week of Nov 13:
Read paper, work on the baseline implementation. It is a little bit different than the class project because class projects use a data structure called PageGurad to manage memory, and that structure uses a lot of lock (we call latches in DBMS).
- Week of Nov 20:
Implementation I. Near the end of the week, the implementation should be able to successfully support read and insert on a fixed hash table, i.e. the hash table won’t do any split or merge at this time. It should support two producers inserting it concurrently, while another consumer reading from the hash table. We’re expecting to see valid results: specifically no loss of insertion and consistency of results with respect to program order.
- Week of Nov 27:
Implementation II. Near the end of this week, we should be able to support read, insert and deletion concurrently on a fixed hash table. We’ll have 2 producers inserting values, 2 workers deleting values, and 1 consumer reading out the table. Again, each working node should follow program order, and we expect to see the correct values when reading from the hash table after all insertion and deletion.
In expectation, we should be finishing this part before the last day of the week since the last part would be the most challenging in terms of correct implementation.
- Week of Dec 4:
Implementation III. By the end of this week, we should be finishing everything. The work for this week is to support growing and shrinking the hash table. Under the same setup with 2 producers inserting values, 2 workers deleting values, and 1 consumer reading out the table, these insertions and deletions are likely to cause our buckets to grow and shrink periodically. Again, we’re measuring correctness in terms of program order and consistency after all writing nodes are done.
- Week of Dec 11:
Benchmark, poster and paper writing.
By this time, all implementation is done. We first need to create a good benchmark on timing this, and then log the statistics, draw graphs and generalize the results. After we get the raw data, we need to create a poster and write up the paper.