Gang migration of virtual machines using cluster-wide deduplication

• US 9,372,726 B2
• Filed: 12/20/2013
• Issued: 06/21/2016
• Est. Priority Date: 01/09/2013
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Gopalan, Kartik
• Primary Examiner(s): Kim, Dong
• Application Number:
  US14/137,131
• Publication Number:
  US 20140196037A1
• Time in Patent Office: 914 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• 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/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence

Abstract

Datacenter clusters often employ live virtual machine (VM) migration to efficiently utilize cluster-wide resources. Gang migration refers to the simultaneous live migration of multiple VMs from one set of physical machines to another in response to events such as load spikes and imminent failures. Gang migration generates a large volume of network traffic and can overload the core network links and switches in a data center. The present technology reduces the network overhead of gang migration using global deduplication (GMGD). GMGD identifies and eliminates the retransmission of duplicate memory pages among VMs running on multiple physical machines in the cluster. A prototype GMGD reduces the network traffic on core links by up to 51% and the total migration time of VMs by up to 39% when compared to the default migration technique in QEMU/KVM, with reduced adverse performance impact on network-bound applications.

Claims

1. A method for gang migration with global deduplication, comprising:

providing a datacenter comprising;

a first plurality of virtual machines in a first cluster having a first controller, defined by a first set of information residing in a first storage medium,

a second cluster having a second controller, defined by a second set of information residing in a second storage medium,

the first cluster and the second cluster each communicating with each other through respective communication ports to at least one data communication network;

maintaining a first hash table of the memory pages of the first storage medium and a second hash table of the memory pages of the second storage medium;

performing a first cluster-wide deduplication of the first plurality of virtual machines, to identify first redundant memory pages of the first storage medium representing the respective virtual machines of the first cluster that have corresponding memory page content to each other based on at least the hashing of the memory pages;

tracking memory pages in the first storage medium that have changed content after hashing;

periodically exchanging the first and second hash tables between the first cluster and the second cluster through the at least one communication network;

initiating a simultaneous live migration of the first plurality of virtual machines, by communicating information to reconstitute the first plurality of virtual machines as a second plurality of virtual machines in the second cluster defined by a second set of information residing in a second storage niedium, through the at least one data communication network, after at least one exchange of the first and second hash tables;

receiving at least one memory page by the second cluster from a third cluster distinct from the first and second clusters, and updating the periodically exchanged second hash table to reflect the received at least one memory page from the third cluster;

based on the identification of the first redundant memory pages, the periodically exchanged first and second hash tables, and tracked memory pages that have changed content after hashing, selectively communicating information representing the unique memory pages of the first storage medium that are not already present in the second storage medium through the at least one communication network to the second storage medium without communicating more than one copy of unchanged redundant memory pages of the first storage medium or any copy of a memory page already in the second storage medium, and updating the periodically exchanged second hash table to reflect the communicated unique memory pages from the first cluster; and

subsequent to communication of the information representing the unique memory pages of the first storage medium through the at least one communication network, duplicating within the second cluster by the second controller, the redundant memory pages of the first storage medium and memory pages already in the second storage medium required for the second plurality of virtual machines, to reconstitute the second plurality of virtual machines within the second cluster.

2. The method according to claim 1, wherein the first cluster comprises a first rack, the second cluster comprises a second rack, each of the first and second racks has a top-of-the-rack switch which manages communications through the through at least one data communication network, wherein the at least one data communication network has a bandwidth of at least 1 Gbps.

3. The method according to claim 1, wherein the first hash table and the second hash table comprise a respective 160 bit hash for each respective memory page.

4. The method according to claim 1, wherein the tracking memory pages in the first storage medium that have changed content after hashing comprises providing a hypervisor configured to control a respective virtual machine, mark all memory pages of a respective virtual machine as write-only after hashing, maintain a shadow page table, trap a first write attempt to a respective memory page, update the shadow page table after the first write attempt to reflect the change, and permit the write attempt to proceed.

5. The method according to claim 1, wherein the second cluster is configured to receive a third hash table from the third cluster, and to r a memory page from he third cluster that is also present on the first cluster.

6. The method according to claim 1, wherein the first controller maintains a page status for each memory page, and updates the page status for a respective memory page when the memory page is sent from the first cluster to the second cluster.

7. The method according to claim 1, wherein the first controller resides within a respective virtual machine on the first cluster and the second controller resides within a respective virtual machine on the second cluster.

8. The method according to claim 7, wherein the first controller comprises has a memory space in a shared memory region which is inaccessible to the first plurality of virtual machines of the first cluster, and the first controller has access to the first set of information residing in a first storage medium.

9. The method according to claim 8, wherein the first controller calculates the first hash table from the first set of information residing in a first storage medium.

10. The method according to claim 1, wherein the first cluster further comprises a deduplication server, a third controller and a third plurality of virtual machines, wherein the first controller calculates the first hash table from the first set of information residing in a first storage medium for the first plurality of virtual machines, the third controller calculates a third hash table from a third set formation residing in a third storage medium for the third plurality of virtual machines, and the deduplication server maintains a fourth hash table representing a composite of the first hash table and the third hash table, and an indication of duplicate memory pages within the first storage medium and the third storage medium.

11. A system for gang migration with global deduplication, in a datacenter comprising a plurality of virtual machines in a first cluster defined by a set information residing in a first storage medium, the first cluster communicating through at least one data communication network, comprising:

at least one first memory configured to store a first hash table representing hash values for memory pages of the first storage medium;

at least one second memory configured to store a second hash table representing hash values of memory pages of a second cluster, distinct from the first cluster;

at least one third memory configured to store an indication that a respective memory page of the first storage medium has a changed content since a prior hash value for the respective memory page was calculated;

at least one processor configured to perform cluster-wide deduplication of the plurality of virtual machines of the first cluster to identify redundant memory pages of the first storage medium representing the respective virtual machines that have corresponding content;

at least one communication link configured to communicate through the at least one communication network, to;

periodically communicate the first hash table from the at least one first memory to the second cluster and to receive the second hash from the second cluster through the at least one data communication network to the at least one second memory; and

perform a simultaneous live migration of the plurality of virtual machines in the first cluster, by communicating information for reconstituting the plurality of virtual machines to the second cluster defined by a set of information residing in a second storage medium;

the at least one processor being further configured, based on the identification of the redundant memory pages having corresponding content, the at least one second memory, and at least one third memory, to selectively communicate information representing the unique memory pages of the first storage medium not present on the second storage medium, through the at least one communication network to the second storage medium, without communicating redundant copies and memory pages having unchanged content of the memory pages of the first storage medium.

12. The system according to claim 11, wherein the first cluster comprises a first rack, the second cluster comprises a second rack, each of the first and second racks has a top-of-the-rack switch which manages communications through the through at least one data communication network, wherein the at least one data communication network has a bandwidth of at least 1 Gbps.

13. The system according to claim 11, wherein the first hash table and the second hash table comprise a respective 160 bit hash for each respective memory page.

14. The system according to claim 11, wherein the third memory has a content defined by a hypervisor configured to control a respective virtual machine, mark all memory pages of a respective virtual machine as write-only after hashing, maintain a shadow page table, trap a first write attempt to a respective memory page, update the shadow page table after the first write attempt to reflect the change, and permit the write attempt to proceed.

15. The system according to claim 11, wherein the second cluster is configured to receive a third hash table from a third cluster, and to request a memory page from the third cluster that is also present on the first cluster.

16. The system according to claim 11, wherein the first cluster comprises a first controller configured to maintain a page status for each memory page, and to update the page status for a respective memory page when the memory page is sent from the first cluster to the second cluster.

17. The system according to claim 11, further comprising a first controller which resides within a respective virtual machine on the first cluster and a second controller which resides within a respective virtual machine on the second cluster, wherein the first controller comprises has a memory space in a shared memory region which is inaccessible to the first plurality of virtual machines of the first cluster, and the first controller has access to the first set of information residing in a first storage medium to generate the first hash table.

18. The system according to claim 11, wherein an order of transmission of respective memory pages of the plurality of virtual machines is dependent on respective virtual machine identifier.

19. The system according to claim 11, wherein the first cluster further comprises a first controller, a deduplication server, a third controller and a third plurality of virtual machines, wherein:

the first controller is configured to calculate the first hash table from the first set of information residing in a first storage medium for the first plurality of virtual machines,

the third controller is configured to calculate a third hash table from a third set of information residing in a third storage medium for the third plurality of virtual machines, and

the at least one processor is configured to implement the deduplication server configured to maintain a fourth hash table representing a composite of the first hash table and the third hash table, and an indication of duplicate memory pages within the first storage medium and the third storage medium.

20. A method for migration of virtual machines with global deduplication, comprising:

providing a plurality of virtual machines having an active status for processing workload at a local facility, defined by a set of stored information comprising redundant portions, the network being interconnected with a wide area network;

identifying at least a subset of the redundant portions of the stored information;

generating a hash table of hashes of respective memory pages of the plurality of virtual machines, and maintaining a list of respective memory pages that have changed content after the respective hash is generated;

periodically transmitting the generated hash table, and periodically receiving a remote hash table from a remote location providing an identifier of content of pages present at the remote location, through the wide area network;

initiating a simultaneous migration of the plurality of virtual machines by communicating through the wide area network to the remote location information for reconstituting the plurality of virtual machines at the remote location from;

information comprising portions of the set of stored information that are not identified as the redundant portions, and

portions of the stored information whose content has changed after the respective hash is generated, and

excluding redundant copies of the subset of the redundant portions of the stored information and information already present at the remote location;

receiving at a remote location the data to reconstitute the plurality of virtual machines;

duplicating the subset of the redundant portions of the stored information to reconstitute the set of stored information defining the plurality of virtual machines and the information already present at the remote location; and

transferring the active status from the plurality of virtual machines to the reconstituted plurality of virtual machines at the remote location, such that the reconstituted plurality of virtual machines at the remote location assume processing of the workload from the plurality of virtual machines at the local facility.