Index structure navigation using page versions for read-only nodes

• US 9,946,735 B2
• Filed: 12/12/2016
• Issued: 04/17/2018
• Est. Priority Date: 09/20/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kharatishvili, Tengiz, Madhavarapu, Pradeep Jnana, Gupta, Anurag Windlass
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US15/376,386
• Publication Number:
  US 20170091226A1
• Time in Patent Office: 491 Days
• Field of Search: 707830
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• 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/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/328 Management therefor

Abstract

Read-only nodes of a distributed database system may implement index structure navigation using page versions. A read request may be received at a read only node of a distributed database for select data. Data pages linked together to form an index structure for data stored for the distributed database may be navigated according to versions maintained for the data pages in order to identify one or more locations to access for the select data. One or more prior versions of data pages may be selected as part navigating the index structure according to a consistent view of the distributed database associated with the read request. Change notifications may also be received at the read-only node modifying the data pages of the index structure. The index structure modifications may be applied without blocking the index structure navigation for servicing the read request.

Claims

1. A system, comprising:

at least one processor; and

a memory to store program instructions that, if executed, cause the at least one processor to perform a method, comprising;

receiving a read request for select data at a read-only node of a distributed database that stores data across a plurality of different data pages linked together according to an index structure;

in response to receiving the read request;

identifying a consistent view of the distributed database associated with the read request;

for individual ones of the plurality of data pages;

selecting a version from among a plurality of versions of the data page based on the selected version being consistent with the consistent view associated with the read request; and

identifying, based on the selected version of the data page, another of the data pages according to a link of the index structure;

determining one or more locations to access for the select data according to the selected versions of the data pages; and

accessing the one or more locations in order to service the read request.

2. The system of claim 1, wherein the method further comprises generating the version of the data page based on applying one or more change notifications received from a read-write node of the distributed database.

3. The system of claim 1, wherein the plurality of different data pages are maintained at a data store that is remote from the read-only node, and wherein the method further comprises obtaining the version of the data page from the data store.

4. The system of claim 1, wherein selecting the version maintained for the data page comprises:

for at least one of the one or more data pages;

determining a most recently committed version for a first data page selected to be read that is linked to a second data page;

identifying a committed version for the second data page that is the same or prior to the most recently committed version for the first data page; and

selecting the committed version of the second data page that is the same or prior to the most recently committed version for the first data page as the respective version of the second data page to read.

5. The system of claim 1, wherein selecting the version maintained for the data page comprises:

for at least one of the one or more data pages;

determining a most recently committed version for a second data page that is linked to by a first data page that is selected to be read;

identifying a committed version for the first data page that is the same or prior to the most recently committed version for the second data page;

determining that the committed version for the first data page is the same as the most recently committed version for the data page; and

in response to determining that the committed version for the first data page is the same as the most recently committed version for the data page, selecting the most recently committed version of the second data page as the respective version of the second data page to read.

6. The system of claim 1, wherein the plurality of different data pages are stored in a log-structured data store and wherein respective versions of the data pages correspond to respective Logical Sequence Numbers (LSNs) of the log-structured data store.

7. The system of claim 1, wherein the distributed database is implemented as part of a network-based database service, wherein the read request is received from a client of the network-based database service via an Application Programming Interface (API) for the network-based database service, and wherein the method further comprises sending one or more results of the read request to the client.

8. A method, comprising:

receiving a read request for select data at a read-only node of a distributed database that stores data across a plurality of different data pages linked together according to an index structure;

in response to receiving the read request;

identifying a consistent view of the distributed database associated with the read request;

for individual ones of the plurality of data pages;

selecting a version from among a plurality of versions of the data page based on the selected version being consistent with the consistent view associated with the read request; and

identifying, based on the selected version of the data page, another of the data pages according to a link of the index structure;

determining one or more locations to access for the select data according to the selected versions of the data pages; and

accessing the one or more locations in order to service the read request.

9. The method of claim 8, further comprising generating the version of the data page based on applying one or more change notifications received from a read-write node of the distributed database.

10. The method of claim 8, wherein the plurality of different data pages are maintained at a data store that is remote from the read-only node, and wherein the method further comprises obtaining the version of the data page from the data store.

11. The method of claim 8, wherein selecting the version maintained for the data page comprises:

for at least one of the one or more data pages;

determining a most recently committed version for a first data page selected to be read that is linked to a second data page;

identifying a committed version for the second data page that is the same or prior to the most recently committed version for the first data page; and

selecting the committed version of the second data page that is the same or prior to the most recently committed version for the first data page as the respective version of the second data page to read.

12. The method of claim 8, wherein selecting the version maintained for the data page comprises:

for at least one of the one or more data pages;

determining a most recently committed version for a second data page that is linked to by a first data page that is selected to be read;

identifying a committed version for the first data page that is the same or prior to the most recently committed version for the second data page;

determining that the committed version for the first data page is the same as the most recently committed version for the data page; and

in response to determining that the committed version for the first data page is the same as the most recently committed version for the data page, selecting the most recently committed version of the second data page as the respective version of the second data page to read.

13. The method of claim 8, wherein the plurality of different data pages are stored in a log-structured data store and wherein respective versions of the data pages correspond to respective Logical Sequence Numbers (LSNs) of the log-structured data store.

14. The method of claim 8, wherein the distributed database is implemented as part of a network-based database service, wherein the read request is received from a client of the network-based database service via an Application Programming Interface (API) for the network-based database service, and wherein the method further comprises sending one or more results of the read request to the client.

15. 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:

receiving a read request for select data at a read-only node of a distributed database that stores data across a plurality of different data pages linked together according to an index structure;

in response to receiving the read request;

identifying a consistent view of the distributed database associated with the read request;

for individual ones of the plurality of data pages;

selecting a version from among a plurality of versions of the data page based on the selected version being consistent with the consistent view associated with the read request; and

identifying, based on the selected version of the data page, another of the data pages according to a link of the index structure;

determining one or more locations to access for the select data according to the selected versions of the data pages; and

accessing the one or more locations in order to service the read request.

16. The non-transitory computer readable storage medium of claim 15, wherein the program instructions cause the one or more computing devices to further implement generating the version of the data page based on applying one or more change notifications received from a read-write node of the distributed database.

17. The non-transitory computer readable storage medium of claim 15, wherein the plurality of different data pages are maintained at a data store that is remote from the read-only node, and wherein the program instructions cause the one or more computing devices to further implement obtaining the version of the data page from the data store.

18. The non-transitory computer readable storage medium of claim 15, wherein, in selecting the version maintained for the data page, the program instructions cause the one or more computing devices to implement:

for at least one of the one or more data pages;

determining a most recently committed version for a first data page selected to be read that is linked to a second data page;

identifying a committed version for the second data page that is the same or prior to the most recently committed version for the first data page; and

selecting the committed version of the second data page that is the same or prior to the most recently committed version for the first data page as the respective version of the second data page to read.

19. The non-transitory computer readable storage medium of claim 15, wherein, in selecting the version maintained for the data page, the program instructions cause the one or more computing devices to further implement:

for at least one of the one or more data pages;

determining a most recently committed version for a second data page that is linked to by a first data page that is selected to be read;

identifying a committed version for the first data page that is the same or prior to the most recently committed version for the second data page;

determining that the committed version for the first data page is the same as the most recently committed version for the data page; and

in response to determining that the committed version for the first data page is the same as the most recently committed version for the data page, selecting the most recently committed version of the second data page as the respective version of the second data page to read.

20. The non-transitory computer readable storage medium of claim 15, wherein the distributed database is implemented as part of a network-based database service, wherein the read request is received from a client of the network-based database service via an Application Programming Interface (API) for the network-based database service, and wherein the program instructions cause the one or more computing devices to further implement sending one or more results of the read request to the client.