Analysis of reorganization overhead in log-structured file systems

Abstract

In a log-structured file system (LFS), in general each block written to disk causes another disk block to become invalid data, resulting in one block of free space. Over time free disk space becomes highly fragmented, and a high level of dynamic reorganization may be required to coalesce free blocks into physically contiguous areas that subsequently can be used for logs. By consuming available disk bandwidth, this reorganization can degrade system performance. In a segmented disk LFS organization, the copy-and-compact reorganization method reads entire segments and then writes back all valid blocks. Other methods, suggested by earlier work on reduction of storage fragmentation for non-LFS disks, may access far fewer blocks (at the cost of increased CPU time). Here, an analytic model is used to evaluate the effects on available disk bandwidth of dynamic reorganization, as a function of the read/write ratio, storage utilization, and degree of data movement required by dynamic reorganization for steady-state operation. It is shown that decreasing reorganization overhead can have dramatic effects on available disk bandwidth.