Synchronizing state among load balancer components

• US 9,438,520 B2
• Filed: 11/18/2014
• Issued: 09/06/2016
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Patel, Parveen, Ivanov, Volodymyr, Zikos, Marios, Petter, Vladimir, Kuznetsov, Vyacheslav, Dion, David Allen
• Primary Examiner(s): Sinkantarakorn, Pao
• Assistant Examiner(s): PHILLIPS, MICHAEL K
• Application Number:
  US14/546,729
• Publication Number:
  US 20150063115A1
• Time in Patent Office: 658 Days
• US Class Current: 1/1
• 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. One or more computer hardware storage device having stored computer-executable instructions which, when executed by at least one computer hardware processor, cause a load balancer to implement a method that includes the following:

monitoring a plurality of destination hosts for changes in an arrangement of the plurality of destination hosts;

maintaining a destination host array that maps flow identifiers to destination hosts;

prior to each array update, copying the destination host array to an old version of the destination host array;

updating the destination host array at periodic intervals;

providing the destination host array and the old version of the destination host array to a plurality of muxes;

monitoring the plurality of muxes for changes;

maintaining a primary ownership array mapping the flow identifiers to primary owner muxes;

maintain a backup ownership array mapping the flow identifiers to backup owner muxes;

providing the primary ownership array and the backup ownership array to the plurality of muxes;

wherein each of the plurality of muxes is configured for;

receiving packets from a router;

formulating a flow identifier for each received packet based on information contained in the packet;

identifying an appropriate destination host, from among the plurality of destination hosts, for the packet; and

sending the packet to identified appropriate destination host.

2. The one or more computer hardware storage device recited in claim 1, wherein the identifying includes:

determining if a data flow associated with the packet is a new data flow;

when the data flow is determined to be an existing data flow, using the flow identifier as an index into the destination host array to identify the appropriate destination host for the packet;

when the contents of the destination host array and the old version of the destination host array do not match, referring to cached state to identify the appropriate destination host for the packet, including;

referring to cached state at the mux to determine if the mux previously cached an indication of the appropriate destination host for flow identifier, including;

when the cached state at the mux contains an indication of the appropriate destination host for flow identifier, accessing the cached state at the mux; and

when the cached state at the mux does not contain the appropriate destination host for flow identifier,

referring to an owner array to identify an owner mux for the flow identifier;

querying the identified owner mux for cached state; and

receiving cached state, indicating the appropriate destination host for the flow identifier, from the identified owner mux.

3. The one or more computer hardware storage device of claim 2, wherein each of the plurality of muxes is further configured to:

receive state for one or more other existing data flows from one or more other muxes, the one or more other muxes having determined the mux to be the primary owner mux for the one or more other existing data flows through reference to the primary ownership array.

4. The one or more computer hardware storage device of claim 3, wherein each of the plurality of muxes is further configured to:

send state for further existing data flow to another mux, the mux having determined, through reference to the primary ownership array, that the other mux is the primary owner of the one or more other existing data flows.

5. The one or more computer hardware storage device of claim 2, wherein each of the plurality of muxes is further configured to:

receive a batch of cached state for other existing data flows from another mux, the other mux balancer being the primary owner mux for the other existing data flows, the other mux having determined that the mux is a backup owner mux for the other existing data flows through reference to the backup ownership array.

6. The one or more computer hardware storage device of claim 2, wherein each of the plurality of muxes is further configured to:

send a batch of cached state for further existing data flows to at least one backup owner mux, identified through reference to the backup ownership array, for caching at the backup owner mux.

7. A load balancing system, comprising:

one or more processors;

system memory;

a router; and

one or more computer storage devices having stored thereon computer-executable instructions representing a load balancing manager, a plurality of muxes, and a plurality of destination hosts, wherein the load balancer is configured to;

monitor the plurality of destination hosts for changes in the arrangement of the plurality of destination hosts;

maintain an destination host array mapping flow identifiers to destination hosts;

prior to each array update, copy the destination host array to an old version of the destination host array;

update the destination host array at periodic intervals;

provide the destination host array and the old version of the destination host array to the plurality of muxes;

monitor the plurality of muxes for changes;

maintain a primary ownership array mapping flow identifiers to primary owner muxes;

maintain a backup ownership array mapping flow identifiers to backup owner muxes;

provide the primary ownership array and the backup ownership array to the plurality of muxes; and

wherein each of the plurality of muxes are configured to;

receive packets from a router;

formulate a flow identifier for each received packet based on information contained in the packet;

identify an appropriate destination host, from among the plurality of destination hosts, for the packet, including;

determining if a data flow associated with the packet is a new data flow;

when the data flow is determined to be an existing data flow, using the flow identifier as an index into the destination host array to identify the appropriate destination host for the packet;

when the contents of the destination host array and the old version of the destination host array do not match, referring to cached state to identify the appropriate destination host for the packet, including;

referring to cached state at the mux to determine if the mux previously cached an indication of the appropriate destination host for flow identifier, including;

 

when the cached state at the mux contains an indication of the appropriate destination host for flow identifier, accessing the cached state at the mux; and

 

when the cached state at the mux does not contain the appropriate destination host for flow identifier,

 

referring to an owner array to identify an owner mux for the flow identifier;

 

querying the identified owner mux for cached state; and

 

receiving cached state, indicating the appropriate destination host for the flow identifier, from the identified owner mux; and

send the packet to identified appropriate destination host.

8. The load balancing system of claim 7, wherein each of the plurality of muxes is further configured to:

receive state for one or more other existing data flows from other muxes, the one or more other muxes having determined the mux to be the primary owner mux for the one or more other existing data flows through reference to the primary ownership array.

9. The load balancing system of claim 8, wherein each of the plurality of muxes is further configured to:

send state for further existing data flow to another mux, the mux having determined, through reference to the primary ownership array, that the other mux is the primary owner of the other existing data flow.

10. The load balancing system of claim 8, wherein each of the plurality of muxes is further configured to:

receive a batch of cached state for other existing data flows from another mux, the other mux balancer being the primary owner mux for the other existing data flows, the other mux having determined that the mux is a backup owner mux for the other existing data flows through reference to the backup ownership array.

11. The load balancing system of claim 10, wherein each of the plurality of muxes is further configured to:

send a batch of cached state for further existing data flows to at least one backup owner mux, identified through reference to the backup ownership array, for caching at the backup owner mux.

12. A computer-implemented method that includes the following being implemented by one or more computing systems:

monitoring a plurality of destination hosts for changes in an arrangement of the plurality of destination hosts;

maintaining a destination host array that maps flow identifiers to destination hosts;

prior to each array update, copying the destination host array to an old version of the destination host array;

updating the destination host array at periodic intervals;

providing the destination host array and the old version of the destination host array to a plurality of muxes;

monitoring the plurality of muxes for changes;

maintaining a primary ownership array mapping the flow identifiers to primary owner muxes;

maintain a backup ownership array mapping the flow identifiers to backup owner muxes; and

providing the primary ownership array and the backup ownership array to the plurality of muxes.

13. The method of claim 12, wherein each of the plurality of muxes is configured for:

receiving packets from a router;

formulating a flow identifier for each received packet based on information contained in the packet;

identifying an appropriate destination host, from among the plurality of destination hosts, for the packet; and

sending the packet to identified appropriate destination host.

14. The method of claim 13, wherein the identifying includes:

determining if the data flow is a new data flow or an existing data flow;

when the data flow is determined to be an existing data flow, using the flow identifier as an index into the destination host array to identify the appropriate destination host for the packet;

when the contents of the destination host array and the old version of the destination host array do not match, referring to cached state to identify the appropriate destination host for the packet, including;

referring to cached state at the mux to determine if the mux previously cached an indication of the appropriate destination host for flow identifier, including;

when the cached state at the mux contains an indication of the appropriate destination host for flow identifier, accessing the cached state at the mux.

15. The method of claim 13, wherein the identifying includes:

determining if the data flow is a new data flow or an existing data flow;

when the data flow is determined to be an existing data flow, using the flow identifier as an index into the destination host array to identify the appropriate destination host for the packet;

when the contents of the destination host array and the old version of the destination host array do not match, referring to cached state to identify the appropriate destination host for the packet, including;

referring to cached state at the mux to determine if the mux previously cached an indication of the appropriate destination host for flow identifier, including;

when the cached state at the mux does not contain the appropriate destination host for flow identifier,

referring to an owner array to identify an owner mux for the flow identifier;

querying the identified owner mux for cached state; and

receiving cached state, indicating the appropriate destination host for the flow identifier, from the identified owner mux.

16. The method of claim 12, wherein each of the plurality of muxes is further configured to:

receive state for one or more other existing data flows from one or more other muxes, the one or more other muxes having determined the mux to be the primary owner mux for the one or more other existing data flows through reference to the primary ownership array.

17. The method of claim 16, wherein each of the plurality of muxes is further configured to:

send state for further existing data flow to another mux, the mux having determined, through reference to the primary owner array, that the other mux is the primary ownership of the one or more other existing data flows.

18. The method of claim 12, wherein each of the plurality of muxes is further configured to:

receive a batch of cached state for other existing data flows from another mux, the other mux balancer being the primary owner mux for the other existing data flows, the other mux having determined that the mux is a backup owner mux for the other existing data flows through reference to the backup ownership array.

19. The method of claim 12, wherein each of the plurality of muxes is further configured to:

send a batch of cached state for further existing data flows to at least one backup owner mux, identified through reference to the backup ownership array, for caching at the backup owner mux.

20. The method of claim 12, wherein monitoring a plurality of destination hosts for changes includes monitoring for a failure.