Dynamic splitting of contentious index data pages

Patent metadata

Field	Value
Publication number	US-11080253-B1
Application number	US-201514977439-A
Country	US
Kind code	B1
Filing date	Dec 21, 2015
Priority date	Dec 21, 2015
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

A storage engine may implement dynamic splitting of contentious data pages. Data pages may store data for a table of a data store as part of an indexing structure for the table. Access to the table may be provided by locating the corresponding data pages via the indexing structure. Access contention for different data pages may be monitored. Data pages may be identified for splitting based on the monitoring. A split operation for an identified data page may be formed to store the data on the identified data page on two different data pages so that subsequent access requests for the data are divided between the two data pages. Monitoring of access contention may also be performed to identify data pages for merging in order to consolidate access requests to a single data page.

First claim

What is claimed is:

1. A system, comprising:
one or more persistent storage devices that store data for a table across a plurality of data pages as part of a data store, wherein the plurality of data pages are stored as part of an indexing structure for the table, wherein each of the plurality of data pages stores a different byte range of the data for the table, and wherein access requests to the table are serviced via the index structure in order to locate corresponding data pages to perform the access requests;
at least one processor;
a memory, storing program instructions that when executed by the at least one processor cause the at least one processor to implement a storage engine, the storage engine configured to:
update tracking information for one or more data pages of the plurality of data pages in order to monitor access contention with respect to the one or more data pages, wherein the tracking information comprises respective numbers of waits incurred when obtaining access to the one or more data pages, and wherein individual ones of the waits are incurred by concurrent access requests to the one or more data pages to ensure consistent use of the indexing structure;
evaluate the tracking information to identify a data page of the one or more data pages for a split operation, wherein the data page stores a particular byte range of the data for the table, and wherein the evaluating identifies the data page as having a number of waits incurred that exceeds a split threshold;
perform the split operation upon the data page to split the particular byte range of the data such that subsequently performed access requests to the particular byte range of the data are divided between different data pages to reduce access contention, wherein to split the particular byte range of the data, the storage engine further configured to store respective different byte ranges of the particular byte range of the data on respective ones of the different data pages, wherein the different data pages comprise the data page and one or more other data pages of the plurality of data pages, and wherein the respective different byte range of the particular byte range stored on the data page replaces the particular byte range of the data.

2. The system of claim 1 , wherein to identify the data page of the one or more data pages for a split operation, the storage engine is configured to determine that a number of attempts to access the data page incurring waits exceeds the split threshold.

3. The system of claim 1 , wherein the storage engine is further configured to:
identify one or more of the different data pages as candidate data pages to track for access contention in response to one or more respective access requests incurring waits for the different data pages; and
upon performance of the split operation upon the data page, remove the data page from the candidate data pages to track.

4. The system of claim 1 , wherein the storage engine is implemented as part of a network-based database service and wherein the one or more persistent storage devices are implemented as part of a separate network-based storage service.

5. A method, comprising:
performing, by one or more computing devices:
maintaining data for a table stored in a data store across a plurality of data pages, wherein the plurality of data pages are maintained as part of an indexing structure for the table, wherein each the plurality of data pages stores a different byte range of the data for the table, and wherein access requests to the table are serviced via the index structure in order to locate corresponding data pages to perform the access requests;
monitoring access contention for one or more data pages of the plurality of data pages to identify a data page of the one or more data pages for splitting, wherein monitoring access contention for the one or more data pages comprises maintaining tracking information comprising a number of waits incurred when obtaining access to the one or more data pages, wherein the data page stores a particular range of the data for the table, wherein individual ones of the waits are incurred by concurrent access requests to the one or more data pages to ensure consistent use of the indexing structure, and wherein the monitoring identifies the data page as having a number of waits incurred that exceeds a split threshold; and
splitting the data page to store respective different byte ranges of the particular byte range of the data in respective ones of different data pages such that subsequently performed access requests to the data are divided between the different data pages to reduce access contention, wherein the different data pages comprise the data page and one or more other data pages of the plurality of data pages, and wherein the respective byte range of the particular byte range to store on the data page replaces the particular byte range of the data.

6. The method of claim 5 , wherein monitoring the access contention for the one or more data pages comprises:
updating tracking information in response to attempts to access the one or more data pages; and
evaluating the tracking information to determine that a number of attempts incurring waits for the data page exceeds the split threshold.

7. The method of claim 5 , further comprising:
identifying one or more of the different data pages as candidate data pages to monitor for splitting in response to one or more respective access requests incurring waits for the different data pages; and
upon splitting the data page, removing the data page from the candidate data pages to monitor.

8. The method of claim 7 , wherein identifying the one or more of the different data pages is performed such that a monitoring limitation on a number data pages that may be identified as candidate data pages is not exceeded.

9. The method of claim 5 , wherein monitoring the access contention for the different data pages comprises determining that a number of items in the one or more data pages exceeds a minimum item threshold for splitting.

10. The method of claim 5 , further comprising:
prior to performing the monitoring and the splitting, automatically enabling the monitoring of access contention for the table based, at least in part on an evaluation of a workload of the table.

11. The method of claim 5 , further comprising:
receiving a request to disable monitoring of access contention of the table from a client via a programmatic interface for the data store; and
in response to receiving the request, disabling monitoring of the access contention of the different data pages.

12. The method of claim 5 , further comprising:
monitoring the access contention of the one or more data pages to identify a plurality of other data pages for merging, wherein the one or more data pages is a plurality of data pages, comprising:
determining that the plurality of other data pages are adjacent data pages; and

merging the plurality of other data pages in order to store the respective byte ranges of the data at the plurality of other data pages as a particular byte range of data on a same data page such access requests directed to the data the plurality of other data pages are directed to the same data page.

13. The method of claim 5 , wherein the data store is a network-based storage service storing the table on behalf of a client of the network-based storage service.

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 data for a table stored in a data store across

Assignees

• Amazon Tech Inc

Inventors

• Leshinsky Yan Valerie
• Gupta Kamal Kant
• Kharatishvili Tengiz
• Verbitski Alexandre Olegovich
• Stefani Stefano
• Gupta Anurag Windlass

Classifications

• G06F3/064

  Management of blocks · CPC title

• G06F3/0671

  In-line storage system · CPC title

• G06F3/0653

  Monitoring storage devices or systems · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title