Serializable isolation for snapshot databases

ABSTRACT

Many popular database management systems offer snapshot isolation rather than full serializability. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that individually maintain consistency. Until now, the only way to prevent these anomalies was to modify the applications by introducing artificial locking or update conflicts, following careful analysis of conflicts between all pairs of transactions.

This paper describes a modification to the concurrency control algorithm of a database management system that automatically detects and prevents snapshot isolation anomalies at runtime for arbitrary applications, thus providing serializable isolation. The new algorithm preserves the properties that make snapshot isolation attractive, including that readers do not block writers and vice versa. An implementation and performance study of the algorithm are described, showing that the throughput approaches that of snapshot isolation in most cases.

REFERENCES

• 1: Atul Adya , Barbara H. Liskov, Weak consistency: a generalized theory and optimistic implementations for distributed transactions, Massachusetts Institute of Technology, 1999
• 2: M. Alomari, M. Cahill, A. Fekete, and U. Röhm. The cost of serializability on platforms that use snapshot isolation. In ICDE '08: Proceedings of the 24th International Conference on Data Engineering, 2008.
• 3: Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.1-10, May 22-25, 1995, San Jose, California, United States
• 4: Semantic Conditions for Correctness at Different Isolation Levels, Proceedings of the 16th International Conference on Data Engineering, p.57, February 28-March 03, 2000
• 5: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• 6: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 7: A. Fekete. Serializability and snapshot isolation. In Proceedings of Australian Database Conference, pages 201--210. Australian Computer Society, January 1999.
• 8: Alan Fekete, Allocating isolation levels to transactions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065193]
• 9: Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable, ACM Transactions on Database Systems (TODS), v.30 n.2, p.492-528, June 2005 [doi>10.1145/1071610.1071615]
• 10: Alan Fekete , Elizabeth O'Neil , Patrick O'Neil, A read-only transaction anomaly under snapshot isolation, ACM SIGMOD Record, v.33 n.3, September 2004 [doi>10.1145/1031570.1031573]
• 11: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 12: Thanasis Hadzilacos, Serialization graph algorithms for multiversion concurrency control, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.135-141, March 1988, Austin, Texas, United States [doi>10.1145/308386.308426]
• 13: K. Jacobs, R. Bamford, G. Doherty, K. Haas, M. Holt, F. Putzolu, and B. Quigley. Concurrency control, transaction isolation and serializability in SQL92 and Oracle7. Oracle White Paper, Part No A33745, 1995.
• 14: K. Jacobs, R. Bamford, G. Doherty, K. Haas, M. Holt, F. Putzolu, and B. Quigley. Concurrency control, transaction isolation and serializability in SQL92 and Oracle7. Oracle White Paper, Part No A33745, 1995.
• 15: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, Proceedings of the fifth international conference on Very Large Data Bases, p.351-351, October 03-05, 1979, Rio de Janeiro, Brazil
• 16: Michael A. Olson , Keith Bostic , Margo Seltzer, Berkeley DB, Proceedings of the annual conference on USENIX Annual Technical Conference, p.43-43, June 06-11, 1999, Monterey, California
• 17: Y. Raz. Commitment ordering based distributed concurrency control for bridging single and multi version resources. In Proceedings of Third International Workshop or Research Issues in Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), pages 189--198. IEEE, June 1993.
• 18: V. T.-S. Shi and W. Perrizo. A new method for concurrency control in centralized database systems. In R. E. Gantenbein and S. Y. Shin, editors, Computers and Their Applications, pages 184--187. ISCA, 2002.
• 19: David Gerard Sullivan , Margo I. Seltzer, Using probabilistic reasoning to automate software tuning, Harvard University, Cambridge, MA, 2003
• 20: Transaction Processing Performance Council. TPC-C Benchmark Specification. http://www.tpc.org/tpcc, 2005.
• 21: Y. Yang. The adaptive serializable snapshot isolation protocol for managing database transactions. Master's thesis, University of Wollongong, NSW Australia, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Performance, Reliability

Keywords:
multiversion concurrency control, serializability theory, snapshot isolation