Revisiting 1-copy equivalence in clustered databases

ABSTRACT

Recently renewed interest in scalable database systems for shared nothing clusters has been supported by replication protocols based on group communication that are aimed at seamlessly extending the native consistency criteria of centralized database management systems. By using a read-one/write-all-available approach and avoiding the fine-grained synchronization associated with traditional distributed locking, one needs just a single distributed interaction step for each update transaction. Therefore the system can easily be scaled to a large number of replicas, especially, with read intensive loads typical of Web server support environments.In this paper we point out that 1-copy equivalence for causal consistency, which is subsumed by both serializability and snapshot isolation criteria, depends on basic session guarantees that are costly to ensure in clusters, especially in a multi-tier environment. We then point out a simple solution that guarantees causal consistency in the Database State Machine protocol and evaluate its performance, thus highlighting the cost of seamlessly providing common consistency criteria of centralized databases in a clustered environment.

REFERENCES

• 1: Atul Adya , Barbara H. Liskov, Weak consistency: a generalized theory and optimistic implementations for distributed transactions, 1999
• 2: M. Ahamad, G. Neiger, P. Kohli, J. Burns, and P. Hutto. Causal memory: definitions, implementation and programming. Distributed Computing, 9(1), Sept. 1995.
• 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: J. Brzeziński, C. Sobaniec, and D. Wawrzyniak. From session causality to causal consistency. In Euromicro Conf. on Parallel, Distributed and Network-Based Processing, 2004.
• 5: Navin Budhiraja , Keith Marzullo , Fred B. Schneider , Sam Toueg, The primary-backup approach, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 6: 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]
• 7: A. Correia Jr., A. Sousa, L. Soares, J. Pereira, F. Moura, and R. Oliveira. Group-based replication of on-line transaction processing servers. In 2nd Latin-American Symposium on Dependable Computing, 2005.
• 8: Sameh Elnikety , Willy Zwaenepoel , Fernando Pedone, Database Replication Using Generalized Snapshot Isolation, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05), p.73-84, October 26-28, 2005 [doi>10.1109/RELDIS.2005.14]
• 9: Rachid Guerraoui , André Schiper, Software-Based Replication for Fault Tolerance, Computer, v.30 n.4, p.68-74, April 1997 [doi>10.1109/2.585156]
• 10: Ricardo Jiménez-Peris , M. Patiño-Martínez , Gustavo Alonso , Bettina Kemme, Are quorums an alternative for data replication?, ACM Transactions on Database Systems (TODS), v.28 n.3, p.257-294, September 2003 [doi>10.1145/937598.937601]
• 11: Bettina Kemme , Gustavo Alonso, Don't Be Lazy, Be Consistent: Postgres-R, A New Way to Implement Database Replication, Proceedings of the 26th International Conference on Very Large Data Bases, p.134-143, September 10-14, 2000
• 12: 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]
• 13: Marta Patiño-Martínez , Ricardo Jiménez-Peris , Bettina Kemme , Gustavo Alonso, Scalable Replication in Database Clusters, Proceedings of the 14th International Conference on Distributed Computing, p.315-329, October 04-06, 2000
• 14: 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]
• 15: A. Sousa , J. Pereira , L. Soares , A. Correia Jr. , F. Moura, Testing the Dependability and Performance of Group Communication Based Database Replication Protocols, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.792-801, June 28-July 01, 2005 [doi>10.1109/DSN.2005.90]
• 16: Douglas B. Terry , Alan J. Demers , Karin Petersen , Mike J. Spreitzer , Marvin M. Theimer , Brent B. Welch, Session guarantees for weakly consistent replicated data, Proceedings of the third international conference on on Parallel and distributed information systems, p.140-150, October 1994, Autin, Texas, United States
• 17: T. P. P. C. (TPC). TPC Benchmark#8482; C standard specification revision 5.0, Feb. 2001.
• 18: 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
• 19: 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 (ICDE'05), p.422-433, April 05-08, 2005 [doi>10.1109/ICDE.2005.108]
• 20: V. Zuikeviciute and F. Pedone. Revisiting the database state machine approach. In VLDB Wks. on Design, Implementation and Deployment of Database Replication, 2005.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency; Transaction processing
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Design, Management, Security