Adaptive file readahead technique for multiple read streams

• US 20050114289A1
• Filed: 11/25/2003
• Published: 05/26/2005
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Fair, Robert L.
• Granted Patent: US 7,333,993 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/084 with a shared cache
• 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/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A storage system implements a storage operating system configured to concurrently perform speculative readahead for a plurality of different read streams. Unlike previous implementations, the operating system manages a separate set of readahead metadata for each of the plurality of read streams. Consequently, the operating system can “match” a received client read request with a corresponding read stream, then perform readahead operations for the request in accordance with the read stream'"'"'s associated set of metadata. Because received client read requests are matched to their corresponding read streams on a request-by-request basis, the operating system can concurrently perform readahead operations for multiple read streams, regardless of whether the read streams'"'"' file read requests are received by the storage system in sequential, nearly-sequential or random orders. Further, the operating system can concurrently perform speculative readahead for the plurality of different read streams, even when the read streams employ different readahead algorithms. The invention may be implemented by file-based or block-based storage systems, or combinations thereof.

Claims

1. A method for a storage operating system implemented in a storage system to concurrently perform readahead operations for a plurality of different read streams established in one or more files, directories, vdisks or luns stored in the storage system, the method comprising:

receiving a client read request at the storage system, the client read request indicating client-requested data for the storage operating system to retrieve from a file, directory, vdisk or lun stored in the storage system;

determining whether the received client read request matches any of a plurality of readset data structures (“

readsets”

) allocated for the file, directory, vdisk or lun containing the client-requested data; and

performing readahead operations in accordance with a set of readahead metadata stored in a readset that is determined to match the received client read request.

2. The method of claim 1, further comprising:

allocating at least one readset for each of the one or more files, directories, vdisks or luns in which the plurality of different read streams is established;

generating a separate set of readahead metadata for each of the plurality of different read streams; and

storing each generated set of readahead metadata in a different readset allocated for the file, directory, vdisk or lun in which the read stream associated with the generated set of readahead metadata is established.

3. The method of claim 1, further comprising:

initializing each allocated readset to store a predetermined set of values.

4. The method of claim 2, wherein the number of readsets allocated for a file, directory, vdisk or lun depends on the size of that file, directory, vdisk or lun.

5. The method of claim 4, wherein the number of readsets allocated for a file, directory, vdisk or lun is dynamically increased as the size of that file, directory, vdisk or lun is increased.

6. The method of claim 1, wherein a first readset is determined to match the received client read request if the first readset stores a set of readahead metadata associated with a read stream that is extended by the client-requested data.

7. The method of claim 1, wherein a second readset is determined to match the received client read request when the client-requested data is located within a predetermined fuzzy range associated with the second readset.

8. The method of claim 7, wherein the fuzzy range is derived based on a multiple of a number of client-requested data blocks specified in the received client read request.

9. The method of claim 7, wherein the fuzzy range extends in both a forward direction and a backward direction in relation to a last data block retrieved in a read stream associated with the second readset.

10. The method of claim 1, wherein a third readset is determined to match the received client read request if the third readset is determined to be unused.

11. The method of claim 10, wherein the third readset is determined to be unused when a level value stored in the third readset equals a special indicator value.

12. The method of claim 1, wherein readahead operations are not performed if the storage operating system determines that the file, directory, vdisk or lun containing the client-requested data is accessed using a random access style.

13. The method of claim 12, wherein a DAFS cache hint included in the received client read request indicates that the file, directory, vdisk or lun containing the client-requested data is accessed using a random access style.

14. The method of claim 1, wherein readahead operations are not performed unless:

(i) a readset is determined to match the received client read request; and

(ii) the matching readset stores a set of readahead metadata associated with a read stream that is extended by the client-requested data past a predetermined data block or memory address.

15. The method of claim 1, further comprising:

if the received client read request does not match any of the readsets allocated for the file, directory, vdisk or lun containing the client-requested data, then performing the steps;

identifying the received client read request as being the first read request in a new read stream;

generating a set of readahead metadata associated with the new read stream;

selecting for reuse one of the readsets allocated for the file, directory, vdisk or lun containing the client-requested data; and

storing the generated set of readahead metadata associated with the new read stream in the readset selected for reuse.

16. The method of claim 15, wherein the readset selected for reuse stores a level value that is less than or equal to level values stored in each of the other readsets associated with the file, directory, vdisk or lun containing the client-requested data.

17. The method of claim 1, wherein the client read request received at the storage system is a file-based client read request.

18. The method of claim 1, wherein the client read request received at the storage system is a block-based client read request.

19. A multiprotocol storage appliance, comprising:

a memory configured to store instructions for implementing a storage operating system and further configured to store at least one readset data structure (“

readset”

) associated with a file, directory, vdisk or lun, the readset including;

a level value indicating the readset'"'"'s relative age with respect to other readsets implemented in the memory, the level value being equal to a value that is between a predetermined upper-bound level value and a predetermined lower-bound level value, inclusive;

a count value indicating the number of client read requests processed in a read stream associated with the readset;

a next readahead value indicating a predetermined file offset or memory address, wherein readahead operations are performed by the storage operating system when the read stream associated with the readset is extended past the predetermined file offset or memory address; and

a readahead size value indicating the amount of data that is prefetched by the storage operating system when readahead operations are performed for the read stream associated with the readset.

20. The multiprotocol storage appliance of claim 19, further comprising:

a processor;

at least one storage device configured to store one or more files, directories, vdisks or luns; and

a network adapter that is adapted to receive at least one client read request, the client read request indicating client-requested data contained in a file, directory, vdisk or lun stored in the at least one storage device.

21. The multiprotocol storage appliance of claim 19, wherein the count value is initially set equal to zero.

22. The multiprotocol storage appliance of claim 19, wherein the level value is set equal to a special indicator value when the readset is first allocated, wherein the special indicator value may be outside the range of values defined by the predetermined upper-bound level value and predetermined lower-bound level value.

23. The multiprotocol storage appliance of claim 19, wherein the level value is incremented by a first step size when the received client read request is determined to match the readset, and the level value is decremented by a second step size when the received client read request causes the storage operating system to reuse a different readset data structure in the memory.

24. The multiprotocol storage appliance of claim 23, wherein the first and second step sizes equal one.

25. The multiprotocol storage appliance of claim 23, wherein if the level value is less than a predetermined initial level value and the level value is to be incremented, the level value is set equal to the predetermined initial level value.

26. The multiprotocol storage appliance of claim 19, wherein the count value is incremented by one if the received client read request is determined to match the readset.

27. The multiprotocol storage appliance of claim 20, wherein the readset is determined to be eligible for reuse if (i) the level value stored in the readset is the lowest level value among all the readsets associated with the file, directory, vdisk or lun containing the client-requested data or (ii) the readset is the most-recently accessed readset associated with the file, directory, vdisk or lun containing the client-requested data and the readset stores a count value equal to one.

28. The multiprotocol storage appliance of claim 27, wherein the most-recently accessed readset associated with the file, directory, vdisk or lun containing the client-requested data is located at the head of a linked list of readsets associated with the file, directory, vdisk or lun containing the client-requested data.

29. A storage system that employs a storage operating system to concurrently perform readahead operations for a plurality of different read streams established in one or more files, directories, vdisks or luns stored in the storage system, the method comprising:

means for receiving a client read request at the storage system, the client read request indicating client-requested data for the storage operating system to retrieve from a file, directory, vdisk or lun stored in the storage system;

means for determining whether the received client read request matches any of a plurality of readset data structures (“

readsets”

) allocated for the file, directory, vdisk or lun containing the client-requested data; and

means for performing readahead operations in accordance with a set of readahead metadata stored in a readset that is determined to match the received client read request.

30. A computer-readable media comprising instructions for execution in a processor for the practice of a method for a storage operating system implemented in a storage system to concurrently perform readahead operations for a plurality of different read streams established in one or more files, directories, vdisks or luns stored in the storage system, the method comprising:

receiving a client read request at the storage system, the client read request indicating client-requested data for the storage operating system to retrieve from a file, directory, vdisk or lun stored in the storage system;

determining whether the received client read request matches any of a plurality of readset data structures (“

readsets”

) allocated for the file, directory, vdisk or lun containing the client-requested data; and

performing readahead operations in accordance with a set of readahead metadata stored in a readset that is determined to match the received client read request.