Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Altruistic locking
Salem K., García-Molina H., Shands J. ACM Transactions on Database Systems19 (1):117-165,1994.Type:Article
Date Reviewed: Apr 1 1995

Long-lived transactions (LLTs) have historically caused processing problems for large, transaction-driven database systems. Such transactions tend to lock a large number of database objects for a long period of time, causing delays in other transactions. In order to handle LLTs, some operational systems defer their processing to off hours, especially if they update a large number of database objects.

Salem, Garcia-Molina, and Shands approach the problem in a different way. Instead of treating database objects as owned by specific transactions (the standard approach of two-phase locking), the authors propose to treat LLTs as leaving a wake of locked records behind them as they progress through the database. Other transactions, if they run in the wake of an LLT, can unlock and use database objects that are no longer needed.

The authors’ extension to the traditional two-phase locking protocols would include rules allowing LLTs to “donate” unneeded records when through with them (hence the term “altruistic locking”). This would permit other transactions to access and unlock the donated records and complete their processing without having to wait for the LLT to complete. In order to guarantee recovery, the LLT would not be able to donate records that it has added or changed until a database commit occurred. Likewise, the transaction running in the wake of another must not access records outside of that wake until the LLT performs its first unlock operation.

The stated purpose of the paper is to propose an extension to the standard two-phase database locking protocol that would allow the running of short transactions in the wake of LLTs. The extensive discussion clearly explains how this can be done, exploring all aspects of blocking and queueing, waiting for objects to be unlocked, recovery processing, and extensions to the basic altruistic locking rules. The theoretical ideas are backed up with simulated results showing substantially better performance when altruistic locking is implemented.

The best feature of the paper is its readability. By using standard database terminology and explaining all new terms before using them, the authors have ensured that the reader is easily able to move through the paper with a minimum of confusion. In some respects, though, the 50-page discussion seems a bit long to cover the subject.

Perhaps the paper’s worst feature is the authors’ misunderstanding of the purpose of savepoints. The authors contend that altruistic locking greatly improves performance as long as LLTs use infrequent write locks for update purposes. The dismissal of savepoints as a solution to this problem because they do not guarantee failure atomicity at the transaction level shows a misunderstanding of how savepoints should operate. Savepoints are defined as logical points in a transaction’s update operation where processing can be rolled back to and restarted in case of an abort. In effect, savepoints preclude the need for failure atomicity at the transaction level because they provide it at the transaction processing sublevel. When a transaction reaches a savepoint, commits are initiated for all locked records up to that point in processing, and then transaction processing continues. Savepoints have been successfully implemented for LLTs for over two decades (since IBM IMS DL/1 in 1973), and their proper implementation would allow altruistic locking to be used for long update transactions.

Overall, the paper is well written and thought-provoking for general students of database technology. It is also a good source of ideas for vendors of database management systems who want to improve their products. The bibliography includes a good mix of theoretical and practical references for background information. In short, I would recommend the paper to anyone with an interest in transaction-based processing systems.

Reviewer:  R. J. Tufts Review #: CR118214
Bookmark and Share
 
Deadlock Avoidance (H.2.2 ... )
 
 
Transaction Processing (H.2.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Deadlock Avoidance": Date
Invariant-based verification of a distributed deadlock detection algorithm
Kshemkalyani A., Singhal M. (ed) IEEE Transactions on Software Engineering 17(9): 789-799, 1991. Type: Article
May 1 1993
Database concurrency control using data flow graphs
Eich M., Wells D. ACM Transactions on Database Systems 13(2): 197-227, 1988. Type: Article
Jan 1 1990

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy