Load balancing and content preservation

• US 9,154,367 B1
• Filed: 12/27/2011
• Issued: 10/06/2015
• Est. Priority Date: 12/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kontothanassis, Leonidas, Presotto, David, Jain, Ankur, Schultz, Paul
• Primary Examiner(s): Wang, Liangche A
• Assistant Examiner(s): AGUIAR, JOHNNY B
• Application Number:
  US13/338,024
• Time in Patent Office: 1,379 Days
• Field of Search: 709/203, 709/217, 709/219, 709/223, 709/224, 709/225, 709/226, 709/238, 709/245, 370/216
• US Class Current: 1/1
• 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 11/2023 Failover techniques
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for receiving a plurality of requests from a plurality of client devices sent to a public internet protocol address; routing the requests to one or more internal Internet protocol addresses, where the one or more internal Internet protocol addresses correspond to one or more compute nodes, and where the one or more compute nodes process the routed requests; determining a particular compute node is offline, where the particular compute node is assigned one or more internal Internet protocol addresses; in response to the determination that the particular node is offline, reassigning the one or more internal Internet protocol addresses corresponding to the particular compute node to one or more different compute nodes, where requests communicated to the reassigned internal Internet protocol addresses are communicated to the one or more different compute nodes for processing.

Claims

1. A computer-implemented method performed by one or more computing devices, the method comprising:

receiving a plurality of requests from a plurality of client devices sent to a public internet protocol address;

for each received request, processing the request to determine an internal Internet protocol address to associate with the request;

routing each request to the internal Internet protocol address of a plurality of internal Internet protocol addresses associated with the request, wherein each internal Internet Protocol address is assigned to a respective compute node of a plurality of compute nodes, and wherein the one or more compute nodes process the routed requests;

determining a particular compute node is offline, wherein the particular compute node is assigned one or more internal Internet protocol addresses; and

in response to the determination that the particular compute node is offline, reassigning the one or more internal Internet protocol addresses corresponding to the particular compute node to one or more different compute nodes, wherein requests communicated to the reassigned internal Internet protocol addresses are communicated to the one or more different compute nodes for processing,

wherein each internal Internet protocol address is reassigned according to a failover order for the internal Internet protocol address with respect to each of the other compute nodes of the plurality of compute nodes, and wherein the failover order for each internal Internet protocol address is based on historical computing workload data for each internal Internet protocol address of the particular compute node, a number of requests sent to each internal Internet Protocol address, a complexity of the requests sent to each internal Internet Protocol address, and historic computing workload data of each of the other compute nodes.

2. The method of claim 1, wherein routing the requests to one or more internal Internet protocol addresses comprises using a hash table to hash an incoming request to a particular internal Internet protocol address.

3. The method of claim 1, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes based in part on a Media Access Control address corresponding to the internal Internet protocol address, wherein the Media Access Control address is identified by performing a lookup operation in an Address Resolution Protocol table.

4. The method of claim 1, wherein routing the requests to one or more internal Internet protocol addresses, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes comprises communicating the request to Media Access Control addresses corresponding to the one or more internal Internet protocol addresses.

5. The method of claim 1, wherein a public Internet protocol address is associated with one or more internal Internet protocol addresses using equal-cost multi-path routing techniques.

6. The method of claim 1, wherein determining a particular compute node in a plurality of compute nodes is offline comprises:

monitoring a broadcast from the particular compute node, wherein the broadcast is communicated at a first specified time interval; and

determining a disruption in the broadcast from the particular compute node in a case where the broadcast is not received within a second specified time interval.

7. The method of claim 1, wherein reassigning the internal Internet protocol addresses associated with the particular compute node to one or more different compute nodes comprises updating, in an Address Resolution Protocol table, one or more Media Access Control addresses corresponding to the internal Internet protocol addresses, wherein the one or more Media Access Control addresses are associated with the one or more different compute nodes.

8. The method of claim 1, wherein reassigning the internal Internet protocol addresses further comprises:

determining the failover order for each internal IP address with respect to a plurality of compute nodes; and

assigning one or more internal internet protocol addresses to a next compute node in the failover order that is online.

9. A system comprising:

one or more first computing devices configured to;

receive a plurality of requests from a plurality of client devices sent to a public internet protocol address;

for each received request, processing the request to determine an internal Internet protocol address to associate with the request;

route each request to the internal Internet protocol address of a plurality of internal Internet protocol addresses associated with the request, wherein each internal Internet Protocol address is assigned to a respective compute node of a plurality of compute nodes, and wherein the one or more compute nodes process the routed requests;

determine a particular compute node is offline, wherein the particular compute node is assigned one or more internal Internet protocol addresses; and

in response to the determination that the particular compute node is offline, reassigning the one or more internal Internet protocol addresses corresponding to the particular compute node to one or more different compute nodes, wherein requests communicated to the reassigned internal Internet protocol addresses are communicated to the one or more different compute nodes for processing,

wherein each internal Internet protocol address is reassigned according to a failover order for the internal Internet protocol address with respect to each of the other compute nodes of the plurality of compute nodes, and wherein the failover order for each internal Internet protocol address is based on historical computing workload data for each internal Internet protocol address of the particular compute node, a number of requests sent to each internal Internet Protocol address, a complexity of the requests sent to each internal Internet Protocol address, and historic computing workload data of each of the other compute nodes.

10. The system of claim 9, wherein routing the requests to one or more internal Internet protocol addresses comprises using a hash table to hash an incoming request to a particular internal Internet protocol address.

11. The system of claim 9, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes based in part on a Media Access Control address corresponding to the internal Internet protocol address, wherein the Media Access Control address is identified by performing a lookup operation in an Address Resolution Protocol table.

12. The system of claim 9, wherein routing the requests to one or more internal Internet protocol addresses, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes comprises communicating the request to Media Access Control addresses corresponding to the one or more internal Internet protocol addresses.

13. The system of claim 9, wherein a public Internet protocol address is associated with one or more internal Internet protocol addresses using equal-cost multi-path routing techniques.

14. The system of claim 9, wherein determining a particular compute node in a plurality of compute nodes is offline comprises:

monitoring a broadcast from the particular compute node, wherein the broadcast is communicated at a first specified time interval; and

determining a disruption in the broadcast from the particular compute node in a case where the broadcast is not received within a second specified time interval.

15. The system of claim 9, wherein reassigning the internal Internet protocol addresses associated with the particular compute node to one or more different compute nodes comprises updating, in an Address Resolution Protocol table, one or more Media Access Control addresses corresponding to the internal Internet protocol addresses, wherein the one or more Media Access Control addresses are associated with the one or more different compute nodes.

16. The system of claim 9, wherein reassigning the internal Internet protocol addresses further comprises:

determining the failover order for each internal IP address with respect to a plurality of compute nodes; and

assigning one or more internal internet protocol addresses to a next compute node in the failover order that is online.

17. A storage medium have instructions stored thereon that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

receiving a plurality of requests from a plurality of client devices sent to a public internet protocol address;

for each received request, processing the request to determine an internal Internet protocol address to associate with the request;

routing each request to the internal Internet protocol address of a plurality of internal Internet protocol addresses associated with the request, wherein each internal Internet Protocol address is assigned to a respective compute node of a plurality of compute nodes, and wherein the one or more compute nodes process the routed requests;

determining a particular compute node is offline, wherein the particular compute node is assigned one or more internal Internet protocol addresses; and

in response to the determination that the particular compute node is offline, reassigning the one or more internal Internet protocol addresses corresponding to the particular compute node to one or more different compute nodes, wherein requests communicated to the reassigned internal Internet protocol addresses are communicated to the one or more different compute nodes for processing,

wherein each internal Internet protocol address is reassigned according to a failover order for the internal Internet protocol address with respect to each of the other compute nodes of the plurality of compute nodes, and wherein the failover order for each internal Internet protocol address is based on historical computing workload data for each internal Internet protocol address of the particular compute node, a number of requests sent to each internal Internet Protocol address, a complexity of the requests sent to each internal Internet Protocol address, and historic computing workload data of each of the other compute nodes.

18. The storage medium of claim 17, wherein routing the requests to one or more internal Internet protocol addresses comprises using a hash table to hash an incoming request to a particular internal Internet protocol address.

19. The storage medium of claim 17, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes based in part on a Media Access Control address corresponding to the internal Internet protocol address, wherein the Media Access Control address is identified by performing a lookup operation in an Address Resolution Protocol table.

20. The storage medium of claim 17, wherein routing the requests to one or more internal Internet protocol addresses, wherein the one or more internal Internet protocol addresses correspond to one or more compute nodes comprises communicating the request to Media Access Control addresses corresponding to the one or more internal Internet protocol addresses.

21. The storage medium of claim 17, wherein a public Internet protocol address is associated with one or more internal Internet protocol addresses using equal-cost multi-path routing techniques.

22. The storage medium of claim 17, wherein determining a particular compute node in a plurality of compute nodes is offline comprises:

monitoring a broadcast from the particular compute node, wherein the broadcast is communicated at a first specified time interval; and

determining a disruption in the broadcast from the particular compute node in a case where the broadcast is not received within a second specified time interval.

23. The storage medium of claim 17, wherein reassigning the internal Internet protocol addresses associated with the particular compute node to one or more different compute nodes comprises updating, in an Address Resolution Protocol table, one or more Media Access Control addresses corresponding to the internal Internet protocol addresses, wherein the one or more Media Access Control addresses are associated with the one or more different compute nodes.

24. The storage medium of claim 17, wherein reassigning the internal Internet protocol addresses further comprises:

determining the failover order for each internal IP address with respect to a plurality of compute nodes; and

assigning one or more internal internet protocol addresses to a next compute node in the failover order that is online.