Index structure navigation using page versions for read-only nodes

• US 9,519,664 B1
• Filed: 09/20/2013
• Issued: 12/13/2016
• 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
• Application Number:
  US14/032,721
• Time in Patent Office: 1,180 Days
• Field of Search: 707/830
• US Class Current: 1/1
• 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:

one or more computing devices each comprising at least one respective hardware processor and memory and configured to implement a plurality of nodes of a distributed database;

a read-write node of the plurality of nodes, configured to;

in response to received updates to the distributed database, perform one or more operations to modify one or more data pages out of a plurality of data pages linked together to comprise an index structure for data stored for the distributed database;

send one or more change notifications corresponding to the operations to one or more read-only nodes of the plurality of nodes implementing the distributed database;

the one or more read-only nodes, wherein each of the read-only nodes is configured to;

in response to receiving the one or more change notifications, update one or more data pages out of a plurality of data pages comprising a replica of the index structure maintained at the read-only node to a respective current version of the page, wherein one or more prior versions for each of the one or more data pages are maintained as part of a plurality of prior versions maintained for the plurality of data pages comprising the replica of the index structure;

receive a read request for select data;

in response to receiving the read request;

navigate between different ones of the plurality of data pages comprising the replica of the index structure in order to identify one or more locations to access for the select data, wherein each navigation is based, at least in part, on the plurality of prior versions of the plurality of data pages, and wherein each of said navigations comprises;

based, at least in part, on a version of a current page, select a destination page, wherein the version of the current page corresponds to a consistent view of the distributed database associated with the read request;

evaluate one or more versions of the destination page in order to select a version of the destination page consistent with the version of the current page; and

identify the selected version of the destination page as the current page.

2. The system of claim 1, wherein to navigate between different ones of the plurality of data pages comprising the replica of the index structure, each of the one or more read-only nodes are further configured to build the version of the current page based, at least in part, on one or more previously received change notifications from the read-write node.

3. The system of claim 1, further comprising:

a distributed storage system, configured to;

maintain the plurality of data pages comprising the index structure and the plurality of prior versions of the plurality of data pages for the distributed database system;

process access requests directed to the plurality of data pages from the read-write node and the one or more read-only nodes;

wherein, to navigate between different ones of the plurality of data pages comprising the replica of the index structure, each of the one or more read-only nodes is configured to request the version of the current page from the distributed storage system.

4. The system of claim 3, wherein the distributed database is a network-based database service, and wherein the distributed storage system is a network-based distributed storage service.

5. A method, comprising:

performing, by one or more computing devices implementing a read-only node of a plurality of nodes implementing a distributed database;

receiving a read request for select data maintained for the distributed database, wherein a plurality of data pages store data for the distributed database and are linked together according to an index structure, wherein one or more different versions for each of the plurality of data pages are maintained;

in response to receiving the read request;

navigating between different ones of the plurality of data pages in the index structure according to the respective page versions maintained for the different ones of the plurality of data pages in order to identify one or more locations to access for the select data, wherein said navigation to at least one of the different ones of the plurality of data pages selects one of multiple versions maintained for the at least one data page consistent with a consistent view of the distributed database associated with the read request; and

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

6. The method of claim 5, further comprising:

receiving one or more change notifications indicating one or more index structure modifications performed at a read-write node, wherein the index structure modifications generate new versions of one or more of the plurality of data pages in the index structure; and

in response to receiving the one or more change notifications, updating the one or more different versions for each of the plurality of data pages maintained to include the new versions of the one or more data pages corresponding to the index structure modifications.

7. The method of claim 6, wherein the one or more change notifications are one or more log records.

8. The method of claim 6, wherein the consistent view of the distributed database associated with the read request is a view of the database prior to the performance of the one or more index structure operations, and wherein the selected version of the at least one data page is a prior version of the at least one data page.

9. The method of claim 5, wherein said navigating between the different ones of the plurality of data pages in the index structure according to the respective page versions maintained for the different ones of the plurality of data pages comprises:

for each navigation;

based, at least in part, on a version of a current page, selecting a destination page, wherein the version for the current page corresponds to the consistent view of the distributed database associated with the read request;

evaluating one or more versions maintained for the destination page in order to select a version of the destination page consistent with the version for the current page; and

identifying the selected version of the destination page as the current page.

10. The method of claim 9, wherein said evaluating the one or more versions maintained for the destination page in order to select the version of the destination page consistent with the version for the current page, comprises:

determining a most recently committed version for the current page;

identifying a committed version for the destination page that is the same or prior to the most recently committed version for the current page; and

selecting the committed version for the destination page that is the same or prior to the most recently committed version for the current page as the selected version of the destination page consistent with the version for the current page.

11. The method of claim 10, wherein said evaluating the one or more versions maintained for the destination page in order to select the version of the destination page consistent with the version for the current page, further comprises:

determining a most recently committed version for the destination page;

identifying a committed version for the current page that is the same or prior to the most recently committed version for the destination page;

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

in response to determining that the committed version for the current page is the same as the most recently committed version for the current page, selecting the most recently committed version for the destination page as the selected version of the destination page consistent with the version for the current page.

12. The method of claim 9, wherein each navigation is performed without locking the different ones of the plurality of data pages.

13. The method of claim 9, wherein said navigating between the different ones of the plurality of data pages in the index structure according to the respective page versions maintained for the different ones of the plurality of data pages, further comprises obtaining the version of the current page.

14. The method of claim 13, wherein the distributed database is a network-based distributed database service storing data for one or more clients, wherein another plurality of nodes implement a network-based storage service, wherein the network-based storage service maintains the one or more different versions for each of the plurality of data pages, and wherein said obtaining the version of the current page, comprises requesting the version of the current page from the network-based storage service.

15. A non-transitory computer-readable storage medium, storing program instructions that when executed by one or more computing devices implement a read-only node of a plurality of nodes implementing a distributed database, wherein the read-only node implements:

receiving a read request for select data maintained for the distributed database, wherein a plurality of data pages store data for the distributed database and are linked together according to an index structure, wherein one or more different versions for each of the plurality of data pages are maintained;

in response to receiving the read request;

navigating between different ones of the plurality of data pages in the index structure according to the respective page versions maintained for the different ones of the plurality of data pages in order to identify one or more locations to access for the select data, wherein each navigation comprises;

based, at least in part, on a version of a current page, selecting a destination page, wherein the version for the current page corresponds to a consistent view of the distributed database associated with the read request;

evaluating one or more versions maintained for the destination page in order to select a version of the destination page consistent with the version for the current page; and

identifying the selected version of the destination page as the current page.

16. The non-transitory computer readable storage medium of claim 15, wherein the read-only node further implements:

receiving one or more change notifications indicating one or more index structure modifications performed at a read-write node, wherein the index structure modifications generate new versions of one or more of the plurality of data pages; and

in response to receiving the one or more change notifications, updating the one or more different versions for each of the plurality of data pages maintained to include the new versions of the one or more data pages corresponding to the index structure modifications.

17. The non-transitory computer readable storage medium of claim 16, wherein the one or more change notifications indicating the one or more index structure modifications performed at the read-write node are one or more log records, wherein said updating the one or more different versions for each of the plurality of data pages maintained to include the new versions of the one or more data pages corresponding to the index structure modifications, comprises appending the one or more log records to a log structure comprising a plurality of other log records that indicate the one or more different versions.

18. The non-transitory computer readable storage medium of claim 17, wherein, in said navigating between the different ones of the plurality of data pages in the index structure according to the respective page versions maintained for the different ones of the plurality of data pages, the read-only node further implements generating the version of the current page based, at least in part, on at least one of the plurality of other log records and the one or more log records.

19. The non-transitory computer readable storage medium of claim 15, wherein in said, evaluating the one or more versions maintained for the destination page in order to select the version of the destination page consistent with the version for the current page, the read-only node further implements:

determining a most recently committed version for the current page;

identifying a committed version for the destination page that is the same or prior to the most recently committed version for the current page;

determining a most recently committed version for the destination page;

identifying a committed version for the current page that is the same or prior to the most recently committed version for the destination page;

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

in response to determining that the committed version for the current page is the same as the most recently committed version for the current page, selecting the most recently committed version for the destination page as the selected version of the destination page consistent with the version for the current page.

20. The non-transitory computer readable storage medium of claim 15, wherein the distributed database is a network-based distributed database service storing data for one or more clients, and wherein the read-only node further implements:

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

sending the select data in response to the read request.