Granted Patent B2

US 12,050,556 · App. 17/359,774 · Granted Jul 30, 2024

Inventors: Lior Kamran (Rishon LeZion, IL); Vladimir Shveidel (Pardes-Hana, IL); Amitai Alkalay (Kadima, IL)

Assignee: EMC IP Holding Company LLC

G06F16/1724G06F16/164

Abstract

Claims (107)

1. A method, comprising:

maintaining stripe metadata corresponding to a plurality of stripes of data stored on a plurality of storage devices of a storage system, the stripe metadata comprising at least a first timestamp, a second timestamp and a read count for each stripe, the first and second timestamps for a given one of the stripes being associated with potentially different read requests directed to the given stripe, each of the first and second timestamps being stored as part of the stripe metadata and collectively defining a variable-length interval that is compared to a threshold interval to control resetting of the read count, the variable-length interval for the given stripe being updated with each of a plurality of additional read requests following a first read request associated with the first timestamp, by updating of the second timestamp to a timestamp associated with a most recent one of the plurality of additional read requests;

obtaining a read request associated with a given stripe of the plurality of stripes, the read request having an associated timestamp;

determining, based at least in part on the obtained read request, whether or not a time period for the given stripe has been exceeded;

updating the stripe metadata corresponding to the given stripe based at least in part on the determination of whether or not the time period for the given stripe has been exceeded and the associated timestamp of the read request;

determining a read access frequency of the given stripe based at least in part on the read count, the first timestamp and the second timestamp of the updated stripe metadata for the given stripe, wherein determining the read access frequency comprises computing the read access frequency as a function of the read count and the variable-length interval collectively defined by the first and second timestamps; and

performing at least one of a defragmentation process and a rebuild process based at least in part on the determined read access frequency of the given stripe;

wherein the stripe metadata corresponding to the plurality of stripes of data further comprises a plurality of different metadata portions for respective ones of a plurality of read access frequency intervals, each read access frequency interval corresponding to a range of read access frequency values, each read access frequency interval having a corresponding data structure that comprises an indication of which stripes have read access frequencies that are within that read access frequency interval; and

wherein the method is performed by at least one processing device of the storage system, the at least one processing device comprising a processor coupled to memory.

2. The method of claim 1 , wherein:

determining whether or not the time period for the given stripe has been exceeded comprises determining that the time period for the given stripe has been exceeded; and

updating the stripe metadata corresponding to the given stripe comprises:

resetting the read count;

setting the first timestamp to the associated timestamp of the read request;

setting the second timestamp to the associated timestamp of the read request; and

incrementing the read count.

3. The method of claim 1 , wherein:

determining whether or not the time period for the given stripe has been exceeded comprises determining that the time period for the given stripe has not been exceeded; and

updating the stripe metadata corresponding to the given stripe comprises:

setting the second timestamp to the associated timestamp of the read request; and

incrementing the read count.

4. The method of claim 1 , further comprising:

updating the indication in the data structure corresponding to the read access frequency interval comprising the read access frequency of the given stripe to include an indication that the given stripe has a read access frequency within that read access frequency interval; and

performing the at least one of the defragmentation process and the rebuild process based at least in part on the determined read access frequency of the given stripe comprises performing the at least one of the defragmentation process and the rebuild process based at least in part on the plurality of read access frequency intervals.

5. The method of claim 4 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the defragmentation process, the defragmentation process comprising:

selecting a source stripe for defragmentation;

determining a read access frequency of the source stripe based at least in part on the stripe metadata for the source stripe;

selecting the read access frequency interval that corresponds to the read access frequency of the source stripe;

determining which stripes indicated by the data structure corresponding to the selected read access frequency interval have sufficient available space to store data pages to be relocated from the source stripe;

selecting one of the determined stripes that has sufficient available space as a destination stripe; and

relocating the data pages of the source stripe to the destination stripe.

6. The method of claim 5 , wherein selecting the one of the determined stripes that has sufficient available space as the destination stripe further comprises one of:

selecting the determined stripe that has the highest read access frequency;

selecting the determined stripe that has the smallest amount of available space.

7. The method of claim 4 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the rebuild process, the rebuild process comprising:

determining that a storage device has failed;

selecting the read access frequency interval that corresponds to the highest range of read access frequencies for which all stripes have not been rebuilt;

determining which stripes have not yet been rebuilt for the selected read access frequency interval based at least in part on the indication of which stripes have read access frequencies that are within the selected read access frequency interval;

selecting the next stripe for rebuilding based at least in part the determination of which stripes have not yet been rebuilt; and

rebuilding the selected next stripe.

8. The method of claim 7 , wherein selecting the next stripe for rebuilding comprises one of:

selecting the stripe that has not yet been rebuilt that has the highest read access frequency in the selected read access frequency interval; and

selecting the stripe that has not yet been rebuilt that is next in order in the data structure.

9. An article of manufacture comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code is executable by one or more processors to implement a method which comprises:

maintaining stripe metadata corresponding to a plurality of stripes of data stored on a plurality of storage devices of a storage system, the stripe metadata comprising at least a first timestamp, a second timestamp and a read count for each stripe, the first and second timestamps for a given one of the stripes being associated with potentially different read requests directed to the given stripe, each of the first and second timestamps being stored as part of the stripe metadata and collectively defining a variable-length interval that is compared to a threshold interval to control resetting of the read count, the variable-length interval for the given stripe being updated with each of a plurality of additional read requests following a first read request associated with the first timestamp, by updating of the second timestamp to a timestamp associated with a most recent one of the plurality of additional read requests;

obtaining a read request associated with a given stripe of the plurality of stripes, the read request having an associated timestamp;

determining, based at least in part on the obtained read request, whether or not a time period for the given stripe has been exceeded;

updating the stripe metadata corresponding to the given stripe based at least in part on the determination of whether or not the time period for the given stripe has been exceeded and the associated timestamp of the read request;

determining a read access frequency of the given stripe based at least in part on the read count, the first timestamp and the second timestamp of the updated stripe metadata for the given stripe, wherein determining the read access frequency comprises computing the read access frequency as a function of the read count and the variable-length interval collectively defined by the first and second timestamps; and

performing at least one of a defragmentation process and a rebuild process based at least in part on the determined read access frequency of the given stripe;

wherein the stripe metadata corresponding to the plurality of stripes of data further comprises a plurality of different metadata portions for respective ones of a plurality of read access frequency intervals, each read access frequency interval corresponding to a range of read access frequency values, each read access frequency interval having a corresponding data structure that comprises an indication of which stripes have read access frequencies that are within that read access frequency interval.

10. The article of manufacture of claim 9 , wherein:

the method further comprises:

updating the indication in the data structure corresponding to the read access frequency interval comprising the read access frequency of the given stripe to include an indication that the given stripe has a read access frequency within that read access frequency interval; and

performing the at least one of the defragmentation process and the rebuild process based at least in part on the determined read access frequency of the given stripe comprises performing the at least one of the defragmentation process and the rebuild process based at least in part on the plurality of read access frequency intervals.

11. The article of manufacture of claim 10 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the defragmentation process, the defragmentation process comprising:

selecting a source stripe for defragmentation;

determining a read access frequency of the source stripe based at least in part on the stripe metadata for the source stripe;

selecting the read access frequency interval that corresponds to the read access frequency of the source stripe;

determining which stripes indicated by the data structure corresponding to the selected read access frequency interval have sufficient available space to store data pages to be relocated from the source stripe;

selecting one of the determined stripes that has sufficient available space as a destination stripe; and

relocating the data pages of the source stripe to the destination stripe.

12. The article of manufacture of claim 11 , wherein selecting the one of the determined stripes that has sufficient available space as the destination stripe further comprises one of:

selecting the determined stripe that has the highest read access frequency;

selecting the determined stripe that has the smallest amount of available space.

13. The article of manufacture of claim 10 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the rebuild process, the rebuild process comprising:

determining that a storage device has failed;

selecting the read access frequency interval that corresponds to the highest range of read access frequencies for which all stripes have not been rebuilt;

determining which stripes have not yet been rebuilt for the selected read access frequency interval based at least in part on the indication of which stripes have read access frequencies that are within the selected read access frequency interval;

selecting the next stripe for rebuilding based at least in part the determination of which stripes have not yet been rebuilt; and

rebuilding the selected next stripe.

14. The article of manufacture of claim 13 , wherein selecting the next stripe for rebuilding comprises one of:

selecting the stripe that has not yet been rebuilt that has the highest read access frequency in the selected read access frequency interval; and

selecting the stripe that has not yet been rebuilt that is next in order in the data structure.

15. An apparatus, comprising:

a storage system comprising a plurality of stripes of data stored on a plurality of storage devices; and

at least one processing device comprising a processor coupled to memory, the at least one processing device being configured:

to maintain stripe metadata corresponding to a plurality of stripes, the stripe metadata comprising at least a first timestamp, a second timestamp and a read count for each stripe, the first and second timestamps for a given one of the stripes being associated with potentially different read requests directed to the given stripe, each of the first and second timestamps being stored as part of the stripe metadata and collectively defining a variable-length interval that is compared to a threshold interval to control resetting of the read count, the variable-length interval for the given stripe being updated with each of a plurality of additional read requests following a first read request associated with the first timestamp, by updating of the second timestamp to a timestamp associated with a most recent one of the plurality of additional read requests;

to obtain a read request associated with a given stripe of the plurality of stripes, the read request having an associated timestamp;

to determine, based at least in part on the obtained read request, whether or not a time period for the given stripe has been exceeded;

to update the stripe metadata corresponding to the given stripe based at least in part on the determination of whether or not the time period for the given stripe has been exceeded and the associated timestamp of the read request;

to determine a read access frequency of the given stripe based at least in part on the read count, the first timestamp and the second timestamp of the updated stripe metadata for the given stripe, wherein determining the read access frequency comprises computing the read access frequency as a function of the read count and the variable-length interval collectively defined by the first and second timestamps; and

to perform at least one of a defragmentation process and a rebuild process based at least in part on the determined read access frequency of the given stripe;

wherein the stripe metadata corresponding to the plurality of stripes of data further comprises a plurality of different metadata portions for respective ones of a plurality of read access frequency intervals, each read access frequency interval corresponding to a range of read access frequency values, each read access frequency interval having a corresponding data structure that comprises an indication of which stripes have read access frequencies that are within that read access frequency interval.

16. The apparatus of claim 15 , wherein:

the at least one processing device is further configured:

to update the indication in the data structure corresponding to the read access frequency interval comprising the read access frequency of the given stripe to include an indication that the given stripe has a read access frequency within that read access frequency interval; and

to perform the at least one of the defragmentation process and the rebuild process based at least in part on the determined read access frequency of the given stripe comprises performing the at least one of the defragmentation process and the rebuild process based at least in part on the plurality of read access frequency intervals.

17. The apparatus of claim 16 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the defragmentation process, the defragmentation process comprising:

selecting a source stripe for defragmentation;

determining a read access frequency of the source stripe based at least in part on the stripe metadata for the source stripe;

selecting the read access frequency interval that corresponds to the read access frequency of the source stripe;

determining which stripes indicated by the data structure corresponding to the selected read access frequency interval have sufficient available space to store data pages to be relocated from the source stripe;

selecting one of the determined stripes that has sufficient available space as a destination stripe; and

relocating the data pages of the source stripe to the destination stripe.

18. The apparatus of claim 17 , wherein selecting the one of the determined stripes that has sufficient available space as the destination stripe further comprises one of:

selecting the determined stripe that has the highest read access frequency;

selecting the determined stripe that has the smallest amount of available space.

19. The apparatus of claim 16 , wherein performing the at least one of the defragmentation process and the rebuild process comprises performing the rebuild process, the rebuild process comprising:

determining that a storage device has failed;

selecting the read access frequency interval that corresponds to the highest range of read access frequencies for which all stripes have not been rebuilt;

determining which stripes have not yet been rebuilt for the selected read access frequency interval based at least in part on the indication of which stripes have read access frequencies that are within the selected read access frequency interval;

selecting the next stripe for rebuilding based at least in part the determination of which stripes have not yet been rebuilt; and

rebuilding the selected next stripe.

20. The apparatus of claim 19 , wherein selecting the next stripe for rebuilding comprises one of:

selecting the stripe that has not yet been rebuilt that has the highest read access frequency in the selected read access frequency interval; and

selecting the stripe that has not yet been rebuilt that is next in order in the data structure.

Assignments (8)

Continuity (1)