Transactional locking semantics allow reliable concurrent access of data by multiple parties. Data structure accessed by concurrent threads can benefit by the introduction of transactional locking. However, common thread packages offer basic locking primitives at a lower level than transactional locking.
In part one of the article, we will discuss the issues of locking policies. In a second follow on article, we will discuss the design of transactional locks using primitive thread locks.
In the design of a database, a primary consideration is the requirement of allowing multiple users concurrent access of data. Even though there are multiple users, each individual user must be able to operate as if the data is being used by one user. This requirement is usually implemented by locking the data to be accessed. Different levels of locks are provided to allow better concurrency, while protecting the integrity of data.
The following table lists the different locking levels, and the compatibilities between each locking levels.
| Already Granted Lock | Requested Lock | ||||
|---|---|---|---|---|---|
| IR | R | U | IW | W | |
| Intention Read (IR) | yes | yes | yes | yes | no |
| Read (R) | yes | yes | yes | no | no |
| Upgrade (U) | yes | yes | no | no | no |
| Intention Write (IW) | yes | no | no | yes | no |
| Write (W) | no | no | no | no | no |
A read lock is required before reading on a data item. A write lock is required before writing on a data item. Multiple parties can read on a data item with no problem. This is indicated in the table by looking at the intersection of requested lock (read), and already granted lock (read also). We should find the 'yes' compatibility label in the intersection. On the other hand, one cannot write on a data item while there are still readers out there. Similarly, one cannot read on a data item while there is a writer out there. For practice, look up these two statements in the compatibility table.
In early database systems, read and write locks are the only locks available. In practice, it was discovered that lock upgrading causes too many deadlocks. Deadlock is a condition in where no one can access the database, because locks are blocked on each other. For example, a party reads on a data item, then writes on the same data item later. It would request a read lock followed by a write lock. If there is a second party doing the same thing at the same time, then deadlock can occur. Since read locks do not block each other, the two parties will share the read locks. When the two parties issue the write locks, they would be waiting for each other to release the read lock. This would never happen, as both parties are stopped in their forward progress.
Upgrade locks are designed to partially resolve this problem. When a party at the first reading of a data item, if it knows it will update it later, then an upgrade lock can be requested in place of a read lock. The difference between upgrade lock and read lock is that two upgrade locks conflict with each other. We can repeat the previous deadlock example to determine that with upgrade locks the deadlock situation is avoided. Each party will request upgrade lock, followed by write lock. The first party to acquire the upgrade lock would prevent the entry of the other party on an upgrade lock. It is only until the first party completes its task and drops its locks, then the second party can acquire the upgrade lock. There is no deadlock.
The disadvantage of the upgrade lock is that its usage requires the power of prediction. Programmer need to use application logic to determine when upgrade locks can be used. If upgrade locks are used indiscriminately in situations where an update does not follow, read concurrency can be negatively impacted.
Intention locks allow for lock management in nested database structures. If a database contains a million records, updating all the records would require a million write locks. It is more efficient to have a single write lock on the whole database level. Having a multi-level database locking structure requires locking requests to travel from higher level to lower level.
Intention locks are placed in the order from high to low level. Request to read a record would need intention read locks on the parent levels. Request to write a record would need intention write locks on the parent levels. Two requests to write different child records do not conflict on the parent level. This is reflected by the fact that two intention write locks do not conflict with each other. However, a request to write a child record would conflict with a request to read all data at the parent level. This is reflected by the fact that an intention write lock conflicts with read locks.
There are a number of locking policies that should be considered as part of the locking design. The policy issues revolve around efficiency, and fairness. The default locking mechanism would need to make some choices to satisfy the typical clients. Modifications on the defaults can be provided to satisfy clients with very specific locking requirements.
The typical locking problems are the writer starvation problem, deadlock problem, and convoy problem.
An implementation may decide to check if a lock request is compatible with the current lock holder. If they are compatible, immediately grant the lock request. Such policy may cause writer starvation problem if there are a large number of read requests. If a reader was granted a read lock, then fellow readers can immediately join in. However, writers will be blocked out, until all readers have finished. In fact, some unlucky writers may get blocked indefinitely.
A solution is to use FIFO (first in, first out) policy to queue up the requests. Only requests at the front of the queue can try to get the lock. However, concurrency and efficiency may be negatively impacted. Some opportunities for parallel access will be lost. Queue processing is serial in nature.
A naive implementation of FIFO policy can lead to deadlock situation where a non-FIFO implementation may avoid it.
Here is an example to illustrate the point. Client X holds a read lock, and client Y is queued up for a write lock. If client X requests for a write lock, the system must grant it if it is to avoid a deadlock. Say we put client X's write lock request to the back of the queue. That would mean client X would be blocked to wait until client Y finished its request. Client Y would also not make any forward progress as it is waiting on client X to release the read lock. The circular waiting results in a deadlock.
From this observation, lock granting priority must be given to the parties who already own some kind of locks.
Sometimes deadlocks are the result of chance alone, and unavoidable. Time-out followed by rollback of the transaction would cause the release of the locks responsible for the deadlock.
Frequently, the detection of the deadlock itself is not practical. Rather a timeout period is specified. If a lock cannot be satisfied during the timeout period, then the system would assume deadlock has occurred, and abort the lock request. The duration of the timeout period can be a parameter in the locking system.
The problem of convoying is well known in the situation of a FIFO policy. When the lock duration is very short, but frequent in the completion of a task, convoy may develop.
Say a client must lock and unlock an object 100 times to complete its task. Each lock / unlock pair occurs very close together. In addition, there are many such clients in the system. If one client is blocked while holding the lock, all other clients would immediately be queued up behind it. The queue would never shrink, and process throughput would be severely impacted. Each client can only do one lock / unlock pair before it is kicked to the back of the queue. The process scheduler would then make up a large percentage of CPU usage.
The solution of convoying is to allow a client chance to regrab a lock after it has released it. The head waiter can also grab the lock if it gets the chance. It is a race between the original owner, and the head waiter. The client has the potential of working longer before it get blocked. The solution is not without problem, as a client can hog a lock for quite a while before the lock is given to someone else. There has to be a time limit to how long a client can re-acquire a lock, possibly user settable in units of 1/100 seconds. A default setting of 1 second may be suitable.
The identity of the client who made a lock request needs to be determined before a lock can be granted. Depending on the context, the current thread ID may or may not be sufficient.
In distributed internet situations, the proper identification of the client is a problem that is yet to be solved. Given the possibility of spoofs, and man-in-the-middle attacks, the identification mechanism would need to stand up in measures of security. My links on internet security may provide some background information on this topic.
There are different mechanisms how the lock release mechanism can be managed. The data item in charge of the lock can release it when the data item is informed by the client that the client is done with the data. Alternatively, a global lock manager can keep track of the outstanding locks kept by various clients. A single 'unlock all' command then can be issued to the lock manager to unlock all locks kept by a certain client. For single process application, the lock manager may provide a simple interface for unlocking. For distributed applications, it may be dangerous to register locks to an external entity that claims to be a lock manager. In cases the data item self manages lock release, the issue of the lock manager is not relevant.
In this article, we have covered the required semantics of a transactional locking service. What remains to be done is to lay down a concrete design, on defining the detailed service interface. That will occur in a follow on article, concentrating on a transactional locking service for Java.