Distributed load balancer

• US 10,069,903 B2
• Filed: 04/16/2013
• Issued: 09/04/2018
• Est. Priority Date: 04/16/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, III, James Christopher, Laurence, Douglas Stewart, Srinivasan, Venkatraghavan, Vaidya, Akshay Suhas, Zhang, Fan
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): Krishnan, Raji
• Application Number:
  US13/864,167
• Publication Number:
  US 20140310418A1
• Time in Patent Office: 1,967 Days
• Field of Search: 709223, 709226, 709232, 709238, 718105, 370259
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A distributed load balancer in which a router receives packets from at least one client and routes packet flows to multiple load balancer (LB) nodes according to a per-flow hashed multipath routing technique. For a given packet flow, the LB nodes randomly select a server node as a target for the packet flow from among multiple server nodes and send a connection request to the server node. A load balancer module on the server node makes the decision on whether to accept or reject the connection based on one or more metrics indicating a respective server'"'"'s current load. If the module accepts the connection request, a connection is established between the server and the client. Otherwise, the load balancer nodes may select another server node and try again. The connections established between clients and servers pass through the load balancer nodes, but are not terminated at the load balancer nodes.

Claims

1. A distributed load balancer system, comprising:

a plurality of load balancer nodes in a provider network; and

a plurality of server nodes in the provider network, each comprising a server and a load balancer module;

wherein the plurality of load balancer nodes is configured to distribute packet flows from one or more clients among the plurality of server nodes, wherein, to distribute the packet flows among the plurality of server nodes, the plurality of load balancer nodes is configured to;

select server nodes from among the plurality of server nodes to receive connection requests for the packet flows from the one or more clients; and

send the connection requests to the selected server nodes;

wherein the load balancer module on each server node is configured to;

receive a connection request of a client for a packet flow from one of the plurality of load balancer nodes;

determine if a data communications protocol connection for the packet flow is to be accepted by the server on the server node;

if the server cannot accept the data communications protocol connection, reject the connection request; and

if the server can accept the data communications protocol connection, cooperate with the plurality of load balancer nodes to establish the data communications protocol connection for the packet flow between the client and the server;

wherein, after establishing the data communications protocol connection for the packet flow between the client and the server, the load balancer module on each server node is further configured to;

receive incoming data communications protocol packets for the data communications protocol connection from one of the load balancer nodes;

send the received incoming data communications protocol packets to the server on the server node;

select one of the plurality of load balancer nodes to act as an egress server for the data communications protocol connection, wherein the selection is based at least in part on an identifier for the packet flow between the client and the server;

intercept outgoing data communications protocol packets for the data communications protocol connection; and

send the intercepted outgoing data communications protocol packets to the selected egress server for delivery to the client.

2. The distributed load balancer system as recited in claim 1, further comprising a router configured to distribute the packet flows from the one or more clients among the plurality of load balancer nodes according to a hashed multipath routing technique.

3. The distributed load balancer system as recited in claim 1, wherein the plurality of load balancer nodes is further configured to select the server nodes from among the plurality of server nodes to receive the connection requests according to a random selection technique.

4. The distributed load balancer system as recited in claim 1, wherein the plurality of load balancer nodes is further configured to select another server node from among the plurality of server nodes to receive a rejected connection requests and send the connection request to the other server node.

5. The distributed load balancer system as recited in claim 1, wherein each packet flow is a Transmission Control Protocol (TCP) packet flow, and wherein each data communications protocol connection established between a client and a server is a TCP connection.

6. The distributed load balancer system as recited in claim 1, wherein each data communications protocol connection established between a client and a server is a direct data communications protocol connection that originates at the client, passes through one or more of the plurality of load balancer nodes, and is terminated by the server, wherein the one or more load balancer nodes do not act as proxies for the data communications protocol connection and do not terminate the data communications protocol connection.

7. The distributed load balancer system as recited in claim 1, wherein, to determine if the data communications protocol connection is to be accepted by the server on the server node, the load balancer module is configured to analyze one or more current resource usage metrics of the server on the server node to determine if the server can accept the data communications protocol connection, wherein the one or more current resource usage metrics include one or more of CPU utilization, bandwidth consumption, server latency, and number of established data communications protocol connections.

8. A method, comprising:

performing, by one or more of a plurality of load balancer nodes;

receiving a data communications protocol packet in a packet flow for a client; and

sending a connection request for the packet flow to a server node selected from among a plurality of server nodes;

performing, by the selected server node;

determining if a server on the server node can or cannot accept a data communications protocol connection for the packet flow;

rejecting the connection request upon determining that the server cannot accept the data communications protocol connection; and

accepting the connection request upon determining that the server can accept the data communications protocol connection, wherein said accepting the connection request comprises;

cooperating with the one or more load balancer nodes to establish the data communications protocol connection between the client and the server for the packet flow; and

selecting one of the plurality of load balancer nodes to act as an egress server for the data communications protocol connection based at least in part on an identifier for the packet flow, wherein outgoing data communications protocol packets on the data communications protocol connection are sent to the client via the selected egress server.

9. The method as recited in claim 8, wherein said determining, said rejecting, and said accepting are performed by a load balancer module on the selected server node, the method further comprising performing, by the load balancer module after accepting the connection request:

receiving incoming data communications protocol packets for the data communications protocol connection from one of the load balancer nodes and sending the incoming data communications protocol packets to the server on the server node; and

intercepting the outgoing data communications protocol packets for the data communications protocol connection and sending the outgoing data communications protocol packets to the selected egress server for delivery to the client.

10. The method as recited in claim 9, wherein the packet flow is a Transmission Control Protocol (TCP) packet flow, and wherein the data communications protocol connection established between the client and the server is a TCP connection.

11. The method as recited in claim 9, wherein the established data communications protocol connection is a direct data communications protocol connection that originates at the client, passes through one or more of the plurality of load balancer nodes, and is terminated by the server, wherein the one or more load balancer nodes do not act as proxies for the data communications protocol connection and do not terminate the data communications protocol connection.

12. The method as recited in claim 8, wherein the packet is received from a router that distributes packet flows from one or more clients among the plurality of load balancer nodes according to a hashed multipath routing technique.

13. The method as recited in claim 8, further comprising the one or more load balancer nodes selecting the server node from among the plurality of server nodes according to a random selection technique.

14. The method as recited in claim 8, further comprising, if the selected server node rejects the connection request, the one or more load balancer nodes sending the connection request to another server node selected from among the plurality of server nodes.

15. The method as recited in claim 8, wherein said determining if a server on the server node can or cannot accept the data communications protocol connection comprises analyzing one or more current resource usage metrics of the server to determine if the server can accept the data communications protocol connection.

16. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement a load balancer module on each of a plurality of server nodes, wherein each load balancer module is configured to:

receive, from one of a plurality of load balancer nodes, a connection request for a packet flow from a client;

determine if a server on the server node can or cannot accept a data communications protocol connection for the packet flow;

reject the connection request upon determining that the server cannot accept the data communications protocol connection; and

upon determining that the server can accept the data communications protocol connection;

communicate with the load balancer node and with the server to establish the data communications protocol connection between the client and the server for the packet flow; and

select one of the plurality of load balancer nodes to act as an egress server for the data communications protocol connection based at least in part on an identifier for the packet flow, wherein outgoing data communications protocol packets on the data communications protocol connection are sent to the client via the selected egress server.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the program instructions are further computer-executable to implement the load balancer node randomly selecting the server node from among the plurality of server nodes to receive the connection request.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein, to reject the connection request, the load balancer module is configured to decrement a time to live (TTL) counter in the connection request and return the connection request to the load balancer node, wherein the program instructions are further computer-executable to implement the load balancer node:

checking the TTL counter in the returned connection request;

if the TTL counter is above a threshold, selecting another server node from among the plurality of server nodes to receive the connection request; and

if the TTL counter is at or below the threshold, dropping the connection request.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein, to determine if a server on the server node can or cannot accept the data communications protocol connection, the load balancer module is configured to analyze one or more current resource usage metrics of the server to determine if the server can accept the data communications protocol connection.

20. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the one or more current resource usage metrics include one or more of CPU utilization, bandwidth consumption, server latency, and number of established data communications protocol connections.