Snapshot isolation and integrity constraints in replicated databases

ABSTRACT

Database replication is widely used for fault tolerance and performance. However, it requires replica control to keep data copies consistent despite updates. The traditional correctness criterion for the concurrent execution of transactions in a replicated database is 1-copy-serializability. It is based on serializability, the strongest isolation level in a nonreplicated system. In recent years, however, Snapshot Isolation (SI), a slightly weaker isolation level, has become popular in commercial database systems. There exist already several replica control protocols that provide SI in a replicated system. However, most of the correctness reasoning for these protocols has been rather informal. Additionally, most of the work so far ignores the issue of integrity constraints. In this article, we provide a formal definition of 1-copy-SI using and extending a well-established definition of SI in a nonreplicated system. Our definition considers integrity constraints in a way that conforms to the way integrity constraints are handled in commercial systems. We discuss a set of necessary and sufficient conditions for a replicated history to be producible under 1-copy-SI. This makes our formalism a convenient tool to prove the correctness of replica control algorithms.

REFERENCES

• 1: Atul Adya , Barbara H. Liskov, Weak consistency: a generalized theory and optimistic implementations for distributed transactions, Massachusetts Institute of Technology, 1999
• 2: Generalized Isolation Level Definitions, Proceedings of the 16th International Conference on Data Engineering, p.67, February 28-March 03, 2000
• 3: Mohammad Alomari , Michael Cahill , Alan Fekete , Uwe Rohm, The Cost of Serializability on Platforms That Use Snapshot Isolation, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.576-585, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497466]
• 4: Cristiana Amza , Alan L. Cox , Willy Zwaenepoel, Distributed versioning: consistent replication for scaling back-end databases of dynamic content web sites, Proceedings of the ACM/IFIP/USENIX 2003 International Conference on Middleware, June 16-20, 2003, Rio de Janeiro, Brazil
• 5: ANSI X3.135-1992. 1992. American National Standard for Information Systems—Database Language- SQL.
• 6: 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
• 7: Philip A. Bernstein , Alan Fekete , Hongfei Guo , Raghu Ramakrishnan , Pradeep Tamma, Relaxed-currency serializability for middle-tier caching and replication, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142540]
• 8: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 9: Yuri Breitbart , Raghavan Komondoor , Rajeev Rastogi , S. Seshadri , Avi Silberschatz, Update propagation protocols for replicated databates, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.97-108, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: Yuri Breitbart , Henry F. Korth, Replication and consistency: being lazy helps sometimes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.173-184, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263681]
• 11: Michael J. Cahill , Uwe Röhm , Alan D. Fekete, Serializable isolation for snapshot databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376690]
• 12: Michael J. Carey , Miron Livny, Conflict detection tradeoffs for replicated data, ACM Transactions on Database Systems (TODS), v.16 n.4, p.703-746, Dec. 1991 [doi>10.1145/115302.115289]
• 13: Emmanuel Cecchet , Julie Marguerite , Willy Zwaenepole, C-JDBC: flexible database clustering middleware, Proceedings of the annual conference on USENIX Annual Technical Conference, p.26-26, June 27-July 02, 2004, Boston, MA
• 14: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 15: Parvathi Chundi , Daniel J. Rosenkrantz , S. S. Ravi, Deferred Updates and Data Placement in Distributed Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.469-476, February 26-March 01, 1996
• 16: Khuzaima Daudjee , Kenneth Salem, Lazy database replication with snapshot isolation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 17: Sameh Elnikety , Willy Zwaenepoel , Fernando Pedone, Database Replication Using Generalized Snapshot Isolation, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.73-84, October 26-28, 2005 [doi>10.1109/RELDIS.2005.14]
• 18: 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]
• 19: Stéphane Gançarski , Hubert Naacke , Esther Pacitti , Patrick Valduriez, The leganet system: Freshness-aware transaction routing in a database cluster, Information Systems, v.32 n.2, p.320-343, April, 2007 [doi>10.1016/j.is.2005.09.004]
• 20: JoAnne Holliday , Robert Steinke , Divyakant Agrawal , Amr El Abbadi, Epidemic Algorithms for Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1218-1238, September 2003 [doi>10.1109/TKDE.2003.1232274]
• 21: Bettina Kemme , Gustavo Alonso, A new approach to developing and implementing eager database replication protocols, ACM Transactions on Database Systems (TODS), v.25 n.3, p.333-379, Sept. 2000 [doi>10.1145/363951.363955]
• 22: Yi Lin , Bettina Kemme , Marta Patiño-Martínez , Ricardo Jiménez-Peris, Middleware based data replication providing snapshot isolation, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066205]
• 23: Microsoft SQL Server 2005. 2007. SQL Server 2005 row versioning-based transaction isolation.
• 24: F. D. Munoz-Esco , J. Pla-Civera , M. I. Ruiz-Fuertes , L. Irun-Briz , H. Decker , J. E. Armendariz-Inigo , J. R. Gonzalez de Mendivil, Managing Transaction Conflicts in Middleware-based Database Replication Architectures, Proceedings of the 25th IEEE Symposium on Reliable Distributed Systems, p.401-420, October 02-04, 2006 [doi>10.1109/SRDS.2006.29]
• 25: Oracle Corporation. 2007. Oracle 11g Release 1.
• 26: Esther Pacitti , Pascale Minet , Eric Simon, Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases, Proceedings of the 25th International Conference on Very Large Data Bases, p.126-137, September 07-10, 1999
• 27: Marta Patiño-Martinez , Ricardo Jiménez-Peris , Bettina Kemme , Gustavo Alonso, MIDDLE-R: Consistent database replication at the middleware level, ACM Transactions on Computer Systems (TOCS), v.23 n.4, p.375-423, November 2005 [doi>10.1145/1113574.1113576]
• 28: Fernando Pedone , Rachid Guerraoui , André Schiper, The Database State Machine Approach, Distributed and Parallel Databases, v.14 n.1, p.71-98, July 2003 [doi>10.1023/A:1022887812188]
• 29: Francisco Perez-Sorrosal , Marta Patiño-Martinez , Ricardo Jimenez-Peris , Bettina Kemme, Consistent and scalable cache replication for multi-tier J2EE applications, Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware, November 26-30, 2007, Newport Beach, California
• 30: Christian Plattner , Gustavo Alonso, Ganymed: scalable replication for transactional web applications, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 31: Christian Plattner , Gustavo Alonso , M. Tamer Özsu, Extending DBMSs with satellite databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.657-682, July 2008 [doi>10.1007/s00778-006-0026-x]
• 32: PostgreSQL. 2007. PostgreSQL, the world's most advanced open source database.
• 33: Uwe Röhm , Klemens Böhm , Hans-Jörg Schek , Heiko Schuldt, FAS: a freshness-sensitive coordination middleware for a cluster of OLAP components, Proceedings of the 28th international conference on Very Large Data Bases, p.754-765, August 20-23, 2002, Hong Kong, China
• 34: Ralf Schenkel , Gerhard Weikum , Norbert Weißenberg , Xuequn Wu, Federated Transaction Management with Snapshot Isolation, Selected papers from the Eight International Workshop on Foundations of Models and Languages for Data and Objects, Transactions and Database Dynamics, p.1-25, September 27-30, 1999
• 35: Gerhard Weikum , Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 36: Shuqing Wu , Bettina Kemme, Postgres-R(SI): Combining Replica Control with Concurrency Control Based on Snapshot Isolation, Proceedings of the 21st International Conference on Data Engineering, p.422-433, April 05-08, 2005 [doi>10.1109/ICDE.2005.108]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Reliability, Theory, Verification

Keywords:
Replication, integrity constraints, snapshot isolation