Burst throttling for multi-tenant storage services

Patent metadata

Field	Value
Publication number	US-9703602-B1
Application number	US-201514675576-A
Country	US
Kind code	B1
Filing date	Mar 31, 2015
Priority date	Mar 31, 2015
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Burst throttling methods may be used manage computing resources of a data storage service. Tokens may represent I/O operations executed by a customer of the data storage service. A global token bucket may contain a set of tokens representing the overall I/O operation capacity of the data storage service. Additionally, a work token bucket may contain a set of tokens for a given logical volume maintained by the data storage service. When I/O request are received tokens may be charged the global token bucket and the work token bucket. Furthermore, if there is sufficient capacity the data storage service may charge a reduced number of tokens to the work token bucket.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a work request indicating an operation to be performed by one or more computer systems of a data storage service and utilizing computing resources of the one or more computer systems, wherein the work request is to access resources of the data storage service;
determining a number of tokens associated with the work request, where the number of tokens indicate an amount of computing resources utilized by the one or more computer systems to process the received work request;
removing the number of tokens from a burst token bucket associated with a logical volume maintained by the data storage service if a sufficient number of tokens to process the work request are in the burst token bucket, where the burst token bucket is configured to allow an increased number of tokens to be removed per an interval of time based at least in part on one or more attributes of the logical volume;
if there are insufficient tokens in the burst token bucket, determining a reduced number of tokens to remove from a work token bucket associated with the logical volume and removing the reduced number of tokens from the work token bucket if there is at least one token remaining in a global token bucket to enable a capacity associated with the logical volume to be exceeded;
removing the number of tokens from the global token bucket, where the global token bucket includes a second number of tokens associated with an amount of computing resources remaining available to the one or more computer systems; and
processing the work request.

2. The computer-implemented method of claim 1 , wherein the computer-implemented method further comprises filling the burst token bucket at a rate based at least in part on a size of a logical volume associated with the work token bucket.

3. The computer-implemented method of claim 1 , wherein the data storage service is a block-level storage service.

4. The computer-implemented method of claim 1 , wherein the work token bucket is configured such that the burst token bucket has a maximum number of tokens that can be removed from the work token bucket per the interval of time.

5. The computer-implemented method of claim 1 , wherein the burst token bucket is configured such that the work token bucket has a maximum capacity of tokens that the burst token bucket can contain.

6. A system, comprising:
one or more processors; and
memory that includes instructions that, when executed by the one or more processors, cause the system to:
receive a request associated with a logical volume to be performed by the system utilizing computing resources of the system;
determine a first number of tokens associated with an amount of computing resources required by the system to process the request;
remove the first number of tokens from a first bucket, wherein the first bucket includes a first set of tokens associated with a burst-throttling mechanism and has sufficient tokens available in the first bucket to process the request;
remove the first number of tokens from a second bucket if there is insufficient tokens available in the first bucket to process the request to enable a capacity associated with the logical volume to be exceeded, wherein the second bucket includes a second set of tokens associated with one or more attributes of the logical volume;
remove the first number of tokens from a third bucket, where the third bucket includes a set of tokens associated with a capacity of the system; and
process the request based at least in part on removing the first number of tokens from the first bucket or the second bucket.

7. The system of claim 6 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to initialize the first bucket including a token fill rate per the interval of time based at least in part on an allocation of computing resources of the system to a customer associated with the logical volume.

8. The system of claim 7 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to modify the token fill rate based at least in part on an additional allocation of computing resources to the customer or one or more attributes of requests received at the system.

9. The system of claim 7 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to allocate the computing resources of the system to the customer such that the customer is allocated a maximum amount of computing resources consumable by the customer over the interval of time.

10. The system of claim 9 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to modify the maximum amount of computing resources consumable by the customer over the interval of time based at least in part on a modification to a total amount of computing resources allocated to the customer.

11. The system of claim 6 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to:
determine that the first bucket has an insufficient number of tokens to remove the first number of tokens;
determine an delay interval of time to delay processing the received request based at least in part on the first number of tokens and a fill rate associated with the first bucket; and
delay processing of the received request for at least the delay interval of time.

12. The system of claim 6 , wherein the first number of tokens associated with a size of an I/O request included in the received request.

13. The system of claim 12 , wherein the instructions further includes instructions that, when executed by the one or more processors cause the system to:
determine that, after removing the first number of tokens, the first bucket contains less than a threshold number of tokens; and
remove the first number of tokens from a work token bucket associated with a secondary throttling mechanism.

14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:
initialize a first token bucket with a first set of tokens associated with an amount of computing resources allocated to a customer;
initialize a second token bucket with a second set of tokens associated with computing resources of the computer system;
receive a request for computing resources associated with the customer;
determine an amount of tokens to be remove from the first token bucket and a third token bucket based at least in part on the received request, the third bucket includes a third set of tokens associated with a throttling mechanism; and
remove the amount of tokens from the first token bucket and the second token bucket as a result of the third set of tokens contained in the third token bucket being less than the amount of tokens to enable a capacity allocated to the customer, and associated with the computing resources associated with the customer to be exceeded; and
process the request.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:
create a logical storage volume utilizing the computing resources of the system; and
wherein initialize the first token bucket with the first set of tokens is based at least in part on a size of th

Assignees

• Amazon Tech Inc

Inventors

• Kusters Norbert Paul
• Smiley John Robert
• Brooker Marc John
• Guo Bei-Jing
• Levy Marc

Classifications

• G06F2209/504

  Resource capping · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F2209/503

  Resource availability · CPC title