NAND 플래시 메모리를 위한 로그 기반의 B-트리
Log-Structured B-Tree for NAND Flash Memory
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
최근 NAND 플래시 메모리는 하드 디스크에 비해 작고, 속도가 빠르며, 저 전력 소모 등의 장점을 가지고 있어 차세대 저장 매체로 각광받고 있다. 그러나 쓰기-전-소거 구조, 비대칭 연산 속도 및 단위와 같은 독특한 특징으로 인하여, 디스크 기반의 시스템이나 응용을 NAND 플래시 메모리 상에 직접 구현시 심각한 성능저하를 초래할 수 있다. 특히 NAND 플래시 메모리 상에 B-트리를 구현할 경우, 레코드의 잦은 삽입, 삭제 및 재구성에 의한 많은 양의 중첩 쓰기가 발생할 수 있으며, 이로 인하여 급격한 성능 저하가 발생할 수 있다. 이러한 성능 저하를 피하기 위해 μ-트리가 제안되었으나, 잦은 노드 분할 및 트리 높이의 빠른 신장 등의 문제점을 가지고 있다. 본 논문에서는 갱신 연산을 위해 특정 단말 노드에 해당하는 로그 노드를 할당하고, 해당 로그 노드에 있는 변경된 데이터를 한 번의 쓰기 연산으로 저장하는 로그 기반의 B-트리(LSB-트리)를 제안한다. LSB-트리는 부모 노드의 변경을 늦추어 추가적인 쓰기 연산의 횟수를 줄일 수 있다는 장점을 가지고 있다. 또한 키 값에 따라 데이터를 순차적으로 삽입할 때, 로그 노드를 새로운 단말 노드로 교환함으로써 추가적인 쓰기 연산의 횟수를 줄일 수 있다. 마지막으로, 다양한 비교 실험을 통하여 μ-트리와 비교함으로써 LSB-트리의 우수성을 보인다.
Abstract
Recently, NAND flash memory is becoming into the spotlight as a next-generation storage device because of its small size, fast speed, low power consumption, and etc. compared to the hard disk. However, due to the distinct characteristics such as erase-before-write architecture, asymmetric operation speed and unit, disk-based systems and applications may result in severe performance degradation when directly implementing them on NAND flash memory. Especially when a B-tree is implemented on NAND flash memory, intensive overwrite operations may be caused by record inserting, deleting, and reorganizing. These may result in severe performance degradation. Although μ-tree has been proposed in order to overcome this problem, it suffers from frequent node split and rapid increment of its height. In this paper, we propose Log-Structured B-Tree(LSB-Tree) where the corresponding log node to a leaf node is allocated for update operation and then the modified data in the log node is stored at only one write operation. LSB-tree reduces additional write operations by deferring the change of parent nodes. Also, it reduces the write operation by switching a log node to a new leaf node when inserting the data sequentially by the key order. Finally, we show that LSB-tree yields a better performance on NAND flash memory by comparing it to μ-tree through various experiments.
참고문헌 (12)
- "Samsung Electronics, “64M×8 Bits NAND Flash Memory (K9F1208X0C),”", ~ (2007)
- "Samsung Electronics, “2G×8 Bit", 4G×8 Bit, pp.2007, ~
- "JFFS3 design issues"[URL]
- Dongwon Kang et al., "μ-Tree: An Ordered Index Structure for NAND Flash Memory", Proceedings of the 7th Annual ACM Conference on Embedded Systems Software (ACM EMSOFT 2007), (2007)
- Patrick O’Neil, "The Log-Structured Merge-Tree", Acta Informatica, 33(4) (1996)
- Douglas Comer, "The Ubiquitous B-Tree", ACM Computing Surveys, 11(2), pp.121~137 (1979)
- Sang-Won Lee, "A Log Buffer based Flash Translation Layer using Fully Associative Sector Translation", ACM Transactions on Embedded Computing Systems, 6(1) (2007)
- Tae-Sun Chung, "System Software for Flash Memory: A Survey.", International Conference on Embedded and Ubiquitous Computing, pp.394~404 (2006)
- Chin-Hsien Wu, "An Efficient B-Tree Layer for Flash-Memory Storage Systems", Real-Time and Embedded Computing Systems and Applications (RTCSA),, pp.409~430 (2003)
- KIM, J. S., "A Space-Efficient Flash Translation Layer for Compactflash Systems", IEEE Transactions on Consumer Electronics, 48, pp.366~375 (2006)
- M. Rosenblum, "Thre Design and Implementation of A Log-Structured File System", ACM Trans. Computer Systems, 10(1), pp.26~52 (1992)
- Henessy, J. L., "Computer Architecture: A Quantitative Approach 3rd ed." (2003), Morgan Kaufmann