US 11,601,512 B2Granted

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

AssigneeAmazon Technologies, Inc.

InventorsWei Xiao, David Alan Lutz, Timothy Andrew Rath, Maximiliano Maccanti, Miguel Mascarenhas Filipe, David Craig Yanacek

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims20

Dependent claims

A system, comprising:

at least one processor;
and a memory storing program instructions that when executed by the at least one processor cause the at least one processor to implement a network-based service, the network-based service configured to:
manage performance of a plurality of service requests received at a network-based service according to a user specified throughput to service requests at the network-based service and within a maximum allowable request rate;
determine respective numbers of units of work performed to service individual requests of a portion of the plurality of service requests at the network-based service;
compare, 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 the user specified throughput to service requests at the network-based service;
and
based, at least in part, on the comparison, adjust the maximum allowable request rate used to manage performance of additional service requests received at the network-based service subsequent to the adjustment to the maximum allowable request rate.

4 more elements

A method, comprising:

managing performance of a plurality of service requests received at a network-based service according to a user specified throughput to service requests at the network-based service and within a maximum allowable request rate;
determining respective numbers of units of work performed to service individual requests of a portion of the plurality of service requests at the network-based service;
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 the user specified throughput to service requests at the network-based service;
and
based, at least in part, on the comparison, adjusting the maximum allowable request rate used to manage performance of additional service requests received at the network-based service subsequent to the adjustment to the maximum allowable request rate.

2 more elements

One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement:

managing performance of a plurality of service requests received at a network-based service according to a user specified throughput to service requests at the network-based service and within a maximum allowable request rate;
determining respective numbers of units of work performed to service individual requests of a portion of the plurality of service requests at the network-based service;
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 the user specified throughput to service requests at the network-based service;
and
based, at least in part, on the comparison, adjusting the maximum allowable request rate used to manage performance of additional service requests received at the network-based service subsequent to the adjustment to the maximum allowable request rate.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/245,811Filed 30 Apr 2021 · continuation
Priority: 15 Dec 2011
Published: US 2021/0329077 A121 Oct 2021
Granted: 7 Mar 2023
Term ends: Not estimatedThe source records don’t support an estimate.

Classification14 codes

G06F 9/505
The resource being a machine, e.g. CPUs, Servers, Terminals: considering the load
G06F 11/3433
For performance assessment: for load management
G06F 11/3452
Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of…:…
G06F 11/3485
Performance evaluation by tracing or monitoring: for I/O devices

Family

Application13/327,620Parent of this continuation · filed 15 Dec 2011
Application14/570,900Parent of this continuation · filed 15 Dec 2014
US 8,914,497 B1Parent of this continuation · filed 16 Dec 2014
Application16/377,078Parent of this continuation · filed 5 Apr 2019
US 10,257,288 B2Parent of this continuation · filed 9 Apr 2019
US 2021/0329077 A1Pre-grant publication · published 21 Oct 2021
US 10,999,381 B2Parent of this continuation
US 2015/0100630 A1Published application
US 2019/0306255 A1Published application
US 11,601,512 B2This patent

From the US filing history. Foreign family members aren’t listed.