Flash memory has become an increasingly important component as a nonvolatile storage media because of its small size, shock resistance, and low power consumption. In nonvolatile memories, NOR flash memory provides fast random access speed, but high cost and low density, compared with NAND flash memory. NAND Flash has advantages in large storage capacity and relatively high performance for large read and write in contrast to NOR flash. Currently, due to its physical characteristics, block level translation interface, called flash translation layer, is required between an existing regular file system and the flash memory chips. However, the approach of regular file systems, which is mounted on top of the emulated block level interface, has many restrictions and is inefficient because these file systems are designed for the disk based storage device. There were some approaches that file system directly uses flash memory without intermediate interface, called flash file system. The popular flash file systems include Journalling Flash File System and Yet Another Flash File System. However, they have many restrictions in their architectures, thus show poor performance in booting time, garbage collection overhead, and memory footprint. In addition, another serious problem in flash file systems is very poor write performance.
In this dissertation, an efficient flash file system is proposed and designed for NAND flash memory storage. The proposed flash file system considers both issues the regular file system and flash memory. Target performance metrics are the system booting time, memory footprint, and garbage collection overhead, which are important issues in flash memory. First, the proposed flash file system tried to store the whole data index entries within inode structire in order to reduce the flash scan time. For this, each inode occupies a whole flash page to preserve sufficient available indexing space. In addition, it provide two inode classes: one has all direct indexing, and the other has all indirect indexing. Second, it separately allocate flash memory block between the metadata and data which leads the pseudo hot-cold separation because metadata are much hotter than data. Hot-cold separation can reduce garbage collection overhead. In experiments, the proposed flash file system outperformed other flash file systems both in booting time, garbage collection overhead, and memory footprint.
Second, The dissertation design and implements write back routine to enhance write performance. Linux OS generally use the write back routine for asynchronous I/O using pdflush and kupdate kernel thread, which writes back the dirty memory pages and buffers to the storage through the block device layer. Flash memory based filesystem does not use block device layer, so they cannot utilize Linux asynchronous I/O. Whenever the write is performed from users, flash file system is not returned from kernel until all the data are flushed to physical flash medium. This write transaction mechanism gives much latency to users, and thus degrades the overall system performance. Deferring write requests is implemented in here to enhance write latency. For this, we first analyze the write procedure of the flash filesystem in detail, and derive the drawback and overhead. Then, we design the flash write back routine for the flash filesystem asynchronous I/O whose method is similar to the Linux pdflush and kupdate operation. The designed flash write back routine can reduce average latency of write operations when the buffers are enough to get users data.
Lastly, duplicate eliminable structure and operation for flash file system are proposed. Whenever a file is modified by either inserts, deletes or replacements, the new blocks in the file are written to storage in company with non-modified blocks. However, due to the inability to efficiently identify those portions of the file that are actually new in the latest update, a large part of existing data must get necessarily re-written to storage. The non-changed existing data is considered as duplicate data since these don't need to be re-written any more. File system incurs a cost in terms of storage space and bandwidth whenever data is created or updated. If flash memory is used for storage, it is benefit to reduce the duplicate write of data as many as possible, since bandwidth is linearly and reversely proportional to the amount of data to be written. Moreover, due to the out-of-place update issue of flash memory, reducing write request can also reduce garbage collection overhead and flash memory block erase operations. When file is written, identification of duplicate region and elimination of these from the write request is very beneficial in flash memory based storage system. The issue is that how to identify and eliminate the duplicate region efficiently. In the file system structure, one of the most important design issue for supporting duplicate elimination is how to manage data blocks and how to identify duplicate region. In this dissertation, indexing structure supports variable-sized blocks in order to increase the flexibility in both of duplicate region and the amount of duplicate region identified. In addition to, It uses non-overlapping duplicate checking algorithm to reduce the complexity of duplicate checking algorithm. The duplicate elimination can prolong flash memory life cycles by reducing actual amount of page writes, as well as increase write bandwidth efficiency.
플래시 메모리는 그 물리적 특성상, 작은 사이즈, 적은 파워 소모, 충격에 대한 강인성 등으로 인해서 비 휘발성 메모리로서 그 중요성이 점점 커지고 있다. 비 휘발성 메모리중에서, 노아 플래시 메모리는 빠른 랜덤 엑세스를 제공하지만 고가이며 밀접도가 낮은 반면, 낸드 플래시 메모리는 대용량에 비교적 큰 I/O에서 좋은 성능을 내기 때문에 저장장치로서 노아 플래시 메모리보다 많은 이점을 가진다. 앞으로 임베디드 시스템 뿐만 아니라 데스크탑 환경까지도 낸드 플래시 메모리의 저장장치로서의 사용성은 기하급수적으로 늘어날 것으로 보고되고 있다.
플래시 메모리는 기술상의 한계점으로 인해서 여러가지 제약을 가지고 있어, 시스템에서 저장장치로 사용될 때에 여러가지 노력이 필요하다. 그 대표적인 예가 플래시 변환 계층이나 플래시 파일 시스템의 디자인이다. 플래시 변환 계층은 기존의 파일시스템을 그대로 수용할 수 있다는 장점이 있지만, 파일 시스템의 정보다 유저 영역의 정보를 가지고 있지 않기 때문에 최적화되기가 어렵다. 플래시 파일 시스템의 경우, 파일 시스템의 정보를 플래시 메모리에 저장할 때 효율적으로 저장할 수 있는 디자인이 가능하다.
현재까지 제안되고 있는 플래시 파일 시스템은 JFF2와 YAFFS가 존재한다. JFFS2는 노아 플래시와 낸드 플래시 메모리를 모두 지원하기 때문에, 앞으로 그 사용성이 증대될 낸드 플래시 메모리에 최적화 되어 있지 못하다. YAFFS는 디자인초기부터 낸드 플래시 메모리를 고려하여 디자인되어 있지만, 파일 시스템의 구조가 효율적이지 못하며, 또한 이 두 디자인은 파일 시스템에 존재하는 파일의 특징, 사용자들의 사용하는 파일의 접근 패턴등을 고려하지 않은 디자인이기 때문에 한계점이 있다. 이로 인해서, 파일 시스템의 마운트 타임, 가비지 콜렉션의 오버헤드, 메모리 사용량, 그리고 I/O 성능등이 좋지 않게 나타나고 있다.
본 논문에서는, 낸드 플래시 메모리를 위한 플래시 파일 시스템을 디자인한다. 본 논문에서 제안하는 플래시 파일 시스템은 기존의 플래시 파일 시스템이 가지는 장점을 최대한 살리고, 또한 이전에 고려하지 못하였던 파일의 특징이나 접근 패턴, 파일 시스템의 메타데이터의 특징을 최대한 적용하고 있다. 구체적으로, 파일 시스템에 존재하는 파일은 일반적으로 다음과 같은 특징을 가진다. 첫째, 파일 시스템에 존재하는 파일의 대부분은 크기가 작은 파일이며 쓰기연산이 주로 작은 파일에 집중되지만, 실제로 대부분의 파일 시스템의 용량은 일부의 큰 파일로 채워지고 이들은 주로 읽기 연산으로 이루어진다. 둘째, 파일 시스템의 데이터의 정보를 관리하는 메타데이터는 실제 데이터보다 훨씬 더 업데이트 빈도가 높다. 이 두가지를 플래시 파일 시스템에 적용하기 위해서 다음의 디자인 방식을 적용한다. 첫째, indexing 방식의 파일 시스템을 적용하되, 파일의 종류를 i-class1, i-class2로 나누고 i-class1은 작은 파일, i-class2는 큰 파일을 나타내도록 한다. 이렇게 나눈 파일들 중, i-class1은 direct index entry만을, i-class2는 indirect index entry 만을 가지도록 한다. 둘째, 메터데이터와 데이터를 플래시 메모리의 서로 다른 블럭에 저장하도록 한다. 이런 방식을 적용함으로써, 부팅시 메타데이터를 가지는 블록만을 읽음으로써 플래시 메모리 스캔이 가능해지며, 메터데이터-데이터 분리라는 hot-cold 분리를 통해서 가비지 콜렉션의 성능을 향상시킬 수 있다. 또한 indexing 방식은 기존의 방식보다 메모리 사용량의 제한을 줄 수있는 방식이기 때문에 메모리 사용량에서도 효율성을 기대할 수 있다.
또한 본 논문에서는, 플래시 파일 시스템의 가장 큰 문제점 중의 하나인 쓰기 문제를 해결하기 위해서, 쓰기 지연 방식과, 중복 제거 방식의 두가지 방식을 제안하고 구현한다. 쓰기 지연 방식은 쓰기 데이터를 플래시 메모리에 직접 쓰기 전에 커널 영역에서 캐싱을 한 이후, 나중에 플래시 메모리에 쓰기를 하는 방식이다. 어플리케이션에서는 커널 영역의 메모리에 데이터를 복사한 후 바로 리턴할 수 있으므로 어플리케이션에서 느낄 수 있는 쓰기 응답 속도를 해결할 수 있으며, 커널 영역에 모아진 데이터가 어플리케이션에 의해서 중복된 데이터인 경우, 혹은 메타데이터의 중복이 일어날 경우, 가장 최근의 데이터만 플래시 메모리에 쓰도록 하는 방법을 적용할 수 있기 때문에 쓰기 연산에 대한 효율성을 높여준다. 중복 제거 방식은 캐싱되지 않은 데이터, 즉 플래시 메모리에 저장되어 있는 데이터와 중복된 데이터가 어플리케이션으로부터 쓰기 연산을 통해 전달되었을 경우, 이를 제거해 줄 수 있도록 하는 방식이다. 이것은 각 파일의 일부분이 변경이 일어났을 경우, 이를 제외한 부분은 쓰기 연산에서 중복이 일어나는 어플리케이션의 특징을 파악해, 쓰기 부분의 중복을 체크하여, 이를 실제 쓰기에서 제거해줌으로써 플래시 메모리 쓰기 연산의 효율성을 높여줄 수 있는 방식이다. 이와 같은 방식을 통해서 플래시 메모리 기반의 파일 시스템에서 가장 문제가 되는 쓰기 연산에 대한 부하를 줄여줌으로써 플래시 파일 시스템의 효율성을 증대할 수 있다.
