Burst-mode admission control using token buckets

• US 9,471,393 B2
• Filed: 06/25/2013
• Issued: 10/18/2016
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Xiao, Wei, Swift, Bjorn Patrick, Muniswamy-Reddy, Kiran-Kumar, Filipe, Miguel Mascarenhas, Lu, Yijun, Marshall, Stuart Henry Seelye, Stefani, Stefano, Hamilton, James R.
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US13/926,686
• Publication Number:
  US 20140380324A1
• Time in Patent Office: 1,211 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/5013 Request control
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Methods and apparatus for burst-mode admission control using token buckets are disclosed. A work request (such as a read or a write) directed to a work target is received. Based on a first criterion, a determination is made that the work target is in a burst mode of operation. A token population of a burst-mode token bucket is determined, and if the population meets a second criterion, the work request is accepted for execution.

Claims

1. A system, comprising:

one or more computing devices configured to;

receive a work request directed to a work target;

in response to a determination that a token population of a normal-mode token bucket associated with the work target meets a first threshold criterion, consume one or more tokens from the normal-mode token bucket in accordance with a normal-mode token consumption policy, and accept the work request for execution; and

in response to a determination that the token population of the normal-mode token bucket does not meet the first threshold criterion,

determine whether a token population of at least one bucket of a burst-mode token bucket set meets a second threshold criterion;

in response to a determination that the token population of the at least one bucket of the burst-mode token bucket set meets the second threshold criterion, consume one or more tokens from the at least one bucket of the burst-mode token bucket set based at least in part on a burst-mode token consumption policy, and accept the work request for execution, and

in response to a determination that the token population of the at least one bucket of the burst-mode token bucket set does not meet the second threshold criterion, reject the work request.

2. The system as recited in claim 1, wherein the one or more computing devices are further configured to:

assign a provisioned throughput capacity to the work target, indicative of a maximum rate of work operations to be performed at the work target during a normal mode of operation;

refill the normal-mode token bucket at a rate based at least in part on the provisioned throughput capacity; and

refill at least one bucket of the burst-mode token bucket set at another rate based at least in part on the provisioned throughput capacity.

3. The system as recited in claim 1, wherein the one or more computing devices are further configured to:

in response to a determination that, at the end of a particular time period in which an average rate at which work requests were received was less than a provisioned rate designated for the work target, one or more work tokens remain in the normal-mode token bucket, increase the token population of at least one bucket of the burst-mode token bucket set by an amount based at least in part on the number of work tokens that remain in the normal-mode token bucket.

4. The system as recited in claim 1, wherein the burst-mode bucket set comprises a local-burst-limit token bucket whose maximum token population is indicative of a maximum burst rate supported for work operations at the work target, and a shared-resource token bucket whose token population is indicative of an available throughput capacity of a resource shared by a plurality of work objects, wherein, in response to said determination that the token population of the normal-mode token bucket does not meet the first threshold criterion, the one or more computing devices are further configured to:

accept the work request for execution in response to determining that the token population of the local-burst-limit token bucket exceeds zero and the token population of the shared-resource token bucket exceeds zero.

5. The system as recited in claim 1, the one or more computing devices are further configured to:

generate, prior to the acceptance of the work request for execution, an estimate of an amount of work to be performed in response to the work request;

determine, subsequent to the acceptance of the work request, the amount of work performed corresponding to the work request; and

in response to a determination of a difference between the amount of work performed and an estimate, modify, based at least in part on the difference, the token population of at least one bucket of one or more of;

(a) the burst-mode token bucket set or (b) the burst-mode token bucket set.

6. A method, comprising:

performing, by one or more computing devices;

assigning a provisioned throughput capacity to a work target, indicative of a maximum rate of work operations to be performed at the work target during a normal mode of operation;

receiving a work request directed to the work target;

determining a token population of a normal-mode token bucket associated with the work target;

in response to determining that the token population of the normal-mode token bucket meets a first threshold criterion,

determining that the token population of at least one bucket of a burst-mode token bucket set associated with the work target meets a second threshold criterion,

accepting the work request for execution; and

modifying the token population of at least one bucket of the burst-mode token bucket set based at least in part on a burst-mode token consumption policy;

refilling the normal-mode token bucket at a rate based at least in part on the provisioned throughput capacity; and

refilling at least one bucket of the burst-mode token bucket set at a different rate based at least in part on the provisioned throughput capacity.

7. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

in response to determining that, at the end of a particular time period in which the work target operated in normal mode, one or more work tokens remain in the normal-mode token bucket, increasing the token population of at least one bucket of the burst-mode token bucket set by an amount based at least in part on the number of work tokens that remain in the normal-mode token bucket.

8. The method as recited in claim 6, wherein the burst mode bucket set comprises a local-burst-limit token bucket whose maximum token population is indicative of a maximum burst rate supported for work operations at the work target, and a shared-resource token bucket whose token population is indicative of an available throughput capacity of a resource shared by a plurality of work objects, wherein, in response to said determining that the token population of the normal-mode token bucket meets a first threshold criterion, the method further comprises performing, by the one or more computing devices:

accepting the work request for execution in response to determining that the token population of the local-burst-limit token bucket exceeds zero and the token population of the shared-resource token bucket exceeds zero.

9. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

generating, prior to accepting the work request for execution, an estimate of an amount of work to be performed in response to the work request;

determining, after said initiating, the amount of work performed corresponding to the work request; and

in response to determining a difference between the amount of work and the estimate, modifying, based at least in part on the difference, the token population of at least one bucket of one or more of;

(a) the burst-mode token bucket set or (b) the burst-mode token bucket set.

10. The method as recited in claim 6, wherein the work target comprises at least a portion of a storage object, wherein the work request comprises at least one of (a) a read operation or (b) a write operation.

11. The method as recited in claim 6, wherein the burst-mode bucket set comprises a read-burst token bucket used for admission control for work requests comprising read operations, and a write-burst token bucket used for admission control for work requests comprising write operations.

12. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

monitoring a work request arrival rate over a time period; and

modifying a maximum token population limit of at least one bucket of the burst-mode token bucket set based at least in part on a result of monitoring the work request arrival rate.

13. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

providing, to a client, an indication of a pricing policy associated with burst-mode operations at the work target; and

modifying a maximum token population limit of at least one bucket of the burst-mode token bucket set based at least in part on a burst-mode capacity increase request received from a client in accordance with the pricing policy.

14. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

assign a provisioned throughput capacity to a work target, indicative of a maximum rate of work operations to be performed at the work target during a normal mode of operation;

receive a work request directed to the work target;

in response to a determination, based at least in part on a first threshold criterion, that the work target is in a burst mode of operation,

determine that the token population of at least one bucket of a burst-mode token bucket set associated with the work target meets a second threshold criterion; and

accept the work request for execution;

refill a normal-mode token bucket associated with the work target at a rate based at least in part on the provisioned throughput capacity, wherein the first threshold criterion is based at least in part on a token population of the normal-mode token bucket and

refill at least one bucket of the burst-mode token bucket set at another rate based at least on the provisioned throughput capacity.

15. The non-transitory computer-accessible storage medium as recited in claim 14, wherein the instructions when executed on the one or more processors:

in response to a determination that, at the end of a particular time period, one or more work tokens remain in a normal-mode token bucket associated with the work target, increase the token population of at least one bucket of the burst-mode token bucket set by an amount based at least in part on the number of work tokens that remain in the normal-mode token bucket.

16. The non-transitory computer-accessible storage medium as recited in claim 14, wherein the burst mode bucket set comprises a local-burst-limit token bucket whose maximum token population is indicative of a maximum burst rate supported for work operations at the work target, and a shared-resource token bucket whose token population is indicative of an available throughput capacity of a resource shared by a plurality of work objects, wherein, in response to a determination that the first threshold criterion has been met, the instructions when executed on the one or more processors:

accept the work request for execution in response to determining that the token population of the local-burst-limit token bucket exceeds zero and the token population of the shared-resource token bucket exceeds zero.

17. The non-transitory computer-accessible storage medium as recited in claim 14, wherein the instructions when executed on the one or more processors:

in response to the determination that the token population of the at least one bucket of the burst-mode token bucket set meets the second threshold criterion, consume at least one token from the at least one bucket in accordance with a token consumption policy.

18. The non-transitory computer-accessible storage medium as recited in claim 14, wherein the work target comprises at least a portion of a partition of a database table, wherein the work request comprises at least one of (a) a read operation or (b) a write operation.