FPTree swMATH ID: 29930 Software Authors: Ismail Oukid; Johan Lasperas; Anisoara Nica; Thomas Willhalm; Wolfgang Lehner Description: FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory. 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. Homepage: https://dl.acm.org/citation.cfm?id=2915251 Related Software: Proteus; ThyNVM; NOVA; WORT; DudeTM; WHISPER; EDO; SoftWrAP; ATOM; Mnemosyne; NICO; gem5 Cited in: 1 Publication Cited by 5 Authors 1 Feng, Dan 1 Liu, Jingning 1 Tong, Wei 1 Wei, Xueliang 1 Ye, Liuqing Cited in 1 Serial 1 IEEE Transactions on Computers Cited in 1 Field 1 Computer science (68-XX) Citations by Year