Concurrency Control for Reliable Data Management

Professional Developers Want More (Concurrency) Control

Usually (with rare exception), a database is a shared resource, meaning that it is used concurrently by two or more tasks. This leads us to the topic of concurrency control; i.e. how do we coordinate tasks’ access to the database? This is part-and-parcel of providing a database management system that adheres to the ACID properties.

The isolation property is implemented through concurrency control. Broadly speaking, there are two forms of concurrency control: pessimistic and optimistic.

eXtremeDB offers both forms of concurrency control through two different transaction managers: MURSIW and MVCC.

MURSIW – MUtiple Readers, SIngle Writer (pessimistic)

MVCC – Multi-Version Concurrency Control (optimistic)

These are so called because pessimistic concurrency control proactively prevents harm (harm, in this case, being a violation of the isolation property), whereas optimistic concurrency control assumes that no harm will happen, but if it is detected only then will measures be taken.

Pessimistic concurrency control

In operational terms, pessimistic concurrency control is affected with locks. Different vendors can, and do, offer different levels of locks: database locks, table locks, row locks and even column locks in extreme cases. For locking at any level of granularity below the database, things get complicated: there must be either a mechanism to prevent deadlocks, or a means to detect and remediate deadlocks. Invariably, this involves a process called a lock manager or lock arbiter. A deadlock happens when

For pessimistic concurrency control with the MURSIW transaction manager, eXtremeDB locks the database for the exclusive use of a task with a READ_WRITE transaction. This eliminates the need for a lock manager/arbiter or to deal with deadlock prevention or detection, and greatly simplifies the transaction manager. Given the speed of an eXtremeDB in-memory database, this coarse level of locking is well-justified: the time (CPU cycles) that would be required for complex lock arbitration would exceed the time a process needs to simply get into the database, do its work, and get out. This calculus also holds up for persistent databases that have a high ratio of READ_ONLY to READ_WRITE transactions, and there are few concurrent READ_WRITE transactions at any given moment, and transactions are short-lived. The definition of “few” and “short-lived” varies for relatively fast SSD compared to relatively slow HDD.

With MURSIW, concurrent access looks something like:

So, the MURSIW transaction manager prevents harm, i.e. the violation of the isolation property, by blocking any task from accessing the database while another task is modifying the database. The other tasks will wait on a spinlock or be put in the operating system’s waiting queue until the transaction manager can schedule their access to the database. In an environment with many tasks that frequently modify the database, having all but one of them blocked at any given moment is undesirable, so optimistic concurrency control could be advantageous.

Optimistic concurrency control

Optimistic concurrency control in eXtremeDB is implemented with the MVCC transaction manager. Again, the optimistic model doesn’t block tasks from concurrent access to the database. This approach optimistically assumes that tasks will not violate each other’s isolation, e.g. that this won’t happen:

In this scenario, when Process 2 writes record A back to the database, it reverts field A.b to the value when both Process 1 and 2 read the record, obliterating Process 1’s change to field A.b. This scenario is generically called a conflict.

But we can’t guarantee that this won’t happen, so MVCC needs a mechanism to detect when a conflict would happen if a transaction was allowed to commit. This is done by creating versions of the record in the database, and then checking the version number when the transaction is committed. The above scenario becomes:

Obviously, there is some overhead involved with MVCC.  Versions (copies) have to be made of records and those versions checked prior to allowing the transaction to commit, and in the event of a conflict, the transaction has to be executed again from the beginning, and finally, old versions have to be cleaned up when they’re no longer in use. So, there are assumptions underlying MVCC: First, that the overhead associated with versions is comparable to the overhead of managing locks, deadlock detection, etc. associated with pessimistic concurrency control, that the benefit of not having tasks blocked (i.e. greater concurrency) justifies slightly more complex programming (to handle possible conflicts) and that conflicts will be rare. If conflicts are common and transactions are being re-executed frequently, then MURSIW might be a better alternative.
In the absence of conflicts, MVCC exhibits far superior concurrency.

Use the following link to learn more about MVCC performance.

The following table summarizes the MVCC and MURSIW comparison.

The choice of transaction manager (MURSIW or MVCC) in eXtremeDB is made by linking one library or another. The APIs are identical, so the only necessary change in the application code is that to deal with conflicts in MVCC. So, a developer can write the application assuming that MVCC will be used, and switch between MURSIW and MVCC with a simple change of libraries (or a configuration parameter if you’re using the xSQL server).