FPTree: A hybrid SCM-DRAM persistent and concurrent B-Tree for Storage Class Memory
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
Abstract
The advent of Storage Class Memory (SCM) is driving a rethink of storage systems towards a single-level architecture where memory and storage are merged. In this context, several works have investigated how to design persistent trees in SCM as a fundamental building block for these novel systems. However, these trees are significantly slower than DRAM-based counterparts since trees are latency-sensitive and SCM exhibits higher latencies than DRAM. In this paper we propose a novel hybrid SCM-DRAM persistent and concurrent B+-Tree, named Fingerprinting Persistent Tree (FPTree) that achieves similar performance to DRAM-based counterparts. In this novel design, leaf nodes are persisted in SCM while inner nodes are placed in DRAM and rebuilt upon recovery. The FPTree uses Fingerprinting, a technique that limits the expected number of in-leaf probed keys to one. In addition, we propose a hybrid concurrency scheme for the FPTree that is partially based on Hardware Transactional Memory. We conduct a thorough performance evaluation and show that the FPTree outperforms state-of-the-art persistent trees with different SCM latencies by up to a factor of 8.2. Moreover, we show that the FPTree scales very well on a machine with 88 logical cores. Finally, we integrate the evaluated trees in memcached and a prototype database. We show that the FPTree incurs an almost negligible performance overhead over using fully transient data structures, while significantly outperforming other persistent trees.
Details
Original language | English |
---|---|
Title of host publication | SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data |
Pages | 371-386 |
Number of pages | 16 |
Volume | 2016 |
ISBN (electronic) | 978-1-4503-3531-7 |
Publication status | Published - 26 Jun 2016 |
Peer-reviewed | Yes |
Externally published | Yes |
Publication series
Series | MOD: International Conference on Management of Data (SIGMOD) |
---|
Conference
Title | 2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016 |
---|---|
Duration | 26 June - 1 July 2016 |
City | San Francisco |
Country | United States of America |
External IDs
ORCID | /0000-0001-8107-2775/work/142253586 |
---|