Obfuscated red-black tree: Decoupling search trees to make them friendly for nonvolatile memories in one-memory systems

摘要

Due to the excellent performance and energy efficiency, modern nonvolatile memories (NVMs) have become popular alternatives to DRAM as main memory. However, the intrinsic characteristics of NVMs are quite different from those of DRAM, making existing designs of system and application software unfavorable on NVMs. For example, a write operation typically takes much more time and energy than a read operation on NVMs, and system or application software should try to reduce write activities so as to enhance the overall performance and energy efficiency of the system. In this work, we propose a novel design of NVM-based self-balancing binary search trees for red-black tree, a widely used dictionary structure. Through intentionally mixing up the pointers of red-black tree nodes, we effectively decouple the pointers of a red-black tree into two parts, namely (a) the pointers that maintain the logical structure of the red-black tree and (b) the pointers that keep the memory addresses of the nodes of the red-black tree. By doing so, the NVM writes are significantly reduced, and the performance and energy efficiency are remarkably improved. The efficacy of the proposed design is then verified by experimental studies, where the results are quite encouraging.