Efficient multi-version locking for main memory databases
AssigneeMicrosoft Corporation
InventorsPer-Ake Larson, Spyridon Blanas, Cristian Diaconu
Life of this patent
Estimating the term…
Abstract
A transaction creates a wait for dependency on a version in a main memory database implementing a multi-version concurrency control scheme. The wait for dependency allows the transaction to update the version while other transactions are reading the version. The multi-version concurrency control scheme also allows commit dependencies to be implementing concurrently with wait for dependencies. Commit dependencies allow a transaction to read an updated version before the updated version is committed.
Claims20
A method for creating a wait for dependency in a multi-version concurrency control scheme of a main memory database, the method comprising:
- a first transaction placing a read marker on a version of a record in a database, the read marker indicating that the first transaction is reading the version of the record, but does not prevent another transaction from reading or updating the record concurrently;
- before the first transaction terminates, a second transaction acquiring a write lock on the version of the record, the write lock preventing another transaction from updating the version of the record;
- as part of acquiring the write lock, the second transaction creating a wait for dependency on the version;
- and
- the second transaction continuing processing, but waiting to begin commit until the first transaction terminates and removes the read marker on the version.
A method for creating a wait for dependency in a multi-version concurrency control scheme of a main memory database, the method comprising:
- one or more first transactions placing a scan marker on a bucket;
- while the bucket is marked by the one or more first transactions, a second transaction attempting to add a new version of a record to the bucket;
- upon detecting the one or more markers on the bucket, the second transaction creating a wait for dependency on each of the one or more first transactions;
- and
- the second transaction continuing processing, but waiting to commit until each of the one or more first transactions terminate.
A method for creating a wait for dependency in a multi-version concurrency control scheme of a main memory database, the method comprising:
- a first transaction acquiring a write lock on a version of a record;
- while the version is write locked by the first transaction, a second transaction attempting to place a read marker on the version;
- upon determining that the version is write locked by the first transaction, the second transaction creating a wait for dependency on the version for the first transaction, wherein the second transaction creates the wait for dependency on the version for the first transaction by incrementing the first transaction's wait for count;
- the second transaction placing a read marker on the version, wherein the wait for dependency causes the first transaction to wait to commit until the second transaction has terminated;
- the second transaction, upon terminating, decrementing the first transaction's wait for count;
- the first transaction determining that its wait for count indicates that the first transaction has no more wait for dependencies;
- and
- the first transaction committing.
Dependencies are inferred from the claim text.