Abstract
Many popular database management systems implement a multiversion concurrency control algorithm called snapshot isolation rather than providing full serializability based on locking. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that would maintain consistency if run serially. Until now, the only way to prevent these anomalies was to modify the applications by introducing explicit locking or artificial update conflicts, following careful analysis of conflicts between all pairs of transactions.
This article 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 of the algorithm in a relational DBMS is described, along with a benchmark and performance study, showing that the throughput approaches that of snapshot isolation in most cases.
- Adya, A. 1999. Weak consistency: A generalized theory and optimistic implementations for distributed transactions. Ph.D. thesis, Laboratory for Computer Science, Massachusetts Institute of Technology. Google ScholarDigital Library
- Agrawal, R., Carey, M. J., and McVoy, L. 1987. The performance of alternative strategies for dealing with deadlocks in database management systems. IEEE Trans. Softw. Eng. 13, 12, 1348--1363. Google ScholarDigital Library
- Alomari, M., Cahill, M. J., Fekete, A., and Röhm, U. 2008. The cost of serializability on platforms that use snapshot isolation. In Proceedings of the 24th International Conference on Data Engineering (ICDE). 576--585. Google ScholarDigital Library
- Berenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E., and O'Neil, P. 1995. A critique of ANSI SQL isolation levels. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). ACM Press, 1--10. Google ScholarDigital Library
- Bernstein, A., Lewis, P., and Lu, S. 2000. Semantic conditions for correctness at different isolation levels. In Proceedings of the 16th International Conference on Data Engineering (ICDE). IEEE, 57--66. Google ScholarDigital Library
- Bernstein, P. A. and Goodman, N. 1983. Multiversion concurrency control—theory and algorithms. ACM Trans. Datab. Syst. (TODS) 8, 4, 465--483. Google ScholarDigital Library
- Bober, P. M. and Carey, M. J. 1992. On mixing queries and transactions via multiversion locking. In Proceedings of the Eighth International Conference on Data Engineering (ICDE). IEEE Computer Society, Washington, DC, 535--545. Google ScholarDigital Library
- Cahill, M. J., Röhm, U., and Fekete, A. D. 2008. Serializable isolation for snapshot databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York, NY, 729--738. Google ScholarDigital Library
- Carey, M. J. and Muhanna, W. A. 1986. The performance of multiversion concurrency control algorithms. ACM Trans. Comput. Syst. 4, 4, 338--378. Google ScholarDigital Library
- Chan, A., Dayal, U., Fox, S., Goodman, N., Ries, D. R., and Skeen, D. 1983. Overview of an ADA compatible distributed database manager. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York, NY, 228--237. Google ScholarDigital Library
- Eswaran, K. P., Gray, J., Lorie, R. A., and Traiger, I. L. 1976. The notions of consistency and predicate locks in a database system. Comm. ACM 19, 11, 624--633. Google ScholarDigital Library
- Fekete, A. 1999. Serializability and snapshot isolation. In Proceedings of the Australian Database Conference. Australian Computer Society, 201--210.Google Scholar
- Fekete, A. 2005. Allocating isolation levels to transactions. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, New York, NY, 206--215. Google ScholarDigital Library
- Fekete, A., Liarokapis, D., O'Neil, E., O'Neil, P., and Shasha, D. 2005. Making snapshot isolation serializable. ACM Trans. Datab. Syst. 30, 2, 492--528. Google ScholarDigital Library
- Fekete, A., O'Neil, E., and O'Neil, P. 2004. A read-only transaction anomaly under snapshot isolation. ACM SIGMOD Record 33, 3, 12--14. Google ScholarDigital Library
- Gray, J. and Reuter, A. 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann. Google ScholarDigital Library
- Hadzilacos, T. 1988. Serialization graph algorithms for multiversion concurrency control. In Proceedings of the 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). ACM, New York, NY, 135--141. Google ScholarDigital Library
- Jacobs, K., Bamford, R., Doherty, G., Haas, K., Holt, M., Putzolu, F., and Quigley, B. 1995. Concurrency control, transaction isolation and serializability in SQL92 and Oracle7. Oracle White Paper, Part No A33745.Google Scholar
- Jorwekar, S., Fekete, A., Ramamritham, K., and Sudarshan, S. 2007. Automating the detection of snapshot isolation anomalies. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB). VLDB Endowment, 1263--1274. Google ScholarDigital Library
- Kung, H. T. and Robinson, J. T. 1981. On optimistic methods for concurrency control. ACM Trans. Datab. Syst. 6, 2, 213--226. Google ScholarDigital Library
- Lomet, D. B. 1993. Key range locking strategies for improved concurrency. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann Publishers Inc., San Francisco, CA, 655--664. Google ScholarDigital Library
- Mohan, C. 1990. ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on b-tree indexes. In Proceedings of the 16th International Conference on Very Large Databases (VLDB). Morgan Kaufmann Publishers Inc., 392--405. Google ScholarDigital Library
- Mohan, C. and Levine, F. 1992. ARIES/IM: an efficient and high concurrency index management method using write-ahead logging. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). ACM, New York, NY, 371--380. Google ScholarDigital Library
- Mohan, C., Pirahesh, H., and Lorie, R. 1992. Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). ACM, New York, NY, 124--133. Google ScholarDigital Library
- MySQL AB. 2006. MySQL Administrator's Guide and Language Reference 2nd Ed. MySQL Press. Google ScholarDigital Library
- Olson, M. A., Bostic, K., and Seltzer, M. I. 1999. Berkeley DB. In Proceedings of the USENIX Annual Technical Conference, FREENIX Track. 183--191. Google ScholarDigital Library
- Raz, Y. 1993. Commitment ordering-based distributed concurrency control for bridging single and multi version resources. In Proceedings of the 3rd International Workshop or Research Issues in Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS). IEEE, 189--198.Google ScholarCross Ref
- Reed, D. P. 1978. Naming and synchronization in a decentralized computer system. Tech. rep., MIT, Cambridge, MA. Google ScholarDigital Library
- Reed, D. P. 1983. Implementing atomic actions on decentralized data. ACM Trans. Comput. Syst. 1, 1, 3--23. Google ScholarDigital Library
- Sarin, S. 2009. Dynamic transaction serializability in netezza performance server. New England Database Day, http://db.csail.mit.edu/nedbday09/htdocs/papers.php.Google Scholar
- Shi, V. T.-S. and Perrizo, W. 2002. A new method for concurrency control in centralized database systems. In Computers and Their Applications, R. E. Gantenbein and S. Y. Shin, Eds. ISCA, 184--187.Google Scholar
- Tada, H., Higuchi, M., and Fujii, M. 1997. A concurrency control algorithm using serialization graph testing with write deferring. Trans. Inform. Proc. Soc. Japan 38, 10 (Oct.).Google Scholar
- Transaction Processing Performance Council. 2005. TPC-C benchmark specification. http://www.tpc.org/tpcc.Google Scholar
- Weihl, W. E. 1987. Distributed version management for read-only actions. IEEE Trans. Softw. Eng. 13, 1, 55--64. Google ScholarDigital Library
- Weikum, G. and Vossen, G. 2002. Transactional Information Systems: Theory, Algorithms and the Practice of Concurrency Control and Recovery. Morgan Kaufmann. Google ScholarDigital Library
- Yang, Y. 2007. The adaptive serializable snapshot isolation protocol for managing database transactions. M.S. thesis, University of Wollongong, NSW Australia.Google Scholar
Index Terms
Serializable isolation for snapshot databases
Recommendations
Serializable isolation for snapshot databases
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of dataMany 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 ...
A critique of snapshot isolation
EuroSys '12: Proceedings of the 7th ACM european conference on Computer SystemsThe support for transactions is an essential part of a database management system (DBMS). Without this support, the developers are burdened with ensuring atomic execution of a transaction despite failures as well as concurrent accesses to the database ...
Making snapshot isolation serializable
Snapshot Isolation (SI) is a multiversion concurrency control algorithm, first described in Berenson et al. [1995]. SI is attractive because it provides an isolation level that avoids many of the common concurrency anomalies, and has been implemented by ...
Comments