FPTree: A hybrid SCM-DRAM persistent and concurrent B-Tree for Storage Class Memory

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

  • Ismail Oukid - , TUD Dresden University of Technology, SAP Research (Author)
  • Johan Lasperas - , SAP Research (Author)
  • Anisoara Nica - , SAP Research (Author)
  • Thomas Willhalm - , Intel (Author)
  • Wolfgang Lehner - , SAP Research (Author)

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 languageEnglish
Title of host publicationSIGMOD '16: Proceedings of the 2016 International Conference on Management of Data
Pages371-386
Number of pages16
Volume2016
ISBN (electronic)978-1-4503-3531-7
Publication statusPublished - 26 Jun 2016
Peer-reviewedYes
Externally publishedYes

Publication series

SeriesMOD: International Conference on Management of Data (SIGMOD)

Conference

Title2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016
Duration26 June - 1 July 2016
CitySan Francisco
CountryUnited States of America

External IDs

ORCID /0000-0001-8107-2775/work/142253586

Keywords

ASJC Scopus subject areas