System and method for throttling service requests using work-based tokens

• US 9,419,904 B2
• Filed: 02/09/2015
• Issued: 08/16/2016
• Est. Priority Date: 12/15/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Xiao, Wei, Lutz, David Alan, Rath, Timothy Andrew, Maccanti, Maximiliano, Filipe, Miguel Mascarenhas, Yanacek, David Craig
• Primary Examiner(s): Haile, Awet
• Application Number:
  US14/617,671
• Publication Number:
  US 20150156123A1
• Time in Patent Office: 554 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A system that provides services to clients may receive and service requests, various ones of which may require different amounts of work. An admission control mechanism may manage requests based on tokens, each of which represents a fixed amount of work. The tokens may be added to a token bucket at rate that is dependent on a target work throughput rate while the number of tokens in the bucket does not exceed its maximum capacity. If at least a pre-determined minimum number of tokens is present in the bucket when a service request is received, it may be serviced. Servicing a request may include deducting an initial number of tokens from the bucket, determining that the amount of work performed in servicing the request is different than that represented by the initially deducted tokens, and deducting additional tokens from or replacing tokens in the bucket to reflect the difference.

Claims

1. A method, comprising:

performing by a computer system that provides storage services to clients;

receiving a request to read or write data on behalf of a client;

determining whether at least one token is present in a token bucket, wherein each token in the token bucket represents a unit of work for an input/output (I/O) operation in terms of a fixed amount of data transferred;

in response to determining that at least one token is present in the token bucket;

accepting the received request for servicing;

deducting an initial number of tokens from the token bucket;

servicing the received request, wherein said servicing comprises transferring a particular amount of data, and wherein the amount of data transferred in servicing different service requests is non-uniform; and

determining that the particular amount of data transferred is at least a threshold amount more or at least a threshold amount less than the transferred data amount represented by the initial number of tokens; and

in response to determining that the particular amount of data transferred is at least the threshold amount more or at least the threshold amount less than the transferred data amount represented by the initial number of tokens, deducting an additional number of tokens from the token bucket or replacing a number of tokens in the token bucket, wherein the additional number of tokens deducted or the number of tokens replaced represents the difference between the particular amount of data transferred and the transferred data amount represented by the initial number of tokens.

2. The method of claim 1, wherein the initial number of tokens represents an estimate of the amount of data to be transferred in servicing the received request or an average of amount of data transferred when servicing requests in one or more recent sample periods.

3. The method of claim 1, further comprising:

generating tokens in the token bucket at a rate that is dependent on a target data transfer rate;

wherein said generating is performed while the number of tokens in the token bucket does not exceed a maximum capacity for the token bucket.

4. The method of claim 3,

wherein the target data transfer rate is specified in terms of a number of input/output (I/O) operations per second.

5. The method of claim 3, wherein the target data transfer rate comprises a committed data transfer rate that is specified by a system-wide policy, by a client-specific policy, or in a service level agreement.

6. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform;

receiving a service request;

determining whether at least a pre-determined minimum number of tokens is present in a token bucket, wherein each token in the token bucket represents a fixed amount of work;

in response to determining that at least the pre-determined minimum number of tokens is present in the token bucket;

accepting the received service request for servicing;

deducting an initial number of tokens from the token bucket;

servicing the received service request, wherein said servicing comprises performing a particular amount of work, and wherein the amount of work performed in servicing different service requests is non-uniform and;

determining that the particular amount of work is at least a threshold amount greater than or at least a threshold amount less than the amount of work represented by the initial number of tokens; and

in response to determining that the particular amount of work is at least the threshold amount greater than or at least the threshold amount less than the amount of work represented by the initial number of tokens, deducting an additional number of tokens from the token bucket or replacing a number of tokens in the token bucket, wherein the additional number of tokens deducted or the number of tokens replaced represents the difference between the particular amount of work and the amount of work represented by the initial number of tokens.

7. The system of claim 6, wherein the initial number of tokens is a fixed number.

8. The system of claim 6, wherein the initial number of tokens is configurable.

9. The system of claim 6, wherein the initial number of tokens represents an estimate of the amount of work to be performed when servicing the received service request.

10. The system of claim 6, wherein the initial number of tokens represents an average amount of work performed per request when servicing requests in one or more recent sample periods.

11. The system of claim 6, wherein when executed by the one or more processors the program instructions further cause the one or more processors to perform:

generating tokens in the token bucket at a rate that is dependent on a target rate for performing work.

12. The system of claim 11,

wherein each token in the token bucket represents a unit of work;

and

wherein the target rate for performing work is specified in terms of a number of units of work performed per second.

13. The system of claim 11, wherein the target rate for performing work comprises a committed rate for performing work that is specified by a system-wide policy, by a client-specific policy, or in a service level agreement.

14. The system of claim 11, wherein said generating is performed while the number of tokens in the token bucket does not exceed a maximum capacity for the token bucket.

15. The system of claim 14, wherein the maximum capacity for the token bucket is dependent on the target rate for performing work.

16. The system of claim 14, wherein when executed by the one or more processors the program instructions further cause the one or more processors to perform:

modifying the rate at which tokens are generated in the token bucket or the maximum capacity for the token bucket; and

subsequent to said modifying;

receiving a second service request;

determining whether at least a current minimum number of tokens is present in the token bucket;

in response to determining that at least the current minimum number of tokens is present in the token bucket;

accepting the second service request;

deducting the initial number of tokens from the token bucket;

servicing the second service request, wherein said servicing the second service request comprises performing a second amount of work, and wherein the second amount of work is different from the particular amount of work;

determining that the second amount of work is greater than or less than the amount of work represented by the initial number of tokens; and

in response to determining that the second amount of work is greater than or less than the amount of work represented by the initial number of tokens, deducting one or more additional tokens from the token bucket or replacing one or more tokens in the token bucket, wherein the one or more additional tokens deducted or the one or more tokens replaced represent the difference between the second amount of work and the amount of work represented by the initial number of tokens.

17. The system of claim 6, wherein when executed by the one or more processors the program instructions further cause the one or more processors to perform:

modifying the initial number of tokens; and

subsequent to said modifying;

accepting a second service request;

deducting the modified initial number of tokens from the token bucket;

servicing the second service request, wherein said servicing the second service request comprises performing a second amount of work, and wherein the second amount of work is different from the particular amount of work;

determining that the second amount of work is greater than or less than the amount of work represented by the modified initial number of tokens; and

in response to determining that the second amount of work is greater than or less than the amount of work represented by the modified initial number of tokens, deducting one or more additional tokens from the token bucket or replacing one or more tokens in the token bucket, wherein the one or more additional tokens deducted or the one or more tokens replaced represent the difference between the second amount of work and the amount of work represented by the modified initial number of tokens.

18. The system of claim 6, wherein said deducting an initial number of tokens from the token bucket, said determining that the particular amount of work is more than the amount of work represented by the initial number of tokens, and said deducting an additional number of tokens from the token bucket or replacing a number of tokens in the token bucket are performed in response to selection of an admission control mechanism that includes a token bucket comprising tokens that represent a fixed amount of work from among two or more admission control mechanisms supported in the system.

19. The system of claim 18, wherein when executed by the one or more processors the program instructions further cause the one or more processors to perform, subsequent to said deducting an additional number of tokens from the token bucket:

selecting a different one of the two or more admission control mechanisms;

receiving one or more additional service requests; and

managing the one or more additional service requests using the different admission control mechanism.

20. The system of claim 18, wherein another one of the two or more admission control mechanisms comprises an admission control mechanism that includes a token bucket comprising tokens that represent service requests.