Amazon Technologies, Inc.

Microsoft Corporation

Pradeep Jnana Madhavarapu

Anurag Windlass Gupta

Samuel James McKelvie

Yan Valerie Leshinsky

James McClellan Corey

Laurion Darrell Burchall

Neal Thomas Fachan

Benjamin Tobler

Christopher Richard Newcombe

Tengiz Kharatishvili

Maximiliano Maccanti

Raman Mittal

Balan Sethu Raman

Surendra Verma

David Kruse

Jacob Lacouture

Sundar Subbarayan

Oscar Ricardo Moll Thomae

Jon Cargille

Matthew David Allen

Shishir Pardikar

James Mcclellan Corey

Mathew George

Ahmed Mohamed

Raman Balan Sethu

A database system may include a database service and a separate distributed storage service. The database service (or a database engine head node thereof) may be responsible for query parsing, optimization, and execution, transactionality, and consistency, while the storage service may be responsible for generating data pages from redo log records and for durability of those data pages. For example, in response to a write request directed to a particular data page, the database engine head node may generate a redo log record and send it, but not the data page, to a storage service node. The storage service node may store the redo log record and return a write acknowledgement to the database service prior to applying the redo log record. The server node may apply the redo log record and other redo log records to a previously stored version of the data page to create a current version.

Database system with database engine and separate distributed storage service

A log-structured data store implementing data backup may implement variable data replication. Write requests may be received at different storage nodes maintaining respective replicas of a portion of a log for data maintained in the log-structured data store. Log records indicating the write requests may be stored in the respective replicas of the log portions at the different storage nodes. The log records may be sent to a backup data store to be durability persisted as part of an archived version of the log. At some of the storage nodes, in response to determining that the log records have been durably persisted in the backup data store, storage space for the log records may be reclaimed. In other remaining storage nodes, the log records may be retained and made accessible for servicing read requests.

Variable data replication for storage implementing data backup

A distributed database system may implement dynamic quorum group membership changes. In various embodiments, a quorum set may maintain a replica of a data object among group members according to a protection group policy for the data object. A group member may be identified as to be replaced. In response, a new quorum set may be created from the remaining group members and a new group member. The protection group policy may be updated to include the new group members such that subsequently received updates are maintained at both the previous to quorum set and the new quorum set. Previously received updates may be replicated on the new group member. Upon completion of replicating the previously received updates, the protection group policy for the data object may be revised such that subsequently received updates are maintained at the new quorum set.

Dynamic quorum membership changes

A distributed database system may implement fast crash recovery. Upon recovery from a database head node failure, a connection with one or more storage nodes of a distributed storage system storing data for a database implemented by the database head node may be established. Upon establishment of the connection with the storage nodes, that database may be made available for access, such as for various access requests. In various embodiments, redo log records may not be replayed in order to provide access to the database. In at least some embodiments, the storage nodes may provide a current state of data stored for the database in response to requests.

Fast crash recovery for distributed database systems

Nodes of a database service may receive a read request to perform a read of a record stored by the database service and a transaction request to perform a transaction to the record. First and second indications of time may be associated with the read and transaction, respectively. A potential read anomaly (e.g., fuzzy read, read skew, etc.) may be detected based, at least in part, on a determination that the first indication of time is within a threshold value of the second indication of time. In response to detecting the potential read anomaly, the read may be performed after the transaction specified by the transaction request, regardless of whether the first indication of time is indicative of an earlier point in time than the second indication of time.

Transaction ordering

A data store may implement variable data replication and quorum-based durability schemes. Write requests may be maintained in complete views of the data or incomplete views of the data at storage nodes in a quorum set in the data store. Write requests may be received at different storage nodes sufficient to establish a write quorum, and stored in the replicas of the data at the storage nodes where they are received. Storage nodes maintaining incomplete views of the data may determine that each of the storage nodes maintaining a complete view of the data in the quorum set stores certain write requests, and in response, may reclaim storage space for those write requests included in the incomplete views of the data in order to store other data at the storage node.

Variable data replication for storage systems implementing quorum-based durability schemes

A database system may receive a write request that specifies a modification to be made to a particular data record stored by the database system. A log record representing the modification to be made to the particular data record may be sent to a storage service of the database system. An indication (e.g., log record or other indication) that indicates a cached version of the particular data record stored in a read replica's cache is stale may be sent to a read replica. For a subsequent read of the particular data record received by the read replica, the read replica may request the particular data record from the storage service.

Efficient read replicas

Hybrid quorum policies may be implemented for access requests to state maintained in a distributed system. An update to state maintained in a distributed system may be sent to multiple nodes in the distributed system maintain the state in order to satisfy a hybrid quorum policy for updating the state in the distributed system. The hybrid quorum policy may include individual quorum policies for multiple quorum sets including nodes of the distributed system. Acknowledgments received from nodes in the distributed system indicating that the update is performed may be evaluated according to the individual quorum policies to determine whether the hybrid quorum policy is satisfied. If the hybrid quorum policy is satisfied, then the update to the state may be considered durable.

Hybrid quorum policies for durable consensus in distributed systems

A log-structured data store may implement optimized log storage for asynchronous log updates. In some embodiments, log records may be received indicating updates to data stored for a storage client and indicating positions in a log record sequence. The log records themselves may not be guaranteed to be received according to the log record sequence. Received log records may be stored in a hot log portion of a block-based storage device according to an order in which they are received. Log records in the hot log portion may then be identified to be moved to a cold log portion of the block-based storage device in order to complete a next portion of the log record sequence. Log records may be modified, such as compressed, or coalesced, before being stored together in a data block of the cold log portion according to the log record sequence.

Optimized log storage for asynchronous log updates

A log-structured data store may implement efficient garbage collection. Log records may be maintained in data blocks according to a log record sequence. Based, at least in part, on a log reclamation point, the log records may be evaluated to identify data blocks to reclaim that have log records in the log sequence prior to the log reclamation point. New versions of data pages updated by log records in the identified data blocks may be generated and stored in base page storage for the log structured data store. The identified data blocks may then be reclaimed for storing new data.

Efficient garbage collection for a log-structured data store

A data store maintaining data may implement reducing input/output (I/O) operations for on-demand data page generation. Log records may be maintained for data pages of data describing changes to the data pages. A coalesce operation may be performed when log records for a data page exceed a coalesce threshold for the data page, applying the log records for the data page to a version of the data page and creating a new version that includes the changes indicated by the log records. An indication may be received to increase the coalesce threshold for a particular data page, delaying to a coalesce operation for the data page according to the increased coalesce threshold. The indication may be received from a storage engine that identifies a delay for the particular data page.

Reducing I/O operations for on-demand demand data page generation

A database system may maintain a plurality of log records at a distributed storage system. Each of the plurality of log records may be associated with a respective change to a data page. Upon detection of a coalesce event for a particular data page, log records linked to the particular data page may be applied to generate the particular data page in its current state. Detecting the coalesce event may be a determination that the number of log records linked to the particular data page exceeds a threshold.

Growing community of inventors

Mountain View, CA, United States of America

Pradeep Jnana Madhavarapu