낸드 플래시 메모리 기반 저장시스템을 위한 회복 가능한 B트리 구축 및 관리 기법

Abstract

낸드 플래시 메모리는 작고, 가볍고, 강한 내구력과 저 전력을 소비하는 특징을 가지고 있는 비휘발성 메모리로 휴대폰, 노트북, 개인 컴퓨터, 엔터프라이즈 서버 등 다양한 컴퓨팅 시스템의 저장장치로 사용되고 있다. 그러나 플래시 메모리가 가지고 있는 다양한 특성 때문에 디스크 기반의 시스템을 플래시 메모리 기반 저장장치에 곧바로 사용하는 것은 여러 단점들을 발생시킬 수 있다. 특히 구축할 때 갱신(update)이 빈번히 발생하는 B트리는 플래시 메모리 기반 저장장치의 성능을 심각하게 저하 시킨다. 본 학위논문에서는 이러한 문제를 해결하기 위해 낸드 플래시 메모리기반 저장시스템을 위한 회복 가능한 B트리 구축 및 관리 기법을 제안한다. 제안하는 기법은 버퍼를 이용하여 고성능으로 B트리를 구축하기위한 IBSF (index buffer management scheme on flash memory) 기법과 버퍼를 이용하여 데이터를 저장할 때 고장으로 인해 발생할 수 있는 고장회복 문제를 해결하기 위한 RIBSF (recoverable IBSF) 기법으로 구성된다. 첫 번째로, 고성능으로 B트리를 구축하기 위해 제안하는 IBSF 기법은 저장장치와 응용(application) 사이에서 색인 버퍼(index buffer)를 이용하여 B트리 구축 시 발생하는 쓰기 연산을 지연시킨다. 또한 버퍼 내에 중복된 데이터를 제거하고 버퍼가 채워졌을 때 첫 번째 색인 데이터와 관련된 데이터를 모아서 하나의 페이지에 저장한다. 따라서 IBSF 기법은 B트리 구축 시 발생하는 쓰기 연산의 횟수를 줄이고 구축 성능을 향상시킬 수 있다. 두 번째로, 고장회복 문제를 해결하기 위해 제안하는 RIBSF는 루트노드의 변경이 발생할 때 버퍼내의 모든 데이터를 커밋(commit)하고 체크포인트(checkpoint)를 생성하기 때문에 마지막 체크포인트 시점으로 고장회복이 가능하다. 또한 RIBSF는 그림자페이징(shadow paging) 정책을 적용하였다. 이 정책은 갱신된 데이터를 새로운 페이지에 저장하기 때문에 커밋 연산을 할 때 제자리갱신(overwrite)연산의 횟수를 줄이고 고장회복 기능 추가로 인한 오버헤드를 줄일 수 있다. 그리고 그림자 페이징 정책은 노드의 갱신된 데이터와 이전 데이터를 동시에 관리하기 때문에 이전 상태로의 고장회복 성능을 향상시킬 수 있다. 마지막으로, 본 학위 논문은 다양한 실험 결과를 통해 제안하는 알고리즘들이 플래시 메모리 기반 저장장치에서 고성능으로 B트리를 구축할 수 있으며 동시에 작은 오버헤드로 다양한 패턴의 고장 상황에서 안정적인 고장회복을 할 수 있는 것을 증명한다.