Equitable distribution of excess shared-resource throughput capacity

• US 9,553,821 B2
• Filed: 06/25/2013
• Issued: 01/24/2017
• 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): Nguyen, Quang N
• Application Number:
  US13/926,684
• Publication Number:
  US 20140379922A1
• Time in Patent Office: 1,309 Days
• Field of Search: 709/224, 709/203, 709/217, 709/219, 709/223, 709/226, 709/228, 709/232, 370/230, 370/235.1
• US Class Current: 1/1
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/80 Actions related to the user profile or the type of traffic

Abstract

Methods and apparatus for equitable distribution of excess shared-resource throughput capacity are disclosed. A first and a second work target are configured to access a shared resource to implement accepted work requests. Admission control is managed at the work targets using respective token buckets. A first metric indicative of the work request arrival rates at the work targets during a time interval, and a second metric associated with the provisioned capacities of the work targets are determined. A number of tokens determined based on a throughput limit of the shared resource is distributed among the work targets to be used for admission control during a subsequent time interval. The number of tokens distributed to each work target is based on the first metric and/or the second metric.

Claims

1. A system, comprising:

one or more computing devices comprising one or more hardware processors and memory and configured to;

configure a first work target and a second work target to utilize a shared resource in response to work requests accepted for execution, wherein the first work target has a first provisioned throughput rate, the second work target has a second provisioned throughput rate, and the shared resource has a throughput limit;

configure the first work target and the second work target with respective token bucket sets for admission control of work requests, wherein each token bucket set comprises one or more buckets whose token population is used to determine whether to accept a work request for execution;

determine (a) an arrival rate ratio indicative of relative rates at which work requests are received at the first and second work targets during a first time interval, (b) a provisioned throughput ratio based at least in part on the first and second provisioned throughput rates, and (c) a combined number of tokens to be distributed among the bucket sets of the first and second work targets for admission control during a second time interval, wherein the combined number is based at least in part on the throughput limit of the shared resource;

add a particular number of tokens, no greater than the combined number, to a particular bucket of the first work target based at least in part on the arrival rate ratio and the provisioned throughput ratio; and

accept a particular work request directed to the first work target for execution during the second time interval based at least in part on the token population of the particular bucket of the first work target.

2. The system as recited in claim 1, wherein the combined number of tokens is determined at least in part by subtracting, from the throughput limit of the shared resource, the sum of the first and second provisioned throughput rates.

3. The system as recited in claim 1, wherein the bucket set of the first work target comprises a normal-mode bucket whose token population is examined for admission control during a normal mode of operation in which the work request arrival rate is less than a threshold, and a burst-mode bucket whose token population is examined for admission control during a burst mode of operation in which the work request arrival rate is not less than the threshold, and wherein the particular bucket comprises the burst-mode bucket.

4. The system as recited in claim 1, wherein the first work target comprises at least a portion of a first storage object managed by a network-accessible service, wherein the second work target comprises at least a portion of a second storage object managed by the network-accessible service, and wherein the shared resource comprises a storage device at which the first work target and the second work target are stored.

5. The system as recited in claim 1, wherein the particular work request comprises one or more of:

(a) a read operation, or (b) a write operation.

6. A method, comprising:

performing, by one or more computing devices;

configuring a first work target and a second work target to utilize a shared resource in response to work requests accepted for execution, wherein the first work target has a first provisioned throughput rate, and the second work target has a second provisioned throughput rate;

configuring the first work target and the second work target with respective token bucket sets for admission control of work requests, wherein each token bucket set comprises one or more buckets whose token population is used to determine whether to accept a work request for execution;

determining (a) a first metric indicative of work request arrival rates at the first and second work targets during a first time interval, and (b) a second metric associated with the first and second provisioned throughput rates;

adding a particular number of tokens to a particular bucket of the first work target based at least in part on the first metric, the second metric, and a throughput limit of the shared resource; and

accepting a particular work request directed to the first work target for execution during a second time interval based at least in part on the token population of the particular bucket of the first work target.

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

determining a combined number of tokens to be distributed among the bucket sets of the first and second work targets based at least in part on the throughput limit of the shared resource, wherein the particular number of tokens is no greater than the combined number.

8. The method as recited in claim 7, wherein the combined number of tokens is determined at least in part by subtracting, from the throughput limit of the shared resource, the sum of the first and second provisioned throughput rates.

9. The method as recited in claim 6, wherein the bucket set of the first work target comprises a normal-mode bucket whose token population is examined for admission control during a normal mode of operation in which the work request arrival rate is less than a threshold, and a burst-mode bucket whose token population is examined for admission control during a burst mode of operation in which the work request arrival rate is not less than the threshold, and wherein the particular bucket comprises the burst-mode bucket.

10. The method as recited in claim 6, wherein the first work target comprises at least a portion of a first storage object managed by a network-accessible service, wherein the second work target comprises at least a portion of a second storage object managed by the network-accessible service, and wherein the shared resource comprises a storage device at which the first work target and the second work target are stored.

11. The method as recited in claim 6, wherein the first work target comprises at least a portion of a first table partition managed by a network-accessible multi-tenant database service, and wherein the second work target comprises at least a portion of a second table managed by the network-accessible multi-tenant database service.

12. The method as recited in claim 6, wherein the shared resource comprises a data structure of a software module.

13. The method as recited in claim 6, wherein the particular work request comprises one or more of:

(a) a read operation, or (b) a write operation.

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

determining the particular number of tokens based at least in part on a particular function of the first metric, the second metric, and the throughput limit;

monitoring one or more additional metrics associated with the first and second work targets; and

modifying the particular function based at least in part on the one or more additional metrics.

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

configure a first work target and a second work target to utilize a shared resource in response to work requests accepted for execution, wherein the first work target has a first provisioned throughput rate, and the second work target has a second provisioned throughput rate;

configure the first work target and the second work target with respective token bucket sets for admission control of work requests, wherein each token bucket set comprises one or more buckets whose token population is used to determine whether to accept a work request for execution;

determine (a) a first metric indicative of work request arrival rates at the first and second work targets during a first time interval, and (b) a second metric associated with the first and second provisioned throughput rates;

add a particular number of tokens to a particular bucket of the first work target based at least in part on the first metric, the second metric, and a throughput limit of the shared resource; and

accept a particular work request directed to the first work target for execution during a second time interval based at least in part on the token population of the particular bucket of the first work target.

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

determine a combined number of tokens to be distributed among the bucket sets of the first and second work targets based at least in part on the throughput limit of the shared resource, wherein the particular number of tokens is no greater than the combined number.

17. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the bucket set of the first work target comprises a normal-mode bucket whose token population is examined for admission control during a normal mode of operation in which the work request arrival rate is less than a threshold, and a burst-mode bucket whose token population is examined for admission control during a burst mode of operation in which the work request arrival rate is not less than the threshold, and wherein the particular bucket comprises the burst-mode bucket.

18. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the first work target comprises at least a portion of a first storage object managed by a network-accessible service, wherein the second work target comprises at least a portion of a second storage object managed by the network-accessible service, and wherein the shared resource comprises a storage device at which the first work target and the second work target are stored.

19. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the shared resource comprises a logical resource implemented in an operating system.

20. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the particular work request comprises one or more of:

(a) a read operation, or (b) a write operation.