Future-Based Persistent Spatial Data Structure for NVM-Based Manycore Machines

Abstract

R-trees have been popular for their support of multidimensional data and high-performing queries. FBR-tree is the state-of-the-art concurrent variant of the R-tree for Intel DC Persistent Memory (DCPM). However, its adoption on manycore servers is impeded by concurrency limitations due to lengthy, lock-based synchronization, including structure modification operations, split and merge. Additionally, emerging DCPM-based machines are equipped with multiple CPU sockets, forming a non-uniform memory access (NUMA) architecture. FBR-tree’s lack of NUMA-awareness induces further performance overhead from remote memory accesses. In this paper, we propose MPR-tree, a concurrent, NUMA-aware and persistent future-based R-tree for DCPM servers. MPR-tree focuses on insert operations due to their laborious nature. MPR-tree relies on per-thread local future objects and a global R-tree. To introduce NUMA-awareness and minimize remote memory accesses, MPR-tree adopts per-socket dedicated asynchronous evaluate threads to checkpoint future objects to the global R-tree. MPR-tree employs an in-memory hash table to mitigate the read overhead of key searches over the future objects. We implemented MPR-tree atop FBR-tree and evaluated its performance on a server with 40 physical cores for insert and lookup queries, and it showed that MPR-tree outperforms FBR-tree on average by $2\times $ on log10 scale.

Keywords

• Futures
• index data structures
• non-volatile memory
• manycore machines