Locking item ranges for creating a secondary index from an online table

• US 9,875,270 B1
• Filed: 09/18/2015
• Issued: 01/23/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, Das, Pejus Manoj, Huang, Xianglong, Mehta, Nirmal
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US14/859,053
• Time in Patent Office: 858 Days
• Field of Search: 707704
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

A data storage system may implement locking item ranges for creating a secondary index of an online table. A secondary index may be generated for a table of items stored in a non-relational data store. Different ranges of items in the data store may be locked while a corresponding portion of the secondary index is generated. Upon generating the corresponding portion of the secondary index, a range of items may be unlocked. While generating the secondary index, the table may be made available for servicing access requests. For a request to update the table received during the generation of the secondary index, a determination may be made as to whether the update is included within a locked range of the table. If locked, the request may be delayed until the range is unlocked.

Claims

1. A non-relational data store, comprising:

one or more computing devices that implement a storage node for the non-relational data store;

the storage node, configured to;

create a secondary index for a table that includes a plurality of items stored at the storage node, wherein the table is available for servicing access requests received during the creation of the secondary index, wherein to create the secondary index the storage engine is configured to;

lock a range of the items such that access requests to update a portion of the table included in the range are not completed while the range is locked;

generate a portion of the secondary index from the range of items; and

upon completion of the generation, unlock the range of the items;

wherein the lock, the generation, and the unlock are performed for different ranges of the items until the secondary index is complete, wherein a request to update the table directed to at least one of the different ranges that is received while the at least one range is locked is performed subsequent to the unlock of the at least one range.

2. The non-relational data store of claim 1, wherein the storage node is further configured to:

receive another request to update the table during the creation of the secondary index;

identify a portion of the table updated according to the other request; and

in response to a determination that the portion of the table updated according to the other request is not within a locked range, perform the update to the portion of the table according to the other request.

3. The non-relational data store of claim 1, wherein the storage node is further configured to:

store the request to update the table directed to at least one range in a buffer;

upon the unlock of the at least one range;

access the buffer to retrieve the request; and

perform the request to update the table.

4. The non-relational data store of claim 1, wherein the non-relational data store is a network-based storage service, wherein the storage node is one of a plurality of storage nodes that store different partitions of the table, wherein other ones of the plurality of storage nodes perform the creation of the secondary index for the partitions stored at the other storage nodes.

5. A method, comprising:

performing, by one or more computing devices;

generating a secondary index for a table that includes a plurality of items stored in a non-relational data store, wherein the table is available for servicing access requests during the creation of the secondary index, wherein the generating comprises locking different ranges of the items until corresponding portions of the secondary index generated from the different ranges of items are complete;

during the generating of the secondary index;

receiving a request to update the table;

determining that the update to the table is within one of the different ranges of the items locked for creating the secondary index;

delaying the request for subsequent performance; and

upon unlocking the one range of items, updating the table in accordance with the stored request.

6. The method of claim 5, further comprising:

during the generating of the secondary index;

receiving another request to update the table;

identifying a portion of the table updated according to the other request; and

determining that the portion of the table updated according to the other request is not within a locked range;

in response to determining that the portion of the table updated according to the other request is not within the locked range, performing the update to the portion of the table according to the other request.

7. The method of claim 6, further comprising:

determining that the portion of the table is within a previously locked range of the items; and

in response to determining that the portion of the table is within the previously locked range, updating the secondary index according to the other request.

8. The method of claim 6, wherein the portion of the table is within a range of items to be locked, and wherein the method further comprises blocking a lock on the range of items to be locked until the other request is performed.

9. The method of claim 5, wherein the update to the table is a modification to an item within the one locked range.

10. The method of claim 5, wherein delaying the request comprises storing the request in a buffer of received requests to update the table.

11. The method of claim 5, further comprising:

during the generating of the secondary index;

receiving another request to update the table, wherein the update to the table of the other request is within the one locked range;

determining that resources are not available to subsequently service the other request; and

in response to determining that the resources are not available, denying the other request to update the table.

12. The method of claim 5, further comprising:

prior to locking at least one of the different ranges of items, determining a size of the at least one range.

13. The method of claim 5, wherein the table is stored across a plurality of partitions in the non-relational data store, wherein the generating, the receiving, the determining, the delaying, and the unlocking are performed at different ones of the partitions.

14. A system, comprising:

one or more storage devices that store data for a non-relational data store;

at least one processor;

a memory that comprises program instructions, wherein the program instructions cause the at least one processor to implement a storage engine for a non-relational data store;

the storage engine, configured to;

generate a secondary index for a table that includes a plurality of items stored in a non-relational data store, wherein the table is available for servicing access requests during the generation of the secondary index, wherein to create the secondary index, the storage engine is configured to lock different ranges of the items until corresponding portions of the secondary index generated from the different ranges of items are complete;

during the generation of the secondary index;

receive a request to update the table;

determine that the update to the table is within one of the different ranges of the items locked for creating the secondary index;

store the request for subsequent performance; and

upon unlock of the range of items, update the table in accordance with the request.

15. The system of claim 14, wherein the storage engine is further configured to:

during the generation of the secondary index;

receive another request to update the table;

identify a portion of the table updated according to the other request; and

determine that the portion of the table updated according to the other request is not within a locked range;

in response to the determination that the portion of the table updated according to the other request is not within the locked range, perform the update to the portion of the table according to the other request.

16. The system of claim 15, wherein the portion of the table is within a range of items to be locked, and wherein the method further comprises updating another secondary index maintained for the table according to the other request.

17. The system of claim 14, wherein the request to update the table is a request to add a new item to the table, wherein the new item would be within the one range of items that is locked.

18. The system of claim 14, wherein the storage engine is further configured to:

during the generation of the secondary index;

receive request to read data from one or more items within the one range of items that is locked;

send the data from the one or more items in response to the request.

19. The system of claim 14, wherein the request is stored in a buffer of received requests, and wherein the storage engine is further configured to:

receive another request to update the table, wherein the update to the table of the other request is within the one locked range;

determine that the resources are not available to subsequently service other request; and

in response to the determination that the resources are not available, deny the other request to update the table.

20. The system of claim 14, wherein the storage engine is implemented as part of a storage node for the non-relational data store, wherein the system further comprises a plurality of storage nodes including the storage node, wherein the table is stored in a plurality of partitions at different storage nodes, and wherein the non-relational data store is a network-based storage service that stores the table for a client of the network-based storage service.