US 10,853,182 B1Granted

Scalable log-based secondary indexes for non-relational databases

AssigneeAmazon Technologies, Inc.

InventorsAkshat Vig, Lokendra Singh Panwar, Subramanian Sankara Subramanian, Rajaprabhu Thiruchi Loganathan, Parikshit Shivajirao Pol, Rama Krishna Sandeep Pokkunuri, Harini Chandrasekharan

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

In response to determining that a secondary index is to be created for a particular table of a non-relational database service, a service component verifies that automated transmission of change records of the table to a log-structured journal has been configured. A given change record comprises a before-image and an after-image associated with a committed database write, and is assigned a unique sequence number. A change record propagator for the secondary index examines change records stored in the journal, and transmits selected change records to an index storage node. The index storage node builds the secondary index using the selected change records.

Claims20

Dependent claims

A system, comprising:

a plurality of computing devices of a distributed non-relational database service of a provider network;
wherein the plurality of computing devices are configured to:
receive a request from a client via a programmatic interface to generate a global secondary index for a particular table, wherein the particular table has a first primary key comprising one or more attributes, wherein at least a portion of the particular table is stored using an overwrite-in-place protocol, wherein the request indicates a key attribute of the global secondary index;
initiate transmission of change records of the particular table of the distributed non-relational database service to a log-structured journal at which a write-once protocol is implemented, wherein a particular change record of the particular table of the distributed non-relational database service transmitted to the log-structured journal includes a pre-image and a post-image associated with a write operation directed to the particular table, wherein the pre-image and post-image respectively indicate a before-value and an after-value of one or more attributes in the particular table affected by the write operation, and wherein individual ones of the change records include a respective sequence number indicative of an order in which the change records are processed by a journal manager of the log-structured journal;
establish one or more change record propagators, including a first change record propagator configured to:
examine at least a subset of change records of the log-structured journal in a sequential order;
in response to determining that a particular change record of the subset of change records of the log-structured journal indicates a write operation whose result is to be represented in the global secondary index, transmit the particular change record obtained from the log-structured journal, including the pre-image and the post-image, to a selected index storage node of the distributed non-relational database service;
and
establish one or more index storage nodes to store contents of the global secondary index, including the selected storage node, wherein the selected index storage node is configured to populate at least a portion of the global secondary index using the particular change record.

6 more elements

A method, comprising:

performing, by one or more computing devices associated with a non-relational database service of a provider network:
determining that a first secondary index is to be established for a particular table of the non-relational database service of the provider network;
verifying that automated transmission of change records of the particular table of the non-relational database service to a log-structured journal has been configured, wherein a particular change record of the particular table of the non-relational database service transmitted to the log-structured journal includes a pre-image and a post-image associated with a write operation directed to the particular table, wherein the pre-image and post-image respectively indicate a before-value and an after-value of one or more attributes in the particular table affected by the write operation;
identifying (a) one or more change record propagators associated with the first secondary index, including a first change record propagator, and (b) one or more index storage nodes associated with the first secondary index, including a first index storage node;
transmitting, from the first change record propagator to the first index storage node associated with the first secondary index, a selected change record, including the pre-image and the post-image, obtained from the log-structured journal;
and
populating, at the first index storage node, at least a portion of the first secondary index based on the selected change record.

4 more elements

A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

determine that a first secondary index is to be created for a particular table of a non-relational database;
verify that automated transmission of change records of the particular table of the non-relational database to a log-structured journal has been initiated, wherein a particular change record of the particular table of the non-relational database transmitted to the log-structured journal includes a pre-image and a post-image associated with a write operation directed to the particular table, and wherein the pre-image and post-image respectively indicate a before-value and an after-value of one or more attributes in the particular table affected by the write operation;
configure a first change record propagator associated with the first secondary index to transmit, to a first index storage node associated with the first secondary index, one or more change records including a selected change record that includes the pre-image and the post-image, obtained from the log-structured journal;
and
cause the first index storage node to generate at least a portion of the first secondary index based on the selected change record.

2 more elements

Dependencies are inferred from the claim text.