Virtual defragmentation in a deduplication vault

Virtual defragmentation in a deduplication vault. In one example embodiment, a method of virtual defragmentation in a deduplication vault includes a virtual defragmentation phase. The virtual defragmentation phase includes accessing file system metadata (FSM) blocks included in a backup of allocated blocks of a source storage and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in a deduplication vault storage.

FIELD

The embodiments disclosed herein relate to virtually defragmenting a backup of a source storage stored in a deduplication vault storage.

BACKGROUND

A storage is computer-readable media capable of storing data in blocks. Storages face a myriad of threats to the data they store and to their smooth and continuous operation. In order to mitigate these threats, a backup of the data in a storage may be created at a particular point in time to enable the restoration of the data at some future time. Such a restoration may become desirable, for example, if the storage experiences corruption of its stored data, if the storage becomes unavailable, or if a user wishes to create a second identical storage.

A storage is typically logically divided into a finite number of fixed-length blocks. A storage also typically includes a file system which tracks the locations of the blocks that are allocated to each file that is stored in the storage. The file system also tracks the blocks that are not allocated to any file as unallocated blocks. The file system generally tracks allocated and unallocated blocks using specialized data structures, referred to as file system metadata (FSM). FSM is also stored in designated blocks in the storage (FSM blocks).

Various techniques exist for backing up a source storage. One common technique involves backing up individual files stored in the source storage on a per-file basis. This technique is often referred to as file backup. File backup uses the file system of the source storage as a starting point and performs a backup by writing the files to a backup storage. Using this approach, individual files are backed up if they have been modified since the previous backup. File backup may be useful for finding and restoring a few lost or corrupted files. However, file backup may also include significant overhead in the form of bandwidth and logical overhead because file backup requires the tracking and storing of information about where each file exists within the file system of the source storage and the backup storage.

Another common technique for backing up a source storage ignores the locations of individual files stored in the source storage and instead simply backs up all allocated blocks stored in the source storage. This technique is often referred to as image backup because the backup generally contains or represents an image, or copy, of the entire allocated contents of the source storage. Using this approach, individual allocated blocks are backed up if they have been modified since the previous backup. Because image backup backs up all allocated blocks of the source storage, image backup backs up both the blocks that make up the contents of the files stored in the source storage (data blocks) as well as the blocks that make up the file system metadata (FSM blocks). Also, because image backup backs up all allocated blocks rather than individual files, this approach does not generally need to be aware of the file system metadata or the files stored in the source storage, beyond utilizing minimal knowledge of the file system metadata in order to only back up allocated blocks since unallocated blocks are not generally backed up.

An image backup can be relatively fast compared to file backup because reliance on the file system is minimized. An image backup can also be relatively fast compared to a file backup because seeking is reduced. In particular, during an image backup, blocks are generally read sequentially with relatively limited seeking. In contrast, during a file backup, blocks that make up the contents of individual files may be scattered, resulting in relatively extensive seeking.

One common problem encountered when backing up multiple similar source storages to the same backup storage using image backup is the potential for redundancy within the backed-up data. For example, if multiple source storages utilize the same commercial operating system, such as WINDOWS® XP Professional, they may store a common set of system files which will have identical blocks. If these source storages are backed up to the same backup storage, these identical blocks will be stored in the backup storage multiple times, resulting in redundant blocks. Redundancy in a backup storage may increase the overall size requirements of backup storage and increase the bandwidth overhead of transporting data to the backup storage.

SUMMARY

In general, example embodiments described herein relate to virtually defragmenting a backup of a source storage stored in a deduplication vault storage. The example methods disclosed herein may be employed to reorder block references in file system metadata (FSM) blocks included in a backup of a source storage to match the order of the corresponding blocks as stored in a deduplication vault storage. Reordering block references in the FSM blocks of a backup of the source storage to match the order of the corresponding blocks in the vault storage may decrease the fragmentation of the data between the original order of the blocks in the source storage and the backup order of the blocks as backed up in the vault storage. This reordering of block references in the FSM blocks of a backup may decrease the amount of time necessary to subsequently restore the backup to a restore storage due to a decrease in the amount of seeking that must be performed at the vault storage and at the restore storage during the restore operation.

In one example embodiment, a method of virtual defragmentation in a deduplication vault includes a virtual defragmentation phase. The virtual defragmentation phase includes accessing FSM blocks included in a backup of allocated blocks of a source storage and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in a deduplication vault storage.

In another example embodiment, a method of multiphase deduplication includes an analysis phase, a backup phase, and a virtual defragmentation phase. The analysis phase includes analyzing each allocated block, including FSM blocks and data blocks, stored in a source storage at a point in time to determine if the block is duplicated in a vault storage. The backup phase is performed after completion of the analysis phase and includes storing, in the vault storage, a backup including each unique nonduplicate allocated block from the source storage. The virtual defragmentation phase includes accessing the FSM blocks that are included in the backup and reordering block references in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage.

In yet another example embodiment, a method of multiphase deduplication includes an analysis phase, a backup phase, a virtual defragmentation phase, and a restore phase. The analysis phase includes analyzing each allocated block, including FSM blocks and data blocks, stored in a source storage at a point in time to determine if the block is duplicated in a vault storage. The backup phase is performed after completion of the analysis phase and includes storing, in the vault storage, a backup including each unique nonduplicate allocated block from the source storage. The virtual defragmentation phase includes accessing the FSM blocks that are included in the backup and reordering block references corresponding to data blocks in the FSM blocks to match the order of the corresponding blocks as stored in the deduplication vault storage. The block references for each set of local duplicate data blocks that are included in the backup are reordered as a run in the reordered FSM blocks. The restore phase is performed after the completion of the virtual defragmentation phase and includes reading, from the vault storage, and storing, in a restore storage, each allocated block that was stored in the source storage at the point in time in the position indicated in the reordered FSM blocks. Each of the runs of local duplicate data blocks is stored in the restore storage as indicated in the reordered FSM blocks.

DESCRIPTION OF EMBODIMENTS

In general, example embodiments described herein relate to virtually defragmenting a backup of a source storage stored in a deduplication vault storage. The example methods disclosed herein may be employed to reorder block references in file system metadata (FSM) blocks included in a backup of a source storage to match the order of the corresponding blocks as stored in a deduplication vault storage. Reordering block references in the FSM blocks of a backup of the source storage to match the order of the corresponding blocks in the vault storage may decrease the fragmentation of the data between the original order of the blocks in the source storage and the backup order of the blocks as backed up in the vault storage. This reordering of block references in the FSM blocks of a backup may decrease the amount of time necessary to subsequently restore the backup to a restore storage due to a decrease in the amount of seeking that must be performed at the vault storage and at the restore storage during the restore operation.

The term “storage” as used herein refers to computer-readable media, or some logical portion thereof such as a volume, capable of storing data in blocks. The term “block” as used herein refers to a fixed-length discrete sequence of bits. The term “run” as used herein refers to one or more blocks physically stored contiguously in a storage. The term “backup” when used herein as a noun refers to a copy or copies of one or more blocks from a storage. The phrase “virtually defragmenting a source storage to match a vault storage” or phrases equivalent thereto as used herein refer to reordering block references in FSM blocks included in a backup of a source storage to match the order of the corresponding blocks as stored in a deduplication vault storage. This “virtual defragmenting of a source storage” is distinct from file-centric defragmenting where blocks that make up the contents of a file that are initially stored in a storage in a non-contiguous fashion are reordered in the storage itself to place the blocks in a physically contiguous order in the storage. However, “virtual defragmenting of a source storage” may result in file-centric defragmentation, especially where blocks from matching files have been previously stored in the vault stored in a file-centric defragmented fashion. It is understood, of course, that a file-centric defragmentation of a source storage may additionally be performed prior to the “virtual defragmenting of a source storage” disclosed herein in order to place nonduplicate blocks in a file-centric defragmented order so that the nonduplicate blocks are stored in the vault storage in a contiguous order such that when identical blocks are reordered in other source storages (from identical files stored in the other source storages, for example) during the “virtual defragmenting” of the other source storages, the identical blocks will be reordered in a file-centric defragmented fashion. The term “FSM blocks” as used herein refers to blocks that include FSM, including blocks that include at least some portion of a file system file allocation table (FSFAT) or at least some portion of a file system block allocation map (FSBAM). The term “data blocks” as used herein refers to blocks that make up the contents of a file.

FIG. 1is a schematic block diagram illustrating an example deduplication backup system100. As disclosed inFIG. 1, the example system100includes a deduplication vault system102, a source system104, and a restore system106. The systems102,104, and106include storages108,110, and112, respectively. The deduplication vault system102also includes a database114, metadata116, and a deduplication module118. The source system104also includes a virtual defragmentation module120. The systems102,104, and106are able to communicate with one another over a network122.

Each of the systems102,104, and106may be any computing device capable of supporting a storage and communicating with other systems including, for example, file servers, web servers, personal computers, desktop computers, laptop computers, handheld devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, smartphones, digital cameras, hard disk drives, and flash memory drives. The network122may be any wired or wireless communication network including, for example, a Local Area Network (LAN), a Metropolitan Area Network (MAN), a Wide Area Network (WAN), a Wireless Application Protocol (WAP) network, a Bluetooth network, an Internet Protocol (IP) network such as the internet, or some combination thereof.

The storages108,110, and112include file system metadata (FSM)124,126, and128, respectively, which may be stored in designated blocks in the storages (FSM blocks). Similarly, each of a base backup and multiple incremental backups of the source storage110that is stored in the vault storage108includes a copy of the FSM from the source storage110. The backups stored in the vault storage108may be created by the deduplication module118of the deduplication vault system102ofFIG. 1. For example, the deduplication module118may be configured to execute computer instructions to perform operations of creating a base backup and multiple incremental backups of the source storage110.

For example, the deduplication module118may create a base backup of all allocated blocks of the source storage110as allocated at time t(0) and store the allocated blocks in the vault storage108. The state of the source storage110at time t(0) may be captured using snapshot technology in order to capture the data stored in the source storage110at time t(0) without interrupting other processes, thus avoiding downtime of the source storage110. The base backup may be very large depending on the size of the source storage110and the number of allocated blocks at time t(0). As a result, the base backup may take a relatively long time to create and consume a relatively large amount of space in the vault storage108.

Then, the deduplication module118may create a 1st incremental backup of only changed allocated blocks of the source storage110present at time t(1) and store the changed allocated blocks in the vault storage108, then later create a 2nd incremental backup of only changed allocated blocks of the source storage110present at time t(2) and store the changed allocated blocks in the vault storage108. The states of the source storage110at times t(1) and t(2) may again be captured using snapshot technology, thus avoiding downtime of the source storage110. Each incremental backup includes only those allocated blocks from the source storage110that were changed after the time of the previous backup. Thus, the 1st incremental backup includes only those allocated blocks from the source storage110that changed between time t(0) and time t(1), and the 2nd incremental backup includes only those allocated blocks from the source storage110that changed between time t(1) and time t(2). In general, as compared to the base backup, each incremental backup may take a relatively short time to create and consume a relatively small storage space in the vault storage108.

Finally, the deduplication module118may create an nth incremental backup of only changed allocated blocks of the source storage110present at time t(n), using snapshot technology, and store the changed allocated blocks in the vault storage108. The nth incremental backup includes only those allocated blocks from the source storage110that changed between time t(n) and time t(n−1).

Therefore, incremental backups may be created on an ongoing basis. The frequency of creating new incremental backups may be altered as desired in order to adjust the amount of data that will be lost should the source storage110experience corruption of its stored data or become unavailable at any given point in time. The data from the source storage110can be restored to the state at the point in time of a particular incremental backup by applying the backups from oldest to newest, namely, first applying the base backup and then applying each successive incremental backup up to the particular incremental backup.

Although only allocated blocks are included in the example incremental backups discussed above, it is understood that in alternative implementations both allocated and unallocated blocks may be backed up during the creation of a base backup or an incremental backup. This is typically done for forensic purposes, because the contents of unallocated blocks can be interesting where the unallocated blocks contain data from a previous point in time when the blocks were in use and allocated. Therefore, the creation of base backups and incremental backups as disclosed herein is not limited to allocated blocks but may also include unallocated blocks.

Further, although only a base backup and incremental backups are discussed above, it is understood that the source storage110may instead be backed up by creating a base backup and decremental backups. Decremental backups are created by initialing creating a base backup to capture the state at an initial point in time, then updating the base backup to capture the state at a subsequent point in time by modifying only those blocks in the base backup that changed between the initial and subsequent points in time. Prior to the updating of the base backup, however, the original blocks in the base backup that correspond to the changed blocks are copied to a decremental backup, thus enabling restoration of the source storage110at the initial point in time (by restoring the updated base backup and then restoring the decremental backup) or at the subsequent point in time (by simply restoring the updated base backup). Since restoring a single base backup is generally faster than restoring a base backup and one or more incremental or decremental backups, creating decremental backups instead of incremental backups may enable the most recent backup to be restored more quickly since the most recent backup is always a base backup or an updated base backup instead of potentially being an incremental backup. Therefore, the creation of backups as disclosed herein is not limited to a base backup and incremental backups but may also include a base backup and decremental backups.

During performance of the example methods disclosed herein, the deduplication module118may analyze, during one phase, the allocated blocks stored in the source storage110, for example, at a point in time to determine if the allocated blocks are already duplicated in the vault storage108. Then, the deduplication module118may back up, during a subsequent phase, those blocks from the source storage110that do not already have duplicate blocks stored in the vault storage108. Also, the virtual defragmentation module120may reorder, during another phase, block references in the copy of the FSM included in the base backup or in one of the incremental backups of the source storage110to match the order of the corresponding blocks as stored in the vault storage108.

The database114and the metadata116may be employed to track information related to the source storage110, the vault storage108, and the backup of the source storage110that are stored in the vault storage108. For example, the database114and the metadata116may be identical in structure and function to the database 500 and the metadata 700 disclosed in related U.S. patent application Ser. No. 13/782,549, titled “MULTIPHASE DEDUPLICATION,” which was filed on Mar. 1, 2013 and is expressly incorporated herein by reference in its entirety. Subsequently, the deduplication module118may restore, during another subsequent phase, each block that was stored in the source storage110at the point in time to the restore storage112as previously reordered during the reordering by the virtual defragmentation module120.

As discussed in greater detail below, reordering block references in the FSM of a backup of the source storage110to match the order of the corresponding blocks in the vault storage108may decrease the fragmentation of the data between the original order of the blocks in the source storage110and the backup order of the blocks as backed up in the vault storage108. This reordering of block references in the FSM of a backup may decrease the amount of time necessary to subsequently restore the backup to the restore storage112due to a decrease in the amount of seeking that must be performed at the vault storage108and at the restore storage112during the restore operation.

In one example embodiment, the deduplication vault system102may be a file server, the source system104may be a first desktop computer, the restore system106may be a second desktop computer, and the network122may include the internet. In this example embodiment, the file server may be configured to periodically back up the storage of the first desktop computer over the internet. The file server may then be configured to restore the most recent backup to the storage of the second desktop computer over the internet if the first desktop computer experiences corruption of its storage or if the first desktop computer's storage becomes unavailable.

Although only a single storage is disclosed in each of the systems102,104, and106inFIG. 1, it is understood that any of the systems102,104, or106may instead include two or more storages. Further, although the systems102,104, and106are disclosed inFIG. 1as communicating over the network122, it is understood that the systems102,104, and106may instead communicate directly with each other. For example, in some embodiments any combination of the systems102,104, and106may be combined into a single system. Also, although the storages108,110, and112are disclosed as separate storages, it is understood that any combination of the storages108,110, and112may be combined into a single storage. For example, in some embodiments the storage110may function as both a source storage during the creation of a backup and a restore storage during a restore of the backup, which may enable the storage110to be restored to a state of an earlier point in time. Further, although the deduplication module118and the virtual defragmentation module120are the only modules disclosed in the example deduplication backup system100ofFIG. 1, it is understood that the functionality of the modules118and120may be replaced or augmented by one or more similar modules residing on any of the systems102,104, and106. For example, the deduplication vault system102may include a module similar to the virtual defragmentation module120in order to perform a virtual defragmentation phase, such as the virtual defragmentation phase404disclosed herein in connection withFIG. 4, at the deduplication vault system102during or after the storing of a backup of the source storage110in the vault storage108. Finally, although only a single source storage and a single restore storage are disclosed in the example deduplication backup system100ofFIG. 1, it is understood that the deduplication vault system102ofFIG. 1may be configured to simultaneously back up or restore multiple source storages. For example, the greater the number of storages that are backed up to the vault storage108of the deduplication vault system102, the greater the likelihood for reducing redundancy and overall size of the data being backed up, resulting in corresponding decreases in the bandwidth overhead of transporting data to the backup storage.

Having described one specific environment with respect toFIG. 1, it is understood that the specific environment ofFIG. 1is only one of countless environments in which the example methods disclosed herein may be employed. The scope of the example embodiments is not intended to be limited to any particular environment.

FIG. 2is a schematic block diagram illustrating the example vault storage108and the example source storage110before performance of a virtual defragmentation phase, such as the virtual defragmentation phase404disclosed herein in connection withFIG. 4. The virtual defragmentation of the source storage110may be performed, in at least some embodiments, by the virtual defragmentation module120of the source system104ofFIG. 1. For example, the virtual defragmentation module120may be configured to execute computer instructions to perform an operation of virtually defragmenting the source storage110prior to, during, or after the storing of a backup of the source storage110in the vault storage108.

As disclosed inFIG. 2, the vault storage108and the source storage110are each partitioned into a physical layout of runs202-226. Each of the runs202-226includes multiple blocks. In some example embodiments, the size of each block is 4096 bytes, although any other block size could instead be employed. The size of each block may be configured to match the standard sector size of a file system of the vault storage108and the source storage110. In some example embodiments, the total number of blocks in the vault storage108may be greater than the total number of blocks in the source storage110in order to allow multiple storages to be backed up in the vault storage108. In some example embodiments, the vault storage108and the source storage110may each have millions or even billions of blocks, or more. The blank runs222and226illustrated inFIG. 2represent unallocated blocks. Each run illustrated with a unique pattern inFIG. 2represents a unique run of allocated blocks.

As disclosed inFIG. 2, prior to the time t(0) of the backup of the source storage110, the vault storage108may have already had blocks of data stored therein from other source storage backups. Alternatively or additionally, the vault storage108may have been seeded prior to time t(0) with common blocks of data. For example, the vault storage108may have been seeded with runs202,204, and206, which each makes up the files of a common operating system. The runs202,204, and206may each be stored in the vault storage108in the sequence of a clean install of the operating system. In this example, where each block is 4096 bytes in length, the run202may include the 2,621,440 blocks that make up a clean install of the 10 gigabytes of files of the WINDOWS® 7 operating system, the run204may include the 1,572,864 blocks that make up a clean install of the 6 gigabytes of files of the Linux 3.6.6 operating system, and the run206may include the 2,359,296 blocks that make up a clean install of the 9 gigabytes of files of the WINDOWS® 8 operating system. It is understood that the gigabyte sizes listed in this example are estimates only.

In addition, the vault storage108may have been seeded with runs208-220, which each makes up the files of a common software application. The runs208-220may each be stored in the vault storage108in the sequence of a clean install of the software application. Continuing with the example above, the run208may include the 786,432 blocks that make up a clean install of the 3 gigabytes of files of the MICROSOFT® Office 2010 software application, and each of the runs210-220may include the blocks that make up a clean install of the files of the Adobe Photoshop Elements 11 software application, the Norton Internet Security 2013 software application, the Quicken Deluxe 2013 software application, the QuickBooks Pro 2013 software application, the Adobe Reader software application, and the Firefox Browser software application, respectively.

Continuing with the above example, the source storage110includes a clean install of the Linux 3.6.6 operating system included in the run204, a clean install of the Adobe Reader software application included in the run218, and a clean install of the Firefox Browser software application included in the run220. Each of the runs204,218, and220stored in the source storage110at time t(0) is identical to the runs204,218, and220that were stored in the vault storage108prior to the time t(0) during the seeding of the vault storage108. Thus, at the time of the creation of a backup of the source storage110at time t(0), all of the blocks in the runs204,218, and220are already duplicated in the vault storage108. In this example, the seeding of the vault storage108with the runs204,218, and220that make up the contents of the files of a common operating system and common software applications, prior to the backing up of the source storage110at time t(0), results in an increase in the number of blocks from the source storage110that are already duplicated in the vault storage108. Therefore, during the creation of a base backup of the source storage110to capture the state at time t(0), all allocated blocks of the source storage110do not need to be transported from the source storage110to the vault storage108. Instead, only the nonduplicate blocks in the run224need to be transported, and the duplicate blocks in the runs204,218, and220do not need to be transported. Thus, the seeding of the vault storage108results in decreased bandwidth overhead, due to transporting fewer blocks, and increased efficiency and speed during the creation of the backup. Further, seeding the vault storage108with each of the runs204,218, and220in the sequence of a clean install may further increase the efficiency and speed during the restoration of the backup. Additional details regarding the seeding of the vault storage108are disclosed in related U.S. patent application Ser. No. 13/782,717, titled “DEDUPLICATION VAULT STORAGE SEEDING,” which was filed on Mar. 1, 2013 and is expressly incorporated herein by reference in its entirety.

As disclosed inFIG. 2, not all of the duplicate runs stored in the source storage110are stored in the same order as the duplicate runs stored in the vault storage108. For example, the duplicate run220is stored before the duplicate run218in the source storage110, while the duplicate run220is stored after the duplicate run218in the vault storage108. This fragmentation between the vault storage108and the source storage110may result in an increase in the amount of seeking performed at the time of a restore of the source storage. To avoid this increase in the amount of seeking, the block references in an FSM of a backup of the source storage110corresponding to the runs218and220may be reordered in the FSM to match the order of the runs218and220as stored in the vault storage108. For example, this reordering may occur during a virtual defragmentation phase, as discussed below, so that after the virtual defragmentation phase the block references in the FSM corresponding to the run220are stored after the block references in the FSM corresponding to the run218to match the order of these runs in the vault storage108. Then, during a subsequent restore phase, the runs218and220can be copied to a restore storage, such as the restore storage112ofFIG. 1, without having to switch the order of the runs218and220, thus reducing seeking in the vault storage108and/or the restore storage112.

FIGS. 3A and 3Bare schematic block diagrams illustrating the blocks stored in the vault storage108, the source storage110, and the restore storage112, along with portions of corresponding FSM, both before and after performance of a virtual defragmentation phase, such as the virtual defragmentation phase404disclosed herein in connection withFIG. 5. The virtual defragmentation of the source storage110may be performed, in at least some embodiments, by the virtual defragmentation module120of the source system104ofFIG. 1. For example, the virtual defragmentation module120may be configured to execute computer instructions to perform an operation of defragmenting the source storage110prior to, during, or after the storing of a backup of the source storage110in the vault storage108. Each blank block illustrated inFIGS. 3A and 3Brepresents an unallocated block, while each block illustrated inFIGS. 3A and 3Bwith a unique pattern represents a unique allocated block.

FIG. 3Adiscloses files seeded into the vault storage108(table130) as well as a file system file allocation table (FSFAT) of the FSM126of the source storage110(FSFAT132). It is noted that in addition to the FSFAT132disclosed inFIG. 3A, the FSM126may each additionally include a file system block allocation map (FSBAM) which indicates which blocks in the corresponding storage are allocated and which blocks in the corresponding storage are unallocated. As disclosed inFIG. 3A, each of the table130and the FSFAT132tracks the file names and corresponding block locations of files stored in the corresponding storage. This tracking may be performed using block references listed in the Block Locations column of the table130and the FSFAT132, where the order of each block reference indicates the order of the corresponding blocks as stored in the corresponding storage.

For example, prior to the time t(0) of the creation of the base backup of the source storage110, the table130indicates that the seeded file named SystemFile1.dll is made up of the three blocks stored in locations108(1),108(2), and108(3). Similarly, the table130indicates that the seeded file named ApplicationFile1.dll is made up of the two blocks stored in locations108(1) and108(4). Also, the table130indicates that the seeded file named ApplicationFile2.dll is made up of the two blocks stored in locations108(1) and108(5). It is noted that the block stored at the block location108(1) is duplicated in the files SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll. However, since the vault storage108is configured to store only a single copy of each unique block, the block stored at the block location108(1) is therefore deduplicated by being stored only once in the vault storage108. Therefore, the seven blocks that make up the contents of the seeded files SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll are stored in only five blocks in the vault storage108.

At the time t(0) of the creation of the base backup of the source storage110, the FSFAT132indicates that the source storage110also includes three files named SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll. In addition, however, the FSFAT132indicates that the source storage110also includes another file named UserDataFile1.txt. The FSFAT132indicates the locations of each of the blocks that make up the contents of these four files using the block references in the Block Locations column. It is noted that even though the three files named SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll include a duplicate block, as discussed above in connection with the table130, this duplicate block is stored multiple times in locations110(5),110(2), and 110(10), instead of being deduplicated by only being stored once, since the source storage110is not a deduplicated storage as is the vault storage108. Therefore, the eight blocks that make up the contents of the files SystemFile1.dll, ApplicationFile1.dll, ApplicationFile2.dll, and UserDataFile1.txt are stored in eight blocks in the source storage110. Further, the source storage110includes two FSM blocks at locations110(1) and110(9), which may be employed to store, for example, the FSFAT132and/or an FSBAM of the FSM126.

It is further noted that even though both the vault storage108and the source storage include identical files named SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll having identical blocks, the order of the blocks differs between the vault storage108and the source storage110. The fragmentation between the vault storage108and the source storage110as disclosed inFIG. 3Amay result in an increase in the amount of seeking performed at the time of a restore of the source storage110. To avoid this increase in the amount of seeking, the block references in a copy of the FSFAT132that is included in a backup of the source storage110may be reordered to match the order of the corresponding blocks in the vault storage108, as disclosed inFIG. 3Band as discussed below.

During the creation of the base backup of the source storage110at the time t(0),FIG. 3Adiscloses that the vault storage108will have the data block from position110(6) stored at108(6), the FSM block from position110(1) stored at the position108(7), and the FSM block from position110(9) stored at the block position108(8). Since one copy of all of the other allocated blocks from the source storage110at the time t(0) was already stored in the positions108(1)-108(5) prior to the time t(0), there is no need to move these blocks again to the vault storage108. Therefore, after the creation of the base backup of the source storage110at the time t(0),FIG. 3Adiscloses that eight unique blocks are stored in the vault storage108in locations108(1)-108(8).

As noted above, and as disclosed inFIG. 3B, the defragmentation between the source storage110and the vault storage108, and the resulting increase in the amount of seeking performed at the time of a restore of the source storage110, may be reduced by reordering the block references in a copy of the FSFAT of the FSM126that is included in a backup of the source storage110(FSFAT134) to match the order of the corresponding blocks in the vault storage108. In particular, as disclosed inFIG. 3B, the block references in the FSFAT134may be reordered such that the block references for the files SystemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll match the order of the corresponding blocks in the vault storage108. In particular, the block references for the files SystemFile1.dllemFile1.dll, ApplicationFile1.dll, and ApplicationFile2.dll are reordered during the virtual defragmentation of the FSFAT134such that the corresponding blocks from the vault storage108can be read in a generally linear fashion from the vault storage108and then stored in a generally linear fashion in the restore storage112.

For example, as disclosed inFIG. 3B, the reordering of the block references in the FSFAT134during the virtual defragmentation results in the three duplicate copies of the block stored in the first location of the vault storage108, namely location108(1), being stored contiguously as a run in positions112(2)-112(4) in the restore storage112; a copy of the block stored in the second-fifth locations of the vault storage108, namely locations108(2)-108(5), being stored contiguously in positions112(5)-112(8) in the restore storage112; and a copy of the block stored in the sixth location of the vault storage108, namely location108(6), being stored in position112(10) in the restore storage112. Thus, the order of the reordered block references in the FSFAT134matches exactly the order of the corresponding blocks in the vault storage108which, during a subsequent restore of the source storage110, allows these blocks to be read in a linear fashion from the vault storage108and then stored in a linear fashion in the restore storage112, thus reducing seeking in the vault storage108and the restore storage112.

Also,FIG. 3Bdiscloses the FSM blocks stored in positions108(7) and108(8) being stored in positions corresponding to the original positions from the source storage110, namely positions112(1) and112(9). The FSM blocks in the backup may thus be excluded from the virtual defragmentation phase due to, for example, file system preferences that prefer to have FSM blocks positioned in certain positions in a storage.

It is understood that although only four files are represented in the FSFATS and the storages inFIGS. 3A and 3B, each represented storage may, in fact, include one file, two files, three files, or more than four files. It is further understood although the four files represented inFIGS. 3A and 3Beach includes only one, two, or three blocks, each file in a software application may include more than three blocks.

FIG. 4is a schematic flowchart diagram of an example method400of virtual defragmentation during multiphase deduplication. The method400may be implemented, in at least some embodiments, by the virtual defragmentation module120of the source system104and the deduplication module118of the deduplication vault system102ofFIG. 1. For example, the virtual defragmentation module120and the deduplication module118may be configured to execute computer instructions to perform operations of virtually defragmenting the source storage110prior to, during, or after the creation of a backup of the source storage110, as represented by one or more of phases402-408which are made up of the steps410-418of the method400. Although illustrated as discrete phases and steps, various phases/steps may be divided into additional phases/steps, combined into fewer phases/steps, or eliminated, depending on the desired implementation. The method400will now be discussed with reference toFIGS. 1-4.

The analysis phase402of the method400may include a step410, in which each allocated block stored in a source storage is analyzed to determine if the block is duplicated in the vault storage. For example, the deduplication module118may analyze each allocated block stored in the source storage110at time t(0) to determine if the block is duplicated in the vault storage108. By determining which blocks stored in the source storage110are duplicated in the vault storage108, the order of the duplicated blocks as stored in the vault storage108can also be determined.

The virtual defragmentation phase404of the method400may include a step412, in which the FSM blocks included in the backup of the source storage are accessed, and a step414, in which block references in the FSM blocks are reordered to match the order of the corresponding blocks as stored in the vault storage. For example, the virtual defragmentation module120may access the FSFAT134disclosed inFIG. 3Bthat is included in FSM blocks of the backup of the source storage110, such as in the FSM blocks stored in positions108(7) and108(8) as disclosed inFIG. 3A, and then reorder block references in the FSFAT134to match the order of the corresponding blocks as stored in the vault storage108.

As noted previously, and as illustrated inFIGS. 2,3A, and3B, these reordered block references may include block references corresponding to blocks that make up the contents of one or more files of an operating system or a software application that is installed in the source storage. Further, the blocks that make up the contents of the one or more files of the operating system or the software application may be stored in the vault storage108in the sequence of a clean install of the operating system or the software application. Further, where it is known in advance that the particular source storage110will eventually be backed up to the vault storage108, and the particular operating system and/or the particular software applications installed in the source storage110are known, the particular operating system and/or the particular software applications can be included in the blocks stored in, or seeded into, the vault storage108.

Also, as noted previously, and as illustrated inFIGS. 3A and 3B, during the virtual defragmentation phase404, block references for each set of local duplicate blocks, such as the set of local duplicate blocks that was stored in positions110(5),110(2), and110(10) in the source storage110at the time t(0), may be reordered as a run in the reordered FSM blocks, such as the run indicated in locations110(2)-110(4) in the FSFAT134inFIG. 3B.

Further, the reordering of block references in the FSM blocks to match the order of the corresponding blocks as stored in the vault storage108during the virtual defragmentation phase404may include only the reordering of block references corresponding to the data blocks in the backup and not the reordering of block references corresponding to the FSM blocks in the backup. For example, block references corresponding to the FSM blocks at positions110(1) and110(9) as disclosed inFIG. 3Amay not be reordered during the virtual defragmentation phase in order to allow the blocks to ultimately be restored in similar positions112(1) and112(9) in the restore storage112due to, for example, file system preferences that prefer to have FSM blocks positioned in certain positions in a storage.

The backup phase406of the method400may include a step416, in which each unique nonduplicate block from the source storage is stored in the vault storage. For example, the deduplication module118may store each block from the source storage110, which was determined during the analysis phase402to be a unique nonduplicate block, in the vault storage108. The blocks stored in the vault storage108during the backup phase406may include both FSM blocks as well as data blocks.

By the conclusion of the backup phase406, a base backup of the source storage110will have been stored in the vault storage108. Unlike a standard base backup image, however, the backup of the source storage110, as stored in the vault storage108, will likely have been reduced in size due to the elimination of local duplicate blocks within the base backup. In addition, where multiple storages are backed up into the vault storage108, the total overall size of the backups will likely be reduced in size due to the elimination of global duplicate blocks across the backups.

It is noted that the analysis phase402, the virtual defragmentation phase404, and the backup phase406can also be employed to create an incremental backup of a storage, which will store and track only those allocated blocks in the source storage110that changed between the point in time of a previous backup and the point in time of the incremental backup. It is further noted that the virtual defragmentation phase404may be performed prior to, during, or after the backup phase406, or may be performed in some combination prior to, during, or after the backup phase406. For example, the virtual defragmentation phase404may begin prior to the backup phase but then conclude during the backup phase406.

The restore phase408of the method400may include a step418, in which each allocated block that was stored in the source storage is restored to a restore storage in the position indicated in the reordered FSM. For example, the deduplication module118may read, from the vault storage108, and restore, in the restore storage112, each allocated block that was stored in the source storage110at time t(0) in the same position as indicated in the reordered FSFAT134disclosed inFIG. 3Bafter the conclusion of the virtual defragmentation phase404. At the conclusion of the restore phase408, the backup of the source storage110will be restored to the restore storage112, such that the restore storage112will include identical files as the source storage110at time t(0) but the positions of the blocks that make up the contents of those files may be reordered as indicated in the FSFAT134at the conclusion of the virtual defragmentation phase404.

Also, as noted previously in connection withFIGS. 3A and 3B, since the virtual defragmentation phase404results in the order of the blocks in the source storage110being reordered to match the order of the blocks as stored in the vault storage108, the amount of time necessary to subsequently restore the backup to the restore storage112may be decreased due to a decrease in the amount of seeking that must be performed at the vault storage108and the restore storage112during the restore phase.

Further, as noted previously, and as illustrated inFIGS. 3A and 3B, during the restore phase408, each of the runs of local duplicate blocks in the reordered FSM blocks, such as the run indicated in locations110(2)-110(4) in the FSFAT134, may be stored in the restore storage112as indicated in the reordered FSM blocks, such as the run stored in locations112(2)-112(4) in the restore storage112.

The analysis phase402and the backup phase406may be accomplished, for example, by performing the steps of the analysis phase 802 and the backup phase 804 disclosed in related U.S. patent application Ser. No. 13/782,549 referenced above.

The embodiments described herein may include the use of a special purpose or general purpose computer including various computer hardware or software modules, as discussed in greater detail below.

Embodiments described herein may be implemented using computer-readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media may be any available media that may be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer-readable media may include non-transitory computer-readable storage media including RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other storage medium which may be used to carry or store desired program code in the form of computer-executable instructions or data structures and which may be accessed by a general purpose or special purpose computer. Combinations of the above may also be included within the scope of computer-readable media.

Computer-executable instructions comprise, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Although the subject matter has been described in language specific to structural features and/or methodological steps, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or steps described above. Rather, the specific features and steps described above are disclosed as example forms of implementing the claims.

As used herein, the term “module” may refer to software objects or routines that execute on a computing system. The different modules described herein may be implemented as objects or processes that execute on a computing system (e.g., as separate threads). While the system and methods described herein are preferably implemented in software, implementations in hardware or a combination of software and hardware are also possible and contemplated.

All examples and conditional language recited herein are intended for pedagogical objects to aid the reader in understanding the example embodiments and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically-recited examples and conditions.