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: