Deduplication of virtual machine content

• US 9,569,124 B2
• Filed: 02/20/2015
• Issued: 02/14/2017
• Est. Priority Date: 11/04/2014
• Status: Active Grant

• Current Assignee: Rubrik, Inc.
• Original Assignee: Rubrik, Inc.
• Inventors: Jain, Arvind, Mazumdar, Soham, Botelho, Fabiano
• Primary Examiner(s): CHEN, SHIN HON
• Application Number:
  US14/628,022
• Publication Number:
  US 20160124676A1
• Time in Patent Office: 725 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1484 involving virtual machines
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: G06F 2009/45562 Creating, deleting, cloning virtual machine instances
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45579 I/O management, e.g. providing access to device drivers or storage
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2201/80 : Database-specific techniques
• CPC Class Codes: G06F 2201/815 : Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 2201/84 : Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0619 : in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 : De-duplication techniques
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0665 : at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 9/45558 : Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5077 : Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: H04L 43/0817 : by checking functioning
• CPC Class Codes: H04L 61/5007 : Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/5061 : Pools of addresses
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 9/3242 : involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 : involving digital signatures

Abstract

Methods and systems for managing, storing, and serving data within a virtualized environment are described. In some embodiments, a data management system may manage the extraction and storage of virtual machine snapshots, provide near instantaneous restoration of a virtual machine or one or more files located on the virtual machine, and enable secondary workloads to directly use the data management system as a primary storage target to read or modify past versions of data. The data management system may allow a virtual machine snapshot of a virtual machine stored within the system to be directly mounted to enable substantially instantaneous virtual machine recovery of the virtual machine.

Claims

1. A method for operating a data management system, comprising:

acquiring a first snapshot of a first virtual machine, the first snapshot comprises a full image of the first virtual machine;

generating a signature for the first virtual machine using the full image, the generating a signature includes generating a plurality of hash values corresponding with a plurality of data blocks within the full image, the plurality of data blocks is arranged such that data blocks of a first plurality of the plurality of data blocks are spaced at a fixed distance from each other and data blocks of a second plurality of the plurality of data blocks are spaced at monotonically increasing distances from each other;

identifying a second virtual machine based on the signature, the second virtual machine is associated with a base image;

generating a dependent base file associated with the first snapshot using the full image and the base image, the dependent base file comprises data differences between the first snapshot of the first virtual machine and a second snapshot of the second virtual machine corresponding with the base image, the first plurality corresponds with a first data region within the full image of the first virtual machine, the second plurality corresponds with a second data region within the full image of the first virtual machine that does not overlap with the first data region; and

storing the dependent base file.

2. The method of claim 1, wherein:

each data block of the first plurality is separated by a fixed length; and

each data block of the second plurality is separated by an increasing data length.

3. The method of claim 1, wherein:

the plurality of data blocks comprises a plurality of noncontiguous data blocks, each data block of the plurality of noncontiguous data blocks does not overlap with any of the other data blocks of the plurality of noncontiguous data blocks, each data block of the plurality of noncontiguous data blocks does not share a data boundary with any of the other data blocks of the plurality of noncontiguous data blocks.

4. The method of claim 1, wherein:

the generating a signature includes generating an ordered list of the plurality of hash values; and

the identifying a second virtual machine based on the signature includes acquiring a second signature associated with the second virtual machine and determining a number of matched hashes between the ordered list of the plurality of hash values and the second signature.

5. The method of claim 1, further comprising:

acquiring a memory size associated with an operating system for the first virtual machine; and

determining the first plurality of the plurality of data blocks based on the memory size.

6. The method of claim 1, further comprising:

acquiring a memory size associated with an operating system for the first virtual machine; and

determining a first portion of the full image based on the memory size, the plurality of data blocks is arranged such that a majority of the plurality of data blocks is located within the first portion of the full image.

7. The method of claim 6, wherein:

the first portion of the full image is located at a beginning of the full image.

8. The method of claim 1, further comprising:

determining a memory location within the full image associated with an operating system for the first virtual machine; and

determining the first plurality of the plurality of data blocks based on the memory location within the full image.

9. The method of claim 1, wherein:

the dependent base file comprises data differences between the full image and the base image.

10. The method of claim 1, wherein:

the generating a plurality of hash values includes applying a cryptographic hash function to each of the plurality of data blocks within the full image.

11. The method of claim 1, wherein:

the plurality of data blocks comprises a first data block that is equal to or less than 10 KB in size and a second data block that is equal to or less than 10 KB in size, the full image of the first virtual machine comprises more than 1 GB of data.

12. A data management system, comprising:

a memory configured to store a first snapshot of a first virtual machine, the first snapshot comprises a full image of the first virtual machine; and

one or more processors configured to generate a signature for the first virtual machine using the full image, the signature includes a plurality of hash values corresponding with a plurality of data blocks within the full image, the plurality of data blocks is arranged such that data blocks of a first plurality of the plurality of data blocks are spaced at a fixed distance from each other and data blocks of a second plurality of the plurality of data blocks are spaced at monotonically increasing distances from each other, the one or more processors configured to identify a second virtual machine different from the first virtual machine based on the signature, the second virtual machine is associated with a base image, the one or more processors configured to generate a dependent base file associated with the first snapshot using the full image and the base image and cause the dependent base file to be stored, the first plurality corresponds with a first data region within the full image of the first virtual machine and the second plurality corresponds with a second data region within the full image of the first virtual machine that does not overlap with the first data region.

13. The data management system of claim 12, wherein:

the one or more processors configured to cause the dependent base file to be stored in the memory;

each data block of the first plurality is separated by a fixed data length; and

each data block of the second plurality is separated by an increasing data length.

14. The data management system of claim 12, wherein:

the plurality of data blocks comprises a plurality of noncontiguous data blocks, each data block of the plurality of noncontiguous data blocks does not overlap with any of the other data blocks of the plurality of noncontiguous data blocks, each data block of the plurality of noncontiguous data blocks does not share a data boundary with any of the other data blocks of the plurality of noncontiguous data blocks.

15. The data management system of claim 12, wherein:

the signature comprises an ordered list of the plurality of hash values; and

the one or more processors configured to acquire a second signature associated with the second virtual machine and determine a number of matched hashes between the ordered list of the plurality of hash values and the second signature, the one or more processors configured to identify the second virtual machine based on the number of matched hashes.

16. The data management system of claim 12, wherein:

the one or more processors configured to acquire a memory size associated with an operating system for the first virtual machine and determine a first portion of the full image based on the memory size, the plurality of data blocks is arranged such that a majority of the plurality of data blocks is located within the first portion of the full image.

17. The data management system of claim 16, wherein:

the first portion of the full image is located at a beginning of the full image.

18. The data management system of claim 12, wherein:

the one or more processors configured to determine a memory location within the full image associated with an operating system for the first virtual machine and determine the first plurality of the plurality of data blocks based on the memory location within the full image.

19. The data management system of claim 12, wherein:

the one or more processors configured to apply a cryptographic hash function to each of the plurality of data blocks within the full image to generate the plurality of hash values.

20. One or more storage devices containing processor readable code for programming one or more processors to perform a method for operating a data management system, the processor readable code comprising:

processor readable code configured to acquire a first snapshot of a first virtual machine, the first snapshot comprises a full image of the first virtual machine;

processor readable code configured to generate a signature for the first virtual machine using the full image, the signature comprises an ordered list of a plurality of hash values, the plurality of hash values derive from a plurality of noncontiguous data blocks within the full image, the plurality of noncontiguous data blocks is arranged such that data blocks of a first plurality of the plurality of noncontiguous data blocks are spaced at a fixed distance from each other and data blocks of a second plurality of the plurality of noncontiguous data blocks are spaced at monotonically increasing distances from each other, the first plurality corresponds with a first data region within the full image of the first virtual machine and the second plurality corresponds with a second data region within the full image of the first virtual machine that does not overlap with the first data region;

processor readable code configured to identify a second virtual machine different from the first virtual machine based on the signature, the second virtual machine is associated with a base image;

processor readable code configured to generate a dependent base file associated with the first snapshot using the full image and the base image, the dependent base file comprises data differences between the first snapshot of the first virtual machine and a second snapshot of the second virtual machine corresponding with the base image; and

processor readable code configured to output the dependent base file from the data management system.