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

• US 10,257,288 B2
• Filed: 12/15/2014
• Issued: 04/09/2019
• 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): Zhang, Shirley X
• Application Number:
  US14/570,900
• Publication Number:
  US 20150100630A1
• Time in Patent Office: 1,576 Days
• Field of Search: None
• 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 one or more computing devices;

receiving a plurality of service requests at a network-based service;

servicing a portion of the plurality of service requests at the network-based service based, at least in part, on a maximum allowable request rate;

determining respective numbers of units of work performed to service individual requests of the portion of the plurality of service requests at the network-based service, wherein the respective numbers of units of work performed to service the individual requests are non-uniform;

comparing, at the network-based service, an observed rate of the respective numbers of units of work performed to service the portion of the plurality of service requests with respect to a target rate determined based, at least in part, on a user specified throughput to service requests at the network-based service;

based, at least in part, on the comparison, adjusting the maximum allowable request rate; and

subsequent to said adjusting;

receiving one or more additional service requests at the network-based service; and

servicing a portion of the additional service requests at the network-based service based, at least in part, on the adjusted maximum allowable request rate.

2. The method of claim 1,

wherein the comparison of the observed rate with the target rate determines that the observed rate exceeds the target rate;

and

wherein said adjusting comprises;

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

lowering the maximum allowable request rate by the determined amount.

3. The method of claim 1,

wherein the comparison of the observed rate with the target rate determines that the observed rate is less than the target rate;

and

wherein said adjusting comprises;

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

raising the maximum request rate by the determined amount.

4. The method of claim 1, wherein said adjusting comprises:

determining a rejection rate for those service requests of the plurality of service requests; and

dependent on the rejection rate, calculating an amount by which the maximum allowable request rate is adjusted is determined.

5. The method of claim 4, wherein said determining the rejection rate comprises calculating a moving average for service request rejections over a plurality of sample periods.

6. The method of claim 1,

wherein the plurality of service requests and the additional service requests are access requests directed toward a partition of multiple partitions of a database table maintained on behalf of one or more clients at the network-based service;

wherein the method further comprises;

prior to receiving the plurality of service requests, initializing the maximum allowable request rate, wherein the maximum allowable request rate is initialized according to the user specified throughput level, and wherein the observed rate at which work was performed is a data transfer rate required to satisfy the portion of the service requests.

7. The method of claim 1, wherein the plurality of service requests and the additional service requests are one type of service request, wherein the maximum allowable request rate is specific to accept service requests of the one type of service request, wherein the receiving, the servicing, the determining, the comparing, the adjusting, and the subsequent receiving and servicing are performed for another plurality of service requests of a different type of service request than the one type such that another maximum allowable request rate specific to the different type of service request is adjusted to service requests of the different type of service request.

8. 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 at a network-based service;

service a portion of the plurality of service requests at the network-based service based, at least in part, on a maximum allowable request rate to service requests at the network-based service;

determine respective numbers of units of work performed to service individual requests of the portion of the plurality of service requests at the network-based service, wherein the respective numbers of units of work performed to service the individual requests are non-uniform;

compare an observed rate of the respective number of units work performed to service the portion of the service requests with respect to a target rate determined, based, at least in part, on a user specified throughput to service requests at the network-based service;

based, at least in part, on the comparison, adjust the maximum allowable request rate; and

subsequent to the adjust;

receive one or more additional service requests at the network-based service; and

service a portion of the additional service requests at the network-based service based, at least in part, on the adjusted maximum allowable request rate.

9. The system of claim 8,

wherein the comparison of the observed rate with the target rate determines that the observed rate exceeds the target rate for performing work;

and

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

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

lower the maximum allowable request rate by the determined amount.

10. The system of claim 8,

wherein the comparison of the observed rate with the target rate determines that the observed rate is less than the target rate for performing work;

and

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

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

raise the maximum allowable request rate by the determined amount.

11. The system of claim 8, wherein to adjust the maximum allowable request rate, the program instructions cause the one or more processors to:

determine a rejection rate for those service requests of the plurality of service requests; and

dependent on the rejection rate, calculate an amount by which the maximum allowable request rate is adjusted is determined.

12. The system of claim 11 wherein to determine the rejection rate, the program instructions cause the one or more processors to calculating a moving average for service request rejections over a plurality of sample periods.

13. The system of claim 8,

wherein the plurality of service requests and the additional service requests are access requests directed toward a partition of multiple partitions of a database table maintained on behalf of one or more clients at the network-based service;

wherein the program instructions further cause the one or more processors to;

prior to the receipt of the plurality of service requests, initialize the maximum allowable request rate, wherein the maximum allowable request rate is initialized according to the user specified throughput level, and wherein the observed rate at which work was performed is a data transfer rate required to satisfy the portion of the service requests.

14. The system of claim 8, wherein the plurality of service requests and the additional service requests are one type of service request, wherein the maximum allowable request rate is specific to accept service requests of the one type of service request, wherein the receive, the service, the determination, the comparison, the adjust, and the subsequent receive and service are performed for another plurality of service requests of a different type of service request than the one type such that another maximum allowable request rate specific to the different type of service request is adjusted to service requests of the different type of service request.

15. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

receiving a plurality of service requests at a network-based service;

servicing a portion of the plurality of service requests at the network-based service based, at least in part, on a maximum allowable request rate to service requests at the network-based service;

determining respective numbers of units of work performed to service individual requests of the portion of the plurality of service requests at the network-based service, wherein the respective numbers of units of work performed to service the individual requests are non-uniform;

comparing, at the network-based service, an observed rate of the respective numbers of units of work performed to service the portion of the service requests with respect to a target rate determined based, at least in part, on a user specified throughput to service requests at the network-based service;

based, at least in part, on the comparison, adjusting the maximum allowable request rate; and

subsequent to said adjusting;

receiving one or more additional service requests at the network-based service; and

servicing a portion of the additional service requests at the network-based service based, at least in part, on the adjusted maximum allowable request rate.

16. The non-transitory, computer-readable storage medium of claim 15

wherein the comparison of the observed rate with the target rate determines that the observed rate exceeds the target rate for performing work;

and

wherein, in said adjusting, the program instructions cause the one or more computing devices to implement;

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

lowering the maximum allowable request rate by the determined amount.

17. The non-transitory, computer-readable storage medium of claim 15,

wherein the comparison of the observed rate with the target rate determines that the observed rate is less than the target rate for performing work;

and

wherein, in said adjusting, the program instructions cause the one or more computing devices to implement;

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

raising the maximum allowable request rate by the determined amount.

18. The non-transitory, computer-readable storage medium of claim 15, wherein, in said adjusting, the program instructions cause the one or more computing devices to implement:

determining a rejection rate for those service requests of the plurality of service requests; and

dependent on the rejection rate, calculating an amount by which the maximum allowable request rate is adjusted is determined.

19. The non-transitory, computer-readable storage medium of claim 15,

wherein the plurality of service requests and the additional service requests are access requests directed toward a partition of multiple partitions of a database table maintained on behalf of one or more clients;

wherein cause the one or more computing devices to further implement;

prior to receiving the plurality of service requests, initializing the maximum allowable request rate, wherein the maximum request rate is initialized according to the user specified throughput, and wherein the observed rate at which work was performed is a data transfer rate required to satisfy the portion of the service requests.

20. The non-transitory, computer-readable storage medium of claim 15, wherein the plurality of service requests and the additional service requests are one type of service request, wherein the maximum allowable request rate is specific to accept service requests of the one type of service request, wherein the receiving, the servicing, the determining, the comparing, the adjusting, and the subsequent receiving and servicing are performed for another plurality of service requests of a different type of service request than the one type such that another maximum allowable request rate specific to the different type of service request is adjusted to service requests of the different type of service request.