Abstract:
A method for improving I/O performance by a storage controller is provided. The method includes receiving a command completion from a storage device and checking for a command stored in a command queue for more than a predetermined time period. If a command has been in the command queue for more than the predetermined time period, then issuing the command and removing the command from the command queue. If no commands have been stored in the command queue for more than the predetermined time period, then determining if there are any uncompleted commands previously issued to the storage device. If there are not any uncompleted commands previously issued to the storage device, then processing a next command in the command queue and removing the next command from the command queue.

Description:
FIELD 
       [0001]    The present invention is directed to computer data storage. In particular, the present invention is directed to methods and apparatuses for efficient processing of mixed sequential and non-sequential data storage commands by a storage controller. 
       BACKGROUND 
       [0002]    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. 
         [0003]    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 commands. Many storage controllers store read and write data in cache memories included as part of the storage controllers. In general, storage controllers are designed and intended to service both sequential and random read and write requests from one or more host computers. Sequential requests are generally sent to a storage controller as either a stream of read requests or a stream of write requests. Most of the time, the Logical Block Addresses of later-issued sequential requests are spatially adjacent to the immediately preceding sequential request, and a sequential stream is generally, but not necessarily, consistently increasing or decreasing in LBA. 
         [0004]    Once processing a sequential stream, conventional storage controllers continue processing the stream until the controller detects the stream has ended. In this way, sequential read or write performance is maximized to the host computer issuing the sequential stream. 
       SUMMARY 
       [0005]    The present invention is directed to solving disadvantages of the prior art. In accordance with embodiments of the present invention, a method for improving I/O performance by a storage controller is provided. The method includes receiving, by the storage controller, a command completion from a storage device coupled to the storage controller, where the storage controller includes a command queue, and checking, by the storage controller, for a command stored in the command queue for more than a predetermined time period. If a command has been in the command queue for more than the predetermined time period, then the method includes issuing to the storage device, by the storage controller, the command that has been stored in the command queue for more than the predetermined time period and removing, by the storage controller, the command from the command queue. If no commands have been stored in the command queue for more than the predetermined time period, then the method includes determining, by the storage controller, if there are any uncompleted commands previously issued to the storage device. If there are not any uncompleted commands previously issued to the storage device, then the method includes processing, by the storage controller, a next command in the command queue and removing, by the storage controller, the next command from the command queue. 
         [0006]    In accordance with another embodiment of the present invention, a storage controller providing improved I/O performance is provided. The storage controller includes a processor and a memory, coupled to the processor. The memory includes a command queue. The processor receives a command completion from a storage device coupled to the storage controller, and checks for a command stored in the command queue for more than a predetermined time period. If a command has been stored in the command queue for more than the predetermined time period, the storage controller issues to the storage device the command that has been in the command queue for more than the predetermined time period and removes the command from the command queue. If no commands have been stored in the command queue for more than the predetermined time period, the processor determines if there are any uncompleted commands previously issued to the storage device. If there are not any uncompleted commands previously issued to the storage device, the processor processes a next command in the command queue and removes the next command from the command queue. 
         [0007]    In accordance with yet another embodiment of the present invention, a storage system for providing improved I/O performance is provided. The storage system includes a storage device and a storage controller coupled to the storage device. The storage controller includes a processor and a memory, coupled to the processor. The memory includes a command queue, which includes a time-sorted queue and an LBA-sorted queue. The processor receives a command completion from the storage device and checks for a command stored in the command queue for more than a predetermined time period. If a command has been stored in the command queue for more than the predetermined time period, the storage controller issues to the storage device the command that has been in the command queue for more than the predetermined time period and the processor removes the command from the command queue. If no commands have been stored in the command queue for more than the predetermined time period, the processor determines if there are any uncompleted commands previously issued to the storage device. If there are not any uncompleted commands previously issued to the storage device, the processor processes a next command in the command queue and removes the next command from the command queue. 
         [0008]    An advantage of the present invention is it provides a method to balance processing of sequential and random host data requests. When a storage device command completion is detected, the method looks for unissued commands in a storage controller command queue that have been present in the queue for more than a predetermined time period. This prevents a host application corresponding to unissued commands from being starved due to non-servicing or late servicing during execution of a large sequential stream by the storage controller. 
         [0009]    Another advantage of the present invention is it provides for an expanding and contracting command queue for each storage device, according to the I/O commands issued to each storage device. 
         [0010]    Yet another advantage of the present invention is it sorts all storage device commands in an LBA-sorted list as well as a time-sorted list. The two lists provide increased efficiency when processing sequential commands (LBA-sorted list), while making sure that unrelated commands (time-sorted list) do not get stalled. 
         [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 block diagram illustrating storage device command queues in accordance with embodiments of the present invention. 
           [0020]      FIG. 5   a  is a block diagram illustrating storage device read and write commands in accordance with embodiments of the present invention. 
           [0021]      FIG. 5   b  is a block diagram illustrating Logical Block Address (LBA) and time-sorted queues in accordance with embodiments of the present invention. 
           [0022]      FIG. 6   a  is a diagram illustrating an exemplary storage device command sequence in accordance with embodiments of the present invention. 
           [0023]      FIG. 6   b  is a diagram illustrating a storage device command sequence sorted by time and LBA in accordance with the embodiments of the present invention. 
           [0024]      FIG. 7  is a diagram illustrating storage device multiple command streams in accordance with embodiments of the present invention. 
           [0025]      FIG. 8  is a flowchart illustrating a new host read or write request update process in accordance with embodiments of the present invention. 
           [0026]      FIG. 9   a  is a flowchart illustrating a first portion of a command issue process for a single older command in accordance with embodiments of the present invention. 
           [0027]      FIG. 9   b  is a flowchart illustrating a second portion of a command issue process for a single older command in accordance with the embodiments of the present invention. 
           [0028]      FIG. 10   a  is a flowchart illustrating a first portion of a command issue process for multiple older commands in accordance with embodiments of the present invention. 
           [0029]      FIG. 10   b  is a flowchart illustrating a second portion of a command issue process for multiple older commands in accordance with embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0030]    The present invention is directed to improvements to storage device command issue in a storage controller in response to host computer read and write requests from multiple host computers. Each host computer generates independent read and write requests, based on operating system and host application execution. These read and write requests may be sequential, random, or a mix of sequential and random. 
         [0031]    Storage controllers convert all received host read and write requests into storage device read and write commands, with a unique command queue maintained in storage controller memory for each storage device controlled by the storage controller. All unissued storage device read and write commands are stored in the command queues. 
         [0032]    What is needed is an efficient way to process simultaneous and disparate storage device read and write commands, so that no host read and write requests are unserviced for an unacceptable period of time. For example, an unacceptable period of time may result in slow system performance, a host read or write request timing out and causing an application error, or other adverse operating system or application failure. 
         [0033]    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. 
         [0034]    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. 
         [0035]    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. 
         [0036]    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. 
         [0037]    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 . 
         [0038]    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. 
         [0039]    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 . 
         [0040]    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. 
         [0041]    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 . 
         [0042]    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 one or more host streams  308 , which includes one or multiple groups of host read and write requests  332 . 
         [0043]    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. 
         [0044]    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. 
         [0045]    Memory  316  includes a read data cache  324 , also known as a read cache, and in some embodiments a write data cache  328 , also known as a write cache, 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 and write requests  332 . 
         [0046]    Storage controller  108  is coupled to storage subsystem  124 ,  132 , which includes one or more storage devices  116   a - 116   n . Read data  340  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 . Write data  344  is provided to storage devices  116  from the write data cache  328 . 
         [0047]    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. 
         [0048]    Referring now to  FIG. 4 , a block diagram illustrating storage device command queues  408  in accordance with embodiments of the present invention is shown. Storage controller  108  includes a storage device command queue  408  for each storage device  116  controlled by storage controller  108 . In the embodiment illustrated in  FIG. 4 , there are z storage devices  116 , identified as storage device 0  116   a  through storage device z  116   z . Each of the z storage devices is coupled to one of z command queues  408  in storage controller memory  316 , identified as storage device 0 command queue  408   a  through storage device Z command queue  408   z . Each of the z command queues  408  provides storage device read and write commands  404  to the z storage devices  116 . 
         [0049]    Each storage device command queue  408  may contain the same or different number of storage device commands  404  as any other storage device command queue  408 . For example, storage device 0 command queue  408   a  includes m storage device commands  404 , identified as SD0 cmd 0 through SD0 cmd m. Storage device 1 command queue  408   b  includes n storage device commands  404 , identified as SD1 cmd 0 through SD1 cmd n. Storage device 2 command queue  408   c  includes o storage device commands  404 , identified as SD2 cmd 0 through SD2 cmd o. Storage device 3 command queue  408   d  includes p storage device commands  404 , identified as SD3 cmd 0 through SD3 cmd p. Storage device Z command queue  408   z  includes q storage device commands  404 , identified as SDZ cmd 0 through SDZ cmd q. 
         [0050]    Referring now to  FIG. 5   a , a block diagram illustrating storage device read and write commands  404  in accordance with embodiments of the present invention is shown. Storage device read and write commands  404  includes storage device read commands  504  and storage device write commands  512 . Each storage device read command  504  includes a read command length  506 , typically in bytes of data, and a read command address  508 , which is the Logical Block Address. Each storage device write command  512  includes a write command length  514 , typically in bytes of data, and a write command address  516 , which is the Logical Block Address. 
         [0051]    Referring now to  FIG. 5   b , a block diagram illustrating Logical Block Address (LBA)  520  and time-sorted  524  queues in accordance with embodiments of the present invention is shown. Each storage device command queue  408  includes two different and independent queues. A storage device LBA-sorted queue  520  stores storage device read and write commands  404  directed to a corresponding storage device 116 in Logical Block Address (LBA) order. A storage device time-sorted queue  524  stores storage device read and write commands  404  directed to the corresponding storage device 116 in time order. Each entry in a storage device time-sorted queue  524  includes a time stamp indicating the time a storage device read or write command  404  is added to the storage device time-sorted queue  524 . 
         [0052]    At all times, there are the same number of storage device read and write commands  404  in a storage device LBA-sorted queue  520  and a storage device time-sorted queue  524  that are part of the same storage device command queue  408 . New storage device read and write commands  404  are added to queues  520  and  524  at the same time, and newly issued storage device read and write commands  404  are removed from queues  520  and  524  at the same time. 
         [0053]    Referring now to  FIG. 6   a , a diagram illustrating an exemplary storage device command  404  sequence in accordance with embodiments of the present invention is shown. A storage controller  108  received host read and write requests  332 , and converts host read and write requests  332  into storage device read and write requests  404 . In the example of  FIG. 6   a , a series of six sequential storage device write commands  404  are directed to a specific storage device 116. The six sequential storage device write commands  404  are identified as write cmd 0  604 , write cmd 1  608 , write cmd 2  612 , write cmd 3  616 , write cmd 4  620 , and write cmd 5  624 . The six sequential storage device write commands  404  are in a sequentially ascending sequence, where a temporally later storage device write command  404  is at a higher LBA than the temporally previous storage device write commands  404 . After the storage controller  108  adds write cmd 2  612  to the storage device command queue  408 , read command 0  628  is added to the storage device command queue  408 . 
         [0054]    Referring now to  FIG. 6   b , a diagram illustrating a storage device command  404  sequence sorted by time and LBA in accordance with the embodiments of the present invention is shown.  FIG. 6   b  illustrates the storage device command  404  sequence illustrated in  FIG. 6   a.    
         [0055]    Each storage device command  404  is present in a storage device time-sorted queue  524  and a storage device LBA-sorted queue  520 . The storage device time-sorted queue  524  stores each command in the time order the command  404  is added to the storage device time-sorted queue  524 . Therefore, read command 0  628  is stored between write command 2  612  and write command 3  616  since read command 0  628  is received into the storage device time-sorted queue  524  between the two write commands, as shown in  FIG. 6   a.    
         [0056]    Each entry in the storage device time-sorted queue  524  includes a time stamp  632 . Write command 0  604  is stored with time stamp  632   a , reflecting the time that write command 0  604  is added to the storage device time-sorted queue  524 . Write command 1  608  is stored with time stamp  632   b , reflecting the time that write command 1  608  is added to the storage device time-sorted queue  524 . Write command 2  612  is stored with time stamp  632   c , reflecting the time that write command 2  612  is added to the storage device time-sorted queue  524 . Read command 0  628  is stored with time stamp  632   d , reflecting the time that read command 0  628  is added to the storage device time-sorted queue  524 . Write command 3  616  is stored with time stamp  632   e , reflecting the time that write command 3  616  is added to the storage device time-sorted queue  524 . Write command 4  620  is stored with time stamp  632   f , reflecting the time that write command 4  620  is added to the storage device time-sorted queue  524 . Finally, write command 5  624  is stored with time stamp  632   g , reflecting the time that write command 5  624  is added to the storage device time-sorted queue  524 . At all times, the oldest storage device command  404  in the storage device time-sorted queue  524  is at one end of the storage device time-sorted queue  524 , and the newest storage device command  404  in the storage device time-sorted queue  524  is at opposite end of the storage device time-sorted queue  524 . 
         [0057]    Storage device commands  404  are stored in the storage device LBA-sorted queue  520  in LBA  508 ,  516  order. As shown in  FIG. 6   a , read command 0  628  has a lower LBA  508  and the LBA  516  for any and all of the write commands  604 ,  608 ,  612 ,  616 ,  620 , and  624 . Therefore, read command 0  628  is at one end of the storage device LBA-sorted queue  520 . The storage device command  404  at the opposite end of the storage-device LBA-sorted queue  520  is write command 5  624 , since it has the highest LBA of all of the storage device commands  404 . Therefore, in the example of  FIG. 6   a , the oldest command, write command 0  604 , is not at one end of the storage device LBA-sorted queue  520 , although write command 5  624  is at the opposite end of the storage device LBA-sorted queue  520 . A next I/O pointer  636  identifies the entry in the storage device LBA-sorted queue  520  with the next highest LBA  508 ,  516 . The processes of  FIGS. 9   a ,  9   b ,  10   a , and  10   b  utilize the next I/O pointer  636  when selecting a next storage device read or write command  404 . 
         [0058]    Referring now to  FIG. 7 , a diagram illustrating storage device multiple command streams in accordance with embodiments of the present invention is shown. Three storage device command streams are shown, identified as storage device write streams a, b, and c. 
         [0059]    Storage device write stream a includes nine storage device write commands  404 , identified as write command a0  704   a  through write command a8  704   i . Storage device write stream b includes nine storage device write commands  404 , identified as write command b0  708   a  through write command b8  708   i . Storage device write stream c includes seven storage device write commands  404 , identified as write command c0  712   a  through write command c6  712   g.    
         [0060]    In addition to the storage device write commands  404  of write streams a, b, and c, six read commands  404  are interspersed temporally and with varying LBAs  508 . For example, read command 0  716  has a time stamp  632  between write commands a0  704   a  and a1  704   b  of write stream a, between write commands b0  708   a  and b1  708   b  of write stream b, and write commands c0  712   a  and c1  712   b  of write stream c. However, read command 0  716  has the lowest LBA  508  of all storage device commands  404  shown in  FIG. 7 . 
         [0061]    Read command 1  720  has a time stamp  632  between write commands a2  704   c  and a3  704   d  of write stream a, between write commands b2  708   c  and b3  708   d  of write stream b, and write commands c2  712   c  and c3  712   d  of write stream c. However, read command 1  720  has an LBA  508  between write command b0  708   a  and write command b1  708   b , and between write command a4  704   e  and write command a5  704   f.    
         [0062]    Read command 2  724  has a time stamp  632  equal to write command a4  704   e  of write stream a, write command b4  708   e  of write stream b, and write command c4  712   e  of write stream c. However, read command 2  724  has an LBA  508  between read command 0  716 , and write commands a0  704   a  and read command 4  732 . 
         [0063]    Read command 3  728  has a time stamp  632  between write commands a5  704   f  and a6  704   g  of write stream a, between write commands b5  708   f  and b6  708   g  of write stream b, and write commands c5  712   f  and c6  712   g  of write stream c. However, read command 3  728  has an LBA  508  between write command a1  704   b  and write command a2  704   c.    
         [0064]    Read command 4  732  has a time stamp  632  between write commands a6  704   g  and a7  704   h  of write stream a, between write commands b6  708   g  and b7  708   h  of write stream b, and after write command c6  712   g  of write stream c. However, read command 4  732  has an LBA  508  equal to write command a0  704   a.    
         [0065]    Read command 5  736  has a time stamp  632  between write commands a7  704   h  and a8  704   i  of write stream a, and between write commands b7  708   h  and b8  708   i  of write stream b. However, read command 5  736  has an LBA  508  between write command b1  708   b  and write command b2  708   c , and between write command a5  704   f  and write command a6  704   g.    
         [0066]    Referring now to  FIG. 8 , a flowchart illustrating a new host read or write request  332  update process in accordance with embodiments of the present invention is shown. Flow begins at block  804 . 
         [0067]    At block  804 , the storage controller  108  receives a new host read or write request  332  from a host computer  104 . Flow proceeds to block  808 . 
         [0068]    At block  808 , the storage controller  108  converts new host read or write request  332  into one or more storage device read or write commands  404 . In some embodiments, the storage controller  108  utilizes Redundant array of Inexpensive Disks (RAID) algorithms to determine which storage devices  116  receive storage device read or write commands  404 , and which data and LBAs these commands should be directed to. In other embodiments, the storage controller  108  utilizes command coalescing processes to combine storage device read or write requests  404  directed to the same or closely spaced LBAs. Flow proceeds to block  812 . 
         [0069]    At block  812 , the storage controller  108  places one or more storage device read or write commands  404  into one or more storage device time-sorted queues  524  and appends time stamps  632  to each new entry in a storage device time-sorted queue  524 . The one or more storage device read or write commands  404  are the one or more storage device read or write commands  404  of block  808 . Flow proceeds to block  816 . 
         [0070]    At block  816 , the storage controller  108  places the one or more storage device read or write commands  404  of block  808  into one or more storage device LBA-sorted queues  520 , according to LBA. The one or more storage device LBA-sorted queues  520  are individually included in the same storage device command queues  408  as the storage device time-sorted queues  524  of block  812 . At this point, the storage device command queues  408  have been fully updated based on the new host read or write request  332  of block  804 , and the asynchronous processes of  FIGS. 9   a ,  9   b ,  10   a , and  10   b  are free to operate on the storage device command queues  408  after receiving command completions from storage devices  116 . Flow ends at block  816 . 
         [0071]    Referring now to  FIG. 9   a , a flowchart illustrating a first portion of a command issue process for a single older command  404  in accordance with embodiments of the present invention is shown. Flow begins at block  904 . 
         [0072]    At block  904 , the storage controller  108  receives a command completion from a storage device 116. The command completion indicates to the storage controller  108  that a storage device read or write command  404  has been completed, and the completed storage device read or write command  404  has been removed from a command queue in the storage device 116. Flow proceeds to block  908 . 
         [0073]    At block  908 , the storage controller  108  checks for an unissued command  404  in the time-sorted queue  524  with age greater than a predetermined time period. An unissued command is a command  404  in the time-sorted queue  524  that has not yet been sent to the storage device 116 as a storage device read or write command  404 . The predetermined time period is based on the number of streams  308  the storage controller  108  is currently processing to a given storage device 116. In the preferred embodiment, the predetermined time period is 100 milliseconds (ms) X the number of host streams  308 , with a maximum time period of 800 ms. Therefore, in the preferred embodiment the predetermined time period may increase or decrease based on the number of active streams  308 . However, in other embodiments, a fixed predetermined time period may be used instead. Flow proceeds to decision block  912 . 
         [0074]    At decision block  912 , the storage controller  108  determines if an older command  404  is present in the time-sorted queue  524 . If there is an unissued command  404  in the time-sorted queue  524  with age greater than the predetermined time period, then flow proceeds to block  916 . If there is not an unissued command  404  in the time-sorted queue  524  with age greater than the predetermined time period, then flow proceeds to decision block  928  of  FIG. 9   b.    
         [0075]    At block  916 , the storage controller  108  issues the older command  404  to the storage device 116. Flow proceeds to block  920 . 
         [0076]    At block  920 , the storage controller  108  removes the older command  404  from both the time-sorted queue  524  and the LBA-sorted queue  520 , and adjusts links in both queues  520 ,  524 . In the preferred embodiment, queues  520  and  524  are linked lists, where each item in the list includes a pointer to the next item in the list. When an item in a linked list is removed from the linked list, the pointer of the immediately previous item in the list is modified to instead point to the item immediately following the removed item. Flow proceeds to block  924 . 
         [0077]    At block  924 , the storage controller  108  increments the next I/O pointer  636  to point to the next command  404  in the LBA-sorted queue  520 . This prepares the LBA-sorted queue  520  to issue the next command  404  in the list in an efficient manner. Flow ends at block  924 , and the process waits until the storage controller  108  receives a new command completion from a storage device 116. 
         [0078]    Referring now to  FIG. 9   b , a flowchart illustrating a second portion of a command issue process for a single older command  404  in accordance with embodiments of the present invention is shown. Flow begins at decision block  928 , continuing from decision block  912  of  FIG. 9   a.    
         [0079]    At decision block  928 , the storage controller  108  determines if there are any pending old I/O commands. Pending old I/O commands are storage device read or write commands  404  that have been issued to the storage device 116 but have not yet completed. The storage controller  108  maintains for each storage device 116 a current count of pending old I/O commands. The count is incremented when a new storage device read or write command  404  is issued to a storage device 116, and the count is decremented when the storage controller  108  receives a command completion from the storage device 116. If there are any pending old I/O commands for the storage device 116, then flow ends at decision block  928 . In this case, it is most efficient to wait until pending old I/O commands have completed before processing a next command  404  in the LBA-sorted queue  520 . If there are not any pending old I/O commands to the storage device 116, then flow proceeds to block  932 . 
         [0080]    At block  932 , the storage controller  108  processes the next command  404  in the LBA-sorted queue  520  identified by the next I/O pointer  636 . There are not more pending old I/O commands to the storage device 116; therefore, continuing processing commands  404  in the LBA-sorted queue  520  is efficient. Flow proceeds to block  936 . 
         [0081]    At block  936 , the storage controller  108  removes the next command 404  processed in block  932  from the time-sorted queue  524  and the LBA-sorted queue  520 , and adjusts links in both queues  520 ,  524  as described with reference to block  920 . Flow proceeds to block  940 . 
         [0082]    At block  940 , the storage controller  108  increments the next I/O pointer  936  to point to the next command  404  in the LBA-sorted queue  520 . This prepares the LBA-sorted queue  520  to issue the next command  404  in the list in an efficient manner. Flow proceeds to decision block  944 . 
         [0083]    At decision block  944 , the storage controller  108  determines if there are more unissued commands  404  in the LBA-sorted queue  520 . If there are more unissued commands  404  in the LBA-sorted queue  520 , then flow proceeds to decision block  948  to check the storage device 116 queue depth. If there are not more unissued commands  404  in the LBA-sorted queue  520 , then the storage controller  108  checks for any pending old I/O commands and proceeds to decision block  928 . 
         [0084]    At decision block  948 , the storage controller  108  determines if the storage device 116 queue depth has been exceeded. The storage device 116 queue depth is the maximum number of storage device read or write commands  404  that the storage device 116 can simultaneously process. If the storage device 116 queue depth has been exceeded, then the storage device 116 can accept no more storage device read or write commands  404 , the storage controller  108  must wait for a command completion, and flow ends at decision block  948 . If the storage device 116 queue depth has not been exceeded, then flow proceeds to block  928  to check for any pending old I/O commands to the storage device 116. 
         [0085]    It should be noted that the process of  FIGS. 9   a  and  9   b  apply to a single time-sorted queue  524  and a single LBA-sorted queue  520  for a single storage device 116. Therefore, the processes of  FIGS. 9   a  and  9   b  would be independently executed for each storage device 116 controlled by the storage controller  108 . 
         [0086]    Referring now to  FIG. 10   a , a flowchart illustrating a first portion of a command issue process for multiple older commands  404  in accordance with embodiments of the present invention is shown. Flow begins at block  1004 . 
         [0087]    At block  1004 , the storage controller  108  receives a command completion from a storage device 116. The command completion indicates to the storage controller  108  that a storage device read or write command  404  has been completed, and the completed storage device read or write command  404  has been removed from a command queue in the storage device 116. Flow proceeds to block  1008 . 
         [0088]    At block  1008 , the storage controller  108  checks for an unissued command 404  in the time-sorted queue  524  with age greater than a predetermined time period. An unissued command is a command  404  in the time-sorted queue  524  that has not yet been sent to the storage device 116 as a storage device read or write command  404 . The predetermined time period is based on the number of streams  308  the storage controller  108  is currently processing to a given storage device 116. In the preferred embodiment, the predetermined time period is 100 milliseconds (ms) X the number of host streams  308 , with a maximum time period of 800 ms. Therefore, in the preferred embodiment the predetermined time period may increase or decrease based on the number of active streams  308 . However, in other embodiments, a fixed predetermined time period may be used instead. Flow proceeds to decision block  1012 . 
         [0089]    At decision block  1012 , the storage controller  108  determines if an older command  404  is present in the time-sorted queue  524 . If there is an unissued command  404  in the time-sorted queue  524  with age greater than the predetermined time period, then flow proceeds to block  1016 . If there is not an unissued command  404  in the time-sorted queue  524  with age greater than the predetermined time period, then flow proceeds to decision block  1028  of  FIG. 10   b.    
         [0090]    At block  1016 , the storage controller  108  issues a predetermined number of older commands  404  to the storage device 116. The predetermined number of older commands  404  issued to the storage device  116  is selected in order to not exceed the storage device 116 queue depth. The count of pending old I/O commands discussed with reference to block  1028  cannot exceed the predetermined number of older commands  404  issued to the storage device 116. Flow proceeds to block  1020 . 
         [0091]    At block  1020 , the storage controller  108  removes the older commands  404  from both the time-sorted queue  524  and the LBA-sorted queue  520 , and adjusts links in both queues  404 . In the preferred embodiment, queues  520  and  524  are linked lists, where each item in the list includes a pointed to the next item in the list. When an item in a linked list is removed from the linked list, the pointer of the immediately previous item in the list is modified to instead point to the item immediately following the removed item. Flow proceeds to block  1024 . 
         [0092]    At block  1024 , the storage controller  108  increments the next I/O pointer  636  to point to the next command  404  in the LBA-sorted queue  520 . This prepares the LBA-sorted queue  520  to issue the next command  404  in the list in an efficient manner. Flow ends at block  1024  to wait for a next command completion from the storage device 116. 
         [0093]    Referring now to  FIG. 10   b , a flowchart illustrating a second portion of a command issue process for multiple older commands  404  in accordance with embodiments of the present invention is shown. Flow begins at decision block  1028 , continuing from decision block  1012  of  FIG. 10   a.    
         [0094]    At decision block  1028 , the storage controller  108  determines if there are any pending old I/O commands. Pending old I/O commands are storage device read or write commands  404  that have been issued to the storage device 116 but have not yet completed. The storage controller  108  maintains for each storage device 116 a current count of pending old I/O commands. The count is incremented when a new storage device read or write command  404  is issued to a storage device 116, and the count is decremented when the storage controller  108  receives a command completion from the storage device 116. If there are any pending old I/O commands to the storage device 116, then flow ends at decision block  1028 . In this case, it is most efficient to wait until pending old I/O commands have completed before processing a next command  404  in the LBA-sorted queue  520 . If there are not any pending old I/O commands to the storage device, then flow proceeds to block  1032 . 
         [0095]    At block  1032 , the storage controller  108  processes the next command  404  in the LBA-sorted queue  520  identified by the next I/O pointer  636 . There are not more pending old I/O commands to the storage device; therefore, continuing processing commands  404  in the LBA-sorted queue  520  is efficient. Flow proceeds to block  1036 . 
         [0096]    At block  1036 , the storage controller  108  removes the next command 404  processed in block  1032  from the time-sorted queue  524  and the LBA-sorted queue  520 , and adjusts links in both queues  520 ,  524  as described with reference to block  1020 . Flow proceeds to block  1040 . 
         [0097]    At block  1040 , the storage controller  108  increments the next I/O pointer  936  to point to the next command  404  in the LBA-sorted queue  520 . This prepares the LBA-sorted queue  520  to issue the next command  404  in the list in an efficient manner. Flow proceeds to decision block  1044 . 
         [0098]    At decision block  1044 , the storage controller  108  determines if there are more unissued commands  404  in the LBA-sorted queue  520 . If there are not more unissued commands  404  in the LBA-sorted queue  520 , then flow proceeds to decision block  1028  to check for pending old I/O commands to the storage device 116. If there are more unissued commands  404  in the LBA-sorted queue  520 , then the storage controller  108  checks the storage device 116 queue depth and flow proceeds to decision block  1048 . 
         [0099]    At decision block  1048 , the storage controller  108  determines if the storage device 116 queue depth has been exceeded. The storage device 116 queue depth is the maximum number of storage device read or write commands  404  that the storage device 116 can simultaneously process. If the storage device 116 queue depth has been exceeded, then the storage device 116 can accept no more storage device read or write commands  404 , the storage controller  108  must wait for a command completion, and flow ends at decision block  1048 . If the storage device 116 queue depth has not been exceeded, then flow proceeds to block  1028  to check for any pending old I/O commands to the storage device 116. 
         [0100]    It should be noted that the process of  FIGS. 10   a  and  10   b  apply to a single time-sorted queue  524  and a single LBA-sorted queue  520  for a single storage device 116. Therefore, the processes of  FIGS. 10   a  and  10   b  would be independently executed for each storage device 116 controlled by the storage controller  108 . 
         [0101]    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. 
         [0102]    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.