Data suppression for faster migration

• US 10,083,062 B2
• Filed: 07/31/2015
• Issued: 09/25/2018
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kuik, Timothy, Thompson, David
• Primary Examiner(s): Kim, Sisley
• Application Number:
  US14/815,650
• Publication Number:
  US 20170031710A1
• Time in Patent Office: 1,152 Days
• Field of Search: None
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• 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 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence

Abstract

The subject technology addresses the need in the art for improving intra-cloud migration of virtual machines in a cloud computing environment. A hash database may be prepopulated with key-value pairs corresponding to hash IDs and associated data chunks of a virtual machine image. In this regard, the virtual machine image may be divided into chunks using boundaries chosen by a Rabin fingerprinting technique. A hash (e.g., MD5 or SHA-1) may be computed over each chunk and act as a unique identifier for the data contained in each chunk. At appropriate times, one or more hash IDs are sent instead of the actual data chunks between clouds when performing the inter-cloud migration of a virtual machine.

Claims

1. A system associated with a first data center providing cloud based services, the system comprising:

at least one processor;

an interface;

a local storage device;

a first hash database including a plurality of hash-data pair entries; and

memory including instructions that, which when executed by the at least one processor, cause the system to;

select, at a first time, a first data chunk from a virtual machine image, the virtual machine image being divided into a plurality of data chunks;

compute a hash identifier (ID) value for the first data chunk, the hash ID value being a key generated using a hash function;

determine whether the hash ID value matches a part of one of the plurality of hash-data pair entries in the first hash database; and

send, using the interface, the hash ID value without the first data chunk to a second data center if the hash ID value matches the part of the one of the plurality of hash-data pair entries in the first hash database, wherein the second data center does not store a replica of the virtual machine image at the first time, the second data center having a second hash database from which a corresponding processor retrieves the first data chunk.

2. The system of claim 1, wherein the memory includes further instructions, which when executed by the at least one processor, further cause the system to:

responsive to the hash ID value being absent from the first hash database, update the first hash database with a new hash-data pair entry comprising the hash ID value and the first data chunk;

compress the first data chunk using at least one compression algorithm; and

send, using the interface, the hash ID value and the compressed first data chunk to the second data center.

3. The system of claim 1, wherein the memory includes further instructions, which when executed by the at least one processor, further cause the system to:

send, using the interface, a logical block address corresponding to the first data chunk to the second data center, the logical block address indicating a location on a virtual disk for writing the first data chunk.

4. The system of claim 1, wherein the memory includes further instructions, which when executed by the at least one processor, further cause the system to:

select a second data chunk from the virtual machine image;

compute a second hash ID value for the second data chunk;

determine whether the second hash ID value is included as part of another one of the plurality of hash-data pair entries in the first hash database; and

upon determining that the second hash ID value is included as part of the other one of the plurality of hash-data pair entries in the first hash database, send, using the interface, the second hash ID value to the second data center as part of a migration of the virtual machine image from the first data center to the second data center.

5. The system of claim 4, wherein an LBA address of the second data chunk comprises a next sequential address following an LBA address of the first data chunk.

6. The system of claim 1, wherein the first data center comprises a first cloud deployment and the second data center comprises a second cloud deployment.

7. The system of claim 1, wherein the virtual machine image is divided into the plurality of data chunks based at least on a Rabin fingerprinting algorithm.

8. The system of claim 1, wherein the hash ID value forms the part of one of the plurality of hash-data pair entries in the first hash database.

9. A computer-implemented method, comprising:

selecting, at a first time, a first data chunk from a virtual machine image on a first data center providing cloud based services, the virtual machine image being divided into a plurality of data chunks;

computing a hash identifier (ID) value for the first data chunk, the hash ID value being a key generated using a hash function;

determining whether the hash ID value matches a part of one of a plurality of hash-data pair entries in a first hash database; and

sending the hash ID value without the first data chunk to a second data center if the hash ID value matches the part of the one of the plurality of hash-data pair entries in the first hash database, wherein the second data center does not store a replica of the virtual machine image at the first time, the second data center having a second hash database from which a corresponding processor retrieves the first data chunk.

10. The computer-implemented method of claim 9, further comprising:

responsive to the hash ID value being absent from the first hash database, updating the first hash database with a new hash-data pair entry comprising the hash ID value and the first data chunk;

compressing the first data chunk using at least one compression algorithm; and

sending the hash ID value and the compressed first data chunk to the second data center.

11. The computer-implemented method of claim 9, further comprising:

sending a logical block address corresponding to the first data chunk to the second data center, the logical block address indicating a location on a virtual disk for writing the first data chunk.

12. The computer-implemented method of claim 9, further comprising:

selecting a second data chunk from the virtual machine image;

computing a second hash ID value for the second data chunk;

determining whether the second hash ID value is included as part of another one of the plurality of hash-data pair entries in the first hash database; and

upon determining that the second hash ID value is included as part of the other one of the plurality of hash-data pair entries in the first hash database, sending the second hash ID value to the second data center as part of a migration of the virtual machine image from the first data center to the second data center.

13. The computer-implemented method of claim 12, wherein an LBA address of the second data chunk comprises a next sequential address following an LBA address of the first data chunk.

14. The computer-implemented method of claim 9, wherein the first data center comprises a first cloud deployment and the second data center comprises a second cloud deployment.

15. The computer-implemented method of claim 9, wherein the virtual machine image is divided into the plurality of data chunks based at least on a Rabin fingerprinting algorithm.

16. The computer-implemented method of claim 9, wherein the hash ID value forms the part of one of the plurality of hash-data pair entries in the first hash database.

17. A non-transitory computer-readable medium including instructions stored therein that, when executed by at least one computing device, cause the at least one computing device to:

select, at a first time, a first data chunk from a virtual machine image on a first data center providing cloud based services, the virtual machine image being divided into a plurality of data chunks;

compute a hash identifier (ID) value for the first data chunk, the hash ID value beinq a key generated using a hash function;

determine whether the hash ID value matches a part of one of a plurality of hash-data pair entries in a first hash database; and

send the hash ID value without the first data chunk to a second data center upon determining that the hash ID value matches the part of the one of the plurality of hash-data pair entries in the first hash database, wherein the second data center does not store a replica of the virtual machine image at the first time, the second data center having a second hash database from which a corresponding processor retrieves the first data chunk.

18. The non-transitory computer-readable medium of claim 17, including further instructions that cause the at least one computing device to:

responsive to the hash ID value being first hash database, update the first hash database with a new hash-data pair entry comprising the hash ID value and the first data chunk;

compress the first data chunk using at least one compression algorithm; and

send the hash ID value and the compressed first data chunk to the second data center.

19. The non-transitory computer-readable medium of claim 17, wherein the hash ID value forms the part of one of the plurality of hash-data pair entries in the first hash database.