Concurrency Control Mechanisms

As part of my PhD, I spent some time studying concurrency control mechanisms, looking for the most appropriate solution for the database system I was developing.

This article describes one such model, read-write-certify, and looks at how it might be extended for use in a distributed database system. I hope this helps to highlight the issues involved in the design of concurrency control mechanisms more generally.

The Basics

Read-write-certify (RWC) is a slightly more liberal version of the typical shared read, exclusive write locking model (as seen in most DBMSs). Unlike the latter approach RWC allows reads and writes to execute concurrently on the same item. To explain, consider the following example.

Figure 1: Single Item Database

Figure one shows a local database containing one item X, which stores the value ‘1’. In theshared-read, exclusive write model a machine updating X obtains an exclusive lock while it makes its update, meaning all read queries must wait on the update to complete. However in RWC, a transaction creates a new version of the item (named XI in figure 2) in its own transaction workspace on which to make the update. This ensures that the original copy of X is available for read queries.

Figure 2: Contrasting Approaches to Locking

The updating transaction uses  its local workspace copy (XI) to execute the update, but must then commit these changes by updating X, the global copy. Another lock called a certify lock is required to give exclusive access to the original while the update is committed.

Figure 3: Certify Locking

The transaction with the certify lock now completes the update by transferring changes to the primary copy, as shown above.

The principal advantage of this approach in a centralized database is that read queries are not blocked while updates are taking place, giving slightly more concurrency. While certify locks block, they are likely to be held for less time because the update has already been written.

The Effect of Distribution

Despite the improvement from the previous approach, Read-Write-Certify must still block read requests when certifying an update. In a distributed database system is it possible to get around this restriction?

To answer that question we require an item with multiple replicas, each on a different machine.

Figure 4: Multiple Replicas

In this system the same locking principles hold for individual replicas as they did with the local database, but the certify lock has only to the lock a single replica, not every copy. While the update is being completed on this replica read queries can still access other copies elsewhere.

Consider this in our example system. A transaction has previously obtained a write lock on X2and has updated its value. It is now attempting to commit the update and has a certify lock onX2. Another transaction requests a read lock and has it granted for X1, the other replica. The read request can be made, unblocked, despite an update being completed on the other machine.

Figure 5: Non-blocking Read Query

If the update transaction on X2 completes before the read on X1 then the read will take place on out-of-date data. This isn’t desirable, but for many applications it is acceptable on the proviso that the result-set is consistent, if outdated. However, this condition isn’t necessarily true either, as the following example shows.

There are two transactions, T1 and T2, and two items, X and YT1 starts by getting a read lock on a copy of X (with the notation R(X)), and subsequently gets a read lock for Y. However, another transaction, T2, has committed an update to both X and Y after T1 obtained a read lock on X but before it obtained a read lock on Y.

T1 completes its query by returning an old value of X and the current value of Y. The result is inconsistent.

Figure 6: Serializability of RWC

This is only a problem because the first transaction obtained read locks for both tables separately. If the system uses a centralized lock manager, locks can be taken out at the same time, making the result consistent. However, a centralized lock manager creates a point of contention (and failure), so it may not be desirable to have one.

Alternatives

Its probably doubtful that you’d want to use this approach in practise. If your application can accept outdated but consistent data then a more expressive multi-version system may be more appropriate. My point is to show what happens when you expand or relax basic pessimistic approaches.

RWC is a two-phase locking approach to multi-version concurrency control. The alternative istimestamp ordering: each transaction is given a unique start timestamp, while data items are given read and write timestamps that are equal to the timestamp of the last timestamp to read or write the item.

Reads and updates never block. If an operation is a read then it accesses the version with the largest timestamp less than the reading transaction. The read timestamp is then updated. If an operation is an update then a new version of the item is created with the timestamp of the updating transaction, provided that a more recent transaction has not read an older version of the data than the updating transaction. In this case the transaction is aborted.

Serializability is ensured by aborting transactions which access data out of timestamp order.

Finally

Every concurrency control mechanism is designed with three things in mind: the degree of concurrency provided (obviously), the potential for deadlock, and the level of consistency that is guaranteed.

Because there is no definitive solution for any of these, concurrency control models vary widely based on their target application. Most of the fundamental research on the topic was done over thirty years ago, so for further reading you can either go back to that work or look at some more recent textbooks. The following texts were useful to me:

Deadlock in Database Systems

Deadlock is what occurs when two or more transactions are waiting on each other to release a lock. Neither can move, and so both stall.

To combat this, a system can either prevent deadlock from occurring, or detect when it does happen and act accordingly.

Models for Concurrency Control

To understand how deadlock occurs in database systems it helps to understand the role of various concurrency control techniques. I’m going to discuss two popular approaches.

Two-phase locking (2PL) is commonly used to guarantee serializability in database systems. In this model a transaction can either obtain a shared or exclusive lock for an item, but all locking operations must occur before the first unlock operation. The name refers to the two phases that result from this: the expanding phase where locks are acquired, and the shrinking phase where locks are released.

There are a number of variations on this model. Conservative 2PL requires that all locks are taken out at the beginning of the transaction, whereas Rigorous 2PL requires that all locks are held until after the transaction commits (or aborts). The former collapses the expanding phase, while the latter collapses the shrinking phase.

Timestamp-based concurrency control involves using unique transaction timestamps in place of conventional locks. Concurrency control is based on the ordering of timestamps. So, for example, when a transaction accesses an item, the system checks whether this transaction is older than the last one which accessed the item. If this is the case the transaction proceeds; otherwise ordering is violated and the transaction is aborted. Such strict timestamp-based approaches can lead to the cyclic restart of transactions and starvation.

Multi-version concurrency control (MVCC) also incorporates timestamps by allowing several versions of an item to be stored. This allows the system to present a consistent (but potentially historical) version of the database to queries, meaning fewer reads are rejected than with basic timestamp ordering.

Optimistic concurrency control (OCC) allows multiple transactions to read and update items without blocking. However, before a transaction is committed the database must check for conflicts – if any are found one of the conflicting transactions is rolled back.

Deadlock Prevention

For deadlock to occur four conditions need to be true (meaning you need to break one to prevent deadlock):

Mutual Exclusion – a resource cannot be held by more than one transaction at a time. This condition is true of database systems using two 2PL where an exclusive lock is required on updates. Systems using OCC don’t hold locks, and so break this condition.

Hold and Wait – transactions already holding resources can request further resources.Conservative 2PL breaks this condition, since it requires all locks to be acquired from the outset. However this isn’t always desirable as it limits concurrency.

No pre-emption – a resource cannot be forcibly removed from a transaction. Pre-emption is used in timestamp-based approaches. Two of the most commonly used schemes are wait-dieand wound-wait. In wait-die (non-preemptive), if a transaction tries to lock an item which is already locked, it waits if the holder of the lock is a younger transaction (based on timestamp); otherwise it will abort. In wound-wait (pre-emptive), instead of waiting as before, the transaction aborts the other younger transaction. If it is the younger transaction it waits.

Circular wait – a number of transactions form a circular chain where each transaction is waiting for a resource that a later transaction (in the chain) holds. This can be prevented by imposing a total ordering on resources, requiring that each transaction requests locks on resources in an agreed order. This may not be possible in some forms of 2PL where locks are not taken out at a single point in time (e.g. rigorous 2PL).

Many of these approaches aren’t ideal because they result in transactions being aborted at the slightest chance of deadlock. In situations where deadlock will rarely occur (for example, when transactions are mostly short-lived and lightweight) detection is more practical.

Deadlock Detection

Deadlock detection involves periodically checking whether the system is in a state of deadlock. There are two basic methods of detection: timeouts and wait-for graphs.

Timeouts represent the simplest method of detection. If a transaction waits for a period longer than some constant timeout period it will be aborted. This method has a low overhead, but may end up aborting transactions even in the absence of deadlock.

Another approach is for the system to construct a wait-for graph. Each node in the graph represents an active transaction. A directed edge is drawn between two transactions when one transaction is waiting for a lock on an item held by the other transaction. Deadlock exists (and is detected) when there is a cycle in the graph. At this point the system engages in victim selection, where one of the transactions is chosen to be aborted. The challenge in this technique is deciding when and how often to check for deadlock in the graph.

For More Information

Hopefully this post provides enough information to give a good understanding of the subject area. If you want to know more I’d recommend looking at some of the material I used while writing this post:

This is a cross-post from my previous site at the University of St Andrews.