Token sharing mechanisms for burst-mode operations

• US 9,218,221 B2
• Filed: 06/25/2013
• Issued: 12/22/2015
• 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, Filipe, Miguel Mascarenhas, Hamilton, James R., Lu, Yijun, Stefani, Stefano, Marshall, Stuart Henry Seelye, Swift, Bjorn Patrick, Muniswamy-Reddy, Kiran-Kumar
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US13/926,708
• Publication Number:
  US 20140380330A1
• Time in Patent Office: 910 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/5016 the resource being the memory
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Methods and apparatus for token-sharing mechanisms for burst-mode operations are disclosed. A first and a second token bucket are respectively configured for admission control at a first and a second work target. A number of tokens to be transferred between the first bucket and the second bucket, as well as the direction of the transfer, are determined, for example based on messages exchanged between the work targets. The token transfer is initiated, and admission control decisions at the work targets are made based on the token population resulting from the transfer.

Claims

1. A system, comprising:

one or more computing devices configured to;

configure a plurality of work targets with respective sets of token buckets for admission control of work requests, including a first work target with a first set of token buckets, wherein a decision to accept a work request for execution at the first work target is to be based at least in part on a token population of one or more token buckets of the first set;

in response to a determination that a token sharing evaluation criterion has been met at the first work target,

identify a second work target of the plurality of work targets with which to exchange token population information from the first work target, wherein the second work target is configured with a second set of token buckets;

determine, based at least in part on an analysis of respective token populations of a first bucket in the first set and a second bucket in the second set, whether to initiate a token transfer between the first and second buckets; and

in response to a determination to initiate a token transfer,

increase the token population of one bucket of the first and second buckets by a particular number of tokens, and decrease the token population of another bucket of the first and second buckets by the particular number of tokens, in accordance with a transfer direction identified for the token transfer; and

in response to receiving a work request directed to the first work target, accept the work request for execution based at least in part on the changed token population of the first bucket.

2. The system as recited in claim 1, wherein the plurality of work targets comprise a first collection of one or more storage objects created at a network-accessible storage service on behalf of a first client, and a second collection of one or more storage objects created at the network-accessible storage service on behalf of a second client, wherein the first work target comprises at least a portion of a storage object of the first collection, and wherein, to identify the second work target, the one or more computing devices are configured to select the second work target from the first collection.

3. The system as recited in claim 1, wherein the first work target comprises at least a portion of a base database table instantiated on behalf of a particular client of a network-accessible database service, and the second work target comprises at least a portion of a derived database table instantiated at the network-accessible database service to implement a secondary index on the base database table.

4. The system as recited in claim 1, wherein the first set of token buckets comprises a normal-mode bucket used for admission control during a normal mode of operation of the first work target, and one or more burst-mode token buckets used for admission control during a burst mode of operation at the first work target, wherein the one or more burst-mode token buckets include the first bucket.

5. The system as recited in claim 1, wherein the second work target is selected from among the plurality of work targets using a random selection policy in accordance with a gossip protocol.

6. A method, comprising:

performing, by one or more computing devices;

configuring a plurality of work targets with respective token bucket sets for admission control of work requests, including a first work target with a first token bucket set, wherein a decision to accept a work request for execution at the first work target is to be based at least in part on a token population of one or more token buckets of the first token bucket set;

in response to determining that a token sharing evaluation criterion has been met at the first work target,

initiating a token transfer in a particular direction between a first bucket of the first token bucket set and a second bucket of a second token bucket set associated with a second work target of the plurality of work targets; and

accepting, in response to receiving a work request directed to the first work target, the work request for execution based at least in part on the token population of the first bucket subsequent to the token transfer.

7. The method as recited in claim 6, wherein the plurality of work targets comprise a first collection of one or more storage objects created at a network-accessible storage service on behalf of a first client, and a second collection of one or more storage objects created at the network-accessible storage service on behalf of a second client, wherein the first work target comprises at least a portion of a storage object of the first collection, further comprising performing, by the one or more computing devices:

selecting the second work target from the first collection.

8. The method as recited in claim 6, wherein the first work target comprises at least a portion of a base database table instantiated on behalf of a particular client of a network-accessible database service, and the second work target comprises at least a portion of a derived database table instantiated at the network-accessible database service to implement a secondary index on the base database table.

9. The method as recited in claim 6, wherein the first token bucket set comprises a normal-mode bucket used for admission control during a normal mode of operation of the first work target, and one or more burst-mode token buckets used for admission control during a burst mode of operation at the first work target, wherein the one or more burst-mode token buckets include the first bucket.

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

selecting the second work target using a random selection policy.

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

selecting the second work target in accordance with a gossip protocol.

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

determining whether the token sharing evaluation criterion has been met based at least in part on one or more of (a) an amount of time since a previous evaluation was initiated at the first work target, (b) an indication that the token population of the first token bucket has fallen below a first threshold value, (c) an indication that the token population of the first token bucket has risen above a second threshold value, or (d) an indication that a rate of rejection of work requests at the first work target is above a particular threshold value.

13. The method as recited in claim 6, wherein the first work target comprises a first replica of a plurality of replicas of a first logical partition of a storage object, wherein each replica of the plurality of replicas is assigned a role comprising one of (a) a master role and (b) a slave role, wherein admission control for a work request that includes a write operation directed to the first logical partition is performed at the replica to which the master role is assigned, wherein the first replica is assigned a first role with respect to the first logical partition, further comprising, performing by the one or more computing devices:

selecting a particular replica of a second logical partition of the storage object as the second work target, wherein the particular replica is assigned the same role with respect to the second logical partition as the role of the first replica with respect to the first logical partition.

14. The method as recited in claim 6, wherein said initiating the token transfer in the particular direction between the first bucket and the second bucket is based at least in part on a determination that, within a particular time window, no other token transfer between the first work target and the second work target was implemented.

15. The method as recited in claim 6, wherein the particular direction is from the token bucket with the greater token population among the first and second buckets, to the token bucket with the smaller token population among the first and second buckets, wherein the method comprises performing, by the one or more computing devices:

determining a number of tokens to be transferred as a function of the difference between the greater and smaller token populations.

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

determine a number of tokens to be transferred between a first bucket in a first token bucket set and a second bucket in a second token bucket set, wherein the first token bucket set is used for admission control of work requests directed at a first work target of a plurality of work targets, and wherein the second token bucket set is used for admission control at a second work target of the plurality of work targets;

initiate a transfer of the number of tokens in a particular direction between the first bucket and the second bucket; and

accept, in response to receiving a work request directed to the first work target, the work request for execution based at least in part on the token population of the first bucket subsequent to the transfer.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the plurality of work targets comprise a first collection of one or more storage objects created at a network-accessible storage service on behalf of a first client, and a second collection of one or more storage objects created at the network-accessible storage service on behalf of a second client, wherein the first work target comprises at least a portion of a storage object of the first collection, and wherein the instructions when executed at the one or more processors:

select the second work target from the first collection.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first work target comprises at least a portion of a base database table instantiated on behalf of a particular client of a network-accessible database service, and the second work target comprises at least a portion of a derived database table instantiated at the network-accessible database service to implement a secondary index on the base database table.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first token bucket set comprises a normal-mode bucket used for admission control during a normal mode of operation of the first work target, and one or more burst-mode token buckets used for admission control during a burst mode of operation at the first work target, wherein the one or more burst-mode token buckets include the first bucket.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the second work target is selected from among the plurality of work targets using a random selection policy in accordance with a gossip protocol.