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

Soojeong Cho

doi:10.1109/TPDS.2020.3028699

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

2021-03-01

8

OA

AI

DOI：10.1109/TPDS.2020.3028699

原文链接

查看原文

摘要

En 中文

In this article, we propose Failure-atomic Byte-addressable R-tree (FBR-tree) that leverages the byte-addressability, persistence, and high performance of persistent memory while guaranteeing the crash consistency. We carefully control the order of store and cacheline flush instructions and prevent any single store instruction from making an FBR-tree inconsistent and unrecoverable. We also develop a non-blocking lock-free range query algorithm for FBR-tree. Since FBR-tree allows read transactions to detect and ignore any transient inconsistent states, multiple read transactions can concurrently access tree nodes without using shared locks while other write transactions are making changes to them. Our performance study shows that FBR-tree successfully reduces the legacy logging overhead and the lock-free range query algorithm shows up to 2.6x higher query processing throughput than the shared lock-based crabbing concurrency protocol.

Keyword:

Data structures

Metadata

Indexing

Computer crashes

Transient analysis

Concurrent computing

R-tree

persistent memory

failure-atomicity

multidimensional indexing structure

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

摘要

AI总结

期刊

机构

引用论文