Adaptive endpoint selection

• US 10,432,711 B1
• Filed: 09/15/2014
• Issued: 10/01/2019
• Est. Priority Date: 09/15/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Greenwood, Christopher Magee, Thompson, James Michael, Brenneman, Kristina Kraemer
• Primary Examiner(s): Parry, Chris
• Assistant Examiner(s): Clayborn, Antony K
• Application Number:
  US14/486,894
• Time in Patent Office: 1,842 Days
• Field of Search: 709203
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A method for selecting a service endpoint from a plurality of service endpoints in a distributed system of a service provider may include storing processing data for each of the plurality of endpoints. A success rate may be calculated for each of the plurality of service endpoints and based on a number of processed requests from a plurality of received requests. An average latency may be calculated based on latency associated with each of the processed requests. A latency score may be calculated based on a minimum average latency and the average latency. A raw score may be calculated based on the latency score and the success rate. A selection weight may be calculated based on the raw score and a balancing parameter. One of the plurality of endpoints may be selected based on the selection weight.

Claims

1. A method for selecting, for a client device, a service endpoint from a plurality of service endpoints in a distributed system of a service provider, the method comprising:

storing processing data for each of the plurality of service endpoints,

for at least a first service request from the client device, where a current history length is less than or equal to a threshold length, applying uniform random selection to select a first one of the plurality of service endpoints;

for at least a second service request from the client device, where the current history length for all of the plurality of service endpoints exceeds the threshold length;

calculating for each of the plurality of service endpoints and using the processing data;

a success rate based on a number of successfully processed requests from a plurality of received requests, wherein the success rate indicates a rate of success for the plurality of received requests;

an average latency based on latency associated with each of the successfully processed requests;

a latency score based on a minimum average latency and the average latency, wherein the minimum average latency is selected from the average latency for each of the plurality of service endpoints;

a raw score based on the latency score and the success rate; and

a selection weight based on the raw score and a balancing parameter, wherein the balancing parameter determines an extent to which the selection weight deviates, based on the processing data, from uniform weights across the plurality of service endpoints; and

selecting a second one of the plurality of service endpoints based on the selection weight; and

directing the first and second service requests to the first and second selected service endpoints respectively.

2. The method according to claim 1, wherein the processing data comprises historic latency data and historic successful request data.

3. The method according to claim 1, wherein calculating the selection weight is performed using a Boltzmann distribution, wherein the Boltzman constant k_B is replaced by an integer k.

4. The method according to claim 3, wherein the Boltzmann distribution is expressed as

5. The method of claim 1, wherein the plurality of service endpoints are servers associated with a Web service, a database service, or a storage service, and wherein the success rate of a given service endpoint indicates the rate of success for Web service requests, database service requests, or storage service requests received and processed at the given service endpoint.

6. The method according to claim 1, wherein:

a relatively lower value of the balancing parameter emphasizes exploitation of the processing data; and

a relatively higher value of the balancing parameter emphasizes exploration of uniform use of the plurality of service endpoints.

7. The method according to claim 1, comprising:

selecting the second one of the plurality of service endpoints based on a random weighted distribution scheme using the selection weight for each of the plurality of service endpoints.

8. A computer-readable storage medium having instructions thereon for executing a method for selecting a service endpoint from a plurality of service endpoints in a distributed system of a compute service provider, the method comprising:

using an endpoint selection service of the compute service provider;

in a first case with an endpoint historic data length parameter of a given endpoint greater than a counter of a current historic length of the given endpoint, applying uniform random endpoint selection to select a first service endpoint; and

in a second case with the endpoint historic data length parameter of the given endpoint less than the counter of the current historic length of the given endpoint;

storing processing data for each of the plurality of service endpoints, wherein the processing data for each service endpoint indicates a success rate and an average latency associated with successfully processed requests from a plurality of received requests, wherein the success rate indicates a rate of success for the plurality of received requests;

in response to receiving a service request, calculating a selection weight for each of the plurality of service endpoints, the selection weight based on the success rate, the average latency and a balancing parameter, the balancing parameter indicating an extent to which the selection weight deviates, based on the processing data, from uniform weights across the plurality of service endpoints; and

selecting a second one of the plurality of service endpoints to receive the service request based on the calculated selection weight for each of the plurality of service endpoints.

9. The computer-readable storage medium according to claim 8, wherein the processing data for each service endpoint comprises:

an endpoint identifier of the service endpoint;

for each of the plurality of received requests, a Boolean value indicating whether the received request was successfully processed; and

for each of the plurality of received requests that was successfully processed, a latency value, wherein the latency value indicates time duration from receiving the request at the service endpoint, processing the request, and communicating a reply from the service endpoint indicating the request was successfully processed.

10. The computer-readable storage medium according to claim 8, wherein the method further comprises:

resetting a historic data profile for each of the plurality of service endpoints, the historic data profile for storing the processing data.

11. The computer-readable storage medium according to claim 8, wherein the method further comprises:

in response to receiving the service request, determining for each of the plurality of service endpoints, whether the processing data includes success rate data and average latency data associated with at least a minimum number of received requests.

12. The computer-readable storage medium according to claim 11, wherein the method further comprises, in a third case for which the processing data includes success rate data and average latency data associated with a number of received requests that is lower than the minimum number:

selecting one of the plurality of service endpoints to receive the service request based on a uniform random selection from the plurality of service endpoints.

13. The computer-readable storage medium according to claim 11, wherein the method further comprises, in a fourth case for which the processing data includes success rate data and average latency data associated with a number of received requests that is higher than or equal to the minimum number:

selecting one of the plurality of service endpoints to receive the service request based on the calculated selection weight for each of the plurality of service endpoints.

14. The computer-readable storage medium according to claim 8, wherein the method further comprises:

for each service endpoint of the plurality of service endpoints, acquiring the balancing parameter from a policy document associated with the service endpoint.

15. The computer-readable storage medium according to claim 8, wherein the method further comprises:

updating success data within the processing data based on whether the received service request was processed successfully.

16. The computer-readable storage medium according to claim 15, wherein the method further comprises:

if the received service request was processed successfully, updating latency data within the processing data based on latency associated with processing the received service request.

17. A system for selecting a service endpoint from a plurality of service endpoints in a distributed system of a compute service provider, the system comprising:

a plurality of host server computers coupled together through a network to form the service provider, at least a portion of the host server computers for executing a plurality of virtual machine instances associated with a customer account;

the plurality of service endpoints operable to execute at least one of a plurality of service requests associated with a service of the service provider, the service requests originating from at least one of the host server computers; and

an endpoint selection service communicatively coupled to the plurality of service endpoints, the endpoint selection service operable to;

store processing data for each of the plurality of service endpoints, wherein the processing data for each service endpoint indicates success rate and average latency associated with successfully processing at least a portion of the plurality of received service requests, wherein the success rate indicates a rate of success for the plurality of received service requests and the average latency is an average of a latency at the each service endpoint for processing each successfully processed request, the latency extending from receipt of the corresponding request from a client device to communicating a reply to the client device indicating that the corresponding request was successfully processed;

acquire a balancing parameter for each of the plurality of service endpoints;

in response to receiving at least one of the service requests, calculate a selection weight for each of the plurality of service endpoints, the selection weight based on the success rate, the average latency and the balancing parameter, wherein the balancing parameter indicates an extent to which the selection weight deviates, based on the processing data, from uniform weights across the plurality of service endpoints, and thereby determines an impact of the success rate on the selection weight; and

select one of the plurality of service endpoints to receive the at least one of the service requests according to;

a uniform random selection in a case where a historic data length parameter is greater than a counter of a current historic length; and

a weighted distribution based on the calculated selection weight for each of the plurality of service endpoints, in another case where the historic data length parameter is less than the counter of the current historic length.

18. The system according to claim 17, wherein calculating the selection weight is performed using a Boltzmann distribution.

19. The system according to claim 18, wherein the endpoint selection service is further operable to:

select the one of the plurality of service endpoints based on a random weighted distribution scheme using the selection weight for each of the plurality of service endpoints.

20. The system according to claim 17, wherein the endpoint selection service is further operable to:

store the processing data in a historic data profile for each of the plurality of service endpoints, the historic data profile comprising an endpoint identifier and a Boolean value indicating whether at least a portion of the received service requests were successfully processed.