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

• US 8,953,453 B1
• Filed: 12/15/2011
• Issued: 02/10/2015
• Est. Priority Date: 12/15/2011
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Xiao, Wei, Lutz, David A., Rath, Timothy Andrew, Maccanti, Maximiliano, Filipe, Miguel Mascarenhas, Yanacek, David C.
• Primary Examiner(s): HAILE, AWET A
• Application Number:
  US13/327,616
• Time in Patent Office: 1,153 Days
• Field of Search: 370/229, 370/263.1, 370/252, 370/230, 370/230.1, 370/234, 370/335, 370/389, 370/394, 370/395.1, 370/395.41, 370/395.52, 370/396, 370/909, 370/412, 370/413
• US Class Current: 370/235.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/0) 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;

determining that the particular amount of data transferred is more or 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 more or 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;

wherein said deducting an initial number of tokens from the token bucket, said determining that the particular amount of data transferred is more or less than the transferred data amount 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 data transferred from among two or more admission control mechanisms supported in the system;

wherein 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.

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,

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

4. The method of claim 1, 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.

5. 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;

determining that the particular 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 particular amount of work is greater than or 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;

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;

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.

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

7. The system of claim 5, wherein the initial number of tokens is configurable.

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

9. The system of claim 5, 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.

10. The system of claim 5,

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.

11. The system of claim 5, 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.

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

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

14. The system of claim 12, 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.

15. The system of claim 5, 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.

16. The system of claim 5, 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.

17. A method, comprising:

performing by a computer system;

receiving a plurality of service requests, wherein the amount of work required to satisfy each of the service requests is non-uniform; and

servicing at least a portion of the service requests, wherein said servicing comprises, for each of the service requests in the at least a portion of the service requests;

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;

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

determining that the particular 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 particular amount of work is greater than or 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;

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;

wherein 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.

18. The method of claim 17, wherein the initial number of tokens represents an estimate of the amount of work to be performed when servicing requests or an average amount of work performed per request when servicing requests in one or more recent sample periods.

19. The method of claim 17, further comprising:

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.

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

21. The method of claim 17, further comprising:

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 one or more additional service requests;

servicing at least a portion of the one or more additional service requests wherein said servicing comprises, for each of the service requests in the at least a portion of the one or more additional service requests;

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

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

accepting the received service request for servicing;

deducting the initial number of tokens from the token bucket;

performing a respective amount of work;

determining that the respective 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 respective 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 represents the difference between the respective amount of work and the amount of work represented by the initial number of tokens.

22. The method of claim 17, further comprising:

modifying the initial number of tokens; and

subsequent to said modifying;

receiving one or more additional service requests;

servicing at least a portion of the one or more additional service requests wherein said servicing comprises, for each of the service requests in the at least a portion of the one or more additional service requests;

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

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

accepting the received service request for servicing;

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

performing a respective amount of work;

determining that the respective 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 respective 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 represents the difference between the respective amount of work and the amount of work represented by the modified initial number of tokens.

23. The method of claim 22, wherein said modifying is dependent on the amount of work performed by the at least a portion of the plurality of service requests.

24. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

while the number of tokens in a token bucket is greater than or equal to a pre-determined minimum number of tokens and does not exceed a maximum capacity for the token bucket;

generating tokens in the token bucket at a rate that is dependent on a target rate for performing work, wherein each token in the token bucket represents a unit of work; and

servicing one or more received service requests, wherein said servicing comprises, for each of the received service requests;

deducting an initial number of tokens from the token bucket;

performing a respective amount of work, wherein the amount of work performed in servicing different service requests is non-uniform;

determining that the respective 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 respective amount of work is greater than or 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 respective amount of work and the amount of work represented by the initial number of tokens;

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;

wherein 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.

25. The storage medium of claim 24, wherein the target rate for performing work is specified in terms of a number of units of work performed per second.

26. The storage medium of claim 24, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

while the number of tokens in the token bucket is positive and exceeds a maximum capacity for the token bucket, servicing one or more additional service requests while refraining from generating any tokens in the token bucket.

27. The storage medium of claim 24, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

while the number of tokens in the token bucket is negative, generating tokens in the token bucket at a rate that is dependent on a target rate for performing work, while refraining from servicing any additional received service requests.

28. The storage medium of claim 24, wherein the initial number of tokens represents an estimate of the amount of work to be performed when servicing requests or an average amount of work performed per request when servicing requests in one or more recent sample periods.

29. The storage medium of claim 24, 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.

30. The storage medium of claim 24, wherein the maximum capacity for the token bucket is dependent on the target rate for performing work.

31. The storage medium of claim 24, wherein at least one of the initial number of tokens, the target rate for performing work, the pre-determined minimum number of tokens, or the maximum capacity for the token bucket is configurable.