Isolation Testing for Transactional Systems

Patrick O'Neil (*)
Elizabeth O'Neil (*)
Dennis Shasha, Consultant (**)
Alan Fekete, Consultant (***)

(*) Department of Mathematics and Computer Science, University of Massachusetts at Boston
(**) Courant Institute of Mathematical Sciences
(***) University of Sydney

Dimitrios Liarokapis, PhD student, University of Massachusetts at Bosto
Denis Rinfret, PhD student, University of Massachusetts at Boston

transaction, isolation level, performance, concurrency, update

The idea of executing a transactional system under a lower isolation level than perfect Serializable isolation was introduced in a 1977 paper by IBM researchers, and implemented in IBM's DB2. It is now offered by most commercial DBMS systems supporting multi-user applications. Lower isolation levels permit more transactional threads to simultaneously execute an application, so processor resources are more effectively utilized. The tradeoff is this: in perfect isolation, no update performed by one application thread can have any effect on data read and updated by an independent transactional thread; in lower isolation levels this is no longer the case. The intent is to use lower isolation levels only for "safe" applications, where the application code will not use isolation weaknesses to arrive at erroneous results. But the database field has no general method for deciding what applications are "safe". The ultimate goal of this project is to develop a method for evaluating large transactional application systems to determine what errors can arise at different isolation levels in common commercial use. This process of evaluation is to be known as Isolation Testing, and provides a list of all isolation problems that can occur in the workload. It is often possible then to make modest changes in the database and application design to eliminate these errors and gain the advantage of a lower isolation level. Isolation Testing has the potential to make many of the largest commercial applications (banking, airline reservation) more efficient in their use of computer resources.

Since the Grant award in September 1997, we have developed a utility to test isolation on given database products by running a canonical set of transactional threads executing ad-hoc transactional histories written in an extended transactional notation we developed to include predicate evaluation. We have begun testing histories on various isolation levels offered by three major database systems we are running on our departmental computers: Oracle 8, DB2 UDB, and Informix DS/UD. The extended notation for transactional histories meets a need explained in the original proposal, e.g.. to develop a notation that handles predicate locking, etc., and we intend to extend the notation for use in the Application Isolation Testing Utility.

We expect to publish papers on the fundamental work being done, possibly leading to a monograph on the underlying theory. As time goes on, we expect to have database vendors express interest in transferring some of the technology. An Isolation Testing Utility is a prefectly salable piece of Middleware. The Project is still at an early stage, butwe are beginning to make some progress, as explained in the next section.

We have also started to design a performance application benchmark to measure benefits of using different isolation levels on canonical applications. We are still trying to locate an appropriate industry partner to determine problems that may arise in their applications under different isolation levels.

The isolation testing utility explained in the first paragraph of the previous section is already a useful capability, both in practice and theory. No previous transactional notation was able to deal with predicate situations, leaving all discussions of "Phantoms" to be expressed only in error-prone English.

We have developed a method of testing an application to determine when "Snapshot Isolation" works with Serializable effect (as for example the TPC-C benchmark was claimed by ORACLE to run serializably under their SERIALIZABLE isolation level; ORACLE's SERIALIZABLE is actually Snapshot Isolation, and therefore subject to concurrency anomalies, not actually guaranteed to be serializable in effect). We have also found an algorithm to strengthen Snapshot Isolation by performing runtime checks, an approach that does away with any type of data item anomaly. These results are currently being written up for publication.

Patrick O'Neil collaborated with Atul Adya and Barbara Liskov, both of MIT (Atul is scheduled to joing Microsoft Research in the near future), on a result of Atul's thesis that Patrick felt offered a possible basis for a new Isolation Level standard. (The current one was shown to have problems in [BBGMOO95], see Project References). The result has been written up and communicated to senior practitioners in the transactional field and is being submitted for publication.

Reference papers or other sources of more information about your project (e.g., on-line demos, availability of the data/software for downloading, etc.). Each reference should be separated by a blank line, including annotated URLs as appropriate.

References to 5-10 papers or other sources of more information about your project.

[ANSI92] ANSI X3.135-1992, "American National Standard for Information Systems Ñ Database Language Ñ SQL," November, 1992.

[BBGMOO95] Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil, "A Critique of ANSI SQL Isolation Levels", Proc. ACM SIGMOD 1995, pp. 1-10.

[BHG87] P. A. Bernstein, V. Hadzilacos, and N. Goodman, "Concurrency Control and Recovery in Database Systems," Addison-Wesley, 1987.

[CETAL81] Chamberlin, D., et al., "A History and Evaluation of System R," Comm. ACM, 24(10), 1981, pp. 632-646.

[EGLT76] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger, "The Notions of Consistency and Predicate Locks in a Database System," Comm. ACM, Nov. 1976, vol. 19, no. 11, pp. 624-633.

[EGLT76] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger, "The Notions of Consistency and Predicate Locks in a Database System," Comm. ACM, Nov. 1976, vol. 19, no. 11, pp. 624-633.

[LMWF94] Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete, "Atomic Transactions," Morgan Kaufmann, 1994.

David Lomet, "Key Range Locking Strategies for Improved Concurrency," Proc. ACM SIGMOD 1993, pp. 655-664.

[MOH90] C. Mohan, "Aries/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction transactions Operating on B-tree Indexes," Proc. 16th VLDB Conference, 1990, pp. 392-405.

[SLSV95] Dennis Shasha, Francois Llirbat, Eric Simon, and Patrick Valduriez, "Transaction Chopping: Algorithms and Performance Studies," ACM TODS, Vol. 20, No. 3, Sept. 1995, pp. 325-363.

Here, we'd like you to write a very brief introduction to your discipline (a couple of paragraphs). The technical level should be suitable for someone from a different discipline but with some familiarity with the IDM topics. Primarily, this introduction should help the interested researchers to understand your area and how it could relate to his/her own work. Include annotated URLs as appropriate.

When database information is updated by numerous users simulataneously, there is some risk that two users will update the same piece of information at the same time, or one will read information that is simultaneously being updated by another. This leads to Anomalies that cause errors in application logic. To guard against such anomalies, the database system offers a mechanism known as transactions that walls off the ongoing results of one user from another. This is a guarantee known as Isolation. The study of how Isolation can be implemented, with possible relaxation of some of the most stringent rules that wall transactions from one another, is the subject of our project. Transactions run significantly faster at lower isolation levels, to an extent we'll measure. Of course we need to ensure that no anomalies happen at the lowered isolation levels, for each particular application.

[PO94] Patrick O'Neil, "Database: Principles, Programming, and Performance," Morgan Kaufmann, 1994, (Fourth Printing, 1997).

[BHG87] P. A. Bernstein, V. Hadzilacos, and N. Goodman, "Concurrency Control and Recovery in Database Systems," Addison-Wesley, 1987. (Download from: http://research.microsoft.com/pubs/ccontrol/default.htm)

[GR93] Jim Gray and Andreas Reuter, "Transaction Processing: Concepts and Techniques," Morgan Kaufmann 1993. (Second corrected printing, 1994)

We have not yet started to think about spawning more projects or collaborations. We expect to think of such connections after more progress has been made.