Patent Publication Number: US-8996468-B1

Title: Block status mapping system for reducing virtual machine backup storage

Description:
RELATED APPLICATION 
     This application claims the benefit of priority under 35 U.S.C. §119(e) of U.S. Provisional Patent Application No. 61/170,520, filed on Apr. 17, 2009, and entitled “Systems and Methods for Mapping Virtual Machine Data,” the disclosure of which is hereby incorporated by reference in its entirety. 
    
    
     BACKGROUND 
     Many companies take advantage of virtualization solutions to consolidate several specialized physical servers and workstations into fewer servers running virtual machines. Each virtual machine can be configured with its own set of virtual hardware (e.g., processor, memory, ports, and the like) such that specialized services that each of the previous physical machines performed can be run in their native operating system. For example, a virtualization layer, or hypervisor, can allocate the computing resources of one or more host servers into one or more virtual machines and can further provide for isolation between such virtual machines. In such a manner, the virtual machine can be a representation of a physical machine by software. 
     In many virtual machine implementations, each virtual machine is associated with at least one virtual machine disk or image located in one or more files in a data store. The virtual machine image can include files associated with a file system of a guest operating system. The virtual machine image can be copied, moved, backed up, or the like, similar to a general data file. 
     SUMMARY 
     In certain embodiments, systems and methods programmatically determine the status of blocks in a virtual machine image. For example, a system can determine which blocks in a virtual machine image are active, deleted, zero, or a combination of the same. The system can determine block status without scanning all the blocks in a virtual machine image in some implementations. Instead, the system can access metadata in a file system of a virtual machine image to determine the block status. When backing up the virtual machine image, the system can back up active blocks while skipping inactive blocks, including deleted and/or zero blocks. As a result, in certain embodiments, the system can take less time to back up a virtual machine image, and the resulting backup file or files can consume less storage space. 
     For purposes of summarizing the disclosure, certain aspects, advantages and novel features of the inventions have been described herein. It is to be understood that not necessarily all such advantages can be achieved in accordance with any particular embodiment of the inventions disclosed herein. Thus, the inventions disclosed herein can be embodied or carried out in a manner that achieves or optimizes one advantage or group of advantages as taught herein without necessarily achieving other advantages as can be taught or suggested herein. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Throughout the drawings, reference numbers are re-used to indicate correspondence between referenced elements. The drawings are provided to illustrate embodiments of the inventions described herein and not to limit the scope thereof. 
         FIG. 1  illustrates an embodiment of a system for performing backup operations in a virtual computing environment; 
         FIG. 2  illustrates an embodiment of another system for performing backup operations in a virtual computing environment; 
         FIG. 3  illustrates an embodiment of a backup process; 
         FIG. 4  illustrates an embodiment of a block mapping process; 
         FIG. 5  illustrates an example mapping that can be performed by the block mapping process of  FIG. 4 ; and 
         FIG. 6  illustrates an embodiment of a restore process. 
     
    
    
     DETAILED DESCRIPTION 
     I. Introduction 
     Virtual machine images often contain a large percentage of white space, which includes empty blocks (zero blocks). A backup of an entire virtual machine image therefore stores the white space together with any active and deleted blocks, wasting storage space and backup time. Some solutions determine which blocks of a virtual machine image are zero blocks and then back up only the active and deleted blocks. This backup approach is called zero handling. A drawback of zero handling is that a full scan of the blocks is performed to determine which blocks are the zero blocks. The full scan can take a significant amount of time. Another drawback of this approach is that zero handling fails to account for blocks of a file system that are marked as deleted. Thus, even when accounting for zero blocks, a backup system can still back up a significant amount of irrelevant deleted data, which still results in wasted storage space and backup time. 
     This disclosure describes systems and methods for programmatically determining the status of blocks in a virtual machine image. In certain embodiments, the system can determine which blocks are active, deleted, zero, or a combination of the same. In certain embodiments, the system advantageously determines block status without scanning some or all the blocks in a virtual machine image. Instead, the system can access metadata in a file system of a virtual machine image to determine the block status. When backing up the virtual machine image, the system can back up active blocks while skipping inactive blocks, including deleted and/or zero blocks. As a result, the system can take less time to back up a virtual machine image, and the resulting backup file or files can consume less storage space. 
     II. Example Backup System 
       FIG. 1  depicts an embodiment of a system  100  for performing backup operations in a virtual computing environment. In general, the backup system  100  provides a tool for backing up virtual machine disk files without backing up a significant amount of deleted or empty data. As such, in certain embodiments, the backup system  100  can perform backups faster and with less storage consumption than currently-available backup systems. 
     As shown in  FIG. 1 , the backup system  100  includes a host server  102  in communication with a data store  104 . In certain embodiments, the host server  102  includes one or more computing devices configured to host one or more virtual machines  106  executing on top of a hypervisor  108 . In certain embodiments, the hypervisor  108  decouples the physical hardware of the host server  102  from the operating system(s) of the virtual machine(s)  106 . Such abstraction allows, for example, for multiple virtual machines  106  with different operating systems and applications to run in isolation or substantially in isolation on the same physical machine. 
     The hypervisor  108  includes a virtualization platform that allows for multiple operating systems to run on a host computer at the same time. For instance, the hypervisor  108  can include a thin piece of software that runs directly on top of the hardware platform of the host server  102  and that virtualizes resources of the machine (e.g., a native or “bare-metal” hypervisor). In such embodiments, the virtual machine(s)  106  can run, with their respective operating systems, on the hypervisor  108  without the need for a host operating system. Examples of such bare-metal hypervisors can include, but are not limited to, ESX SERVER by VMware, Inc. (Palo Alto, Calif.), XEN and XENSERVER by Citrix Systems, Inc. (Fort Lauderdale, Fla.), ORACLE VM by Oracle Corporation (Redwood City, Calif.), HYPER-V by Microsoft Corporation (Redmond, Wash.), VIRTUOZZO by Parallels, Inc. (Switzerland), or the like. 
     In yet other embodiments, the host server  102  can include a hosted architecture in which the hypervisor  108  runs within a host operating system environment. In such embodiments, the hypervisor  108  can rely on the host operating system for device support and/or physical resource management. Examples of such hosted hypervisors can include, but are not limited to, VMWARE WORKSTATION and VMWARE SERVER by VMware, Inc., VIRTUAL SERVER by Microsoft Corporation, PARALLELS WORKSTATION by Parallels, Inc., or the like. 
     In certain embodiments, each virtual machine  106  includes a guest operating system and associated applications. In such embodiments, the virtual machine  106  accesses the resources (e.g., privileged resources) of the host server  102  through the hypervisor  108 . At least some of the machines can also include a backup service  132  in certain embodiments, which can assist with backup operations, as described below. 
     The host server  102  communicates with the data store  104  to access data stored in one or more virtual machine files. For instance, the data store  104  can include one or more virtual machine file systems  110  that maintain virtual disk files or virtual machine images for some or all of the virtual machines  106  on the host server  102 . In certain embodiments, the virtual machine file system  110  includes a VMWARE VMFS cluster file system provided by VMware, Inc. In such embodiments, the VMFS cluster file system enables multiple host servers (e.g., with installations of ESX server) to have concurrent access to the same virtual machine storage and provides on-disk distributed locking to ensure that the same virtual machine is not powered on by multiple servers at the same time. In other embodiments, the virtual machine file system  110  is stored on the host server  102  instead of in a separate data store. 
     The data store  104  can include any physical or logical storage for holding virtual machine files. The data store  104  can exist on a physical storage resource, including one or more of the following: local disks (e.g., local small computer system interface (SCSI) disks of the host server  102 ), a disk array, a storage area network (SAN) (e.g., fiber channel), an iSCSI disk area, network attached storage (NAS) arrays, network file system (NFS), or the like. In certain embodiments, the virtual machine(s)  106  uses a virtual disk file  112  or virtual machine image residing on the data store  104  to store its operating system, program files, and other data associated with its activities. 
     The backup system  100  further includes a management server  120  in communication with the host server  102  over a network  130 . In certain embodiments, the management server  120  includes one or more computing devices. The management server  120  can coordinate the backup operations of the virtual machine disk files  112  through the host server  102 . In one embodiment, the management server  120  causes the backup service  132  of the virtual machine  106  to perform certain backup operations. For example, the backup service  132  can perform shadow copy or snapshot operations, such as are described in U.S. application Ser. No. 12/182,364, filed Jul. 30, 2008, titled “Systems and Methods for Performing Backup Operations of a Virtual Machine,” the disclosure of which is hereby incorporated by reference in its entirety. In addition, the backup system  100  can include additional features described in U.S. application Ser. No. 12/502,052, filed Jul. 13, 2009, titled “Backup Systems and Methods for a Virtual Computing Environment,” the disclosure of which is hereby incorporated by reference in its entirety. 
     Advantageously, in certain embodiments, the management server  120  analyzes the virtual disk files  112  to identify the status of portions of the virtual disk files  112  to determine whether these portions include active, deleted, and/or zero data. The management server  120  can identify the status of these disk file portions efficiently by accessing metadata within the virtual disk file  112 . The management server  120  can then initiate a backup of the active portions of the virtual disk file  112 . 
     The management server  120  analyzes the virtual disk file  112  in certain embodiments outside of the virtual machine  106 , for example, outside of a guest operating system of the virtual machine  106 . The management server  120  can therefore reduce the impact of backup operations on the virtual machine  106 . Alternatively, in certain embodiments, a component operating within the virtual machine  106  can perform this analysis, such as an application executing in the virtual machine  106 . For instance, the management server  120  can inject a lightweight binary file into the virtual machine  106  executing on the host. On WINDOWS systems, for example, the management server  120  can inject the binary using Windows Management Instrumentation (WMI) features. The binary file can then analyze the virtual disk file  112 . Additional features of the management server  120  are described in greater detail below with respect to  FIG. 2 . 
     As further illustrated in  FIG. 1 , the backup system  100  includes a backup, or target, server  140  for storing backup files, such as a backup of one or more of the virtual disk files  112 . As shown, the backup server  140  is coupled to the network  130  and can directly communicate with the management server  120 . The management server  120  can cause backups of virtual disk files  112  to be stored in the backup server  140 . 
     As shown, the network  130  provides a wired and/or wireless communication medium between the host server  102 , the management server  120  and/or the backup server  140 . In certain embodiments, the network  130  includes a local area network (LAN). In yet other embodiments, the network includes one or more of the following: Internet, intranet, wide area network (WAN), public network, combinations of the same or the like. 
     Although the backup system  100  has been described with reference to particular arrangements, other embodiments can comprise more or fewer components. For example, in certain embodiments, the backup system  100  can function without the backup server  140 , and backup files can be stored to the data store  104  or a local storage device directly coupled to the management server  120  or host system  102 . 
     In yet other embodiments, the host server  102  can comprise a plurality of servers in a clustered arrangement such that the computing and memory resources of the clustered servers are shared by one or more virtual machines  106 . Moreover, in certain embodiments, the backup tool maintained by the management server  120  can instead reside on the host server  102  and/or the backup server  140 . 
       FIG. 2  illustrates a more detailed embodiment of a backup system  200  for performing storage operations in a virtual computing environment. The backup system  200  includes the features of the backup system  100  of  FIG. 1  and further includes additional features. For example, the backup system  200  can back up virtual machine disk files without backing up a significant amount of deleted or empty data. 
     In the depicted embodiment, the management server  120  includes a backup module  222 , a mapping module  224 , and a user interface module  228 . Each of these modules can be implemented in hardware and/or software. In certain embodiments, the backup module  222  coordinates backup operations of virtual disk files  112  stored in the data store  104 . The backup module  222  can perform, for example, full backups, differential backups, incremental backups, or the like. The backup module  222  can coordinate with the backup service  132  within the virtual machine  106  to perform virtual disk snapshots in the manner described in U.S. application Ser. No. 12/182,364, referred to above. However, in some embodiments, the backup module  222  performs backup operations without coordinating with a backup service inside the virtual machine  106 . 
     The mapping module  224  can determine status information about a virtual disk file  112 . In the context of VMWARE systems, for instance, the mapping module  224  can access a .VMDK virtual disk file  112 . In one embodiment, the backup module  222  invokes the mapping module  224  prior to backing up the virtual disk file  112 . Status information determined by the mapping module  224  can include information on which portions of the virtual disk file  112  include active or inactive data. Active data can include data that is currently used by the virtual machine  106 . For example, active data can include non-deleted and non-zero data. In contrast, inactive data can include deleted data or zero (empty) data. Some guest operating systems merely mark data as deleted when a user deletes the data, rather than actually erasing the data from storage. Thus, the deleted data can include actual data that has been marked as deleted. 
     The mapping module  224  can determine the status information about the virtual disk file  112  by accessing a guest operating system file system  250  stored within the file  112 . The file system  250  includes files  252 , such as guest operating system files, application files, user documents, and so on. Metadata  254  in the file system  250  describes the logical structure of the files  252 , including the locations of the files in a logical hierarchy such as a directory tree. In addition, the metadata  254  can specify the physical structure of the files  252 , such as the locations of the files  252  in the virtual disk file  112 , the size of the files  252 , and so on. 
     Different guest operating systems can include different file systems. For example, many WINDOWS operating systems use the NTFS file system, whereas LINUX systems use a different file system. While file systems from different operating systems are implemented differently, most file systems share the common characteristic of using metadata to describe the structure of the files. In certain embodiments, the mapping module  224  can determine status information from many different types of files systems  250 . 
     Advantageously, in certain embodiments, the mapping module  224  accesses the metadata  254  to determine the status information. Accessing the metadata  254  can be faster than scanning (or reading) some or all of the file system  250  to determine status information because the metadata  254  can include a summary or description of the status information. In one embodiment, the metadata  254  for a WINDOWS-based NTFS file system  250  can include a header file called a Master File Table (MFT). The MFT can be organized as a database table or tables, with each row in the table or tables representing one file. Data about the files  252  stored in the MFT can include information such as file permissions, ownership, size, location, and status of data blocks of the file. The mapping module  224  can therefore access the MFT to obtain the status information for portions of the file system. In contrast, the metadata  254  in many LINUX and UNIX-based systems include an inode or vnode for some or all of the files. The inodes (or vnodes) are data structures that can include file permissions, ownership, size, location, and status of data blocks of the file. Thus, in LINUX or UNIX-based systems, the mapping module  224  can access the inodes or vnodes to obtain status information for portions of the file system. 
     Different implementations of the mapping module  224  can analyze the metadata  254  at different levels of granularity. In one implementation, the mapping module  224  determines the status of storage blocks of the file system  250  from the metadata  254 . In another embodiment, the mapping module  224  determines the status of the files  252  of the file system  250 . In yet another embodiment, the mapping module  224  determines the status of directories of the file system  250 . For ease of illustration, the remainder of this specification will refer to determining the status of blocks in the file system  250 . However, it should be understood that the various features described herein can apply to any type of metadata mapped by the mapping module  224 . 
     Advantageously, in certain embodiments, the mapping module  224  can store the status information about blocks (or other storage units) in a virtual disk map  244  on the backup server  140  or on another device (e.g., in a memory). The virtual disk map  244  can be a data structure or the like that includes some indication of the status of some or all of the blocks in the file system  250 . The virtual disk map  244  can advantageously consume far less storage than the data in the virtual disk file  112  because the map  244  represents the data but does not include the actual data. For example, the virtual disk map  244  can be a bitmap, a bytemap, or some other data structure. Various features of the virtual disk map  244  will be described in greater detail below with respect to  FIGS. 4 and 5 . 
     When backing up the virtual disk file  112 , the backup module  222  can consult the virtual disk map  244  to determine which blocks of the file system  250  are active or inactive. The backup module  222  can then save the active blocks in a backup virtual disk file  242 . An embodiment of a backup process used by the backup module  222  is described below with respect to  FIG. 3 . 
     The user interface module  228  of the management server  120  can provide functionality for users to control settings of the backup module  222  and/or the mapping module  224 . For instance, the user interface module  228  can provide a scheduling user interface that allows an administrator to schedule backups of the virtual disk file  112 . In one embodiment, the user interface module  228  also provides an interface to enable or disable the functions of the mapping module  224 . An administrator may wish to disable the mapping module  224  because in some embodiments undelete operations cannot be performed on the backup virtual disk file  242  when deleted blocks are not saved in the file  242 . The user interface module  228  can also allow an administrator to enable some functionality of the mapping module  224  while disabling others. For example, a user interface might allow an administrator to enable zero block removal to reduce backup size while disabling deleted block removal to allow for undelete operations. 
     III. Backup Process 
       FIG. 3  illustrates an embodiment of a backup process  300  for efficiently backing up a virtual machine image. The backup process  300  can be implemented by the systems  100  or  200  described above. For example, the backup process  300  can be implemented by the management server  120 , or more specifically, the backup and mapping modules  222 ,  224  of the management server  120 . In certain embodiments, the backup process  300  performs virtual machine image backups more efficiently than currently-available backup solutions. 
     At state  302 , a map of active and/or inactive blocks of a guest operating system file system are created. The map created can be the virtual disk map  244  described above with respect to  FIG. 2  and can be created by the mapping module  224 . The map can include an indication of which blocks are active, which blocks are inactive, or both. Further, inactive blocks can be broken down to include deleted blocks and zero blocks, which can be separately indicated in the map. The map is stored in computer storage at state  304 , for example, by the mapping module  224 . The mapping module  224  can persist the map or can store the map in memory (see  FIG. 4 ). 
     For some or all of the blocks in the file system, at state  306 , the map is accessed to determine whether the block or blocks are active or inactive. In one embodiment, state  306  is implemented by the backup module  222  at the start of a backup operation. At decision state  308 , it is determined whether the block is active or inactive. The backup module  222  can access a value for the block stored in the map, for instance, which indicates whether the block is active or inactive. If the block is active, the block is backed up at state  310 . Otherwise, the block is skipped (not backed up) at state  312 . In another embodiment, the active blocks are backed up at one time, for example, as one backup operation, instead of backing up individual active blocks. 
     To illustrate the potential benefits of the backup process  300 , an example virtual machine image might include 70 GB of zero blocks, 20 GB of active blocks, and 10 GB of deleted blocks. A traditional backup process without zero or deleted block handling would create a backup file of 70+20+10=100 GB (or somewhat smaller with file compression). With zero handling, the backup file would be 20+10=30 GB (or smaller with compression). However, applying the backup process  300 , the backup file size would be 20 GB because both zeros and deleted blocks are skipped by the backup process  300 . This file can also be compressed to further reduce storage consumption. 
     In addition, the backup process  300  can still provide benefits even if the example above were changed to include 70 GB of zero blocks, 20 GB of active blocks, and 0 GB of deleted blocks. While the size of the backup file would be the same or approximately the same whether using zero handling or the process  300 , the speed of the backup process  300  can be greater than a zero handling process. The speed increase can be due to the process  300  determining which blocks are zeros more quickly than a traditional zero handling process, which scans all the blocks to determine where the zero blocks are. Techniques for rapidly detecting zeros, deleted blocks, and active blocks are described below more fully with respect to  FIG. 4 . 
     IV. Block Mapping 
       FIG. 4  illustrates an embodiment of a block mapping process  400  for identifying active and inactive blocks in a virtual machine image. The block mapping process  400  can be implemented by the systems  100  or  200  described above. For example, the block mapping process  400  can be implemented by the management server  120 , or more specifically, the mapping module  224  of the management server  120 . In certain embodiments, the mapping module  224  efficiently maps block status to a map data structure. 
     At state  402 , a virtual disk file is accessed, and file system data is accessed from the virtual disk file at state  404 . In one embodiment, the mapping module  224  directly accesses the metadata in the virtual disk file. For example, the mapping module  224  can access a Master Boot Record (MBR) in the virtual disk file, which is typically in the same location for most virtual disk files (such as within the first several bytes of the file). The mapping module  224  can determine the location of the file system data from the MBR. For NTFS file systems, for example, the MFT metadata file is at a certain offset in the MBR. Thus, once the mapping module  224  has located the file system, the mapping module  224  can access the MFT at the expected location. 
     In another embodiment, the mapping module  224  indirectly obtains access to the virtual disk file by calling an application programming interface (API) provided, for example, by a virtual machine vendor. For example, in VMWARE virtual machine environments, such an API exists for accessing virtual disk file data. The API can further include functionality for accessing the contents of the virtual disk file, including the file system metadata. This indirect approach to accessing metadata can be useful when the mapping module  224  is implemented in a different file system than the virtual disk file. For instance, if the mapping module  224  is implemented in a WINDOWS file system but the virtual disk file is formatted for the LINUX file system, an API can allow the mapping module  224  to read the LINUX-formatted virtual disk file. 
     At state  406 , for a storage block in the metadata, it is determined what type of data is represented by the block. As described above, the mapping module  224  can determine whether a block contains active, deleted, or zero data. At decision state  406 , it is determined whether the block is active. In one embodiment, an active block is any block that contains a portion of active data, however small. Many file systems use a standard block size for partitioning data storage, such as 4 kB. A file system might mark a 4 kB (or other size) block as active even if that active data in the block includes a tiny fraction of the full block size. Thus, even though the backup processes described herein can avoid backing up a substantial amount of deleted data, some deleted data may still be saved in a backup process. 
     In some embodiments, the mapping module  224  maps a plurality of file system blocks to a single status bit, byte, or the like. For instance, instead of mapping each 4 kB block in a file system to a single status bit (e.g., representing active or deleted), the mapping module  224  can map 256 file system blocks to a single status bit if any of the 256 blocks have active data. If each of the file system blocks is 4 kB large, the mapping module  224  can therefore equivalently map 1 MB of file system data (256×4 kB) to a single status bit. In another embodiment, the mapping module  224  can map 64 file system blocks to a single status bit if any of the 64 blocks have active data. If each of the file system blocks is 4 kB large, the mapping module  224  can then equivalently map 256 kB of file system data (64×4 kB) to a single status bit. Other mapping sizes can be chosen. 
     In one embodiment, the mapping size is chosen to optimize or otherwise improve the performance of compression algorithms employed by the backup module  222  when compressing the backup virtual disk file  242 . Some compression algorithms, when used as an in-line process (e.g., in-line with a backup process) take less processing time when using smaller mapping sizes, whereas others take less time when using larger mapping sizes. Using a larger mapping size can result in storing more deleted data at the possible beneficial tradeoff of reducing compression processing time. The mapping module  224  can automatically adjust the mapping size used based at least partly on the compression algorithm selected. 
     If the block is not active, an entry is created in a map to indicate that the block is not active at state  410 . Otherwise, it is further determined at decision state  412  whether the block is part of an active temporary file. If the block is part of an active temporary file, the block is active because it does not contain deleted data. However, to save backup storage space, in certain embodiments, an entry is created in a map to indicate that the temporary file block is not active at state  410 . Examples of temporary files include virtual memory files (e.g., pagefile.sys in WINDOWS), system sleep or hibernate state files (such as hiberfile.sys in WINDOWS), temporary Internet files, and the like. An option to skip (e.g., mark as inactive) or to not skip temporary files can be provided by the user interface module  228  described above. 
     If the block is not part of a temporary file, an entry is created in the map indicating that the block is active at state  414 . It is then determined whether additional blocks are left in the metadata to analyze at decision state  416 . If so, the block mapping process  400  loops back to state  406 . Otherwise, the block mapping process  400  ends. 
     The mapping process  400  can be used in conjunction with other systems that provide zero handling. For instance, the mapping process  400  can be applied as a filter to the output of a zero handling system. An example zero handling system provided by VMWARE is the Change Block Tracking (CBT) system. In one embodiment, the backup module  222  can use the CBT system to obtain information about zero blocks. The CBT can perform a full file system scan to identify and map the zero blocks. Thereafter, the mapping module  224  can apply the process  400  to identify deleted blocks in the machine image. The mapping module  224  can modify the map provided by the CBT system to indicate the locations of deleted blocks. 
     It should be noted that in certain embodiments, the mapping module  224  stores the map in memory instead of persisting the map to disk storage. In another embodiment, the mapping module  224  does not create a map data structure. Instead, the mapping module  224  can determine whether a block is active, deleted, and/or zero and provide an indication of this determination to the backup module  222  (e.g., through memory). The backup module  222  can then back up the referenced block. The mapping module  224  can then examine the next block, followed by the backup module  222  backing up the next block, and so on. Thus, the determination of active, deleted, and/or zero blocks can be performed in-line with backup operations. 
     Moreover, in certain embodiments, the mapping module  224  can map the virtual disk file  112  from outside of the virtual machine  106 , for example, outside of a guest operating system of the virtual machine  106 . The mapping module  224  can therefore reduce the impact of mapping operations on the virtual machine  106 . The mapping module  224  and/or the backup module  222  can also facilitate obtaining a more complete picture of the virtual disk file  112  because the mapping module  224  and/or the backup module  222  can execute outside of the virtual machine. In addition, in some embodiments, the backup module  222  performs backup operations from outside of the virtual machine  106 . In other embodiments, the mapping module  224  is a process running in the virtual machine and therefore maps the file system from within the virtual machine  106 . In one such embodiment, the mapping module  224  can access an operating system API to determine the location of the metadata and access the metadata. The backup module  222  can also be a process running in the virtual machine  106  (e.g., as a volume shadow copy service). In another embodiment, the mapping module  224  can run inside of the virtual machine  106  while the backup module  224  runs outside, or vice versa. 
       FIG. 5  illustrates a conceptual example of a mapping  500  that can be performed by the block mapping process  400  of  FIG. 4 . A portion of a file system  510  is represented by a plurality of blocks  512 . The blocks  512  are marked with an ‘A’, D′, or ‘0’ character to represent active, deleted, or zero (empty) data, respectively. Some or all of the blocks can represent a particular size or chunk of data; 1 Mb block sizes are used in some NTFS file system implementations, for example. 
     Some or all of the blocks  512  can be mapped by the block mapping process  400  to a corresponding unit  522  of a map  520 . In the depicted embodiment, the map  520  is a bitmap, and each unit  522  of the map represents one bit of storage. Thus, the block mapping process  400  can map the file system blocks  512  to bit units  522  (“bits  522 ”) in the map  520 . As each unit  522  is one bit large in some embodiments, the map  520  can consume far less memory than the file system  510  and therefore can be an efficient way to store block status information. In certain embodiments, the map  520  can also be compressed to further reduce its storage impact. 
     In the depicted embodiment, the bits  522  in the map  520  include a ‘1’ to represent active blocks  512  and a ‘0’ to represent inactive blocks, including both deleted and zero blocks  512 . Of course, the roles of the ‘1’ and ‘0’ characters can be reversed or other symbols can be used to represent active and inactive blocks. In another embodiment, a third symbol can be used to distinguish deleted and zero blocks  512 . The bits  522  can be packed into bytes or octets so as to be addressable in most storage systems. In other embodiments, a single byte or other unit of storage can be used to represent each block  512 . 
     Data structures other than maps can be used to store block  512  status information. For example, database tables, lists, arrays, or other structures can be used to store status information. Many other storage options will be apparent from this disclosure. 
     V. Restore 
       FIG. 6  illustrates an embodiment of a restore process  600  for restoring a virtual machine image. Like the processes  300 ,  400  described above, the restore process  600  can be implemented by the systems  100  or  200 . For example, the restore process  600  can be implemented by the management server  120 , or more specifically, the backup module  222  of the management server  120 . In certain embodiments, the backup module  222  accesses the virtual disk map  244  created by the mapping module  224  to rapidly restore the backup virtual disk file  242 . 
     At state  602 , zeros are written to blocks in a restore file to provide a clean file when restoring a virtual machine image. Advantageously, in certain embodiments, these zeros can be written at disk subsystem speeds and can be faster than restoring zero blocks over a network. 
     A map of active and inactive blocks is accessed at state  604 , for example, from the backup server  140 . Active blocks are identified in the map at state  606 . The active blocks are then restored by overwriting the zero blocks in the proper locations at state  608 . In certain embodiments, state  602  can be omitted from the restore process  600 . 
     VI. Terminology 
     Depending on the embodiment, certain acts, events, or functions of any of the algorithms described herein can be performed in a different sequence, can be added, merged, or left out all together (e.g., not all described acts or events are necessary for the practice of the algorithm). Moreover, in certain embodiments, acts or events can be performed concurrently, e.g., through multi-threaded processing, interrupt processing, or multiple processors or processor cores or on other parallel architectures, rather than sequentially. 
     The various illustrative logical blocks, modules, and algorithm steps described in connection with the embodiments disclosed herein can be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. The described functionality can be implemented in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the disclosure. 
     The various illustrative logical blocks and modules described in connection with the embodiments disclosed herein can be implemented or performed by a machine, such as a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor can be a microprocessor, but in the alternative, the processor can be a controller, microcontroller, or state machine, combinations of the same, or the like. A processor can also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration. 
     The steps of a method, process, or algorithm described in connection with the embodiments disclosed herein can be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module can reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of computer-readable storage medium known in the art. An exemplary storage medium can be coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium can be integral to the processor. The processor and the storage medium can reside in an ASIC. The ASIC can reside in a user terminal. In the alternative, the processor and the storage medium can reside as discrete components in a user terminal. 
     Conditional language used herein, such as, among others, “can,” “might,” “may,” “e.g.,” and the like, unless specifically stated otherwise, or otherwise understood within the context as used, is generally intended to convey that certain embodiments include, while other embodiments do not include, certain features, elements and/or states. Thus, such conditional language is not generally intended to imply that features, elements and/or states are in any way required for one or more embodiments or that one or more embodiments necessarily include logic for deciding, with or without author input or prompting, whether these features, elements and/or states are included or are to be performed in any particular embodiment. 
     While the above detailed description has shown, described, and pointed out novel features as applied to various embodiments, it will be understood that various omissions, substitutions, and changes in the form and details of the devices or algorithms illustrated can be made without departing from the spirit of the disclosure. As will be recognized, certain embodiments of the inventions described herein can be embodied within a form that does not provide all of the features and benefits set forth herein, as some features can be used or practiced separately from others. The scope of certain inventions disclosed herein is indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.