Database Seminar

Monday, January 29, 2018 - 4:30pm to 6:00pm

Location:

8102 Gates Hillman Centers

Speaker:

ZIQI WANG, Ph.D. Student https://www.linkedin.com/in/ziqi-wang-b54274118

The Cost of Lock-Freedom and its Implication for In-Memory Database Indices

Lock-free data structures have long been rumored to provide better performance and scalability than their lock-based counterparts. On the other hand, however, there are state-of-the-art in-memory indices using various fine-grained synchronization techniques that outperform the classical lock coupling implementation. In this talk, we investigate into a concrete, optimized implementation of a lock-free B+Tree, the Bw-Tree[1], and then conduct an apple-to-apple comparison between the Bw-Tree and other state-of-the-art in-memory indices such as the Skiplist[2], MassTree[3], BTree (OLC[4]) and ART[5] (OLC). We also present a detailed dissection of the composition of Bw-Tree’s performance figures, using the BTree (OLC) as a baseline. We believe our study could provide more insight into the performance characteristic of both worlds with or without locks, and serve as a reference for system designers to measure trade-offs between different index types.

[1] Levandoski, Justin J., David B. Lomet, and Sudipta Sengupta. "The Bw-Tree: A B-tree for new hardware platforms." In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 302-313. IEEE, 2013.

[2] Crain, Tyler, Vincent Gramoli, and Michel Raynal. "No hot spot non-blocking skip list." In Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on, pp. 196-205. IEEE, 2013.

[3] Mao, Yandong, Eddie Kohler, and Robert Tappan Morris. "Cache craftiness for fast multicore key-value storage." In Proceedings of the 7th ACM european conference on Computer Systems, pp. 183-196. ACM, 2012. [

4] Leis, Viktor, Florian Scheibner, Alfons Kemper, and Thomas Neumann. "The ART of practical synchronization." In Proceedings of the 12th International Workshop on Data Management on New Hardware, p. 3. ACM, 2016.

[5] Leis, Viktor, Alfons Kemper, and Thomas Neumann. "The adaptive radix tree: ARTful indexing for main-memory databases." In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 38-49. IEEE, 2013.

Event Website:

http://db.cs.cmu.edu/events/db-seminar-spring-2018-ziqi-wang

For More Information, Contact:

Keywords:

Seminar Series