Altering prefetch depth based on ready data

A system comprises a controller and a buffer accessible to the controller. The controller is configured to prefetch data from a storage medium in advance of such prefetch data being requested by a host device, some of such prefetch data being retrieved from the storage medium and stored in the buffer ready for access by the host device (“ready data”) and a remainder of such prefetch data in process of being retrieved from the storage medium but not yet stored in the buffer (“not ready data”). The controller alters a depth of the prefetch data based on a ratio of the ready data to a combined total of the ready data and not ready data.

BACKGROUND

In storage devices such as disk drives and disk arrays, the primary media on which the data resides is slow compared to the “consumers” or clients of the storage devices, such as servers or personal computers. That is, a computer often is able to request and receive data at a faster rate than a disk drive is able to provide the requested data. The storage subsystem can anticipate a consumer's need for data by prefetching such data, that is, retrieving the data from the storage medium before the consumer has actually requested the data. Prefetching data, however, can be wasteful of system resources. For example, prefetching data into a cache buffer can be wasteful of the capacity of the cache buffer if more data than is needed is prefetched.

NOTATION AND NOMENCLATURE

A system may refer to a collection of computers or computer-related devices (e.g., storage device), a subsystem within a computer, etc.

DETAILED DESCRIPTION

FIG. 1illustrates a system10comprising one or more host devices12coupled to a storage system16via a communication link14. Each host device12comprises a computer (e.g., personal computer, server, etc.) in accordance with some embodiments. In general, each host device12is any type of electronic device that has a need to access data stored on the storage system16. The communication link14may comprise a local area network (LAN), wide area network (WAN), wireless and/or wired networks, etc. In some embodiments, the storage system16may connect directly to one or more of the host devices12.

In some embodiments, the storage system16is external to a host device12, while in other embodiments, the storage system16is part of the host device. In the embodiment shown inFIG. 1, the storage system16comprises a processor18coupled to storage20and to a controller22. The controller22couples to one or more storage media24. In accordance with some embodiments, storage20comprises volatile storage (e.g., random access memory) while the storage media24comprises non-volatile storage such as disk drives, tape drives, and the like. In some embodiments, the storage media24are configured as a Redundant Array of Independent Disks (RAID) controlled by controller22(functioning as a RAID controller in this configuration). The storage20of the storage system16comprises firmware26executable by processor18and/or controller22, a cache buffer28, a lower threshold (LT)25, and an upper threshold (UT)27.

FIG. 2shows an illustrative embodiment of the controller22. As shown, the controller22comprises control logic15coupled to storage interface19(interface to storage20), storage21(e.g., volatile or non-volatile storage), a processor interface23, and a storage media interface17. The control logic15of the example ofFIG. 2comprises a processing core that may execute firmware29stored on the storage21to provide the controller22with the functionality described herein.

Referring again toFIG. 1, in general, a host device12issues one or more read or write requests to the storage system16for access to data contained on the storage media24. For read requests, the host device12is capable of receiving data from the storage media24at a faster rate than the storage media24is capable of delivering the requested data. Accordingly, the controller22prefetches data from the storage media24in advance and in anticipation of the host device12submitting a read request to the storage system for such data. Data prefetched by the controller22is stored by the controller22in the cache buffer28implemented in storage20.

Once the processor18of the storage system16receives a read request for data from a host device12, the processor18determines whether the requested data is already stored in the cache buffer28(i.e., has been prefetched). If the requested data is already stored in the cache buffer28, the processor18retrieves the requested data from the cache buffer and provides the data to the requesting host device12. If the data is already in the cache buffer28when the host12requests the data, the read request by the host device is referred to as a “hit.”

However, if the requested read data is not in the cache buffer28(i.e., has not been prefetched), the processor18asserts a signal or a message to the controller22to retrieve the requested data from the appropriate storage media24. Once retrieved from the storage media24, the data is provided to the requesting host device12. If the data is not in the cache buffer28when the data is requested by the host device12, the read request by the host device is referred to as a “miss.” A host read request resulting in a hit results in a faster reply back to the host with the requested data than for a miss because a hit only requires access to the cache buffer28and not, as in the case of a miss, access to the slower storage media24.

The terms “ready data,” “not ready data,” and “prefetch depth” will now be explained. When the controller22prefetches data, the controller22issues a read request to one or more of the storage media24. It takes a finite amount of time for the requested data to be retrieved from the storage media24and stored in the cache buffer28. The controller22may issue a series of read requests to the storage media24. Eventually, each data retrieved in reply to a specific read request is stored in the cache buffer28. Consequently, a series of multiple read requests may have been issued to the storage media24by the controller22, but none, some, or all of the requested data may have been actually stored in the cache buffer28.

Data that has been prefetched and currently resides in the cache buffer28awaiting retrieval in response to a host device request is called “ready data.” Data that is in the process of being prefetched from the storage media24and stored in the cache buffer28, but is not currently resident in the cache buffer, is called “not ready data.” Both of the ready data and the not ready data represent prefetch data. Ready data has been completely prefetched and not ready data is currently being prefetched. The combined amount of ready data and not ready data represents the “prefetch depth.” The prefetch depth thus represents the total amount of data the controller22is trying to prefetch ahead of read requests from the host12.

The controller22does not necessarily always prefetch data. In accordance with at least some embodiments, the controller22detects when a host12is reading the storage media24in a predictable fashion. In some embodiments, the controller22detects when a host12is reading through the storage media24in a contiguous (sequential) manner. For example, the controller22logs the addresses targeted by the read requests from a host. The log may be stored internal to the controller22or in storage20. Upon detecting, for example, a fourth consecutive address in a series of read requests (or other predetermined number of consecutive addresses), the controller22determines that the host12is reading the storage media24contiguously. In some embodiments, the each read by the host12comprises a read of a “block” of data. Each block of data comprises one or more bytes of data. For example, a block of data may include 128 megabytes (MB) of data. Thus, the host12reads 128 MB of data at a time. The controller22determines whether the host12is reading contiguous blocks of data.

Once that determination is made, the controller22begins prefetching data starting with the next contiguous block of data. In some embodiments, the processor18detects when a host device12is reading storage media24in a contiguous fashion and requests the controller22to begin prefetching data. The number of blocks of data to be prefetched ahead of the host's read requests comprises an amount of data to be prefetched and is the prefetch depth explained above. Upon initially beginning to prefetch data, the prefetch depth is set at an initial value. In some embodiments, the initial prefetch depth is set at 3 blocks of data. For the example in which each block includes 128 MB of data, the controller22prefetches 3×128 MB or 384 MB of data. The number of blocks to be prefetched generally depends on the size of each block, and both values (size of a block and initial number of blocks to prefetch (initial prefetch depth)) can be varied as desired.

In accordance with various embodiments, any time a change in the prefetch depth is made such as setting the depth at the initial prefetch depth from no prefetching at all (in essence a 0 prefetch depth), the storage system16is allowed to stabilize before determining whether to further change the prefetch depth. Otherwise, changes to the prefetch depth may be unstable. Instability may result from deciding to increase the prefetch depth before a prior increase of the depth is actually completed. It takes a finite amount of time to increase the prefetch depth. During that time, the storage system16may decide to again increase the prefetch depth because the host device12may attempt to read data from the storage media12faster than the storage media can supply the requested data.

In accordance with various embodiments, a determination is not made as to whether to further change the size of the prefetch depth until the last entry in the newly increased prefetch depth is requested by the host device12. In the example of initially starting to prefetch data and initially setting a prefetch depth of 3 blocks, the storage system16will not determine whether to further change the prefetch depth until the third block of data in the initial set of three prefetched blocks is requested by the host device12. If a prefetch depth is increased from 5 blocks to 6 blocks, the storage system16will not determine whether to further change the prefetch depth until the sixth block of data in the subsequent set of six prefetched blocks is requested by the host device12. Ceasing determining whether to further change the prefetch depth advantageously gives the storage system16some time to actually have the prefetch depth transition to its new target.

FIGS. 3a-3dprovide examples of prefetching data and how the controller22determines whether to change the size of the prefetch depth in accordance with various embodiments.FIG. 3aillustrates a contiguous set of blocks from storage media24. The blocks are designated as blocks30-40. Each block comprises one or more bytes of data (e.g., 128 MB) as desired for a block size. The arrows along the top of the representation represent read requests from a host device12. Upon the host device12issuing a read request for block34, the controller22determines that the host device has issued read requests for four contiguous blocks, blocks31-34. At that time, the controller22determines that the host device12is reading through the storage media24in a contiguous fashion and begins to prefetch data ahead of the requests from the host device. The arrows along the bottom represent prefetch read requests by controller22of a number of blocks ahead of where the host device12is currently reading (i.e., block34). That is, the host device12is currently reading block34and the controller22begins prefetching blocks35,36, and37. In this example, the initial prefetch depth is 3 blocks, but could be different in other embodiments as noted above.

Once the system stabilizes as explained above, the controller22determines whether to change the prefetch depth. If the controller22experiences a miss (i.e., the host device12requests data that has not yet been prefetched and stored in the cache buffer28as “ready data”), the controller22may automatically increase the prefetch depth. For example, the controller22may change the prefetch depth from 3 blocks to 4 blocks. The controller22waits for the system to stabilize before again determining whether to further change the prefetch depth. Changes (e.g., increases) to the prefetch depth may occur upon a miss event.

InFIG. 3b, the prefetch depth has increased to a depth of 5 blocks, for example, due to one or cache buffer misses. In this example, the host device12has most recently issued a read request for block81. The controller22in the storage system16has been prefetching data and had prefetched block81previously, as well as blocks80,79, and78before that (as indicated by the dashed arrows along the bottom of the blocks. Thus, when the host device12requests block81, that particular data is already stored in cache as ready data. The controller22in the example ofFIG. 3bis prefetching 5 blocks ahead of where the host device12is requesting, and thus is prefetching blocks82-86. As noted above, some data targeted by the prefetching process is already stored in cache buffer28and thus is “ready data,” while other data is still being prefetched and is not ready data (i.e., not yet stored in cache buffer28). InFIG. 2, the data of blocks82and83are ready (R) data (represented visually by cross-hatching for convenience) meaning such data has already been stored in cache buffer28. The data of blocks84,85, and86are not ready (NR) data.

As two of the five prefetch blocks inFIG. 3bcomprise ready data, the amount of ready data in the example ofFIG. 3brepresents ⅖, or 40%, of the prefetch depth. Algebraically, the percent ready data is calculated as R/(R+NR). In accordance with various embodiments, once the prefetch depth increases to a predetermined size of N (e.g., N=5 blocks), determining whether to alter the size of the prefetch depth changes from increasing based upon a miss to altering the depth based on a ratio of the ready (R) data to a combined total of ready and not ready (NR) data. Alternatively stated, the prefetch depth is calculated based on a ratio of the ready (R) data to the prefetch depth. The ratio may be computed as a fraction (e.g., ⅖) or as a percentage (e.g., 40%). The percent ready data is indicative of how much data has been prefetched relative to a total amount of data that has been and is being prefetched.

In the example ofFIG. 3c, the prefetch depth is still 5 blocks, but the amount of ready (R) data comprises three blocks of data (blocks82,83, and84). The amount of not ready (NR) data is the remaining two blocks85and86of the prefetch data. Thus, percent ready data is ⅗ (60%).

In the example ofFIG. 3d, the prefetch depth is still 5 blocks, but the amount of ready (R) data comprises only one block of data (block82). The amount of not ready (NR) data is the remaining four blocks83-86of the prefetch data. Thus, percent ready data is ⅕ (20%).

The percent ready data is computed by the controller22and then compared by the controller22to one or more threshold values. In accordance with various embodiments, a lower threshold (LT) and an upper threshold (UT) are provided against which to compare the computed percent ready data. In some embodiments, the lower threshold is 25% (or ¼) and the upper threshold is 50% (or ½). The LT and UT thresholds may be hard-coded into the controller's firmware or stored (and thus programmable) in storage20as shown inFIG. 1.

If the percent ready data exceeds the upper threshold (UT), then the controller22dynamically and automatically (i.e., without user involvement and during run-time) decreases the prefetch depth. That the percent ready value exceeds the upper threshold indicates that more data than necessary is being prefetched thereby possibly wasting system resources. Reducing the size of the prefetch depth will likely still provide an adequate prefetch depth but require fewer system resources (e.g., less cache buffer storage, less use of the controller22, etc.). In the example ofFIG. 3c, the percent ready is 60% which exceeds an illustrative upper threshold of 50%. As such, for the example ofFIG. 3c, the controller22would respond by reducing the prefetch depth from 5 blocks to a value less than 5 (e.g., 4).

If the percent ready data falls below the lower threshold (LT), then the controller22dynamically and automatically (i.e., without user involvement and during run-time) increases the prefetch depth. That the percent ready value drops below the lower threshold indicates that a miss condition may soon result in which the host device12requests data that is not already prefetched and in the cache buffer28. Increasing the size of the prefetch depth should reduce the risk of encountering a miss, and thus reduce the risk of the latency associated with a cache miss. In the example ofFIG. 3d, the percent ready is 20% which is below an illustrative lower threshold of 25%. As such, for the example ofFIG. 2d, the controller22would respond by increasing the prefetch depth from 5 blocks to a value greater than 5 (e.g., 6).

In accordance with various embodiments, each time the storage system16(and in particular the controller22) receives a read request from a host device12for which the controller22is prefetching data, the controller22computes the percent ready data and determines whether the prefetch depth should be increased or decreased. Changing (either increasing or decreasing) the prefetch depth may be performed in one block increments or multiples of one block increments. Further, the prefetch process is allowed to stabilize as explained above before the controller22again reassesses whether to alter the prefetch depth.

FIG. 4shows a method in accordance with various embodiments. At90, the controller22computes the percent ready data which is indicative of how much data has been prefetched relative to a total amount of data that has been and is being prefetched. At92, the controller alters the prefetch depth based on the computed percent ready data.

FIG. 5shows another method in accordance with various embodiments. The actions depicted inFIG. 5are performed by the controller22of the storage system16. The actions can be performed in the order shown or in a different order. Further, some of the actions can be performed at the same time (i.e., in parallel).

At block102, the method comprises the controller22detecting a contiguous access condition by a host device12. As explained above, this action can be performed by the controller detecting that a host device has attempted to read the Nth (e.g., 4th) block in a row in a contiguous fashion. The method continues to monitor for this condition until the controller22detects that the contiguous access condition has occurred. At that point, the controller22begins prefetching data from storage media24on behalf of the host device12, and in anticipation of the host device12requesting such data. At104, the controller22sets the initial prefetch depth and begins to prefetch the data.

At106, the controller22may detect a miss and as a result of the miss, increase the prefetch depth. The controller may continue to increase the prefetch depth upon detecting misses until a predetermined prefetch depth size is reached. At that point, the controller22changes from basing prefetch depth changes on misses to basing prefetch depth changes on a computation of the percent ready data. Actions108-120depict that part of the method ofFIG. 4devoted to basing prefetch depth changes on a computation of the percent ready data.

At108, the controller22receives a request (e.g., a read request) from a host device12. At110, the controller determines whether to alter the prefetch depth based on a computation of the percent ready data. That is, if the prefetch depth has recently been altered but has not stabilized, the controller22may skip the subsequent actions of computing the percent ready data and using that value to determine whether the prefetch depth should be altered.

At112, the controller computes the percent ready data and at114compares the percent ready data to the lower threshold. If the computed percent ready data is less than the lower threshold, then at116, the controller22increases the size of the prefetch depth and control loops back to action108in which another host device request is received. If the percent ready data is not below the lower threshold, then at118the controller22determines whether the percent ready data exceeds the upper threshold. If the percent ready is greater than the upper threshold, then at120, the controller22decreases the prefetch depth. If, at118, the percent ready is not greater than the upper threshold (i.e., the percent ready data is between the lower and upper thresholds), then control simply loops back to action108waiting for another request from the host device.