Transparent load-balancing for cloud computing services

• US 8,958,293 B1
• Filed: 12/06/2011
• Issued: 02/17/2015
• Est. Priority Date: 12/06/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Anderson, Evan K.
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Qin, Zhiren
• Application Number:
  US13/312,872
• Time in Patent Office: 1,169 Days
• Field of Search: 370/230, 370/229, 370/235, 370/254
• US Class Current: 370/230
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

Systems and techniques are described for virtual machine (VM) load-balancing. A described technique includes running VMs that communicate via a virtual network, the VMs being configured to handle requests associated with at least a destination address on a public network and operating gateways that provide connectivity between the virtual network and the public network, and use a consistent mapping operation to perform load-balancing among the VMs. A gateway can obtain VM health information; determine based on the VM health information a group of healthy VMs; receive an incoming packet that includes a source address and the destination address; select a handling VM based on an output of the consistent mapping operation given the source address and the group of healthy VMs; forward the incoming packet to the handling VM via the virtual network; and create an entry to forward one or more additional incoming packets to the handling VM.

Claims

1. A method comprising:

executing virtual machines that are each configured to communicate with each other over a virtual network and are configured to handle requests associated with at least a destination address on a public network;

operating gateways, including a first gateway and a separate and distinct second gateway, that are each configured to provide connectivity between the virtual network and the public network, that each separately and independently implement a consistent mapping operation to perform load-balancing among the virtual machines, wherein at the first gateway a first mapping data structure includes entries reflecting mappings between source addresses and virtual machines, and wherein at the second gateway a distinct second mapping data structure includes entries reflecting mappings between source addresses and virtual machines;

independently obtaining health information of the virtual machines, by each of the first gateway and the second gateway;

independently determining, based on the health information of the virtual machines, a group of healthy virtual machines comprising two or more of the virtual machines, by each of the first gateway and the second gateway;

receiving, at the first gateway, a first incoming packet that includes a source address and the destination address, wherein the first mapping data structure does not include, at a time of receiving the first incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines;

selecting, at the first gateway, a handling virtual machine from among the group of healthy virtual machines that was independently determined by the first gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the first gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the first gateway;

forwarding, by the first gateway, the first incoming packet to the handling virtual machine over the virtual network;

creating, in the first mapping data structure at the first gateway, a first mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine;

receiving at the second gateway, a second incoming packet that includes the same source address and the same destination address as the first incoming packet, wherein the second mapping data structure does not include, at a time of receiving the second incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines, and the first mapping data structure does include the first mapping entry;

selecting, solely by operation of the second gateway independent of the first gateway and of the first mapping data structure, the same handling virtual machine from among the group of healthy virtual machines that was independently determined by the second gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the second gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the second gateway;

forwarding, by the second gateway, the second incoming packet to the handling virtual machine over the virtual network; and

creating, in the second mapping data structure at the second gateway, a second mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine.

2. The method of claim 1, wherein the virtual network is for Internet Protocol (IP) based communications, wherein each gateway has an IP address on the public network and a different IP address on the virtual network, and wherein operating the gateways comprises using separate IP tunnels to effect delivery of IP packets on the virtual network to the virtual machines.

3. The method of claim 1, wherein forwarding the first incoming packet to the handling virtual machine comprises sending the first incoming packet to the handling virtual machine without changing the destination address, wherein the handling virtual machine includes a network interface that is configured to receive packets that are addressed to the destination address.

4. The method of claim 1, wherein forwarding the first incoming packet to the handling virtual machine comprises performing a network address translation on the first incoming packet where the destination address of the first incoming packet is replaced with a network address of the handling virtual machine, the network address being private to the virtual network.

5. The method of claim 1, wherein selecting, at the first gateway, the handling virtual machine is further based on a geographical proximity of a virtual machine to a geographical location associated with an origin of the first incoming packet.

6. The method of claim 1, wherein selecting, at the first gateway, the handling virtual machine comprising:

generating a flow identifier based on the source address, the destination address, a source port of the first incoming packet, and a destination port of the first incoming packet;

using the flow identifier as input to a hash function to produce a hash value; and

selecting a virtual machine based on the hash value.

7. The method of claim 1, wherein obtaining the health information comprises:

sending packets to check respective virtual machines; and

receiving one or more responses to the sent packets.

8. The method of claim 1, wherein at least one of the gateways is configured to encapsulate the received incoming packets from the public network when sending to the virtual machines, and to de-encapsulate received packets from the virtual machines when sending to the public network.

9. A system comprising:

one or more data processing apparatus; and

one or more memory apparatus in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising;

executing virtual machines that are each configured to communicate with each other over a virtual network and are configured to handle requests associated with at least a destination address on a public network;

operating gateways, including a first gateway and a separate and distinct second gateway, that are each configured to provide connectivity between the virtual network and the public network, that each separately and independently implement a consistent mapping operation to perform load-balancing among the virtual machines, wherein at the first gateway a first mapping data structure includes entries reflecting mappings between source addresses and virtual machines, and wherein at the second gateway a distinct second mapping data structure includes entries reflecting mappings between source addresses and virtual machines;

independently obtaining health information of the virtual machines, by each of the first gateway and the second gateway;

independently determining, based on the health information of the virtual machines, a group of healthy virtual machines comprising two or more of the virtual machines, by each of the first gateway and the second gateway;

receiving, at the first gateway, a first incoming packet that includes a source address and the destination address, wherein the first mapping data structure does not include, at a time of receiving the first incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines;

selecting, at the first gateway, a handling virtual machine from among the group of healthy virtual machines that was independently determined by the first gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the first gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the first gateway;

forwarding, by the first gateway, the first incoming packet to the handling virtual machine over the virtual network;

creating, in the first mapping data structure at the first gateway, a first mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine;

receiving at the second gateway, a second incoming packet that includes the same source address and the same destination address as the first incoming packet, wherein the second mapping data structure does not include, at a time of receiving the second incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines, and the first mapping data structure does include the first mapping entry;

selecting, solely by operation of the second gateway independent of the first gateway and of the first mapping data structure, the same handling virtual machine from among the group of healthy virtual machines that was independently determined by the second gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the second gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the second gateway;

forwarding, by the second gateway, the second incoming packet to the handling virtual machine over the virtual network; and

creating, in the second mapping data structure at the second gateway, a second mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine.

10. The system of claim 9, wherein the virtual network is for Internet Protocol (IP) based communications, wherein each gateway has an IP address on the public network and a different IP address on the virtual network, and wherein operating the gateways comprises using separate IP tunnels to effect delivery of IP packets on the virtual network to the virtual machines.

11. The system of claim 9, wherein forwarding the first incoming packet to the handling virtual machine comprises sending the first incoming packet to the handling virtual machine without changing the destination address, wherein the handling virtual machine includes a network interface that is configured to receive packets that are addressed to the destination address.

12. The system of claim 9, wherein forwarding the first incoming packet to the handling virtual machine comprises performing a network address translation on the first incoming packet where the destination address of the first incoming packet is replaced with a network address of the handling virtual machine, the network address being private to the virtual network.

13. The system of claim 9, wherein selecting, at the first gateway, the handling virtual machine is further based on a geographical proximity of a virtual machine to a geographical location associated with an origin of the first incoming packet.

14. The system of claim 9, wherein selecting, at the first gateway, the handling virtual machine comprising:

generating a flow identifier based on the source address, the destination address, a source port of the first incoming packet, and a destination port of the first incoming packet;

using the flow identifier as input to a hash function to produce a hash value; and

selecting a virtual machine based on the hash value.

15. The system of claim 9, wherein obtaining the health information comprises:

sending packets to check respective virtual machines; and

receiving one or more responses to the sent packets.

16. The system of claim 9, wherein at least one of the gateways is configured to encapsulate the received incoming packets from the public network when sending to the virtual machines, and to de-encapsulate received packets from the virtual machines when sending to the public network.