Concurrency Control and Transactions

Concurrency is defined as the ability for multiple tasks to access shared data simultaneously. Database concurrency control in eXtremeDB is implemented through database transactions. eXtremeDB Transaction Managers ensure that database transactions are performed concurrently without violating data integrity and that transactions adhere to ACID principles).

There are traditionally two models for database concurrency: optimistic and pessimistic. Pessimistic concurrency control works on the assumption that data modification operations are likely to affect any read operation made by a different task; the database system pessimistically assumes that a conflict will occur. eXtremeDB behavior when using pessimistic concurrency control is to use locks and block access to the database when any data is modified.

Optimistic concurrency control works on the assumption that data modifications are unlikely (although possible) to interfere with any other task reading or modifying data. The runtime behavior when using optimistic concurrency control is to use versioning to allow read operations to see the state of the data before the modification took place.

To allow developers the best choice of concurrency control, eXtremeDB provides three transaction managers, implemented as separate libraries, which makes it easy for applications to use one or the other by simply linking with the appropriate library:

• MURSIW (MUltiple Readers SIngle Writer): a traditional lock-based (pessimistic) transaction manager,
• MVCC (Multi-Version Concurrency Control): an optimistic transaction manager, and
• EXCL (EXCLusive): one task at a time may access the database for reading or writing.

(The transaction managers are discussed in detail in the eXtremeDB User's Guide.)

MURSIW

MURSIW, the traditional, lock-based transaction manager, is implemented as a simple queue. Transactions initiated by applications are added into a queue that is sorted based on the transaction priorities and within each priority, chronologically. This approach to concurrency allows the MURSIW transaction manager to simplify locking mechanisms, eliminating overhead due to resource-consuming complex lock arbitration and deadlock prevention algorithms. This extremely lightweight transaction manager is ideal for many in-memory databases and persistent databases with few concurrent transactions, and for databases that are entirely or predominantly read-only.

Within a priority segment of the transaction queue, read-only transactions are executed simultaneously. Each write transaction is scheduled in its turn and has exclusive use of the database during its transaction. Serialization of write transactions is transparent to the application programmer. Because the transaction manager is “light”, properly designed and implemented application transactions execute swiftly and serialization is not a performance concern.

Imagine that the transaction queue has the following transaction types queued:

All the transactions in group ‘A’ will execute in parallel. When all three transactions have completed, transaction ‘B’ will be scheduled. When ‘B’ has completed, all the transactions in group ‘C’ will be scheduled and execute in parallel. When all of the ‘B’ transactions have completed, the ‘D’ transaction will be scheduled. Any new transactions that are started will enter the queue behind ‘D’ (subject to transaction priorities, of course).

MVCC

The MVCC transaction manager enhances applications’ database concurrency management options. With the MVCC model, while querying a database each transaction sees a snapshot of committed data, regardless of any in-progress transactions belonging to other tasks. This protects the transaction from viewing inconsistent data that could be caused by other transaction updates on the same set of objects or indexes, thus providing transaction isolation for each transaction. The MVCC manager allows applications to choose how transactions are isolated from each other by setting the transaction isolation level at runtime.

Locking optimization

eXtremeDB uses two kinds of synchronization primitives - latches and locks. The first kind (latch) is a lightweight lock implemented with atomic instructions. It is used, for example, in tree indexes to lock branches. The second kind (lock) is a full size synchronization primitive implemented with kernel-locks (and/or lightweight atomics for performance, if possible). One lock is used for the eXtremeDB registry and database header, but all other locks applied during transaction processing depend on the choice of Transaction Manager:

• MVCC - multiple latches in indexes, multiple latches/locks in transaction processing.
• MURSIW – no latches in indexes, multiple latches/locks (but fewer than MVCC) in transaction processing.
• EXCL - no latches in indexes, one single lock on the transaction queue

For single-threaded and single-process applications, it is possible to eliminate latches and locks completely by employing the EXCLusive Transaction Manager and/or “hollow” synchronization implementation. (A sample “hollow” synchronization implementation that makes no kernel calls nor atomic operations or spinlocks is provided as a template for custom user-defined synchronization.)

The developer has complete choice regarding the transaction manager and lock implementations by selecting the transaction manager and synchronization implementation libraries. Most likely the choice will be between MURSIW and MVCC based on the characteristics of the application. For applications having mostly read-only transactions with occasional updates, MURSIW may be the best choice. If there are a relatively high number of concurrent processes / threads attempting to modify the database at the same time, then MVCC will probably be the better choice.

One can experiment between the transaction managers by simply linking the appropriate library. No application code changes are needed (except to handle conflict errors if MVCC is ultimately the choice).

Please see the eXtremeDB User's Guide pages for further explanation and transaction manager implementation details.