# Patent

## Title
Method of optimizing the space and improving the write performance of volumes with multiple virtual copies

## Abstract

Disclosed is a method and apparatus for optimizing memory space and improving the write performance in a data processing system having a data volume with multiple virtual copies thereof. In one embodiment of the method, a first virtual copy of a primary data volume is created. Thereafter, first data of the primary data volume is modified. A second virtual copy of the primary data volume is created after modification of the first data thereof. A write-data transaction for modifying second data of the modified primary data volume is generated after creation of the second virtual copy. The second data of the modified primary data volume is copied to memory allocated to store data of the second virtual copy. The second data of the modified primary data volume is modified after the second data is copied to the memory allocated to store data of the second virtual copy.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
The present patent application is a continuation of U.S. patent application Ser. No. 10/324,812, filed on Dec. 20, 2002 now U.S. Pat. No. 6,996,687, entitled “Method of Optimizing the Space and Improving the Write Performance of Volumes with Multiple Virtual Copies” and is incorporated by reference herein in its entirety and for all purposes.


BACKGROUND OF THE INVENTION
Many businesses rely on large-scale data processing systems for storing and processing business data. FIG. 1 illustrates (in block diagram form) relevant components of a data processing system 10. Data processing system 10 and the description thereof should not be considered prior art to the invention described or claimed herein.
Data processing system 10 includes a host node 12 coupled to data storage system 14 and data storage systems 16(1)-16(y). The term “coupled” should not be limited to what is shown within FIG. 1. Two devices (e.g., host node 12 and data storage system 14) may be coupled together directly or indirectly via a third device. Although data storage systems 14 and 16(1) appear to be coupled in series with host node 12, the present invention should not be limited thereto. Data storage systems 14 and 16(1) could be coupled together in parallel with host node 12 in an alternative embodiment. Storage systems 16(1)-16(y) may also be coupled in parallel with host node 12 in an alternative embodiment.
For purposes of explanation, data storage system includes memory 20 while data storage systems 16(1)-16(y) include memories 22(1)-22(y), respectively. Memories 20 and 22(1)-22(y) need not be contained in separate data storage systems. In an alternative embodiment, several of the memories 20 and 22(1)-22(y) may be part of a single memory unit contained within one data storage system.
Each of the data memories 20 and 22(1)-22(y) may take form in one or more dynamic or static random access memories, one or more arrays of magnetic or optical data storage disks, or combinations thereof. Data memories 20 and 22(1)-22(y) should not be limited to the foregoing hardware components; rather, these memories may take form in any hardware, software, or combination of hardware and software in which data may be persistently stored and accessed. Data memories 20 and 22(1)-22(y) may take form in a complex construction of several hardware components operating under the direction of software. The data memories may take form in mirrored hardware. It is further noted that the present invention may find use with many types of redundancy/reliability systems. For example, the present invention may be used with a redundant array of independent disks (RAID) systems. Moreover, the present invention should not be limited to use in connection with the host node of a data storage network. The present invention may find use in a storage switch or in any of many distinct appliances that can be used with a data storage system.
Data memory 20 stores data of a primary data volume. The primary data volume is the working volume of data processing system 10. Data memories 22(1)-22(y) store data or are configurable to store data of separate data volumes. For purposes of explanation, data memories 22(1)-22(y) will be described as storing data of data volume(1)-data volume(y), respectively. Each of data volume(1)-data volume(y) may be a point in time (PIT) copy of the primary data volume or a modified PIT (MPIT) copy of the primary data volume. A PIT copy, as its name implies, is a copy of the primary data volume created at some point in time. An MPIT copy is a PIT copy which contains data that was modified after creation of the PIT copy. Each of data volume(1)-data volume(y), whether PIT or MPIT, can be used to restore the primary data volume in the event of a data corruption thereof.
As will be more fully described below, each of data volume(1)-data volume(y) can be virtual or real. For example, data volume(1) is virtual when some data of data volume(1) is found stored within memory 20 rather than memory 22(1). Data volume(1) is real when all data of data volume(1) is stored in memory 22(1). A virtual data volume can be converted to a real data volume via a background data copying process performed by host node 12. In the background copying process, for example, data of the virtual data volume(1) is copied from memory 20 to memory 22(1) until all data of data volume(1) is stored in memory 22(1).
FIG. 2 represents (in block diagram form) a logical structure of data memories 20 and 22(1)-22(y). Each memory is shown having nmax memory blocks into which data can be stored. Each memory block shown in FIG. 2 represents one to an arbitrarily large number of regions in physical memory that store data. The physical memory regions of a block need not be contiguous to each other. However, the physical memory regions are viewed as logically contiguous by a data management system executing on host node 12. Any or all of memories 20 and 22(1)-22(y) may have more than nmax memory blocks.
For purposes of explanation, each block of data memory 20 stores data of the primary data volume. For purposes of explanation, the nmax memory blocks of memories 22(1)-22(y) can be allocated by host node 12 for storing data of data volumes(1)-(y), respectively. Corresponding memory blocks in data memories 20 and 22(1)-22(y) can be equal in size. Thus, memory block 1 of data memory 20 can be equal in size to memory block 1 of data memories 22(1)-22(y). Each of the memory blocks within data memory 20 may be equal in size to each other. Alternatively, the memory blocks in data memory 20 may vary in size.
Host node 12 may take form in a computer system (e.g., a server computer system) that processes requests from client computer systems (not shown). Host node 12 generates read or write data transactions that access memory 20 in response to receiving requests from client computer systems. Host node 12 is capable of accessing memories 22(1)-22(y) via read or write data transactions.
Host node 12 includes a data storage management system (not shown) that takes form in software instructions executing on one or more processors (not shown) within host node 12. The data management system includes a file system and a system for managing the distribution of data of a volume across several memory devices. Volume Manager provided by VERITAS Software Corporation of Mountain View, Calif., is an exemplary system for managing the distribution of volume data across memory devices. Volume and disk management products from other product software companies also provide a system for managing the distribution of volume data across memory devices. Hardware RAID adapter cards and RAID firmware built into computer systems likewise provide this function.
As noted above, each of data volumes(1)-(y) can be a virtual PIT or virtual MPIT copy of the primary data volume. Host node 12 creates data volumes(1)-(y) in succession beginning with data volume(1). Each of the data volumes(1)-(y) is initially created as a virtual PIT copy of the primary data volume as it exists at the time each of the data volumes(1)-(y) is respectively created. Host node 12 can create a virtual data volume according to the methods described in copending U.S. patent application Ser. No. 10/143,059 entitled “Method and Apparatus for Creating a Virtual Data Copy,” which is incorporated herein by reference in its entirety.
When host node 12 creates virtual data volumes(1)-(y), host node 12 creates valid/modified (VM) maps such as VM map 30 and VM maps 32(1)-32(y) represented in FIG. 3. VM map 30 and VM maps 32(1)-32(y) may be persistently stored in memory of host node 12 or elsewhere. VM map 30 corresponds to memory 20 while VM maps 32(1)-32(y) correspond to memories 22(y)-22(y), respectively.
VM maps 30 and 32(1)-32(y) include nmax entries of two bits each in the embodiment shown in FIG. 3. Each entry of VM map 30 corresponds to a respective block of memory 20, while each entry of VM maps 32(1)-32(y) corresponds to a respective block of data memories 22(1)-22(y), respectively. The first and second bits in each entry are designated Vn and Mn, respectively. Vn in each entry, depending upon its state, indicates whether its corresponding memory block n contains valid data. For example, when set to logical 1, V2 of VM map 30 indicates that block 2 of memory 20 contains valid primary volume data, and when set to logical 0, V2 of VM map 30 indicates that block 2 of memory 20 contains no valid primary volume data. It is noted that when Vn is set to logical 0, its corresponding memory block n may contain data, but this data is not considered valid. V2 of VM map 32(1), when set to logical 1, indicates that block 2 of memory 22(1) contains valid data of data volume(1). V2 of VM map 32(1), when set to logical 0, indicates that block 2 of memory 22(1) does not contain valid data.
Mn in each entry, depending on its state, indicates whether data within its corresponding memory block n has been modified. For example, when set to logical 1, M3 of VM map 30 indicates that block 3 of memory 20 contains data that was modified via a write data transaction since creation of a data volume. When set to logical 0, M3 via map 30 indicates that block 3 of memory 20 contains unmodified data. Likewise, M3 in VM map 32(1), when set to logical 1, indicates that block 3 in memory 22(1) contains data that was modified via a write data transaction since creation of data volume(1). When set to logical 0, M3 of VM map 32(1) indicates that block 3 of memory 22(1) contains no modified data.
When VM map 30 is first created, Vn in each entry is initially set to logical 1 thus indicating that each block n in memory 20 contains valid data of the primary volume. When each of the VM maps 32(1)-32(y) is first created, Vn and Mn of each entry is set to logical 0 thus indicating that the corresponding memory block n contains no valid or modified data. Host node can change the state of one or more bits in each map entry using single or separate I/O operations at the memory address that stores the map entry.
As noted above, host node 12 may run a background copying process to transform a virtual data volume into a real data volume. In this background copying process, host node 12 copies data of memory 20 to, for example, memory 22(1) in a block by block or blocks by blocks fashion until virtual data volume(1) is transformed into a real data volume(1). However, before the background copying process is started or completed, host node 12 can modify data of the primary data volume.
FIG. 4 illustrates relevant operational aspects of modifying data of the primary data volume via a write data transaction after creation of virtual data volumes(1)-(y). The process illustrated in FIG. 4 implements a copy-on-write procedure which is initiated in response to a client computer request to modify data of the primary data volume. More particularly, in step 40, host node 12 generates a write data transaction for modifying data in block n of primary memory 20. This write data transaction can be generated in response to the request from the client computer system to modify data of the primary data volume. For purposes of explanation, the phrase “modifying data” includes writing new data to an otherwise empty memory region. In response to generating the write data transaction, host node 12 sets variable x to 0 in step 42. Thereafter, in step 44, host node 12 increments x by 1. Thereafter, in step 46, host node accesses VM map 32(x) to determine the state of Vn therein. If Vn is set to logical 0, block n of memory 22(x) does not contain a valid copy of block n of memory 20. Accordingly, the process proceeds to step 50 where host node 12 copies the data contents of block n of primary memory 20 to block n of memory 22(x). In step 52, host node sets Vn of VM map 32(x) to logical 1.
As noted above, host node 12 must copy the contents of block n of primary memory 20 to block n in each of the memories 22(1)-22(y) if these memories do not already have a valid copy of the data in block n of memory 20. The counter x is used to check whether all of the memories 22(1)-22(y) contain a valid copy of the data of block n in memory 20. Accordingly, in step 54, host node compares the current value of x to y. If x does not equal y, then host node 12 increments x by 1 in step 44 and Vn of the next VM map 32(x) is checked to see if block n of memory 22(x) contains a valid copy of the data in block n of memory 20. Eventually, after all memories 22(1)-22(y) are checked to determine whether block n thereof contain a valid copy of block n of memory 20, x will be incremented to equal y and the process will proceed to step 56 where host node 12 sets Mn of VM map 30 to logical 1. Lastly, in accordance with the write data transaction generated in step 40, host node 12 modifies data in block n of primary memory 20.
FIG. 4 shows the VM maps 30 and 32(1)-32(y) of FIG. 3 after modification of block 3 in memory 20 using the process described in FIG. 4. As can be seen in FIG. 5, V3 in VM maps 32(1)-32(y) is set to logical 1 thus indicating that memory block 3 in memories 22(1)-22(y) contain a valid copy of data in block 3 of memory 20. Before modifying block 3 in memory 20 in accordance with step 60 of the process shown in FIG. 4, step 50 must be repeated y times to copy data from block n of memory 20 to block n of memories 22(1)-22(y). If y, the total number of virtual data volumes is large enough, a substantial delay may be created between the time host node 12 receives a request to modify data in the primary volume and the time data in block n in memory 20 is modified in step 20.
SUMMARY OF THE INVENTION
Disclosed is a method and apparatus for optimizing memory space and improving the write performance in a data processing system having a data volume with multiple virtual copies thereof. In one embodiment of the method, a first virtual copy of a primary data volume is created. Thereafter, first data of the primary data volume is modified. A second virtual copy of the primary data volume is created after modification of the first data thereof. A write-data transaction for modifying second data of the modified primary data volume is generated after creation of the second virtual copy. The second data of the modified primary data volume is copied to memory allocated to store data of the second virtual copy. The second data of the modified primary data volume is modified after the second data is copied to the memory allocated to store data of the second virtual copy.



BRIEF DESCRIPTION OF THE DRAWINGS
The present invention may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings.
FIG. 1 is a block diagram of a data processing system;
FIG. 2 shows block diagrams illustrating memory structure of storage systems shown in FIG. 2;
FIG. 3 is a block diagram of VM maps created by the host node shown in FIG. 1;
FIG. 4 is a flow chart illustrating operational aspects of the host node shown in FIG. 1 performing a write-data transaction for modifying data of the primary data volume;
FIG. 5 shows the VM maps of FIG. 3 after performing a write-data transaction according to the process illustrated in FIG. 4;
FIG. 6 is a block diagram of a data processing system employing one embodiment of the present invention;
FIG. 7 is a flow chart illustrating operational aspects of the host node shown in FIG. 6 performing a write-data transaction for modifying data of the primary data volume in accordance with one embodiment of the present invention;
FIG. 8 shows the VM maps of FIG. 3 after performing a write-data transaction according to the process illustrated in FIG. 7;
FIG. 9 is a flow chart illustrating operational aspects of the host node shown in FIG. 6 performing a read-data transaction in accordance with one embodiment of the present invention, and;
FIG. 10 is a flow chart illustrating operational aspects of the host node shown in FIG. 6 performing a write-data transaction in accordance with one embodiment of the present invention.



The use of the same reference symbols in different drawings indicates similar or identical items.
DETAILED DESCRIPTION
The present invention relates to a method and apparatus for improving the efficiency of modifying data of a volume. In one embodiment, the method is implemented as software instructions executing on one or more processors. The software instructions may be stored within a memory medium transferable to a computer system having the one or more microprocessors.
FIG. 6 illustrates a data processing system employing one embodiment of the present invention. The data processing system of FIG. 8 is the same as the data processing system 10 of FIG. 1 except host node 12 is replaced by host node 38. Host node 38, like host node 12, is capable of successively creating multiple virtual data volumes(1)-(y) which are PIT copies or MPIT copies of the primary data volume stored within memory 20. However, host node 38, as will be more fully described below, operates in a manner different compared to host node 12 when host node 12 receives a request to write data to the primary data volume from a client computer system (not shown) coupled thereto.
FIG. 7 illustrates operational aspects of host node 38 responding to a client computer request to modify data in the primary data volume according to one embodiment of the present invention. More particularly, host node 38 generates a write data transaction for modifying data in block n of primary memory 20 in step 70 in response to host node 38 receiving the request. After generating the write data transaction, host node 38 checks the status of Vn of VM map 32(y) corresponding to the most recently created virtual data volume(y) in step 72. If Vn is equal to logical 0, then memory 22(y) does not have a copy of the data contents in block n of memory 20. Accordingly, in step 74, host node 38 copies the data contents of block n in memory 20 to block n of memory 22(y). Thereafter, in step 76 host node 38 sets Vn of VM map 32(y) to logical 1. After step 76 or in response to determining that Vn of VM map 32(y) is equal to logical 1 in step 72, host node 38 sets Mn of VM map 30 to logical 1. Lastly, in step 82, host node 38 modifies the data contents of block n in primary memory 20 according to the write data transaction generated in step 70.
In the process described in FIG. 6, host node 38 copies data of block n of memory 20 only to block n of memory 22(y). In contrast, the process described in FIG. 4 may require host node 12 to copy data of block n of primary memory 22 to block n in each of the memories 22(1)-22(y). Because the process described in FIG. 6 requires only one copy process, host node 38 can respond to a request to write data to the primary data volume more quickly than host node 12 of FIG. 1. Moreover, because data of data block n is copied only to block n of the memory 22(y) in the process of FIG. 7, the process is more efficient. Also, the total amount of memory needed to implement primary data volume modification can be smaller when using the process in FIG. 6 when compared to the process shown in FIG. 4 if cache structured or space optimized storage is used. It should be noted that a cache structured or space optimized storage is not necessary for this invention to work. Other space saving storage organization techniques may also be applied. FIG. 8 illustrates the VM maps 30 and 32(1)-32(y) shown in FIG. 3 after performing a write data transaction to memory block 3 of memory 20 in accordance with the process shown in FIG. 6. In contrast to FIG. 5, only Vn of VM map 32(y) is set to logical 1.
Host node 38 is capable of reading data from any of the virtual data volumes (1)-(y). FIG. 8 illustrates operational aspects of one embodiment employed by host node 38 for reading data from one of the virtual data volumes. More particularly, in step 90, host node 38 generates a read data transaction for reading data from block n of memory 22(x) where x is any number from 1-y. When host node 38 generates the read data transaction, host node 38 accesses VM map 32(x) in step 92 to determine the state of Vn therein. If Vn is set to logical 0, then the data sought to be read by host node 38 is not contained within block n of memory 22(x). Presuming Vn is set to logical 0 in step 92 host node 38 determines whether x is equal to y in step 94. If x does not equal y, host node 38 increments x by 1 and the process repeats with step 92 where host node 38 again checks the value of Vn in the next VM map 32(x). At some point, Vn will equal logical 1 in step 92 or x will compare equally to y in step 94. If Vn in VM map 32(x) equates to logical 1 in step 92, then data is read from block n of memory 22(x) and returned to host node 38 as the data sought, and the process ends. If x equates equally to y in step 94, then data is read from block n of memory 20 and returned as the data sought, and the process ends.
As noted above, host node 38 is capable of modifying data of any of the virtual data volumes (1)-(y). FIG. 10 illustrates operational aspects of host node 38 modifying data in one of virtual data volumes (1)-(y). More particularly, in step 110, host node 38 generates a write data transaction for modifying data in block n of memory 22(x) where x is a number from 1 to y. In response to step 110, host node 38 accesses VM map 32(x) to determine the state of Vn therein. If Vn in VM map 32(x) is equal to logical 1, host node 38 in step 130 writes data to block n of memory 22(x) according to the write-data transaction and the process ends. If Vn in VM map 32(x) is equal to logical 0 in step 112, the process proceeds to step 114 where host node 38 compares x to 1. If x does not equal 1, host node 38 sets variable z to x−1 in step 116. In step 120, host node 38 checks the value of Vn of VM map 32(z). If Vn equals logical 0 in step 120, data to be modified must be retrieved from block n of memory 22(z) using the read process of FIG. 9 as shown in step 122. Thereafter, in step 124, host node 38 writes the data read in step 122 to memory 22(x) and sets Vn of VM map (z) to logical 1. After step 124 or in response to a determination that x equals 1 in step 114, host node 38 writes data to block n of memory 22(x) and sets Vn of VM map (x) to logical 1 in step 126 and the process ends.
Although the present invention has been described in connection with several embodiments, the invention is not intended to be limited to the specific forms set forth herein. On the contrary, it is intended to cover such alternatives, modifications, and equivalents as can be reasonably included within the scope of the invention as defined by the appended claims.

## Claims

1. A method comprising:
creating y virtual data volumes, wherein y is a number greater than 2, and wherein the yth virtual data volume is the most recently created of the y virtual data volumes, wherein the y virtual data volumes comprise y virtual copies, respectively, of a primary data volume;
copying first data of the primary data volume to memory allocated to store data of the yth virtual data volume;
modifying the first data of the primary data volume after the first data is copied to the memory allocated to store data of the yth virtual data volume;
wherein, before the first data of the primary volume is modified, the first data is copied only to the memory allocated to store data of the yth virtual data volume;
after the first data of the primary volume is modified, copying the first data from the memory allocated to store data of the yth virtual data volume to memory allocated to store data of one of the other y virtual data volumes in response to a generation of a write-data transaction for modifying data of the one of the other y virtual data volumes.

2. The method of claim 1 wherein the first data of the primary volume is copied to memory allocated to store data of the yth virtual data volume in response to a generation of a write-data transaction for modifying first data of the primary data volume, wherein the write-data transaction is generated after creation of the y virtual data volumes.

3. The method claim 1 wherein the yth virtual data volume is a virtual copy of the primary data volume and wherein the yth virtual data volume is created before modification of the first data of the primary data volume.

4. A computer readable medium comprising instructions executable by a computer system, wherein the computer system implements a method in response to executing the instructions, the method comprising:
sequentially creating y virtual data volumes, wherein y is a number greater than 2, and wherein the yth virtual data volume is the most recently created of the y virtual data volumes, wherein the y virtual data volumes comprise y virtual copies, respectively, of a primary data volume;
copying first data of the primary data volume to memory allocated to store data of the yth virtual data volume;
modifying the first data of the primary data volume after the first data is copied to the memory allocated to store data of the yth virtual data volume;
wherein, before the first data of the primary volume is modified, the first data is copied only to the memory allocated to store data of the yth virtual data volume;
generating a read-data transaction for reading data from one of the y virtual data volumes;
accessing memory allocated to store data of the yth virtual data volume in response to generating the read-data transaction;
reading data from the accessed memory.

5. The computer readable medium of claim 4 wherein the first data of the primary volume is copied to memory allocated to store data of the yth virtual data volume in response to a generation of a write-data transaction for modifying first data of the primary data volume, wherein the write-data transaction is generated after creation of the y virtual data volumes.

6. The computer readable medium of claim 4 wherein the method further comprises after the first data of the primary volume is modified, copying the first data from the memory allocated to store data of the yth virtual data volume to memory allocated to store data of one of the other y virtual data volumes.

7. The computer readable medium of claim 4 wherein the yth virtual data volume is a virtual copy of the primary data volume and wherein the yth virtual data volume is created before modification of the first data of the primary data volume.

8. The computer readable medium of claim 4 wherein the method further comprises:
generating a read-data transaction for reading data from another of the y virtual data volumes;
accessing memory allocated to store data of the primary data volume in response to generating the read-data transaction for reading data from the other of the y virtual data volumes;
reading data from the accessed memory.

9. The computer readable medium of claim 4 wherein the method further comprises:
generating a write-data transaction for modifying data of one of the y virtual data volumes, wherein the one of the y virtual data volumes is distinct from the yth virtual data volume;
copying the first data stored in the memory allocated to store data of the yth virtual data volume to memory allocated to store data of the one of the y virtual data volumes;
modifying the first data stored in the memory allocated to store data of the one of the y virtual data volumes.

10. An apparatus comprising:
a primary memory for storing a primary data volume;
y secondary memories wherein y is a number greater than 2;
a computer system in data communication with the primary and the y secondary memories, the computer system comprising a computer readable medium for storing instructions executable by the computer system, wherein the computer system implements a method in response to executing the instructions, the method comprising:
creating y virtual data volumes, wherein the yth virtual data volume is the most recently created of the y virtual data volumes, wherein the y virtual data volumes comprise y virtual copies, respectively, of the primary data volume;
allocating the yth secondary memory to store data of the yth virtual copy;
copying the first data of the primary data volume to the yth secondary memory;
modifying the first data of the primary data volume after the first data is copied to the yth secondary memory;
wherein, before the first data of the primary volume is modified, the first data is copied only to the yth secondary memory;
allocating another of the y secondary memories to store data of another of the y virtual data volumes;
after the first data of the primary volume is modified, copying the first data from the yth secondary memory to the other of the y secondary memories in response to a generation of a write-data transaction for modifying data of the other of the y virtual data volumes.

11. The apparatus of claim 10 wherein the first data of the primary volume is copied to memory allocated to store data of the yth virtual data volume in response to a generation of a write-data transaction for modifying first data of the primary data volume, wherein the write-data transaction is generated after creation of the y virtual data volumes.