Adaptive file readahead technique for multiple read streams

• US 7,333,993 B2
• Filed: 11/25/2003
• Issued: 02/19/2008
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Fair, Robert L.
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Ahluwalia; Navneet K
• Application Number:
  US10/721,596
• Publication Number:
  US 20050114289A1
• Time in Patent Office: 1,547 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 709200-250
• US Class Current: 707/770
• 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:

allocating at least one readset data structure (“

readset”

) for each of the one or more files, directories, vdisks or luns in which the plurality of different read streams is established, wherein the number of readsets allocated for each file, directory, vdisk or lun depends on the size of that file, directory, vdisk or lun;

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 the plurality of readsets allocated for the file, directory, vdisk or lun containing the client-requested data;

performing readahead operations in accordance with a set of readahead metadata stored in an associated readset that is determined to match the received client read request, wherein the readahead metadata describes the associated readset; and

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.

2. The method of claim 1, further comprising:

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 is dynamically increased as the size of that file, directory, vdisk or lun is increased.

5. 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.

6. 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.

7. The method of claim 6, 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.

8. The method of claim 6, 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.

9. 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.

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

11. 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.

12. The method of claim 11, 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.

13. 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.

14. The method of claim 1, wherein the read set 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.

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

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

17. 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 storage system comprising:

means for allocating at least one readset data structure (“

readset”

) for each of the one or more files, directories, vdisks or luns in which the plurality of different read streams is established, wherein the number of readsets allocated for each file, directory, vdisk or lun depends on the size of that file, directory, vdisk or lun;

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 the plurality of readsets”

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

means for performing readahead operations in accordance with a set of readahead metadata stored in an associated readset that is determined to match the received client read request, wherein the readahead metadata describes the associated readset; and

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 means for performing;

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

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

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

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

18. 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:

allocating at least one readset data structure (“

readset”

) for each of the one or more files, directories, vdisks or luns in which the plurality of different read streams is established, wherein the number of readsets allocated for each file, directory, vdisk or lun depends on the size of that file, directory, vdisk or lun;

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 the plurality of readsets allocated for the file, directory, vdisk or lun containing the client-requested data;

performing readahead operations in accordance with a set of readahead metadata stored in an associated readset that is determined to match the received client read request, wherein the readahead metadata describes the associated readset; and

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.

19. 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 stored in the storage system, comprising:

allocating at least one read ser data structure (“

readset”

) for each of the one or more files, directories, vdisks or luns in which the plurality of different read streams is established wherein the number of readsets allocated for each file depends on the size of that file;

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 in which the read stream associated with the generated set of readahead metadata is established;

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, stored in the storage system;

determining whether the received client read request matches any of a plurality of readsets allocated for the file 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; and

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 xvith the new read stream;

selecting for reuse one of the readsets allocated for the file, directory, vdisk or kin 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.

20. The method of claim 19, wherein the file is broad term describing either a file, directory, vdisk or lun.

21. The method of claim 19, further comprising:

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

22. The method of claim 19, wherein the number of readsets allocated for a file is dynamically increased as the size of that file is increased.

23. The method of claim 19, 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.

24. The method of claim 19, 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.

25. The method of claim 24, 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.

26. The method of claim 24, 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.

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

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

29. The method of claim 19, 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.

30. The method of claim 29, wherein a DAPS 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.

31. The method of claim 19, 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.

32. The method of claim 19, 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.

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

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