Incremental out-of-place updates for index structures

• US 10,013,440 B1
• Filed: 10/31/2014
• Issued: 07/03/2018
• Est. Priority Date: 10/31/2014
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass, Kulesza, Jakub
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Onat, Alp
• Application Number:
  US14/530,483
• Time in Patent Office: 1,341 Days
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing

Abstract

Incremental, out-of-place updates may be implemented for index structures maintained for data stores. Portions of the index structure may be selected for updating, and an updated version of the portion of the index structure generated in another storage location different than a current storage location for the index structure such that the index structure may be searched in order to perform access requests. Updating the portion of the index structure may include compacting the portion of the index structure and/or merging the portion of the index structure with a sub-index structure generated from a portion of a log of index updates that may be maintained. The current portion of the index structure may then be replaced with the updated version of the current portion so that the updated version may be evaluated when searches of the index structure are performed.

Claims

1. A system, comprising:

one or more block-based persistent storage devices, configured to maintain an index structure for a data store and a log of index updates to the index structure, wherein the index structure is maintained according to an indexing schema for the data store, wherein the log of index updates is not maintained according to the indexing schema, wherein the index structure and the log of index updates are searched in response to access requests received for the data store;

at least one processor;

a memory, comprising program instructions that when executed cause the at least one processor to execute a storage manager to;

select a portion of the log of index updates to incrementally update the index structure;

generate a sub-index structure for the selected portion of the log of index updates according to the indexing schema;

in response to the generation of the sub-index structure, make the sub-index structure available for performing searches such that the sub-index structure is searched in response to access requests received for the data store;

merge the sub-index structure with a current portion of the index structure to generate an updated version of the current portion of the index structure according to the index schema, wherein the updated version of the current portion of the index structure is generated in a different one or more storage locations at the one or more block-based persistent storage devices than a respective one or more storage locations of the current portion of the index structure at the one or more block-based persistent storage devices; and

replace the current portion of the index structure with the updated version of the index structure such that subsequent searches performed on the index structure evaluate the updated version of the current portion of the index structure and the log of index updates.

2. The system of claim 1, wherein the selection, the generation, and the sub-index structure made available are performed for multiple other portions of the log of index updates prior to the merge of the sub-index structure for the portion of the log of index updates with the current portion of the index structure, wherein sub-index structures generated for the other portions of the log of index updates are searched in response to access requests received for the data store.

3. The system of claim 1, wherein the selection of the portion of log of index updates and the generation of the sub-index structure are performed in response to a determination that a search efficiency metric for the log of index updates is below and efficiency threshold.

4. The system of claim 1, wherein the index schema for the index structure is a b-tree index schema, wherein the index structure is implemented as part of a database maintained at the data store, and wherein searches of the index structure are performed in response to receiving queries for select data of the database.

5. A method, comprising:

performing, by one or more computing devices;

storing an index structure for a data store in at least one block-based persistent storage device according to an indexing schema for the data store;

storing a log of index updates to the index structure, wherein the log of index updates is not maintained according to the indexing schema, and wherein the index structure and the log of index updates are searched in response to access requests received for the data store;

incrementally updating the index structure, wherein the index structure is available for searches during the updating, and wherein updating the index structure comprises;

selecting a current portion of the index structure to update;

generating an updated version of the current portion of the index structure as a result of one or more updates received for the data store according to the indexing schema for the data store, wherein the updated version of the current portion of the index structure is generated in a different one or more storage locations than a respective one or more storage locations maintaining the current portion of the index structure; and

replacing the current portion of the index structure with the updated version of the index structure such that subsequent searches performed on the index structure evaluate the updated version of the current portion of the index structure and the log of index updates.

6. The method of claim 5, wherein generating the updated version of the current portion of the index structure comprises compacting the current portion of the index structure, wherein a size of the updated version of the current portion of the index structure is less than a size of the current portion of the index structure prior to compacting the current portion of the index structure.

7. The method of claim 6, wherein incrementally updating the index structure is performed in response to determining that a search efficiency metric for the index structure is below an efficiency threshold.

8. The method of claim 5, wherein generating the updated version of the current portion of the index structure comprises merging the current portion of the index structure with a sub-index structure generated from a plurality of updates received for the index structure.

9. The method of claim 8,

wherein a log of index updates is persistently maintained, wherein a portion of the log of index updates comprises the plurality of updates received for the index structure, wherein the log of index updates is searched in response to access requests received for the data store in addition to the index structure;

wherein the method further comprises generating the sub-index structure according to the indexing schema from the portion of the log of index updates, wherein the sub-index structure is searched in response to access requests received for the data store in addition to the index structure until merged with the current portion of the index structure.

10. The method of claim 9, wherein a plurality of other sub-index structures are generated from different portions of the log of index updates prior to merging the sub-index structure for the portion of the log of index updates with the current portion of the index structure, wherein the plurality of other sub-index structures are searched in response to access requests received for the data store.

11. The method of claim 5, wherein the data store is a log-structured data store, wherein the indexing schema for the index structure co-locates one or more log records corresponding to respective data blocks in the log-structure data store such that a particular version of a particular data block of the respective data blocks is generated according to at least one log record found for the particular data block as a result of a search of the index structure.

12. The method of claim 5, wherein the index schema for the index structure is a b-tree index schema.

13. The method of claim 5, wherein the index structure is implemented as part of a database maintained at the data store, and wherein searches of the index structure are performed in response to receiving queries for select data of the database.

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:

maintaining a log of index updates to an index structure maintained for a data store in at least one block-based persistent storage device, wherein the index structure is maintained according to an indexing schema for the data store, wherein the log of index updates is not maintained according to the indexing schema, wherein the index structure and the log of index updates are searched in response to access requests received for the data store;

selecting a portion of the log of index updates to incrementally update the index structure;

generating a sub-index structure for the selected portion of the log of index updates according to the indexing schema;

in response to generating the sub-index structure, making the sub-index structure available for performing searches such that the sub-index structure is searched in response to access requests received for the data store;

merging the sub-index structure with a current portion of the index structure to generate an updated version of the current portion of the index structure according to the index schema, wherein the updated version of the current portion of the index structure is generated in a different one or more storage locations than a respective one or more storage locations maintaining the current portion of the index structure; and

replacing the current portion of the index structure with the updated version of the index structure such that subsequent searches performed on the index structure evaluate the updated version of the current portion of the index structure and the log of index updates.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the selecting of the portion of log of index updates and the generating of the sub-index structure are performed in response to determining that a search efficiency metric for the log of index updates is below and efficiency threshold.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the selecting, the generating, and the making are performed for multiple other portions of the log of index updates prior to merging the sub-index structure for the portion of the log of index updates with the current portion of the index structure, wherein sub-index structures generated for the other portions of the log of index updates are searched in response to access requests received for the data store.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the index schema for the index structure is a b-tree index schema.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the selecting, the generating, the making, the merging, and the replacing are automatically performed as part of background processing, and wherein processing access requests for the data store that perform searches is performed as part of foreground processing.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the data store is a log-structured data store, wherein the indexing schema for the index structure co-locates one or more log records corresponding to respective data blocks in the log-structure data store such that a particular version of a particular data block of the respective data blocks is generated according to at least one log record found for the particular data block as a result of a search of the index structure, and wherein the sub-index structure co-locates at least one log record corresponding to one or more of the respective data blocks according to a range of time associated with the selected portion of the log of index updates.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the index structure is implemented as part of a file system maintained at the data store, wherein searches of the index structure are performed in response to receiving access requests for select files of the file system.