비대칭적 성능의 고용량 비휘발성 메모리를 위한 계층적 구조의 이진 탐색 트리
A Hierarchical Binary-search Tree for the High-Capacity and Asymmetric Performance of NVM
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For decades, in-memory data structures have been designed for DRAM-based main memory that provides symmetric read/write performances and has no limited write endurance. However, such data structures provide sub-optimal performance for NVM as it has different characteristics to DRAM. With this motivation, we rethink a conventional red-black tree in terms of its efficacy under NVM settings. The original red-black tree constantly rebalances sub-trees so as to export fast access time over dataset, but it inevitably increases the write traffic, adversely affecting the performance for NVM with a long write latency and limited endurance. To resolve this problem, we present a variant of the red-black tree called a hierarchical balanced binary search tree. The proposed structure maintains multiple keys in a single node so as to amortize the rebalancing cost. The performance study reveals that the proposed hierarchical binary search tree effectively reduces the write traffic by effectively reaping the high capacity of NVM.
Abstract
For decades, in-memory data structures have been designed for DRAM-based main memory that provides symmetric read/write performances and has no limited write endurance. However, such data structures provide sub-optimal performance for NVM as it has different characteristics to DRAM. With this motivation, we rethink a conventional red-black tree in terms of its efficacy under NVM settings. The original red-black tree constantly rebalances sub-trees so as to export fast access time over dataset, but it inevitably increases the write traffic, adversely affecting the performance for NVM with a long write latency and limited endurance. To resolve this problem, we present a variant of the red-black tree called a hierarchical balanced binary search tree. The proposed structure maintains multiple keys in a single node so as to amortize the rebalancing cost. The performance study reveals that the proposed hierarchical binary search tree effectively reduces the write traffic by effectively reaping the high capacity of NVM.
참고문헌 (15)
- A. Eisenman, "Reducing DRAM Footprint with NVM in Facebook", Proceedings of the 9th European Conference on Computer Systems, (42) (2018)
- S. R. Dulloor, "System Software for Persistent Memory", Proceedings of the 9th European Conference on Computer Systems (Eurosys), (15) (2014)
- E. Lee, "P2FS: Supporting Atomic Writes for Reliable File System Design in PCM Storage", Proceedings of EICE Electronics Express, 11, pp.1~6 (2014)
- J. Condit, "Better I", O Through Byte-addressable, Persistent Memory, 2009, 133~146
- E. Lee, "Unioning of Buffer Cache and Journaling Layers", Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST), pp.73~80 (2013)
- E. Lee, "On-demand Snapshot: An Efficient Versioning File System for Phase Change Memory", Journal of IEEE Transactions on Knolwedge and Data Engineering, 25(12), pp.2841~2853 (2013)
- J. Xu, "NOVA: A Log Structured File System for Hybrid Volatile", Non-volatile Main Memories, 2016, 323~338
- S. Venkataraman, "Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory", Proceedings of the 9th USENIX Conference on File and Storage Technologies (FAST), 11, pp.61~75 (2011)
- D. Hwang, "Endurable Transient Inconsistency in Byte-Addressable Persistent B+-Tree", Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST), pp.187~200 (2018)
- P. Chi, "Adapting B+-Tree for Emerging Nonvolatile Memory-Based Main Memory", Journal of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35(9), pp.1461~1474 (2016)
- J. Yang, "NV-tree: a Consistent and Workload-adaptive Tree Structure for Non-volatile Memory", Journal of IEEE Transactions on Computers, 65(7), pp.2169~2183 (2016)
- D. Bittman, "Optimizing Systems for Byte-Addressable NVM by Reducing Bit Flipping", Proceedings of 17th USENIX Conference on File and Storage Technologies, pp.17~30 (2019)