NAND 플래시 메모리용 B+트리의 인덱스 버퍼를 위한 효율적인 고장회복 관리기법

Abstract

최근 NAND 플래시 메모리는 빠른 속도와 저 전력 소비라는 특징 때문에 차세대 저장장치의 소재로써 주목 받고 있다. 따라서 오늘날 다양한 저장 장치의 저장 매체가 하드디스크에서 플래시 메모리 기반의 SSD(solid state disk)로 대체되고 있다. 그러나 SSD는 플래시 메모리의 쓰기 전 소거 구조(erase-before-write architecture)와 비대칭 읽기 쓰기 연산 속도의 특성을 가지고 있기 때문에, 같은 지역에 집중적인 쓰기 연산을 발생하는 B트리를 구축하는 것은 많은 비용을 야기 할 것이다. 따라서 B트리 구축의 비용을 줄이기 위해 색인 버퍼를 이용한 방법들이 제안되어 왔다. 그러나 이러한 방법들은 전원 차단 시 버퍼에 유지되어 있던 색인 데이터를 유실하기 때문에 고장 회복의 문제를 가지고 있다. 이러한 문제를 해결하기 위해 본 논문에서는 NAND 플래시 메모리용 B트리의 인덱스 버퍼를 위한 효율적인 고장회복 관리 기법을 소개한다. 본 논문에서 제안하는 기법은 루트노드의 데이터가 갱신될 때 마다 검사점(checkpoint)을 두고 버퍼의 모든 색인 데이터들을 SSD로 커밋(commit)하기 때문에 고장 시점으로부터 마지막 커밋 시점으로 복구할 수 있다. 또한 본 알고리즘에 그림자 페이징(shadow paging) 정책을 적용하여 커밋 연산을 할 때 제자리갱신(overwrite)연산의 횟수를 줄였다. 이 방법은 복구를 할 때 쓰기 연산의 횟수를 줄여주기 때문에 고장회복의 속도를 향상시킬 수 있다. 결과적으로 제안하는 알고리즘은 SSD상에서 B트리를 구축할 때 작은 오버헤드로 안정적인 B트리를 구축 할 수 있을 뿐만 아니라 고장 회복을 위한 복구 시간을 줄였다. 또한 다양한 실험을 통하여 본 기법이 기존에 제안되었던 기법보다 SSD 상에서 좋은 성능을 보이는 것을 증명한다.;Recently, NAND flash memory has been remarked as a best medium of the next generation storage because of its fast speed and low power consumption. Therefore, in various computing systems, the HDD (hard disk drive) has been replaced by the SSD (NAND flash-based solid state disk). However, since the SSD inherits the limitations of NAND flash memory such as erase-before-write architecture and asymmetric read/write speeds, it may result in severe performance degradation when building a B-tree that causes intensive writes at the same location. To reduce the cost of a B-tree implementation, several methods exploiting the buffer have been proposed so far. However, they have the recovery problem because all index data in the buffer are eliminated when power-failure occurs. In this paper, we introduce an efficient recovery management scheme for an index buffer of B-tree based on NAND flash memory for solving the recovery problem. Since the proposed method flushes all index data in the buffer into the SSD and creates the checkpoint whenever updating the root node, it can always recover the index structure into the last commit time. Also, it adopts the shadow-paging strategy for reducing the number of overwrites when committing the node. This method may reduce the time of recovery because it can eliminate a number of writes during the recovery. Consequently, it can efficiently reduce not only the consumed time but also the time of recovery when constructing a B-tree on SSD. We also show that our proposed algorithm yields a good performance on the SSD by comparing it to the related technique through various experiments.