Adaptive throttling for shared resources

Patent metadata

Field	Value
Publication number	US-9712453-B1
Application number	US-201213429735-A
Country	US
Kind code	B1
Filing date	Mar 26, 2012
Priority date	Mar 26, 2012
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

Customers of shared resources in a multi-tenant environment can have token buckets allocated that have an associated depth and fill rate, with each token enabling the customer to obtain an amount of work from a shared resource. A resource management system can monitor one or more system or output metrics, and can adjust a global fill rate based at least in part upon values of the monitored metrics. Such an approach can provide a fair distribution of work among the customers, while ensuring that the metrics stay within acceptable ranges and there are no drastic changes in performance levels of the system. The fill rate can update dynamically with changes in the monitored parameters, such that the system can float near an equilibrium point. Commitments for specific minimum service levels also can be met.

First claim

What is claimed is:

1. A computer-implemented method of managing access to shared resources, comprising:
providing a requestor with a token bucket configured to contain up to a determined number of tokens, a token configured to enable the requestor to obtain an amount of work from a shared resource in a multi-tenant environment, wherein the determined number of tokens in at least one token bucket is one token that is replenished after a previous token is used;
receiving a request from the requestor to perform an input/output (I/O) operation with respect to at least one shared resource, the requestor associated with a token bucket;
enabling the request to be processed using the at least one shared resource when there is at least one token in the token bucket for the requestor;
determining a value for a performance parameter of the multi-tenant environment;
analyzing a current read request latency value for a subset of customer requests in the multi-tenant environment, wherein the current read request latency value comprises a duration of time for responding to a read request;
determining that the current read request latency value is outside a target range;
updating a token fill rate, the token fill rate being updated until the current read request latency value is back inside the target range, the token fill rate being based upon the current read request latency value and the value for the performance parameter; and
enabling the token bucket having less than the determined number of tokens to have additional tokens added at a rate up to the token fill rate.

2. The computer-implemented method of claim 1 , wherein the token fill rate is further updated when a value of the performance parameter falls outside a target range, the performance parameter including at least one of an amount of memory usage, an amount of processor usage, an amount of storage space, an amount of network usage, or a number of pending requests.

3. The computer-implemented method of claim 1 , wherein the at least one shared resource includes at least one data volume in a data environment.

4. The computer-implemented method of claim 1 , wherein the received request is capable of requiring more than one token to enable the request to be processed.

5. The computer-implemented method of claim 4 , wherein the received request is unable to be processed until a required number of tokens is contained in the token bucket.

6. The computer-implemented method of claim 4 , wherein the request is able to be processed using more tokens than are allowed for a current determined number of tokens for a token bucket, the token bucket having a token balance of less than zero tokens after processing of the request, the token balance being refilled at the token fill rate.

7. A computer-implemented method in a multi-tenant environment, comprising:
under control of one or more computer systems configured with executable instructions,
providing a requestor with a token bucket configured to contain up to a determined number of tokens, a token configured to enable the requestor to obtain an amount of work from a shared resource in the multi-tenant environment, wherein the determined number of tokens in at least one token bucket is one token that is replenished after a previous token is used;
determining a rate at which the requestor is allowed to submit requests;
monitoring a value of a read request latency of the multi-tenant environment, wherein the value comprises a duration of time for responding to a read request;
determining that at least one system performance value is outside a target range;
updating a threshold rate at which the requestor is allowed to submit requests to the shared resource until the at least one system performance value is within the target range, wherein the rate is based at least in part on the value and the at least one system performance value; and
throttling requests from the requestor based at least in part on determining that requests are submitted at greater than the threshold rate.

8. The computer-implemented method of claim 7 , wherein the at least one system performance value includes at least one of an amount of memory usage, an amount of processor usage, an amount of storage space, an amount of network usage, or a number of pending requests.

9. The computer-implemented method of claim 7 , wherein the rate at which the requestor is allowed to submit requests is updated by larger increments as the monitored value approaches a constraint value for a respective performance parameter.

10. The computer-implemented method of claim 7 , wherein the shared resource includes a data volume or a server instance.

11. The computer-implemented method of claim 7 , wherein multiple system performance parameters are monitored, and
wherein the rate at which the requestor is allowed to submit requests is updated according to a minimum rate determined by a performance parameter.

12. The computer-implemented method of claim 7 , further comprising:
determining a rate guarantee for the requestor; and
providing the rate guarantee for the requestor in addition to the rate at which an additional requestor is allowed to submit requests.

13. The computer-implemented method of claim 12 , wherein the one or more computer systems are capable of providing the requestor with less than the rate guarantee when a value of a performance parameter falls outside a constraint value for the performance parameter.

14. The computer-implemented method of claim 7 , wherein the request is received as a Web service request to at least one application programming interface (API).

15. The computer-implemented method of claim 7 , further comprising monitoring of a value of at least one performance parameter performed using a random sampling of data for the performance parameter.

16. The computer-implemented method of claim 7 , wherein the at least one system performance parameter includes at least one apparent value of a performance parameter as determined by at least one client device for the requestor.

17. The computer-implemented method of claim 7 , wherein the request includes an input/output (I/O) operation to be performed by the shared resource.

18. A system for managing shared computing resources, comprising:
at least one processor; and
memory including instructions that, when executed by the at least one processor, cause the system to:
provide a requestor with a token bucket configured to contain up to a determined number of tokens, a token enabling the requestor to obtain an amount of work from a shared resource in a multi-tenant environment, wherein the determined number of tokens in at least one token bucket is one token that is replenished after a previous token is used;
determine a rate at which the requestor is allowed to submit requests, at least a portion of the requests specifying an I/O operation to be performed;
monitor a read request latency with respect to the shared resource, wherein the read request latency comprises a duration of time for responding to a read request;
determine that the read request latency is outside a target range; and
updating the rate at which the requestor is allowed to submit requests, the rate being updated until the monitored read request latency is back inside the target range, the rate being based at least in part on the read request latency and an additional performance parameter.

19. The system of claim 18 , wherein the additional performance parameter includes at least one of an amount of memory usage, an amount of processor u

Assignees

• Certain Tate Andrew
• Hamilton James R
• Amazon Tech Inc

Inventors

• Certain Tate Andrew
• Hamilton James R

Classifications

• H04L43/0817

  by checking functioning · CPC title

• G06F9/00

  Arrangements for program control, e.g. control units (program control for peripheral devices G06F13/10) · CPC title

• H04L41/5025

  by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade · CPC title

• H04L43/0852

  Delays · CPC title

• H04L41/5009

  Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF] · CPC title