플래시 메모리 기반 저장 시스템에서 지연 갱신을 활용하는 B-트리 인덱스 구조

Abstract

플래시 메모리 기반의 저장 시스템은 빠른 접근 속도, 저전력 소모, 높은 안정성의 이유로 다양한 응용 분야에서 널리 사용된다. 대부분의 플래시 메모리 기반 저장 시스템은NAND 플래시 메모리로 이루어져 있기 때문에 NAND 플래시 메모리 고유의 특성을 그대로 가지고 있다. NAND 플래시 메모리는 제자리 갱신을 지원하지 않기 때문에, 이미 저장된 페이지에 중첩쓰기 전에 전체 블록을 소거 후 쓰기 연산을 수행한다. 이러한 특성 때문에 같은 노드에 빈번한 갱신을 수행하는 B-트리를 플래시 메모리 기반의 저장 시스템에 아무런 변경 없이 그대로 구현할 경우 심각한 성능 감소가 발생하게 된다. 이를 해결하기 위하여 다양한 플래시 메모리 전용의 인덱스 구조가 개발되었다. 그러나 값비싼 메모리 버퍼의 사용, 갑작스러운 전원 차단으로 발생하는 데이터 손실, 불필요한 쓰기 연산으로 인한 성능 감소, 불필요한 공간 낭비 등의 문제점을 여전히 가지고 있다. 본 학위 논문에서는, 다양한 환경에서 사용되는 플래시 메모리 기반의 저장 시스템을 위한 새로운 B-트리 인덱스 구조를 제안한다. 제안하는 시스템은 크게 NAND 플래시 메모리를 저장 장치로 사용하는 임베디드 시스템을 위한 로그 기반의B-트리 인덱스 구조인 LSB-트리와 범용 플래시 메모리 기반의 저장 시스템에서 대용량 자료를 고성능으로 다루는 지연 갱신을 활용한 B-트리 인덱스 구조인 LUB-트리로 구성된다. LSB-트리는 NAND 플래시 메모리를 저장 장치로 사용하고 제한된 메모리 사용량을 가지는 소규모 임베디드 시스템에 적합한 B-트리 인덱스 구조이다. LSB-트리는 삽입되는 데이터를 해당 리프 노드에 새로운 로그 노드를 할당하여 부모 노드의 갱신 없이 변경된 데이터를 한 번의 쓰기 연산으로 저장하여 쓰기 성능을 향상 시킨다. 로그 노드가 가득찰 경우 해당 리프 노드와 병합하지만 순차적인 키 값이 삽입된 로그 노드는 병합 연산없이 리프 노드로 변경하여 추가적인 쓰기 연산을 줄인다. 제안하는 기법의 우수성을 보이기 위하여 다양한 수학적 분석과 실제 시스템에서 인덱스 생성과 검색 실험을 수행하였다. LUB-트리는 임베디드 시스템뿐만 아니라 범용 플래시 메모리 기반의 저장 시스템에서 대용량 자료를 고성능으로 처리하기 위한 B-트리 인덱스 구조이다. LUB-트리는 레코드의 삽입, 갱신, 삭제로 변경이 발생하는 리프 노드에서 루트 노드까지의 모든 노드를 메모리 영역에 두고 해당 연산을 수행함으로써 전체적인 쓰기 연산을 지연시킨다. 게다가 연속적인 키 값을 가진 레코드가 삽입되면 리프 노드를 분할하지 않고 플래시 메모리에 그대로 저장함으로써 추가적인 쓰기 연산을 줄이고 페이지 효율성을 향상시킨다. 수학적 분석과 실제 트레이스를 통한 실제 환경에서의 실험 결과를 통하여 제안하는 기법의 우수성을 보인다. |Flash memory-based storage systems have been widely used in various application areas because of their fast access speed, low power consumption, and high reliability. Most flash memory-based storage systems consist of NAND flash memories so that they inherit the distinctive characteristics of a NAND flash memory. Since a NAND flash memory cannot support an in-place update, an erase-before-write procedure is required instead of overwriting data in the prewritten page. Due to this characteristic, directly implementing a B-tree that invokes frequent updates in the same node without any modifications on the flash memory-based storage system may result in severe performance degradation. To solve this problem, various flash-aware index structures have been proposed. However, they suffer from employing the high-cost memory buffer, the risk of data loss in case of a sudden power failure, the degradation of write performance, poor space usage, and so on. In this thesis, we propose new B-tree index structures for flash memory-based storage systems used in various environments. The proposed system is composed of a log-structured B-tree (LSB-tree) for the embedded system equipped with NAND flash memory and a B-tree exploiting lazy update (LUB-tree) for handling large scale records with the high performance on the general purpose flash memory-based storage systems. LSB-tree is an index structure for the small embedded system that uses NAND flash memory as a storage device and has limited memory resources. LSB-tree stores only the modified contents into a log node corresponding to the leaf node to be inserted when an insert operation occurs. LSB-tree improves the write performance by storing a log node in a single write operation. Although LSB-tree merges a log node with the related leaf node when the log node becomes full, it avoids additional write operations for the merge operation by directly switching a log node for a leaf node when records are sequentially inserted. In order to show the superiority of LSB-tree, we mathematically analyze the operation cost and perform various experiments for the tree creation and search in the real environments LUB-tree is more proper index structure for general purpose flash memory-based storage systems as well as the embedded system for handling large scale records with the high performance. When the record insertion, update, and deletion occur, LUB-tree delays the write operation by keeping all the modified contents from the leaf node to the root node into the memory. In addition, it reduces the number of additional write operations and improves the space utilization by not splitting the leaf node in case of sequential insertions with continuous key values. Through the mathematical analysis and realistic experimental results from the real traces, we show better performance compared to the related works.; Flash memory-based storage systems have been widely used in various application areas because of their fast access speed, low power consumption, and high reliability. Most flash memory-based storage systems consist of NAND flash memories so that they inherit the distinctive characteristics of a NAND flash memory. Since a NAND flash memory cannot support an in-place update, an erase-before-write procedure is required instead of overwriting data in the prewritten page. Due to this characteristic, directly implementing a B-tree that invokes frequent updates in the same node without any modifications on the flash memory-based storage system may result in severe performance degradation. To solve this problem, various flash-aware index structures have been proposed. However, they suffer from employing the high-cost memory buffer, the risk of data loss in case of a sudden power failure, the degradation of write performance, poor space usage, and so on. In this thesis, we propose new B-tree index structures for flash memory-based storage systems used in various environments. The proposed system is composed of a log-structured B-tree (LSB-tree) for the embedded system equipped with NAND flash memory and a B-tree exploiting lazy update (LUB-tree) for handling large scale records with the high performance on the general purpose flash memory-based storage systems. LSB-tree is an index structure for the small embedded system that uses NAND flash memory as a storage device and has limited memory resources. LSB-tree stores only the modified contents into a log node corresponding to the leaf node to be inserted when an insert operation occurs. LSB-tree improves the write performance by storing a log node in a single write operation. Although LSB-tree merges a log node with the related leaf node when the log node becomes full, it avoids additional write operations for the merge operation by directly switching a log node for a leaf node when records are sequentially inserted. In order to show the superiority of LSB-tree, we mathematically analyze the operation cost and perform various experiments for the tree creation and search in the real environments LUB-tree is more proper index structure for general purpose flash memory-based storage systems as well as the embedded system for handling large scale records with the high performance. When the record insertion, update, and deletion occur, LUB-tree delays the write operation by keeping all the modified contents from the leaf node to the root node into the memory. In addition, it reduces the number of additional write operations and improves the space utilization by not splitting the leaf node in case of sequential insertions with continuous key values. Through the mathematical analysis and realistic experimental results from the real traces, we show better performance compared to the related works.