System and method for throttling service requests having non-uniform workloads

• US 8,914,497 B1
• Filed: 12/15/2011
• Issued: 12/16/2014
• 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 A., Rath, Timothy Andrew, Filipe, Miguel Mascarenhas, Yanacek, David C., Maccanti, Maximiliano
• Primary Examiner(s): ZHANG, SHIRLEY X
• Application Number:
  US13/327,620
• Time in Patent Office: 1,097 Days
• Field of Search: 709224-226, 370229-2351
• US Class Current: 709/224
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 47/76 using dynamic resource allocation, e.g. in-call renegotiation requested by the user or requested by the network in response to changing network conditions
• CPC Class Codes: H04L 47/78 Architectures of resource allocation
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A system that provides services to clients may receive and service requests, various ones of which may require different amounts of work. The system may determine whether it is operating in an overloaded or underloaded state based on a current work throughput rate, a target work throughput rate, a maximum request rate, or an actual request rate, and may dynamically adjust the maximum request rate in response. For example, if the maximum request rate is being exceeded, the maximum request rate may be raised or lowered, dependent on the current work throughput rate. If the target or committed work throughput rate is being exceeded, but the maximum request rate is not being exceeded, a lower maximum request rate may be proposed. Adjustments to the maximum request rate may be made using multiple incremental adjustments. Service request tokens may be added to a leaky token bucket at the maximum request rate.

Claims

1. A method, comprising:

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

receiving a plurality of requests to read or write data on behalf of one or more clients;

servicing a portion of the requests, wherein the portion of the plurality of service requests that is serviced is dependent on a maximum request rate;

determining that the rate at which the plurality of requests was received exceeds the maximum request rate;

in response to said determining, adjusting the maximum request rate, wherein said adjusting is dependent on an observed data transfer rate required to satisfy the portion of the requests, and wherein the amount of data transferred in servicing each of the requests in the portion of the requests is non-uniform; and

subsequent to said adjusting;

receiving one or more additional requests to read or write data on behalf of the one or more clients; and

servicing a portion of the additional requests, wherein the portion of the additional requests that is serviced is dependent on the adjusted maximum request rate.

2. The method of claim 1,

wherein the observed data transfer rate exceeds a target data transfer rate;

and

wherein said adjusting comprises;

determining an amount by which to lower the maximum request rate; and

lowering the maximum request rate by the determined amount.

3. The method of claim 2,

wherein the maximum request rate represents the maximum number of requests that can be accepted for servicing per second;

and

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 observed data transfer rate is an average of data transfer rates measured in two or more sample periods.

5. The method of claim 1,

wherein the observed data transfer rate is less than a target data transfer rate;

and

wherein said adjusting comprises;

determining an amount by which to raise the maximum request rate; and

raising the maximum request rate by the determined amount.

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;

receive a plurality of service requests;

service a portion of the service requests, wherein the portion of the plurality of service requests that is serviced is dependent on a maximum request rate;

determine that the rate at which the plurality of requests was received exceeds the maximum request rate;

in response to said determination, adjust the maximum request rate, wherein said adjustment is dependent on an observed rate at which work was performed to service the portion of the service requests, and wherein the amount of work performed to service each of the service requests in the portion of the service requests is non-uniform; and

subsequent to said adjust;

receive one or more additional service requests; and

service a portion of the additional service requests, wherein the portion of the additional service requests that is serviced is dependent on the adjusted maximum request rate.

7. The system of claim 6,

wherein the observed rate at which work was performed exceeds a target rate for performing work when servicing requests;

and

wherein to adjust the maximum request rate, the program instructions further cause the one or more processors to;

determine an amount by which to lower the maximum request rate; and

lower the maximum request rate by the determined amount.

8. The system of claim 7,

wherein the maximum request rate represents the maximum number of requests that can be accepted for service per second;

and

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

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

10. The system of claim 6, wherein the observed rate at which work was performed represents an average of the rates at which work was performed in two or more sample periods.

11. The system of claim 10, wherein the average of the rates at which work was performed represents a moving average over a particular number of sample periods.

12. The system of claim 6,

wherein the observed rate at which work was performed is less than a target rate for performed work for service of one or more requests;

and

wherein to adjust the maximum request rate, the program instructions further cause the one or more processors to;

determine an amount by which to raise the maximum request rate; and

raise the maximum request rate by the determined amount.

13. The system of claim 6, wherein to adjust the maximum request rate, the program instructions further cause the one or more processors to raise or lower the maximum request rate with two or more incremental adjustments, and wherein the number of incremental adjustments is dependent on a configurable parameter value.

14. The system of claim 6, wherein to determine that the rate at which the plurality of requests was received exceeds the maximum request rate, the program instructions further cause the one or more processors to determine that at least some of the plurality of requests were rejected.

15. The system of claim 6, wherein prior to said adjustment, the maximum request rate comprises an initial maximum request rate, and wherein the initial maximum request rate is dependent on a system-wide or client-specific policy, a historical request rate, a maximum possible amount of work required to satisfy a request, a minimum possible amount of work required to satisfy a request, or a historical amount of work required to satisfy a request.

16. The system of claim 6, wherein said determination and said adjustment are performed in response to selection of an admission control mechanism that includes a token bucket comprising tokens that represent service requests from among two or more admission control mechanisms supported in the system.

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

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

receive one or more additional service requests; and

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

18. The system of claim 16, 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 a fixed amount of work.

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

servicing at least a portion of the service requests, wherein service requests are accepted for servicing at a rate no higher than a maximum request rate;

determining that the rate at which work was performed when servicing the at least a portion of the service requests exceeds a target rate for performing work;

in response to said determining, adjusting the maximum request rate, wherein said adjusting is dependent on the rate at which work was performed in servicing the at least a portion of the service requests; and

subsequent to said adjusting;

receiving one or more additional service requests; and

servicing at least a portion of the additional service requests, dependent on the adjusted maximum request rate.

20. The method of claim 19,

wherein the rate at which the plurality of service requests was received exceeds the maximum request rate;

and

wherein said adjusting comprises lowering the maximum request rate.

21. The method of claim 20, wherein said lowering comprises:

determining an amount by which to lower the maximum request rate dependent on the maximum request rate; and

lowering the maximum request rate by the determined amount.

22. The method of claim 21, wherein said lowering comprises lowering the maximum request rate using two or more incremental adjustments, and wherein the number of incremental adjustments is dependent on a configurable parameter value.

23. The method of claim 19, wherein the rate at which work was performed is expressed as an average of the rates at which work was performed in two or more sample periods.

24. The method of claim 19,

wherein the rate at which the plurality of service requests was received is less than the maximum request rate;

and

wherein said adjusting comprises calculating a proposed new maximum request rate, wherein said calculating is not dependent on the maximum request rate.

25. The method of claim 19,

wherein said determining and said adjusting are performed in response to selection of an admission control mechanism that includes a token bucket comprising tokens that represent service requests from among two or more supported admission control mechanisms;

wherein the method further comprises;

selecting a different one of the two or more supported 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.

26. The method of claim 25, wherein another one of the two or more supported admission control mechanisms comprises an admission control mechanism that includes a token bucket comprising tokens that represent a fixed amount of work.

27. 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:

receiving and servicing a plurality of service requests, wherein the service requests are received at a rate no higher than a maximum request rate, wherein the amount of work required to satisfy each of the plurality of service requests is non-uniform, and wherein the rate at which work is performed in servicing the plurality of service requests is no higher than a target rate for performing work in servicing service requests;

receiving and servicing one or more additional service requests;

determining that the rate at which work was performed when servicing the one or more additional service requests is different from the rate at which work is performed in servicing the plurality of service requests; and

in response to said determining, adjusting the maximum request rate, wherein said adjusting is dependent on the rate at which work was performed in servicing the one or more additional service requests.

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

subsequent to said adjusting;

receiving one or more other service requests; and

servicing at least a portion of the other service requests, dependent on the adjusted maximum request rate.

29. The storage medium of claim 27,

wherein the rate at which the one or more additional service requests was received exceeds the maximum request rate;

wherein the rate at which work was performed when servicing the one or more additional service requests exceeds the target rate for performing work in servicing requests; and

wherein said adjusting comprises;

determining an amount by which to lower the maximum request rate; and

lowering the maximum request rate by the determined amount.

30. The storage medium of claim 27,

wherein the rate at which work was performed when servicing the one or more additional service requests is less than the target rate for performing work in servicing requests;

and

wherein said adjusting comprises;

determining an amount by which to raise the maximum request rate; and

raising the maximum request rate by the determined amount.

31. The storage medium of claim 30,

wherein the rate at which the one or more additional service requests was received exceeds the maximum request rate;

and

wherein said raising the maximum request rate is performed in accordance with a policy specifying that the maximum request rate be raised only in situations in which the rate at service requests are received exceeds the maximum request rate.

32. The storage medium of claim 27,

wherein the rate at which the one or more additional service requests was received is less than the maximum request rate;

wherein the rate at which work was performed when servicing the one or more additional service requests exceeds the target rate for performing work in servicing requests; and

wherein said adjusting comprises calculating a proposed new maximum request rate, wherein said calculating is not dependent on the maximum request rate.

33. The storage medium of claim 27,

wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform, subsequent to said adjusting, generating service request tokens in a token bucket at a rate equal to the adjusted maximum request rate;

wherein said servicing at least a portion of the other service requests comprises servicing any service request that is received while at least a pre-determined minimum number of service tokens is present in the token bucket; and

wherein servicing a service request that is received while at least the pre-determined minimum number of service tokens is present in the token bucket comprises removing a service token from the token bucket.

34. The storage medium of claim 27, wherein the rate at which work was performed when servicing the one or more additional service requests is expressed as an average of the rates at which work was performed in two or more sample periods.

35. The storage medium of claim 27, wherein said adjusting comprises raising or lowering the maximum request rate using two or more incremental adjustments, and wherein the number of incremental adjustments is dependent on a configurable parameter value.