Hole plugging garbage collection for a data storage system

Abstract

A data storage management system performs garbage collection to reduce fragmentation in storage by moving data from source fragmented areas to holes (unused storage space) in target fragmented areas, rather than copying data to the end of an extending target area. New areas are not consumed. Preferably, source areas are emptier (i.e., more fragmented) relative to the whole set of areas in the storage system, and target areas are fuller (i.e., less fragmented) relative to the whole set of areas in the storage system. The goal of freeing (defragmenting) an area is realized with fewer I/O moves, if most areas are lightly fragmented, because fragmentation is reduced in more than one area substantially concurrently. Namely, fragmentation is eliminated in a source area by continuing to empty the area (i.e., by moving the data from the source area) and, substantially concurrently, fragmentation is reduced in a target area by continuing to fill the area (i.e., by moving/plugging the data into holes in the target area). In a lightly fragmented storage, this reduction in moves outweighs the increased cost incurred for read-modify-write in parity storage, thereby providing better overall garbage collection efficiency and performance.