NV-Heaps: Safe, Fast, Persistent Objects
Persistent, user-defined objects present an attractive abstraction for working with non-volatile program state. However, the slow speed of persistent storage (i.e., spinning disk) has limited their performance, and programmers are often stuck using un-typed file-based IO operations. 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 data 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 created a lightweight, high-performance persistent object system called NV-Heaps. NV-Heaps provides programmers with a familiar set of simple primitives (i.e., objects, pointers, memory allocation, and atomic sections) that make it easy to build fast, robust, flexible non-volatile data structures. NV-Heaps avoids OS overheads on all common case access operations and protects programmers from common mistakes: NV-Heaps provides automatic garbage collection, pointer safety, and protection from several novel kinds of bugs that non-volatile objects make possible.
We have implemented search trees, hash tables, sparse graphs, and arrays using NV-Heaps, BerkeleyDB, and Stasis. Our results show that NV-Heaps 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. The cost of enforcing safety guarantees with NV-Heaps is modest and the required system support is minimal.
|The NV-Heaps system stack allows read and write operations to bypass the OS entirely.||Accessing a linked list in a NV-Heap involves both volatile and non-volatile pointers. Objects are logged for safety and concurrency.|
NV-Heaps: Making Persistent Objects Fast and Safe With Next-Generation, Non-Volatile Memories
Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems, 2011.