NV-Heaps: Making Persistent Objects Fast and Safe with Next-Generation Non-Volatile Memories

Persistent, user-defined objects present an attractive abstraction for working with non-volatile program state. However, the slow speed of persistent storage (i.e., disk) has limited their performance. Fast, byte-addressable, non-volatile technologies, such as phase change memory, will remove this constraint and allow programmers to build high-performance, persistent structures in non-volatile storage that is almost as fast as DRAM. However, existing persistent object systems are ill-suited to these memories because the assumption that storage is slow drives many aspects of their design. Creating structures that are flexible and robust in the face of application and system failure, while minimizing software overheads, is challenging. The system must be lightweight enough to expose the performance of the underlying memories, but it also must avoid familiar bugs such as dangling pointers, multiple free()s, and locking errors in addition to unique types of hard-to-find pointer safety bugs that only arise with persistent objects. These bugs are especially dangerous since any corruption they cause will be permanent.

We have implemented a lightweight, high-performance persistent object system called NV-heaps that prevents these errors and provides a model for persistence that is easy to use and reason about. We implement search trees, hash tables, sparse graphs, and arrays using NV-heaps, BerkeleyDB, and Stasis. Our results show that NV-heap performance scales with thread count and that data structures implemented using NV-heaps out-perform BerkeleyDB and Stasis implementations by 32x and 244x, respectively, when running on the same memory technology. We also quantify the cost of enforcing the safety guarantees that NV-heaps provides and measure the costs for NV-heap primitive operations.