Patent ID: 9513817
Filing Date: 2016-12-06
CPC Classification: G06F

Claim Text:
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: 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.