2017 · 15 citations · 29 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureData StructuresStorage SystemsCache CoherenceConcurrency AnalysisConcurrency ControlMemory HierarchyMemory Hierarchy DesignMemory Hierarchy OptimizationConcurrent Search TreesContention ManagementContention ResolutionHardware Transactional MemoryKey-value StorageKey-value StoresMulti-core ComputingTransactional Memory
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.
29
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Benchmarking cloud serving systems with YCSB
Brian F. Cooper, Adam Silberstein, Erwin Tam et al. · 2010 · 3.6K citations
Nicholas Nethercote, Julian Seward · 2007 · 2.3K citations
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
Speedy transactions in multicore in-memory databases
Stephen Tu, Wenting Zheng, Eddie Kohler et al. · 2013 · 527 citations · Full text