Hard disk-based file system is a core component of today`s computer systems. As the principal means of sharing and storing data, the file system needs to be both reliable and fast. Unfortunately, improvements in file system performance have lagged improvements in processor performance and disk bandwidth. The performance gap is most pronounced when applications manipulate small files. The gap is especially felt in the UNIX world, where small tools that manipulate small files are the norm.
Small file performance can be improved by grouping and clustering, each of which places multiple files in a directory and places blocks of the same file on disks contiguously. These schemes make it possible for file systems to use large data transfers in accessing small files, reducing disk accesses. However, as file systems become aged, disks become too fragmented to support the grouping and clustering of small files. This fragmentation makes it difficult for file systems to take advantage of large data transfers, increasing disk I/Os.
This dissertation introduces a novel file system called De-Fragmented File System (DFFS), which offers a solution to the problem caused by file system aging. DFFS provides two adaptive mechanisms, IntrA-file De-fragmentation (IAD) and IntEr-file De-fragmentation (IED) mechanisms. These mechanisms relocate and cluster related data in a dynamic manner by using data cached in memory. First, IAD relocates and clusters data blocks of small fragmented files. Second, IED clusters related small files in the same directory at contiguous disk locations.
DFFS exploits a technique called journaling to prevent data on disks from being lost due to system failures such as a power failure. The journaling records file system changes in an append-only log file. In particular, DFFS logs blocks that will be overwritten by the relocating blocks when a target region is de-fragmented. After the crash, DFFS replays the logs to rollback the logged blocks to their original disk locations.
Finally, DFFS was implemented on a personal computer system running an OpenBSD operating system. Measurements show that DFFS alleviates small file fragmentation by up to 150% and 260% compared to FFS. This alleviation makes it possible for DFFS to improve small file performance over FFS by 47% and 78% respectively.
최근 디스크의 성능은 데이터 전송 대역폭이 40 M/B 정도에 이를 만큼 크게 향상 되었다. 개선된 성능은 기존의 파일 시스템의 큰 파일 참조 속도를 크게 향상시켰다. 하지만, 작은 크기의 파일에 대해서는 성능 향상이 크지 않다. 이 이유는 작은 파일의 참조 시에 디스크 데이터 전송 속도 보다 헤더의 움직임이 대부분을 차지하기 때문이다.
작은 파일의 성능은 디스크 참조 횟수에 크게 의존한다. Fast File System (FFS) 및 Co-located Fast File System (C-FFS) 파일 시스템은 각각 클러스터링 (Clustering) 및 그룹 나누기 (Grouping)을 사용한다. 먼저 FFS에서는 파일 내의 논리적으로 연속적인 블록들을 디스크 상에서 물리적으로 연속적으로 배치토록 한다. 연속적으로 배치된 블록들은 한번에 여러 개의 블록을 참조하는 다중 블록 전송 방식에 의해서 참조될 수 있다. 따라서, 더 적은 디스크 참조 횟수로 파일을 참조할 수 있기 때문에 성능 향상에 큰 기여를 한다. C-FFS의 경우, 서로 연관성이 있는 작은 파일들(즉, 동일한 디렉토리에 포함된 파일들)을 디스크 상에 서로 연속적으로 배치시키며, 그 파일들 중 한 파일을 읽을 때 연속적으로 배치된 다른 파일들을 미리 읽어 메모리에 저장한다. 이때, 연속적으로 배치된 파일들을 그룹이라 하며, 미리 읽혀진 파일을 참조할 때 디스크를 참조하지 않기 때문에 성능을 극대화할 수 있다. FFS와 C-FFS는 심각한 공통적인 문제들을 가지고 있다. 그것은 디스크의 조각화 (Fragmentation)이다. 디스크를 오래 사용하면서 많은 파일을 생성 및 제거하게 되면 디스크가 조각나게 된다. 이 조각화 때문에 FFS에서는 파일 내의 블록들을 디스크에 연속적으로 배치할 수 없을 만큼 빈 공간이 조각나게 된다. 따라서, FFS는 파일 블록의 클러스트링에 실패한다. 이때, 한 파일 내의 블록 간의 조각화를 IntrA-file Fragmenation (IAF) 이라고 한다. 또한, C-FFS에서는, 파일들이 생성 및 제거가 반복될 때 그 제거는 그룹 내에 빈 공간을 생성시키게 된다. 이 빈 공간에 의해 그룹에 포함될 수 있는 파일들의 수가 적어지게 된다. 따라서, 미리 읽어올 수 있는 파일의 수가 적어지게 되고, C-FFS의 장점을 얻을 수 없게 된다. 서로 관련된 파일들 간의 조각화를 IntEr-file Fragmentation (IEF) 라고 한다. 또한, 두 파일 시스템이 한번 데이터의 위치가 결정되면 더 이상 변경할 수 없는 update-in-place 방식에 포함된다. 비록 데이터 위치를 재배치를 하면 클러스팅과 그룹 나누기(Grouping) 등이 가능한 환경임에도 불구하고, update-in-place 특성 때문에 그러한 동작을 하지 않는다. 이러한 특성 때문에 특히 파일 참조시 disk seek를 겪는 데이터는 전체 파일 시스템의 성능을 크게 감소시킨다.
본 논문은 파일 시스템의 조각화 문제점을 해결하기 위해서 De-Fragmented File System (DFFS)을 제안한다. DFFS는 메모리 상에 존재하며 IAF 및 IEF 을 가진 작은 파일들 (예, 2 - 12 블록 크기)의 블록 위치를 재배치하는 파일 시스템이다. DFFS는 IAF 및 IEF를 제거하기 위해서 각각 IAD (IntrA-file Defragmentation) 및 IED(IntEr-file Defragmentation)을 소개한다. 첫째, IAD는 한 파일 내에 존재하는 블록들을 디스크 상에서 연속적으로 재배치 (relocation)하는 방법이다. 둘째, IED는 한 디렉토리 내에 속하는 작은 파일들을 디스크 상에 연속적으로 재배치를 하는 방법이다. 이 방법은 잠재적으로 C-FFS의 성능을 매우 증가시킬 수 있다. 이 재배치는 파일 시스템의 플러싱 (Flushing) 시기 동안 이루어진다. 즉, 한 개의 변경된 블록이 디스크로 저장될 때 그 블록을 시작으로 일정한 윈도우 (Window) 내에 있는 블록들이 IAF 또는 IEF가 존재하는지 검사한다. 만일 존재할 경우, DFFS는 그 영역에 존재하는 블록들을 위치를 변경하고 그 변경된 데이터와 함께 한번의 디스크 쓰기로 저장한다. 하지만, 추가적인 쓰기
부하는 크지 않다. 왜냐하면, 최근의 디스크들은 한 블록을 참조하는 것과 여러 블록을 한 번에 참조하는 부하가 거의 비슷하기 때문이다. 이 DFFS는 이러한 하드웨어 특성을 이용한다. 또한, DFFS는 단지 메모리 상에 존재하는 블록들에 대해서 재배치를 하기 때문에 추가적으로 디스크에서 데이터를 읽는 부하는 없다.
본 논문에서는, DFFS 파일 시스템의 데이터 무결성(Data integrity)을 위한 알고리즘을 제안한다. 재배치 과정 중에 갑작스러운 시스템 사고 등이 발생했을 때 파일 시스템에서 데이터 데이터 손실을 막아야 한다. 이를 위해 DFFS에 적합한 저널링 (journaling) 알고리즘을 제안한다. 기존의 journaling 알고리즘을 그대로 적용할 경우 상당히 큰 디스크 부하가 발생할 수 있다. 이러한 문제점을 해결하기 위해 다중 타깃 영역 로깅 (Logging of multiple target regions)을 고용했다. 이 로깅 방법은 DFFS 동작과 비슷하게 최근 디스크의 고성능 대역폭을 이용하기 때문에 잦은 디스크 움직임을 최소화할 수 있는 것이 큰 특징이다. DFFS는 Pentium III 700 MHz, 128 MB 메인 메모리 및 OpenBSD 버전 2.8를 가지는 PC에서 한 개의 모듈로 구현되었다. 성능 측정을 위해 사용된 벤치마크는 실제 파일 시스템 사용 패턴을 그대로 실행할 수 있도록 합성되었다. 이러한 벤치마크를 장시간 수행함으로써 FFS 및 DFFS의 성능을 비교했다. 그 비교에서 DFFS는 디스크 조각화 정도 (Aggregate layout score)에서 FFS보다 260%까지 앞섰으며, 작은 파일의 읽기 성능을 최고 78%까지 개선시켰다. 반면에, 파일 시스템의 플러싱 부하가 증가하였다. 하지만, 이러한 플러싱 부하는 전체 시스템의 성능에 크게 영향을 미치지 않기 때문에 크게 걱정할 필요가 없다. 결국 DFFS는 수시로 변경된 데이터가 있으면 언제든지 디스크의 조각화를 점차적으로 완화시킨다. 이러한 조각화 문제를 해결함으로써 작은 파일의 읽기 성능을 개선시키는 시스템이다.
