High performance transactions in database management systems

Patent metadata

Field	Value
Publication number	US-9928264-B2
Application number	US-201414588390-A
Country	US
Kind code	B2
Filing date	Dec 31, 2014
Priority date	Oct 19, 2014
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

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.

First claim

What is claimed is:

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 recor

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Lomet David Bruce
• Levandoski Justin Jon
• Sengupta Sudipta
• Stutsman Ryan

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/2322

  using timestamps · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/2329 Primary

  using versioning · CPC title

• G06F16/219

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title