TOKEN-BASED ADMISSION CONTROL FOR REPLICATED WRITES

• US 20140279905A1
• Filed: 03/13/2013
• Published: 09/18/2014
• Est. Priority Date: 03/13/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: RATH, TIMOTHY ANDREW, STEFANI, STEFANO, XIAO, WEI, HAMILTON, JAMES R., MUNISWAMY-REDDY, KIRAN-KUMAR, SWIFT, BJORN PATRICK, FILIPE, MIGUEL MASCARENHAS, LU, YIJUN, MARSHALL, STUART HENRY SEELYE
• Granted Patent: US 11,086,898 B2
• Time in Patent Office: Days
• US Class Current: 707/639
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Methods and apparatus for token-based admission control for replicated writes are disclosed. Data objects are divided into partitions, and corresponding to each partition, at least a master replica and a slave replica are stored. A determination as to whether to accept a write request directed to the partition is made based at least in part on one or more of (a) available throughput capacity at the master replica, and (b) an indication, obtained using a token-based protocol, of available throughput capacity at the slave replica. If the write request is accepted, one or more data modification operations are initiated.

Claims

1. A method, comprising:

storing, corresponding to a logical partition of a data object comprising one or more logical partitions, a master replica of the logical partition and one or more slave replicas of the logical partition, wherein writes to the logical partition are replicated at the master replica and at least one slave replica in accordance with a replication policy;

storing, corresponding to the master replica, a master bucket set comprising one or more buckets, and a slave-snapshot bucket set comprising one or more buckets, wherein each bucket of the master bucket set and the slave-snapshot bucket set (a) comprises a respective refillable collection of tokens usable to limit throughput of operations directed at the logical partition and (b) has a token consumption policy indicating a number of tokens to be consumed for an allowed operation;

updating a token population of a particular bucket of the slave-snapshot bucket set based at least in part on a slave bucket update protocol, wherein, in accordance with the slave bucket update protocol, the master replica is configured to obtain an indication of an available throughput capacity at a shared storage device at which at least a portion of data of a particular slave replica of the one or more slave replicas is stored, wherein the shared storage device is configurable to store data corresponding to one or more logical partitions of one or more data objects;

in response to receiving a write request directed to the logical partition,

determining whether the write request is to be accepted for execution based at least in part on whether a sufficient number of tokens is available in at least one bucket set of the master bucket set and the slave-snapshot bucket set, in accordance with respective token consumption policies of the buckets of the master bucket set and the slave-snapshot bucket set; and

in response to determining that the write request is to be accepted for execution, initiating one or more data modification operations corresponding to the write request.

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

determining, based at least in part on a token population of a particular bucket of the master bucket set, whether the logical partition is in a burst mode of operation; and

in response to determining that the logical partition is in a burst mode of operation, determining whether the write request is to be accepted for execution based at least in part on whether a sufficient number of tokens is available in (a) the master bucket set and (b) the slave-snapshot bucket set.

3. The method as recited in claim 1, wherein the one or more slave replicas comprise the particular slave replica and a second slave replica, further comprising:

storing, corresponding to the particular slave replica, a first shared-device bucket whose token population is indicative of available throughput capacity at the shared storage device;

storing, corresponding to the second slave replica, a second shared-device bucket whose token population is indicative of available throughput capacity at a second shared storage device at which at least a portion of data of the second slave replica is stored, wherein the second shared storage device is configurable to store data corresponding to one or more logical partitions of one or more data objects;

and wherein implementing said slave bucket update protocol comprises the master replica obtaining respective point-in-time snapshots of the (a) the token population of the first shared-device bucket and (b) the token population of the second shared-device bucket.

4. The method as recited in claim 3, wherein the slave-snapshot bucket set comprises a common proxy bucket, wherein implementing said slave bucket update protocol comprises:

determining, based at least in part on the respective point-in-time snapshots, an estimate of the minimum of the token populations among the token populations of the first and second shared-device buckets; and

updating the token population of the common proxy bucket based at least in part on the estimate;

and wherein, in accordance with a token consumption policy associated with the common proxy bucket, the method further comprises;

accepting the write request for execution based on a determination that the common proxy bucket comprises at least one token and that at least one bucket of the master bucket set comprises at least one token.

5. The method as recited in claim 3, wherein the slave-snapshot bucket set comprises a first snapshot bucket corresponding to the particular slave replica and a second snapshot bucket corresponding to the second slave replica, wherein implementing said slave bucket update protocol comprises:

updating the token population of the first snapshot bucket based on a point-in-time indication of the token population of the first shared-device bucket;

updating the token population of the second snapshot bucket based on a point-in-time indication of the token population of the second shared-device bucket;

and wherein the method further comprises;

accepting the write request for execution based on a determination that the first snapshot bucket comprises at least one token, the second snapshot bucket comprises at least one token, and at least one bucket of the master bucket set comprises at least one token.

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

transmitting, from the master replica to the particular slave replica, a write replication request corresponding to the write request; and

receiving, at the master replica, an acknowledgment of the write replication request, wherein the acknowledgment comprises, in accordance with the slave bucket update protocol, an indication of the available throughput capacity at the shared storage device.

7. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform;

storing, corresponding to a master replica of a logical partition of one or more logical partitions of a data object, a master bucket set comprising one or more buckets and a slave-snapshot bucket set comprising one or more buckets, wherein each bucket of the master bucket set and the slave-snapshot bucket set comprises a respective collection of tokens usable to limit throughput of write operations directed at the logical partition;

updating a token population of a particular bucket of the slave-snapshot bucket set based at least in part on an indication of an available throughput capacity at a shared storage device at which at least a portion of data of a particular slave replica of the logical partition is stored;

in response to receiving a write request directed to the logical partition,

determining whether the write request is to be accepted for execution based at least in part on whether a sufficient number of tokens is available in at least one bucket set of (a) the master bucket set and (b) the slave-snapshot bucket set in accordance with respective token consumption policies of the buckets of the master bucket set and the slave-snapshot bucket set; and

in response to determining that the write request is to be accepted for execution, initiating one or more data modification operations corresponding to the write request.

8. The system as recited in claim 7, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

storing a plurality of slave replicas of the logical partition, including the particular slave replica and a second slave replica;

storing, corresponding to the particular slave replica, a first shared-device bucket whose token population is indicative of available throughput capacity at the shared storage device;

storing, corresponding to the second slave replica, a second shared-device bucket whose token population is indicative of available throughput capacity at a second shared storage device at which at least a portion of data of the second slave replica is stored;

and wherein said updating the token population of the particular bucket is based at least in part on the master replica obtaining (a) a snapshot of the token population of the first shared-device bucket and (b) a snapshot of the token population of the second shared-device bucket.

9. The system as recited in claim 8, wherein the particular bucket comprises a common proxy bucket corresponding to the combination of at least the particular slave replica and the second slave replica, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

determining, based at least in part on obtaining a respective snapshot of the first and second shared-device buckets, an estimate of the minimum token population among the token populations of the first and second shared-device buckets;

updating a token population of the common proxy bucket based on the estimate; and

accepting the write request for execution based at least in part on an indication that the common proxy bucket comprises at least one token.

10. The system as recited in claim 8, wherein the slave-snapshot bucket set comprises a first snapshot bucket corresponding to the particular slave replica and a second snapshot bucket corresponding to the second slave replica, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

updating the token population of the first snapshot bucket based on an indication of the token population of the first shared-device bucket;

updating the token population of the second snapshot bucket based on an indication of the token population of the second shared-device bucket;

accepting the write request for execution based at least in part on a determination that the first snapshot bucket comprises at least one token and the second snapshot bucket comprises at least one token.

11. The system as recited in claim 7, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

transmitting, from the master replica to the particular slave replica, a replication request corresponding to the write request; and

receiving, at the master replica, an acknowledgment of the replication request, wherein the acknowledgment comprises an indication of the available throughput capacity at the shared storage device.

12. The system as recited in claim 7, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

receiving, at the master replica from the particular slave replica, a heartbeat message indicative of a health state of the particular slave replica, wherein the heartbeat message comprises an indication of the available throughput capacity at the shared storage device.

13. The system as recited in claim 7, wherein the master bucket set comprises a provisioned capacity bucket, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

configuring one or more parameters of the provisioned capacity bucket, including its initial token population and refill rate, based at least in part on an indication of a targeted throughput provided by a client authorized to access the data object; and

determining that the write request is to be accepted for execution based at least in part on a determination that the provisioned capacity bucket comprises at least one token.

14. The system as recited in claim 13, wherein the master bucket set comprises a burst-handling bucket, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

adding tokens to the burst-handling bucket, wherein the number of tokens added is based at least in part on a determination that a measured rate of operations directed to the logical partition is less than the targeted throughput during a particular time period; and

in response to (a) receiving a different write request and (b) determining that the provisioned capacity bucket does not contain tokens when the different write request is received, accepting the different write request for execution based at least in part on a determination that the burst-handling bucket comprises at least one token.

15. The system as recited in claim 7, wherein the master bucket set comprises a master shared-device bucket whose token population is based at least in part on available throughput capacity of a different shared storage device used to store at least a portion of the master replica'"'"'s data, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

accepting the write request for execution based at least in part on a determination that the master shared-device bucket comprises at least one token.

16. The system as recited in claim 7, wherein the master bucket set comprises a node capability bucket whose token population is based at least in part on a metric of a performance capability of a storage node at which at least a portion of the master replica'"'"'s data is stored, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

accepting the write request for execution based at least in part on a determination that the node capability bucket comprises at least one token.

17. The system as recited in claim 7, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

modifying, in accordance with a configuration request received via a programmatic interface, a property of an admission control policy;

in response to receiving a different write request directed to the logical partition, determining whether the different write request is to be accepted for execution based at least in part on the property.

18. 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:

storing, corresponding to a logical partition of a data object, a master replica and one or more slave replicas including a particular slave replica, wherein the master replica comprises data stored on a first storage device and the particular slave replica comprises data stored on a second storage device;

receiving a write request directed to at least a portion of the logical partition;

determining whether to accept the write request for execution based at least in part on one or more of (a) available throughput capacity at the master replica, and (b) an indication, obtained using a token-based protocol, of available throughput capacity at the particular slave replica;

in response to accepting the write request for execution, initiating one or more data modification operations corresponding to the write request.

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

storing, corresponding to the master replica, a master bucket set comprising one or more buckets and a slave-snapshot bucket set comprising one or more buckets, wherein each bucket of the master bucket set and the slave-snapshot bucket set comprises a respective collection of tokens;

updating a token population of at least a particular bucket of the master bucket set to represent available throughput capacity at the master replica;

updating a token population of at least a particular bucket of the slave-snapshot bucket set to represent available throughput capacity at the particular slave replica;

and wherein said determining whether to accept the write request for execution comprises;

in response to determining that the logical partition is in a burst mode of operation, examining the token population of the particular bucket of the master bucket set and the token population of the particular bucket of the slave-snapshot bucket set.

20. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the program instructions when executed on the one or more processors cause the one or more processors to perform:

in accordance with said accepting the write request for execution, consuming at least one token from the particular bucket of the master bucket set and at least one token from the particular bucket of the slave-snapshot bucket set.

21. The non-transitory computer-accessible storage medium as recited in claim 20, wherein the at least one token from the particular bucket of the master bucket set and the at least one token from the particular bucket of the slave-snapshot bucket set are consumed within an atomic operation.

22. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the program instructions when executed on the one or more processors cause the processors to perform:

storing a plurality of slave replicas of the logical partition, including the particular slave replica and a second slave replica;

storing, corresponding to the particular slave replica, a first shared-device bucket whose token population is indicative of available throughput capacity at the second storage device;

storing, corresponding to the second slave replica, a second shared-device bucket whose token population is indicative of available throughput capacity at a third storage device at which at least a portion of data of the second slave replica is stored;

and wherein said updating the token population of the particular bucket of the slave-snapshot bucket set is based at least in part on obtaining a respective snapshot of (a) the token population of the first shared-device bucket and (b) the token population of the second shared-device bucket.

23. The non-transitory computer-accessible storage medium as recited in claim 22, wherein the particular bucket of the slave-snapshot bucket set comprises a common proxy bucket, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

determining an estimate of the minimum token population among the token populations of the first and second shared-device buckets;

updating the population of the common proxy bucket based on the estimate; and

accepting the write request for execution based at least in part on determining that the common proxy bucket comprises at least one token.

24. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

transmitting, from the master replica to the particular slave replica, a replication request corresponding to the write request; and

receiving, at the master replica, an acknowledgment of the replication request, wherein the acknowledgment comprises the indication of the available throughput capacity at the particular slave replica.

25. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the program instructions when executed by the one or more processors cause the one or more processors to perform:

receiving, at the master replica from the particular slave replica, a heartbeat message indicative of a health state of the particular slave replica, wherein the heartbeat message comprises the indication of the available throughput capacity at the shared storage device.

26. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the data object comprises contents of a database table.