Endpoint call backoff in a computing service environment

• US 10,296,411 B1
• Filed: 03/31/2016
• Issued: 05/21/2019
• Est. Priority Date: 03/31/2016
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Diggins, Michael F., Howard, Craig Wesley
• Primary Examiner(s): Schell, Joseph O
• Application Number:
  US15/087,921
• Time in Patent Office: 1,146 Days
• CPC Class Codes: G06F 11/0706 the processing taking place on a specific hardware platform or in a specific software environment
• CPC Class Codes: G06F 11/0754 by exceeding limits
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• 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/101 based on network conditions

Abstract

A technology is provided for call failure backoff in a computing service environment. An allowable call failure rate is defined for application programming interface (API) calls sent to one or more endpoints. Each endpoint may use a token bucket containing a plurality of tokens, wherein a single token is defined as being equal to one API call failure. A number of tokens in the token bucket are determined prior to executing an API call to the one or more endpoints. A health status of the one or more endpoints is identified according to the number of tokens in the token bucket. The API calls to the one or more endpoints having the determined number of tokens in the token bucket that are equal to zero or may be delayed for a predetermined backoff time period.

Claims

1. A method for providing an endpoint backoff operation in a computing service environment, the method comprises:

under control of at least one processor and memory configured with executable instructions that;

define an allowable call failure rate for application programming interface (API) calls sent to one or more endpoints, and the allowable call failure rate is defined using a token bucket for storing a plurality of tokens, wherein removal of a single token from the token bucket is defined as being equal to one API call failure, and one or more additional tokens are added to the token bucket when a predetermined number of successful calls are sent to and executed by the endpoint;

determine a number of tokens in the token bucket prior to executing an API call to the one or more endpoints;

identify a health status of the one or more endpoints according to the number of tokens in the token bucket;

determine that the one or more endpoints, having a number of tokens in the token bucket that is equal to zero or less than a defined number of tokens, are unhealthy; and

delay the API calls to the one or more endpoints determined to be unhealthy.

2. The method of claim 1, wherein the executable instructions further delay the API calls to the one or more endpoints for a second predetermined backoff time period, wherein the second predetermined backoff time period is greater than a first predetermined backoff time period.

3. The method of claim 1, wherein the executable instructions further define the allowable call failure rate as one API call failure per predetermined unit of time for sending API calls to the one or more endpoints or receiving API calls from the endpoints.

4. The method of claim 1, wherein the executable instructions further define the allowable call failure rate as a percentage of calls per total number of calls in a predetermined time period for sending the API calls with the one or more endpoints or receiving the API calls to the one or more endpoints.

5. The method of claim 1, wherein the executable instructions further:

poll a total number of tokens in the token bucket at predetermined token tracking time periods; and

remove a token from the token bucket upon each occurrence of an API call failure to the one or more endpoints.

6. The method of claim 1, wherein the executable instructions further:

determine a least recently used endpoint from the one or more endpoints;

define the least recently used endpoint as operating in a healthy state; and

remove the least recently used endpoint from the one or more endpoints.

7. A method for providing call failure backoff in a computing service environment, the method comprises executable instructions that:

identify an endpoint configured to execute calls received as an application programming interface (API) call;

define an allowable call failure rate for calls executed to an endpoint;

determine a number of tokens in a token bucket for the endpoint prior to sending a call to the endpoint for execution, wherein a token represents a call failure, and one or more additional tokens are added to the token bucket when a predetermined number of successful calls are sent to and executed by the endpoint; and

delay calls to the endpoint upon determining the number of tokens in the token bucket is less than a defined number of tokens.

8. The method of claim 7, wherein the executable instructions for exponential backoff operations further:

delay the calls to the endpoint during a first predetermined backoff time period upon determining the number of tokens in the token bucket is less than the defined number of tokens;

send an unsuccessful call to the endpoint after the first predetermined backoff time period;

enter into a second predetermined backoff time period; and

delay the calls to the endpoint during the second predetermined backoff time period upon determining the number of tokens in the token bucket is less than the defined number of tokens, wherein the second predetermined backoff time period is double the first predetermined backoff time period.

9. The method of claim 7, wherein the executable instructions further define an allowable failure rate as one call failure per second for calls sent to the endpoint.

10. The method of claim 7, wherein the executable instructions further define an allowable failure rate as a percentage of total calls per predetermined time period for calls sent to the endpoint.

11. The method of claim 7, wherein the executable instructions further:

assign a token in the token bucket to each API call failure;

define a selected token as equal to one call failure to the endpoint;

decrement a total token count number in the token bucket upon a call failure;

define an unhealthy state of the endpoint as having a number of tokens in the token bucket below a predetermined number of tokens; and

define a healthy state of the endpoint as having a number of tokens in the token bucket above or equal to a predetermined number of tokens.

12. The method of claim 7, wherein the executable instructions further:

use an endpoint tracker key specifying an endpoint identification (ID) to access information relating to the endpoint and the number of tokens in the token bucket for each of a plurality of endpoints;

collect information for each of the endpoints according to the accessed information; and

determine a health state of each of the endpoints according to the information collected.

13. The method of claim 7, wherein the executable instructions further track the number of tokens in the token bucket.

14. The method of claim 7, wherein the executable instructions further:

determine a percentage of the calls to the endpoint exceeding the allowable call failure rate;

set a flag for an endpoint that has a number of tokens in a token bucket below the allowable call failure rate to trigger delaying the calls to the endpoint; and

issue an alert indicating the percentage of the calls to the endpoint exceed the allowable call failure rate.

15. The method of claim 7, wherein the executable instructions further refill the token bucket with at least one token per passing of a predefined time period.

16. The method of claim 7, wherein the executable instructions further remove at least one token from the token bucket upon each occurrence of a call failure to the endpoint.

17. The method of claim 7, wherein the executable instructions further:

determine the endpoint is a least recently used endpoint in a group of endpoints;

define the least recently used endpoint as operating in a healthy state; and

remove the least recently used endpoint from the group of endpoints.

18. A method for providing a call failure backoff in a computing service environment, the method comprises:

defining an allowable call failure rate using a token bucket for application programming interface (API) calls executed on an endpoint, wherein a single token is defined as being equal to one API call failure;

determining a number of tokens in the token bucket prior to executing an API call at the endpoint;

assigning a token in the token bucket to failed API calls;

decrementing a total token count number in the token bucket when the failed API calls are identified;

delaying API calls to the endpoint upon determining the number of tokens in the token bucket is equal to zero;

adding an additional token to the token bucket for each successful API call to the endpoint; and

refilling the token bucket with at least one token per predefined time period that has passed.

19. The method of claim 18, further comprising:

defining a selected token as equal to one call failure to the endpoint;

removing a token from the token bucket for each call failure to the endpoint;

defining an unhealthy state of the endpoint as having a number of tokens in the token bucket below a predetermined number of tokens; and

defining a healthy state of the endpoint as having a number of tokens in the token bucket above a predetermined number of tokens.

20. The method of claim 18, further comprising;

using an endpoint tracker key to identify a health status of endpoints; and

using the endpoint tracker key for grouping endpoints according to the health status.

21. The method of claim 20, wherein, the endpoint tracker key represents one or more endpoints, one or more combinations of properties of a request, a data stream type, a device type, network localities of a user issuing a request, or a geographical locality of a user.