플래시 메모리상에 B+트리를 위한 효율적인 색인 버퍼 관리 정책

Abstract

Recently, NAND flash-memory has been used for storage device in various mobile computing devices such as PDAs, MP3 players, mobile phones and laptops because of its shock-resistant, low-power consumption, and non-volatile properties. However, due to the very distinct characteristics of flash memory, disk based systems could result in a severe performance degradation to a flash-memory storage system. Especially when the B-tree is constructed, the split happens frequently that could result in the performance degradation to flash memory. In this paper, we propose a buffer management scheme, called IBSF (index buffer scheme on flash memory) which could efficiently build a B-tree on flash memory. IBSF, a software module which manages the index buffer between an application and flash memory, stores a node related data into a page. If redundant data exists in the index buffer, it replaces this with new data. Moreover, it defines data structure which can include many data. Therefore, IBSF delays the time which the buffer is filled, and reduces the number of record data to a flash memory.; NAND 플래시 메모리는 작고, 가볍고, 강한 내구력과 저 전력을 소비하는 특징을 가지고 있는 비휘발성 메모리로 휴대폰, 단말기(PDA), 노트북등과 같은 다양한 이동 컴퓨팅 장비의 저장장치로 사용되고 있다. 그러나 플래시 메모리가 가지고 있는 다양한 특성 때문에 디스크 기반의 시스템을 플래시 메모리에서 곧바로 사용하는 것은 여러 단점들을 발생시킬 수 있다. 특히 B트리를 구축할 때 노드 분할(split)과 같이 데이터 갱신(update) 처리가 빈번하게 발생하는 작업은 플래시 메모리의 성능을 저하 시킨다. 본 논문에서는 플래시 메모리에 효과적으로 B트리를 구축하기 위한 IBSF(index buffer scheme on flash memory) 기법을 제안한다. IBSF는 플래시 메모리와 응용(application) 사이에 색인버퍼(index buffer)를 관리하는 소프트웨어 모듈로써 데이터를 기록할 때 하나의 노드에 관련된 데이터는 완성된 노드의 형태로 하나의 페이지에 저장하며 색인 버퍼에 데이터를 삽입 시 동일한 데이터에 대한 색인 단위가 있는지 검색한 후 중복된 색인 단위가 존재 할 경우 이것을 새로운 데이터로 교체한다. 또한 색인 단위의 구조를 재정의 하여 적은 개수의 색인 단위로 다수의 정보를 표현할 수 있도록 함으로써 버퍼가 채워지는 주기를 늦추고 플래시 메모리로 데이터를 기록하는 횟수를 줄인다.