Open Access
- 26 January 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 23, 385-399
Abstract
While hardware transactional memory (HTM) has recently been adopted to construct efficient concurrent search tree structures, such designs fail to deliver scalable performance under contention. In this paper, we first conduct a detailed analysis on an HTM-based concurrent B+Tree, which uncovers several reasons for excessive HTM aborts induced by both false and true conflicts under contention. Based on the analysis, we advocate Eunomia, a design pattern for search trees which contains several principles to reduce HTM aborts, including splitting HTM regions with version-based concurrency control to reduce HTM working sets, partitioned data layout to reduce false conflicts, proactively detecting and avoiding true conflicts, and adaptive concurrency control. To validate their effectiveness, we apply such designs to construct a scalable concurrent B+Tree using HTM. Evaluation using key-value store benchmarks on a 20-core HTM-capable multi-core machine shows that Eunomia leads to 5X-11X speedup under high contention, while incurring small overhead under low contention.Keywords
Funding Information
- National Key Research and Development Program of China (2016YFB0800104)
- National Natural Science Foundation of China (61672160)
- ShanghaiScience andTechnologyDevelopment Funds (16JC1400801)
- NFS (CNS-1218117)
This publication has 28 references indexed in Scilit:
- Staring into the abyssProceedings of the VLDB Endowment, 2014
- On Developing Optimistic Transactional Lazy SetLecture Notes in Computer Science, 2014
- Speedy transactions in multicore in-memory databases2013
- Evaluation of Blue Gene/Q hardware support for transactional memories2012
- Cache craftiness for fast multicore key-value storage2012
- Towards Consistency Oblivious Programming2011
- Deletion Without Rebalancing in Balanced Binary Trees2010
- Dwarfs in the rearview mirrorProceedings of the VLDB Endowment, 2008
- A practical scalable distributed B-treeProceedings of the VLDB Endowment, 2008
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970