Amazon Technologies, Inc.

James McClellan Corey

Samuel James McKelvie

Pradeep Jnana Madhavarapu

Anurag Windlass Gupta

Yan Valerie Leshinsky

Benjamin Tobler

Christopher Richard Newcombe

Laurion Darrell Burchall

Neal Thomas Fachan

Oscar Ricardo Moll Thomae

Raman Mittal

Mustafa I Abrar

Matthew David Allen

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 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

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 database management system may utilize a log-structured storage system instead of a conventional storage system. The log-structured storage system may store a baseline of an object and a series of log entries describing changes to the object. At various positions in the log, a combined record may be written to contain a description of a change to the object and a copy of the corresponding version of the object. Combined records may be used to employ alternative strategies for constructing or transmitting a version of an object. Embodiments may employ these alternative strategies for replication and data caches.

Absolute and relative log-structured storage

A distributed database system may implement log-structured distributed storage using a single log sequence number space. A log for a data volume may be maintained in a log-structured distributed storage system. The log may be segmented across multiple protection groups according to a partitioning of user data for the data volume. Updates to the log may be assigned a log sequence number from a log sequence number space for the data volume. A protection group may be determined for an update according to which partition of user data space the update pertains. Metadata to be included with the log record may indicate a previous log sequence number of a log record maintained at the protection group. The log record may be sent to the protection group and identified as committed based on acknowledgments received from storage nodes implementing the protection group.

Log-structured distributed storage using a single log sequence number space

A log-structured distributed storage system may implement individual write quorums. Log records may be sent to different storage nodes of a quorum set storing data for a storage client sufficient to satisfy a write quorum requirement. For each log record, acknowledgments from storage nodes are received, and a determination is made whether the write quorum requirement is satisfied for the log record. Different log records may be maintained at different storage nodes, and still satisfy the write quorum requirement such that in some embodiments no one storage node may maintain all of the log records sent to storage nodes in the quorum set.

Individual write quorums for a log-structured distributed storage system

A data store maintaining data may implement memory-based on-demand data page generation. Log records may be maintained in system memory according to a version threshold for data pages of data stored in persistent storage. When a request for a version of a particular data page is received that is within the version threshold, the data page may be obtained from persistent storage and log records associated with the data page may be applied to the data page to generate the requested version of the data page. The version threshold for the data pages may change, and log records in system memory may be identified for coalesce operations. The coalesce operations may be efficiently performed (e.g., in the background), updating the data pages in persistent storage to include the changes of the identified log records and space in system memory for the identified log records may be reclaimed.

Memory-based on-demand data page generation

Self-describing data blocks of a minimum atomic write size may be stored for a data store. Data may be received for storage in a data block at a persistent storage device. Metadata may be generated for the data that includes an error detection code which is generated for the data and the metadata together. An individual atomic write operation may write together the data and the metadata in the data block. When accessed, the error detection code is applicable to detect errors and the metadata may also be applicable to determine whether the data is stored for a currently assigned purpose or a previously assigned purpose of the data block.

Growing community of inventors

Bothell, WA, United States of America

James McClellan Corey