Optimizing Adaptive Radix Trees for NVM-Based Hybrid Memory Architecture
Junchen Zhang, Yongping Luo, Peiquan Jin, Shouhong Wan · 2020
Non-Volatile Memory (NVM) has emerged as an alternative to next-generation memories. Compared to the traditional DRAM, NVM offers data persistency and higher density. However, so far, NVM has higher accessing latency than DRAM. Therefore, to ensure the high performance of data accessing, we still need to consider using DRAM in memory architecture. This leads to the hybrid memory architecture involving DRAM and NVM. Some previous benchmark works have shown that such hybrid memory architecture is more efficient than NVM-only architecture. Due to NVM's unique properties, the traditional memory B+-tree becomes unsuitable for NVM because of its high cost of maintaining node orderliness and high space-filling feature. In this paper, we propose to optimize the Adaptive Radix Tree (ART) for the hybrid memory architecture and offer a new index called HART (Hybrid Adaptive Radix Tree). HART takes advantage of ART's deterministic structure to get good query performance. Meanwhile, we only selectively persist linked list to reduce NVM access cost. In particular, we exploit the compression path to improve the leaf node's space utilization, making the subtree shorter. We run a preliminary experiment on a server with Intel Optane DC Persistent Memory and compare HART with several NVM-aware indexes. The results suggest the efficiency of our proposal.