Disk I/O is a major performance bottleneck in modern computer systems. The Log-structured File System (LFS) [12,15,16] tries to improve the I/O performance by combining small write requests into large logs. While LFS can significantly improve the performance for small-write dominated workloads, it suffers from a major drawback, namely the garbage collection overhead or cleaning overhead. LFS has to constantly re-organize the data on the disk, through a process called garbage collection or cleaning, to make space for new data. Previous studies have shown that the garbage collection overhead can considerably reduce the LFS performance under heavy workloads. Seltzer et al. [17] pointed out that cleaning overhead reduces LFS performance by more than 33% when the disk is 50% full. Due to this significant problem, LFS has limited success in real-world operating system environments, although it is used internally by several RAID (Redundant Array of Inexpensive Disks) systems [20,10]. Therefore it is important to reduce the garbage collection overhead in order to improve the performance of these RAID systems and to make LFS more successful in the operating system field.
Several schemes have been proposed [9,20] to speed up the garbage collection process. These algorithms focus on improving the efficiency of garbage collection after data has been written to the disk. In this paper, we propose a novel method that tries to reduce the I/O overhead during the garbage collection, by reorganizing data in two or more segment buffers, before data is written to the disk.