Microsoft Technology Licensing, LLC

Amazon Technologies, Inc.

Justin Jon Levandoski

David Bruce Lomet

Sudipta Sengupta

Per-Ake Larson

Kamal Kant Gupta

Tengiz Kharatishvili

Xiaofeng Bao

Niket Goel

Alexandre Olegovich Verbitski

Badrish Chandramouli

Donald Kossmann

Mike Barnett

Ahmed Eldawy

James Adam Hunter

Ryan Stutsman

Gunaprasaad Jeganathan

Saileshwar Krishnamurthy

Ippokratis Pandis

Michail Petropoulos

Yongsik Yoon

Sangyong Hwang

Punit Rajgaria

Xiang Peng

Umar Farooq Minhas

Tianzheng Wang

Alexandre Olegovich Vebitski

Joy James Prabhu Arulraj

Darko Makreshanski

Mohamed Mokbel

Keliang Zhao

Kamal Kunt Gupta

Systems and methods are disclosed to implement, in a multi-writer database system, a database engine node that optimistically sends queued purge operations to a backend storage system without waiting for acknowledgement of previous operations from the storage system. If a conflict is later detected for a particular operation, the database engine node may retry some portion of the purge operations in the queue. In embodiments, the purge operations are performed as part of a garbage collection phase of a multi-version concurrency control (MVCC) protocol, where unneeded versions of objects previously generated for isolated snapshots are deleted. In embodiments, the operations in the queue may be grouped so that a rejection of one operation in the group will cause the entire group to be retried. Because these purge operations are idempotent and directed to objects that are invisible, they may be freely retried in arbitrary order, without maintaining any rollback state.

Efficient garbage collection in optimistic multi-writer database systems

Queries to a consistent view of a data set across different types of query engines are performed. Portions of a query received at a first type of query engine that can be performed at a different type of a query engine can be identified. A consistent view of a data set stored in a common data store can be provided by the first type of query engine to the second query engine. When the different type of query engine performs the portion of the query, the different type of query engine applies the consistent view of the data set. A result for the query can be returned by the first type of query engine based on results from the different type of query engine.

Performing queries to a consistent view of a data set across query engine types

A system includes a processor and a memory storing multiple records in a key-value data structure and processor executable instructions for managing access to records in the key-value data structure. The instructions are executable to perform operations including managing a shared atomic epoch counter and thread epoch counters, determining a maximal safe epoch as a function of the shared atomic epoch counter and the thread epoch counters, maintaining a drain list of trigger actions, and triggering the trigger actions in the drain list as a function of an update of the shared atomic epoch counter and the maximal safe epoch.

Key-value store system

Systems and methods are disclosed to implement, in a database system, a database engine node that generates write tracking transactions to atomically enforce cross-page constraints for write operations. In embodiments, the database system may include multiple database engine nodes that optimistically perform page writes without checking for potential conflicts at a shared storage system. The storage system is configured to detect and report conflicting writes on the same page. To cause the storage system to report cross-page conflicts for a write, the database engine node creates a transaction that includes the write and a write tracker (WT) operation for a tracked page. The WT operation will cause the storage system to report any conflicting writes to the tracked page before the actual write is accepted by the storage system. If a reported conflict is not favorably resolved, the database engine node will abort the entire transaction, including the actual write.

Atomic enforcement of cross-page data constraints in decoupled multi-writer databases

Batch processing of undo log records may be performed for rolling back a database transaction. When a rollback operation for a database transaction is performed, undo log records from an undo log to rollback the database transaction are divided into different groups of undo log records. Different requests for the different undo log records are sent to a storage system to be performed. If a conflict is detected for an undo log record in a group, an indication of the conflicting undo log record may be provided to indicate the conflict. The group of undo log records may be resent with a request to reapply the undo log records in the group. When all groups have been identified as successfully completed, then the rollback operation may be considered completed.

Batch undo processing for transaction rollbacks in a multi-writer database

A data manager may include a data opaque interface configured to provide, to an arbitrarily selected page-oriented access method, interface access to page data storage that includes latch-free access to the page data storage. In another aspect, a swap operation may be initiated, of a portion of a first page in cache layer storage to a location in secondary storage, based on initiating a prepending of a partial swap delta record to a page state associated with the first page, the partial swap delta record including a main memory address indicating a storage location of a flush delta record that indicates a location in secondary storage of a missing part of the first page. In another aspect, a page manager may initiate a flush operation of a first page in cache layer storage to a location in secondary storage, based on atomic operations with flush delta records.

Log-structured storage for data access

Various technologies described herein pertain to accessing records of an in-memory database. A memory can include a primary storage and a data store can include a secondary storage. The primary storage includes a first subset of the records of the database, and the secondary storage includes a second subset of the records of the database. Moreover, the memory includes an update memo that includes timestamp notices. The timestamp notices specify statuses of records of the database having updates that span the primary storage and the secondary storage. The memory further includes a database management system that is executable by a processor. The database management system processes a transaction. Further, the database management system includes a storage interface component that accesses a record of the database for the transaction based on at least one of the timestamp notices of the update memo.

Transactional access to records on secondary storage in an in-memory database

Systems and methods are disclosed to implement, in a database system, database engine nodes that implement multi-page writes as an atomic operation. In embodiments, the database system may include multiple database engine nodes that optimistically perform page writes locally without checking for potential conflicts at a shared storage system. The storage system will detect and report conflicting writes on a single page. To ensure that a group of writes to multiple pages occur atomically, the database engine node maintains a transaction context for the group, so that if a page conflict is later detected for any write in the group, the entire group will be rolled back at the database engine node and the storage system. In embodiments, the transaction context will track subsequent writes generated by the node to any page written by the group, so that these subsequent writes are also rolled back with the group.

Optimistic atomic multi-page write operations in decoupled multi-writer databases

A computer implemented method includes receiving multiple requests to update a data structure stored in non-volatile memory (NVM) and applying an atomic multiword update to the data structure to arbitrate access to the NVM. In a further embodiment, a computer implemented method includes allocating a descriptor for a persistent multi-word compare-and-swap operation (PMwCAS), specifying targeted addresses of words to be modified, returning an error if one of the targeted addresses contains a value not equal to a corresponding compare value, executing the operation atomically if the targeted addresses contain values that match the corresponding compare values, and aborting the operation responsive to the returned error.

Index structure using atomic multiword update operations

A current state of one or more entries in a mapping table that are associated with latch-free updates of a data structure that uses indirection mapping tables is accessed. A transformation of the current state of the one or more entries in the mapping table to a transformed state of the entries in the mapping table, is controlled. The controlling includes initiating an atomic multi-word compare-and-swap (MWCAS) operation on a plurality of words using a hardware transactional memory (HTM) resident in a device processor, and the MWCAS operation is performed using hardware primitive operations of the HTM, via the device processor. A transformation of a current state of the data structure to an updated state of the data structure, is controlled, via the transformation of the current state of the one or more entries in the mapping table to the transformed state of the entries in the mapping table.

Controlling atomic updates of indexes using hardware transactional memory

A transaction engine includes a multi-version concurrency control (MVCC) module that accesses a latch-free hash table that includes respective hash table entries that include respective buckets of respective bucket items. The bucket items represent respective records, the respective bucket items each including a value indicating a temporal most recent read time of the item and a version list of descriptions that describe respective versions of the respective records, the MVCC module performing timestamp order concurrency control, using the latch-free hash table. Recovery log buffers may be used as cache storage for the transaction engine.

High performance transactions in database management systems

Various technologies described herein pertain to classifying data in a main memory database system. A record access log can include a sequence of record access observations logged over a time period from a beginning time to an end time. Each of the record access observations can include a respective record ID and read timestamp. The record access log can be scanned in reverse from the end time towards the beginning time. Further, access frequency estimate data for records corresponding to record IDs read from the record access log can be calculated. The access frequency estimate data can include respective upper bounds and respective lower bounds of access frequency estimates for each of the records. Moreover, the records can be classified based on the respective upper bounds and the respective lower bounds of the access frequency estimates, such that K records can be classified as being frequently accessed records.

Growing community of inventors

Seattle, WA, United States of America

Justin Jon Levandoski