Anastasia Braginsky
Erez Petrank
ABSTRACT
Lock-free data structures provide a progress guarantee and are known for facilitating scalability, avoiding deadlocks and livelocks, and providing guaranteed system responsiveness. In this paper we present a design for a lock-free balanced tree, specifically, a B+tree. The B+tree data structure has an important practical applications, and is used in various storage-system products. As far as we know this is the first design of a lock-free, dynamic, and balanced tree, that employs standard compare-and-swap operations.
- R. Bayer and M. Schkolnick. Concurrency of operations on b-trees. Acta Informatica, 9, 1977.Google Scholar
- M. A. Bender, J. T. Fineman, S. Gilbert, and B. C. Kuszmaul. Concurrent cache-oblivious b-tree. SPAA, 2005. Google ScholarDigital Library
- A. Braginsky and E. Petrank. Lock-free B+tree (full version). http://www.cs.technion.ac.il/ erez/Papers/lfbtree-full.pdf.Google Scholar
- A. Braginsky and E. Petrank. Lock-free linked lists with improved locality. ICDCN, 2011.Google Scholar
- S. Chen, P. B. Gibbons, T. C. Mowry, and G. Valentin. Fractal prefetching b+-trees: Optimizing both cache and disk performance. SIGMOD, 2002. Google ScholarDigital Library
- D. Comer. The ubiquitous b-tree. ACM Computing Surverys, 11(2), 1979. Google ScholarDigital Library
- F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search tree. PODC, 2010. Google ScholarDigital Library
- K. Fraser. Practical lock-freedom, 2004. Technical Report UCAM-CL-TR-579, University of Cambridge, Computer Laboratory.Google Scholar
- T. L. Harris. A pragmatic implementation of non-blocking linked-lists. DISC, 2001. Google ScholarDigital Library
- M. Herlihy. Wait-free synchronization. TOPLAS, 13(1):124--149, 1991. Google ScholarDigital Library
- M. Herlihy and J. Wing. Linearizability: a correctness condition for concurrent objects. TOPLAS, 12(3):463--492, 1990. Google ScholarDigital Library
- M. M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. TPDS, 15(6):491--504, 2004. Google ScholarDigital Library
- E. Petrank, M. Musuvathi, and B. Steensgaard. Progress guarantee for parallel programs via bounded lock-freedom. PLDI, pages 144--154, 2009. Google ScholarDigital Library
- J. Rao and K. A. Ross. Cache conscious indexing for decision-support in main memory. VLDB, 1999. Google ScholarDigital Library
- O. Rodeh. B-trees, shadowing, and clones. ACM Transactions on Storage Journal, 2008. Google ScholarDigital Library
Index Terms
- A lock-free B+tree
Recommendations
Lock-Free Data-Structure Iterators
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205Concurrent data structures are often used with large concurrent software. An iterator that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from almost all concurrent data-...
Efficient lock-free binary search trees
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computingIn this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of ...
Lock-free Contention Adapting Search Trees
SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and ArchitecturesConcurrent key-value stores with range query support are crucial for the scalability and performance of many applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity ...
Comments