US 9,519,664 B1Granted

Index structure navigation using page versions for read-only nodes

AssigneeAmazon Technologies, Inc.

InventorsTengiz Kharatishvili, Pradeep Jnana Madhavarapu, Anurag Windlass Gupta

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

10 more elements

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.

3 more elements

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.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/032,721Filed 20 Sep 2013
Granted: 13 Dec 2016
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G06F 16/27
Of structured data, e.g. relational data: replication, distribution or synchronisation of data between databases or within a distributed database…
G06F 16/22
Of structured data, e.g. relational data: indexing; Data structures therefor; Storage structures
G06F 16/2228
Indexing; Data structures therefor; Storage structures: indexing structures
G06F 16/2329
Optimistic concurrency control: using versioning

Family

No related US applications are recorded in the indexed filing history.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key