Equitable distribution of excess shared-resource throughput capacity

• US 9,917,782 B2
• Filed: 01/23/2017
• Issued: 03/13/2018
• 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:
  US15/413,325
• Publication Number:
  US 20170134289A1
• Time in Patent Office: 414 Days
• Field of Search: 709224, 707639, 705 2, 370230, 370252
• 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 method, comprising:

determining a first rate of operations directed to a first object, and a second rate of operations directed to a second object, wherein the first object has a first provisioned throughput and the second object has a second provisioned throughput, and wherein at least one operation directed to the first object comprises a use of a first resource shared by the first object and the second object;

identifying, based at least in part on (a) a throughput constraint of the first resource, (b) the respective rates of operations directed to the first and second objects, and (c) the respective provisioned throughputs, a first throughput limit for the first object, and a second throughput limit for the second object; and

determining, based at least in part on the first throughput limit, whether a request for an operation directed to the first object is to be accepted.

2. The method as recited in claim 1, further comprising:

establishing at least a first token bucket to represent throughput capacity of the first object, and at least a second token bucket to represent throughput capacity of the second object;

populating the first token bucket based at least in part on the first throughput limit; and

populating the second token bucket based at least in part on the second throughput limit.

3. The method as recited in claim 2, wherein the program instructions, if executed, cause the one or more processors to:

determining a combined number of tokens to be distributed among the first token bucket and the second token bucket based at least in part on the throughput constraint of the first resource.

4. The method as recited in claim 3, wherein said determining the combined number of tokens comprises subtracting, from the throughput constraint of the first resource, the sum of the first and second provisioned throughputs.

5. The method as recited in claim 2, further comprising:

establishing a first plurality of token buckets, including the first token bucket and a second token bucket, to represent throughput capacity of the first object, wherein the first token bucket is examined for admission control of requested operations during a first mode of operation in which a request arrival rate of operations directed at the first object exceeds a threshold, and wherein the second token bucket is examined for admission control of requested operations during a second mode of operation in which a request arrival rate of operations directed at the first object does not exceed the threshold.

6. The method as recited in claim 1, further comprising:

obtaining one or more metrics associated with the first object; and

modifying, based at least in part on the one or more metrics, a function used to determine the first throughput limit.

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

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

9. The method as recited in claim 1, wherein the first resource comprises a data structure.

10. The method as recited in claim 1, wherein the requested operation directed to the first object comprises one or more of:

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

11. A system, comprising:

memory storing program instructions that, if executed, cause one or more processors to;

determine a first rate of operations directed to a first object, and a second rate of operations directed to a second object, wherein the first object has a first provisioned throughput and the second object has a second provisioned throughput, and wherein at least one operation directed to the first object comprises a use of a first resource shared by the first object and the second object;

identify, based at least in part on (a) a throughput constraint of the first resource, (b) the respective rates of operations directed to the first and second objects, and (c) the respective provisioned throughputs, a first throughput limit for the first object, and a second throughput limit for the second object; and

determine, based at least in part on the first throughput limit, whether a request for an operation directed to the first object is to be accepted.

12. The system as recited in claim 11, wherein the program instructions, if executed, cause the one or more processors to:

establish at least a first token bucket to represent throughput capacity of the first object, and at least a second token bucket to represent throughput capacity of the second object;

populate the first token bucket based at least in part on the first throughput limit; and

populate the second token bucket based at least in part on the second throughput limit.

13. The system as recited in claim 12, wherein the program instructions, if executed, cause the one or more processors to:

determine a combined number of tokens to be distributed among the first token bucket and the second token bucket based at least in part on the throughput constraint of the first resource.

14. The system as recited in claim 13, wherein the combined number of tokens is determined at least in part by subtracting, from the throughput constraint of the first resource, the sum of the first and second provisioned throughputs.

15. The system as recited in claim 11, wherein the first resource comprises a network device.

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors cause the one or more processors to perform a method comprising:

determining a first rate of operations directed to a first object, and a second rate of operations directed to a second object, wherein the first object has a first provisioned throughput and the second object has a second provisioned throughput, and wherein at least one operation directed to the first object comprises a use of a first resource shared by the first object and the second object;

identifying, based at least in part on (a) a throughput constraint of the first resource, (b) the respective rates of operations directed to the first and second objects, and (c) the respective provisioned throughputs, a first throughput limit for the first object, and a second throughput limit for the second object; and

determining, based at least in part on the first throughput limit, whether a request for an operation directed to the first object is to be accepted.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the method further comprises:

establishing at least a first token bucket to represent throughput capacity of the first object, and at least a second token bucket to represent throughput capacity of the second object;

populating the first token bucket based at least in part on the first throughput limit; and

populating the second token bucket based at least in part on the second throughput limit.

18. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the method further comprises:

determining a combined number of tokens to be distributed among the first token bucket and the second token bucket based at least in part on the throughput constraint of the first resource.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the method comprises:

collecting one or more metrics comprising results of monitoring the first object; and

modifying, based at least in part on the one or more metrics, a function used to determine the first throughput limit.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the wherein the first resource comprises a processor.