[DB Seminar] Spring 2018: Ziqi Wang

Event Date: Monday January 29, 2018
Event Time: 04:30pm EDT
Location: GHC 8102
Speaker: Ziqi Wang

Title: 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.