Abstract:
A method for providing efficient use of a read cache by a storage controller is provided. The method includes the storage controller receiving a read request from a host computer and determining if a host stream size is larger than a read cache size. The host stream size is a current cumulative size of all read requests in the host stream. If the host stream size is larger than the read cache size then migrating data to a first area of the read cache containing data that has been in the read cache for the longest time. If the host stream size is not larger than the read cache size then migrating data to a second area of the read cache containing data that has been in the read cache for the shortest time. The host stream is a consecutive group of sequential read requests from the host computer.

Description:
CROSS REFERENCE TO RELATED APPLICATION(S) 
       [0001]    This application claims the benefit of pending U.S. Provisional Application Ser. No. 61/772,691 (Docket No. DHP0108 PV) filed Mar. 5, 2013, entitled METHOD FOR HEURISTICALLY ABANDONING LRU TO PROMOTE READ AHEAD, which is hereby incorporated by reference for all purposes. 
     
    
     FIELD 
       [0002]    The present invention is directed to computer data storage. In particular, the present invention is directed to methods and apparatuses for efficient storage controller read data caching. 
       BACKGROUND 
       [0003]    The need to store digital files, documents, pictures, images and other data continues to increase rapidly. In connection with the electronic storage of data, systems incorporating one or more data storage controllers have been devised. Storage controllers receive data read and write requests from host computers and control one or more physical storage devices to beneficially store or provide the requested data from/to the host computers. 
         [0004]    Storage controllers generally buffer read and write data requests, often converting the host data read and write requests into RAID or storage device read or write requests. Many storage controllers store read and write data in cache memories included as part of the storage controllers. Cache memories are small compared to external storage devices such as hard drives, and generally orders of magnitude faster. However, cache memory costs significantly more per byte than storage devices, and therefore cache memory size is correspondingly small in order to be cost effective. The need is always present for cache memories to operate as efficiently as possible in order for overall storage controller performance to be maximized to all interconnected host computers. 
         [0005]    Many storage controllers have separate areas of memory dedicated to read cache and write cache. If requested data is in the read cache when a host computer requests the data that is a “cache hit”. If requested data is not in the read cache when a host computer requests the data that is a “cache miss”. Storage controllers execute caching policies to attempt to maximize the likelihood that requested data will be present in a read cache when the data is requested by a host computer. One of the most common such policies is LRU or “least recently used”. LRU policies maintain a log of which data has been present in the read cache for the longest time, and replace that oldest data with newer data that has either been requested by a host read request or in spatial proximity to previous host read requests. 
       SUMMARY 
       [0006]    The present invention is directed to solving disadvantages of the prior art. In accordance with embodiments of the present invention, a method for efficient use of a read cache by a storage controller is provided. The method includes receiving, by the storage controller, a read request from a host computer and determining, by the storage controller, if a host stream size is larger than a read cache size. The host stream size is a current cumulative size of all read requests in the host stream. If the host stream size is larger than the read cache size then migrating data corresponding to the read request, by the storage controller, to a first area of the read cache containing data that has been in the read cache for the longest time. If the host stream size is not larger than the read cache size then migrating data corresponding to the read request, by the storage controller to a second area of the read cache containing data that has been in the read cache for the shortest time. The host stream is a consecutive group of sequential read requests from the host computer, and the storage controller includes the read cache. 
         [0007]    In accordance with another embodiment of the present invention, a storage controller providing for efficient use of a read cache is provided. The storage controller includes a processor and a memory, coupled to the processor. The memory includes the read cache and metadata, which includes a host stream size. The host stream size is a current cumulative size of all read requests in a host stream, and the host stream is a consecutive group of sequential read requests from the host computer. The metadata also includes the read cache size. After the storage controller receives a read request from a host computer coupled to the storage controller, the processor determines if the host stream size is larger than the read cache size. If the host stream size is larger than the read cache size, the processor migrates data corresponding to the read request to an area of the read cache containing data that has been in the read cache for the longest time. If the host stream size is not larger than the read cache size the processor migrates data corresponding to the read request to an area of the read cache containing data that has been in the read cache for the shortest time. 
         [0008]    In accordance with yet another embodiment of the present invention, a storage system for providing for efficient use of a storage controller read cache is provided. The storage system includes a host computer for providing read requests, a storage controller coupled to the host computer, and one or more storage devices coupled to the storage controller. The storage controller includes a processor and a memory, coupled to the processor. The memory includes the read cache, which includes an ordered list of equal sized cache elements that store read data. A first end of the ordered list stores data that has been in the read cache for the longest time, and a second end of the ordered list stores data that has been in the read cache for the shortest time. The first end of the ordered list is opposite to the second end of the ordered list. The memory also includes metadata, including a host stream size. The host stream size is a current cumulative size of all read requests in a host stream, and the host stream is a consecutive group of sequential read requests from the host computer. The metadata also includes a read cache size, where the read cache size is the cumulative size of all cache elements. After the storage controller receives a read request from the host computer, the processor determines if the host stream size is larger than the read cache size. If the host stream size is larger than the read cache size, the processor migrates data corresponding to the read request to the first end of the ordered list. If the host stream size is not larger than the read cache size, the processor migrates data corresponding to the read request to the second end of the ordered list. 
         [0009]    An advantage of the present invention is it provides a method to more efficiently utilize valuable storage controller cache resources. Cache memory is small compared to storage device resources coupled to the storage controller, and common cache update and replacement policies such as Least Recently Used (LRU) may fill the cache with data that is unlikely to be read in the near future. 
         [0010]    Another advantage of the present invention is it does not require preserving data when a host stream won&#39;t be re-reading it. This frees up cache space to service all of the current host streams. Read cache sizes are typically small when compared to the size of common host streams, which can quickly outgrow read cache size. By abandoning the LRU process early in a host stream, the read cache may not be filled as quickly as when using only the LRU process. 
         [0011]    Additional features and advantages of embodiments of the present invention will become more readily apparent from the following description, particularly when taken together with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1   a  is a block diagram illustrating components of a first non host-based data storage system in accordance with embodiments of the present invention. 
           [0013]      FIG. 1   b  is a block diagram illustrating components of a second non host-based data storage system in accordance with embodiments of the present invention. 
           [0014]      FIG. 1   c  is a block diagram illustrating components of a third non host-based data storage system in accordance with embodiments of the present invention. 
           [0015]      FIG. 2   a  is a block diagram illustrating components of a first host-based data storage system in accordance with embodiments of the present invention. 
           [0016]      FIG. 2   b  is a block diagram illustrating components of a second host-based data storage system in accordance with embodiments of the present invention. 
           [0017]      FIG. 2   c  is a block diagram illustrating components of a third host-based data storage system in accordance with embodiments of the present invention. 
           [0018]      FIG. 3  is a block diagram illustrating a data storage system in accordance with embodiments of the present invention. 
           [0019]      FIG. 4  is a diagram illustrating a host read request in accordance with embodiments of the present invention. 
           [0020]      FIG. 5   a  is a diagram illustrating a sequential forward data stream and metadata in accordance with embodiments of the present invention. 
           [0021]      FIG. 5   b  is a diagram illustrating a sequential reverse data stream and metadata in accordance with embodiments of the present invention. 
           [0022]      FIG. 6   a  is a diagram illustrating metadata stored in the data stream metadata memory in accordance with the preferred embodiment of the present invention. 
           [0023]      FIG. 6   b  is a diagram illustrating cache element reordering during read ahead in accordance with the preferred embodiment of the present invention. 
           [0024]      FIG. 7   a  is a diagram illustrating a host data read with stream size greater than read cache size in accordance with embodiments of the present invention. 
           [0025]      FIG. 7   b  is a diagram illustrating free list re-ordering following a host data read in accordance with embodiments of the present invention. 
           [0026]      FIG. 8   a  is a diagram illustrating a host data read with stream size less than read cache size in accordance with embodiments of the present invention. 
           [0027]      FIG. 8   b  is a diagram illustrating free list re-ordering following a host data read in accordance with embodiments of the present invention. 
           [0028]      FIG. 9  is a flowchart illustrating a host stream size calculation process in accordance with the embodiments of the present invention. 
           [0029]      FIG. 10  is a flowchart illustrating a cache element update process during read ahead in accordance with embodiments of the present invention. 
           [0030]      FIG. 11  is a flowchart illustrating a host stream analysis process in accordance with embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0031]    The present invention is directed to improvements to read cache performance in a storage controller in response to host computer read requests. Keeping in mind the desire to maintain a small read cache memory to keep the storage controller cost down, it is necessary to improve read cache efficiency and performance. 
         [0032]    One way to improve read cache performance is simply to increase the amount of read ahead data as much as possible for each received read request. However, this will usually fill the read cache with useless data that the host computer may never request or may request much later. Additionally, in systems where a storage controller is coupled to multiple host computers, filling a cache with large amounts of read ahead data for a specific host computer may prevent other host computers from utilizing the read cache, severely limiting read performance to the other host computers. 
         [0033]    Each host computer issues read data requests based on the applications and other programs executed by that host computer. In most cases, the applications and other programs currently being executed by one host computer is different than the applications and other programs being executed by a different host computer. Each host computer therefore issues a different set of read requests, which are known as a host stream. In general, storage controllers attempt to maintain a static amount of read ahead data in the read cache for each host stream. A given host computer can issue multiple host streams. 
         [0034]    When an attached host computer is reading large files, it generally does not return to re-read a previously-read area of storage devices. When this happens, it is not efficient to use the LRU algorithm once the attached host reads the data. In most cases, the data is just taking up needless room in read cache when the read cache space could be used more effectively by a read ahead operation. 
         [0035]    While a storage controller is servicing one or more sequential host streams, sometimes the current host stream size is larger than the read cache size. In order to be able to service data requests efficiently when requested read data is in the read cache, the storage controller can employ a cache optimization process that temporarily abandons the LRU algorithm and frees up read cache space that most likely will not be read in the near future. 
         [0036]    What is needed is a storage controller that maintains only enough read ahead data in read cache for each host stream so that cache hits are maximized while reducing un-needed space allocated to unused read ahead data that has already been read by the host computer. 
         [0037]    Referring now to  FIG. 1   a , a block diagram illustrating components of a first non host-based data storage system  100  in accordance with embodiments of the present invention is shown. 
         [0038]    The data storage system  100  includes one or more host computers  104 . Host computer  104  is generally a server, but could also be a desktop or mobile computer. Host computer  104  executes application programs that generate read and write requests to storage controller  108  over host bus or network  112 . Host bus or network  112  in one embodiment is a bus such as SCSI, FC-AL, USB, Firewire, SSA, SAS, SATA, or Infiniband. In another embodiment, host bus or network  112  is a network such as Ethernet, iSCSI, Fiber Channel, SSA, ESCON, ATM, FICON, or Infiniband. 
         [0039]    Host computer  104  interfaces with one or more storage controllers  108 , although only a single storage controller  108  is illustrated for clarity. In one embodiment, storage controller  108  is a RAID controller. In another embodiment, storage controller  108  is a storage appliance such as a provisioning, virtualization, replication, or backup appliance. Storage controller  108  transfers data to and from storage devices  116   a ,  116   b  in storage subsystem  124 , over storage device bus  120 . Storage device bus  120  is any suitable storage bus or group of buses for transferring data directly between storage controller  108  and storage devices  116 , including but not limited to SCSI, Fiber Channel, SAS, SATA, or SSA. 
         [0040]    Storage subsystem  124  in one embodiment contains twelve storage devices  116 . In other embodiments, storage subsystem  124  may contain fewer or more than twelve storage devices  116 . Storage devices  116  include various types of storage devices, including hard disk drives, solid state drives, optical drives, and tape drives. Within a specific storage device type, there may be several sub-categories of storage devices  116 , organized according to performance. For example, hard disk drives may be organized according to cache size, drive RPM (5,400, 7,200, 10,000, and 15,000, for example), queue depth, random transfer rate, or sequential transfer rate. 
         [0041]    Referring now to  FIG. 1   b , a block diagram illustrating components of a second non host-based data storage system  128  in accordance with embodiments of the present invention is shown. Non host-based data storage system  128  is similar to non host-based data storage system  100 , with the exception being storage controller  108  is within storage subsystem  132 , along with storage devices  116 . In the embodiment illustrated in  FIG. 1   b , storage controller  108  is a single RAID controller  108 . However, in other embodiments, storage controller  108  represents multiple RAID controllers  108 . 
         [0042]    Referring now to  FIG. 1   c , a block diagram illustrating components of a third host-based data storage system  136  in accordance with embodiments of the present invention is shown. Data storage system  136  is similar to data storage systems  100  and  128 , except storage controller  108  represents two redundant storage controllers  108   a ,  108   b . In one embodiment, storage controllers  108   a ,  108   b  utilize active-active failover in order to have continued availability to storage devices  116  by host  104  in the event of a failure of one of storage controllers  108   a ,  108   b . Inter-controller messaging link  140  provides a communication and data path between storage controllers  108   a ,  108   b  in order to mirror write data and synchronize failover and failback operations. 
         [0043]    Referring now to  FIG. 2   a , a block diagram illustrating components of a first host-based data storage system  200  in accordance with embodiments of the present invention is shown. First host-based data storage system  200  is similar to first non host-based storage system  100  of  FIG. 1   a , except storage controller  108  is within host computer  104 . Storage controller  108  interfaces through a local bus of host computer  104 , where the local bus may be any suitable bus for high speed transfers between the CPU of host computer  104  and storage controller  108 , including Rapid IO, PCI, PCI-X, or PCI Express. Storage controller  108  may either be integrated on the motherboard of host computer  104 , or may be an add-in board or other form of assembly in host computer  104 . 
         [0044]    Referring now to  FIG. 2   b , a block diagram illustrating components of a second host-based data storage system  204  in accordance with embodiments of the present invention is shown. Second host-based data storage system  204  integrates the functions of storage subsystem  124  into host computer  104 . Data storage system  204  represents a self-contained highly integrated data storage system. 
         [0045]    Referring now to  FIG. 2   c , a block diagram of illustrating components of a third host-based data storage system  208  in accordance with embodiments of the present invention is shown. Third host-based data storage system  208  is similar to first host-based data storage system  200 , but instead of an integrated storage controller  108 , a software-based approach is used. Interface between host computer  104  and storage device bus  120  is provided by host bus adapter  212 , which provides appropriate data and command buffering functions as well as protocol control and low-level error handling. CPU  216  executes applications  224  in memory  220  to control data flow between memory  220  and storage devices  116   a ,  116   b  in storage subsystem  124 . 
         [0046]    Referring now to  FIG. 3 , a block diagram illustrating a data storage system  300  in accordance with embodiments of the present invention is shown. Data storage system  300  includes one or more host computers  104  interconnected to a storage controller  108  through bus or network  336 . Host computer  104  generates a host stream  308 , which includes one or multiple groups of host read requests  332 . 
         [0047]    Storage controller  108  includes a CPU or processor  312 , which executes program instructions stored in a memory  316  coupled to the CPU  312 . CPU  312  includes any processing device suitable for executing storage controller  108  programs, such as Intel x86-compatible processors, embedded processors, mobile processors, and/or RISC processors. CPU  312  may include several devices including field-programmable gate arrays (FPGAs), memory controllers, North Bridge devices, and/or South Bridge devices. 
         [0048]    Memory  316  may be one or more forms of volatile memory  316 , non-volatile memory  316 , or a combination of both volatile and non-volatile memories  316 . The memory  316  includes firmware which includes program instructions that CPU  312  fetches and executes, including program instructions for the processes of the present invention. Examples of non-volatile memory  316  include, but are not limited to, flash memory, SD, EPROM, EEPROM, hard disks, and NOVRAM. Volatile memory  316  stores various data structures and user data. Examples of volatile memory  316  include, but are not limited to, SRAM, DDR RAM, DDR2 RAM, DDR3 RAM, Z-RAM, TTRAM, A-RAM, ETA RAM, and other forms of temporary memory. 
         [0049]    Memory  316  includes a read data cache  324 , also known as a read cache, and in some embodiments a write data cache  328 , which provide improved read and write performance, respectively, to the host computer  104 . Memory  316  also includes data stream metadata  320 . Data stream metadata  320  stores parameters related to host read requests  332 , and are used to control read ahead operations and allocation decisions to the read data cache  324 . 
         [0050]    Storage controller  108  is coupled to storage subsystem  124 ,  132 , which includes one or more storage devices  116   a - 116   n . The most recently accessed data is read from storage devices  116  into the read data cache  324 , where it can be provided in response to host read requests  332  much faster than directly from the storage devices  116 . 
         [0051]    It should be understood that storage controller  108  may be functionally organized in countless different functional organizations and architectures without diverting from the scope or operation of the present invention. 
         [0052]    Referring now to  FIG. 4 , a diagram illustrating a host read request  332  in accordance with embodiments of the present invention is shown. Each host read request  332  includes a read I/O length  440  and a read I/O address  444 . Read I/O length  440  is the number of blocks or bytes to be read from storage devices  116 , and the read I/O address  444  is the starting address the host read request  332  will be read from. 
         [0053]    Referring now to  FIG. 5   a , a diagram illustrating a sequential forward data stream  308   a  and metadata in accordance with embodiments of the present invention is shown. Sequential forward data stream  308   a  includes host read requests  332 . A host computer  104  issues host read requests  332  for the sequential forward data stream  308   a  in ascending order, where the starting address for a next host read request  332  is just following the ending address for the immediately previous host read request  332 . 
         [0054]    When a storage controller  108  detects a sequential forward data stream  308   a , the lowest Logical Block Address (LBA)  504   a  for the sequential forward data stream  308   a  is stored in data stream metadata  320  in the storage controller memory  316 . When a storage controller  108  detects the end of a sequential forward data stream  308   a , the highest Logical Block Address (LBA)  508   a  for the sequential forward data stream  308   a  is stored in data stream metadata  320  in the storage controller memory  316 . 
         [0055]    The difference between the highest LBA in the sequential forward data stream  508   a  and the lowest LBA in the sequential forward data stream  504   a  is the host stream size  512   a , which is also stored in the data stream metadata  320  in the storage controller memory  316 . 
         [0056]    Referring now to  FIG. 5   b , a diagram illustrating a sequential reverse data stream  308   b  and metadata in accordance with embodiments of the present invention is shown. Although many data streams  308  are sequential forward data streams  308   a , in some cases including reverse video playback data streams  308  are sequential reverse data streams  308   b . Sequential reverse data stream  308   b  includes host read requests  332 . A host computer  104  issues host read requests  332  for the sequential reverse data stream  308   b  in descending order, where the starting address for a next host read request  332  is just below the ending address for the immediately previous host read request  332 . 
         [0057]    When a storage controller  108  detects a sequential reverse data stream  308   b , the highest Logical Block Address (LBA)  508   b  for the sequential reverse data stream  308   b  is stored in data stream metadata  320  in the storage controller memory  316 . When a storage controller  108  detects the end of a sequential reverse data stream  308   b , the lowest Logical Block Address (LBA)  504   b  for the sequential reverse data stream  308   b  is stored in data stream metadata  320  in the storage controller memory  316 . 
         [0058]    The difference between the highest LBA in the sequential reverse data stream  508   b  and the lowest LBA in the sequential reverse data stream  504   b  is the host stream size  512   b , which is also stored in the data stream metadata  320  in the storage controller memory  316 . 
         [0059]    In some cases, a data stream  308  may be a sequential forward data stream  308   a  for part of the data stream  308 , and a sequential reverse data stream  308   b  for a different part of the same data stream  308 . 
         [0060]    Referring now to  FIG. 6   a , a block diagram illustrating metadata stored in the data stream metadata  320  in accordance with the preferred embodiment of the present invention is shown. The data stream metadata  320  stores parameters used in the process of the present invention. 
         [0061]    The data stream metadata  320  includes parameters for one or more host streams  308 . Multiple host streams  308  may be issued by multiple host computers  104 , or a single host computer  104 . Each host stream  308  has associated host stream metadata  604 . 
         [0062]    Host stream metadata  604  includes three parameters used in  FIGS. 9-11  of the present invention. A lowest LBA (starting address) in host stream  504 , highest LBA in host stream  508 , and current host stream size  512  is stored for each host stream  308 . The current host stream size  512  is the difference between the highest LBA in host stream  508  and the lowest LBA in host stream  504 . 
         [0063]    The data stream metadata  320  also stores a total cache elements size  608 . The read data cache  324  is divided into an equal number of cache elements  632 . The total cache elements size  608  is the read data cache  324  size. In one embodiment the read data cache size  608  is 798.8 Megabytes (MB), and there are 49,925 cache elements  632  in the read data cache  324 . This means that each cache element  632  is 16 Kilobytes (KB) in size. In other embodiments, the read data cache size  608  is less than or more than 798.8 Megabytes (MB) and there are other than 49,925 cache elements  632  in the read data cache  324 . 
         [0064]    The data stream metadata  320  also includes a free list head pointer  612  and a free list tail pointer  616 . The free list head pointer  612  and free list tail pointer  616  are discussed in more detail with respect to  FIG. 6   b.    
         [0065]    Referring now to  FIG. 6   b , a block diagram illustrating cache element  632  reordering during read ahead in accordance with the preferred embodiment of the present invention is shown. The read data cache  324  is organized into a predetermined number of cache elements  632 . A free list  620  is an ordered sequential list of cache elements  632 . In the preferred embodiment, the free list  620  is organized as a linked list. A linked list is a data structure consisting of a group of nodes which together represent a sequence. Each item in the linked list provides a data element as well as a pointer to the next node in the data structure. 
         [0066]    The free list  620  includes cache elements  632  containing valid read data from storage devices  116 . In some cases, the read data in cache elements  632  is from a cache read ahead operation. In other cases, the read data in cache elements  632  is provided in direct response to a host read request  332 . The free list  620  has a free list head  624  and a free list tail  628 . The free list head  624  and free list tail  628  are identified by the free list head pointer  612  and free list tail pointer  616 , respectively, in the data stream metadata  320 . The free list head  624  and free list tail  628  are the first and second ends, respectively, of the free list  620 . 
         [0067]    The cache elements  632  at the free list head  624  are the oldest cache elements  632  in the read data cache  324 , and the cache elements  632  at the free list tail  628  are the newest cache elements  632  in the read data cache  324 . Therefore, the most recently used cache elements  632  are found at the free list tail  628 , and the least recently used cache elements  632  are found at the free list head  624 . 
         [0068]    In a read ahead operation, the storage controller  108  predicts which data will next be required from host computers  104  and reads that data into the read data cache  324 . In the case of a sequential forward data stream  308   b , the read ahead data will have a higher LBA than the read request operation currently being processed by the storage controller  108 . In the case of a sequential reverse data stream  308   b , the read ahead data will have a lower LBA than the read request operation currently being processed by the storage controller  108 . 
         [0069]    With respect to the free list  620 , the storage controller  108  first stores the read ahead data in cache elements  632  at the head of the free list  624 , and second appends those cache elements  632  to the free list tail  628 . In this way, the newest data in the read data cache  324  is at the free list tail  628 . If cache elements  632   a  and  632   b  include the read ahead data, they are moved to the free list tail  628 , and cache element  632   c  then becomes the oldest data in the read data cache  324  after the read ahead data is appended to the free list tail  628 . 
         [0070]    Referring now to  FIG. 7   a , a diagram illustrating a host data read with stream size  512  greater than read cache size  608  in accordance with embodiments of the present invention is shown. Free list  620  includes cache elements  632 , identified as cache element 0  632   a  through cache element z  632   z . In the illustrated host data read, the requested data is already in the read data cache  704 , stored in cache element l  632   l , cache element m  632   m , and cache element n  632   n.    
         [0071]    Referring now to  FIG. 7   b , a diagram illustrating free list  620  re-ordering following a host data read in accordance with embodiments of the present invention is shown.  FIG. 7   b  illustrates the re-ordering process following the host data read directed to cache elements  632   l ,  632   m , and  632   n  of  FIG. 7   a , after the storage controller  108  has determined the stream size  512  is greater than the data read cache size  608 . Since the stream size  512  is greater than the data read cache size  608 , the storage controller  108  moves cache elements  632   l ,  632   m , and  632   n  containing the requested data to the free list head  708 , or first area of the read cache  324 . Following the move, cache elements  632   l ,  632   m , and  632   n  are no longer present at the old locations illustrated in  FIG. 7   a , but are now available at the free list head  624 , before cache elements 0  632   a,  1  632   b , and 2  632   c . This makes cache elements l  632   l, m    632   m , and n  632   n  positioned as the oldest cache elements  632  in the read data cache  324 , and the first cache elements  632  to be replaced during a read ahead operation. The process steps illustrated in  FIGS. 7   a  and  7   b  are shown in  FIG. 11  steps  1112 - 1120 ,  1140 , and  1144 . 
         [0072]    Referring now to  FIG. 8   a , a diagram illustrating a host data read with stream size  512  less than read cache size  608  in accordance with embodiments of the present invention is shown. Free list  620  includes cache elements  632 , identified as cache element 0  632   a  through cache element z  632   z . In the illustrated host data read, the requested data is already in the read data cache  804 , stored in cache element l  632   l , cache element m  632   m , and cache element n  632   n.    
         [0073]    Referring now to  FIG. 8   b , a diagram illustrating free list  620  re-ordering following a host data read in accordance with embodiments of the present invention is shown.  FIG. 8   b  illustrates the re-ordering process following the host data read directed to cache elements l, m, and n of  FIG. 8   a , after the storage controller  108  has determined the stream size  512  is less than the data read cache size  608 . Since the stream size  512  is less than the data read cache size  608 , the storage controller  108  moves cache elements  632   l ,  632   m , and  632   n  containing the requested data to the free list tail  808 , or second area of the read cache  324 . Following the move, cache elements  632   l ,  632   m , and  632   n  are no longer present at the old locations illustrated in  FIG. 8   a , but are now available at the free list tail  628 , after cache elements x  632   x, y    632   y , and z  632   z . This makes cache elements l  632   l, m    632   m , and n  632   n  positioned as the newest cache elements  632  in the read data cache  324 , and the last cache elements  632  to be replaced during a read ahead operation. The process steps illustrated in  FIGS. 8   a  and  8   b  are shown in  FIG. 11  steps  1112 - 1120 ,  1140 , and  1148 . 
         [0074]    Referring now to  FIG. 9 , a flowchart illustrating a host stream size  512  calculation process in accordance with the embodiments of the present invention is shown. Flow begins at block  904 . 
         [0075]    At block  904 , the storage controller  108  receives a host read request  332  from a host computer  104 . Flow proceeds to decision block  908 . 
         [0076]    At decision block  908 , the storage controller  108  determines if the host read request  332  is part of a new host stream  308  or an already existing host stream  308 . If the host read request  332  is part of a new host stream  308 , then flow proceeds to block  912 . If the host read request  332  is not part of a new host stream  308 , then flow proceeds to block  916 . 
         [0077]    At block  912 , the storage controller  108  stores the lowest  504  and highest  508  LBAs of the received host read request  332  in data stream metadata  320 . Flow returns to block  904  to await a next host read request  332 . 
         [0078]    At block  916 , the storage controller  108  compares the lowest LBA of the received host read request  332  to the lowest LBA  508  of the stream including the host read request  332  in stream metadata  604 . Flow proceeds to decision block  920 . 
         [0079]    At decision block  920 , the storage controller  108  determines if the lowest LBA of the host read request  332  received in block  904  is less than the lowest LBA  504  in stream metadata  604 . If the lowest LBA of the host read request  332  received in block  904  is less than the lowest LBA  504  in stream metadata  604 , then flow proceeds to block  924 . If the lowest LBA of the host read request  332  received in block  904  is not less than the lowest LBA  504  in stream metadata  604 , then flow proceeds to decision block  928 . 
         [0080]    At block  924 , the storage controller  108  sets the lowest LBA  504  in stream metadata  604  equal to the lowest LBA of the host read request  332  received in block  904 . The lowest LBA of the host read request  332  received in block  904  is equal to the read I/O address  444  of the host read request  332 . Flow proceeds to decision block  928 . 
         [0081]    At decision block  928 , the storage controller  108  determines if the highest LBA of the host read request  332  received in block  904  is greater than the highest LBA  508  in stream metadata  604 . If the highest LBA of the host read request  332  received in block  904  is greater than the highest LBA  508  in stream metadata  604 , then flow proceeds to block  932 . If the highest LBA of the host read request  332  received in block  904  is not greater than the highest LBA  508  in stream metadata  604 , then flow proceeds to block  936 . 
         [0082]    At block  932 , the storage controller  108  sets the highest LBA  508  in stream metadata  604  equal to the highest LBA of the host read request  332  received in block  904 . The highest LBA of the host read request  332  received in block  904  is equal to the sum of the read I/O address  444  and the read I/O length  440  of the host read request  332 . Flow proceeds to block  936 . 
         [0083]    At block  936 , the storage controller  108  sets the host stream size  512  equal to the highest LBA  508  in stream metadata  604  minus the lowest LBA  504  in stream metadata  604 . Flow proceeds to at block  904 . 
         [0084]    Referring now to  FIG. 10 , a flowchart illustrating a cache element  632  update process during read ahead in accordance with embodiments of the present invention is shown. Flow begins at block  1004 . 
         [0085]    At block  1004 , the storage controller  108  determines the number of cache elements  632  to replace. The number of cache elements  632  to replace depends on the cache element  632  size, the read data cache size  608 , and the desired amount of read ahead data to fetch from storage devices  116 . In the preferred embodiment where the storage devices  116  are striped, two stripes are generally the amount of data brought into the read data cache  324  during a read ahead operation. Flow proceeds to block  1008 . 
         [0086]    At block  1008 , the storage controller  108  removes the determined cache elements  632  from the head of the free list  624 . Flow proceeds to block  1012 . 
         [0087]    At block  1012 , storage controller  108  reads read ahead data from storage devices  116 . Flow proceeds to block  1016 . 
         [0088]    At block  1016 , the storage controller  108  stores the read ahead data from block  1004  in the removed cache elements  636 . Flow proceeds to block  1020 . 
         [0089]    At block  1020 , the storage controller  108  adds the removed cache elements  640  to the tail of the free list  628 . Flow ends at block  1020 . 
         [0090]    Referring now to  FIG. 11 , a flowchart illustrating a host stream  308  analysis process in accordance with embodiments of the present invention is shown. Flow begins at block  1104 . 
         [0091]    At block  1104 , the storage controller  108  receives a host read request  332  from a host computer  104 . Flow proceeds to decision block  1108 . 
         [0092]    At decision block  1108 , the storage controller  108  determines if the read request data corresponding to the host read request  332  of block  1104  is present in the cache elements  632 . If the read request data corresponding to the host read request  332  of block  1104  is present in the cache elements  632 , then flow proceeds to block  1112 . If the read request data corresponding to the host read request  332  of block  1104  is not present in the cache elements  632 , then flow proceeds to block  1124 . 
         [0093]    At block  1112 , the storage controller  108  determines the cache elements  632  containing the host read request data. Flow proceeds to block  1116 . 
         [0094]    At block  1116 , the storage controller  108  removes the cache elements  632  containing the host read request data from the free list  620 . Flow proceeds to block  1120 . 
         [0095]    At block  1120 , the storage controller  108  processes the host read request  332  from cache elements  632  containing the host read request data. Flow proceeds to decision block  1140 . 
         [0096]    At block  1124 , the storage controller  108  determines the number of cache elements  632  to replace. Flow proceeds to block  1128 . 
         [0097]    At block  1128 , the storage controller  108  removes the determined number of cache elements  632  from block  1124  from the head of the free list  624 . Flow proceeds to block  1132 . 
         [0098]    At block  1132 , the storage controller  108  processes the host read request  332  from block  1104  from storage devices  116  containing the host read request data. Flow proceeds to block  1136 . 
         [0099]    At block  1136 , the storage controller  108  stores the host read request data in the removed cache elements  632  from block  1128 . Flow proceeds to decision block  1140 . 
         [0100]    At decision block  1140 , the storage controller  108  determines if the current host stream size  512  is greater than the total cache elements size  608 . The total cache elements size  608  is the size of the read data cache  324 . If the current host stream size  512  is greater than the total cache elements size  608 , then flow proceeds to block  1144 . If the current host stream size  512  is not greater than the total cache elements size  608 , then flow proceeds to block  1148 . 
         [0101]    If the host stream size  512  is larger than read data cache size  608 , this means the host stream  308  is large and the storage controller  108  will perform better by using all read data cache  324  for read ahead data, rather than maintaining older cache elements  632  in case those cache elements  632  are again re-read. If the host stream size  512  is smaller than the read data cache size  608 , this means the storage controller  108  should maintain read data cache  324  data as long as possible via the LRU update process and attempt to promote read data cache  324  hits in the event of data being re-read in the future. 
         [0102]    At block  1144 , the storage controller  108  adds the previously removed cache elements  632  from blocks  1116  and  1128  to the head of the free list  624 . Flow ends at block  1144 . 
         [0103]    At block  1148 , the storage controller  108  adds the previously removed cache elements  632  from blocks  1116  and  1128  to the tail of the free list  628 . Flow ends at block  1148 . 
         [0104]    Although the process steps of the present invention describe the storage controller  108  performing the actions, it is understood by one of ordinary skill in the art that a CPU or processor  312  generally performs these steps. However, in other embodiments, one or more processors, state machines, programmable logic devices, or other devices may perform these steps. 
         [0105]    Finally, those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiments as a basis for designing or modifying other structures for carrying out the same purposes of the present invention without departing from the spirit and scope of the invention as defined by the appended claims.