Methods and systems for managing prioritized database transactions

A database management system for controlling prioritized transactions, comprising: a processor adapted to: receive from a client module a request to write into a database item as part of a high-priority transaction; check a lock status and an injection status of the database item; when the lock status of the database item includes a lock owned by a low-priority transaction and the injection status is not-injected status: change the injection status of the database item to injected status; copy current content of the database item to an undo buffer of the low-priority transaction; and write into a storage engine of the database item.

FIELD

The present disclosure, in some embodiments thereof, relates to prioritizing database transactions and, more particularly, but not exclusively, to simultaneously executing conflicting transactions by managing lock status.

BACKGROUND

Database systems process units of computation that are called transactions. A transaction has a set of properties that are summarized with the acronym ACID:

(A) Atomicity: all transaction changes are applied as a whole, or none of them are applied.

(C) Consistency: if the database fulfills all integrity constraints before the transaction, the database still fulfills the constraints afterwards.

(I) Isolation: the result of a concurrent execution of multiple transactions is equivalent to one serial execution of all concurrent transactions. The ANSI/ISO SQL standard defines different degrees of isolation. With this disclosure, we target the highest possible isolation level, which is called “serializable”.

(D) Durability: the transaction changes survive system failures.

In order to support ACID properties, current database systems are implemented with concurrency control techniques that guarantee these properties. There are two broad families of concurrency control techniques for databases: lock based and timestamp ordering based.

In some cases, a transaction might be associated to a high priority configuration. High priority transactions are atomic and are required to have better quality of service than the rest of the transactions.

Lock based approaches set a lock on each item modified. The lock may be issued as a shared lock when the transaction reads the object; or an exclusive lock when the transaction writes the object. One transaction may obtain a shared lock on an item if the item is not locked by other transaction, or if other transaction holds a shared lock. One transaction can obtain an exclusive lock on an item if the item is not locked by another transaction. This prevents two simultaneous transactions modifying the object concurrently. Lock based techniques use the two phase locking protocol: one transaction gets the corresponding locks before accessing the object, and releases all of them when the transaction commits or aborts.

If one transaction A holds the lock and transaction B requests it, there are several techniques to handle this situation that are used in existing systems:

WAIT: transaction B waits until transaction A releases the lock.

NO WAIT: transaction B aborts when it requests a lock hold by another transaction.

WAIT-IF: transaction B waits if some condition is met, otherwise it aborts. Typical conditions are: B is younger than A (WAIT-DIE) or B is older than A (WAIT-WOUND).

SUMMARY

According to a first aspect of the present disclosure, there is provided a database management system for controlling prioritized transactions, including: a processor adapted to: receive from a client module a request to write into a database item as part of a high-priority transaction; check a lock status and an injection status of the database item; when the lock status of the database item includes a lock owned by a low-priority transaction and the injection status is not-injected status: change the injection status of the database item to injected status; copy current content of the database item to an undo buffer of the low-priority transaction; and write into a storage engine of the database item.

This allows a high-priority transaction to be executed even when a lock exists on the item by a low-priority transaction. Both transactions may execute, while the low-priority transaction does not wait or is aborted.

According to a second aspect of the present disclosure, there is provided a computer implemented method of controlling prioritized transactions in a database management system, including: receiving from a client module a request to write into a database item as part of a high-priority transaction; checking a lock status and an injection status of the database item; when the lock status of the database item includes a lock owned by a low-priority transaction and the injection status is not-injected status: changing the injection status of the database item to injected status; copying current content of the database item to an undo buffer of the low-priority transaction; and writing into a storage engine of the database item.

According to a third aspect of the present disclosure, there is provided a computer program with a program code for performing a method according to the second aspect, when the computer program runs on a computer.

Optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure, the high-priority transaction is a single action transaction, including only the request.

Optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: when the lock status of the database item includes a lock owned by a low-priority transaction and the injection status is injected status: write into a storage engine of the database item.

When a lock is injected, it means that the data in the storage engine of the database item is already updated by another high-priority transaction, so it may now be updated again directly.

Optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: receive from a client module a request to read from a database item as part of a high-priority transaction; check a lock status and an injection status of the database item; when the lock status of the database item includes an exclusive lock owned by a low-priority transaction and the injection status is not-injected status: read from an undo buffer of the low-priority transaction.

When an exclusive lock is not injected, the low-priority transaction may be writing in the storage engine, and the undo buffer keeps the old value for the item in case that the transaction rolls back the changes.

More optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: when the lock status of the database item includes a shared lock owned by a low-priority transaction and the injection status is not-injected status: read from a storage engine of the database item.

When a shared lock is not injected, the low priority transaction processes a read request on a data item that has not been modified concurrently by a high priority transaction. Since no changes are made, the storage engine may be used.

More optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: when the lock status of the database item includes a lock owned by a low-priority transaction and the injection status is injected status: read from a storage engine of the database item.

When a lock is injected, it means that the data in the storage engine of the database item is already updated by a previous high-priority transaction, so the storage engine contains the most updated version of the data.

Optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: receive from a client module a request to write into a database item as part of a low-priority transaction; check a lock status and an injection status of the database item; when the lock status of the database item includes a shared lock owned by the low-priority transaction and the injection status is injected status: change the shared lock to an exclusive lock; and write into an undo buffer of the low-priority transaction.

When a lock is injected, it means that the data in the storage engine of the database item is already updated by a high-priority transaction. The low-priority transaction does not apply further changes to the object in the SE in case of commit or rollback. Instead, the undo buffer is used to store a private copy of the object for the transaction.

More optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: when the lock status of the database item includes an exclusive lock owned by the low-priority transaction and the injection status is injected status: write into an undo buffer of the low-priority transaction.

Optionally, in a further implementation form of the first, the second and/or the third aspects of the disclosure and any of the previous implementations, the processor is further adapted to: receive from a client module a request to read from a database item as part of a low-priority transaction; check a lock status and an injection status of the database item; when the lock status of the database item includes a lock owned by the low-priority transaction and the injection status is injected status: read from an undo buffer of the low-priority transaction.

When a lock is injected, it means that the data in the storage engine of the database item is already updated by a high-priority transaction. Therefore, the undo buffer of the low-priority transaction is used.

DETAILED DESCRIPTION

The present disclosure, in some embodiments thereof, relates to prioritizing database transactions and, more particularly, but not exclusively, to simultaneously executing conflicting transactions by managing lock status.

The present disclosure, in some embodiments thereof, relates to a database system that is implemented with lock based concurrency control technique. According to some embodiments of the present disclosure, the concurrency control technique increases transaction concurrency by allowing some transactions to run concurrently even when they conflict on the same objects, while guaranteeing atomicity, consistency, isolation and durability (ACID) properties. Prioritized transactions have preference over other transactions, but do not force them to abort.

As in currently implemented concurrency control techniques, two standard types of locks are implemented: Shared lock (S), acquired when a transaction reads an object; and Exclusive lock (X), acquired when a transaction writes an object (also referred to as item). A shared lock may be promoted to an exclusive lock. As in a standard S/X policy, Shared locks are compatible with other shared locks, but not with exclusive locks, while Exclusive locks are not compatible with either shared or exclusive locks.

In currently existing systems, independently of the locking policy, transactions are mutually harming each other when they conflict on an object. For example, with WAIT policy transactions may be blocked, and with NOWAIT policy they may be aborted. WAIT-IF policies may implement priorities, but low priority transactions are aborted when in a conflict.

For the purpose of embodiments of the present disclosure, two types of transactions are defined: Low priority transactions (LpTs) and High priority single operation transactions (HpTs). LpTs may affect an arbitrary number of objects, may be committed or rolled back by the client, and are a sequence of operations, which may have control statements such as conditional statements or loops. HpTs affect only one object and have only one operation —allowed operations for HpT are Read object and Write object. HpT are executed in auto commit mode, (i.e. no rollback allowed by the application, however an HpT can fail (abort) on an internal error).

According to some embodiments of the present disclosure, there is provided an injection state for each lock. The lock may be in non-injected state or in injected state. When a lock is in non-injected state, the transactional behavior is normal, as in existing systems. When a HpT tries to write to an object locked by a LpT, the HpT sets a flag in the lock to mark it as injected, copies current content of the object to the LpT's undo buffer, and writes its changes to the database storage engine (SE). When a LpT tries to access an object, it uses its undo buffer to read or write, instead of the SE.

This presents anew non-blocking method where a HpT can apply its operation even when a LpT holds a lock. The HpT neither waits for the lock taken by the LpT nor aborts the LpT. The method according to the present disclosure improves concurrency by saving some transactions that would be aborted in other methods, using only the undo buffer and the SE (no multiversioning for objects is required). HpT may always proceed when a lock is taken by a LpT (read and write transactions are supported), and never aborts a LpT.

Also, in existing systems, short lived HpT suffer from potentially long-live LpT keeping locks on objects for a longer time. Benefits of the method according to the present disclosure are more significant in a distributed transaction, where LpT may hold a lock for a long time and HpT are expected to have low latency.

Another benefit of the method according to the present disclosure is minimizing deadlocks. HpT do not produce deadlocks because they do not acquire locks. When a LpT is read only, it never deadlocks. When a LpT may write an object, it may acquire an exclusive lock on first access, because this prevents any transaction deadlock.

Before explaining at least one exemplary embodiment of the present invention in detail, it is to be understood that the embodiments of the invention are not necessarily limited in their application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples.

The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing.

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network.

Referring now to the drawings,FIG.1is a flowchart schematically representing a method of controlling HpTs in a database management system, according to some embodiments of the present disclosure. Reference is also made toFIG.2, which is a schematic illustration of a database management system for controlling prioritized transactions, according to some embodiments of the present disclosure.

Requests are received from a client210, as transactions, to read and/or write in a database200. Database200may be a relational database or a non-relational database. Database200includes a transaction manager201, which registers transactions204and executes them. Each transaction204has an undo buffer205to store the original state of the database if the transaction is rolled back or aborted.

Database200also includes a storage engine202, which stores the data items of database200. Optionally, database200also includes a database manager203, which receives the transaction requests from client210and registers them into transaction manager201.

Database200may be included in any type of computer and/or computer system, which may include one or more computing devices, for example, a mainframe computer, an enterprise server, a workstation, multiple connected computers, one or more virtual machines and/or a personal computer. Client210may be located in a separate computer, for example a remote computing device connected to database200via a network. Client210may also be included in the same computer and/or computer system as database200, for example a software module such as an application and/or an operating system.

Actions of the method may be performed by a processor and instructions to perform the actions may be implemented in transaction manager201, a transactional storage engine and/or any other component that implements the transaction logic.

In a transactional database, the method may be implemented for example on row level, on page level or on table level or any similar data granularity. Also, it could be implemented on a combination of multiple levels. This may also be implemented in a non-relational database, for example where an object has a unique identifier, like keys in a key/value, document identifiers in a document-oriented database, or vertex/edge identifiers in a graph model.

Optionally, storage engine202provides no specific transactional support. Therefore, it may be assumed that: storage engine202stores a single version of an item; write operations apply the changes immediately to storage engine202unless specified otherwise; write operations are atomic and isolated, meaning only the results of completed writes are exposed at any time; read operations return items being in a consistent state (representing a point in a transaction history); and/or transactions store a copy of the old version of the item, which is applied for rollback of the changes.

Optionally, for LpT, it is not needed to declare all operations at the beginning of the LpT transaction; it is possible to add more operations. It may also be assumed that LpTs use a state of the art two phase locking policy for lock acquisition, and/or that database200includes a standard deadlock detection or prevention mechanism to avoid deadlocks.

Optionally, a single operation for a HpT may be applied atomically and in isolation from others. This may be achieved, for example, by known methods such as: a mutex that is acquired and released on each access to the object. Both HpTs and LpTs acquire the lock in each access; a cooperative multitask engine based on light weight threads, where a light weight thread does not yield to others until it completes the operation; an algorithm based on atomic primitives given by the processor; and/or a transactional memory implementation.

First, as shown at101, a request is received from a client module to write into a database item as part of a HpT.

Then, as shown at102, the lock status and the injection status of the item are checked.

When the lock status of the item includes a lock owned by a LpT and the injection status is not-injected status, as shown at103(when the lock is S-not injected or X-not injected), the following is performed:

First, as shown at104, the injection status of the item is changed to injected status.

Then, as shown at105, the current content of the item is copied to the undo buffer205of the LpT.

Finally, as shown at106, the change to the item is written into storage engine202.

Below is an exemplary HpT transaction executed while a LpT is concurrently executed. Each row indicates the operation applied by the processor. Time advances from top to bottom.

In the final state Obj1=‘B’, Obj2=‘A’, both HpT and LpT commit. By comparison, in a similar situation executed with known methods, HpT waits (in WAIT) or HpT aborts (in NO WAIT).

Optionally, when the lock status of the item includes a lock owned by a LpT and the injection status is injected status, as shown at107(when the lock is S-injected or X-injected), the change to the item is directly written into storage engine202, as shown at106. Optionally, this is also done when the lock status of the item does not include a lock, as shown at108(case: not locked).

Optionally, when a request is received from a client module to read from a database item as part of a HpT, as shown at109, the lock status and the injection status of the item are checked as shown at110.

Then, optionally, when the lock status of the item includes an exclusive lock owned by a LpT and the injection status is not-injected status, as shown at111(when the lock is X-not injected), the data is read from the undo buffer205of the LpT, as shown at112.

Optionally, when the lock status of the item includes an exclusive lock owned by a LpT and the injection status is injected status, as shown at113(when the lock is X-injected), the data of the item is read from storage engine202, as shown at114. Optionally, this is also done when the lock status of the item includes a shared lock owned by a LpT, as shown at115(when the lock is S-not injected or S-injected). Optionally, this is also done when the lock status of the item does not include a lock, as shown at116(case: not locked).

Reference is now made toFIG.3, which is a flowchart schematically representing a method of controlling LpTs in a database management system, according to some embodiments of the present disclosure. When the injection status is not-injected status, LpT may be handled the same way as in known methods.

Optionally, when a request is received from a client module to write into a database item as part of a LpT, as shown at301, the lock status is checked as shown at302. Optionally, when the lock status of the item does not include a lock, an exclusive lock is acquired, as shown at303. Optionally, when the lock status of the item includes a shared lock owned by the LpT the shared lock is changed to an exclusive lock, as shown at304. Optionally, when the lock status of the item includes a lock owned by another transaction, the LpT waits.

Optionally, then, as shown at305and306, an undo buffer is created for the LpT and the current content of the item is copied to the undo buffer of the LpT.

Optionally, then, as shown at307, the injection status of the item is checked. Optionally, when the injection status of the item is injected status, the change to the item is written into the undo buffer of the LpT, as shown at308(lock X-injected). Optionally, when the injection status of the item is not-injected status, the change to the item is directly written into storage engine202, as shown at309. After a HpT write, the status is injected, and the LpT does not apply further changes to the object in the SE in case of commit or rollback. Instead, the undo buffer is used to store a private copy of the object for the transaction.

Optionally, when a request is received from a client module to read from a database item as part of a LpT, as shown at310, the lock status is checked as shown at311. Optionally, when the lock status of the item does not include a lock or includes a shared lock by another transaction, a shared lock is acquired, as shown at312. Optionally, when the lock status of the item includes an exclusive lock owned by another transaction, the LpT waits.

Optionally, then, as shown at313, the injection status of the item is checked. Optionally, when the injection status of the item is injected status, the item is read from the undo buffer of the LpT, as shown at314(lock X-injected or S-injected). Optionally, when the injection status of the item is not-injected status, the item is directly read from the storage engine202, as shown at315. When a lock is injected, it means that the data in the storage engine of the database item is already updated by a high-priority transaction. Therefore, the undo buffer of the low-priority transaction is used.

The application of the rules as described above, provides the following serialization order for concurrent HpT and LpT:Write HpTs are always serialized after LpTs.Read HpTs on an injected lock are always serialized after LpTs.Read HpTs on a non-injected lock are always serialized before LpTs.

Reference is now made toFIG.4, which is a state diagram schematically representing the database locks in a database management system, according to some embodiments of the present disclosure. The diagram shows, for each lock status and injection status, the content of the storage engine and the content of the undo buffer, according to the method as described above. The diagram also shows changes in status that are made by the actions described above.

Reference is now made toFIGS.5A and5B, which are sequence diagrams schematically representing the actions made for a read and write transactions, respectively, according to some embodiments of the present disclosure.

InFIG.5A, client210begins a transaction (501); then database manager203registers the transaction and its priority into transaction manager201(502); client210issues read requests (503); transaction manager201grants access according to HpT and LpT policies (504); database manager203provides the data (505); and finally client210commits or rolls back the transaction (506).

InFIG.5B, after the transaction begins (507) and is registered (508), client210issues write requests (509); transaction manager201grants access according to HpT and LpT policies (510); database manager203reads and stores old versions of the modified objects in undo buffers205(511and512); database manager203writes the object in storage engine202(513); and finally client210commits or rolls back the transaction (514).

It is expected that during the life of a patent maturing from this application many relevant database systems will be developed and the scope of the term database is intended to include all such new technologies a priori.

As used herein the term “about” refers to ±10%.