Gang migration of virtual machines using cluster-wide deduplication

• US 10,156,986 B2
• Filed: 11/20/2017
• Issued: 12/18/2018
• Est. Priority Date: 05/12/2014
• 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, Kartlik, Deshpande, Umesh
• Primary Examiner(s): Rossiter, Sean D
• Application Number:
  US15/818,163
• Publication Number:
  US 20180113610A1
• Time in Patent Office: 393 Days
• Field of Search: 711161-162
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 2009/45562 Creating, deleting, cloning virtual machine instances
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

Gang migration refers to the simultaneous live migration of multiple Virtual Machines (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 datacenter. In this paper, we present an approach to reduce 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. The design, implementation and evaluation of a GMGD prototype is described using QEMU/KVM VMs. Evaluations on a 30-node Gigabit Ethernet cluster having 10GigE core links shows that GMGD can reduce the network traffic on core links by up to 65% and the total migration time of VMs by up to 42% when compared to the default migration technique in QEMU/KVM. Furthermore, GMGD has a smaller adverse performance impact on network-bound applications.

Claims

1. A method of tracking duplication of memory content, comprising:

computing in each of a plurality of servers, a respective a hash value for each of a plurality of respective memory pages used by the plurality of servers;

communicating the hash value for each of the plurality of respective memory pages for the plurality of servers to a memory control server for the plurality of servers, to form a hash table;

transmitting the hash table of the memory control server for the plurality of servers through a communication network to a corresponding memory control server for a different plurality of servers;

receiving, from the corresponding memory control server, a corresponding hash table comprising a plurality of corresponding hash values for memory pages used by the different plurality of servers;

comparing, by the memory control server, the respective hash values in the hash table with the corresponding hash values in the corresponding hash table; and

determining memory duplication between the plurality of server and the plurality of different servers, based on said comparing.

2. The method according to claim 1, further comprising:

determining, by the memory control server, uniqueness of each memory page within the hash table; and

sending a single copy of unique memory page content to the corresponding memory control server.

3. The method according to claim 1, further comprising:

sending a copy of unique memory page content from the memory control server to the corresponding memory control server if the unique memory page content is not present at any of the different plurality of servers.

4. The method according to claim 1, further comprising:

receiving, by the memory control server, a memory page having unique memory page content not present in the plurality of respective memory pages used by the plurality of servers; and

duplicating, under control of the memory control server, the unique memory page content within the plurality of servers.

5. The method according to claim 4, wherein the plurality of servers are involved in a gang migration of a plurality of live servers comprising the plurality of servers to the plurality of different servers, further comprising communicating a central processing unit state for a respective live server from the memory control server to the corresponding memory control server.

6. The method according to claim 1, wherein the plurality of servers are organized in a cluster, running a plurality of virtual machines, which communicate with each other and the memory control server using a communication medium selected from the group consisting of Gigabit Ethernet, 10GigE, and Infiniband.

7. The method according to claim 1, wherein the plurality of servers implement a plurality of virtual machines, wherein the hash table of the memory control server is organized according to memory page association with a respective virtual machine.

8. The method according to claim 1, further comprising communicating, by the memory control server to the corresponding memory control server, a plurality of memory pages, each having unique memory page content, prioritized with respect to at least one of a memory page dirtying rate and a delta difference for dirtied memory pages.

9. The method according to claim 1, wherein said memory control server has a distributed architecture, and said determining memory duplication comprises implementing a distributed indexing mechanism which computes content hashes on a plurality of servers.

10. The method according to claim 9, wherein the distributed indexing mechanism comprises a distributed hash table.

11. The method according to claim 1, wherein each memory page has a unique identifier comprising a respective identification of an associated virtual machine.

12. The method according to claim 1, wherein the hash table further comprises a memory page status for each respective memory page.

13. The method according to claim 12, further comprising:

sending a respective memory page from the memory control server to the corresponding memory control server; and

updating the memory page status in the hash table with an indication that the respective memory page has been sent.

14. The method according to claim 1, further comprising:

maintaining, by the memory control server, a list of servers of the plurality of servers that require a copy of a respective memory page by the memory control server;

retrieving a copy of a respective memory page by the memory control server from the corresponding memory control server;

sending the retrieved copy of the respective memory page to each server of the plurality of servers that requires a copy of the respective memory page based on the list of servers; and

marking the memory page as having been sent in the hash table.

15. The method according to claim 14,

wherein the list of servers is sorted in order of most recently changed memory page;

said retrieving is performed according to the sorted order; and

after a respective memory page is marked as having been sent, the memory control server removes references to earlier versions of that respective memory page from the list of servers without overwriting any more recent copy of the respective memory page.

16. The method according to claim 1, further comprising performing a live gang migration of a plurality of virtual machines executing on the plurality of servers to the corresponding plurality of servers, wherein:

a respective virtual machine executing on the plurality of servers remains operational until at least one version of each memory page of the respective virtual machine is transferred to the corresponding plurality of servers;

the respective virtual machine is inactivated after at least one version of each memory page of the respective virtual machine is transferred to the corresponding plurality of servers; and

a replica of the respective virtual machine is activated to execute on the corresponding plurality of servers using the transferred at least one version of each memory page of the respective virtual machine.

17. A method for transfer of information to a plurality of servers in a server rack under control of a memory server, from a corresponding memory server, comprising:

determining the content redundancy in memory pages or sub-pages across the plurality of servers in the server rack at a respective time for each respective memory page or sub-page;

transferring, from the corresponding memory server to the memory server, a copy of each unique memory page or sub-page through a communication interface of the server rack;

determining, by the memory server, which of the plurality of servers in the server rack require the unique memory page or sub-page; and

duplicating, under control of the memory server, the unique memory page or sub-page within the server rack for each server that requires but did not receive the copy of the unique memory page or sub-page.

18. The method according to claim 17, wherein the plurality of servers are involved in a gang migration of a plurality of live servers, further comprising receiving by the memory server, a central processing unit state for a respective live server from the corresponding memory server.

19. A method for gang migration, comprising:

determining, by a memory server associated with the plurality of servers, a content redundancy in memory pages for use by a plurality of virtual machines to be gang migrated to the plurality of servers;

initiating a gang migration under control of the memory server, wherein only a single copy of each unique memory page according to the determined content redundancy is transferred during the gang migration to the plurality of servers, with a reference to each respective unique memory page for virtual machines that require but do not receive a copy of the unique memory page; and

after receipt of a unique memory page by the plurality of servers, communicating the unique memory page under control of the memory server to each virtual machine that requires but did not receive the copy of the unique memory page.

20. The method according to claim 19, wherein the plurality of servers are involved in a gang migration of a plurality of live virtual machines, further comprising receiving, by the memory server, a central processing unit state for each respective live virtual machine and activating each respective live virtual machine after receipt of its respective central processing unit state and communication of each unique memory page required by the respective live virtual machine.