FREE SPACE COLLECTION IN LOG STRUCTURED STORAGE SYSTEMS

摘要

Free space collection in a log structured storage system. In response to receiving a request to collect free space, the segment in a recently invalidated segment list having the largest cumulative sum of invalidation duration values is selected for free space collection if this cumulative sum is larger than the cumulative sum of invalidation duration values for the segment in a stable segment list having the largest cumulative sum of invalidation duration values. Otherwise, the segment in the stable segment list having the largest cumulative sum of invalidation duration values is selected for free space collection. emptying. The selected segments are then emptied and become available for the writing of data to their tracks.

主权项

1. A method for free space collection in a log structured storage system having segments, each segment including a plurality of tracks, the method comprising:
in response to initially writing data to all the tracks of an empty one of the segments, adding an entry for the one segment to a stable segment list, the entry including a collection score value of zero; in response to invalidating a track in one of the segments to which data has been written:
adding an entry for the invalidated track to an invalidated track list (ITL); andremoving the segment from the stable segment list, if it is in the stable segment list, and adding an entry for the segment to a recently invalidated segment list, if such an entry is not in the recently invalidated segment list; periodically determining a collection score value for each segment with a track in the ITL by calculating a cumulative sum of invalidation duration values corresponding to the durations that tracks belonging to the segment have remained on the ITL; in response to determining that the collection score value for a track in the ITL is greater than a predetermined collection score threshold value, setting the collection score to the collection score threshold value and removing the track from the ITL; in response to determining that a segment in the recently invalidated segment list has no associated tracks in the ITL, moving the segment from the recently invalidated segment list to the stable segment list; in response to receiving a request to collect free space in the log structured storage system, selecting for free space collection the segment in the recently invalidated segment list having the largest cumulative sum of invalidation duration values if this cumulative sum is larger than the cumulative sum of invalidation duration values for the segment in the stable segment list having the largest cumulative sum of invalidation duration values, otherwise, selecting for free space collection the segment in the stable segment list having the largest cumulative sum of invalidation duration values; and emptying the selected segments, whereby the emptied segments become available for the writing of data to their tracks.