Failure-Atomic Byte-Addressable R-tree for Persistent Memory

Department of Computer Science and EngineeringWith the emergence of persistent memory (PM), which enables byte-addressable, 64-byte cacheline flush and 8-byte store instructions are expected to be used as persist and failure-atomic write operations, respectively, instead of calls from fsync() and write() system. The granularity of such a small atomic write represents a challenge to the crash consistency of in-PM data structure. In addition, even if the process does not explicitly invoke clflush, a dirty cachelines can be flushed to PM unexpectedly and exposed to other concurrent processes when the system recovers. These challenges occur in PM, but high-density PM is attractive in enabling multidimensional indexing to navigate efficiently through large scientific datasets due to their high performance, durability and large capacity. This work proposes a Fail-atomic Byte Addressable R-tree (FBR tree) that utilizes byteaddressability, persistence and high performance of PM while ensuring crash consistency. We carefully control the order of the store and cashline flush instruction and prevent any sinble store instruction from making the FBR tree inconsistent and unrecoverable. We also develop a non-blocking lock-free range query algorithm for the proposed FBR-tree. Since FBR-tree allows read transactions to detect and ignore any transient inconsistent states, multiple read transactions can access tree nodes concurrently without using shared locks while other write transactions make changes to them. Our performance study shows that FBR-tree successfully reduces legacy logging overhead, and the lock-free range query algorithm shows up to 9.4x higher query processing throughputs than the shared lock-based crabbing concurrency protocol.clos