Patent Publication Number: US-11663144-B2

Title: LRU list reorganization for favored and unfavored volumes

Description:
BACKGROUND 
     Field of the Invention 
     This invention relates to systems and methods for increasing cache hit ratios for selected volumes within a storage system. 
     Background of the Invention 
     When an I/O request is performed by an application, several processes may be performed to complete the request. These processes affect I/O latency, which can be a significant part of application response time. zHyperLink is a technology designed to reduce I/O latency by providing a fast, reliable, and direct communication path between a host system and a storage system. This is accomplished by installing zHyperLink adapters on the z/OS host system and storage system, and connecting the components together using zHyperLink cables. This configuration creates a point-to-point connection between the host system and storage system, which reduces I/O response times by up to ten times compared to z High-Performance FICON® (zHPF). Such low response times are achieved by using synchronous I/O requests, which reduce the amount of time required for some functions, such as I/O interrupts and z/OS dispatch operations. 
     Standard I/O processing that is available using technologies, such as zHPF, requires I/O operations to perform a series of time-consuming tasks, such as z/OS dispatching, interrupt handling, CPU queuing, and L1/L2 processor cache reloading. These tasks and others required for I/O processing may cause I/O response times to be relatively long compared to transferring data within virtual storage, with response times of 130+ microseconds plus interrupt handling and CPU dispatch time. 
     Using zHyperLink or synchronous I/O generally, when a synchronous I/O operation is performed, the CPU on the host system waits or “spins” until the I/O is complete, or a timeout value is reached. zHyperLink can significantly reduce the time that is required to complete the I/O because the dispatching, interrupt handling, CPU queue time, and CPU cache reload activities are no longer necessary. This saves the processor time associated with two context swaps involved in a normal I/O operation, putting the thread to sleep and then re-dispatching it, as well as performing the I/O interrupt. 
     In order to achieve the improved I/O response times associated with synchronous I/O (e.g., zHyperLink), the code path used to process the I/O needs to be highly optimized. Any conditions that delay a synchronous I/O operation, such as a cache miss, may cause a notification to be returned to a host system and the operation to be retried using a slower communication path such as zHPF. Synchronous I/O is only successful when microcode can complete a synchronous I/O operation in a very short amount of time, such as 10-30 microseconds. If the synchronous I/O operation cannot be completed in that amount of time, it may fail and the host system may need to retry the operation over a non-optimal path such as FICON. 
     In view of the foregoing, what are needed are systems and methods to improve cache hit ratios for selected volumes when using synchronous I/O technologies such as zHyperLink. Such systems and methods will ideally reduce or prevent delays that may hinder execution of synchronous I/O operations. 
     SUMMARY 
     The invention has been developed in response to the present state of the art and, in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available systems and methods. Accordingly, systems and methods have been developed to improve cache hit ratios for selected storage elements within a storage system. The features and advantages of the invention will become more fully apparent from the following description and appended claims, or may be learned by practice of the invention as set forth hereinafter. 
     Consistent with the foregoing, a method for improving cache hit ratios for selected storage elements within a storage system is disclosed. In one embodiment, such a method includes storing, in a cache of a storage system, non-favored storage elements and favored storage elements. The favored storage elements are retained in the cache longer than the non-favored storage elements. The method maintains a first LRU list containing entries associated with non-favored storage elements and designating an order in which the non-favored storage elements are evicted from the cache, and a second LRU list containing entries associated with favored storage elements and designating an order in which the favored storage elements are evicted from the cache. The method periodically scans the first LRU list for non-favored storage elements that have changed to favored storage elements, and the second LRU list for favored storage elements that have changed to non-favored storage elements. 
     A corresponding system and computer program product are also disclosed and claimed herein. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In order that the advantages of the invention will be readily understood, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered limiting of its scope, the embodiments of the invention will be described and explained with additional specificity and detail through use of the accompanying drawings, in which: 
         FIG.  1    is a high-level block diagram showing one example of a network environment in which systems and methods in accordance with the invention may be implemented; 
         FIG.  2    is a high-level block diagram showing one example of a storage system for use in the network environment of  FIG.  1   ; 
         FIG.  3    is a high-level block diagram showing different communication paths between a host system and a storage system; 
         FIG.  4    is a high-level block diagram showing a system for improving cache hit ratios for selected volumes when using synchronous I/O; 
         FIG.  5    is a high-level block diagram showing various exemplary sub-modules within an optimization module in accordance with the invention; 
         FIG.  6    is a flow diagram showing one embodiment of a method for evicting storage elements from cache in order to free up space in the cache while providing a preference to favored storage elements; 
         FIG.  7    is a high-level block diagram showing a host system sending commands and/or lists to a storage system to designate which volumes should be treated as favored and unfavored; 
         FIG.  8    is a flow diagram showing an alternative method for evicting storage elements from cache in order to free up space in the cache while providing a preference to favored storage elements; 
         FIG.  9    is a high-level block diagram showing a host system sending a residency multiplier to a storage system to indicate how strong of a cache preference to apply to favored volumes; 
         FIG.  10    is a high-level block diagram showing a preference tuning module for tuning a cache preference for favored volumes; 
         FIG.  11    is a high-level block diagram showing a first example of a list of favored volumes and associated residency multipliers; 
         FIG.  12    is a high-level block diagram showing a second example of a list of favored volumes and associated residency multipliers; 
         FIG.  13    is a high-level block diagram showing an LRU list for each group of favored volumes that have the same residency multiplier, as well as an LRU list for non-favored volumes; 
         FIG.  14    is a flow diagram showing a method for evicting storage elements from cache using LRU lists such as those illustrated in  FIG.  13   ; 
         FIG.  15    shows reorganization of entries in a “favored” LRU list and “non-favored” LRU list in response to changes to favored and non-favored volumes; 
         FIG.  16    is a flow diagram showing a method for moving entries from a “favored” LRU list to a “non-favored” LRU list; and 
         FIG.  17    is a flow diagram showing a method for moving entries from a “non-favored” LRU list to a “favored” LRU list. 
     
    
    
     DETAILED DESCRIPTION 
     It will be readily understood that the components of the present invention, as generally described and illustrated in the Figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the invention, as represented in the Figures, is not intended to limit the scope of the invention, as claimed, but is merely representative of certain examples of presently contemplated embodiments in accordance with the invention. The presently described embodiments will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. 
     The present invention may be embodied as a system, method, and/or computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention. 
     The computer readable storage medium may be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire. 
     Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device. 
     Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. 
     The computer readable program instructions may execute entirely on a user&#39;s computer, partly on a user&#39;s computer, as a stand-alone software package, partly on a user&#39;s computer and partly on a remote computer, or entirely on a remote computer or server. In the latter scenario, a remote computer may be connected to a user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention. 
     Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, may be implemented by computer readable program instructions. 
     These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus, or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     Referring to  FIG.  1   , one example of a network environment  100  is illustrated. The network environment  100  is presented to show one example of an environment where systems and methods in accordance with the invention may be implemented. The network environment  100  is presented by way of example and not limitation. Indeed, the systems and methods disclosed herein may be applicable to a wide variety of different network environments, in addition to the network environment  100  shown. 
     As shown, the network environment  100  includes one or more computers  102 ,  106  interconnected by a network  104 . The network  104  may include, for example, a local-area-network (LAN)  104 , a wide-area-network (WAN)  104 , the Internet  104 , an intranet  104 , or the like. In certain embodiments, the computers  102 ,  106  may include both client computers  102  and server computers  106  (also referred to herein as “host systems”  106 ). In general, the client computers  102  initiate communication sessions, whereas the server computers  106  wait for requests from the client computers  102 . In certain embodiments, the computers  102  and/or servers  106  may connect to one or more internal or external direct-attached storage systems  110   a  (e.g., arrays of hard-disk drives, solid-state drives, tape drives, etc.). These computers  102 ,  106  and direct-attached storage systems  110   a  may communicate using protocols such as ATA, SATA, SCSI, SAS, Fibre Channel, or the like. 
     The network environment  100  may, in certain embodiments, include a storage network  108  behind the servers  106 , such as a storage-area-network (SAN)  108  or a LAN  108  (e.g., when using network-attached storage). This network  108  may connect the servers  106  to one or more storage systems, such as arrays  110   b  of hard-disk drives or solid-state drives, tape libraries  110   c , individual hard-disk drives  110   d  or solid-state drives  110   d , tape drives  110   e , CD-ROM libraries, or the like. To access a storage system  110 , a host system  106  may communicate over physical connections from one or more ports on the host  106  to one or more ports on the storage system  110 . A connection may be through a switch, fabric, direct connection, or the like. In certain embodiments, the servers  106  and storage systems  110  may communicate using a networking standard such as Fibre Channel (FC). 
     Referring to  FIG.  2   , one embodiment of a storage system  110  containing an array of hard-disk drives  204  and/or solid-state drives  204  is illustrated. As shown, the storage system  110  includes a storage controller  200 , one or more switches  202 , and one or more storage drives  204 , such as hard disk drives  204  or solid-state drives  204  (such as flash-memory-based drives  204 ). The storage controller  200  may enable one or more hosts  106  (e.g., open system and/or mainframe servers  106  running operating systems such z/OS, zVM, or the like) to access data in the one or more storage drives  204 . 
     In selected embodiments, the storage controller  200  includes one or more servers  206 . The storage controller  200  may also include host adapters  208  and device adapters  210  to connect the storage controller  200  to host devices  106  and storage drives  204 , respectively. Multiple servers  206   a ,  206   b  may provide redundancy to ensure that data is always available to connected hosts  106 . Thus, when one server  206   a  fails, the other server  206   b  may pick up the I/O load of the failed server  206   a  to ensure that I/O is able to continue between the hosts  106  and the storage drives  204 . This process may be referred to as a “failover.” 
     In selected embodiments, each server  206  may include one or more processors  212  and memory  214 . The memory  214  may include volatile memory (e.g., RAM) as well as non-volatile memory (e.g., ROM, EPROM, EEPROM, hard disks, flash memory, etc.). The volatile and non-volatile memory may, in certain embodiments, store software modules that run on the processor(s)  212  and are used to access data in the storage drives  204 . These software modules may manage all read and write requests to logical volumes in the storage drives  204 . 
     In selected embodiments, the memory  214  includes a cache  218 , such as a DRAM cache  218 . Whenever a host  106  (e.g., an open system or mainframe server  106 ) performs a read operation, the server  206  that performs the read may fetch data from the storages drives  204  and save it in its cache  218  in the event it is required again. If the data is requested again by a host  106 , the server  206  may fetch the data from the cache  218  instead of fetching it from the storage drives  204 , saving both time and resources. Similarly, when a host  106  performs a write, the server  106  that receives the write request may store the write in its cache  218 , and destage the write to the storage drives  204  at a later time. When a write is stored in cache  218 , the write may also be stored in non-volatile storage (NVS)  220  of the opposite server  206  so that the write can be recovered by the opposite server  206  in the event the first server  206  fails. In certain embodiments, the NVS  220  is implemented as battery-backed memory in the opposite server  206 . 
     One example of a storage system  110  having an architecture similar to that illustrated in  FIG.  2    is the IBM DS8000™ enterprise storage system. The DS8000™ is a high-performance, high-capacity storage controller providing disk storage that is designed to support continuous operations. Nevertheless, the systems and methods disclosed herein are not limited to operation with the IBM DS8000™ enterprise storage system  110 , but may operate with any comparable or analogous storage system  110 , regardless of the manufacturer, product name, or components or component names associated with the system  110 . Furthermore, any storage system that could benefit from one or more embodiments of the invention is deemed to fall within the scope of the invention. Thus, the IBM DS8000™ is presented by way of example and is not intended to be limiting. 
     Referring to  FIG.  3   , when an I/O request is performed by an application residing on a host system  106 , several processes may be performed to complete the request. These processes may affect I/O latency and application response time. zHyperLink is a technology designed to reduce I/O latency by providing a fast, reliable, and direct communication path  300  between a host system and storage system  110 . This may be accomplished by installing zHyperLink adapters on the host system  106  and storage system  110 , and connecting the components using zHyperLink cables. This configuration creates a point-to-point connection  300  between the host system  106  and the storage system controller  200 . This technology may reduce I/O response times by up to ten times compared to using a conventional communication path  302 , such as a z High-Performance FICON® (zHPF) communication path  302 . Such low response times may be achieved by using synchronous I/O requests, which reduce the amount of time required for some functions, such as I/O interrupts and I/O dispatch operations. 
     Standard I/O processing that is available using technologies, such as zHPF, requires I/O operations to perform a series of time-consuming tasks, such as z/OS dispatching, interrupt handling, CPU queueing, and L1/L2 processor cache reloading. These tasks and others required for I/O processing may cause I/O response times to be relatively long compared to transferring data within virtual storage, with response times of 130+ microseconds plus interrupt handling and CPU dispatch time. 
     Using zHyperLink, when a synchronous I/O is performed over the higher performance communication path  300 , the CPU on the host system  106  may wait or “spin” until the I/O is complete, or a timeout value is reached. zHyperLink can significantly reduce the time that is required to complete the I/O because the dispatching, interrupt handling, CPU queue time, and CPU cache reload activities are no longer necessary. This reduces processor time needed to perform two context swaps in a normal I/O operation, putting the thread to sleep and then re-dispatching it, as well as performing the I/O interrupt. 
     In order to achieve the improved I/O response times associated with synchronous I/O, the code path used to process the I/O needs to be highly optimized. Any conditions that delay a synchronous I/O operation, such as a cache miss, may cause a notification to be returned to a host system  106  and the operation to be retried over a slower communication path  302 , such as zHPF. Synchronous I/O over the higher performance communication path  300  is typically only successful when microcode can complete a synchronous I/O operation in a very short amount of time, such as 10-30 microseconds. If a synchronous I/O operation cannot be completed in that amount of time, the synchronous I/O operation may be failed and the host system  106  may need to retry the operation over a non-optimal path  302  such as FICON. 
     Referring to  FIG.  4   , while continuing to refer generally to  FIG.  3   , in order to perform synchronous I/O to data stored in volumes  304  of the storage system  110 , the requested data is ideally contained in cache  218 . A cache miss may cause the synchronous I/O operation to fail and be retried over a slower communication path  302 , such as zHPF. In order to improve cache hit ratios for data that is accessed using synchronous I/O, in certain embodiments, volumes  304  on a storage system  110  may be divided into favored volumes  304   a  and non-favored volumes  304   b . Favored volumes  304   a  may be those volumes  304  that are preferably accessed using synchronous I/O. These may be volumes  304  that are deemed more important or critical, or contain data where performance is important or critical (e.g., directories, etc.) Non-favored volumes  304   b , by contrast, may be any volumes  304  that are not designated as favored volumes  304   a.    
     As shown in  FIG.  4   , the volumes  304  may be made up of storage elements  402 , such as tracks. Storage elements  402  from favored volumes  304   a  may be designated as favored storage elements  402   a , whereas storage elements  402  from non-favored volumes  304   b  may be designated as non-favored storage elements  402   b . At any given time, a cache  218  of the storage system  110  may store a first set  404   b  of non-favored storage elements  402   b  and a second set  404   a  of favored storage elements  402   a  from the non-favored volumes  304   b  and favored volumes  304   a  respectively. Because the favored volumes  304   a  are those volumes  304  where use of synchronous I/O is preferred, the favored storage elements  402   a  may be preferred in cache  218  over the non-favored storage elements  402   b . This will ideally increase cache hit ratios for the favored storage elements  402   a , thereby optimizing synchronous I/O and increasing the percentage of synchronous I/O operations that complete successfully. 
     In order to provide preferred treatment of favored storage elements  402   a  over non-favored storage elements  402   b  in the cache  218 , an optimization module  400  may be provided. Among other things, the optimization module  400  may provide functionality to designate which volumes  304  are favored and non-favored, as well as implement a cache eviction policy wherein favored storage elements  402   a  reside in cache  218  longer than non-favored storage elements  402   b . The optimization module  400  and its functionality will be discussed in more detail in association with  FIG.  5   . 
     Referring to  FIG.  5   , a high-level block diagram showing the optimization module  400  and associated sub-modules is illustrated. The optimization module  400  and associated sub-modules may be implemented in hardware, software, firmware, or combinations thereof. The optimization module  400  and associated sub-modules are presented by way of example and not limitation. More or fewer sub-modules may be provided in different embodiments. For example, the functionality of some sub-modules may be combined into a single or smaller number of sub-modules, or the functionality of a single sub-module may be distributed across several sub-modules. Although the optimization module  400  and associated sub-modules are shown within the storage system  110 , all functionality is not necessarily implemented within the storage system  110  nor is it limited to implementation within the storage system  110 . Thus, the location of the optimization module  400  and associated sub-modules is provided by way of example and not limitation. 
     As shown, the optimization module  400  includes one or more of an establishment module  500 , adjustment module  502 , life expectancy determination module  504 , residency determination module  506 , and cache eviction module  508 . The establishment module  500  may be configured to designate favored volumes  304   a  and non-favored volumes  304   b  as previously discussed. In certain embodiments, the host system  106  communicates these designations to the storage system  110 . In certain embodiments, the favored/non-favored volumes  304  are established using an online command or a configuration list. In other embodiments, functionality may be built into the host system  106  to determine which volumes  304  to favor/non-favor. For example, the host system  106  may observe I/O patterns and may determine that certain volumes  304  should be or are preferably accessed using the faster synchronous I/O process. The host system  106  may add these volumes  304  to the set of favored volumes  304   a.    
     The adjustment module  502  may adjust which volumes  304  are favored/non-favored. For example, as time passes, access patterns or data importance may change on the volumes  304 . The adjustment module  502  may, in certain embodiments, adjust which volumes  304  are considered favored/non-favored as these access patterns or data importance change. Alternatively, the adjustment module  502  may enable a user to manually adjust the volumes  304  that are considered favored or non-favored. In certain embodiments, as will be explained in more detail in association with  FIG.  7   , the host system  102  periodically sends commands and/or lists to the storage system  110  to change or update which volumes  304  are considered favored or non-favored. 
     The life expectancy determination module  504  may be configured to determine the life expectancy (i.e., residency time) of storage elements (e.g., tracks) in cache  218 . For example, in certain embodiments, the life expectancy determination module  504  is configured to determine the amount of time non-favored storage elements  402   b  will reside cache  218  prior to being evicted. This life expectancy may be a number at some point in time or an average over a period of time. In certain embodiments, the life expectancy is calculated by subtracting a timestamp of a least recently used non-favored storage element  402   b  in the cache  218 , from a timestamp of a most recently used non-favored storage element  402   b  in the cache  218 , where the timestamps indicate when the non-favored storage elements  402   b  were most recently accessed. 
     The residency determination module  506 , by contrast, may determine how long a particular storage element has resided in cache  218 . The residency time may be calculated, for example, by subtracting the timestamp of a storage element  402  (which indicates the time the storage element  402  was most recently accessed) from the current time. 
     Using the life expectancy calculated by the life expectancy determination module  504  and the residency time calculated by the residency determination module  506 , the cache eviction module  508  may execute a cache eviction policy such that favored storage elements  402   a  are maintained in cache  218  longer than the life expectancy of the non-favored storage elements  402   b . For example, the cache eviction policy may require that favored storage elements  402   a  are maintained in cache  218  for double the life expectancy of non-favored storage elements  402   b . Other multiples (i.e., numbers, decimals, or fractions that are greater than one) are possible and within the scope of the invention. One example of a method  600  that may be executed by the cache eviction module  508  is described in association with  FIG.  6   . 
       FIG.  6    shows one embodiment of a method  600  for evicting entries from cache  218  in order to free up space in the cache  218 . The method  600  references the first set  404   b  of non-favored storage elements  402   b  and the second set  404   a  of favored storage elements  402   a  previously described in association with  FIG.  4   . In certain embodiments, the first set  404   b  of non-favored storage elements  402   b  is documented in a first LRU (least recently used) list (i.e., a “non-favored” LRU list), and the second set  404   a  of favored storage elements  402   a  is documented in a second LRU list (i.e., a “favored” LRU list). 
     As shown, the method  600  initially determines  602  whether it is time to evict one or more storage elements  402  from cache  218 . This step  602  may, in certain embodiments, involve determining whether the cache  218  is low on free space. If it is time to evict entries from cache  218 , the method  600  determines  604  whether the “favored” LRU list is empty. If so, the method  600  evicts  606 , from cache  218 , the oldest non-favored storage element  402   b  (i.e., the non-favored storage element  402   b  with the oldest timestamp) listed in the “non-favored” LRU list. If the “favored” LRU list is not empty, the method  600  determines  608  whether the “non-favored” LRU list is empty. If so, the method  600  evicts  610 , from cache  218 , the oldest favored storage element  402   a  listed in the “favored” LRU list. 
     If neither the “non-favored” LRU list nor the “favored” LRU list is empty, method  600  determines  612  whether the oldest non-favored storage element  402   b  in the “non-favored” LRU list has an older timestamp than the oldest favored storage element  402   a  in the “favored” LRU list. If so, the method  600  evicts  614 , from cache  218 , the oldest non-favored storage element  402   b  in the “non-favored” LRU list. If not, the method  600  proceeds to step  616 . At step  616 , the method  600  determines  616  whether the residency time of an oldest favored storage element  402   a  in the cache  218  (i.e., the amount of time that the oldest favored storage element  402   a  in the “favored” LRU list has resided in the cache  218 ) is less than the multiple N multiplied by the life expectancy of non-favored storage elements  402   b  in the cache  218 . If so, the method  600  evicts  618 , from cache  218 , the oldest non-favored storage element  402   b  in the “non-favored” LRU list. By contrast, if the residency time for an oldest favored storage element  402   a  in the “favored” LRU list is more than N*(the life expectancy of non-favored storage elements  402   b  in the cache  218 ), the method  600  evicts  620 , from cache  218 , the oldest favored storage element  402   a  in the “favored” LRU list. The variable N is a residency multiplier, details of which will be explained in more detail hereafter. 
     Referring to  FIG.  7   , as previously mentioned, a host system  102  may periodically send commands and/or lists to the storage system  110  to change or update which volumes  304  are considered favored or non-favored, and thus which storage elements  402  are given a cache preference. In certain embodiments, the host system  102  periodically sends a command to the storage system  110  with a list  700  of volumes  304  that should be favored. This list  700  of volumes  304  may change each time the host system  102  issues a command to the storage system  110 . If a volume  304  was previously designated in the list  700  as favored but is not designated as such in a new list  700 , the storage system  110  may change the status of the volume  304  to unfavored and cease to provide a cache preference to the volume  304 . 
     In certain embodiments, the host system  102  may set an indicator (e.g., a “FORCE FAVORED CACHE” indicator) for a particular volume  304  that indicates that the volume  304  is to retain its favored status until the host system  102  affirmatively changes the volume status to unfavored. The host system  102  may use a “REMOVE FAVORED CACHE” command to change the status of a volume  304  from favored to unfavored. In certain embodiments, the “FORCE FAVORED CACHE” indicator may have a duration attached to it that indicates how long the volume  304  should have favored status before it returns to unfavored status. After the duration expires and the volume  304  is no longer contained in the list  700 , the status of the volume  304  may be automatically changed to unfavored so that it does not receive a cache preference. 
     Referring to  FIG.  8   , because volumes  304  may be dynamically changed from favored to unfavored status and vice versa, various modification may be made to the method  600  of  FIG.  6    to account for that fact that a volume&#39;s status may have changed. This status change may warrant moving storage elements  402  from the “non-favored” LRU list to the “favored” LRU list or vice versa. 
       FIG.  8    shows one embodiment of method  800  for evicting entries (i.e., storage elements  402 ) from cache  218  in order to free up space in the cache  218 . This method  800  is similar to the method  600  illustrated in  FIG.  6    except that the method  800  has been modified to account for volumes  304  that may have changed from favored to unfavored status and vice versa. The steps of the method  800  that are the same as the method  600  of  FIG.  6    are shown with the same numbering, while new steps (i.e., steps  802 ,  804 , and  806 ) have been assigned new numbering. The flow of the method  800  compared to the method  600  of  FIG.  6    has also been altered somewhat to account for the new steps  802 ,  804 , and  806 . 
     As shown in  FIG.  8   , after determining  608  whether the “non-favored” LRU list is empty, the method  800  may determine  802  whether the oldest entry of the “favored” LRU list is no longer favored. In other words, the method  800  may determine  802  whether the status of the oldest entry (i.e., storage element  402 ) in the “favored” LRU list was changed from favored to unfavored. If so, the method  800  evicts  610 , from cache  218 , the oldest entry in the “favored” LRU list. 
     Similarly, after the decision step  616  has been performed, the method  800  determines  806  whether the oldest entry in the “non-favored” LRU list is now favored. In other words, the method  800  determines  806  whether the status of the oldest entry (i.e., storage element  402 ) in the “non-favored” LRU list was changed from unfavored to favored. If so, the method  800  moves  804  the entry from the “non-favored” LRU list to the most recently used end of the “favored” LRU list and the method  800  returns to step  612 . If not, the method  800  evicts  618 , from cache  218 , the oldest entry in the “non-favored” LRU list. 
     Referring to  FIG.  9   , as previously mentioned, a host system  102  may periodically send a command to a storage system  110  that includes a list  700  of which volumes  304  should be favored. In certain embodiments, the host system  102  may include, with the list  700 , a residency multiplier  902  that indicates how strong a cache preference to apply to the favored volumes  304   a . The higher the residency multiplier  902 , the stronger the cache preference and thus the longer favored volumes  304   a  will be retained in cache  218  relative to non-favored volumes  304   b . The lower the residency multiplier  902 , the weaker the cache preference and thus the shorter favored volumes  304   a  will be retained in cache  218  relative to non-favored volumes  304   b . In certain embodiments, a single residency multiplier  902  is provided for all favored volumes  304   a  in the list  700 . In other embodiments, different residency multipliers  902  are provided for different favored volumes  304   a , as will be explained in more detail in association with  FIGS.  10  and  11   . 
     A preference tuning module  900  may be provided on the host system  102  or another system to determine which volumes  304  should be treated as favored volumes  304   a , as well as determine the residency multiplier(s)  902  for each of the favored volumes  304   a . In general, the preference tuning module  900  may track I/O to the volumes  304  on the storage system  110  and, based on this tracking information, determine which volumes  304  should be treated as favored. Using the tracking information, the preference tuning module  900  may also determine how strong the cache preference should be for the favored volumes  304   a  individually or as a whole. 
     Referring to  FIG.  10   , a high-level block diagram showing the preference tuning module  900  and associated sub-modules is illustrated. The preference tuning module  900  and associated sub-modules may be implemented in hardware, software, firmware, or combinations thereof. The preference tuning module  900  and associated sub-modules are presented by way of example and not limitation. More or fewer sub-modules may be provided in different embodiments. For example, the functionality of some sub-modules may be combined into a single or smaller number of sub-modules, or the functionality of a single sub-module may be distributed across several sub-modules. Although the preference tuning module  900  and associated sub-modules are shown within the host system  102 , all functionality is not necessarily implemented within the host system  102  nor is it limited to implementation within the host system  102 . Thus, the location of the preference tuning module  900  and associated sub-modules is provided by way of example and not limitation. 
     As shown, the preference tuning module  900  includes one or more of an I/O tracking module  1000 , volume ranking module  1010 , list creation module  1012 , residency time determination module  1014 , multiplier calculation module  1016 , and transmission module  1018 . 
     The I/O tracking module  1000  may be configured track I/O that is issued from a host system  102  to a storage system  110 . This I/O may indicate which volumes  304  should be favored and accessed via a faster synchronous I/O process. For example, a higher amount of I/O to a volume  304  may indicate that a job is running against the volume  304  and the job could be executed faster and more efficiently using synchronous I/O. In such a scenario, the volume  304  may be granted a cache preference in order to retain more of its data in cache  218  for a longer amount of time, thereby ensuring a higher cache hit ratio when accessing the volume  304 . 
     When tracking I/O to a volume  304 , the I/O tracking module  1000  may differentiate between different types of I/O. For example, the I/O tracking module  1000  may track reads  1002  inside transactions, writes  1004  inside transactions, reads  1006  outside transactions, and writes  1008  outside transactions. In certain embodiments, the I/O tracking module  1000  may utilize counters to track an amount of each of these different types of I/O against a volume  304 . 
     Using the information gathered by the I/O tracking module  1000 , the volume ranking module  1010  may rank volumes  304  on the storage system  110 . For example, the volume ranking module  1010  may rank each volume  304  using the formula A*L+B*M+C*P+D*Q, where A is a number of accesses to a volume  304  for reads inside transactions, B is a number of accesses to the volume  304  for writes inside transactions, C is a number of accesses to the volume  304  for reads outside transactions, and D is a number of accesses to the volume  304  for writes outside transactions. L, M, P, and Q are weight coefficients (e.g., L=4, M=3, P=2, Q=1), where L&gt;M&gt;P&gt;Q. In other words, accesses to volumes  304  inside transactions may be weighted more heavily than accesses to volumes  304  outside transactions for the purpose of establishing a cache preference. Also, reads to volumes  304  may be weighted more heavily than writes to volumes  304  for the purpose of establishing a cache preference. 
     Using the output of the above-described calculation for each volume  304 , the volume ranking module  1010  may rank volumes  304  on the storage system  110  by the magnitude of their output value. Volumes  304  with greater amounts of I/O may, in general, have a larger output value and thus be ranked higher than volumes  304  with lesser amounts of I/O within the same time period. The list creation module  1012  may then create a list  700  of volumes  304  that should be favored and provided a cache preference. This may be a certain number of the most highly ranked volumes  304 , volumes  304  with an output value above a certain threshold, or the like. 
     The residency time determination module  1014  may determine the residency time (i.e., life expectancy) of storage elements  402  of non-favored volumes  304   b  within the cache  218 . The multiplier calculation module  1016  may then determine a residency multiplier  902  for favored volumes  304   a . For example, if storage elements  402  of favored volumes  304   a  are to reside in cache  218  for twice the amount of time as storage elements  402  of non-favored volumes  304   b , the residency multiplier  902  may be set at two. In certain embodiments, the residency multiplier  902  is determined by taking the above-described output value from a favored volume  304   a  and dividing it by the output value from a non-favored volume  304   b  to yield a ratio. If desired, a floor may be set for the residency multiplier  902  such that it does not fall below a certain value (e.g., two), regardless of the ratio. This will ensure that the storage elements  402  of favored volumes  304   a  are retained in cache  218  for at least twice the amount of time as the storage elements  402  of non-favored volumes  304   b.    
     Once the list  700  has been created and the residency multiplier  902  has been determined, the transmission module  1018  may transmit the list  700  and residency multiplier  902  from the host system  102  to the storage system  110 . As previously explained, in certain embodiments, a single residency multiplier  902  may be calculated for all favored volumes  304   a  in the list  700 . In other embodiments, a different residency multiplier  902  (N) may be calculated for each favored volume  304   a  in the list  700 , as shown in  FIG.  11   . As illustrated in  FIG.  11   , the list  700  documents volumes  304  that are to be favored in order of ranking (i.e., in order of their output values using the above-described calculation). Each favored volume  304   a  has a different residency multiplier  902  associated therewith. The higher rank of the volume  304 , the larger residency multiplier  902 . As previously mentioned, the residency multiplier  902  may be multiplied by the life expectancy of storage elements  402  of non-favored volumes  304   b  to determine the amount of time storage elements  402  of favored volumes  304   a  should be retained in cache  218 . 
     Referring to  FIG.  12   , in certain embodiments, favored volumes  304   a  in the list  700  may share the same residency multiplier  902  and thus have the same preferred cache residency time. For example, a first set of favored volumes  304   a  (i.e., Volumes A, B, and C) may be assigned a first residency multiplier N 1 , a second set of favored volumes  304   a  (i.e., Volumes D and E) may be assigned a second residency multiplier N 2 , and a third set of favored volumes  304   a  (i.e., Volumes F and G) may be assigned a third residency multiplier N 3 , where N 1 &gt;N 2 &gt;N 3 . Each residency multiplier  902  indicates how strong the cache preference (i.e., preferred cache residency time) should be for its respective group of favored volumes  304   a . In certain embodiments, in a storage system  110  such as the IBM DS8000™ enterprise storage system  110 , the residency multiplier  902  for each volume  304  is stored in a global status area (e.g., an area in cache  218  that is mirrored to more persistent storage drives  204 ) so that the residency multiplier  902  is not lost across reboots, power loss, failures, or the like. 
     Referring to  FIG.  13   , in certain embodiments, an LRU list  1300  is created for each residency multiplier  902  and associated group of favored volumes  304   a . An LRU list  1300   d  may also be created for all non-favored volumes  304   b  (i.e., volumes  304  without a residency multiplier  902  or with a residency multiplier  902  of one). When an unmodified storage element  402  (e.g., an unmodified track) is added to the cache  218 , the volume  304  associated with the storage element  402  may be checked to determine if it is a favored volume  304   a  and, if so, what the residency multiplier  902  is for the volume  304 . Based on the residency multiplier  902  (or lack thereof) for the volume  304 , an entry associated with the unmodified storage element  402  may be added to the most recently used (MRU) end of appropriate LRU list  1300 . In the event an LRU list  1300  does not exist for the residency multiplier  902  associated with the volume  304 , an LRU list  1300  may be created for the residency multiplier  902  and an entry associated with the unmodified storage element  402  may be added to the newly created LRU list  1300 . 
       FIG.  14    shows a method  1400  for evicting storage elements from cache  218  using LRU lists  1300  such as those illustrated in  FIG.  13   . As shown, the method  1400  initially determines  1402  whether it is time to evict one or more storage elements  402  from the cache  218 . This step  1402  may, in certain embodiments, involve determining whether the cache  218  is low on free space. If it is time to evict entries from cache  218  (e.g., the cache  218  is low on free space), the method  1400  determines  1404  whether the LRU lists  1300  associated with favored volumes  304   a  (hereinafter referred to as “favored” LRU lists  1300 ) are all empty. If so, the method  1400  evicts  1406 , from cache  218 , the storage element  402  associated with the oldest entry (i.e., the entry on the LRU end of the LRU list) in the LRU list  1300  for non-favored volumes  304   b  (hereinafter referred to as the “non-favored” LRU list  1300 ). 
     If, on the other hand, the “favored” LRU lists  1300  are not all empty, the method  1400  computes  1410  a “time above required residency time” for non-empty “favored” LRU lists  1300 . In certain embodiments, the “time above required residency time” may be calculated by determining the residency time of the oldest entry in the “favored” LRU list  1300  and subtracting, from this value, the “life expectancy” multiplied by the residency multiplier  902 . As previously explained, the “life expectancy” may be equivalent to the amount of time non-favored storage elements  402   b  will reside cache  218  prior to being evicted. In general, the step  1410  determines the amount by which an oldest entry in the “favored” LRU list  1300  has exceeded (or fallen short of) its preferred residency time in cache  218 . 
     The method  1400  then picks  1412  the “favored” LRU list  1300  where the “time above required residency time” for the oldest entry is the largest. The method  1400  then determines  1414  whether this “time above required residency time” is negative (meaning that the storage element associated with the oldest entry in the “favored” LRU list  1300  has resided in cache  218  for some amount of time less than its preferred residency time). If the “time above required residency time” is negative, the method  1400  determines  1416  whether the “non-favored” LRU list  1300  is empty. If it is not empty, the method  1400  evicts  1406 , from cache  218 , the storage element  402  associated with the oldest entry in the “non-favored” LRU list  1300 . 
     If, at step  1414 , the “time above required residency time” is not negative (meaning that the oldest entry in the “favored” LRU list  1300  has resided in cache  218  for some amount of time greater than or equal to its preferred residency time), the method  1400  evicts  1408 , from cache  218 , the storage element associated with the oldest entry in the “favored” LRU list  1300  with the greatest “time above required residency time.” Similarly, if the “non-favored” LRU list  1300  is found to be empty at step  1416 , the method  1400  also evicts  1408 , from cache  218 , the oldest entry in the “favored” LRU list  1300  with the greatest “time above required residency time.” 
     Referring to  FIG.  15   , in certain cases, such as in cases where a cache  218  is very large, the LRU lists  1300  associated with favored and unfavored volumes  304  may be periodically scanned and reorganized when the status of certain volumes  304  changes (i.e., when favored volumes  304   a  are changed to non-favored volumes  304   b  and vice versa). More specifically, the “favored” LRU list  1300   e  may be scanned for entries that are now associated with non-favored volumes  304   b  and the “non-favored” LRU list  1300   f  may be scanned for entries that are now associated with favored volumes  304   a . Any entries in the “favored” LRU list  1300   e  that are associated with non-favored volumes  304   b  may be moved from the “favored” LRU list  1300   e  to the “non-favored” LRU list  1300   f . One example of a method  1600  to accomplish this is illustrated in  FIG.  16   . Similarly, any entries in the “non-favored” LRU list  1300   f  that are associated with favored volumes  304   a  may be moved from the “non-favored” LRU list  1300   f  to the “favored” LRU list  1300   e . One example of a method  1700  to accomplish this is illustrated in  FIG.  17   . 
     Referring to  FIG.  16   , while continuing to refer generally to  FIG.  15   , one embodiment of a method  1600  for moving entries from a “favored” LRU list  1300   e  to a “non-favored” LRU list  1300   f  list is illustrated. Such a method  1600  may be executed when the list  700  of favored volumes  304   a  and/or non-favored volumes  304   b  changes, for example. As shown, the method  1600  initially inspects  1602  a first storage element (e.g., track) in the “favored” LRU list  1300   e . If, at step  1604 , the storage element is still favored (i.e., the storage element is associated with a volume  304  that is still favored), the method  1600  proceeds to the next storage element in the “favored” LRU list  1300   e , if there are any remaining, by way of steps  1618 ,  1602 . 
     If, on the other hand, the storage element is not still favored (meaning that the volume  304  that is associated with the storage element changed status from favored to non-favored), the method  1600  compares  1606  a timestamp associated with the storage element (indicating when the storage element was last accessed) to a timestamp associated with an entry at the LRU end  1502   b  of the “non-favored” LRU list  1300   f . If, at step  1608 , the timestamp associated with the storage element is older than the timestamp of the entry at the LRU end  1502   b  of the “non-favored” LRU list  1300   f  (meaning that the storage element was accessed less recently than the storage element referenced at the LRU end  1502   b ), the method  1600  moves  1610  the storage element to the LRU end  1502   b  of the “non-favored” LRU list  1300   f.    
     If, on the other hand, the storage element is not older than the storage element referenced at the LRU end  1502   b  of the “non-favored” LRU list  1300   f , the method  1600  determines  1612  whether the timestamp of the storage element is younger than a storage element referenced at the MRU end  1500   b  of the “non-favored” LRU list  1300   f . In other words, the method  1600  determines  1612  if the storage element was accessed more recently than the storage element referenced at the MRU end  1500   b  of the “non-favored” LRU list  1300   f . If so, the method  1600  moves  1614  the entry associated with the storage element from the “favored” LRU list  1300   e  to the MRU end  1500   b  of the “non-favored” LRU list  1300   f.    
     If the storage element referenced in the “favored” LRU list  1300   e  does not satisfy either of the conditions  1608 ,  1612 , then the timestamp associated with the storage element is somewhere between the timestamp associated with the LRU end  1502   b  of the “non-favored” LRU list  1300   f  and the timestamp associated with MRU end  1500   b  of the “non-favored” LRU list  1300   f . In such a case, the method  1600  moves  1616  the storage element to the temporally closest of the LRU end  1502   b  and the MRU end  1500   b . That is, if the timestamp associated with the storage element is temporally closer to the timestamp associated with the LRU end  1502   b  of the “non-favored” LRU list  1300   f , the method  1600  moves  1616  the storage element to the LRU end  1502   b  of the “non-favored” LRU list  1300   f . By contrast, if the timestamp associated with the storage element is temporally closer to the timestamp associated with the MRU end  1500   b  of the “non-favored” LRU list  1300   f , the method  1600  moves  1616  the storage element to the MRU end  1500   b  of the “non-favored” LRU list  1300   f.    
     At step  1618 , the method  1600  is repeated for each storage element in the “favored” LRU list  1300   e  to determine which storage elements are now “non-favored” and need to be moved to the “non-favored” LRU list  1300   f . The method  1600  illustrated in  FIG.  16    assumes that the LRU end  1502   b  and the MRU end  1500   b  are the only two insertion points for adding entries to the “non-favored” LRU list  1300   f . If more insertion points  1504   b  are available between the LRU end  1502   b  and the MRU end  1500   b , the method  1600  may be modified to move the storage element to the insertion point of the “non-favored” LRU list  1300   f  to which the storage element&#39;s timestamp is temporally closest. 
     Referring to  FIG.  17   , while also continuing to refer generally to  FIG.  15   , one embodiment of a method  1700  for scanning and reorganizing a “non-favored” LRU list  1300   f  is illustrated. Such a method  1700  may be executed when the list  700  of favored volumes  304   a  and/or non-favored volumes  304   b  changes. As shown, the method  1700  initially inspects  1702  the first storage element (e.g., track) in the “non-favored” LRU list  1300   f . If, at step  1704 , the storage element is still non-favored (i.e., meaning that the storage element is associated with a volume  304  that is still non-favored), the method  1700  proceeds to the next storage element in the “non-favored” LRU list  1300   f  by way of steps  1718 ,  1702 . 
     If, on the other hand, the storage element is not still non-favored (meaning that the volume  304  that is associated with the storage element changed status from non-favored to favored), the method  1700  compares  1706  a timestamp associated with the storage element (indicating when the storage element was last accessed) to a timestamp associated with an entry at the LRU end  1502   a  of the “favored” LRU list  1300   e . If, at step  1708 , the timestamp associated with the storage element is older than the timestamp of the entry at the LRU end  1502   a  of the “favored” LRU list  1300   e  (meaning that the storage element was accessed less recently than the storage element referenced at the LRU end  1502   a  of the “favored” LRU list  1300   e ), the method  1700  moves  1710  the storage element to the LRU end  1502   a  of the “favored” LRU list  1300   e.    
     If, on the other hand, the storage element is not older than the storage element referenced at the LRU end  1502   a  of the “favored” LRU list  1300   e , the method  1700  determines  1712  whether the timestamp of the storage element is younger than a storage element referenced at the MRU end  1500   a  of the “favored” LRU list  1300   e . In other words, the method  1700  determines  1712  if the storage element was accessed more recently than the storage element referenced at the MRU end  1500   a  of the “favored” LRU list  1300   e . If so, the method  1700  moves  1714  the entry associated with the storage element from the “non-favored” LRU list  1300   f  to the MRU end  1500   a  of the “favored” LRU list  1300   e.    
     If the storage element referenced in the “non-favored” LRU list  1300   f  does not satisfy either of the conditions  1708 ,  1712 , then the timestamp associated with the storage element is somewhere between the timestamp associated with the LRU end  1502   a  of the “favored” LRU list  1300   e  and the timestamp associated with MRU end  1500   a  of the “favored” LRU list  1300   e . In such a case, the method  1700  moves  1716  the storage element to one of the LRU end  1502   a  and the MRU end  1500   a  of the “favored” LRU list  1300   e  depending on which end is temporally closest. That is, if the timestamp associated with the storage element is temporally closer to the timestamp associated with the LRU end  1502   a  of the “favored” LRU list  1300   e , the method  1700  moves  1716  the storage element to the LRU end  1502   a  of the “favored” LRU list  1300   e . If, on the other hand, the timestamp associated with the storage element is temporally closer to the timestamp associated with the MRU end  1500   a  of the “favored” LRU list  1300   e , the method  1700  moves  1716  the storage element to the MRU end  1500   a  of the “favored” LRU list  1300   e.    
     At step  1718 , the method  1700  is repeated for each storage element in the “non-favored” LRU list  1300   f  to determine which storage elements are now “favored” and need to be moved to the “favored” LRU list  1300   e . The method  1700  illustrated in  FIG.  17    assumes that the LRU end  1502   a  and the MRU end  1500   a  are the only two insertion points for adding entries to the “favored” LRU list  1300   e . If more insertion points  1504   a  are available between the LRU end  1502   a  and the MRU end  1500   a , the method  1700  may be modified to move the storage element to the insertion point of the “favored” LRU list  1300   e  to which the storage element&#39;s timestamp is temporally closest. 
     The flowcharts and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowcharts or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the Figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. Other implementations may not require all of the disclosed steps to achieve the desired functionality. It will also be noted that each block of the block diagrams and/or flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, may be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.