ABSTRACT
Non-Volatile Memory (NVM) technologies exhibit 4X the read access latency of conventional DRAM. When the working set does not fit in the processor cache, this latency gap between DRAM and NVM leads to more than 2X runtime increase for queries dominated by latency-bound operations such as index joins and tuple reconstruction. We explain how to easily hide NVM latency by interleaving the execution of parallel work in index joins and tuple reconstruction using coroutines. Our evaluation shows that interleaving applied to the non-trivial implementations of these two operations in a production-grade codebase accelerates end-to-end query runtimes on both NVM and DRAM by up to 1.7X and 2.6X respectively, thereby reducing the performance difference between DRAM and NVM by more than 60%.
- 2013. Intel Memory Latency Checker. http://www.intel.com/software/mlc {Online; accessed 18-March-2019}.Google Scholar
- 2019. Aerospike 4.5: Persistent Memory and Compression. https://www.aerospike.com/blog/aerospike-4-5-persistent-memory-compression/ {Online; accessed 18-March-2019}.Google Scholar
- 2019. How to configure persistent memory (PMEM) for SQL Server on Linux. https://docs.microsoft.com/en-us/sql/linux/sql-server-linux-configure-pmem?view=sqlallproducts-allversions {Online; accessed 18-March-2019}.Google Scholar
- 2019. Intel Optane DC Persistent Memory Module. www.intel.com/optanedcpersistentmemory {Online; accessed 20-March-2019}.Google Scholar
- 2019. Oracle TimesTen In-Memory Database. https://www.oracle.com/database/technologies/related/timesten.html {Online; accessed 18-March-2019}.Google Scholar
- 2019. Working Draft, Standard for Programming Language C++. http://eel.is/c++draft/dcl.fct.def.coroutine {Online; accessed 25-March-2019}.Google Scholar
- Mihnea Andrei, Christian Lemke, Günter Radestock, Robert Schulze, Carsten Thiel, Rolando Blanco, Akanksha Meghlan, Muhammad Sharique, Sebastian Seifert, Surendra Vishnoi, Daniel Booss, Thomas Peh, Ivan Schreter, Werner Thesing, Mehul Wagle, and Thomas Willhalm. 2017. SAP HANA Adoption of Non-volatile Memory. Proc. VLDB Endow. 10, 12 (Aug. 2017), 1754--1765. Google ScholarDigital Library
- Joy Arulraj, Justin Levandoski, Umar Farooq Minhas, and Per-Ake Larson. 2018. BzTree: A high-performance latch-free range index for non-volatile memory. Proceedings of the VLDB Endowment 11, 5 (2018), 553--565.Google ScholarDigital Library
- Joy Arulraj and Andrew Pavlo. 2017. How to Build a Non-Volatile Memory Database Management System. In Proceedings of the 2017 ACM International Conference on Management of Data. ACM, 1753--1758.Google ScholarDigital Library
- Joy Arulraj, Matthew Perron, and Andrew Pavlo. 2016. Write-behind logging. PVLDB 10, 4 (2016), 337--348.Google ScholarDigital Library
- Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, and Todd C. Mowry. 2007. Improving Hash Join Performance Through Prefetching. ACM Trans. Database Syst. 32, 3 (2007). Google ScholarDigital Library
- Shimin Chen, Phillip B Gibbons, and Suman Nath. 2011. Rethinking Database Algorithms for Phase Change Memory. In Fifth Biennial Conference on Innovative Data Systems Research (CIDR). 21--31.Google Scholar
- Shimin Chen and Qin Jin. 2015. Persistent B+-Trees in Non-Volatile Main Memory. Proceedings of the VLDB Endowment 8, 7 (2015), 786--797. Google ScholarDigital Library
- Xiangyu Dong, Xiaoxia Wu, Guangyu Sun, Yuan Xie, Helen Li, and Yiran Chen. 2008. Circuit and microarchitecture evaluation of 3D stacking magnetic RAM (MRAM) as a universal memory replacement. In 45th ACM/IEEE Design Automation Conference. IEEE, 554--559. Google ScholarDigital Library
- B Govoreanu, GS Kar, YY Chen, V Paraschiv, S Kubicek, A Fantini, IP Radu, L Goux, S Clima, R Degraeve, et al. 2011. 10X 10nm 2 Hf/HfO x crossbar resistive RAM with excellent performance, reliability and low-energy operation. In IEEE International Electron Devices Meeting (IEDM). IEEE, 31--6.Google Scholar
- Mark Horowitz, Margaret Martonosi, Todd C. Mowry, and Michael D. Smith. 1996. Informing Memory Operations: Providing Memory Performance Feedback in Modern Processors. SIGARCH Comput. Archit. News 24, 2 (May 1996), 260--270. Google ScholarDigital Library
- Stratos Idreos, Martin L. Kersten, and Stefan Manegold. 2009. Self-organizing Tuple Reconstruction in Column-stores. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data (SIGMOD '09). ACM, New York, NY, USA, 297--308.Google ScholarDigital Library
- Intel Corporation. 2019. Intel® 64 and IA-32 Architectures Optimization Reference Manual.Google Scholar
- Joseph Izraelevitz, Jian Yang, Lu Zhang, Juno Kim, Xiao Liu, Amirsaman Memaripour, Yun Joon Soh, Zixuan Wang, Yi Xu, Subramanya R Dulloor, et al. 2019. Basic Performance Measurements of the Intel Optane DC Persistent Memory Module. arXiv preprint arXiv: 1903.05714 (2019).Google Scholar
- Daniel J. Abadi, Daniel S. Myers, David J. DeWitt, and Samuel Madden. 2007. Materialization Strategies in a Column-Oriented DBMS. Proceedings - International Conference on Data Engineering, 466--475.Google ScholarCross Ref
- Christopher Jonathan, Umar Farooq Minhas, James Hunter, Justin Levandoski, and Gor Nishanov. 2018. Exploiting Coroutines to Attack the "Killer Nanoseconds". PVLDB 11, 11 (July 2018), 1702--1714. Google ScholarDigital Library
- Hideaki Kimura. 2015. FOEDUS: OLTP engine for a thousand cores and NVRAM. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 691--706. Google ScholarDigital Library
- Vladimir Kiriansky, Haoran Xu, Martin Rinard, and Saman Amarasinghe. 2018. Cimple: Instruction and Memory Level Parallelism: A DSL for Uncovering ILP and MLP. In Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques (PACT '18). ACM, New York, NY, USA, Article 30, 16 pages. Google ScholarDigital Library
- Onur Kocberber, Babak Falsafi, and Boris Grot. 2015. Asynchronous Memory Access Chaining. PVLDB 9, 4 (2015), 252--263. Google ScholarDigital Library
- James Laudon, Anoop Gupta, and Mark Horowitz. 1994. Interleaving: A Multithreading Technique Targeting Multiprocessors and Workstations. In Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VI). ACM, New York, NY, USA, 308--318. Google ScholarDigital Library
- Benjamin C Lee, Ping Zhou, Jun Yang, Youtao Zhang, Bo Zhao, Engin Ipek, Onur Mutlu, and Doug Burger. 2010. Phase-Change Technology and the Future of Main Memory. IEEE Micro 30, 1 (2010). Google ScholarDigital Library
- Se Kwon Lee, K Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H Noh. 2017. WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems. In 15th USENIX Conference on File and Storage Technologies (FAST 17). 257--270. Google ScholarDigital Library
- Lucas Lersch, Ismail Oukid, Ivan Schreter, and Wolfgang Lehner. 2017. Rethinking DRAM caching for LSMs in an NVRAM environment. In European Conference on Advances in Databases and Information Systems. Springer, 326--340.Google ScholarCross Ref
- Ismail Oukid, Daniel Booss, Wolfgang Lehner, Peter Bumbulis, and Thomas Willhalm. 2014. SOFORT: A hybrid SCM-DRAM storage engine for fast data recovery. In Proceedings of the Tenth International Workshop on Data Management on New Hardware. ACM, 8.Google ScholarDigital Library
- Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. 2016. FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory. In Proceedings of the 2016 ACM International Conference on Management of Data (SIGMOD). ACM, 371--386.Google ScholarDigital Library
- Georgios Psaropoulos, Thomas Legler, Norman May, and Anastasia Ailamaki. 2017. Interleaving with Coroutines: A Practical Approach for Robust Index Joins. PVLDB 11, 2 (Oct. 2017), 230--242.Google Scholar
- Georgios Psaropoulos, Thomas Legler, Norman May, and Anastasia Ailamaki. 2018. Interleaving with coroutines: a systematic and practical approach to hide memory latency in index joins. The VLDB Journal (14 Dec 2018).Google Scholar
- Richard Smith and Gor Nishanov. 2018. Halo: coroutine Heap Allocation eLision Optimization: the joint response. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0981r0.html {Online; accessed 15-March-2019}.Google Scholar
- Alexander van Renen, Viktor Leis, Alfons Kemper, Thomas Neumann, Takushi Hashida, Kazuichi Oe, Yoshiyasu Doi, Lilian Harada, and Mitsuru Sato. 2018. Managing non-volatile memory in database systems. In Proceedings of the 2018 International Conference on Management of Data. ACM, 1541--1555.Google ScholarDigital Library
- Stratis D Viglas. 2014. Write-limited sorts and joins for persistent memory. Proceedings of the VLDB Endowment 7, 5 (2014), 413--424. Google ScholarDigital Library
- J. Yang, Q. Wei, C. Wang, C. Chen, K. Yong, and B. He. 2015. NV-Tree: A Consistent and Workload-adaptive Tree Structure for Non-volatile Memory. IEEE Trans. Comput. PP, 99 (2015).Google Scholar
Index Terms
- Bridging the Latency Gap between NVM and DRAM for Latency-bound Operations
Recommendations
NVM duet: unified working memory and persistent store architecture
ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systemsEmerging non-volatile memory (NVM) technologies have gained a lot of attention recently. The byte-addressability and high density of NVM enable computer architects to build large-scale main memory systems. NVM has also been shown to be a promising ...
NVM duet: unified working memory and persistent store architecture
ASPLOS '14Emerging non-volatile memory (NVM) technologies have gained a lot of attention recently. The byte-addressability and high density of NVM enable computer architects to build large-scale main memory systems. NVM has also been shown to be a promising ...
NVM duet: unified working memory and persistent store architecture
ASPLOS '14Emerging non-volatile memory (NVM) technologies have gained a lot of attention recently. The byte-addressability and high density of NVM enable computer architects to build large-scale main memory systems. NVM has also been shown to be a promising ...
Comments