Synchronizing state among load balancer components

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.

What is claimed is: 
     
         1 . One or more computer hardware storage device having stored thereon computer-executable instructions which, when executed by at least one computer hardware processor, implement a method for sharing state between load balancers in a computer environment that includes 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, wherein the method includes:
 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; 
   subsequent to determining 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; 
 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 one or more computer hardware storage device as recited in  claim 1 , the method 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 one or more computer hardware storage device as recited in  claim 1 , the method 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 one or more computer hardware storage device 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 one or more computer hardware storage device as recited in  claim 4 , the method 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 one or more computer hardware storage device 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 one or more computer hardware storage device as recited in  claim 1 , the method 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 the 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 one or more computer hardware storage device 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 one or more computer hardware storage device 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 one or more computer hardware storage device 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 one or more computer hardware storage device as recited in  claim 1 , wherein the method further includes an act of the load balancer sending a request for the data flow state information to the owner load balancer. 
     
     
         12 . The one or more computer hardware storage device as recited in  claim 1 , wherein the method further includes the load balancer sending the packet to the owner load balancer. 
     
     
         13 . The one or more computer hardware storage device as recited in  claim 1 , the method 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. 
     
     
         14 . 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;   updating the destination host array at periodic intervals;   prior to each array update, copying the destination host array to an old version of the destination host array;   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 the 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.   
     
     
         15 . The one or more computer hardware storage device recited in  claim 14 , wherein the identifying includes:
 determining if the data flow 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 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. 
 
 
   
     
     
         16 . The one or more computer hardware storage device of  claim 15 , 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 owner array; and   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 owner of the other existing data flow.   
     
     
         17 . The one or more computer hardware storage device of  claim 15 , 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 owner array; and   send a batch of cached state for further existing data flows to at least one backup owner mux, identified through reference to the backup owner array, for caching at the backup owner mux.   
     
     
         18 . 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; 
 update the destination host array at periodic intervals; 
 prior to each array update, copy the destination host array to an old version of the destination host array; 
 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 the 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 the data flow 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 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. 
 
 
   
     
     
         19 . The load balancing system of  claim 18 , 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 owner array; and   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 owner of the other existing data flow.   
     
     
         20 . The load balancing system of  claim 19 , 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 owner array; and   send a batch of cached state for further existing data flows to at least one backup owner mux, identified through reference to the backup owner array, for caching at the backup owner mux.