Incremental out-of-place updates for datasets in data stores

• US 10,061,834 B1
• Filed: 10/31/2014
• Issued: 08/28/2018
• Est. Priority Date: 10/31/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kulesza, Jakub, Chelepalli, Bharath Kumar, Agarwal, Deepak, Gupta, Anurag Windlass
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Onat, Alp
• Application Number:
  US14/530,495
• Time in Patent Office: 1,397 Days
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A data store may implement incremental out-of-place updates to a dataset. A dataset may maintain data across different storage locations linked together according to an ordering schema for servicing queries. As updates to the dataset are received, the updates may be persisted but not maintained in-place. In order to update the data store and maintain the ordering schema, incremental updates to the dataset may be performed without blocking queries directed toward the dataset. The dataset may be divided into multiple data chunks that correspond to different storage locations and an updated version of the data chunk may be generated in new storage locations. The new storage locations may then replace the storage locations of the prior version of the data chunk in order to link the new storage locations to the other linked storage locations in the dataset for servicing queries.

Claims

1. A system, comprising:

one or more block-based persistent storage devices, configured to maintain a plurality of data chunks that together comprise a dataset as part of a relational data store, wherein individual ones of the plurality of data chunks correspond to a respective one or more storage locations at the one or more block-based persistent storage devices, wherein the respective storage locations for the plurality of data chunks are linked together according to an ordering schema that specifies a sort order according to a data value of the dataset such that data of the dataset for the relational data store is stored across the respective linked storage locations according to the sort order of the ordering schema for servicing queries;

at least one processor;

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

the storage manager, configured to;

for individual ones of the plurality of data chunks;

generate an updated version of the data chunk in one or more new storage locations at the block-based persistent storage device that are not included among the respective storage locations for the plurality of data chunks, wherein the generation of the updated version of the data chunk applies at least one data value insertion or deletion to the data chunk such that data of the updated version of the data chunk is stored within the one or more new storage locations according to the sort order of the ordering schema, wherein the plurality of data chunks including the data chunk are available to service queries during the generation of the updated version of the data chunk;

in response to the generation of the updated version of the data chunk;

replace the respective one or more storage locations corresponding to the data chunk with the one or more new storage locations storing the updated version of the data chunk in order to link the one or more new storage locations together in the sort order with remaining ones of the respective storage locations for the plurality of data chunks, wherein subsequent queries are serviced from the plurality of data chunks including the updated version of the data chunk; and

reclaim the respective one or more storage locations for the data chunk to store other data.

2. The system of claim 1, wherein the dataset is one of a plurality of datasets maintained as part of the relational data store, and wherein the storage manager is further configured to:

prior to the generation, the replacement, and the reclamation, identify the dataset of the plurality of datasets to update.

3. The system of claim 1,

wherein updates for the dataset are not performed in place, wherein the at least one update comprises a plurality of requests to delete respective portions of the data chunk;

wherein to apply the at least one update to the data chunk the storage manager is configured to identify the respective portions of the data chunk to delete; and

wherein to generate the updated version of the data chunk the storage manager is further configured to copy remaining portions of the data chunk not identified for deletion into the one or more new storage locations such that storage space for the respective portions of the data chunk identified for deletion are not included in the one or more new storage locations.

4. The system of claim 1, wherein the relational data store is implemented as a network-based data warehouse service, wherein the dataset is maintained for a client of a plurality of clients of the network-based data warehouse, wherein the one or more block-based persistent storage devices are multi-tenant such that another dataset for another client of the plurality of clients is maintained across the one or more block-based storage devices.

5. A method, comprising:

performing, by one or more computing devices;

selecting a data chunk of a plurality of data chunks that together comprise a dataset maintained as part of a data store, wherein individual ones of the plurality of data chunks correspond to a respective one or more storage locations at a block-based persistent storage device, wherein the respective storage locations for the plurality of data chunks are linked together according to an ordering schema that specifies a sort order according to a data value of the dataset such that data of the dataset for the data store is stored across the respective linked storage locations according to the sort order of the ordering schema for servicing queries;

generating an updated version of the data chunk in one or more new storage locations at the block-based persistent storage device that are not included among the respective storage locations for the plurality of data chunks, wherein generating the updated version of the data chunk comprises applying at least one data value insertion or deletion to the data chunk such that data of the updated version of the data chunk is stored within the one or more new storage locations according to the sort order of the ordering schema, wherein the plurality of data chunks including the selected data chunk are available to service queries during the generation of the updated version of the data chunk;

in response to generating the updated version of the data chunk;

replacing the respective one or more storage locations corresponding to the selected data chunk with the one or more new storage locations storing the updated version of the data chunk in order to link the one or more new storage locations together in the sort order with remaining ones of the respective storage locations for the plurality of data chunks, wherein subsequent queries are serviced from the plurality of data chunks including the updated version of the data chunk; and

reclaiming the respective one or more storage locations for the selected data chunk to store other data.

6. The method of claim 5, wherein the dataset is one of a plurality of datasets maintained as part of the data store, and wherein the method further comprises:

prior to the selecting, the generating, the replacing, and the reclaiming, identifying the dataset of the plurality of datasets to update.

7. The method of claim 6, wherein identifying the dataset of the plurality of datasets for update is based, at least in part, on input/output (I/O) efficiency for servicing queries directed toward the dataset.

8. The method of claim 5,

wherein updates for the dataset are not performed in place, wherein the at least one update comprises a plurality of requests to delete respective portions of the data chunk;

wherein applying the at least one update to the data chunk comprises identifying the respective portions of the data chunk to delete; and

wherein generating the updated version of the data chunk further comprises copying remaining portions of the data chunk not identified for deletion into the one or more new storage locations such that storage space for the respective portions of the data chunk identified for deletion are not included in the one or more new storage locations.

9. The method of claim 8, wherein the one or more new storage locations are less than the respective one or more storage locations such that a size of the updated version of the data chunk is less than a size of the selected data chunk.

10. The method of claim 5,

wherein updates for the dataset are not performed in place, wherein the at least one update comprises one or more requests to insert new data portions into the data chunk;

and

wherein applying the at least one update to the data chunk comprises inserting the one or more new portions of the data chunk into the one or more new storage locations according to the ordering schema.

11. The method of claim 5, wherein the selecting, the generating, the replacing, and the reclaiming are automatically performed as part of background processing, and wherein servicing queries directed toward the dataset is performed as part of foreground processing.

12. The method of claim 5, wherein the selecting, the generating, the replacing, and the reclaiming are performed incrementally for individual ones of the plurality of data chunks of the dataset.

13. The method of claim 5, wherein selecting the data chunk of the plurality of data chunks comprises identifying a remaining data chunk to be updated of the plurality of data chunks subsequent to a restart, wherein the selecting, the generating, the replacing, and the reclaiming were performed for at least one or more other data chunks of the plurality of data chunks prior to the restart.

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 plurality of data chunks that together comprise a dataset as part of a data store, wherein individual ones of the plurality of data chunks correspond to a respective one or more storage locations at a block-based persistent storage device, wherein the respective storage locations for the plurality of data chunks are linked together according to an ordering schema that specifies a sort order according to a data value of the dataset such that data of the dataset for the data store is stored across the respective linked storage locations according to the sort order of the ordering schema for servicing queries;

for individual ones of the plurality of data chunks;

generating an updated version of the data chunk in one or more new storage locations at the block-based persistent storage device that are not included among the respective storage locations for the plurality of data chunks, wherein generating the updated version of the data chunk comprises applying at least one data value insertion or deletion to the data chunk such that data of the updated version of the data chunk is stored within the one or more new storage locations according to the sort order of the ordering schema, wherein the plurality of data chunks including the data chunk are available to service queries during the generation of the updated version of the data chunk;

in response to generating the updated version of the data chunk;

replacing the respective one or more storage locations corresponding to the data chunk with the one or more new storage locations storing the updated version of the data chunk in order to link the one or more new storage locations together in the sort order with remaining ones of the respective storage locations for the plurality of data chunks, wherein subsequent queries are serviced from the plurality of data chunks including the updated version of the data chunk; and

reclaiming the respective one or more storage locations for the data chunk to store other data.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the generating, the replacing, and the reclaiming for the individual ones of the plurality of data chunks are performed in response to detecting an update event for the dataset.

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

wherein updates for the dataset are not performed in place, wherein the at least one update comprises a plurality of requests to delete respective portions of the data chunk;

wherein, in applying the at least one update to the data chunk, the program instructions cause the one or more computing devices to implement identifying the respective portions of the data chunk to delete; and

wherein, in generating the updated version of the data chunk, the program instructions cause the one or more computing devices to further implement copying remaining portions of the data chunk not identified for deletion into the one or more new storage locations such that storage space for the respective portions of the data chunk identified for deletion are not included in the one or more new storage locations.

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

wherein updates for the dataset are not performed in place, wherein the at least one update comprises one or more requests to insert new data portions into the data chunk;

and

wherein, in applying the at least one update to the data chunk, the program instructions cause the one or more computing devices to further implement inserting the one or more new portions of the data chunk into the one or more new storage locations according to the ordering schema.

18. The non-transitory, computer-readable storage medium of claim 17,

wherein the one or more requests to insert new portions of data into the data chunk are maintained along with a larger collection of requests to insert new portions of data into the dataset in other storage locations different than the respective storage locations for the plurality of data chunks;

wherein, the program instructions cause the one or more computing devices to implement sorting the larger collection of requests to insert new portions of data into the dataset according to the ordering schema; and

wherein, in applying the at least one update to the data chunk, the program instructions cause the one or more computing devices to further implement obtaining the one or more requests to insert new portions of data into the data chunk from the sorted larger collection of requests in the other storage locations.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the selecting, the generating, the replacing, and the reclaiming are automatically performed as part of background processing, and wherein servicing queries directed toward the dataset is performed as part of foreground processing.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the data store is implemented as part of a multi-tenant, network-based storage service.