Performance of the Greedy Garbage-Collection Scheme in Flash-Based Solid-State Drives

In flash-based solid-state drives (SSD) and log-structured file systems, new data is written out-of-place, which over time exhausts the available free space. New free space is created by the garbage-collection process, which reclaims the space occupied by invalidated data. The write amplification, incurred because of the additional write operations performed by the garbage-collection mechanism is a critical factor that negatively affects the lifetime and endurance of SSDs. A theoretical model is developed to evaluate the impact of the greedy garbage-collection mechanism on the performance of large storage systems. The system operation and behavior are comprehensively characterized for uniformly-distributed random small user writes. Results of theoretical and practical importance are analytically derived and confirmed by means of simulation. Closed-form expressions are derived for both the number of relocated pages and the write amplification. The write amplification is analytically assessed for the key system parameters, i.e., the total system memory space, the proportion of the memory space occupied by valid user data, and the block size in terms of number of pages. Our results demonstrate that as the system occupancy increases, the write amplification increases. Furthermore, as the number of pages contained in a block increases, the write amplification increases and approaches an upper bound. They also show that the number of free pages reclaimed by the greedy garbage-collection mechanism after each block recycling takes one of two successive values, which provides a quasi-deterministic performance guarantee.