Shimin Chen
Abstract
Computer systems in the near future are expected to have <u>N</u>on-<u>V</u>olatile <u>M</u>ain <u>M</u>emory (NVMM), enabled by a new generation of <u>N</u>on-<u>V</u>olatile <u>M</u>emory (NVM) technologies, such as Phase Change Memory (PCM), STT-MRAM, and Memristor. The non-volatility property has the promise to persist in-memory data structures for instantaneous failure recovery. However, realizing such promise requires a careful design to ensure that in-memory data structures are in known consistent states after failures.
This paper studies persistent in-memory B+-Trees as B+-Trees are widely used in database and data-intensive systems. While traditional techniques, such as undo-redo logging and shadowing, support persistent B+-Trees, we find that they incur drastic performance overhead because of extensive NVM writes and CPU cache flush operations. PCM-friendly B+-Trees with unsorted leaf nodes help mediate this issue, but the remaining overhead is still large. In this paper, we propose write atomic B+-Trees (wB+-Trees), a new type of main-memory B+-Trees, that aim to reduce such overhead as much as possible. wB+-Tree nodes employ a small indirect slot array and/or a bitmap so that most insertions and deletions do not require the movement of index entries. In this way, wB+-Trees can achieve node consistency either through atomic writes in the nodes or by redo-only logging. We model fast NVM using DRAM on a real machine and model PCM using a cycle-accurate simulator. Experimental results show that compared with previous persistent B+-Tree solutions, wB+-Trees achieve up to 8.8x speedups on DRAM-like fast NVM and up to 27.1x speedups on PCM for insertions and deletions while maintaining good search performance. Moreover, we replaced Memcached's internal hash index with tree indices. Our real machine Memcached experiments show that wB+-Trees achieve up to 3.8X improvements over previous persistent tree structures with undo-redo logging or shadowing.
- R. Agrawal and H. V. Jagadish. Recovery algorithms for database machines with nonvolatile main memory. In IWDM, pages 269--285, 1989. Google Scholar
Digital Library
- 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). JETC, 9(2): 13, 2013. Google ScholarDigital Library
- R. Barber, P. Bendel, M. Czech, O. Draese, F. Ho, N. Hrle, S. Idreos, M.-S. Kim, O. Koeth, J.-G. Lee, T. T. Li, G. M. Lohman, K. Morfonios, R. Müller, K. Murthy, I. Pandis, L. Qiao, V. Raman, S. Szabo, R. Sidle, and K. Stolze. Blink: Not your father's database! In BIRTE, pages 1--22, 2011.Google Scholar
- G. W. Burr, M. J. Breitwisch, M. Franceschini, D. Garetto, K. Gopalakrishnan, B. Jackson, B. Kurdi, C. Lam, L. A. Lastras, A. Padilla, B. Rajendran, S. Raoux, and R. S. Shenoy. Phase change memory technology. J. Vacuum Science, 28(2), 2010.Google Scholar
- G. W. Burr, B. N. Kurdi, J. C. Scott, C. H. Lam, K. Gopalakrishnan, and R. S. Shenoy. Overview of candidate device technologies for storage-class memory. IBM J. Res. Dev., 52(4): 449--464, July 2008. Google ScholarDigital Library
- S. Chen, P. B. Gibbons, and T. C. Mowry. Improving index performance through prefetching. In SIGMOD, 2001. Google ScholarDigital Library
- S. Chen, P. B. Gibbons, and S. Nath. Rethinking database algorithms for phase change memory. In CIDR, 2011.Google Scholar
- 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. In ASPLOS, 2011. Google ScholarDigital Library
- J. Condit, E. B. Nightingale, C. Frost, E. Ipek, B. C. Lee, D. Burger, and D. Coetzee. Better I/O through byte-addressable, persistent memory. In SOSP, 2009. Google ScholarDigital Library
- C. Diaconu, C. Freedman, E. Ismert, P.-Å. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL server's memory-optimized OLTP engine. In SIGMOD Conference, 2013. Google ScholarDigital Library
- E. Doller. Phase change memory and its impacts on memory hierarchy. http://www.pdl.cmu.edu/SDI/2009/slides/Numonyx.pdf, 2009.Google Scholar
- R. A. Hankins and J. M. Patel. Effect of node size on the performance of cache-conscious B+-trees. In SIGMETRICS, 2003. Google ScholarDigital Library
- Intel Corp. Intel 64 and ia-32 architectures software developers manual. Order Number: 325462-047US, June 2013.Google Scholar
- ITRS. International technology roadmap for semiconductors (2011 edition executive summary). http://www.itrs.net/Links/2011ITRS/2011Chapters/2011ExecSum.pdf.Google Scholar
- B. C. Lee, E. Ipek, O. Mutlu, and D. Burger. Architecting phase change memory as a scalable DRAM alternative. In ISCA, 2009. Google ScholarDigital Library
- D. E. Lowell and P. M. Chen. Free transactions with Rio Vista. Operating Systems Review, 31, 1997. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD Conference, pages 135--146, 2010. Google ScholarDigital Library
- V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. S. III, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. In TRANSACT, 2006.Google Scholar
- Memcached. http://memcached.org/.Google Scholar
- D. Narayanan and O. Hodson. Whole-system persistence. In ASPLOS, 2012. Google ScholarDigital Library
- W. T. Ng and P. M. Chen. Integrating reliable memory in databases. In VLDB, 1997. Google ScholarDigital Library
- J. K. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazières, S. Mitra, A. Narayanan, D. Ongaro, G. M. Parulkar, M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman. The case for ramcloud. Commun. ACM, 54(7): 121--130, 2011. Google ScholarDigital Library
- S. Pelley, T. F. Wenisch, B. T. Gold, and B. Bridge. Storage management in the NVRAM era. PVLDB, 7(2): 121--132, 2013. Google ScholarDigital Library
- H. Plattner. The impact of columnar in-memory databases on enterprise systems (keynote). In VLDB, 2014. Google ScholarDigital Library
- PTLsim. http://www.ptlsim.org/.Google Scholar
- M. K. Qureshi, V. Srinivasan, and J. A. Rivers. Scalable high performance main memory system using phase-change memory technology. In ISCA, 2009. Google ScholarDigital Library
- R. Ramakrishnan and J. Gehrke. Database management systems (3. ed.). McGraw-Hill, 2003. Google ScholarDigital Library
- J. Rao and K. A. Ross. Making B+-trees cache conscious in main memory. In SIGMOD, 2000. 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 FAST, 2011. Google ScholarDigital Library
- S. Viglas. Write-limited sorts and joins for persistent memory. PVLDB, 7(5): 413--424, 2014. Google ScholarDigital Library
- H. Volos, A. J. Tack, and M. M. Swift. Mnemosyne: lightweight persistent memory. In ASPLOS, 2011. Google ScholarDigital Library
- M. Wu and W. Zwaenepoel. eNVy: a non-volatile, main memory storage system. In ASPLOS, 1994. Google ScholarDigital Library
- X. Wu and A. L. N. Reddy. Scmfs: a file system for storage class memory. In SC, 2011. Google ScholarDigital Library
- J. J. Yang and R. S. Williams. Memristive devices in computing system: Promises and challenges. JETC, 9(2): 11, 2013. Google ScholarDigital Library
- M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauly, M. J. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI, pages 15--28, 2012. Google ScholarDigital Library
- P. Zhou, B. Zhao, J. Yang, and Y. Zhang. A durable and energy efficient main memory using phase change memory technology. In ISCA, 2009. Google ScholarDigital Library
Index Terms
- Persistent B+-trees in non-volatile main memory
Recommendations
Redesign the Memory Allocator for Non-Volatile Main Memory
Special Issue on Hardware and Algorithms for Learning On-a-chip and Special Issue on Alternative Computing SystemsThe non-volatile memory (NVM) has the merits of byte-addressability, fast speed, persistency and low power consumption, which make it attractive to be used as main memory. Commonly, user process dynamically acquires memory through memory allocators. ...
Register allocation for write activity minimization on non-volatile main memory
ASPDAC '11: Proceedings of the 16th Asia and South Pacific Design Automation ConferenceNon-volatile memories are good candidates for DRAM replacement as main memory in embedded systems and they have many desirable characteristics. Nevertheless, the disadvantages of non-volatile memory co-exist with its advantages. First, the lifetime of ...
File-Based Memory Management for Non-volatile Main Memory
COMPSAC '13: Proceedings of the 2013 IEEE 37th Annual Computer Software and Applications ConferenceActive research and development efforts on byte addressable non-volatile (NV) memory technologies, such as STT-RAM, PCM, and ReRAM, have been conducted in recent years. Because they are byte addressable, they can be used as main memory by directly ...
Comments