System-level Crash Safe Sorting on Persistent Memory

Abstract

Sorting is a fundamental operation in software systems. An example for that is a prepossessing phase before executing analytics operations. Persistent memory (PM) is a nonvolatile device with low latency and byte-addressable access. Our experiments used Intel's first commercially device called Intel Optane DC. In this paper, we evaluate system-level Crash Safe Sorting trade-offs while running with PM. We choose the merge-sort algorithm, which is widely used to organize and search for information. We integrated our sorting algorithm into MCAS (Memory Centric Active Storage), which is a high-performance client-server key-value store explicitly designed for PM. Our evaluation shows that Sorting fully on PM is only 1.58 slower than sorting on DRAM while giving persistent ability. In addition, the time for persisting the data is the bottleneck in the crash-safe implementation. This bottleneck can indicate the potential for utilizing a trade-off between performance and persistence.