Free space collection in log structured storage systems

Patent metadata

Field	Value
Publication number	US-9513817-B2
Application number	US-201615160019-A
Country	US
Kind code	B2
Filing date	May 20, 2016
Priority date	Sep 6, 2012
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

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.

First claim

What is claimed is:

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); and
removing 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.

2. The method of claim 1 , wherein the predetermined collection score threshold value is equal to one hour.

3. The method of claim 1 , wherein determining the collection score value comprises calculating an estimated collection score value for at least one of the plurality of segments and wherein selecting the one or more segments comprises selecting the one or more segments from among the plurality of segments for free space collection based on the determined estimated collection score value.

Assignees

• IBM

Inventors

• Mcnutt Bruce

Classifications

• G06F2212/466

  Metadata, control data · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/0611 Primary

  in relation to response time · CPC title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title