Mechanism for determining read-ahead length in a storage system

• US 8,732,406 B1
• Filed: 03/15/2011
• Issued: 05/20/2014
• Est. Priority Date: 03/15/2011
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Pase, Douglas Michael, Faith, Rickard, Vanninen, Matti
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US13/048,486
• Time in Patent Office: 1,162 Days
• Field of Search: 711/137
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

A storage system tracks statistical behavior of client read requests directed to a storage device to form prediction about data that the client will require next. The storage system collects the size of read sequences for various streams into a data structure, which summarizes past behavior of read requests. This data structure reports the number of streams in each equivalence class of stream sizes that is tracked. The data structure is then used to determine expected size of a selected read stream. The data structure is also used to improve predictions about an expected size computed by a known technique.

Claims

1. A method for managing an amount of read-ahead data, comprising:

monitoring client read operations, a client read operation requesting data blocks representing a read stream;

populating a data structure with read stream sizes and read stream counts based upon the client read operations;

evaluating the data structure to select a first read stream having a first read stream size;

evaluating the data structure to identify a set of read streams, where read streams within the set of read streams have read stream sizes equal to or greater than the first read stream size;

generating a stream metric corresponding to the read stream sizes and a count of the read streams within the set of read streams;

determining an expected size of a target read stream based upon the stream metric, the determining comprising;

determining a probability that the first read stream corresponds to the expected size; and

adjusting the expected size, comprising;

responsive to the probability exceeding a first threshold, decreasing the expected size; and

responsive to the probability exceeding a second threshold, increasing the expected size; and

reading ahead a number of data blocks corresponding to a difference between the first read stream size and the expected size after the adjusting.

2. The method of claim 1, the first threshold indicative of the first read stream size being less than the expected size.

3. The method of claim 1, the second threshold indicative of the first read stream size being greater than the expected size.

4. The method of claim 1, the determining an expected size comprising:

using the data structure to determine a next highest populated read stream field in the data structure.

5. The method of claim 1, the data structure corresponding to a storage container of a storage system.

6. The method of claim 1, the populating the data structure comprising:

responsive to a new read stream being within a proximity to an existing read stream, updating at least one of a start address or an end address of the new read stream for incrementing the data structure according to a size of the new read stream.

7. The method of claim 1, the populating the data structure comprising:

responsive to a new read stream not being within a proximity to an existing read stream, creating a new read set of the new read stream.

8. The method of claim 1, the first read stream being a most recently used stream by a client.

9. The method of claim 1, the set of read streams not comprising a most recently used stream by a client.

10. A system for managing an amount of read-ahead data, comprising:

one or more processors; and

memory comprising instructions that when executed by at least one of the one or more processors implement at least some of;

a read streams monitoring engine configured to;

monitor client read operations, a client read operation requesting data blocks representing a read stream; and

populate a data structure with read stream sizes and read stream counts based upon the client read operations;

a read-ahead length computing engine configured to;

evaluate the data structure to select a first read stream having a first read stream size;

evaluate the data structure to identify a set of read streams, where read streams within the set of read streams have read stream sizes equal to or greater than the first read stream size;

generate a stream metric corresponding to the read stream sizes and a count of the read streams within the set of read streams; and

determine an expected size of a target read stream based upon the stream metric, the determining comprising;

determining a probability that the first read stream corresponds to the expected size; and

adjusting the expected size, comprising;

responsive to the probability exceeding a first threshold, decreasing the expected size; and

responsive to the probability exceeding a second threshold, increasing the expected size; and

a read-ahead engine configured to;

read ahead a number of data blocks corresponding to a difference between the first read stream size and the expected size after the adjusting.

11. The system of claim 10, the first threshold indicative of the first read stream size being less than the expected size.

12. The system of claim 10, the second threshold indicative of the first read stream size being greater than the expected size.

13. A computer-readable medium comprising instructions which when executed at least in part via a processor perform a method for managing an amount of read-ahead data, comprising:

monitoring client read operations, a client read operation requesting data blocks representing a read stream;

populating a data structure with read stream sizes and read stream counts based upon the client read operations;

evaluating the data structure to select a first read stream having a first read stream size;

evaluating the data structure to identify a set of read streams, where read streams within the set of read streams have read stream sizes equal to or greater than the first read stream size;

generating a stream metric corresponding to the read stream sizes and a count of the read streams within the set of read streams;

determining an expected size of a target read stream based upon the stream metric, the determining comprising;

determining a probability that the first read stream corresponds to the expected size; and

adjusting the expected size, comprising;

responsive to the probability exceeding a first threshold, decreasing the expected size; and

responsive to the probability exceeding a second threshold, increasing the expected size; and

reading ahead a number of data blocks corresponding to a difference between the first read stream size and the expected size after the adjusting.

14. The computer-readable medium of claim 13, the first threshold indicative of the first read stream size being less than the expected size.

15. The computer-readable medium of claim 13, the second threshold indicative of the first read stream size being greater than the expected size.

16. The computer-readable medium of claim 13, the determining an expected size comprising:

using the data structure to determine a next highest populated read stream field in the data structure.

17. The computer-readable medium of claim 13, the data structure corresponding to a storage container of a storage system.

18. A method for managing an amount of read-ahead data, comprising:

monitoring client read operations, a client read operation requesting data blocks representing a read stream;

populating a data structure with read stream sizes and read stream counts based upon the client read operations;

evaluating the data structure to select a first read stream having a first read stream size;

evaluating the data structure to identify a set of read streams, where read streams within the set of read streams have read stream sizes equal to or greater than the first read stream size;

generating a stream metric corresponding to the read stream sizes and a count of the read streams within the set of read streams;

determining an expected size of a target read stream based upon the stream metric, the determining comprising;

determining a probability that the first read stream corresponds to the expected size; and

adjusting the expected size, comprising;

responsive to the probability exceeding a first threshold indicative of the first read stream size being less than the expected size, decreasing the expected size; and

responsive to the probability exceeding a second threshold indicative of the first read stream size being greater than the expected size, increasing the expected size; and

reading ahead a number of data blocks corresponding to a difference between the first read stream size and the expected size after the adjusting.