High performance transactions in database management systems

• US 9,928,264 B2
• Filed: 12/31/2014
• Issued: 03/27/2018
• Est. Priority Date: 10/19/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lomet, David Bruce, Levandoski, Justin Jon, Sengupta, Sudipta, Stutsman, Ryan
• Primary Examiner(s): Pham, Tuan A
• Application Number:
  US14/588,390
• Publication Number:
  US 20160110403A1
• Time in Patent Office: 1,182 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2329 using versioning

Abstract

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.

Claims

1. A system comprising:

one or more processors; and

one or more computer-readable hardware storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the system to be configured with an architecture for providing high performance data transactions in a database management system, the architecture comprising;

a recovery log that acts, in part, as a deferred delivery queue for a transaction outcome message and the recovery log stores a version of a record wherein the recovery log stores redo records and record entries representing copies of versions of respective records that are associated with a key-value store;

a latch-free hash table comprising an offset value that indicates a storage location of the version of the record stored in the recovery log and a most recent read time value indicating a temporal most recent read time of the version of the record;

a multi-version concurrency control (MVCC) module that performs timestamp order concurrency control using the temporal most recent read time of the record as determined by the most recent read time value from the latch-free hash table to identify the offset value that indicates the storage location of the version of the record stored in the recovery log; and

a version manager that sends a log buffer to a transaction component proxy that receives the log buffer and posts committed transactions to stable storage for records associated with the committed transactions.

2. The system of claim 1, the architecture further comprising:

an epoch engine that controls reuse of freed memory locations by denying permission to reuse respective freed memory locations until active threads are unable to dereference pointers to the respective freed memory locations.

3. The system of claim 1, the architecture further comprising:

a transaction component that includes a transaction table that includes respective entries that represent respective transactions, wherein the respective entries each include;

a transaction identifier (TID),

a timestamp value indicating a start time of the respective transaction,

a list representing updates made by the transaction, and

a flag value indicating whether the respective transaction is active, committed, or aborted.

4. The system of claim 3, wherein:

the transaction table includes an entry representing an oldest active transaction that is periodically determined by the transaction component, as one of the respective transactions that is active and is associated with an oldest timestamp, wherein the entry representing the oldest active transaction is used for controlling garbage collection of versions in the latch-free hash table.

5. The system of claim 3, wherein:

the transaction component controls respective commit record write operations for respective commit operations for respective read-only transactions, to store commit records for the respective read-only transactions.

6. The system of claim 5, wherein:

the transaction component initiates the respective commit record write operations for the respective commit operations for the respective read-only transactions, as a result of respective determinations of a commit stability status of a most recently read version that has been read so far by each of the respective read-only transactions.

7. The system of claim 1, wherein:

the transaction component approves a transaction update of a current record, initiates storage of a copy of an updated version of the current record in a recovery log, and initiates generation of a new entry in the latch-free hash table that includes an offset value indicating a position of the updated version of the current record in the recovery log, and an indication of a transaction responsible for the transaction update of the current record.

8. The system of claim 1, wherein:

the transaction component proxy is located remotely from the version manager, substantially close to a location of a data component associated with the stable storage, or locally to the version manager.

9. The system of claim 8, wherein:

the transaction component proxy posts the committed transactions to stable storage for records associated with the committed transactions, maintains a tracking of progress of recovery application to the data component, and provides a summary of the tracked progress to the transaction component.

10. The system of claim 8, wherein:

the transaction component proxy posts the committed transactions to stable storage for records associated with the committed transactions, wherein

the transaction component proxy performs a first scan of the received log buffer to determine committed transactions received from the transaction component, and

the transaction component proxy performs a second scan of the received log buffer to apply operations of the committed transactions at the data component, for the committed transactions determined in the first scan, wherein

the transaction component proxy stores information associated with respective versions, for respective versions associated with respective transactions that are determined as not yet durably committed, wherein

the transaction component proxy tracks progress in apply operations to the data component using a pair of log sequence numbers (LSNs).

11. The system of claim 1, wherein:

a version manager maintains a record read cache for storing copies of preexisting record versions that are read from a data component, wherein the record read cache includes latch-free, log-structured buffers that are populated and cleaned in first-in-first-out (FIFO) order.

12. The system of claim 1, wherein:

a transaction component that includes a version manager that includes the recovery log structured as a plurality of latch-free recovery log buffers using dynamic allocation of storage for newly arriving recovery log buffer entries, wherein;

the version manager maintains the offset variable value indicating a next available location for newly requested storage allocation within a particular recovery log buffer, the offset variable value updated via an atomic fetch and increment operation to add a size of a requested allocation to the offset variable value, and

the offset variable value further indicates a current number of active users of the particular recovery log buffer.

13. The system of claim 1, wherein:

the latch-free hash table includes respective hash table entries that include respective buckets of respective bucket items that represent respective records, the respective bucket items including a value indicating a temporal most recent read time of the respective bucket item and a version list of one or more descriptions that describe one or more respective versions of the respective records.

14. The system of claim 13, wherein:

the one or more descriptions that describe one or more respective versions of the respective records includes;

a transaction identifier (TID) that identifies a creating transaction associated with the respective version of the respective record, and

a version offset value indicating a referencing offset of a copy of the respective version of the respective record that is stored in a recovery log at a location in the recovery log that corresponds to the version offset value.

15. A computer-implemented method performed by one or more processors executing computer executable instructions for the computer-implemented method, the computer-implemented method comprising:

approving a transaction update of a record;

storing a copy of an updated version of the record in a recovery log that acts, in part, as a queue for the deferred delivery of the transaction update to a data component in lieu of using a separate queue wherein the recovery log stores redo records and record entries representing copies of versions of respective records that are associated with a key-value store;

creating a new entry in a latch-free hash table, the new entry comprising an offset value that corresponds to the updated version of the record and a most recent read time value indicating a temporal most recent read time of the updated version of the record;

performing timestamp order concurrency control using a multi-version concurrency control (MVCC) module wherein the temporal most recent read time of the record as determined by the most recent read time value from the latch-free hash table to identify the offset value that indicates the storage location of the version of the record stored in the recovery log; and

sending a log buffer to a transaction component proxy that receives the log buffer and posts committed transactions to stable storage for records associated with the committed transactions.

16. A computer program product comprising a computer-readable storage medium storing executable instructions that when executed by at least one processor cause at least one computing device to:

approve a transaction update of a respective record;

storing a copy of an updated version of the record in a recovery log that acts, in part, as a queue for the deferred delivery of the transaction update to a data component in lieu of using a separate queue wherein the recovery log stores redo records and record entries representing copies of versions of respective records that are associated with a key-value store;

create a new entry in a latch-free hash table comprising an offset value that indicates a storage location of a version of a record in a recovery log and a most recent read time value indicating a temporal most recent read time of the updated version of the respective record;

perform timestamp order concurrency control using a multi-version concurrency control (MVCC) module wherein the temporal most recent read time of the record as determined by the most recent read time value from the latch-free hash table to identify the offset value that indicates the storage location of the version of the record stored in the recovery log; and

send a log buffer to a transaction component proxy that receives the log buffer and posts committed transactions to stable storage for records associated with the committed transactions.

17. The computer program product of claim 16, wherein:

the offset value is updated via an atomic fetch and increment operation to add a size of a requested allocation to the offset value, the offset value further indicating a current number of active users of the recovery log.

18. The computer program product of claim 16, further comprising executable instructions, when executed by the at least one processor, cause the at least one computing device to:

store a copy of an updated version of the respective record in a recovery log comprising one or more in-memory storage buffers; and

determine whether one of the in-memory storage buffers is sealed by determining whether the offset value generated by an atomic fetch and increment operation indicates a buffer offset value that is larger than an extent of the one of the storage buffers and there are no active writers for the one or the storage buffers.