Dynamic mirror service policy with seek adjustment in a non-physical mirrored storage environment

[0002] The invention relates generally to data storage systems, and in particular, to data storage systems in which data is stored on mirrored logical volumes.

[0003] Various techniques have been developed for increasing the reliability of data storage systems and to protect against failure due to data loss. One such technique is data mirroring, which involves the storage of two or more copies of the data, preferably on different storage devices. A data storage having mirrored data operates to maintain all copies up to date. Typically, there are two copies.

[0004] In a typical data storage system, each physical device, such as a disk storage device, may have a format that defines a number of units, and the units may correspond to logical volumes. Each logical volume appears to the host computer or computers to be a separate storage device and, therefore, operations take place with regard to the logical volume as if it were a physical volume. Typically, the physical devices are configured as mirrored pairs, with each physical device in the pair storing corresponding copies of logical volumes. Such a data storage system is said to employ both mirrored physical devices and mirrored logical copies.

[0005] Some logical volumes are accessed for read and/or write operations substantially more often than other logical volumes, and the nature of the operations can vary from random accesses to sequential accesses during any particular sequence of read or write operations. As a result, with larger storage devices, the risk of having concurrent jobs, each pertaining to a relatively small file (local activity) interfering with each other's activity increases. The use of striping techniques further increases the risk. Depending upon the nature and frequency of the read and write operations to a storage device containing many logical volumes, the disk read/write heads may be severely worked and the access time can, on average, be increased if sequential read and write locations are not located near one another.

[0006] One prior solution sets a mirror service policy, statically or preferably dynamically (as described in U.S. application Ser. No. 08/936,122, filed Sep. 24, 1997, issued as U.S. Pat. No. 6,112,257 on Aug. 29, 2000, and entitled “Dynamic Adjustment of Mirror Service Policy for Logical Volumes in a Disk Drive System Based on Collected Statistics,” the contents of which are incorporated herein, by reference), in an attempt to optimize the reading and writing of data. Such a policy may, for example, assume that most data transfers are sequential in nature, or that they are random. The policies can include, for example, interleaved, mixed, dedicated, or other policies that appear, after reviewing the manner in which a storage device is, or is to be, used, to provide the best average access time to the data.

[0007] One such policy is to only service requests that fall within the first half of a logical volume on one of a mirrored pair of physical devices and the requests to the second half of the logical volume on the other, mirrored physical device. Another policy might be to only service requests that fall in odd groups with a group being defined in terms of a number of blocks. For instance the first group (blocks 0-959) will be serviced by copy 1 and the next group by copy 2, etc. These policies, when implemented statically, are limited because the policies are chosen at system configuration time and never change. A dynamic mirror policy can substantially improve performance as the policies for the system change periodically.

[0008] Once a policy to service each logical volume is determined, the approach described in the U.S. Pat. No. 6,112,257 attempts to optimize seeks fur the logical volumes on the same physical devices. There may, however, be circumstances that require greater flexibility in configuring the physical devices for logical volumes, or it may become necessary or desirable to transfer data in a logical volume from one of the mirrored physical devices to a third device, thus destroying the mirroring at the physical device level. The existing seek optimization described in the U.S. Pat. No. 6,112,257, which is based on physical mirrors, will be ineffective in maintaining seek balances under such circumstances.

[0009] This invention relates to seek adjustment in a data storage system of physical devices having mirrored logical volumes.

[0010] In an aspect of the invention, statistics describing at least reading data from the mirrored volumes during successive time periods are collected and an activity level associated with each of the mirrored logical volumes is determined from the collected statistics. Seek activity values for each of the physical devices are then computed based on the activity levels associated with the logical volumes on the physical devices and used to minimize seek activity for non-mirrored ones of the physical devices.

[0011] Embodiments of the invention may include one or more of the following features.

[0012] The computed seek activity values computed for the physical devices may relate a physical device seek activity to the activity level associated with, and distance between, the mirrored logical volumes residing the physical devices.

[0013] The computed seek activity values may be used to minimize seek activity for non-mirrored ones of the physical devices in the following manner. A sum of the computed seek activity values is computed. At least one simulated mirror policy change based on the computed sum of the computed seek activity values is performed. The sum of the computed seek activity values are recomputed using the results of the at least one mirror policy change. If the recomputed sum of the seek activity values is determined to be less than the computed sum of the seek activity values, then at least one simulated mirror policy change is implemented.

[0014] At least one simulated mirror policy change may be made by selecting a most active one of the physical devices based on the computed seek activity values, selecting a most active one of the logical volumes residing on the selected most active one of the physical devices based on the associated-activity level, modifying a mirror policy associated with the selected one of the logical volumes to reduce the seek activity value for the selected one of the physical devices and recomputing the seek activity values for the selected one of the physical devices and another one of the physical devices which stores a mirrored copy of the most active one of the logical volumes.

[0015] At least one simulated policy change may include a plurality of simulated policy changes. The plurality of simulated policy changes may be repeated a predetermined number of times.

[0016] The use of the seek activity values to minimize seek activity for non-mirrored ones of the physical devices may repeat until a predetermined time interval has expired or, alternatively, until the recomputed sum is zero.

[0017] The recomputed sum may include a factor equal to an average of the activity levels of the logical volumes.

[0018] The seek adjustment mechanism of the invention offers several advantages. It provides for both device-specific seek reduction as well as seek balancing in a data storage system that employs non-physical mirroring techniques. To minimize seeks for a physical device in such a non-physical mirrored environment, the seek adjustment mechanism uses a seek function that takes into account the activity levels of and distances between the logical volumes residing on the physical device. At the same time, the mechanism determines the impact that a particular mirror policy change will have on storage devices other than the two storage devices involved in that mirror policy change. It does so by examining mirror policy changes likely to follow (predicted future policy changes) and determining if there is continued improvement in overall seek reduction over the course of those predicted future changes.

[0019] Other features and advantages of the invention will be apparent from the following description taken together with the drawings in which:

[0020] FIG. 1 is a block diagram of a data storage system in which the invention can be employed;

[0021] FIG. 2 is a detailed block diagram of the disk controller shown in FIG. 1;

[0022] FIG. 3 is a block diagram of the disk adapter shown in FIG. 2;

[0023] FIG. 4 is a flow diagram illustrating the mirror service policy process for the disk adapter shown in FIG. 3;

[0024] FIG. 5 is a flow diagram illustrating the process of seek adjustment for non-physical mirrors performed by at least one of the disk adapters shown in FIG. 3.

[0025] FIG. 6 is a flow diagram illustrating an alternative process of seek adjustment for non-physical mirrors performed by at least one of the disk adapters shown in FIG. 3.

[0026] FIG. 7 is an example of three simulated policy changes as performed by the process of seek adjustment for non-physical mirrors shown in FIG. 5; and

[0027] FIG. 8 is a depiction of three seek function value sorts performed in relation to the three simulated policy changes shown in FIG. 6.

[0028] Referring to FIG. 1, a data processing system 10 includes a plurality of host computers 12a, 12b, . . . , 12m, connected to a data storage system 14. The data storage system 14 receives data and commands from, and delivers data and responses to, the host computers 12. The data storage system 14 is a mass storage system having a controller 16 coupled to a plurality of physical storage devices (or, simply, physical devices) shown as disk storage devices 18a, 18b, . . . , 18k. The controller 16 interconnects the host computers 12 and the physical devices 18, and can be, for example, that made by EMC and known as the Symmetrix controller. The controller 16 thus receives memory write commands from the various host computers over buses 20a, 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 physical devices 18 over respective connecting buses 22a, 22b, . . . 22k. Buses 22 also preferably operate in accordance with a SCSI protocol. The controller 16 also receives read requests from the host computers 12 over buses 20, and delivers requested data to the host computers 12, either from a cache memory of the controller 16 or, if the data is not available in cache memory, from the physical devices 18.

[0029] Each of the physical devices 18 is logically divided, in accordance with known techniques, into a plurality of units. While typically one unit represents a logical volume, when a logical volume is striped across several physical devices, a unit will store only a fraction of a logical volume. There can be a plurality of units, for example 4, 8, or more units, on a physical device. In a typical configuration, the controller 16 also connects to a console PC 24 through a connecting bus 26. Console PC 24 is used for maintenance and access to the controller 16 and can be employed to set parameters of the controller 16 as is well known in the art.

[0030] In operation, the host computers 12a, 12b, . . . send, as required by the applications they are running, commands to the data storage system 14 requesting data stored in the logical volumes or providing data to be written to the logical volumes. Referring to FIG. 2, and using the EMC Symmetrix controller as an illustrative example, the communications from the host computer 12 typically connects to a port of a plurality of channel adapters 30 over the SCSI bus lines 20. Each channel adapter, in turn, connects over one or more system busses 32 or 34 to a global memory 36. The global memory 36 is preferably a large memory through which the channel adapter 30 can communicate to the physical devices 18 and can include a cache memory 38. Also connected to the global memory 36 are a plurality of device adapters shown as disk adapters 40, which control the physical devices 18. The disk adapters 40 also communicate with the global memory 36 over, preferably, SCSI busses 42. During a write operation, the disk adapters 40 read data stored in the global memory 36 by a channel adapter 30 and 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 adapters 40 read data from a logical volume and write that data to global memory for later delivery by the channel adapter to the requesting host.

[0031] As is known in the art, mirrors of logical volumes may be maintained in conjunction with mirrors of physical devices. The logical volume mirrors are copies of each other and the physical device mirrors are copies of each other. For example, if there are two mirrored physical devices M1 and M2, four mirrored logical volumes A, B, C, D and M1 stores logical volumes A through D only, then M2 stores logical volumes A through D only. It is also possible to support logical volume mirrors on non-mirrored physical devices. In such a non-physical mirrored configuration, all of the corresponding mirrored copies of the logical volumes stored on one of the non-mirrored physical devices will not reside together on a different physical device. An example of a “non-physical” mirrored arrangement (i.e., logical volume mirrors stored on non-mirrored physical devices) is later shown in FIG. 7.

[0032] With reference to the data storage system 14, it is assumed that mirroring exists at the logical volume level, but not necessarily at the physical device level. Typically, for purposes of this embodiment, paired logical volume copies are employed and it is assumed that each unit stores a logical volume. The controller 16 can then respond to a read request by reading from either of the logical volume copies or mirrors stored in the physical devices 18.

[0033] Accordingly, there is implemented in the controller 16, and among the disk adapters 40, a mirror service policy which identifies which of the device adapters 40 is primarily responsible for reading in response to requests from a host computer. This policy could be fixed at the beginning of a system set up, taking into account the expected loads. Preferably, however, the mirror service policy implementation is dynamic. That is, the mirror service policy can be modified, periodically, in response to statistics describing the nature of the read and write requests to the data storage system 14, to change the mirror service policy during the operation of the data storage system 14.

[0034] An example of a dynamic mirror service policy (DMSP) is described in the above-referenced U.S. application Ser. No. 08/936,122. Over a given time period, data access information is collected. At the end of the period, a decision is made for each logical volume about the best policy to use for it. Logical volumes with higher access rates receive more attention than volumes with lower access rates. The information collected includes access rates for both read and write operations and how sequential the accesses were during the time period. Many factors are included in the policy decisions. These factors include: the activity level of the physical devices involved, the activity level of the disk adapters involved, and how sequential the accesses were. Also, information about the relationships between the different logical volumes that use the same mirrored physical devices is used to perform seek minimization.

[0035] However, in a data storage system (such as the data storage system 14 of the present embodiment) in which the mirrors of logical volumes do not necessarily reside on mirrored physical devices, it is desirable, also, to ensure load balancing over the non-mirrored physical devices. To that end, in addition to the existing seek function described in the above-referenced patent application, the controller 16 is suitably adapted to perform a seek minimization operation to adjust seek activity in a data storage system in which the logical volumes, but not the physical devices, are mirrored.

[0036] As shown in FIG. 3, each disk adapter 40 includes a processor 50 coupled to a local, nonvolatile memory (NVM) 52 by an internal bus 54. The processor 50 controls the overall operations of the disk adapter and communicates with the local memory 52. The local memory 52 stores firmware 56 and parameter data, such as the DMSP table, in a parameter store 58, and is read each time the data storage system 10 is initialized. Included as a component of the firmware 56 is a mirror service policy process 60, which is copied to the processor's internal RAM (or external RAM, not shown), at initialization for subsequent execution by the processor 50. The mirror service policy process includes a DMSP decision process and seek optimization for logical/physical mirror arrangements like that discussed above and as further described in the above-referenced U.S. application Ser. No. 08/936,122. In addition, the mirror service policy process 60 includes a seek minimizer 62, which provides seek adjustment functionality to a non-physical mirrored data storage environment, as described below. The disk adapter 40 may include more than one processor 50 for parallel or distributed processing within a particular disk adapter.

[0037] Although not shown, it will be understood by those skilled in the art that the disk adapter 40 will include I/O interface logic, as well as bus and control logic. In addition, the disk adapter 40 may include transmit/receive buffers for temporarily storing data to be transferred to and received from the global memory 36.

[0038] The seek minimizer 60 employs a seek function to estimate seek activity for each physical device in the data storage system. The seek function is given by $\begin{array}{cc}S=\left[1/2\sum _{i=1}^n\sum _{j=1}^n{a}_i{a}_j\left|i-j\right|\right]/\sum _{k=1}^n{a}_k& \mathrm{Eq}.\left(1\right)\end{array}$

[0039] where n is the number of logical volumes on the physical device, a_iis the weighted activity for ith logical volume and |i−j| is a measure of the distance between a pair of logical volumes on the physical device. The weighted activity is as defined in the above-reference U.S. application Ser. No. 08/936,122. The seek function of Eq. (1) therefore provides an indication of seek activity (the total weighted distance of seeks on a physical device) and assumes that the number of seeks performed to a given physical device is related to the weighted activity a_iof the logical volumes and the distance between such logical volumes.

[0040] It is desirable to minimize to the extent possible the seek time over all of the physical devices D_fby solving for each seek function S_fand minimizing the sum of the seek functions, i.e., ΣS_f, where f=1, 2, . . . k, and k is the number of physical devices. It may be noted, however, that, while the ultimate goal may be to reduce the seek function sum to zero, that is, each call for information to the data storage devices is handled by a different physical device, in practice it is rarely achievable since the number of units or logical volumes is typically much larger than the number of physical devices.

[0041] Referring to FIG. 4, a flow diagram illustrating the mirror services policy process 60 is shown. The process 60 collects statistics for all logical volumes (step 70). Once the time has come to reconsider the mirror policies (step 72), the statistics for all logical volumes are reviewed and the logical volumes are sorted by activity level (preferably using the approach described in U.S. application Ser. No. 08/936,122) (step 74). Having sorted the logical volumes by activity level, the process 60 performs a load balancing process (step 76) and a first seek adjustment (step 78) process (again, preferably using the approaches described in co-pending application Ser. No. 08/936,122). The seek adjustment attempts to minimize seeks for all logical volume mirrored pairs residing on the same two physical devices (i.e., for physical mirrors). Once these load balancing and seek adjustment processes have been completed, the seek minimizer 62 is invoked to perform a second seek adjustment for non-physical mirrors (step 80). After the second seek adjustment of step 80 has been completed, the statistics collection process resumes (at step 70).

[0042] Referring now to FIG. 5, the second seek adjustment process 80 (for or corresponding to the seek minimizer 62 of FIG. 3) is shown. The process 80 begins by initializing a timer programmed to a time interval value (step 82) corresponding to the maximum allowable run time, e.g., 100 ms. The process 80 computes a seek function value S (according to Eq. 1 above) for each of the physical devices (step 84). Once the seek function values have been computed, the sum of all computed S values is computed (step 86) and the physical devices are sorted by the computed S values (step 88). The process 80 then initializes a count “c” (step 90). The count c counts a predetermined threshold number “r” of “simulated” mirror policy changes performed by the process 80, as will be described. It should be noted that the count and time interval values are arbitrary, that is, they are a matter of design choice and thus may be selected in accordance with system performance requirements. In the illustrated embodiment, the count threshold value r is chosen to be to 3.

[0043] Using the sorted S values, the process 80 simulates a first policy change for the most active logical volume LV_ion the busiest physical device by selecting the logical value with the highest a_ivalue on the physical device corresponding to the highest S value, and reassigns the preferred device mirror policy to the corresponding mirrored copy of LV_iresiding on a different one of the physical devices (step 92). At this stage, and as indicated above, the process is merely simulating the change, that is, the reassignment has not actually been implemented (by recording the policy “swap” in the DMSP table as described in the above-referenced U.S. application). Rather, the reassignment information, as well as the various computation results, are stored in processor memory. Once the simulated change is complete, the S values for the two physical devices involved in the policy swap are recomputed (step 94). The S values for the physical devices are again sorted (step 96) and the count is advanced by one (step 98). The seek minimizer determines if the count has expired (step 100). If the count has not expired, the seek minimizer repeats steps 92, 94, 96 and 98 until the count expires.

[0044] Once the count has expired, the process 80 computes a “new” sum of S values, or, (ΣS)′, to reflect the changes in S values for the devices involved in policy swaps in each of the simulated changes (step 102). The process determines if the (ΣS)′ is less than the original ΣS (step 104). That is, it determines if the first of the simulated changes as well as the simulated changes likely to follow in future policy update decisions, have a favorable impact on seek activity. If (ΣS)′ is less than ΣS, then the process 80 implements the first of the three simulated changes by updating the mirror policy information (i.e., the “preferred device” settings) for the associated logical mirrored pair (step 106). On the other hand, if there is no reduction in the ΣS value as a result of the simulated policy changes, then the process is terminated (step 108).

[0045] If the first policy change has been made, the process returns to step 86 only if (ΣS)′ is greater than zero (step. 110) and a time-out has not yet occurred (step 112). If the (ΣS)′ is equal to zero or a time-out has occurred, the process will terminate (steps, 114 and 116, respectively). By returning to step 86, the process again performs “r” simulated changes for the next policy change iteration, starting with the “new” busiest physical device (i.e., the busiest physical device after the last policy change has been implemented in step 106 and the resorting of the S values, as determined during the previous determination, in step 88), and again compares before and after values of the sum of all S values (as described above) to determine the efficacy of making a mirror policy change for the most active volume on the “new” busiest physical device.

[0046] In the preferred embodiment, the process adds to the (ΣS)′ value a factor of y, where y is equal to the average activity level of the logical volumes, that is, the sum of a_i/n for i=1, 2, 3, . . . , n−1, n, where n is the number of logical volumes. This factor is used to ensure that the change is worth making, or, in other words, that it will not merely result in a situation in which the data storage system toggles back and forth between the physical devices.

[0047] It will be appreciated that the S values which are recomputed during the successive simulated changes may be stored by the processor and used in subsequent iterations. For example, and as illustrated in FIG. 6, an alternative process 120 may perform steps 82 through 112 as shown in FIG. 5 and, if a time out has not occurred at step 112, the process computes the ΣS value based on the S values as a result of the implemented policy change (step 122). This sum becomes the new “before” value for the next set of simulated changes to be performed. Because the simulated changes to be performed begin with the new busiest disk after the implemented policy change, the process can skip all but the last of the simulated changes to be performed (that is, c=1, 2, . . . , r−1), as these changes were performed in the previous policy change iteration, and proceed directly to the next simulated change in line. Thus, at step 124, and based on the results of the last re-sort operation, the process performs a simulated policy change for busiest physical device by changing the mirror policy for the most active logical volume. The S values for the physical devices involved in the simulated policy change are recomputed (step 126), the S values are re-sorted (step 128) and the (ΣS)′ is computed by retrieving the S values as updated during the previous iteration (i.e., previous set of r simulated changes) as well as the most recently recomputed S values (from step 126)(step 130). The comparison of S sums is performed as previously described (step 132). If (ΣS)′ is not less than the ΣS, then the process is terminated (step 133). If the (ΣS)′ is less than the ΣS, the process implements the “next” first policy change (i.e., the oldest of the policy changes to performed and not yet implemented) (step 134). Again, the process determines if either the (ΣS)′ is equal to zero (step 136) or a time-out has occurred (step 138). In the event that either condition is true, the process will be terminated (steps 140, 142). Otherwise, the process returns to step 122 for the next iteration of policy change simulations.

[0048] Thus, for all but the first set of policy change simulations, it may only be necessary to perform the final pass of the simulated changes. For example, if r=3, the process could go directly to the third pass of the simulated changes, as the modified S values of the first and second simulated changes were already computed as part of the second and third simulated changes for the previous iteration.

[0049] FIG. 7 provides an example of a first iteration involving r=3 simulated changes for ten physical devices 18. FIG. 8 illustrates the sorted lists accompanying the simulated changes. Referring to FIG. 7, the physical devices store a plurality of logical volumes 150. In example shown, the physical devices 18 are configured to store four logical volumes apiece, for a total of twenty logical volume mirrored pairs. The logical volume mirrored pairs are distributed throughout the ten physical devices according to a random configuration of the physical devices 18. That is, they are placed on the physical devices in a non-physical mirrored fashion.

[0050] Now referring to FIG. 7, together with FIGS. 5 and 8, the physical devices are sorted by S (step 88). In the table of FIG. 8, the devices are sorted in descending order from the most active to least active. In the first sort (sort 1) , S₁corresponds to the busiest device and S₁₀the least active. As indicated by the arrow labeled “1” in FIG. 7, (and as described in step 92), a simulated policy swap is performed between the most active volume, LV₁₈, on S₁, and the device which stores its mirrored copy, that is, S₁₀. The S values for S₁and S₁₀are recomputed (step 94) and the S list is resorted (step 96) to produce the “sort 2” list. Because the most active volume no longer contributes to the S value for S₁, S₁moves to a lower position on the list and S₂rises to the top of the list as the busiest device.

[0051] The second simulated change is performed for S₂. As indicated by the arrow labeled “2”, a policy swap is made between the most active volume LV₁₀on S₂and its mirrored counterpart on S₁. The S values for S₂and S₁are recomputed and the list resorted again.

[0052] In “sort 3”, as shown in the table of FIG. 8, S₃is now the busiest device. In the final simulated change in this first iteration, indicated by the arrow labeled “3”, a policy swap is made between the most active volume LV₅and its copy on S₇and the S values for each of impacted devices S₃and S₇are recomputed.

[0053] Although not shown, the S values would again be resorted in preparation for a next iteration. The device at the top of the list in this last sort could, for example, be S₄. Once the S sums have been compared, the first policy swap for S₁is implemented as appropriate. If the process 25 continues with the next iteration, it will examine S₂, S₃and S₄. If the computation results for the simulated policy swaps involving S₂and S₃are still available from the previous iteration, the process need only look at the simulated policy swap for S₄.

[0054] Returning briefly to FIGS. 2 and 3, the mirror service policy process 60 typically is performed infrequently and is handled as a low priority task in a disk adapter 40 designated the master DA. After execution of the process begins, the process (or portions thereof, such as the seek minimizer) can be executed in fragments so there is no significant time during which the master disk adapter is unavailable to process incoming host-generated requests. The fragment size (if needed) can be selectable and will be determined, for example, in terms of how many logical volumes to examine before resuming, temporarily, normal disk adapter operation. In the event of a failure of the master DA, a designated back-up disk adapter will be responsible for the operation.

[0055] Alternatively, the operation (or portions thereof, such as the seek minimizer) can be divided into tasks (e.g., seek function computation, sorting, seek balancing) and those tasks may be distributed among the different disk adapters (DA's). Each DA performs the task (or tasks) to which it is assigned and publishes the results to one or more of the other DAs. This distributed approach does not necessarily reduce the amount of time required to complete the operation, but does reduce the performance impact on any single DA. In addition, or alternatively, certain tasks which lend themselves to the use of parallel processing techniques can be distributed to more than one DA and executed in parallel. For example, a sorting operation could be performed in halves, each half being sorted by a different DA.

[0056] Additions, subtractions, and other modifications of the preferred embodiments of the invention will be apparent to those practiced in this field and are within the scope of the following claims.