Isolation Testing

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

Contact Information

Patrick O'Neil
Department of Mathematics and Computer Science
University of Massachusetts at Boston
Boston, MA 02125
Home Office Phone: (617) 661-1054
Home Office Fax : (617) 354-6460
Email: poneil@cs.umb.edu
Home Page: http:/www.cs.umb.edu/~poneil

Project WWW Page

http:/www.cs.umb.edu/~isotest

Keywords

transaction, isolation level, performance, concurrency, update

Project Award Information

Award Number: IRI 97-11374
Duration: 3 years, now 1st year.
Title: Isolation Testing

Project Summary

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.

Goals, Objectives, and Targeted Activities

We were awarded this grant in September of 1997.

We are currently developing a utility to test isolation on given database products by running a canonical set of transactional threads to execute a transactional history. Be have brought up three major database systems on our departmental computers: Oracle 8, DB2 UDB, and Informix IUS. We expect this activity to help us extend notation for transactional histories, to meet the need explained in the original proposal, e.g.. to develop a notation that handles predicate locking, etc. This notation would eventually be used in the Isolation Testing Utility.

We have also started to design a performance application benchmark to measure benefits of using different isolation levels on canonical applications. We expect during the Summer, when we will have our Consultants visiting, to be doing work on the theoretical underpinnings of isolation levels, and to locate an appropriate industry partner to determine problems that may arise in their applications under different isolation levels.

Indication of Success

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 at an early stage as of now, but the potential for new transactional insights clearly justifies the funding.

Project Impact

Include a brief discussion on the impact of the project on

Human Resources: We have two students working on this project, one of whom is a Ph.D. candidate working toward his degree in this area.
Education and curriculum development at all levels: Patrick O'Neil has developed some notes on Isolation Levels in a graduate course he developed on Database Internals.
Your department/institution infrastructure: Patrick O'Neil and Elizabeth O'Neil are co-PI's and paying student salaries, with the help of the Grant Development Office.
Industry -- collaborations, transfer of technology, patents: Collaboration with industry is planned; transfer of technology is quite likely; we have no plans to take patents on the work at present, since we feel it is basic research that should be freely available to all. We might ask for student aid from companies who want us to help with transfer of technology.

What activities have been enabled/spawned because of the accomplishments made possible by your award? One student is being supported on his Doctoral topic.

Project References

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.

[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.

Area Background

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.

Area References

In order of difficulty, references follow.

[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.

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

Potential Related Projects

The project is too new at present to think about spawning more projects or collaborations. We expect to think of such connections after more progress has been made.