SYNCHRONIZING STATE AMONG LOAD BALANCER COMPONENTS
First Claim
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;
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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 the load balancer receiving an encapsulated packet from another 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; an act of the load balancer determining that the received packet is for an existing data flow; an act of the load balancer determining that the load balancer is the owner of the existing data flow; an act of the load balancer determining that the 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 load balancer sending the received packet to the destination host mapped to the existing data flow; and an act of load balancer sending the cached state to the other load balancer for use in appropriately forwarding subsequent packets in the existing data flow to the one of the destination hosts. - View Dependent Claims (14, 15, 16, 17)
-
-
18. A load balancing system, comprising:
-
one or more processors; system memory; a router; 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 IDs 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 IDs to primary owner muxes; maintain a backup ownership array mapping flow IDs 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 ID 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 data flow ID 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 ID, including;
when the cached state at the mux contains an indication of the appropriate destination host for flow ID, accessing the cached state at the mux; and
when the cached state at the mux does not contain the appropriate destination host for flow ID,
referring to an owner array to identify an owner mux for the flow ID;
querying the identified owner mux for cached state; and
receiving cached state, indicating the appropriate destination host for the flow ID,from the identified owner mux; and send the packet to identified appropriate destination host. - View Dependent Claims (19, 20)
-
Specification