Ismail Oukid
Anisoara Nica
Wolfgang Lehner
Editorial Notes
Computationally Replicable. The experimental results of this paper were replicated by a SIGMOD Review Committee and were found to support the central results reported in the paper. Details of the review process are found here
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.
Supplemental Material
Available for Download
Rights information
Benchmarks, Data
- SR. Dulloor. phSystems and Applications for Persistent Memory. PhD Thesis, 2016. https://smartech.gatech.edu/bitstream/handle/1853/54396/DULLOOR-DISSERTATION-2015.pdf.Google Scholar
- Intel® Architecture Instruction Set Extensions Programming Reference. Technical report, 2015. http://software.intel.com/en-us/intel-isa-extensions.Google Scholar
- SNIA NVM Programming Model V1.1. Technical report, 2015. http://www.snia.org/sites/default/files/NVMProgrammingModel_v1.1.pdf.Google Scholar
- D. Apalkov, A. Khvalkovskiy, S. Watts, V. Nikitin, X. Tang, D. Lottis, K. Moon, X. Luo, E. Chen, A. Ong, A. Driskill-Smith, and M. Krounbi. Spin-transfer torque magnetic random access memory (stt-mram). ACM J. Emerg. Technol. Comput. Syst., 9(2), 2013. Google ScholarDigital Library
- J. Arulraj, A. Pavlo, and S. R. Dulloor. Let's talk about storage & recovery methods for non-volatile memory database systems. In ACM SIGMOD, 2015. Google ScholarDigital Library
- G. W. Burr, M. J. Breitwisch, M. Franceschini, D. Garetto, K. Gopalakrishnan, B. Jackson, B. Kurdi, C. Lam, L. A. Lastras, A. Padilla, et al. Phase change memory technology. Journal of Vacuum Science & Technology B, 28(2), 2010.Google ScholarCross Ref
- A. Chatzistergiou, M. Cintra, and S. D. Viglas. Rewind: Recovery write-ahead system for in-memory non-volatile data-structures. PVLDB, 8(5), 2015. Google ScholarDigital Library
- S. Chen, P. B. Gibbons, and S. Nath. Rethinking database algorithms for phase change memory. In CIDR, 2011.Google Scholar
- S. Chen and Q. Jin. Persistent b+-trees in non-volatile main memory. PVLDB, 8(7), 2015. Google ScholarDigital Library
- J. Coburn, A. M. Caulfield, A. Akel, L. M. Grupp, R. K. Gupta, R. Jhala, and S. Swanson. Nv-heaps: Making persistent objects fast and safe with next-generation, non-volatile memories. ACM SIGPLAN Not., 47(4), 2011. Google ScholarDigital Library
- J. Condit, E. B. Nightingale, C. Frost, E. Ipek, B. Lee, D. Burger, and D. Coetzee. Better i/o through byte-addressable, persistent memory. In ACM SOSP, 2009. Google ScholarDigital Library
- S. Dulloor, S. Kumar, A. Keshavamurthy, P. Lantz, R. Sankaran, J. Jackson, and D. Subbareddy. System software for persistent memory. In EuroSys, 2014. Google ScholarDigital Library
- R. Fang, H.-I. Hsiao, B. He, C. Mohan, and Y. Wang. High performance database logging using storage class memory. In IEEE ICDE, 2011. Google ScholarDigital Library
- G. Graefe. A survey of b-tree locking techniques. ACM Transactions on Database Systems (TODS), 35(3):16, 2010. Google ScholarDigital Library
- G. Graefe. Modern b-tree techniques. Foundations and Trends in Databases, 3(4):203--402, 2011. Google ScholarDigital Library
- G. Graefe and H. Kimura. Orthogonal key-value locking. In BTW, 2015.Google Scholar
- T. Karnagel, R. Dementiev, R. Rajwar, K. Lai, T. Legler, B. Schlegel, and W. Lehner. Improving in-memory database index performance with intel(®) transactional synchronization extensions. In IEEE HPCA, 2014.Google Scholar
- H. Kimura. Foedus: Oltp engine for a thousand cores and nvram. In ACM SIGMOD, 2015. Google ScholarDigital Library
- J. J. Levandoski, D. B. Lomet, and S. Sengupta. The Bw-Tree: A B-tree for new hardware platforms. In IEEE ICDE, 2013. Google ScholarDigital Library
- D. Narayanan and O. Hodson. Whole-system persistence. In ASPLOS XVII, 2012. Google ScholarDigital Library
- I. Oukid, W. Lehner, T. Kissinger, T. Willhalm, and P. Bumbulis. Instant recovery for main-memory databases. In CIDR, 2015.Google Scholar
- S. Pelley, T. F. Wenisch, B. T. Gold, and B. Bridge. Storage Management in the NVRAM Era. PVLDB, 7(2), 2013. Google ScholarDigital Library
- J. Rao and K. A. Ross. Making B+- Trees cache conscious in main memory. In ACM SIGMOD. Google ScholarDigital Library
- S. Venkataraman, N. Tolia, P. Ranganathan, and R. H. Campbell. Consistent and durable data structures for non-volatile byte-addressable memory. In USENIX FAST, 2011. Google ScholarDigital Library
- S. Viglas. Write-limited sorts and joins for persistent memory. PVLDB, 7(5), 2014. Google ScholarDigital Library
- H. Volos, A. J. Tack, and M. M. Swift. Mnemosyne: Lightweight persistent memory. SIGPLAN Not., 47(4), 2011. Google ScholarDigital Library
- T. Wang and R. Johnson. Scalable logging through emerging non-volatile memory. PVLDB, 7(10), 2014. Google ScholarDigital Library
- J. Yang, Q. Wei, C. Wang, C. Chen, K. Yong, and B. He. Nv-tree: A consistent and workload-adaptive tree structure for non-volatile memory. IEEE Transactions on Computers, PP(99), 2015.Google Scholar
- J. J. Yang and R. S. Williams. Memristive devices in computing system: Promises and challenges. ACM J. Emerg. Technol. Comput. Syst., 9(2), 2013. Google ScholarDigital Library
- J. Zhao, S. Li, D. H. Yoon, Y. Xie, and N. P. Jouppi. Kiln: Closing the performance gap between systems with and without persistence support. In IEEE/ACM MICRO-46, 2013. Google ScholarDigital Library
Index Terms
- FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory
Recommendations
Brief Announcement: Hardware Transactional Storage Class Memory
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and ArchitecturesEmerging persistent memory technologies (generically referred to as Storage Class Memory or SCM) hold tremendous promise for accelerating popular data-management applications like in-memory databases. However, programmers now need to deal with ensuring ...
Continuous checkpointing of HTM transactions in NVM
ISMM 2017: Proceedings of the 2017 ACM SIGPLAN International Symposium on Memory ManagementThis paper addresses the challenges of coupling byte addressable non-volatile memory (NVM) and hardware transaction memory (HTM) in high-performance transaction processing. We first show that HTM transactions can be ordered using existing processor ...
Design of heterogeneously-integrated memory system with storage class memories and NAND flash memories
ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation ConferenceHeterogeneously-integrated memory system is configured with various types of storage class memories (SCMs) and NAND flash memories. SCMs are faster than NAND flash, and they are divided into memory and storage types with their characteristics. NAND ...
Comments