Incremental out-of-place updates for index structures

Patent metadata

Field	Value
Publication number	US-10013440-B1
Application number	US-201414530483-A
Country	US
Kind code	B1
Filing date	Oct 31, 2014
Priority date	Oct 31, 2014
Publication date	Jul 3, 2018
Grant date	Jul 3, 2018

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.

First claim

What is claimed is:

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

Assignees

• Amazon Tech Inc

Inventors

• Gupta Anurag Windlass
• Kulesza Jakub

Classifications

• G06F17/30327

  Physics · mapped topic

• G06F17/30067

  Physics · mapped topic

• G06F17/30312 Primary

  Physics · mapped topic

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title