Rate-limiting secondary index creation for an online table

Patent metadata

Field	Value
Publication number	US-10102230-B1
Application number	US-201514859069-A
Country	US
Kind code	B1
Filing date	Sep 18, 2015
Priority date	Sep 18, 2015
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A data storage system may implement rate-limiting 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, maintaining the updates determined according to indexing different portions of the table in a queue of pending updates that are subsequently applied at the secondary index. Prior to indexing a portion of the table, an evaluation of a current number of pending updates in the queue of pending updates may be performed with respect to a throttle threshold. If the current number of pending updates exceeds the throttle threshold, then indexing the portion of the table may be throttled. Received updates to previously indexed portions of the table, may be applied to the table and placed in the queue of pending updates without an evaluation of the current number of pending requests.

First claim

What is claimed is:

1. A system, comprising:
a plurality of computing devices comprising respective processors and a memory to implement a plurality of storage nodes for a data store;
at least one of the storage nodes, configured to:
incrementally evaluate different portions of a table stored in the data store in order to create a secondary index for the table, wherein the table is available for servicing access requests during the creation of the secondary index, wherein to incrementally evaluate the different portions of the table, the at least one storage node is configured to:
scan the different portions of the table to identify items in the table that are to be included in the secondary index;
place updates to write the identified items in the secondary index in a queue of pending updates to be applied to the secondary index;
send pending updates from the queue to another storage node hosting at least a portion of the secondary index to which the pending updates are applied; and
remove the pending updates applied to the secondary index from the queue; and

prior to the evaluation of individual ones of the portions of the table for the secondary index, compare a number of pending updates to the secondary index in the queue with respect to a throttle threshold for the secondary index in order to throttle the evaluation of a portion of the table when the number of pending updates in the queue exceeds the throttle threshold, wherein the evaluation of at least one of the portions is throttled.

2. The system of claim 1 , wherein the storage node is further configured to:
for one other portion of the table:
in response to a determination that the number of pending updates to the secondary index in the queue does not exceed the throttle threshold according to the comparison for the one other portion, perform the scan and the placement for the one other portion of the table.

3. The system of claim 1 , wherein the storage node is configured to determine the throttle threshold according to a provisioned throughput capacity specified for the table.

4. The system of claim 1 , wherein the table is partitioned across different storage nodes of the plurality of storage nodes, including the storage node, wherein other ones of the different storage nodes are configured to perform the evaluation for other portions of the table and the comparison for pending updates in respective queues at the other ones of the different storage nodes.

5. A method, comprising:
performing, by one or more computing devices:
incrementally indexing a table stored in a data store in order to create a secondary index for the table, wherein the table is available for servicing access requests during the creation of the secondary index, wherein the indexing comprises:
maintaining updates to the secondary index determined as part of indexing different portions of the table in a queue of pending updates to the secondary index, wherein the pending updates are subsequently applied to the secondary according to the queue;

prior to indexing individual ones of the portions of the table for the secondary index, evaluating a number of pending updates to the secondary index in the queue with respect to a throttle threshold for the secondary index; and
for at least one of the different portions:
in response to determining that the number of pending updates to the secondary index in the queue exceeds the throttle threshold according to the evaluation, throttling the indexing of the at least one portion of the table for the secondary index.

6. The method of claim 5 , further comprising:
for one other portion of the table:
in response to determining that the number of pending updates to the secondary index in the queue does not exceed the throttle threshold according to the evaluation, performing the indexing of the one other portion, comprising:
analyzing the portion of the table to generate one or more new updates to the secondary index; and
placing the one or more new updates into the queue of pending updates.

7. The method of claim 5 , further comprising determining the throttle threshold according to a provisioned throughput capacity specified for the table.

8. The method of claim 7 , further comprising:
receiving a request to modify the provisioned throughput capacity for the table;
determining a change to the throttle threshold according to the modification of the provisioned throughput capacity; and
updating the throttle threshold such that subsequent evaluations of the number of pending updates are performed with respect to the updated throttle threshold.

9. The method of claim 8 , wherein the request to modify the provisioned throughput capacity is a request to increase the provisioned throughput capacity and wherein the change to the throttle threshold is an increase of the throttle threshold.

10. The method of claim 7 , wherein the secondary index is stored in a plurality of partitions.

11. The method of claim 5 , further comprising:
during the indexing of the table:
receiving a request to update the table in a previously indexed portion from a client;
performing the request to update the table; and
placing a corresponding update for the request in the queue of pending updates, wherein the corresponding update is included in subsequent evaluations of the number of pending updates to the secondary index until the corresponding update is applied to the secondary index and removed from the queue of pending updates.

12. The method of claim 5 , wherein the table is stored in a plurality of partitions, wherein the maintaining, the evaluating, and the throttling are performed by a storage node hosting one of the partitions, wherein other storage nodes host the remaining partitions of the table, wherein the other storage nodes perform the maintaining, and the evaluating with respect to the same throttle threshold.

13. The method of claim 5 , wherein the data store is non-relational storage service, wherein the table is stored for a client of the storage service, and wherein the indexing of the secondary index is performed in response to a request to create the secondary index received from the client.

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 a storage node for a data store, wherein the storage node implements:
incrementally indexing portions a table stored in a data store in order to create a secondary index for the table, wherein the table is available for servicing access requests during the creation of the secondary index, wherein the indexing comprises:
placing updates to the secondary index determined as part of indexing the portions of the table in a queue of pending updates to the secondary index, wherein a pending update is removed from the queue upon application of the pending update at the secondary index; and

prior to indexing individual ones of the portions of the table for the secondary index, evaluating a number of pending updates in the queue with respect to a throttle threshold for the secondary index in order to throttle indexing of a portion of the table when the number of pending updates in the queue exceeds the throttle threshold, wherein the indexing of at least one of the portions of is throttled.

15. The non-transitory, computer-readable storage medium of claim 14 , wherein the storage node further implements:
for another portion of the table:
in response to determining that the number of pending updates to the secondary index in the queue does not exc

Assignees

• Amazon Tech Inc

Inventors

• Muniswamy Reddy Kiran Kumar
• Xiao Wei
• Das Pejus Manoj
• Panwar Lokendra Singh
• Huang Xianglong

Classifications

• G06F16/23 Primary

  Updating · CPC title

• H04L43/0888

  Throughput · CPC title

• G06F17/30345

  Physics · mapped topic

• G06F17/30321 Primary

  Physics · mapped topic

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title