Implicit prioritization to rate-limit secondary index creation for an online table

• US 9,898,614 B1
• Filed: 09/18/2015
• Issued: 02/20/2018
• Est. Priority Date: 09/18/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Muniswamy Reddy, Kiran Kumar, Xiao, Wei, Morley, Adam Douglas, Panwar, Lokendra Singh
• Primary Examiner(s): Le, Chau
• Application Number:
  US14/859,072
• Time in Patent Office: 886 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 21/604 Tools and structures for managing or administering access control systems
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: H04L 47/215 using token-bucket

Abstract

A data storage system may implement implicit prioritization to rate-limit secondary index creation for an online table. A secondary index may be generated for a table stored in a data store. The table may be incrementally indexed, performing multiple indexing operations to populate the secondary index. Prior to performing an indexing operation, an evaluation of a capacity limitation for performing indexing operations may be made with respect to capacity to process access requests at the data store. If a determination is made that performance of the indexing operation exceeds the capacity limitation, then the indexing operation may be throttled. If a determination is made that performance of the indexing operation does not exceed the capacity limitation, then the indexing operation may be performed.

Claims

1. A system, comprising:

at least one processor;

a memory, storing program instructions that when executed by the at least one processor cause the at least one processor to implement a storage host for a data store;

the storage host, configured to;

receive a request to create a secondary index for a table stored in the data store, wherein the table is available for servicing access requests using a primary key, and wherein the secondary index provides an alternative access schema for the table in addition to the primary key;

in response to receipt of the request, incrementally perform a plurality of indexing operations to create the secondary index while the table remains available for servicing access requests using the primary key, wherein to incrementally perform the indexing operations, the storage engine is configured to;

prior to performance of individual ones of the indexing operations;

verify that utilization of available capacity to perform the indexing operation is within a capacity limitation for performance of the indexing operations, wherein the capacity limitation is a portion of a total capacity of a storage device that stores at least a portion of the table to process access requests directed to the storage device;

in response to a determination that the utilization of the available capacity to perform the indexing operation exceeds the capacity limitation, throttle performance of the indexing operation; and

wherein at least one of the indexing operations is throttled.

2. The system of claim 1,

wherein the storage host is further configured to maintain an access token bucket for the total capacity of the storage device to process access requests directed to the storage device and an access token bucket for the capacity limitation for performance of the indexing operations;

wherein to verify that the utilization of available capacity to perform the indexing operation is within the capacity limitation, the storage host is configured to attempt to obtain an access token for the indexing operation from the access token bucket for the capacity of the storage device and the access token bucket for the capacity limitation; and

wherein to determine that the utilization of the available capacity to perform the indexing operation exceeds the capacity limitation, the storage host is configured to detect at least one of;

a failure to obtain the access token from the access token bucket for the capacity of the storage device;

or

a failure to obtain the access token bucket for the capacity limitation.

3. The system of claim 2, wherein the storage host is further configured to:

maintain an access token bucket for user access to the table;

during the generation of the secondary index;

receive an access request directed to the table from a user;

attempt to obtain an access token from the access token bucket for user access to the table;

in response to obtainment of the access token from the access token bucket for user access to the table;

perform the access request; and

deduct an access token from the access token bucket for the total capacity of the storage device to process access requests directed to the table.

4. The system of claim 1, wherein the data store is a non-relational data storage service, wherein the table is associated with a customer account of the non-relational data storage service, and wherein the storage host is a multi-tenant storage host that stores data for at least a portion of one or more other tables associated with different customer accounts of the network-based storage service at the storage device.

5. A method, comprising:

performing, by one or more computing devices;

performing a plurality of indexing operations to generate a secondary index for a table stored in a data store, wherein the table is available for servicing access requests using a primary key, and wherein the secondary index provides an alternative access schema for the table in addition to the primary key, performing the plurality of indexing operations comprising;

prior to performing at least one indexing operation;

evaluating a capacity limitation for performing the indexing operations with respect to a capacity of the data store to process access requests;

determining, according to the evaluation, that performing the at least one indexing operation exceeds the capacity limitation; and

in response to determining that performing the at least one indexing operation exceeds the capacity limitation, throttling performance of the at least one indexing operation.

6. The method of claim 5,

wherein the method further comprises maintaining an access token bucket for the capacity of the data store to process access requests and an access token bucket for the capacity limitation for performing the indexing operations;

wherein the evaluating the capacity limitation for performing the indexing operations with respect to the capacity of the data store comprises attempting to obtain an access token for the at least one indexing operation from the access token bucket for the capacity of the data store and the access token bucket for the capacity limitation; and

wherein determining that performing the at least one indexing operation exceeds the capacity limitation comprises detecting at least one of;

a failure to obtain the access token from the access token bucket for the capacity of the data store;

or

a failure to obtain the access token bucket for the capacity limitation.

7. The method of claim 6, further comprising:

maintaining an access token bucket for user access to the table;

during the generating of the secondary index;

receiving an access request directed to the table from a user;

attempting to obtain an access token from the access token bucket for user access to the table;

in response to obtaining the access token from the access token bucket for user access to the table;

performing the access request; and

deducting an access token from the access token bucket for the capacity of the data store to process access requests.

8. The method of claim 5, wherein the method further comprises:

prior to performing at least one other indexing operation;

evaluating the capacity limitation for performing the indexing operations with respect to the capacity;

determining, according to the evaluation, that performing the at least one other indexing operation does not exceed the capacity limitation; and

in response to determining that performing the at least one other indexing operation does not exceed the capacity limitation, performing the at least one other indexing operation.

9. The method of claim 8,

wherein the method further comprises maintaining an access token bucket for the capacity of the data store to process access requests and an access token bucket for the capacity limitation for performing the indexing operations;

wherein the evaluating the capacity limitation for performing the indexing operations with respect to the capacity of the data store comprises attempting to obtain an access token for the at least one other indexing operation from the access token bucket for the capacity of the data store and the access token bucket for the capacity limitation; and

wherein determining that performing the at least one other indexing operation exceeds the capacity limitation comprises obtaining;

the access token from the access token bucket for the capacity of the data store; and

the access token bucket for the capacity limitation.

10. The method of claim 5, wherein the evaluating the capacity limitation for performing the indexing operations comprises:

verifying utilization of available capacity at a master replica to perform the indexing operation with respect to capacity of one or more storage devices at the master replica to process access requests; and

verifying utilization of available capacity at one or more peer replicas to perform the indexing operation with respect to capacity of one or more storage devices at the one or more peer replicas to process access requests.

11. The method of claim 5, wherein the indexing operation is an Input/Output (I/O) operation to write to a storage device storing at least a portion of the table.

12. The method of claim 5, wherein the data store is a network-based storage service, wherein the performing the plurality of secondary index operations, the evaluating the capacity limitation, the determining that the capacity limitation is exceeded, and the throttling the at least one indexing operation are performed in response to a request to create the secondary index received via a network-based interface for the network-based storage service.

13. The method of claim 12, wherein the performing the plurality of secondary index operations, the evaluating the capacity limitation, the determining that the capacity limitation is exceeded, and the throttling the at least one indexing operation are performed at a multi-tenant storage host of the network-based storage service storing data for at least a portion of the table, wherein the table is associated with a customer account of the network-based storage service, wherein the storage host stores data for at least a portion of one or more other tables associated with different customer accounts of the network-based storage service, and wherein the method further comprises:

in response to receiving a request to generate a secondary index for one of the other tables, migrating the data for at least the portion of the other table to a different storage host.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

performing a plurality of indexing operations to generate a secondary index for a table stored in a data store, wherein the table is available for servicing access requests using a primary key, and wherein the secondary index provides an alternative access schema for the table in addition to the primary key, performing the plurality of indexing operations comprising;

prior to performing at least one indexing operation;

verifying that utilization of available capacity to perform the at least one indexing operation is within a capacity limitation for performance of the indexing operations, wherein the capacity limitation is a portion of a total capacity of the data store to process access requests;

determining, according to the verification, that the utilization of the available capacity to perform the at least one indexing operation exceeds the capacity limitation; and

in response to determining that the utilization of the available capacity to perform the indexing operation exceeds the capacity limitation, throttling performance of the at least one indexing operation.

15. The non-transitory, computer-readable storage medium of claim 14,

wherein the programming instructions cause the one or more computing devices to further implement maintaining an access token bucket for the capacity of the data store to process access requests and an access token bucket for the capacity limitation for performing the indexing operations;

wherein, in the verifying that the utilization of available capacity to perform the at least one indexing operation is within the capacity limitation, the programming instructions cause the one or more computing devices to implement attempting to obtain an access token for the indexing operation from the access token bucket for the capacity of the data store and the access token bucket for the capacity limitation; and

wherein, in determining that the utilization of the available capacity to perform the at least one indexing operation exceeds the capacity limitation, the programming instructions cause the one or more computing devices to implement detecting at least one of;

a failure to obtain the access token from the access token bucket for the capacity of the data store;

or

a failure to obtain the access token bucket for the capacity limitation.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions cause the one or more computing devices to further implement:

maintaining an access token bucket for user access to the table;

during the generating of the secondary index;

receiving an access request directed to the table from a user;

attempting to obtain an access token from the access token bucket for user access to the table;

in response to obtaining the access token from the access token bucket for user access to the table;

performing the access request; and

deducting an access token from the access token bucket for the capacity of the data store.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

prior to performing at least one other indexing operation;

verifying that the utilization of available capacity to perform the at least one other indexing operation is within the capacity limitation;

determining, according to the verification, that the utilization of the available capacity to perform the at least one other indexing operation does not exceed the capacity limitation; and

in response to determining that the utilization of the available capacity to perform the indexing operation does not exceed the capacity limitation, performing the at least one other indexing operation.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the capacity of the data store is the capacity of is total Input/Output Operations per Second (IOPS) capability of one or more storage devices storing at least a portion of the table.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the indexing operation is an Input/Output (I/O) operation to read from a persistent storage device storing at least a portion of the table.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the data store is a network-based storage service, wherein the performing the plurality of secondary index operations, the verifying the utilization of the available capacity, the determining that the capacity limitation is exceeded, and the throttling the at least one indexing operation are performed in response to a request to create the secondary index received via a network-based interface for the network-based storage service.