Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：7

、訪客IP：18.118.227.69

姓名

羅暉棠(Hui-Tang Luo) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes)

相關論文

★ 重新思考虛擬記憶體管理的方式以開放通道式固態硬碟最大限度地減少深度學習推薦系統演算法的讀寫流量	★ 開啟製程相似檢查方法在組裝超級塊上以最小化額外的寫入延遲
★ LaDy: Enabling Locality-aware Deduplication Technology on Shingled Magnetic Recording Drives	★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory
★ WABE: Rethinking B-epsilon-tree to Minimize Write-amplification on NAND Flash Memory	★ Prophet’s Insight: Unleashing Deduplication System Performance in Multi-tier Storage Systems
★ Freeing the Power of High Parallelism: Accelerating the Bϵ-Tree Indexing Scheme Performance on Open-Channel SSD	★ Applying Content-Defined Chunking to OCSSD-based Deduplication Systems
★ GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory	★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2026-6-30以後開放)

摘要(中)

Bϵ 樹因其卓越的讀寫性能，已成為現代檔案和資料庫系統中優選的索引結構。該結構的內部節點包含一個緩衝空間，通過利用暫時局部性（temporal locality）提升讀取性能，並通過促進連續寫入來提高寫入性能。然而，構建Bϵ 樹會帶來顯著的寫入性能開銷，因為所有鍵值都要通過刷新（flushing）過程重複寫入到持久性記憶體。本研究旨在通過引入一個新的寫入框架，即mw-Bϵ 樹，來應對這一挑戰，該框架利用具有多寫入模式支援的持久性記憶體，以最小化構建Bε 樹所需的寫入成本。所提出的方法利用各個樹節點的更新頻率，選擇最適合的寫入模式將索引鍵值存儲到持久性記憶體中。與固定模式選擇方法相比，所提出的解決方案顯著提高了Bϵ 樹索引方案的性能。本研究的結果表明，利用支援多寫入模式的持久性記憶體可以顯著提升構建Bϵ 樹索引結構的效率。

摘要(英)

The Bϵ tree has emerged as a preferred indexing structure in modern file and database systems due to its remarkable read and write performance. The internal nodes of the structure embed a buffer space that enhances read performance by capitalizing on temporal locality and write performance by facilitating sequential write. However, constructing a Bϵ tree comes with significant write performance overhead since all keys are repeatedly written to persistent memory through a flushing process. This study aims to address this challenge by introducing a new writing framework, namely the mw-Bϵ tree, which takes advantage of persistent memory with multi-write mode support to minimize the writing costs associated with constructing the Bϵ tree. The proposed approach leverages the update frequency of the various tree nodes to select the most suitable write mode for storing the indexing keys to persistent memory. Compared to the fixed-mode selection approach, the proposed solution markedly improves the performance of the Bϵ tree indexing scheme. The findings of this study suggest that utilizing persistent memory with multi write mode support can significantly enhance the efficiency of constructing the Bϵ tree indexing structure.

關鍵字(中)

★ Bϵ 樹
★ 鍵值存儲
★ 索引方案
★ 非揮發性記憶體
★ 多寫入模式

關鍵字(英)

★ Bϵ-tree
★ key-value store
★ indexing scheme
★ non-volatile memory
★ multi-write modes

論文目次

1 Introduction 1
2 Technical Background & Motivation 5
2.1 Bϵ tree Indexing Scheme . . . .. . . . . . . . . . . . 5
2.2 Multi-level Cell Phase-change Memory . . . . . . . . . 7
2.3 Motivation . . . . . . . . . . . .. . . . . . . . . . 10
3 Bϵ tree Scheme with Write-mode Selection 13
3.1 Overview of mw-Bϵ tree . . . . . . .. . . . . . . . . 13
3.2 Timing: Retention-time-aware Flushing Mechanism . . . 16
3.3 Unit: Coarse and Fine-grained Write Control . . . . . 19
3.4 Policy: Well-suited Write-mode Selection . .. . . . . 22
3.5 DRAM Overhead Analysis . . . . . . . . . . . . . . . 25
4 Evaluations 27
4.1 Experimental Environment . . . . . . . . . . . . . . 27
4.2 Results and Analysis . . . . . . .. . . . . . . . . . 29
4.2.1 Energy Consumption . . . . . . . . . . . . . . . . 29
4.2.2 Performance Improvement . . . . . . . . . . . . . . 31
5 Concluding Remarks 33

參考文獻

[1] W. Jannen, J. Yuan, Y. Zhan, A. Akshintala, J. Esmet, Y. Jiao, A. Mittal, P. Pandey, P. Reddy, L. Walsh, M. A. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, and D. E. Porter., “BetrFS: Write-Optimization in a Kernel File System,” ACM Transactions on Storage, vol. 11, no. 18, pp. 1–29, Nov. 2015.
[2] M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, B. C. Kuszmaul, D. E. Porter, J. Yuan, and Y. Zhan, “An Introduction to Bϵ-trees and Write Optimization,” Login: The USENIX Magazine, vol. 40, no. 5, pp. 22–28, Oct. 2015.
[3] M. Chang and C. Lin, A. Lee, Y. Chiang, C. Kuo, G. Yang, H. Tsai, T. Chen, and S. Sheu, “A 3T1R Nonvolatile TCAM Using MLC ReRAM for Frequent-Off Instant-On Filters in IoT and Big-Data Processing,” IEEE Journal of Solid-State Circuits, vol. 52, no. 6, pp. 1664 - 1679, June 2017, doi: 10.1109/JSSC.2017.2681458.
[4] Y. Liang, Y. Hsu, T. Chen, S. Chen, H. Wei, T. Hsu, and W. Shih, “Ecofeller: Minimizing the Energy Consumption of Random Forest Algorithm by an Eco-pruning Strategy over MLC NVRAM,” 2021 58th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA, 2021, pp. 649-654, doi: 10.1109/DAC18074.2021.9586164.
[5] T. Chen, Y. Chang, M. Yang, and H. Chen, “How to cultivate a green decision tree without loss of accuracy?,” In Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design (ISLPED ’20), Online, 2020, pp. 1-6.
[6] S. Chen, P. B. Gibbons and S. Nath, “Rethinking database algorithms for phase change memory,” In The Conference on Innovative Data Systems Research 2011 (CIDR ’11), 2011.
[7] C. Pan, M. Xie, J. Hu, Y. Chen, and C. Yang, “3M-PCM: exploiting multiple write modes MLC phase change main memory in embedded systems,” In Proceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis (CODES ’14), Article 33, pp. 1– 10. https://doi.org/10.1145/2656075.2656076
[8] M. Zhang, L. Zhang, L. Jiang, Z. Liu and F. T. Chong, “Balancing Performance and Lifetime of MLC PCM by Using a Region Retention Monitor,” 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA), Austin, TX, USA, 2017, pp. 385-396, doi: 10.1109/HPCA.2017.45.
[9] W. Cheng, T. Zheng, L. Zeng, Y. Wang and A. Brinkmann, “DPLFS: A Dual-Mode PCM-based Log-Structured File System,” 2022 IEEE 40th International Conference on Computer Design (ICCD), Olympic Valley, CA, USA, 2022, pp. 324-331, doi: 10.1109/ICCD56317.2022.00054.
[10] Q. Li, L. Jiang, Y. Zhang, Y. He, and C. J. Xue, “Compiler directed write-mode selection for high performance low power volatile PCM,” In Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems (LCTES ’13), pp. 101-110. https://doi.org/10.1145/2491899.2465564.
[11] S. -H. Chen, Y. -H. Chang, Y. -M. Chang and W. -K. Shih, “mwJFS: A Multiwrite-Mode Journaling File System for MLC NVRAM Storages,” in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 27, no. 9, pp. 2060-2073, Sept. 2019, doi: 10.1109/ TVLSI.2019.2919907.
[12] O. Eytan, D. Harnik, E. Ofer, R. Friedman, and R. Kat, “It’s Time to Revisit LRU vs. FIFO,” 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20), July 2020.
[13] SNIA IOTTA Repository, “Key-Value Traces”, http:// iotta.snia.org/ traces/key-value
[14] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, “Benchmarking cloud serving systems with YCSB.,” In Proceedings of the 1st ACM symposium on Cloud computing (SoCC ’10), pp. 143–154, June 2010, https://doi.org/10.1145/1807128.1807152

指導教授

陳增益(Tseng-Yi Chen)

審核日期

2023-7-10

推文