Compound token buckets for burst-mode admission control

• US 9,385,956 B2
• Filed: 06/25/2013
• Issued: 07/05/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, Stefani, Stefano, Hamilton, James R.
• Primary Examiner(s): Renner, Brandon
• Assistant Examiner(s): Preval, Voster
• Application Number:
  US13/926,697
• Publication Number:
  US 20140376368A1
• Time in Patent Office: 1,106 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion

Abstract

Methods and apparatus for compound token buckets usable for burst-mode admission control are disclosed. A peak burst rate and a sustained burst rate of work requests that are to be supported at a work target are determined. The maximum token populations of a peak-burst token bucket and a sustained-burst token bucket are configured, based on the peak burst rate and the sustained burst rate respectively. In response to receiving a work request directed at the work target, a determination to accept the work request for execution is made based at least in part on the token population of the peak-burst token bucket and/or the sustained-burst token bucket.

Claims

1. A system, comprising:

one or more computing devices configured to;

determine a peak burst rate at which work requests directed to a work target are to be accepted for execution during a burst mode of operation, and a peak burst window size indicative of a maximum duration for which work requests at the peak burst rate are to be accepted;

determine a sustained burst rate smaller than the peak burst rate, and a sustained burst window size greater than the peak burst window size, wherein the sustained burst window size is indicative of a maximum duration for which work requests directed to the work target at the sustained burst rate are to be accepted during the burst mode of operation;

configure a first maximum token population, a first initial token population, and a first token consumption policy for a peak-burst token bucket to be used for admission control of work requests directed at the work target, wherein the first maximum token population is based at least in part on the peak burst rate;

configure a second maximum token population, a second initial token population, and a second token consumption policy for a sustained-burst token bucket to be used for admission control of work requests directed at the work target, wherein the second maximum token population is based at least in part on the sustained burst rate; and

in response to receiving a work request directed at the work target during a burst mode of operation, determine to accept the work request for execution based at least in part on the respective token populations of the peak-burst token bucket and the sustained-burst token bucket.

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

in response to a determination to accept the work request for execution, consume at least one token from the peak-burst token bucket in accordance with the first token consumption policy, and consume at least one token from the sustained-burst token bucket in accordance with the second token consumption policy.

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

in response to receiving a particular work request directed at the work target, determine whether the work target is in a burst mode of operation based at least in part on a token population of a provisioned-capacity token bucket.

4. The system as recited in claim 1, wherein said peak burst rate is based at least in part on a provisioned throughput capacity of the work target, and wherein said sustained burst rate is based at least in part on the provisioned throughput capacity.

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

determine a first refill rate for the peak-burst token bucket based at least in part on a provisioned throughput capacity of the work target; and

determine a second refill rate for the sustained-burst token bucket based at least in part on a provisioned throughput capacity of the work target.

6. A method, comprising:

performing, by one or more computing devices;

determining a peak burst rate at which work requests directed to a work target are to be accepted during a burst mode of operation;

determining a sustained burst rate at which work requests directed to the work target are to be accepted for up to a particular duration during the burst mode of operation;

configuring a first maximum token population for a peak-burst token bucket to be used for admission control of work requests directed at the work target, and a second maximum token population for a sustained-burst token bucket to be used for admission control of work requests directed at the work target, wherein the first maximum token population is based at least in part on the peak burst rate and the second maximum token population is based at least in part on the sustained burst rate,

wherein the first token maximum token population is based at least in part on a peak burst time window indicative of a maximum duration for which the work requests directed to the work target are to be accepted for execution by the work target at the peak burst rate, and

wherein the second maximum token population is based at least in part on a sustained burst time window indicative of the particular duration; and

in response to receiving a work request directed at the work target during a burst mode of operation, determining to accept the work request for execution based at least in part on a token population of at least one of;

the peak-burst token bucket and the sustained-burst token bucket.

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

in response to determining to accept the work request for execution, consuming at least one token from the peak-burst token bucket, and consuming at least one token from the sustained-burst token bucket.

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

in response to receiving a particular work request directed at the work target, determining whether the work target is in a burst mode of operation based at least in part on a token population of a provisioned-capacity token bucket.

9. The method as recited in claim 6, wherein the peak burst rate is based at least in part on a provisioned throughput capacity of the work target, and wherein the sustained burst rate is based at least in part on the provisioned throughput capacity.

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

determining a first refill rate for the peak-burst token bucket based at least in part on a provisioned throughput capacity of the work target; and

determining a different refill rate for the sustained-burst token bucket based at least in part on a provisioned throughput capacity of the work target.

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

in response to receiving the work request directed at the work target during the burst mode of operation, determining to accept the work request for execution based at least in part on a token population of a shared-resource token bucket representing available throughput capacity at a resource shared by a plurality of work targets.

12. 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 a request for at least one of:

(a) a read operation on the storage object and (b) a write operation on the storage object.

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

determine a peak burst rate at which work requests directed to a work target are to be accepted;

determine a sustained burst rate at which work requests directed to the work target are to be accepted for up to a particular duration;

configure a first maximum token population for a peak-burst token bucket to be used for admission control of work requests directed at the work target and a second maximum token population for a sustained-burst token bucket to be used for admission control of work requests directed at the work target, wherein the first maximum token population is based at least in part on the peak burst rate and the second maximum token population is based at least in part on the sustained burst rate,

wherein the first token maximum token population is based at least in part on a peak burst time window indicative of a maximum duration for which the work requests directed to the work target are to be accepted for execution by the work target at the peak burst rate, and

wherein the second maximum token population is based at least in part on a sustained burst time window indicative of the particular duration; and

in response to receiving a work request directed at the work target, determine to accept the work request for execution based at least in part on a token population of at least one of;

the peak-burst token bucket and the sustained-burst token bucket.

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

determine a peak burst time window indicative of a maximum duration for which work requests at the peak burst rate are to be accepted for execution;

wherein said first maximum token population is based at least in part on the peak burst time window.

15. The non-transitory computer-accessible storage medium as recited in claim 13, wherein said second maximum token population is based at least in part on a sustained burst time window indicative of the particular duration.

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

in response to a determination to accept the work request for execution, consume at least one token from the peak-burst token bucket, and consume at least one token from the sustained-burst token bucket.

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

in response to receiving a particular work request directed at the work target, determine, based at least in part on a token population of a provisioned-capacity token bucket associated with the work target, whether an admission control decision for the particular work request is to be based on the token population of one or more of;

(a) the peak-burst token bucket and (b) the sustained-burst token bucket.

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

determine a first refill rate for the peak-burst token bucket based at least in part on a provisioned throughput capacity of the work target; and

determine a second refill rate for the sustained-burst token bucket based at least in part on a provisioned throughput capacity of the work target.