Analysis of Steady-State Segment Storage Utilizations in a Log-Structured File System with Least-Utilized Segment Cleaning

Abstract

The steady-state distribution of storage utilizations of segments in a log-structured file system with least-utilized (greedy) segment cleaning is found using analytic methods. Furthermore, it is shown that as the number of segments increases, this distribution approaches a limiting continuous distribution, which is also derived. These results could be useful for preliminary performance analysis of LFS-type system designs prior to the development of detailed simulation models or actual implementation.