Incremental backup of a data volume

[0001] The present patent application is a continuation of U.S. patent application Ser. No. 10/264,934, filed on Oct. 4, 2002, now U.S. Pat. No. 6,938,135, entitled “INCREMENTAL BACKUP OF A DATA VOLUME” and is incorporated by reference herein in its entirety and for all purposes.

[0002] Many modern businesses rely on large-scale data processing systems for storing and processing their data. Often, the viability of a business depends on the accuracy of the data volume it stores within its data processing system. Data volumes are often corrupted as a result of human operator error or software problems. Data volume corruption results in storing false data or the deletion of needed data. Businesses must stand ready to correct data volume corruptions. Moreover, businesses that rely heavily on their data processing systems must stand ready to correct data volume corruption in the shortest amount of time possible.

[0003] Businesses often store their data in one or more data volumes. A data volume is a collection of files that store data. When an unexpected corruption occurs within a data volume, businesses can restore the data volume to its state just prior to corruption using a previously created backup copy of the data volume. To illustrate, FIG. 1 is a block diagram illustrating the relevant components of an exemplary data processing system 10 having a host node 12, and data storage systems 14 and 16. Data storage systems 14 and 16 include data memories 24 and 26, respectively. The data processing system 10 shown in FIG. 1 and the description thereof should not be considered prior art to the invention described or claimed herein.

[0004] Data memories 24 and 26 store data volumes. More particularly, data memory 24 stores a primary data volume while data memory 26 stores a point-in-time (PIT) backup copy of the primary data volume. The primary data volume is the working data volume of data processing system 10, while the PIT backup copy, as its name implies, is a copy of the primary data volume created at a point in time. The PIT backup copy can be used to restore the primary data volume after a corruption thereof, as will be more fully described below.

[0005] Host node takes form in a computer system (e.g., the server computer system) that receives and processes requests to read or write data to the primary data volume. The requests are received from client computer systems (not shown) coupled to host node 12. In response to receiving the requests to read or write data, host node 12 generates read or write-data transactions for reading or writing data to one or more addresses within data memory 24. A copy of each request to write data to the primary data volume or a copy of each write-data transaction generated by host node 12, is stored in a write-data transaction log (not shown). The contents of this log are flushed each time host node 12 backs up the primary data volume. Host node 12 backs up the primary data volume by creating an initial PIT backup copy of the primary data volume or by refreshing the PIT backup copy. These processes are more fully described below.

[0006] Occasionally, host node 12 unwittingly generates an invalid or erroneous write-data transaction. This write-data transaction corrupts the primary data volume stored in memory 24 by inadvertently deleting data or overwriting good data with false data. When the data corruption is discovered, host node 12 can use the PIT backup copy in data memory 26 and the write-data transactions stored in the write-data transaction log to restore the primary data volume in memory 24 to this state it occupied just before the data corrupting event.

[0007] In the restore process, host node 12 applies all write-data transactions held in the write-data transaction log to the PIT backup copy, up to but not including the write-data transaction that caused the data corruption. After host node 12 finishes applying the appropriate logged write-data transactions, the PIT backup copy should be transformed into a copy of the primary data volume at the point in time just before execution of the invalid or erroneous write-data transaction. Host node 12 completes the restore process by synchronizing the corrupted primary data volume in memory 24 with the modified PIT copy in data memory 26. Synchronization includes overwriting each block of data memory 24 with the contents of its corresponding block in data memory 26. After the primary data volume is restored, host node 12 can resume access via read and write-data transactions.

[0008] When creating the first PIT backup copy in memory 26, host node 12 copies data from each block of data memory 24 that stores primary data volume data to a respective block of data memory 26 until the entire content of the primary data volume is copied into memory 24. Almost all data copied to data memory 26 can be compressed using a lossless compression algorithm to decrease the time needed to successfully complete the backup operation.

[0009] The primary data volume is typically backed up once a day to capture changes to the data line that occurred during the day. In backup operations subsequent to the first, host node 12 could copy the entire contents of the primary data volume to data memory 26 in the block by block copy process described above. Copying the entire contents of the primary data volume to memory 26, however, could be a time-consuming process during which access to the primary data volume is denied other than for the backup operation itself.

[0010] Not all blocks in memory 24 that store primary data volume data are changed during the course of the day. As such, the entire content of the primary data volume need not be copied to data memory 26 when performing backup operations subsequent to the first backup operation. In an alternative embodiment, host node 12 performs successive backup operations of the primary data volume by refreshing the previously generated PIT backup copy in memory 26. In this alternative, host node 12 maintains a map that tracks memory blocks in data memory 24 that store primary data volume. Each time a write-data transaction writes data to a memory block in data memory 24, host node 12 sets a bit in the map corresponding to the memory block. In this fashion, host node 12 knows which blocks of data memory 24 have been modified since the last time the primary data volume was backed up. Using this map, host node 12 need only copy to memory 26 those corresponding blocks in memory 24 that contain new or modified data of the primary data volume. This alternative process reduces the time needed to backup the primary data volume. However, host node 12 is still denied access to data memory 24 other than for backing up the contents of the primary data volume. Because host node 12 is denied access to the primary data volume, host node cannot service requests to read or write data received from client computer systems coupled thereto.

[0011] Disclosed is a method and apparatus for incrementally baking up a data volume. In one embodiment of the method, the data volume is created in a first memory, and a point-in-time (PIT) copy of the data volume is created at time T0. First data of the data volume is modified between times T0 and T1, wherein time T1 is subsequent to time T0. Second data of the data volume is copied to a second memory after time T1. The second data of the data volume is modified after the second data is copied to the second memory. Lastly, data of the PIT copy is overwritten with (1) the copy of the second data stored in the second memory and (2) the modified first data of the data volume.

[0021] The use of the same reference symbols in different drawings indicates similar or identical items.

[0022] The present invention relates to an apparatus and method for incrementally backing up a data volume. FIG. 2 illustrates (in block diagram form) relevant components of a data processing system 30 deploying one embodiment of the present invention. Data processing system 30 includes a host node 32 coupled to data storage systems 34-38. Data storage systems 34-38 include data memories 44-48, respectively. Host node 32 can store, access and process data stored in each of the data memories 44-48. The definition of the term “coupled devices” should not be limited to two devices coupled directly together. Two devices (e.g., host node 32 and data storage system 34) may be coupled together via a third device (not shown).

[0023] Data memory 44 stores the contents of a primary data volume of data processing system 30, while data memory 46 stores a PIT backup copy of the primary data volume. The PIT backup copy may be real or virtual as will be more fully described below. The use of data memory 48 will also be more fully described below.

[0024] The primary data volume in memory 44 is the working data volume of data processing system 30, while the PIT backup copy in memory 46 is a copy of the primary data volume created at a point in time. Although the present invention will be described with reference to creating a PIT backup copy in a data storage system (i.e. data storage system 36) separate from the data storage system that stores the primary data volume, it is understood that the present invention should not be limited thereto. For example, the PIT backup copy could be stored within data memory 44 along the primary data volume.

[0025] The primary data volume is a collection of files that store data. While it is said that files store data, in reality the data of the primary volume is stored in blocks of data memory 44 allocated to the files by host node 32. Data memories 44-48 may take form in one or more dynamic or static random access memories (RAM), one or more arrays of magnetic or optical data storage disks, or combinations thereof. Data memories 44-48 should not be limited to the foregoing hardware components; rather, data memories 44-48 may take form in any hardware, software, or combination of hardware and software in which data may be accessed and persistently stored. Data memories 44-48 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 redundancies/reliability systems. For example, the present invention may be used with redundant array of independent disks (RAID) systems. Moreover, the present invention should not be limited to use and connection with the host node of the 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.

[0026] Host node 32 may take form in a computer system (e.g., a server computer system) that receives and processes requests to read or write data to the primary data volume. The requests may be received by host node 32 from client computer systems (not shown) coupled thereto. Host node 32 includes a data storage management system (not shown) that takes in instructions executing in one or more processors within host node 32. The data management system may include a file system (not shown) and a system (not shown) for managing the distribution of the primary data volume across several memory devices of data memory 44 in addition for managing the distribution of data of the PIT backup copy across several memory devices of data memory 46. Volume Manager™ provided by Veritas Software Corporation of Mountain View, Calif., is an exemplary system for managing the distribution of volume data across several memory devices.

[0027] FIG. 3 represents (in block diagram form) a logical structure of data memories 44-48. Each of the data memories 44-48 includes n_max memory blocks into which data can be stored. For purposes of explanation, each block of data memory 44 is allocated to and stores data of the primary data volume. Although the blocks of each memory are shown contiguous in FIG. 3, the present invention should not be limited thereto. For example, memory blocks allocated to the primary data volume may be distributed across several memory devices that form data memory 44. Moreover it is noted that any or all of memories 44-48 may have more than n_max memory blocks. The first n_max blocks of data memories 44 and 46, however, are allocated by host node 32 for storing the primary data volume and the PIT backup thereof, respectively. Corresponding memory blocks in data memories 44-48 are equal in size. Thus, memory block 1 of data memory 44 is equal in size to memory block 1 of data memories 46 and 48. Each of the memory blocks within data memory 44 may be equal in size to each other. Alternatively, the memory blocks in data memory 44 may vary in size.

[0028] Host node generates read and write-data transactions, as noted above, in response to receiving and processing requests from client computer system to read and write data to the primary data volume. The read or write-data transactions result in I/O operations to data memory 44. Data storage system 34 (FIG. 2) returns primary volume data to host node 32 in response to receiving a read data transaction therefrom, or data storage system 34 returns an acknowledgement to host node 32 that data has been successfully stored in response to receiving a write-data transaction therefrom.

[0029] Host node 32 is capable of creating a virtual PIT backup copy of the primary data volume stored in data memory 44. Creating a virtual copy of a data volume is more fully described in co-pending 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. Virtual data volume copies can be instantly created. Once the virtual PIT backup copy is created in memory 46, host node 32 can access either the primary data volume or its virtual PIT backup copy. The virtual PIT backup copy in data memory 46 can eventually be transformed into a real or actual PIT backup copy of the Primary data volume using a background data copying process which will be described below. The primary data volume in data memory 44 (and the virtual PIT backup copy in data memory 46) can be immediately accessed by read and/or write-data transactions generated by host node 32 before the virtual PIT backup copy is transformed into an actual or real PIT backup copy. This concept is more fully described in co-pending U.S. patent application Ser. No. 10/143,059 or in co-pending U.S. patent application Ser. No. 10/254,753 entitled “Method And Apparatus For Restoring a Corrupted Data Volume,” filed Sep. 25, 2002, which is incorporated herein by reference in its entirety. The PIT backup copy can be refreshed to assume the new point in time image of the primary data volume. This concept is more fully described in U.S. patent application Ser. 10/326,427 entitled Instant Refresh Operation Of A Data Volume Copy.

[0030] In one embodiment, host node 32 creates the virtual PIT backup copy in memory 46 by creating a pair of valid/modified (VM) maps such as VM maps 52 and 54 illustrated in FIG. 4. VM maps 52 and 54 correspond to the primary data volume and the virtual PIT backup copy thereof, respectively. VM maps 52 and 54 can be allocated by host node 32 in memory of host node 32 or elsewhere. VM maps 52 and 54 include n_max entries of two bits each in the embodiment shown. Each entry of VM map 52 corresponds to a respective block of data memory 44, while each entry of VM map 54 corresponds to a respective block of data memory 46.

[0031] The first and second bits in each entry of VM maps 52 and 54 are designed V_n and M_n, respectively. V_n in each entry, depending on its states, indicates whether the corresponding block n of the associated memory contains valid data. For example, when set to logical 1, V₂ of VM map 52 indicates that block 2 of data memory 44 contains valid primary volume data, and when set to logical zero V₂ of VM map 52 indicates that block 2 of data memory 44 contains no valid primary volume data. It is noted that when V_n is set to logical zero, the corresponding memory block n may contain data, but the data is not considered valid. V₂ of VM map 54, when set to logical one, indicates that block 2 of data memory 46 contains a valid copy of data that existed in block 2 of memory 44 at the time the PIT backup copy was first created or at the time the PIT backup copy was last refreshed. V₂ of VM map 54, when set to logical zero, indicates that block 2 of data memory 46 does not contain a valid copy of data of the primary data volume.

[0032] M_n in each entry, depending upon its date, indicates whether data within the corresponding block n of the associated memory has been modified since some point in time. For example, when set to logical 1, M₃ of VM map 52 indicates that block 3 of data memory 44 contains data that was modified via a write-data transaction since the time the PIT backup copy in memory 46 was first created or since the last time the PIT backup copy was refreshed. When set to logical 0, M₃ Of VM map 52 indicates that data has not been modified in block 3 of memory 44 since the time the PIT backup copy in memory 46 was first created or since the last time the PIT backup copy was refreshed. It is noted that the term data modification of a memory block includes overwriting existing data or adding new data to the memory block. As will be more fully described below, all M_n bits of VM map 52 will be cleared to logical 0 when the PIT backup copy in data memory 46 is refreshed.

[0033] When VM map 52 and 54 are first created by host node 32, each entry of map 54 is set to logical 0, thus indicating that the n_max blocks of data memory 46 contain no valid or modified data. For purposes of explanation, it is presumed that each of the n_max blocks in memory 44 contains valid data of the primary data volume. Accordingly, V_n of each entry map 52 is initially set to logical 1. Lastly, M_n of each entry in VM map 52 is initially set to logical 0. Host node 32 can change the state of each or both bits of the map entry using a single write operation to the memory address that stores the map entry.

[0034] Host node 32 creates the virtual PIT backup copy in memory 46. The PIT backup copy in memory 46 is virtual to the extent that the PIT backup copy is less than a full copy of the primary data volume. Host node 32 may run a background data copying process to copy the data contents of data memory 44 to data memory 46 in a block by block manner while host node 32 accesses the primary data volume with read or write-data transactions. Eventually this background process will completely copy the contents of the primary data volume into memory 46, thus transforming the virtual PIT backup copy in data memory 46 into a real PIT backup copy.

[0035] FIG. 4 shows that each V_n bit in map 54 is set to logical 1 thus indicating that the entire contents of the primary data volume has been backed up into data memory 46 either through the background copying process itself or by combination of the background copying process and a copy-on-write process more fully described with reference to FIG. 5. The copy on write process described in FIG. 5 is initiated in response to host node 32 receiving a request to write data to the primary volume from a client computer system coupled thereto. This request is received after creation of VM maps 52 and 54. In response to receiving the requests to write data, host node 32 generates a write-data transaction for writing the data to a block n of memory 44, where block n is specified by, for example, the file system executing within host node 32. Host node 32 then accesses VM map 54 to determine whether V_n is set to logical 1 in step 62. If V_n is set to logical 0, then in step 64 host node 32 copies the data contents of block n of memory 44 to block n of memory 46. In step 66, host node 32 sets V_n of VM map 54 to logical one. If V_n of VM map 54 is set to logical 1 in step 62 or after V_n of VM map 54 is set to logical 1, in step 66 host node accesses and sets the M_n bit of VM map 52 to logical 1 as shown in step 70. Thereafter, data is written to block n of memory 44 in accordance with the write-data transaction of step 60. FIG. 4 shows that M₁, M₃, and M₅ are set to logical 1 thus indicating that the contents of blocks 1, 3, and 5, respectively, of memory 44 were the subject of write-data transactions after, for example, initial creation of the virtual PIT copy within data memory 46. Further, it is noted that the contents of blocks 1, 3, and 5 of memory 44 may have been modified before the virtual PIT backup copy was transformed into a real PIT backup copy.

[0036] Host node 32 is capable of incrementally backing up the primary data volume one or more times each day in order to capture changes that occurred to the primary data volume during the course of the day. In other words, host node 32 is capable of refreshing the PIT backup copy one or more times each day after a real PIT backup copy has been formed within memory 46. Host node 32, in response to a backup instruction internally generated or received from a source external to host node 32 at time T1, initiates the incremental backup operation by instantly creating a virtual PIT copy of the primary data volume. In creating the virtual PIT copy at T1, host node 32 creates VM maps 80 and 82 shown within FIG. 6 in memory after allocation thereof. VM maps 80 and 82 include n_max entries corresponding to n_max entries of memories 44 and 48, respectively (see FIG. 3). Each entry of VM map 80 and 82, like VM maps 52 and 54, includes V_n and M_n entries. V_n in VM map 82, depending on its state, indicates whether the corresponding block n of memory 48 contains valid data. For example, when set to logical 1, V₃ of VM map 82 indicates that block 3 of memory 48 contains a valid copy of the contents that existed in block 3 in memory 44 at time T1. When set to logical 0, V₃ of VM map 82 indicates that block 3 of memory 48 contains no valid copy of the primary data volume stored within memory 44.

[0037] Initially, each entry of VM maps 80 and 82 is set to logical 0. Shortly after time T1, host node 32 copies the content of VM map 52 into VM map 80. Thereafter, host node clears each M_n bit of map 52. At that point, host node 32 can begin servicing requests to read or write data to the primary data volume. FIG. 7 illustrates operational aspects of servicing a request, received from a client computer system coupled to host node 32, to write data to the primary data volume. More particularly, in step 94, host node 32 generates a write-data transaction for writing data to block n of memory 44. Host node 32 accesses VM map 82 to determine whether V_n is set to logical 1 in step 96. If V_n of VM map 82 is set to logical 0, then in step 100 host node 32 copies the contents of block n of memory 44 to block n of memory 48 as shown in step 100. It is noted that block n of memory 44 may have been modified since the PIT backup copy was created in memory 46. In steps 102 and 104, host node sets V_n and M_n of VM map 82 and VM map 52, respectively, to logical 1. If V_n of VM map 82 is set to logical 1 in step 96 or after V_n of VM map 82 is set to logical 1 in step 102, data is written to block n of memory 44 according to the write-data transaction generated in step 94, as shown in step 106.

[0038] Before, during, or after host node 32 services a request to write data according to the copy-on-write process described in FIG. 7, host node 32 begins the incremental backup process. FIG. 8 illustrates operational aspects of one embodiment of the incremental backup process. More particularly, in step 110, host node sets variable n to 0. Thereafter, instep 112, host node increments n by 1. In step 114, host node 32 accesses VM map 82 to determine whether V_n is set to logical 1. If V_n of VM map 82 is set to logical 1 then host node 32 determines the state of M_n in VM map 80 as shown in step 116. If M_n is set to logical 1 in step 116, then host node 32 copies the data contents of block n in memory 48 to block n of memory 46 as shown in step 118. If M_n of VM map 80 is set to logical 0 in step 120, host node 32 skips step 118.

[0039] If, in step 114, V_n of VM map 82 is set to logical 0, host node 32 determines the state of M_n in VM map 80 as shown in step 122. If M_n is set to logical 1 in step 122, then host node 32 copies the data contents of block n in memory 44 to block n of memory 46 as shown in step 124. If M_n of VM map 80 is set to logical 0 in step 122, host node 32 skips step 124.

[0040] After step 116, 118, 122, or 124, host node compares variable n to n_max in step 120. If n does not equal n_max, then the process returns to step 112 where n is incremented by 1. If, however, n equals n_max in step 120, then host node 32 sets all V_n bits of VM map 82 to logical 1 as shown in step 126.

[0041] Using the copy-on-write process shown in FIG. 7 and the incremental backup process shown in FIG. 8, host node 32 can incrementally back up the primary data volume (or refresh the PIT backup copy) while servicing requests to read or write data to the primary data volume. Once the point in time backup copy in memory 46 has been refreshed, host node 32 can discard VM maps 80 and 82. When the maps 80 and 82 are discarded, the condition in step 96 of FIG. 7 should evaluate to Yes since steps 100 and 102 are no longer required. VM map 52 tracks the changes to the primary data volume subsequent to T1 via the copy-on-write process of FIG. 7 subsequent. As such, the PIT backup copy in memory 46 can be refreshed at a later time T2. At time T2, host node recreates VM maps 80 and 82 with all bits initialized to logical 0, host node copies the contents of VM map 52 to VM map 80, and host node initiates the copy-on-write and incremental backup processes of FIGS. 7 and 8, respectively.

[0042] It is noted that in an alternative embodiment, host node 32 can incrementally back up the primary data volume by creating a single VM table having n_max entries, each entry having a V_n and M_n bit. In this alternative VM map, each V_n bit corresponds to a respective memory block of memory 48, while each M_n corresponds to a respective memory block of memory 44. Once this alternative VM map is created, host node 32 can set the state of the M_n bits in the alternative VM map to the state of the M_n bits, respectively, of VM map 52. Like the embodiment described above, host node 32 can then clear each of the M_n bits of VM map 52. The copy-on-write process described in FIG. 7 is followed except that step 96 is replaced with the step whereby a host node 32 determines the state of V_n in the alternative VM map as opposed to VM map 82, and in step 102 host node 32 sets V_n of the alternative map to logical 1 rather than setting V_n of the VM map 82. Further, in the incremental backup process described in FIG. 8, V_n of the alternative VM map is checked in step 114 as opposed to V_n of VM map 82, and host node 32 checks the state of M_n of the alternative map in step 116,122 rather than M_n of VM map 80.

[0043] Although the present invention has been described in connection with several embodiments, the invention is not intended to be limited to the embodiments described 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.