Data structure for write pending

Destaging activities in a data storage system are controlled by providing a write pending list of elements, where each element is defined to store information related to a cache memory data element for which a write to storage is pending, and maintaining the write pending list so that destaging of a data element can be based on the maturity of the pending write.

BACKGROUND

The invention relates generally to destaging operations in data storage systems.

Mass storage systems typically employ a large number of storage devices, such as disk drives, that are accessible by one or more host processors or computers. Since reading and writing to disks is still a relatively slow operation, many data storage systems use a cache memory to speed up the transfer of information to/from the disks. In such systems, the host computers interact with the cache memory on all transfers to and from storage devices.

For example, if data is modified by a host computer, the modified data is written to cache memory, and later written back to disk (the latter operation often being referred to “destaging”). When the data storage system employs mirroring, the data to be destaged must be written to each mirror, however not necessarily at the same time.

Typically, a data structure is maintained to indicate which data elements in cache memory have been modified and therefore need to be written back to storage. Such data structures are sometimes referred to as “write pending data structures”. When host computers write new or modified data into the cache memory, the data structure is marked to indicate that the data elements are “write pending” data elements. When the data elements are destaged to storage by a data storage system controller, the data structure is cleared to indicate that the data elements on the storage devices now correspond to the data elements in the cache memory.

To speed up the destaging process, many data storage systems depend on using proximity data to allow destaging to store data at approximately similar locations on a disk. For example, if data writes are performed in a sequential order, which minimizes head movement, the data storage system minimizes delays introduced by head seeks.

Therefore, many data storage systems attempt to select and sort destaging disk writes to minimize seek time. The write pending data structure for indicating write-backs is often set up to allow a device controller looking to do a write-back to a device to search for localized write-backs and thus increase speed. One such write pending data structure is known as a “write tree”, where the data is arranged in a tree-like structure which is sorted by a predetermined index system, for example, cylinder number. The device controller is able to search the write tree by cylinder numbers for proximate write-backs, and thereby minimize the head movement necessary to write data to the disk volumes. As the number of logical volumes on a disk grows, however, the technique becomes much less efficient with respect to seek minimization.

Moreover, because searching the write tree in cache memory is a time-consuming operation that requires multiple accesses to find appropriate data, that is, data that is mature enough for destaging, data storage system performance tends to suffer. Using redundant logical volumes (or mirrors) only tends to make the problem more severe, since each mirror separately searches the same write tree.

SUMMARY

In one aspect of the invention, controlling destaging activities in a data storage system includes providing a write pending list of elements, where each element is defined to store information related to a cache memory data element for which a write to storage is pending, and maintaining the write pending list to enable destaging of a data element based on the maturity of the pending write.

One or more aspects of the invention may include one or more of the following advantages. Unlike prior write tree data structures, which are geared towards finding a write pending which is physically closest to the current head location and requires multiple memory accesses, the write pending list and destaging control mechanism of the present invention instead finds the list element corresponding to the data element with the least chance of being written. This approach maximizes the write hit rate, and thus reduces the amount of destaging activity that is needed. In addition, this approach enables more educated decisions about optimal write delay.

DETAILED DESCRIPTION

Referring toFIG. 1, a data processing system10includes host computers12a,12b, . . . ,12m, connected to a data storage system14. The data storage system14receives data and commands from, and delivers data and responses to, the host computers12. The data storage system14is a mass storage system having a controller16coupled to pluralities of physical storage devices shown as disk devices18a, disk devices18b, . . . , disk devices18k. Each of the disk devices18is logically divided, in accordance with known techniques, into one or more logical volumes. The logical volumes can be mirrored on one or more other disk devices.

The controller16interconnects the host computers12and the disk devices18. The controller16can be, for example, the controller of the Symmetrix data storage system from EMC Corporation. Although described herein as a component of a data storage system, the controller16could also be a separate appliance or server. The controller16thus receives memory write commands from the various host computers over buses20a,20b, . . . ,20m, respectively, for example, connected and operated in accordance with a SCSI protocol, and delivers the data associated with those commands to the appropriate devices18a,18b, . . . ,18k, over respective connecting buses22a,22b, . . . ,22k. Buses22also operate in accordance with a SCSI protocol. Other protocols, for example, Fibre Channel, could also be used for buses20,22. The controller16also receives read requests from the host computers12over buses20, and delivers requested data to the host computers12, either from a cache memory of the controller16or, if the data is not available in cache memory, from the disk devices18.

In a typical configuration, the controller16also connects to a console PC24through a connecting bus26. The console PC24is used for maintenance and access to the controller16and can be employed to set parameters of the controller16as is well known in the art. The controller16may be connected to another, remote data storage system (not shown) by a data link28.

In operation, the host computers12a,12b, . . . ,12m, send, as required by the applications they are running, commands to the data storage system14requesting data stored in the logical volumes or providing data to be written to the logical volumes. Referring toFIG. 2, and using the EMC Symmetrix data storage system controller as an illustrative example, details of the internal architecture of the data storage system14are shown. The communications from the host computer12typically connect the host computer12to a port of one or more host directors30over the SCSI bus lines20. Each host director, in turn, connects over one or more system buses32or34to a global memory36. The global memory36is preferably a large memory through which the host director30can communicate with the disk devices18. The global memory36includes a common area38for supporting communications between the host computers12and the disk devices18, a cache memory40for storing data and control data structures, a cache index/directory41for mapping areas of the disk devices18to areas in the cache memory40, as well as various cache management data structures42, as will be described.

Also connected to the global memory36are back-end (or disk) directors44, which control the disk devices18. In the preferred embodiment, the disk directors are installed in the controller16in pairs. For simplification, only two disk directors, indicated as disk directors44aand44b, are shown. However, it will be understood that additional disk directors may be employed by the system.

Each of the disk directors44a,44bsupports four bus ports. The disk director44aconnects to two primary buses22aand22b, as well as two secondary buses22a′ and22b′. The buses are implemented as 16-bit wide SCSI buses. As indicated earlier, other bus protocols besides the SCSI protocol may be used. The two secondary buses22a′ and22b′ are added for redundancy. Connected to the primary buses22a,22b, are the plurality of disk devices (e.g., disk drive units)18aand18b, respectively. The disk director44bconnects to two primary buses22cand22d. Connected to the primary buses22c,22dare the plurality of disk devices or disk drive units18cand18d. Also connected to the primary buses22cand22dare the secondary buses22a′ and22b′. When the primary bus is active, its corresponding secondary bus in inactive, and vice versa. The secondary buses of the disk director44bhave been omitted from the figure for purposes of clarity.

Like the host directors30, the disk directors44are also connected to the global memory36via one of the system buses32,34. During a write operation, the disk directors44read data stored in the global memory36by a host director30and write that data to the logical volumes for which they are responsible. During a read operation and in response to a read command, the disk directors44read data from a logical volume and write that data to global memory for later delivery by the host director to the requesting host computer12.

As earlier mentioned, the data storage system14may be remotely coupled to another data storage system14via the data link28. The remote system may be used to mirror data residing on the data storage system14. To support such a configuration, the data storage system14can include a remote director48to connect to the data line28and handle transfers of data over that link. The remote director48communicates with the global memory36over one of the system buses32,34.

Still referring toFIG. 2, the cache memory40operates as a cache buffer in connection with storage and retrieval operations, in particular, caching update information provided by the host director30during a storage operation and information received from the storage devices18which may be retrieved by the host director30during a retrieval operation. The cache index/directory41is used to store metadata associated with the cached data stored in the cache memory40.

The cache memory40includes a plurality of storage locations, which are organized in a series of cache slots. Typically, each cache slot includes a header and data portion that contains data that is cached in the cache slot for a data element, typically a track, with which the cache slot is associated, i.e., a track identified by the header.

The cache index/directory41operates as an index for the cache slots in the cache memory40. It includes a cache index table for each of the storage devices18a,18b,18k, in the data storage system12. Each cache index table includes device header information, for example, selected identification and status information for the storage device18associated with the table. In addition, each cache index table includes cylinder descriptors and each cylinder descriptor includes track descriptors for each track in the cylinder. Each track descriptor includes information for the associated track of the storage device, including whether the track is associated with a cache slot, and, if so, an identification of the cache slot with which the track is associated. Preferably, each track descriptor includes a “cached” flag and a cache slot pointer. The cached flag, if set, indicates that the track associated with the track descriptor is associated with a cache slot. If the cached flag is set, the cache slot pointer points to one of the cache slots, thereby associating the track with the respective cache slot. If the cached flag is set, information from the track is cached in the cache slot identified by the cache slot pointer for retrieval by one or more of the host directors20.

As described above, and referring back toFIGS. 1 and 2, the host director30typically performs storage (or write) and retrieval (or read) operations in connection with information that has been cached in the cache memory40, and the disk directors44performs operations to transfer information in the storage devices18to the cache memory40for buffering (“staging”) and to transfer information from the cache memory40to the storage devices18for storage (“destaging”).

Generally, the host director30, during a read operation, attempts to retrieve the information for a particular track from the cache memory40. However, if the condition of the cached flag associated with that track indicates that the information is not in the cache memory40(in other words, a cache miss has occurred), it will enable the disk director44which controls the storage device18that contains the information to retrieve the information from the track which contains it and transfer the information into a cache slot in the cache memory40. Once the disk director44has performed this operation, it updates the directory41to indicate that the information from the track resides in a cache slot in the cache memory40, in particular, setting a corresponding cached flag and loading a pointer to the cache slot in the cache slot pointer.

After the disk director44has stored the data in the cache memory40, it notifies the host director30that the requested data is available. At some point after receiving the notification, the host director30uses the tables of the directory41to identify the appropriate cache slot and retrieves the requested data from that cache slot.

During a write operation, the host director30determines if information from a track to be written is cached in a cache slot. If cached, the host director updates the cache slot with new data. If the host director30determines that the track is not associated with a cache slot, it selects a cache slot, stores the new data in the selected cache slot and updates the track descriptor. Once the new data is stored in the cache slot, the host director30notifies the disk director44so that the disk director44can write the data cached in the cache slot to the track and storage device with which the cache slot is associated as part of a destaging operation.

As discussed above, the cache index/directory41provides an indication of the data that are stored in the cache memory40and provides the addresses of the data stored in the cache memory40. The cache index/directory41can be organized as a hierarchy of tables for devices (logical volumes), cylinders and tracks, as described in Yanai et al., U.S. Pat. No. 5,206,939, and Vishlitzky et al., U.S. Pat. No. 6,049,850, both of which are incorporated herein by reference.

Referring toFIG. 3, the data structures42include a cache slots Least Recently Used (LRU) data structure50and Global Memory Write Pending Data Structures52. One Global Memory write pending data structure52is maintained for each logical volume residing on the data storage system14.

The cache slots LRU data structure50includes a list of cache slots in the cache memory40, as well as a head pointer to point to the head of the list and a tail pointer to point to the tail of the list. The cache slots LRU data structure50is used by the directors30,44and48for readily identifying the least-recently-used cache slot or data element in the cache memory40. The cache slots LRU data structure50can be a conventional LRU queue, or, more preferably, a “replacement queue” as described in Vishlitzky et al., U.S. Pat. No. 5,706,467, incorporated herein by reference.

Each of the Global Memory write pending data structures52includes a Write Pending List54of nodes (elements) or entries56, and a head pointer (“HEAD”)58associated with each WPL54that points to the head of or first entry of that WPL54. The WPL54can be organized as a singly linked list, with each node or entry56pointing to the adjacent node above it on the list, as shown.

The WPL54is used to identify, by cylinder, cache slots that have been written to but not yet written back to a storage device, that is, those cache slots for which a write is pending and should not be overwritten with new data. For that reason, if a cache slot is represented by a cylinder on the WPL54, then it should not be in the cache slots LRU data structure50. The Global Memory write pending data structures52are accessed by the disk directors44for performing the destaging tasks of writing the modified data from the cache memory to the appropriate logical volumes on the storage devices18. Thus, it is desirable to provide a separate pending Global Memory write pending data structure52for each of the logical volumes so that each disk director44need access only the data structures for the logical volumes it services.

For simplification, the WPLs54and the cache index/directory are shown as separate structures. However, it will be appreciated that the WPLs54are associated with the entries in the cylinder tables of the cache index/directory41, and may in fact be a subset of those entries, that is, be formed by those entries in which a write pending indicator is set. In the latter case, the cylinder table entries could be adapted to include the additional fields required by the WPLS54, as will be described with reference toFIG. 5.

Typically, when a host computer12writes to or updates a data element in the cache memory40, the corresponding host director30updates the cache index/directory41as necessary to indicate a write pending in the appropriate tables and, if a write pending is not already indicated, removes the cache slot or slots containing the modified data from the LRU data structure50(so that they will not be overwritten before destaging can occur) as necessary.

The WPL is also updated to reflect that a write has occurred. If a write pending is not already indicated for the data element written to by the host director, then an entry or node is added to the head of the appropriate WPL54. As will be discussed in further detail later, the WPL nodes include a timestamp that is updated to reflect a write to a data element on a cylinder already represented on the that WPL, that is, a data element for which a write back to storage is currently pending.

As indicated earlier, the WPL is a list of all cylinders with write-pending tracks belonging to the logical volume to which the WPL corresponds. As it is expensive to keep the cylinders sorted by the time they were most recently touched, the disk directors use a modified LRU technique to track such updates in the WPL. Instead of promoting a cylinder in the WPL when the data is written to one of its tracks, the responsible disk director marks the last time that the cylinder is written. When the cylinder reaches the tail of the WPL, the director checks a “Last_Written” timestamp and may promote the cylinder to the head of the WPL if it is not mature enough for destaging. Alternatively, the WPL entries56each can include a promotion bit that is used to indicate if the cylinder is to be promoted. The promotion bit is initially set to zero. When data is written to a track of a cylinder whose entry is somewhere in the middle of the list (i.e., not at the head or tail, where the cylinder/entry can be easily promoted), the disk director sets the promotion bit to a ‘1’. When that cylinder reaches the tail of the WPL, the disk director checks the promotion bit and promotes the cylinder to the head of the WPL if the promotion bit is a ‘1’.

As shown inFIG. 4, the directors30,44and48(represented in the figure by the director44a) include a processor60coupled to a control store61and a local, nonvolatile memory (NVM)62by an internal bus64. The processor50controls the overall operations of the director44and communications with the memories61and62. The local memory62stores firmware (or microcode)66, as well as data structures and parameter/variable data in a parameter (and data structure) store68.

The firmware66and parameter store68are read each time the data storage system14is initialized. The microcode66is copied into the control store61at initialization for subsequent execution by the processor60.

The components of the director microcode66include the following: a system calls/host application layer70; advanced functionality modules72, which may be optional at the director level or even at the data storage subsystem level; common function modules74, which are provided to each director; an interface module76; and one or more physical transport (or device) drivers77. Interface modules exist for each of the different types of directors that are available based on connectivity and/or function and thus define the director functionality. Specifically, for the disk director44, the interface module76is a disk interface module. That is, a director that has been loaded with the disk interface code76is thus programmed to serve as the disk director44or one of disk directors44(when more than one is present in the system). As such, it is responsible for controlling back-end operations of the controller16.

The common function modules74includes a number of processes executed by the processor60to control data transfer between the host computer12, the global memory36and the disk devices18, e.g., a cache manager having routines for accessing the cache memory40, as well as the associated cache index/directory41and cache slots LRU data structure50.

The disk director interface module76includes code to support services for read misses, write destaging, RAID, data copy, and other background drive operations. In particular, to optimize performance for write destaging, the module76includes destaging support processes or routines78. These destaging support processes78include a cylinder destaging selection process80, a cylinder destaging selection indication process82, a “mark track write-pending (WP)” process84and a process85used to place a WPL node at the head of the WPL.

The parameter store68includes a copy of a tail pointer (“TAIL”)86for each WPL54in global memory36that corresponds to a logical volume serviced by the disk director44a. Only one such tail pointer is shown in the figure. If, for any reason, the local copy of the tail pointer is lost, the disk director can recover it by reading the head of the WP list54. Although preferably located locally in disk director memory to minimize access time and the number of accesses to global memory, the tail pointer86could be stored in the global memory36. The parameter data of the parameter store68includes, among other information, time delay parameters Time-Delay87and Min-Delay88, which are used by the processes78to determine a threshold level of maturity for destaging selection.

The format of each WPL entry56(at least those fields that pertain to pending writes and the processes78) is shown inFIG. 5. It includes the following fields:

The Last_at_Head field90specifies the last time the cylinder was at the head of the WPL54. The Last_Written field92specifies the last time a track from the cylinder was written to by one of the host computers12. The Visited field94is a Boolean array having one value per each mirror M. Thus, Visited[M] indicates if the cylinder has been “visited by” (that is, considered for possible destaging activity by) mirror M. If Visited[M] is TRUE, then the TAIL of mirror M points to a node above the current node. If Visited[M] is FALSE, then the TAIL of mirror M points to the current node or points to a node below the current node. The Destaged field96is also implemented as a Boolean array having one value per mirror. The flag setting of the Destaged[M] indicates if the cylinder has been destaged to mirror M. If Destaged[M] is TRUE, then Visited[M] is also be TRUE. The NEXT field98stores the pointer to the next node in the WPL.

As mentioned earlier, the time delay parameters Time-Delay87and Min-Delay88are maintained and adjusted by the microcode. The value of the parameter Time-Delay87is the desired amount of time (since the last write) that the write pending cylinder has to remain in the cache memory40before it is allowed to be destaged. The value of the parameter Min-Delay88is the minimal amount of time that the write pending cylinder has to remain in the cache memory40before it can be destaged. Preferably, the Min-Delay88should be about 75% of the Time-Delay87. For example, if the Time-Delay87is 20 seconds, then the Min-Delay88is 15 seconds. All the writes to this cylinder in the first 5 seconds following the first write are not counted in the determination of whether the cylinder is mature enough for destaging. One technique for adjusting such maturity threshold parameters is described in co-pending U.S. patent application Ser. No. 09/850,551, entitled “Cache Management via Statistically Adjusted Slot Aging”, filed on May 7, 2001, incorporated herein by reference.

Referring toFIG. 6, a depiction of a mirrored configuration99of devices and associated write pending data structures supporting the mirrored configuration is shown. In the example shown, the disk devices18a-1and18c-1each store two logical volume mirrors. The disk device18a-1stores a first mirror for a first logical volume LV1(M1-LV1)100aand a first mirror for a second logical volume LV2(M1-LV2)100b. The disk device18c-1stores a second mirror for the first logical volume (M2-LV1)10a′ and a second mirror for the second logical volume (M2-LV2)100b′. The mirrors100aand100bare serviced by the disk controller44a, while the mirrors100a′ and the mirrors100b′ are serviced by the disk controller44b. The global memory36stores two Global Memory write pending data structures, one for each of the logical volumes, thus a first WPL54aand associated head pointer58afor LV1, and a second WPL54band associated head pointer58bfor LV2. Each disk director maintains a copy of a tail pointer for each WPL that corresponds to a logical volume that it service. Therefore, each disk director maintains a tail pointer to point to the tail of the WPL54afor LV1and a tail pointer to point to the tail of the WPL54bfor LV2. As indicated earlier, a separate tail pointer is maintained for each logical volume mirror. Thus, disk director44bstores its own tail pointers for the write pending lists for LV1and LV2, that is, tail pointer72a′ and tail pointer72b′, respectively. Each disk director uses its own WPL tail pointers to access the WPLs for the logical volume mirrors it supports. Thus, for example, if the disk director44awants to examine the WPL54ato select a destaging candidate for M1-LV1, it uses the tail pointer72ato locate the tail node. Upon examining the information in that node, the disk controller may do one of the following: select the node for destaging; promote the node to the head of the list and/or mark the node as having been considered (“visited”) for destaging to M1; or take no action. In all but the latter case, the disk director moves the tail pointer to the next node in the list. Consequently, at any given time, the tail pointers for each of a logical volume's mirrors may point to different nodes, depending on whether the disk director for a given mirror has examined that node yet. Only when all mirrors for a logical volume have considered and selected a node for destaging activity will the node be removed from the write pending list.

FIG. 7illustrates an entire write pending data structure for LV1, indicated by reference number102. The data structure102includes the head pointer58aand list of nodes54(from Global Memory36), as well as both tail pointers72aand72a′ (stored in the memories of respective disk controllers44aand44b). In the figure, a node X56ais the current node to be accessed by the disk controllers44aand44bvia their respective tail pointers72aand72a′, respectively.

The various destaging support processes78will now be described with reference toFIGS. 8-11, in conjunction withFIG. 7. For purposes of illustration, it will be assumed that the processes78will be performed by the disk director44afor servicing LV1. Thus, disk director44afollows the tail pointer72ato the node X56a.

Referring first toFIG. 8, an overview of the destaging selection process80is shown. The process80begins by examining the WPL node56apointed to by the local copy of the tail pointer, that is, TAIL72a(step110). The process80′ determines if a value of current (elapsed) time (“Current-Time”) is less than the amount of time delay equal to the sum of the values in the fields Last_at_Head90(FIG. 5) and Time-Delay87(FIG. 4) (step112). If so, the process80returns a failure indication (step114), thereby indicating that no write pending cylinder on the WPL is mature enough to be destaged yet. Otherwise, at step114, the process80determines if the Current-Time is less that the sum of the values of the Last_Written field92(FIG. 5) and Min-Delay88(FIG. 4), or determines from examining flags in the Visited array94and Destaged array96(FIG. 5) in the node or entry that another mirror has visited the node without destaging it (step116). If both conditions are false, that is, the Last_Written value plus the Min-Delay value is greater than the Current-Time, and no other mirror has visited the node without destaging it, the process80returns a selection of the cylinder corresponding to the node for destaging (Step118). Using a separate process (not shown), according to techniques well understood in the art, the disk director44performing the process80commences a destaging operation to destage one or more write pending tracks for the selected cylinder from the cache memory40to the logical volume.

Referring again to step116, if at least one of the conditions is true, the cylinder corresponding to the current node will not be destaged at this time. The process80marks the Visited array94of the node to indicate that the mirror M serviced by the disk director currently executing the process80has visited the node (step120) and sets the value of TAIL72ato the value stored in NEXT98, thus moving the tail pointer72ato the next node in the list (that is, the node above the current node X, e.g., node X56ainFIG. 7) (step122). In the illustration ofFIG. 7, the new value of the TAIL for M1is indicated by the dashed arrow pointing to the next node, node56b. The process80determines if all of the mirrors for the logical volume have visited the current node X (step124). If so, process80invokes process85to place the current node X at the head of the WPL (step126). Otherwise, if all of the mirrors have not visited the current node X, the process80returns to step110to examine the node now pointed to by TAIL as the current node X.

Referring now toFIG. 9, the details of the cylinder destaging selection/indication routine or process82are shown. The process82marks the node X (selected for destaging by the process80as discussed above) as visited by the current mirror M (step130) as well as marks the current node as destaging by the current mirror M (step132). The process82sets TAIL to the value NEXT (step134). The process82determines if all of the mirrors have visited the current node X (step136). If, at step136, it is determined that all mirrors have not visited the current node X, then the process82uses the process85to place the node X at the head of the WPL (step137). If all mirrors have visited the node X, the process82determines if all mirrors have destaged node X (step138). If all mirrors have destaged the node X, then the process82removes the node X from the WPL (step139), thereby causing any associated device/cylinder/track write pending flags in the cache index/directory41to be cleared and any cache slots corresponding to the destaged cylinder track(s) to be returned to the cache slots LRU data structure50(the returned slots thus being made available again for access by the host computers12).

Referring toFIG. 10, the track pending marking process84, that is, the process of updating the WPL when a track has been written to by one of the host computers12, is shown. The process84detects a write to a track on a cylinder of a logical volume mirror serviced by the disk director performing the process89(step140). The process determines if the cylinder is already represented by a node on the WPL (step142). If it is not, the process89prepares a node (step144) and sets the Last_Written field in that node to the Current-Time value (step146) and proceeds to invoke process85in order to place the node at the head of the WPL (step147). If, at step142, the process89determines that the cylinder is already represented by a node on the WPL, the process89sets the Last_Written field to Current-Time (step148) and clears all Destaged flags that have been set in that node (step150).

The details of the process85that performs the placement of a node (that is, the current node, e.g., node X fromFIG. 8) at the head of the WPL are shown inFIG. 11. Referring toFIG. 11, the process85sets the value of Last_at_Head to the value of Current-Time (step160). The process85clears any Visited and Destaged flags in the current node (step162). The process85sets the value of NEXT to point to the current node (step164) and sets the value of HEAD to point to current node (step166).

Preferably, the destage support processing is performed as a background task. However, it may be desirable to elevate the destage support processing to a priority task for servicing pending writes when the number of pending writes exceeds a threshold number.

In an alternative embodiment, illustrated inFIGS. 12-13, as well asFIGS. 10-11, the destage support processing also performs a sort based on physical location within the disk to achieve benefits of prior “pyramid” data structures (examples of which are described in the above-referenced patents, as well as Mason, Jr., U.S. Pat. No. 6,304,946), in addition to the good statistics behavior of the WP list.

Referring toFIG. 12, details of an alternative destaging selection process80, indicated as process80′, are shown. The process80′ begins by examining the WPL node pointed to by the local copy of the tail pointer, TAIL (step170). The process80′ determines if a value of current (elapsed) time (“Current-Time”) is less than the amount of time delay equal to the sum of the values in the fields Last_at_Head90(FIG. 5) and Time-Delay87(FIG. 4) (step172). If so, the process80′ returns a failure indication (step174) indicating that no write pending cylinder on the WPL is mature enough to be destaged yet. Otherwise, the process80′ determines if the Current-Time is less that the sum of the values of the Last_Written field92(FIG. 5) and Min-Delay88(FIG. 4), or determines from examining flags in the Visited array94and Destaged array96(FIG. 5) in the node or entry that another mirror has visited the node without destaging it (step176). If both conditions are false, that is, the Last_Written value plus the Min-Delay value is greater than the Current-Time, and no other mirror has visited the node without destaging it, the process80′ returns a selection of the cylinder corresponding to the node for destaging (step178). In addition, the process80′ selects up to N more nodes (cylinders) from the WP list within a predetermined window of time, e.g., “x” seconds (step180, and sorts the cylinders represented by those nodes according to physical proximity to the cylinder C already selected for destaging (step182). For example, the cylinders can be sorted by cylinder numbers (stored in the cylinder tables). The process80′ destages the N additional cylinders in the sorted order so that the I/O requests directed to those cylinders are issued in that order.

Referring again to step176, if at least one of the conditions is true, the cylinder corresponding to the current node will not be destaged at this time. The process80′ marks the Visited array94of the node to indicate that the mirror M serviced by the disk director currently executing the process80′ has visited the node (step186) and sets the value of TAIL to the value stored in NEXT98, thus moving the tail pointer to the next node in the list (step188). The process80′ determines if all of the mirrors for the logical volume have visited the current node X (step190). If so, process80′ invokes process85(shown inFIG. 11) to place the current node X at the head of the WPL (step192). Otherwise, if all of the mirrors have not visited the current node X, the process80′ returns to step170to examine the node now pointed to by TAIL as the current node X.

Referring toFIG. 13, the details of an alternative cylinder destaging selection/indication routine or process82, indicated as process82′, are shown. The process82′ is repeated for each of the nodes/cylinders destaged by process80′. The process82′ marks the destaged node as visited by the current mirror M (step200) as well as marks the current node as destaging by the current mirror M (step202). If it is determined that the destaged node currently being processed is the Nth node (step204), the process82′ sets TAIL to the value NEXT (step206). The process82′ determines if all of the mirrors have visited the destaged node (step208). If, at step208, it is determined that all mirrors have not visited the destaged node, then the process82′ uses the process85to place the node at the head of the WPL (step210). If all mirrors have visited the node, the process82′ determines if all mirrors have destaged the node (step212). If all mirrors have destaged the node, then the process82′ removes the node from the WPL (step214), thereby causing any associated device/cylinder/track write pending flags in the cache index/directory41to be cleared and any cache slots corresponding to the destaged cylinder track(s) to be returned to the cache slots LRU data structure50(the returned slots thus being made available again for access by the host computers12).

The process84and process85remain as described above with reference toFIG. 10andFIG. 11, respectively.