Garbage collection in log-structured information storage systems using age threshold selection of segments

Claim 1

A method for performing a garbage collection process in an information storage system having direct access storage units in which information segments are located, the method comprising the steps of: selecting an age threshold value; determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.

Claim 2

A method for performing a garbage collection process in an information storage system having direct access storage units in which information segments are located, the method comprising the steps of: selecting an age threshold value; determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.

Claim 11

A method for managing storage of information segments in a computer processing system that stores information in a plurality of direct access storage devices, the method comprising the steps of: setting the age of a segment filled by track writing operations to a current value of a destage clock; placing the filled segment at a tail position of a first-in, first-out (FIFO) queue; designating a segment from a head position of the FIFO queue as a garbage collection candidate if the age of the segment is greater than an age threshold value; ordering a plurality of designated candidate segments in accordance with their respective free space yield upon garbage collection; and choosing candidate segments for performing a garbage collection process in the order of their relative yield ranking such that candidate segments with lower yield rankings are selected before candidate segments with higher yield rankings.

Claim 12

A method for managing storage of information segments in a computer processing system that stores information in a plurality of direct access storage devices, the method comprising the steps of: setting the age of a segment filled by track writing operations to a current value of a destage clock; placing the filled segment at a tail position of a first-in, first-out (FIFO) queue; designating a segment from a head position of the FIFO queue as a garbage collection candidate if the age of the segment is greater than an age threshold value; ordering a plurality of designated candidate segments in accordance with their respective free space yield upon garbage collection; and choosing candidate segments for performing a garbage collection process in the order of their relative yield ranking such that candidate segments with lower yield rankings are selected before candidate segments with higher yield rankings.

Claim 19

A method for performing a garbage collection process in a computer processing system that stores information segments, the method comprising the steps of: setting an age threshold value to an initial value of zero; selecting a garbage collection direction to an up value; determining an initial garbage collection utilization (GCU) measurement value over a predetermined amount of time; determining an initial age threshold value by performing the steps of: adjusting the age threshold value by increasing the age threshold value if the garbage collection direction has an up value, and decreasing the age threshold value if the garbage collection direction has a down value, calculating the GCU value over the time since the last determined GCU value, and selecting the garbage collection direction to be the opposite of its current value if the calculated GCU value is worse than the last determined GCU value and maintaining the garbage collection direction at its current value if the calculated GCU value otherwise; and responding to a garbage collection command by performing garbage collection on partially-filled segments of the computer processing system according to the steps of: determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.

Claim 20

A method for performing a garbage collection process in a computer processing system that stores information segments, the method comprising the steps of: setting an age threshold value to an initial value of zero; selecting a garbage collection direction to an up value; determining an initial garbage collection utilization (GCU) measurement value over a predetermined amount of time; determining an initial age threshold value by performing the steps of: adjusting the age threshold value by increasing the age threshold value if the garbage collection direction has an up value, and decreasing the age threshold value if the garbage collection direction has a down value, calculating the GCU value over the time since the last determined GCU value, and selecting the garbage collection direction to be the opposite of its current value if the calculated GCU value is worse than the last determined GCU value and maintaining the garbage collection direction at its current value if the calculated GCU value otherwise; and responding to a garbage collection command by performing garbage collection on partially-filled segments of the computer processing system according to the steps of: determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.

Claim 29

A method for determining when a filled segment in a log-structured file information storage system should be subjected to a garbage collection process, the method comprising the steps of: calculating an age threshold value defined by F×S×{1-ASU- (max-empty-min-empty)/(S-min-empty)!}, where: 0<=F<=1,ASU=average segment utilization, max-empty is a maximum number of empty segments, min-empty is a minimum number of empty segments, and S is the number of segments in the information storage system; and responding to a garbage collection command by performing garbage collection on partially-filled segments of the computer processing system according to the steps of: determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.

Claim 30

A method for determining when a filled segment in a log-structured file information storage system should be subjected to a garbage collection process, the method comprising the steps of: calculating an age threshold value defined by F×S×{1-ASU- (max-empty-min-empty)/(S-min-empty)!}, where: 0<=F<=1,ASU=average segment utilization, max-empty is a maximum number of empty segments, min-empty is a minimum number of empty segments, and S is the number of segments in the information storage system; and responding to a garbage collection command by performing garbage collection on partially-filled segments of the computer processing system according to the steps of: determining an age value for each segment that indicates the time that segment has been located in a direct access storage device and designating each segment as a candidate for garbage collection if the segment has an age value greater than the age threshold value; and choosing a candidate segment for garbage collection if it will yield a maximized amount of free space.