187
© The Author(s) 2020
S. Scargall, Programming Persistent Memory, https://doi.org/10.1007/978-1-4842-4932-1_11
CHAPTER 11
Designing Data Structures
for Persistent Memory
Taking advantage of the unique characteristics of persistent memory, such as byte
addressability, persistence, and update in place, allows us to build data structures that
are much faster than any data structure requiring serialization or flushing to a disk.
However, this comes at a cost. Algorithms must be carefully designed to properly persist
data by flushing CPU caches or using non-temporal stores and memory barriers to
maintain data consistency. This chapter describes how to design such data structures
and algorithms and shows what properties they should have.
Contiguous Data Structures and Fragmentation
Fragmentation is one of the most critical factors to consider when designing a data
structure for persistent memory due to the length of heap life. A persistent heap can
live for years with different versions of an application. In volatile use cases, the heap is
destroyed when the application exits. The life of the heap is usually measured in hours,
days, or weeks.
Using file-backed pages for memory allocation makes it difficult to take advantage
of the operating system–provided mechanisms for minimizing fragmentation, such as
presenting discontinuous physical memory as a contiguous virtual region. It is possible
to manually manage virtual memory at a low granularity, producing a page-level
defragmentation mechanism for objects in user space. But this mechanism could lead to
complete fragmentation of physical memory and an inability to take advantage of huge
pages. This can cause an increased number of translation lookaside buffer (TLB) misses,
which significantly slows down the entire application. To make effective use of persistent
memory, you should design data structures in a way that minimizes fragmentation.
© The Author(s) 2020
S. Scargall, Programming Persistent Memory, https://doi.org/10.1007/978-1-4842-4932-1_11
CHAPTER 11
Designing Data Structures
for Persistent Memory
Taking advantage of the unique characteristics of persistent memory, such as byte
addressability, persistence, and update in place, allows us to build data structures that
are much faster than any data structure requiring serialization or flushing to a disk.
However, this comes at a cost. Algorithms must be carefully designed to properly persist
data by flushing CPU caches or using non-temporal stores and memory barriers to
maintain data consistency. This chapter describes how to design such data structures
and algorithms and shows what properties they should have.
Contiguous Data Structures and Fragmentation
Fragmentation is one of the most critical factors to consider when designing a data
structure for persistent memory due to the length of heap life. A persistent heap can
live for years with different versions of an application. In volatile use cases, the heap is
destroyed when the application exits. The life of the heap is usually measured in hours,
days, or weeks.
Using file-backed pages for memory allocation makes it difficult to take advantage
of the operating system–provided mechanisms for minimizing fragmentation, such as
presenting discontinuous physical memory as a contiguous virtual region. It is possible
to manually manage virtual memory at a low granularity, producing a page-level
defragmentation mechanism for objects in user space. But this mechanism could lead to
complete fragmentation of physical memory and an inability to take advantage of huge
pages. This can cause an increased number of translation lookaside buffer (TLB) misses,
which significantly slows down the entire application. To make effective use of persistent
memory, you should design data structures in a way that minimizes fragmentation.