Synchronizing state among load balancer components

• US 8,755,283 B2
• Filed: 12/17/2010
• Issued: 06/17/2014
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Patel, Parveen, Ivanov, Volodymyr, Zikos, Marios, Petter, Vladimir, Kuznetsov, Vyacheslav, Dion, David Allen
• Primary Examiner(s): Masur, Paul H
• Assistant Examiner(s): PHILLIPS, MICHAEL K
• Application Number:
  US12/972,340
• Publication Number:
  US 20120155266A1
• Time in Patent Office: 1,278 Days
• Field of Search: 718/105, 718/FOR.164, 370/229, 370/235, 370/236, 370/401, 370/230, 455/453, 709/235
• US Class Current: 370/236
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

The present invention extends to methods, systems, and computer program products for synchronizing state among load balancer components. Embodiments of the invention include load balancers using a consistent hashing algorithm to decide how new connections should be load balanced. Use of consistent hashing algorithm permits load balancers to work in a stateless manner in steady state. Load balancers start keeping flow state information (destination address for a given flow) about incoming packets when it is needed, i.e. such as, for example, when a change in destination host configuration is detected. State information is shared across load balancers in a deterministic way, which allows knowing which load balancer is authoritative (e.g., is the owner) for a given flow. Each load balancer can reach the authoritative load balancer to learn about a flow that cannot be determined locally.

Claims

1. At a computer system including a router and a load balancing system, the load balancing system including a load balancer, one or more other load balancers, and a plurality of destination hosts, the router connected to a network and being a point of ingress into the load balancing system, components on the network using a virtual electronic address to communicate with the load balancing system, a method for sharing state between load balancers, the method comprising:

an act of the load balancer receiving a packet from the router, the packet containing source electronic address information identifying a source on the wide area network and destination electronic address information including the virtual electronic address;

an act of the load balancer determining that the packet is for an existing data flow;

an act of the load balancer using an algorithm to generate a data flow identifier for the existing data flow from the packet contents, including the packet headers;

an act of load balancer determining that the load balancer lacks sufficient information to identify the destination host, from among the plurality of destination hosts, that corresponds to the existing data flow, including;

an act of the load balancer determining that the load balancer does not have any cached state mapping the existing data flow to one of the destination hosts in the plurality of destination hosts;

in response to the determination that the load balancer lacks sufficient information to identify the destination host that corresponds to the existing data flow;

an act of the load balancer identifying an owner load balancer that is designated as the owner of the existing data flow, the owner load balancer selected from among the one or more other load balancers; and

an act of the load balancer sending a request for data flow state information to the owner load balancer, wherein the act of the load balancer sending the request for data flow state information to the owner load balancer comprises an act of the load balancer sending the packet to the owner load balancer;

an act of the load balancer receiving state information from the owner load balancer, the state information identifying the destination host that corresponds to the existing data flow; and

an act of the load balancer caching the received state information.

2. The method as recited in claim 1, further comprising in response to the determination that the arrangement of the plurality of destination hosts is in a transition:

an act of the load balancer identifying cached state for one or more other existing data flows, the cached state mapping the one or more other existing data flows to corresponding destination hosts in the plurality of destination hosts;

an act of the load balancer using the current destination host array to identify data flows for which the destination host is different from the current mapping;

for each of these one or more existing more data flows;

an act of the load balancer identifying an owner load balancer, selected from among the one or more other load balancers, that is designated as the owner of the existing data flow; and

an act of sending cached state for the existing data flow to the owner load balancer for the existing data flow.

3. The method as recited in claim 1, further comprising an act of the load balancer receiving cached state for one or more other existing data flows from the one or more other load balancers, the one or more other load balancers having determined the load balancer to be an owner load balancer for the one or more other existing data flows.

4. The method as recited in claim 3, wherein the act of the load balancer receiving cached state for one or more other existing data flows from the one or more other load balancers comprises an act of receiving cached state for at least one existing data flow from another load balancer that the load balancer determined to be the primary owner load balancer for the at least one existing data flow.

5. The method as recited in claim 4, further comprising the load balancer sending the cached state for the at least one existing data flow to at least one other load balancer, the at least one other load balancer designated as a backup owner load balancer for the existing data flow.

6. The method as recited in claim 1, wherein the act of the load balancer receiving a packet from the router comprises an act of the load balancer receiving a packet in accordance with one of:

an Equal Cost Multi-Path (ECMP) algorithm or a Domain Name System (DNS) round robin algorithm.

7. The method as recited in claim 1, further comprising:

an act of the load balancer receiving a second packet for the existing data flow; and

an act of the load balancer referring to cached state information to identify the destination host as corresponding to the existing data flow; and

an act of the load balancer sending the second packet to the destination host.

8. The method as recited in claim 1, wherein the act of the load balancer using an algorithm to generate a data flow identifier for the existing data flow comprise an act of using a hash algorithm to hash a source Internet Protocol address for the source and virtual Internet Protocol address, the data flow identifier representing an index into a current mapping array that maps data flows to corresponding destination hosts.

9. The method as recited in claim 8, wherein the act of the load balancer detecting that the arrangement of the plurality of destination hosts is in a transition comprises an act of determining that the contents of the current mapping array different from the contents of a prior version of the mapping array.

10. The method as recited in claim 8, wherein the act of the load balancer identifying an owner load balancer that is designated as the owner of the existing data flow comprises:

an act of using a second hashing algorithm to hash the source Internet Protocol address and the virtual Internet Protocol address into a second hash value, the second hash value representing a position in a primary owner partition array, the primary owner partition array mapping data flows to corresponding load balancers that maintain cached state for the data flows; and

an act of referring to the position in the primary owner partition array to identify the load balancer that that is mapped as the owner of the existing data flow.

11. The method as recited in claim 1, further comprising an act of the load balancer sending the packet to the destination host that corresponds to the data flow in accordance with the received state information.

12. At a computer system including a router and a load balancing system, the load balancing system including a load balancer, one or more other load balancers, and a plurality of destination hosts, the router connected to a network and being a point of ingress from the wide area network into the load balancing system, components on the network using a virtual electronic address to communicate with the load balancing system, a method for sharing state between load balancers, the method comprising:

an act of a first load balancer receiving a packet directly from a second load balancer, the packet containing source electronic address information identifying a source on the network and destination electronic address information including the virtual electronic address and which is sufficient to identify a data flow associated with the packet, wherein the packet was sent to the first load balancer in response to a determination being made that the second load balancer lacks sufficient information to identify a destination host corresponding to the dataflow, and wherein the packet was routed to the second load balancer by the router;

an act of the first load balancer determining that the received packet is for an existing data flow;

an act of the first load balancer determining that the first load balancer is the owner of the existing data flow;

an act of the first load balancer determining that the first load balancer has cached state for the existing data flow, the cached state mapping the existing data flow to one of the destination hosts in the plurality of destination hosts;

an act of the first load balancer sending the received packet to the destination host mapped to the existing data flow; and

an act of first load balancer sending the cached state to the second load balancer for use in appropriately forwarding subsequent packets in the existing data flow to the one of the destination hosts.

13. The method as recited in claim 12, further comprising an act of the first load balancer receiving cached state for one or more other existing data flows from the one or more other load balancers, the one or more other load balancers having determined the first load balancer to be the primary owner load balancer for the one or more other existing data flows.

14. The method as recited in claim 12, further comprising an act of the first load balancer receiving a batch of cached state for another existing data flow from another load balancer, the other load balancer being the primary owner load balancer for the other existing data flow, the other load balancer having determined that the first load balancer is a backup owner load balancer for the other existing data flow.

15. The method as recited in claim 12, further comprising an act of the first load balancer sending a batch of cached state for the existing data flow to at least one other owner load balancer for caching at the at least one other load balancer, the first load balancer determining that the at least one other load balancers are designated as a backup owner load balancers for the existing data flow.

16. The method as recited in claim 12, further comprising an act of the first load balancer sending state for another existing data flow to another load balancer, the first load balancer having determined that the data flow state is different in the current destination array;

and

an act of the first load balancer determining that the other load balancer is the primary owner of the other existing data flow.

17. A computer system including a router and a load balancing system, the load balancing system including a load balancer, one or more other load balancers, and a plurality of destination hosts, the router connected to a network and being a point of ingress into the load balancing system, components on the network using a virtual electronic address to communicate with the load balancing system, the computing system further comprising one or more storage media having stored computer-executable instructions which, when executed by the at least one processor, implement a method for sharing state between load balancers, the method comprising:

an act of the load balancer receiving a packet from the router, the packet containing source electronic address information identifying a source on the wide area network and destination electronic address information including the virtual electronic address;

an act of the load balancer determining that the packet is for an existing data flow;

an act of the load balancer using an algorithm to generate a data flow identifier for the existing data flow from the packet contents, including the packet headers;

an act of load balancer determining that the load balancer lacks sufficient information to identify the destination host, from among the plurality of destination hosts, that corresponds to the existing data flow, including;

an act of the load balancer determining that the load balancer does not have any cached state mapping the existing data flow to one of the destination hosts in the plurality of destination hosts;

in response to the determination that the load balancer lacks sufficient information to identify the destination host that corresponds to the existing data flow;

an act of the load balancer identifying an owner load balancer that is designated as the owner of the existing data flow, the owner load balancer selected from among the one or more other load balancers; and

an act of the load balancer sending a request for data flow state information to the owner load balancer, wherein the act of the load balancer sending the request for data flow state information to the owner load balancer comprises an act of the load balancer sending the packet to the owner load balancer;

an act of the load balancer receiving state information from the owner load balancer, the state information identifying the destination host that corresponds to the existing data flow; and

an act of the load balancer caching the received state information.

18. The system as recited in claim 17, wherein the method further comprises, in response to the determination that the arrangement of the plurality of destination hosts is in a transition:

an act of the load balancer identifying cached state for one or more other existing data flows, the cached state mapping the one or more other existing data flows to corresponding destination hosts in the plurality of destination hosts;

an act of the load balancer using the current destination host array to identify data flows for which the destination host is different from the current mapping;

for each of these one or more existing more data flows;

an act of the load balancer identifying an owner load balancer, selected from among the one or more other load balancers, that is designated as the owner of the existing data flow; and

an act of sending cached state for the existing data flow to the owner load balancer for the existing data flow.