Lock free database system

First lock free database system

 

Team Members: Tong Che, Zhicong Huang, Cheng Wang 

Team Leader: Tong Che

 

Project Description:

 

Motivation:

 

Lock freedom provides very attractive non-blocking properties and scalability. In nowadays concurrent programming, using Lock-Free data structures to achieve synchronization has become a trend. However, it is very difficult to design such data structures with high performance. As far as we know, current DBMS are all based on locks which leads to the dependence on a lock manager. Our plan is to introduce lock free indexing data structure into such systems to avoid the overhead of handling

locks, as well as to scale the system nearly linearly.

 

Specification:

There is already one lock-free B+ tree proposed in recent publication. Firstly, we want to implement this in SHORE. Though lock-free B+ tree is already available, we doubt its performance and the easiness to merge it into a real database system. Therefore there is a very high possibility that we need to design our own lock-free version of B+ tree.

After we have implemented a rough version, the following work is comparison and optimization. The part needs only some routine works.

 

If everything progresses very fast, we can dive into the transaction protocols, for which we think lock freedom is also quite reasonable. Since a large portion of the database is trying to deal with deadlocks, lock free primitives would also bring considerable change in system design itself.

 

Method description:

First, we dive into different lock free indexing algorithms, compare their performance in theory, and choose a right one to improve and implement. Then we try to adapt the implementation and design to real architectures such as NUMA and cc-NUMA. We will run our implementation on real data, to identify bottlenecks and try to avoid them. 

 

Required resources:

It seems that we need only a NUMA cluster to test the scalability of our implementation on real data. The lab is going to provide us with such things, so we do not have to worry about it too much.

 

Milestones of the project:

1st week: Read the code, and the 3 algorithm papers, make a decision on the algorithm which we are going to implement in Shore-MT.

2nd week: Read the code, make decision on design alternatives.

3rd week: Implement a new B tree indexing algorithm in Shore-MT.

4th week: Implementation, a first deliverable come out: DEADLINE 1.

5th week: Try to scale the implementation to different architectures, identify performance bottlenecks. 

6th week: Implement the scalability tricks, new algorithms, and architectural improvements, targeting at NUMA and cc-NUMA architecture. Test the scalability on real clusters and real data. Identify performance bottlenecks.

7th week: More improvements on performance.

8th week: More improvements. Comparison with other systems, a second deliverable: DEADLINE 2.

9th week: Exploration on lock free concurrency control algorithms.

 

Risks to success:

Shore-MT is a relatively complex piece of code. The main risk is that we may fail to achieve scalability for a lock-free implementation for a particular architecture, such as NUMA. But this is not very likely to happen, based on our previous experiences.

 

Work packages and assign to team members:

 

Tong Che:  working on algorithms and design alternatives, especially for NUMA and cc-NUMA architecture. Comparision of different synchronization primitives. Performance testing. Providing code for core algorithms.

 

Zhicong Huang: Providing code for core systems, writing test cases for indexing algorithms, preparing test data, deploying the system on real clusters, and make design decision based on performance tests.

 

Cheng Wang: working on indexing algorithms, providing code for these algorithms, writing performance tests and make choices based on these tests.