Mechanism for determining read-ahead length in a storage system

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.

RELATED APPLICATIONS

This application is related to U.S. Pat. No. 7,631,148, commonly assigned to NetApp, Inc., entitled ADAPTIVE FILE READ-AHEAD TECHNIQUE FOR MULTIPLE READ STREAMS, by Robert L. Fair, the teachings of which are expressly incorporated herein by reference.

FIELD OF THE INVENTION

The inventive techniques described herein relate to storage systems and, more specifically, to a novel mechanism for a storage system to determine length of read-ahead operations for read streams.

BACKGROUND OF THE INVENTION

A storage system provides storage service relating to the organization of information on storage devices. The storage system may be configured to operate according to a client-server model of information delivery to allow many client systems to access shared resources, such as data containers, stored on the storage system. An application may reside on a client system connected over a network to a storage system, such as a controller provided by NetApp, Inc., of Sunnyvale, Calif., or it may reside on the storage system itself. In either implementation, the application sends requests for data to the storage system and the requested data are returned to the application by the storage system.

The storage system may retrieve the requested data from the storage device or from a memory, if the requested data are in the memory. Retrieving data from the memory is faster than retrieving data from the storage device, such as a disk. However, since the memory has size limitations, the storage system predicts what data might be needed before the request is made in order to have the data in the memory when the request arrives. The storage system may employ speculative read-ahead operations to retrieve data blocks that are likely to be requested by future client read requests. These “read-ahead” blocks are typically retrieved from a storage device and stored in memory (i.e., buffer cache) in the storage system, where each read-ahead data block is associated with a unique block number.

Read-ahead techniques are known to “prefetch” a predetermined number of data blocks that logically extend the read stream. For instance, when a client's read request retrieves a sequence of data blocks assigned to consecutively numbered block numbers, a read-ahead operation may be invoked to retrieve additional data blocks assigned to block numbers that further extend the sequence, even though these additional read-ahead blocks have not yet been requested by the client. Typically, the read-ahead operations are “triggered” when a read stream is detected to have done multiple sequential read operations. For example, suppose a read stream read block number1,2,3, and4in one read operation, and then, sometime later, reads blocks5,6,7, and8. A read-ahead engine might predict that the next read operation will be for blocks9,10,11, and12, instructing the storage system to retrieve blocks5through12.

While known read-ahead techniques work well in certain situations, they occasionally suffer from disadvantages. For example, some of read-ahead algorithms assume that the read stream length will be short, at least until proven otherwise. This causes the algorithms to undershoot, that is, to behave as if the stream is smaller than it actually is and does not predict data that could be profitably read. Also, known algorithms may request large amounts of data on the assumption that the read requests will always be sequential. This causes the algorithms to overshoot, i.e., to predict that the stream will be larger than it actually is, thereby causing the system to read a relatively large fixed number of read-ahead data blocks. The overshooting, in turn, consumes an excessive amount of buffer memory in the storage system. The resulting excessive memory usage, or “cache pollution,” may cause the storage system to consume memory and resources that are needed for other system operations, and consequently may negatively impact the system's performance. For example, such cache pollution may increase the latency of data retrieval from the buffer memory since the storage system has to search a large number of “in-core” buffers containing read-ahead data. Furthermore, the risk of prefetching too much data may cause other data, which is more valuable than the prefetched data, to be evicted from the cache.

Accordingly, what is needed is a technique for optimizing prefetching of read-ahead data blocks in the storage system.

SUMMARY OF THE INVENTION

Embodiments described herein provide a system, method, and computer program product for optimizing the amount of data that need to be speculatively read ahead in a storage system in order to efficiently serve future client requests. The novel optimized technique studies past behavior of client read requests directed to a storage system (or subsystem) and uses the past behavior to predict the system's performance with respect to the future read requests. Throughout this description, the term “prediction” is used in its colloquial sense of “declaring in advance” or “making an inference regarding a future event based on probability theory.” A “read stream” as used herein is an incoming read request to a storage device that requests sequential data blocks.

The inventive technique uses the past behavior of the multiple read streams to determine expected size of a selected read stream. According to one aspect of the invention, the storage system monitors client read requests in order to form prediction of what data a client will request next. To this end, the inventive technique collects the size of read sequences for various read streams into a read streams data structure, such as a histogram, which summarizes past behavior of the read streams. Histogram entries reflect the count of read streams having a certain size or that fall within a range of size. The size of each existing read stream is reflected in an entry of the histogram. As a new read request arrives for an existing stream, the size of the stream is updated in the read streams data structure (such as a histogram). The read streams data structure is then used to select a read stream based on various factors. The inventive techniques use the read streams data structure to compute expected size of the selected read stream and to speculatively read ahead a number of data blocks which represent difference between the expected size and the given size of the selected read stream.

According to another embodiment, the inventive techniques use the computed read streams data structure to determine probability if the selected read stream reaches expected size (which, for example, was computed using a known technique). The probabilities are compared to a predetermined threshold to decide whether the expected size should be used as an indication of how many data blocks the storage system should read ahead into its memory. The assessed probability allows the system to make a better prediction with respect to a size of a read ahead operation, thereby reducing the undesirable impact of reading ahead by the storage system too many or too few data blocks.

The storage system executes a number of engines to implement inventive techniques described herein. For example, a read stream monitoring engine is adapted to monitor read requests received by the storage system and to generate a read streams data structure reflecting past behavior of the read streams. A read-ahead length computing engine is configured to determine a read-ahead size of a read stream. A probability computing engine is responsible for computing probability that a selected read stream achieves a given length. The read-ahead engine is configured to speculatively read data into memory.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

Storage System

FIG. 1is a schematic block diagram of the multiprotocol storage system100configured to provide storage service relating to the organization of information on storage devices, such as disks160. The storage system includes a storage operating system that logically organizes the information as a set of data blocks stored on the disks. The storage system supports both file-based requests to access data and block-based requests.

The storage devices may be arranged in various configurations, such as a redundant array of independent disks (RAID). The storage system100comprises a processor110, a memory150, a plurality of network adapters120,140and a storage adapter130interconnected by a system bus115. Those skilled in the art would understand that although in one implementation data can be stored on disks, other random access storage devices, such as flash, CD, or DVD drives can be used for storing data.

In the illustrative embodiment, the memory150comprises storage locations that are addressable by the processor110and adapters120,140for storing software program code and data structures associated with the present invention. Portions of the memory may be organized as an inode “pool”154containing one or more inode data structures and a read set pool152containing read set data structures. Another portion of the memory may be further organized as a buffer cache156containing data buffers1200. The processor and adapters may comprise processing elements and/or logic circuitry configured to execute the software code and manipulate the data structures stored in the memory150. A storage operating system200, portions of which are typically resident in memory and executed by the processing elements, functionally organizes the storage system by, inter alia, invoking storage operations in support of the storage service implemented by the system. It will be apparent to those skilled in the art that other processing and memory means, including various computer readable media, may be used for storing and executing program instructions pertaining to the inventive system and method described herein. The storage operating system can be implemented as a microkernel, like the Data ONTAP™ operating system available from NetApp, Inc., Sunnyvale, Calif. The storage operating system can also be implemented as an application program operating over a general-purpose operating system, such as UNIX® or Windows NT®, or as a general-purpose operating system with configurable functionality, which is configured for storage applications as described herein. It is expressly contemplated that any appropriate storage operating system may be enhanced for use in accordance with the inventive principles described herein.

To facilitate access to the storage devices160, the storage operating system200implements a write-anywhere file system that cooperates with virtualization modules to “virtualize” the storage space provided by disks160. The file system logically organizes the information as a hierarchical structure of named directories and files on the disks. Each “on-disk” file may be implemented as set of disk blocks configured to store information, such as data, whereas the directory may be implemented as a specially formatted file in which names and links to other files and directories are stored. The virtualization modules allow the file system to further logically organize information as a hierarchical structure of blocks on the disks that are exported as named logical unit numbers (LUNs).

The storage adapter130interacts with the storage operating system200executing on the storage system to access data requested by the clients190a,b. The data may be stored on the storage devices160The storage adapter includes input/output (I/O) interface circuitry that couples to the storage devices over an I/O interconnect arrangement, such as a conventional Fibre Channel (FC) serial link topology. The data are retrieved by the storage adapter and, if necessary, processed by the processor110(or the adapter130itself) prior to being forwarded over the system bus115to the network adapters120,140, where the information is formatted into packets or messages and returned to the clients.

The network adapter120couples the storage system100to a plurality of clients190a,bover, e.g., point-to-point links, wide area networks (WANs), virtual private networks (VPNs) implemented over a public network (e.g., the Internet) or shared local area networks (LANs), such as the illustrative Ethernet network175. The clients190may be general-purpose computers configured to execute applications over a variety of operating systems, including the UNIX® and Microsoft® Windows™ operating systems. Client systems generally utilize file-based access protocols when accessing information (in the form of files and directories) over a NAS-based network. Therefore, each client190may request the services of the storage system100by issuing file access protocol messages (in the form of packets) to the system over the network175. For example, client190aexecuting the Windows operating system may communicate with the storage system100using the Common Internet File System (CIFS) protocol over TCP/IP. On the other hand, a client190brunning the UNIX operating system may communicate with the multiprotocol system using either the Network File System (NFS) protocol over TCP/IP or the Direct Access File System (DAFS) protocol over a virtual interface (VI) transport in accordance with a remote direct memory access (RDMA) protocol over TCP/IP. It will be apparent to those skilled in the art that clients running other types of operating systems may also communicate with the integrated multiprotocol storage system using other file access protocols.

The storage network “target” adapter140couples the multiprotocol storage system100to clients190that may be configured to access the stored information as blocks, disks or logical units.

Storage Operating System

FIG. 2is a schematic block diagram of an exemplary storage operating system200that may be advantageously used with the present invention. The storage operating system comprises a series of software layers organized to form an integrated network protocol stack or, more generally, a multiprotocol engine222that provides data paths for clients to access information stored on the multiprotocol storage system100using block and file access protocols.

In addition, the storage operating system200includes a RAID subsystem280that may implement a storage protocol, such as a RAID protocol, as well as a driver subsystem250for retrieving data blocks from the storage devices160.

Bridging the subsystems280and250with the multiprotocol engine222is a virtualization system that is implemented by file system260interacting with virtualization modules illustratively embodied as, e.g., virtual disk (“vdisk”) module270. The vdisk module270is layered on the file system260to enable access by administrative interfaces, such as a user interface (UI)275, in response to a user, such as a system administrator issuing commands to the storage system. The UI275is disposed over the storage operating system in a manner that enables administrative or user access to various layers and subsystems, such as the RAID subsystem280.

The file system260is illustratively a message-based system that provides volume management capabilities used to access data stored on the storage devices, such as the storage devices160. The illustrative file system260uses index nodes (“inodes”) to identify data containers and store data container attributes (such as creation time, access permissions, size, and block location).

File system260further comprises the following components configured to implement novel techniques described herein. These components are include read streams monitoring engine210, read-ahead length computing engine220, probability computing engine230, and read-ahead engine240.

Engine210is configured to monitor read streams received by the storage system and to populate a read streams data structure, such as a histogram, with the entries that reflect behavior of the read streams. An entry in a histogram reflects the count of read streams that have a certain size or fall within a certain size range. Populating the read streams data structure with entries is described in greater detail in reference toFIGS. 5a-5e. The read streams data structure can be implemented as a table, a histogram, or any other structure for holding data. In the illustrated embodiment the data structure storing information about read streams is implemented as a histogram.

In one implementation, engine220is configured to determine the expected length of a specific read stream using the histogram populated by engine210.

Engine230is configured to determine probability that a specific read stream achieves the expected size (which might have been determined using known techniques). To this end, engine230examines histogram values and determines probability that a selected read stream reaches the expected size.

Engine240, in turn, is configured to read, into the memory, read ahead data blocks. The address of the read ahead data blocks can be provided by engine220.

At this point, it is useful to provide a brief description of organization of file system260, such as a buffer tree, an inode and associated read sets, and a read set data structure. These data structures are later used to describe inventive techniques of determining a length of a read ahead operation.

FIG. 3is a schematic block diagram of a buffer tree of data container330. The buffer tree is an internal representation of blocks of the data container stored in memory. The buffer tree comprises a top-level inode300that contains metadata describing the data container330, and also contains pointers referencing the data blocks320, e.g., 4 kB data blocks, which store the actual data of the data container. In particular, for a large data container (e.g., greater than 64 kB of data), each pointer in the inode300may reference an indirect (level 1) block310that contains up to 1024 pointers, each of which can reference a data block320. By way of example, each pointer in the indirect blocks310may store a value identifying a volume block number (vbn) that corresponds to a data block320in the file system260. Operationally, the file system260receives a client request, which has been processed by various software layers of the multi-protocol engine222. For example, a client request received at a network adapter120or140may be processed by a network driver. The client request is then formatted as a file-system “message” that can be passed to the file system260. The message may specify, among other things, a client-requested data container or directory (e.g., typically represented by an inode number), a starting offset within the requested data container or directory, and a length of data to write or retrieve following the starting offset. The file system extracts this information from the message and determines whether the data blocks requested by the client are accessible in one or more of the “in-core” buffers. If the requested data blocks are resident in the buffers, the file system retrieves the requested data blocks from memory150and processes the retrieved data. However, if the requested data are not resident in the in-core memory150, the file system260generates operations to retrieve the requested data from the storage devices160and places the data in memory. The file system passes a message structure identifying the vbn numbers assigned to the client-requested data blocks to the RAID subsystem280, which maps the vbns to corresponding disk block numbers (dbn). The file system then sends the latter to an appropriate driver (e.g., SCSI) of the driver subsystem250. The driver subsystem accesses the requested dbns from the storage devices160and loads the requested data block(s) in memory150for processing by the file system260.

As will be described in greater detail in reference toFIG. 6, in addition to retrieving data blocks containing the client-requested data, the file system260may also instruct subsystems280and250to retrieve additional “read-ahead” data blocks from the storage device160. These read-ahead data blocks may correspond to a range of data blocks (e.g., fbns) that further extend the sequence of the data blocks, even though the read-ahead blocks have not yet been requested by the client.

Similarly to the client-requested data blocks, the read-ahead data blocks can be retrieved by e.g., subsystems280and250and copied into memory buffers (e.g., memory buffers1200shown inFIG. 1) accessible to the file system260. Such memory buffers may be obtained from the buffer cache156. The file system may access (through a read or write operation) the client-requested data in the retrieved data blocks in accordance with the client's request, and, when appropriate, return the requested data and/or an acknowledgement message back to the requesting client190.

Read Sets

In accordance with the known technique, which was described in a commonly-owned patent application Ser. No. 10/721,596, entitled ADAPTIVE FILE READ-AHEAD TECHNIQUE FOR MULTIPLE READ STREAMS, by Robert L. Fair, the teachings of which are expressly incorporated herein by reference, the storage operating system200maintains a separate set of read-ahead metadata for each of a plurality of concurrently managed read streams. In one implementation, the operating system also stores metadata for each read stream in a separate “read set” data structure such that one read set stores metadata for one read stream. A data container or directory supporting multiple read streams may be associated with a plurality of different read sets. The description of read sets is provided below for background purposes.

FIG. 4Aillustrates an exemplary inode400and its associated set of read sets420a-c. The inode400comprises, inter alia, an inode number (or other identifier)402, a read set pointer404, a read-access style406, a default read-ahead value408, file metadata410and a data section412. The inode400may be dynamically allocated or obtained from the inode pool154in response to the storage operating system200receiving a client request to access data in the inode. The inode number402, e.g., which equals 17 in this example, may be used to uniquely identify the file or directory associated with the inode400. For instance, the client request may specify an inode number whose associated file or directory contains a particular range of data that the client desires to access. The client-specified inode number may be coupled with an indication of a starting offset in the file and a length of data to access beginning at the starting offset.

The read set pointer404stores a value that indicates the memory location of read sets420a-c. In operation, the file system260may dynamically allocate the read sets or acquire previously allocated read sets from a read set pool152. Each read set allocated for the inode400may be initialized to store a predetermined set of values. Illustratively, the read sets420a-cassociated with the inode400are arranged as a linked list, wherein each read set comprises a “next” pointer602that stores a value indicating the memory location of a next read set in the list. The next pointer in the list' last read set, e.g., read set420c, may store a predetermined “null” value to indicate that it is at the end of the list. While read sets in the illustrative embodiment are arranged as a linked list, those skilled in the art will appreciate that the read sets may be arranged in other configurations, such as a search tree.

The read-access style406stores a value indicating a read-access pattern that describes the manner by which data is read from the file or directory associated with the inode400. For instance, the read-access style may indicate that data in the inode's file or directory will be read according to, e.g., a normal, sequential or random access pattern. The storage operating system200may dynamically identify and update the read-access pattern value406as it processes client read requests. The default read-ahead value408indicates a predetermined number of data blocks that may be prefetched (i.e., read in advance) in anticipation of future client read requests for data stored in the inode400's associated file or directory.

The metadata field410stores other metadata information related to the data container or directory associated with the inode400. Such metadata information may include, inter alia, security credentials, such as user identifiers and group identifiers, access control lists, flags, pointers to other data structures, and so forth. The inode400also includes a data section412including a set of pointers that (directly or indirectly) reference the memory locations of the data blocks320containing the inode's associated file or directory. In this example, the pointers in the data section412reference one or more indirect blocks (not shown), which in turn contain pointers that reference the memory locations of a set of contiguous data blocks containing the file or directory. Hereinafter, it is assumed that each of the data blocks accessible from the inode400is assigned a corresponding fbn and the data container (or directory) associated with the inode400comprises a set of data blocks which are assigned consecutive fbn values. Advantageously, multiple read streams may be concurrently established among the data blocks320containing the inode400's file or directory. As shown, for example, two concurrent read streams430and435are identified in the set of data blocks9through18. The read stream430corresponds to a logically contiguous sequence of fbns retrieved by the file system260up to, but not including, the file block number9. Similarly, the read stream435corresponds to a logically contiguous sequence of fbns retrieved up to, but not including, the file block number15. In accordance with the illustrative embodiment, each of these read streams may be associated with a respective set of read-ahead metadata stored in a different one of the read sets420a-c.

As noted, each read set is configured to store metadata associated with a corresponding read stream. Therefore, because the illustrative inode400is associated with three read sets420a-c, the inode's associated file or directory can support up to three different read streams. However, it is expressly contemplated that the inode may be associated with an arbitrary number of read sets420.

FIG. 4Billustrates an exemplary read set420which may be accessed via the read set pointer902. The description of the read sets is provided in part in order to explain where start and end address of a read stream are maintained. Those skilled in the art would understand that the start and end address of a read stream can be maintained in any other structure. The read set contains metadata associated with a corresponding read stream. The read set420may comprise, inter alia, a next pointer902, a level value904, a count value906, a last read offset value908, a last read size910, a next read-ahead value912, a read-ahead size914and various flags916. Those skilled in the art will understand that the read set420also may be configured to store other information. The next read-ahead value912stores an indication of a predefined data container offset or memory address where the file system260will perform its next set of read-ahead operations for the read stream associated with the read set920. The read-ahead size value914stores the number of read-ahead data blocks that are prefetched. Having retrieved the read-ahead data blocks, the file system260may update the next read-ahead value912to indicate the next file offset or memory address where read-ahead operations will be performed for the read stream. After the read-ahead data blocks are retrieved, they are copied into in-core memory buffers in the memory150and the file system finishes processing the client read request. Last Read Offset908stores the last offset for the I/O. Thus, suppose a read stream reads block number1,2,3, and4in one read operation, and then some time later, it reads blocks5,6,7, and8, then the last offset for I/O is block8. Each read set420may optionally include one or more flag values914that enable the file system260to specialize read-ahead operations for the read set associated read stream. For instance, one of the flag values may indicate in which “direction” the file system should speculatively retrieve data blocks for the read stream. That is, the file system may be configured to retrieve data blocks in a logical “forward” direction (i.e., in order of increasing data block numbers) or in a logical “backward” direction (i.e., in order of decreasing data block numbers). Other flag values914may indicate whether the read-ahead data blocks contain “read-once” data and therefore should not be stored in the memory150for a prolonged period of time.

Read Stream Monitoring and Determining Expected Read-Ahead Length

Embodiments described herein provide novel techniques for optimizing the amount of data that need to be read ahead in a storage system in order to serve future client requests. The novel optimized technique monitors behavior of client read requests to a storage system and uses the previous read requests to predict the system's performance with respect to the future read requests. The novel technique uses a data structure, such as a histogram, to maintain information about read streams. The novel technique also employs probabilistic analysis to determine whether a selected read stream will achieve the expected size, which might have been computed using known techniques. This analysis is based on the monitored behavior of the previous read requests.

Referring now toFIG. 6, a flowchart summarizing a sequence of steps to determine expected read-ahead length of a selected stream is illustrated. Initially, at step610, engine210monitors the received I/Os and populates a histogram195illustrated inFIGS. 5a-5e). When storage system100is first booted, the data structure does not have any entries. This indicates that there are no read streams yet.

As a new read request arrives, engine210examines the existing read sets (such as the ones illustrated inFIGS. 4A and 4B) to determine if the new read operation is related to any previous read operation that has taken place (step620). In one implementation, to this end, engine210examines the starting location of the read operation and compares it to the ending location of each read stream as it is recorded in its read set (as shown inFIG. 4B) If the starting address (location) of the new read request is within a close proximity to the value stored in the Last Read Offset field (as shown inFIG. 4B, as Last Read Offset908), engine210determines that the current read operation is part of the existing read steam. The end block address is the sum of the value in the Last Read Offset908and the value in the Last Read Size910(shown inFIG. 4B). The close proximity can be defined, for example, as being within one to five data blocks from the location where the previous read stream ended. Those skilled in the art would appreciate though that the close proximity may be defined by other parameters.

If the determination is positive in step620, size N of any previous I/O is determined (step630). Size N is equal to the difference between the end block address of the previous I/O and the start block address of the previous I/O less one. Engine210decrements by one a histogram value representing the count of I/Os having length N (step640) since the new I/O is part of the existing I/O (as determined by the close proximity of the end/start address).

Since the two I/Os are combined, at step650, the start address and end address of the new I/O is updated to reflect the start or end address of the previous I/O. Upon updating the start/end address of the new I/O, the N1 length of the new I/O is recomputed (step660) to represent a difference between the updated end address and updated start address incremented by one. Now the histogram count for the recomputed N length can be increased by one (an example illustrating population of the histogram is described below in reference toFIGS. 5a-5e).

If the determination in step620earlier is negative (which essentially means that the new I/O is not within close proximity of any existing I/O and thus is not part of the existing I/O), a new read set for the new I/O is created (such as indicated inFIG. 4A) and stored in memory (step615). Then, length N is computed as equal to the difference between the end address of the new I/O and start address of the new I/O incremented by one (step625). The histogram value for the computed N size is incremented by one (step670).

To illustrate the above steps, the following example is chosen. Suppose that a client accesses storage system100to read two blocks of data and that the location it reads from is block number47within a LUN. The storage system identifies an available read set data structure (read set) from the pool of read sets and populates the histogram to indicate that there is now one read stream that has read two blocks (seeFIG. 5a).

The next read to occur might be by the same client or by a different client, which reads five blocks from a different location, say, from block192. The storage system examines the existing read set(s) to determine if the new read operation is related to any previous read operations that have taken place. To this end, the read stream monitoring engine compares the new read stream at block192and the existing read streams which read blocks47and48. Since block numbers47and48are not within close proximity to block192, these two read streams are not related. As shown inFIG. 5b, data structure195bis updated to indicate that there are two read streams that have been received—one has read two blocks and the other has read five blocks.

Suppose that another client read operation arrives. This operation reads four blocks starting at location49. Engine210examines the starting location of the read operation and compares it against the ending location of each read stream as it is recorded in its respective read set. Block49is next to where the first read stream ended (block48). The read stream monitoring engine210determines that the current read operation is part of the first stream. The read stream monitoring engine210updates the histogram195cby decrementing the old entry for this stream. Engine210also updates the stream length to 2+4=6 blocks, as shown inFIG. 5c. The histogram195cnow reflects that one read stream has read a total of six blocks and a second read stream has read a total of five blocks.

The next client read operation reads a single block from block197. The read stream monitoring engine210determines if this read operation is related to any of the previously monitored read streams. Engine210determines that this read operation is related to the second read stream since block197is within close proximity to the previously read block192. Thus, it is part of the same read stream. The new size of this read stream is determined to be 5+1=6. Now the two streams have the same size, 6 data blocks. Because the read operations take place at different locations, they are maintained as separate read streams, but they are merged in the histogram195dbecause they are now of the same size (seeFIG. 5d).

As more read requests arrive, some related to existing streams and some not, the histogram gradually builds up a history of behavior of read streams. At some point, there could be 15 total streams represented by 15 separate read sets, as shown inFIG. 5e. The inventive technique assumes that the behavior of the clients issuing I/Os with respect to the existing read streams is indicative of the client behavior in the near future. Therefore, the statistics collected in the histogram can be used to make better decisions as to how much data should be read ahead by the storage system, as will be described in connection with a flow diagram illustrated inFIG. 7.

FIG. 7is a flow diagram illustrating steps to determine expected size of a selected read stream using the computed histogram. The expected size of the selected read stream will be used to determine the read-ahead size of the selected read stream. The read-ahead size of the read stream is the expected size of the read stream less the actual size of the read stream. The actual length of the read stream reflects a number of sequential data blocks that has been read by the I/O.

In one implementation, the expected size of the read stream is determined as a weighted average. At step710, for each bucket in the histogram, where the bucket represents a count of read streams having a particular size N, engine220generates a product of a count of read streams having a size N and a size of the read stream. Then engine220accumulates the products. For example, inFIG. 5e, five streams have each read 10 blocks, two streams have each read 15 blocks and 8 streams have each read 20 blocks. The accumulated product is generated as follows: (5×10+2×15+8×20)=240.

At step720, engine220determines expected size of a selected read stream. The selected read stream can be chosen based on various characteristics. For example, the I/O can be selected because it is the most recently used. The expected size of the selected I/O, as determined by engine220, is the result of the product of the sum computed in step720and an inversion factor of a count of read streams having the same size as the selected read stream or greater. The resultant number is the expected size of the selected I/O. Those skilled in the art would understand that the read streams having the same size as the selected read stream or greater can be selected based on other criteria. For example, reads streams from the same volume (or other storage container) having sizes equal to or greater than the selected read stream can be chosen. As a result, multiple histograms will be built to monitor read requests rather than having one histogram for the system.

Consider the following example. The selected read stream has a size of 10 data blocks. Referring to the example shown inFIG. 5e, the total number of read streams having the size equal to or greater than 10 is 15. Continuing with the same example, the expected size of the selected read stream is 240/15=16. Thus, the expected size of the selected read stream having size 10 is 16. In other embodiments, the expected size of the selected read stream can be determined by using the next highest populated field in the histogram. For example, inFIG. 5e, if the system has already read 11 blocks, then based on the histogram values shown inFIG. 5e, the next highest populated value is 15 (reflecting that 2 read streams have read 15 data blocks).

At step730, if the expected size of the read stream is greater than the actual size of the selected read stream, engine220determines read ahead size as a difference between the expected size and the actual size of the read stream. For example, if the expected size is 16, engine220determines the read ahead size of the read stream as the difference between 16 and 10 data blocks, which is 6.

At step740, read-ahead engine240speculatively reads the read-ahead size of the stream, which is the difference between the expected length and the actual length N of the I/O. In one implementation, read-ahead engine240retrieves read ahead data blocks from the storage device and stores them in memory, such as buffer cache154(shown inFIG. 1). The read-ahead blocks preferably logically extend the read stream. Furthermore, the read set data structure (shown inFIG. 4A) corresponding to the read stream is updated to reflect a number of speculatively read data blocks.

According to another embodiment (as illustrated in a flow diagram inFIG. 8), the computed histogram values can be used to correct the results of the existing read-ahead algorithms. For example, a known algorithm was used to compute a read-ahead size of a selected read stream. One such algorithm is described in the U.S. Pat. No. 7,631,148 assigned to NetApp, Inc., entitled ADAPTIVE FILE READ-AHEAD TECHNIQUE FOR MULTIPLE READ STREAMS, by Robert L. Fair, the teachings of which are expressly incorporated herein by reference. However, the method described in U.S. Pat. No. 7,631,148 can potentially overshoot or undershoot (which essentially means that too many or too few data blocks are read into memory in anticipation of the client read request).

Thus, according to the novel embodiment described herein, the data collected in the histogram can be used to improve predictions of the existing read-ahead methods. To determine if the computed read ahead size N will result in undershooting, the probability p1that the selected stream would ultimately read N or fewer additional blocks is determined by the probability computing engine230. If p1is below a given threshold (provided by a system administrator, for example, and stored in the storage system memory), it is likely the storage system will read too few blocks. To determine if the computed read-ahead length N will result in overshooting, the probability p2that the selected stream would ultimately read N or more blocks is determined. If p2is below a given threshold, it is likely that the storage system will read too many blocks.

Engine230uses the computed histogram and the expected size of a selected read stream to determine probability if the selected read stream will be greater or less than its expected size prior to being abandoned (step810). Abandoning a read stream means reusing the same read set for a new read stream so that the abandoned read stream is not used for purposes of statistical analysis. To determine probability of a condition (such a condition can be that a read stream is greater than a certain size, for example), engine230determines a product of the count of the number of read streams that meet the condition (being greater in size than a certain value) and an inverse factor of the total population of read streams.

To determine the total number of read streams, probability computing engine230goes through the entries in the histogram shown inFIGS. 5a-5cand adds the count of read streams of each size. As shown inFIG. 5e, the total population of read streams is 15. The number of read streams smaller than size 10 is zero; so the probability that a stream will be smaller than 10 is also zero. Thus, engine230uses histogram195to determine the number of streams that meet the condition and multiplies it by the inverse factor of the total number of streams. To determine the total number of streams, engine230iterates through the entire histogram and adds up the count of streams of each size. To find the count of streams below or above a certain size, engine230starts at that size and counts the number of streams below it or it starts at the beginning and counts up to that size. The probability that a stream is of a certain size is a result of the product of the count of streams of that size and an inverse factor of the total population of the read streams.

Now consider the following example. If a specific stream has already read 15 blocks and another technique determined that a read-ahead size should be six more data blocks, it results in the expected size of 21 of the read stream. The probability that the storage system overshoots at 21 blocks is 100% because none of the read streams have achieved this length. In contrast, the probability that the storage system undershoots at 21 blocks is zero.

Considering another example, if the selected stream has already read 15 blocks and a read-ahead size is determined to be 2 blocks, the expected length of the read stream is 17. The probability that the storage system overshoots or undershoots at 17 is determined as follows. The total number of streams of length 15 or greater is ten. The number of streams that have read more than 17 blocks is eight; so the probability that storage system undershoots at 17 is 8/10=80%. The number of streams that have read at least 15 data blocks but less than 17 data blocks is two, so the probability that the storage system overshoots at 17 is 2/10=20%.

At step820, engine230compares the computed probability to a threshold value T1(such as a value stored in the memory of the storage system and selected by a user administrator of the storage system). If the computed probability that the selected read stream size will ultimately be less than the expected length exceeds a threshold value T1, it is likely that the storage system will read too many blocks than the client might request. Thus, to correct this problem, the expected length is decreased downwards (step830). In one implementation, the size of the expected length, for example, can be divided by a factor selected by a system administrator and provided to the storage system. This process can be performed iteratively until the threshold T1is not exceeded. If the probability that the read stream size will ultimately be greater than the expected length exceeds the threshold T2(step840), it is likely that the storage system will read too few blocks and thus undershoots. To correct this problem, the given length is increased upwards (step850). The size of the expected length can be, for example, multiplied by a factor. Those skilled in the art should understand that in one embodiment T1and T2values in steps820and840could be the same. While in other implementations, T1and T2can be different.

Thus, using the past behavior of client read requests and computing the probabilities that a specific read stream will achieve a certain expected size allows the storage system to make a better prediction with respect to a size of a read ahead operation. This, in turn, reduces the undesirable implications of reading ahead by the storage system too many or too few data blocks.

If neither threshold T1or T2is exceeded, then the expected length is used for speculatively reading the data blocks (step860).

It should be noted that the threshold T1and T2can be adjusted based on various factors, such as the buffer cache size, the workload of the storage system and the prior use of read-ahead data. From the standpoint of the buffer cache size, the risk of reading too much data is taking up extra space by the buffer cache. Using that extra space might cause other data to be evicted from the buffer cache. That “other data” might be more valuable to the clients than the data prefetched by the clients but never required by a client. If the buffer cache size were to change dynamically though (e.g., growing and shrinking in response to competing demands for memory while the storage system is running), then the storage system has more flexibility to use more buffer cache space even if the probability of using prefetched data is lower. Thus, in situations when the buffer cache size can change dynamically, the threshold T1and T2can be changed to a lower number.

Similarly, read-ahead engine240may analyze the usage by prior use of the previously read-ahead data. If in the past 90% of the read-ahead data were not used by clients, the threshold could be moved upwards to have more certainty that the read-ahead data will be used prior to increasing the expected size. Read-ahead engine240then speculatively reads the read-ahead length of the stream, which is the difference between the expected length and the current length of the specific read stream.

The techniques introduced above can be implemented by programmable circuitry that is configured by software and/or firmware, or entirely by special-purpose circuitry, or by a combination of such forms. Such special-purpose circuitry (if any) can be in the form of, for example, one or more application-specific integrated circuits (ASICs), programmable logic devices (PLDs), field-programmable gate arrays (FPGAs), etc. Software or firmware to implement the techniques introduced here may be stored on a machine-readable storage medium and may be executed by one or more general-purpose or special-purpose programmable microprocessors. A “machine-readable medium”, as the term is used herein, includes any mechanism that can store information in a form accessible by a machine (a machine may be, for example, a computer, network device, cellular phone, personal digital assistant (PDA), manufacturing tool, any device with one or more processors, etc.). For example, a machine-accessible medium includes recordable/non-recordable media (e.g., read-only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; etc.), etc.

References in this specification to “an embodiment”, “one embodiment”, or the like, mean that the particular feature, structure or characteristic being described is included in at least one embodiment of the present invention. Occurrences of such phrases in this specification do not necessarily all refer to the same embodiment. On the other hand, different embodiments may not be mutually exclusive either.