Abstract:
A system for progressive just-in-time restoration of data from backup media. Backup data may be stored on any kind of media such as DAS disk, object storage, USB drive, network share or tape. The backup data does not need to reside on contiguous media and can span multiple media. An index map is maintained that represents contiguous blocks of backup data of a volume. The backup data may be compressed, encrypted, or de-duplicated. The backup data may be located on different media, object stores, or network shares, or differing geographic locations. To perform a recovery, a virtual LUN is provided to the operating system and applications of the restored computer.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/842,563, filed Jul. 3, 2013. 
     
    
     BACKGROUND 
       [0002]    The present disclosure is in the field of information technology, and more particularly relates to enterprise backup and disaster recovery. 
         [0003]    Commonly assigned U.S. Pat. No. 8,346,726, which is incorporated herein by reference, discloses systems and methods for providing backups of computing systems, which provide for instant restoration of those systems as virtual machines. Additional methods for instantly available backups through virtual LUNs are disclosed in, for example, commonly assigned U.S. Pat. No. 7,937,547, also incorporated herein by reference. The hardware and software environment in which some of the embodiments of the disclosed subject matter operate is described in the &#39;726 and &#39;547 patents. 
       SUMMARY 
       [0004]    The purpose and advantages of the disclosed subject matter will be set forth in and apparent from the description that follows, as well as will be learned by practice of the disclosed subject matter. Additional advantages of the disclosed subject matter will be realized and attained by the methods and systems particularly pointed out in the written description and claims hereof, as well as from the appended drawings. 
         [0005]    To achieve these and other advantages and in accordance with the purpose of the disclosed subject matter, as embodied and broadly described, the disclosed subject matter includes a method of data backup and restoration. A backup of a source volume is created. The backup is divided into a plurality of chunks. Each chunk comprises a plurality of blocks. Each of the plurality of chunks is copied to a location in a cloud storage. An index is maintained indicating the location of each of the plurality of chunks in the cloud storage. A virtual volume is provided. The virtual volume includes a data cache and a cloud storage interface. The virtual volume is mounted on a computer system. The virtual volume receives a read request for a first block. A first location in cloud storage associated with a first chunk of the plurality of chunks is determined from the index such that the first chunk comprises the first block. The first chunk is copied from the first location in cloud storage to the data cache via the cloud storage interface. The read request is fulfilled from the data cache. 
         [0006]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and are intended to provide further explanation of the disclosed subject matter claimed. 
         [0007]    The accompanying drawings, which are incorporated in and constitute part of this specification, are included to illustrate and provide a further understanding of the method and system of the disclosed subject matter. Together with the description, the drawings serve to explain the principles of the disclosed subject matter. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    A detailed description of various aspects, features, and embodiments of the subject matter described herein is provided with reference to the accompanying drawings, which are briefly described below. The drawings are illustrative and are not necessarily drawn to scale, with some components and features being exaggerated for clarity. The drawings illustrate various aspects and features of the present subject matter and may illustrate one or more embodiment(s) or example(s) of the present subject matter in whole or in part. 
           [0009]      FIG. 1  is a schematic representation of a restoration system according to an embodiment of the present disclosure. 
           [0010]      FIG. 2  is a schematic representation of chunking according to an embodiment of the present disclosure. 
           [0011]      FIG. 3  is a schematic representation of de-duplication according to an embodiment of the present disclosure. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The following is a description of several preferred embodiments of various aspects of the disclosed subject matter, showing details of how systems may be constructed to carry out various aspects of the disclosure, and the steps that can be employed to utilize such systems and to practice such methods. These embodiments are illustrative only, and the disclosed subject matter is by no means limited to particular examples shown. The specific features of any particular embodiment should not be understood as limiting the scope of what is claimed. 
         [0013]    In addition, it should be understood that the accompanying figures are presented for illustrative purposes only. The disclosed methodology and system are each sufficiently flexible and configurable such that they may be utilized in ways other than those depicted. 
         [0014]    In various embodiments, program instructions are provided. Such program instructions may be recorded on non-transitory machine-readable media. Non-transitory machine-readable media include computer-readable media exclusive of transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media, or electrical signals transmitted through a wire. Examples of non-transitory machine-readable media include, without limitation, hard disks drives, solid-state drives, other optical and magnetic storage media known in the art, random access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM), compact disc (CD), DVD, floppy disks, and punch cards. 
         [0015]    Various operations described herein may be carried out by one or more computer processors. Suitable processors include general those present in general purpose computers, special purpose computers, and ASICs. Operations executable by such processors include transmission and receipt of data via a network. In various embodiments, transmission and reception may be performed via a network interface. Suitable data networks include LANs, WANs, and the Internet. In other embodiments, logic may be provided in the form of discrete logic or programmable logic arrays, which perform the specified operations through a combination of hardware elements. 
         [0016]    The methods and systems presented herein may be used to provide progressive restoration of a backup. The disclosed subject matter is particularly suited for progressive restoration from a remote storage system such as cloud storage in response to ongoing data requests. For purpose of explanation and illustration, and not limitation, an exemplary embodiment of the system in accordance with the disclosed subject matter is shown in  FIG. 1  and is designated generally by reference character  100 . Similar reference numerals (differentiated by the leading numeral) may be provided among the various views and Figures presented herein to denote functionally corresponding, but not necessarily identical structures. 
         [0017]    According to embodiments of the present disclosure, a storage client provides just in time restoration of data. The storage client may provide a virtual file system, for example, through a plugin to FUSE (Filesystem in Userspace). The virtual file system may be backed by one or more arbitrary storage media. In some embodiments, a FUSE plugin is backed by cloud storage such as buckets in Amazon S3 (Simple Storage Service). Restoration of data is provided via a virtual logical disk, for example via an iSCSI logical unit. Rather than automatically proceeding to restore an entire volume or file, data is restored as needed to satisfy requests made during the course of usage in production. 
         [0018]    Referring to  FIG. 1 , a system according to one embodiment of the present disclosure is provided. Client  101  includes a FUSE plugin  102  to FUSE  103 . FUSE plugin  102  includes a filesystem mount  104 , a translator module  105  and an API client  106 . API client  106  accesses cloud storage  105  via a network such as the Internet (not pictured). Filesystem mount  104  provides access to storage  108 , which in some embodiments is an NFS or CIFS volume. The translator module  105  is responsible for translating data requests for the API client  106  and the filesystem mount  104 . In some embodiments, translator  105  maintains an index map (discussed further below). In some embodiments, the API client  106  is a REST API client and cloud storage  107  is Amazon S3. However, other combinations of cloud storage providers and APIs may be used by API client  106 . 
         [0019]    Client  101  provides an iSCSI target  109  that is accessible via a network (not pictured) by client  110 . To restore data previously backed up to cloud storage  107 , individual data blocks are retrieved from cloud storage  107  as needed by the operating system or application. 
         [0020]    In some embodiments, a data backup is created that is segmented or chunked into smaller parts. Chunking the backup data provides the ability to selectively restore data without the requirement to restore the entire backup at once. Chunking additionally allows the backup data to span multiple media. In some embodiments, multiple chunks are stored as multiple objects or files. In some embodiments, data chunks are replicated in parallel. During a backup process of a volume, an index map (SDA) is created that describes each block of the volume and the location of the data chunk where the data is stored. The index map is kept both on backup media with the data chunk and in a central database. The index map keeps track of replicas of each volume backup. The index map further includes location data for each data chunk. Using the location data, the recovery process may preferentially retrieve from the closest available location. 
         [0021]    As shown in  FIG. 2 , chunks  201 ,  202 ,  203  may comprise a plurality of blocks and may reside in cloud storage  204  (e.g., Amazon S3) or at a local mount point  205 . A volume copy  206 ,  207  of volume  208  may refer to blocks in one or more chunks. 
         [0022]    In addition to allowing retrieval of data in the course of restoration, the index map allows global de-duplication among all backups. In particular, by including identifying information such as a hash value for each backed up chunk, any duplicate data blocks may share the same backup chunk. Additionally, full and incremental backups may be merged to provide restoration of a physical volume at a selected time. 
         [0023]    As depicted in  FIG. 3 , base backups  301 ,  302  may be made of volumes  303 ,  304 . A plurality of subsequent delta backups  305 ,  306 ,  307 ,  308  may be made. Delta backups  306 ,  307 , may refer to the same block in order to avoid duplication. Similarly, deltas  305 ,  308  of different volumes may also refer to the same blocks to avoid duplication. 
         [0024]    An exemplary embodiment of the index map is described at  Insets  1-5, below. 
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Inset 1 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Volume 
               
               
                   
                 { 
               
               
                   
                  client_node_id; 
               
               
                   
                  volumeid; 
               
               
                   
                  mountpoint; 
               
               
                   
                  os_type; 
               
               
                   
                  os_version; 
               
               
                   
                  fs_type; 
               
               
                   
                  Volume_Copy { } 
               
               
                   
                  Volume_Copy { } 
               
               
                   
                  . . . 
               
               
                   
                 } 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Inset 2 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Volume_Copy 
               
               
                   
                 { 
               
               
                   
                  Base 
               
               
                   
                  { 
               
               
                   
                   Time { } 
               
               
                   
                   Bitmap_Index { } 
               
               
                   
                  } 
               
               
                   
                  Delta 
               
               
                   
                  { 
               
               
                   
                   Time 
               
               
                   
                   Bitmap_Index { } 
               
               
                   
                  } 
               
               
                   
                  Delta 
               
               
                   
                  { 
               
               
                   
                   Time 
               
               
                   
                   Bitmap_Index { } 
               
               
                   
                  } 
               
               
                   
                  . . .  
               
               
                   
                 } 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Inset 3 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Bitmap_Index 
               
               
                   
                 { 
               
               
                   
                  Block { } 
               
               
                   
                  Block { } 
               
               
                   
                  . . . 
               
               
                   
                 } 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Inset 4 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Block  
               
               
                   
                 { 
               
               
                   
                  Compression_Type { } 
               
               
                   
                  Length { } 
               
               
                   
                  Compressed_Length { } 
               
               
                   
                  Block_Offset 
               
               
                   
                  Is_Sparse { } 
               
               
                   
                  SHA256 Hash ( use for dedupe ) 
               
               
                   
                  Chunk_ID 
               
               
                   
                  Chunk_Offset 
               
               
                   
                 } 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Inset 5 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Chunk 
               
               
                   
                 { 
               
               
                   
                  chunk_id; 
               
               
                   
                  storage_pool_id; 
               
               
                   
                  location_id; 
               
               
                   
                  objectstore 
               
               
                   
                  { 
               
               
                   
                   accesspoint: https://s3.amazon.us.com/:443 
               
               
                   
                   bucket: mybackupslocation 
               
               
                   
                   secret key: &lt; &gt; 
               
               
                   
                   access key: &lt; &gt; 
               
               
                   
                  } 
               
               
                   
                  tapemedia 
               
               
                   
                  { 
               
               
                   
                   . . . 
               
               
                   
                  } 
               
               
                   
                  Networkshare 
               
               
                   
                  { 
               
               
                   
                   . . . 
               
               
                   
                  } 
               
               
                   
                  Localmountpoint 
               
               
                   
                  { 
               
               
                   
                   . . . 
               
               
                   
                  } 
               
               
                   
                  Usbdrive 
               
               
                   
                  { 
               
               
                   
                   . . . 
               
               
                   
                  } 
               
               
                   
                 } 
               
               
                   
               
             
          
         
       
     
         [0025]    To recover a volume, a virtual disk is exposed that provides the same data as the original volume at the time backup was taken. The virtual disk does not perform a restore operation for a given block of data from backup media until that block of data is requested by an operating system or application accessing the virtual disk. 
         [0026]    In some embodiments, an instant data recovery appliance houses an iSCSI, SCSI, or FC target and provides a virtual storage file. The virtual storage file does not use any storage space until data is requested by the operating system or applications. The chunks of data are read from backup media as they are requested by the iSCSI, SCSI, or FC target system. As data is read from media, chunks of data are cached in local storage. To increase performance given the overhead of reading from backup media, instead of retrieving only a block of data, the entire chunk of data that holds the data block is read and cached in local storage. Each chunk of data may hold multiple blocks of data. Since backup media may be high-latency storage such as tape or cloud object storage, overall performance is increased by reading a large chunk of data instead of a block of data at a time. For example, a given filesystem may have 2 kilobytes blocks, while chunks may be 50 megabytes or larger. If local cache storage is full, the least used chunks may be removed to make space for newly requested data chunk. 
         [0027]    In cases where a bare metal recovery is required, such as where the original operating system on the physical machine has been destroyed, the machine may be booted into a recovery mode. The machine may be booted using a modular device such as a USB drive, network boot, or CD/DVD. In recovery mode, a boot partition is installed and an operating volume is restored by reading data from a network or USB drive. Once the operating system volume is recovered, the application volumes or any non-OS volumes are mounted via iSCSI, SCSI, or FC targets via the virtual disk as described above. If the operating system is capable of booting from iSCSI, FC, or SCSI target then virtual LUN recovery may be performed for the operating system volumes. If recovery of a virtual machine is required, both operating system and application volumes are provided as virtual LUNs. 
         [0028]    The virtual LUN that is presented from backup media will allow operating system and applications to write data to the virtual disk as if it were primary storage. Any new write data is cached locally on recovery appliance. At set intervals, the new data is backed up to backup media. Data chunks that have been the subject of write operations are flagged, and are not removed from the local cache storage until it has been transferred to backup media. 
         [0029]    Further advantages of the virtual LUN of the present disclosure are apparent where data storage and data retrieval are asymmetric in speed or cost. For example, where downstream bandwidth is lower than upstream bandwidth, the virtual LUN of the present disclosure allows immediate restoration without the delays involved in downloading an entire backup. Similarly, where downloads are subject to higher service charges than uploads, it is advantageous to download the minimum amount of data necessary. In these and similar cases, the present disclosure enables cost and resource efficient data restoration. 
         [0030]    While the disclosed subject matter is described herein in terms of certain exemplary embodiments, those skilled in the art will recognize that various modifications and improvements may be made to the disclosed subject matter without departing from the scope thereof Moreover, although individual features of one embodiment of the disclosed subject matter may be discussed herein or shown in the drawings of the one embodiment and not in other embodiments, it should be apparent that individual features of one embodiment may be combined with one or more features of another embodiment or features from a plurality of embodiments. 
         [0031]    In addition to the specific embodiments claimed below, the disclosed subject matter is also directed to other embodiments having any other possible combination of the dependent features claimed below and those disclosed above. As such, the particular features presented in the dependent claims and disclosed above can be combined with each other in other manners within the scope of the disclosed subject matter such that the disclosed subject matter should be recognized as also specifically directed to other embodiments having any other possible combinations. Thus, the foregoing description of specific embodiments of the disclosed subject matter has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the disclosed subject matter to those embodiments disclosed. 
         [0032]    While various embodiments have been described, it should be understood that they have been presented by way of example and not limitation. It will be apparent to persons skilled in the relevant art(s) that various changes in form and detail can be made therein without departing from the spirit and scope of the disclosed subject matter. Thus, the present embodiments should not be limited by any of the above-described embodiments. Accordingly, it is intended that the disclosed subject matter include modifications and variations that are within the scope of the claims appended to (and forming a part of) this disclosure, and their equivalents.