High performance transactions in database management systems

Patent metadata

Field	Value
Publication number	US-2016110403-A1
Application number	US-201414588390-A
Country	US
Kind code	A1
Filing date	Dec 31, 2014
Priority date	Oct 19, 2014
Publication date	Apr 21, 2016
Grant date	—

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:
at least one processor; a transaction component that includes a computer-readable storage medium that stores executable instructions that are executable by the at least one processor, the executable instructions including a transaction engine that 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 that represent respective records, the respective bucket items each including a value indicating a temporal most recent read time of the each item and a version list of one or more descriptions that describe one or more respective versions of the respective records, using a recovery log as a source of the one or more respective versions of the respective records, the MVCC module performing timestamp order concurrency control, using the latch-free hash table, the temporal most recent read time of the each item including a timestamp value representing the temporal last time the each item was read.

2 . The system of claim 1 , 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 , wherein:
each of 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.

4 . The system of claim 1 , wherein:
the transaction component 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.

5 . The system of claim 4 , wherein:
the transaction table includes an entry representing an oldest active transaction that is periodically determined by the transaction engine, 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.

6 . The system of claim 1 , wherein:
the transaction engine 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.

7 . The system of claim 6 , wherein:
the transaction engine 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.

8 . The system of claim 1 , wherein:
the transaction component includes a version manager that includes a recovery log that stores, in recovery log buffers, pure redo records and record entries representing copies of versions of respective records that are associated with a key-value store.

9 . The system of claim 8 , wherein:
the transaction engine 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 buffer, in the recovery log, and initiates generation of a new entry in the MVCC latch-free hash table that includes an offset value indicating a position of the updated version of the current record in the recovery log buffer, and an indication of a transaction responsible for the transaction update of the current record.

10 . The system of claim 8 , wherein:
the version manager sends log buffers to a transaction component proxy that receives the log buffers and posts committed transactions to stable storage for records associated with the committed transactions, wherein the transaction component proxy is located remotely from the transaction component, substantially close to a location of a data component associated with the stable storage, or locally to the transaction component.

11 . The system of claim 10 , wherein:
the transaction component proxy posts the committed transactions to stable storage for records associated with the committed transactions, the stable storage managed by the data component that includes the data component of a key-value store, wherein the transaction component proxy maintains a tracking of progress of recovery application to the data component, and provides a summary of the tracked progress to the transaction component.

12 . The system of claim 10 , wherein:
the transaction component proxy posts the committed transactions to stable storage for records associated with the committed transactions, the stable storage managed by the data component that includes the data component of a key-value store, wherein the transaction component proxy performs a first scan of each received log buffer to determine committed transactions received from the transaction component, and the transaction component proxy performs a second scan of the each 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).

13 . The system of claim 8 , wherein:
the 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.

14 . The system of claim 1 , wherein:
the transaction component includes a version manager that includes a 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 an 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 (FAI) operation to add the 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.

15 . A method comprising:
accessing a latch-free hash table that includes respective hash table entries that include respective buckets of respective bucket items that represent respective records, the respective bucket items each including a value indicating a temporal most recent read time of the each item and a version list of one or more descript

Assignees

• Microsoft Corp

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

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

• G06F16/2329 Primary

  using versioning · CPC title