A new approach to developing and implementing eager database replication protocols

ABSTRACT

Database replication is traditionally seen as a way to increase the availability and performance of distributed databases. Although a large number of protocols providing data consistency and fault-tolerance have been proposed, few of these ideas have ever been used in commercial products due to their complexity and performance implications. Instead, current products allow inconsistencies and often resort to centralized approaches which eliminates some of the advantages of replication. As an alternative, we propose a suite of replication protocols that addresses the main problems related to database replication. On the one hand, our protocols maintain data consistency and the same transactional semantics found in centralized systems. On the other hand, they provide flexibility and reasonable performance. To do so, our protocols take advantage of the rich semantics of group communication primitives and the relaxed isolation guarantees provided by most databases. This allows us to eliminate the possibility of deadlocks, reduce the message overhead and increase performance. A detailed simulation study shows the feasibility of the approach and the flexibility with which different types of bottlenecks can be circumvented.

REFERENCES

• 1: Atul Adya , Barbara H. Liskov, Weak consistency: a generalized theory and optimistic implementations for distributed transactions, 1999
• 2: Generalized Isolation Level Definitions, Proceedings of the 16th International Conference on Data Engineering, p.67, February 28-March 03, 2000
• 3: Divyakant Agrawal , Gustavo Alonso , Amr El Abbadi , Ioana Stanoi, Exploiting Atomic Broadcast in Replicated Databases (Extended Abstract), Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.496-503, August 26-29, 1997
• 4: D. Agrawal , A. El Abbadi , R. C. Steinke, Epidemic algorithms in replicated databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-172, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263680]
• 5: D. Agrawal , A. El Abbadi, The tree quorum protocol: an efficient approach for managing replicated data, Proceedings of the sixteenth international conference on Very large databases, p.243-254, September 1990, Brisbane, Australia
• 6: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 7: ALONSO, G. 1997. Partial database replication and group communication primitives. In Proceedings of European Research Seminar on Advances in Distributed Systems (Zinal, Switzerland, Mar.).
• 8: G. Alonso , B. Reinwald , C. Mohan, Distributed data management in workflow environments, Proceedings of the 7th International Workshop on Research Issues in Data Engineering (RIDE '97) High Performance Database Management for Large-Scale Applications, p.82, April 07-08, 1997
• 9: Gustavo Alonso , Divyakant Agrawal , Amr El Abbadi , Mohan Kamath , Roger Günthör , C. Mohan, Advanced Transaction Models in Workflow Contexts, Proceedings of the Twelfth International Conference on Data Engineering, p.574-581, February 26-March 01, 1996
• 10: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• 11: Todd Anderson , Yuri Breitbart , Henry F. Korth , Avishai Wool, Replication, consistency, and practicality: are these mutually exclusive?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.484-495, June 01-04, 1998, Seattle, Washington, United States
• 12: ANSI. 1992. X3.135-1992. American National Standard for Information Systems-Database Languages-SQL.
• 13: Catriel Beeri , Philip A. Bernstein , Nathan Goodman, A model for concurrency in nested transactions systems, Journal of the ACM (JACM), v.36 n.2, p.230-269, April 1989 [doi>10.1145/62044.62046]
• 14: 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
• 15: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 16: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 17: 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
• 18: 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]
• 19: William Bridge , Ashok Joshi , M. Keihl , Tirthankar Lahiri , Juan Loaiza , N. MacNaughton, The Oracle Universal Server Buffer, Proceedings of the 23rd International Conference on Very Large Data Bases, p.590-594, August 25-29, 1997
• 20: Stefano Ceri , Maurice A. W. Houtsma , Arthur M. Keller , Pierangela Samarati, A classification of update methods for replicated databases, Stanford University, Stanford, CA, 1991
• 21: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112627]
• 22: CHEN, S. -W. AND PU, C. 1992. A structural classification of integrated replica control mechanisms. Tech. Rep. CUCS-006-92. Columbia University, New York, NY.
• 23: Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990
• 24: 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
• 25: Danny Dolev , Dalia Malki, The Transis approach to high availability cluster communication, Communications of the ACM, v.39 n.4, p.64-70, April 1996 [doi>10.1145/227210.227227]
• 26: A. El Abbadi , S. Toueg, Maintaining availability in partitioned replicated databases, ACM Transactions on Database Systems (TODS), v.14 n.2, p.264-290, June 1989 [doi>10.1145/63500.63501]
• 27: 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]
• 28: Roy Friedman , Robbert van Renesse, Packing Messages as a Tool for Boosting the Performance of Total Ordering Protocols, Cornell University, Ithaca, NY, 1995
• 29: FRIEDMAN, R. AND VAN RENESSE, R. 1995b. Strong and weak virtual synchrony in Horus. Tech Rep. TR-95-1537. Department of Computer Science, Cornell University, Ithaca, NY.
• 30: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 31: GOLDRING, R. 1994. A discussion of relational database replication technology. InfoDB 8,1.
• 32: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 33: GRAY, J., LORIE, R., PUTZOLU, G., AND TRAIGER, I. 1976. Granularity of locks and degrees of consistency in a shared database. In Modeling in Data Base Mangement Systems. Elsevier North-Holland, Inc., Amsterdam, The Netherlands.
• 34: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 35: Rachid Guerraoui , André Schiper, Transaction Model vs. Virtual Synchrony Model: Bridging the Gap, Selected Papers from the International Workshop on Theory and Practice in Distributed Systems, p.121-132, September 05-09, 1994
• 36: Ramesh Gupta , Jayant Haritsa , Krithi Ramamritham, Revisiting commit processing in distributed database systems, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.486-497, May 11-15, 1997, Tucson, Arizona, United States
• 37: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 38: JoAnne Holliday , Divykant Agrawal , Amr El Abbadi, The Performance of Database Replication with Group Multicast, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.158, June 15-18, 1999
• 39: Bettina Kemme , Gustavo Alonso, A Suite of Database Replication Protocols based on Group Communication Primitives, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.156, May 26-29, 1998
• 40: Fernando Pedone , André Schiper, Optimistic Atomic Broadcast, Proceedings of the 12th International Symposium on Distributed Computing, p.318-332, September 24-26, 1998
• 41: Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance in replicated systems, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.63-74, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113419]
• 42: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 43: Michael J. Carey , Miron Livny, Parallelism and concurrency control performance in distributed database machines, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.122-133, June 1989, Portland, Oregon, United States
• 44: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 45: MOSER, L. E., AMIR, Y., MELLIAR-SMITH, P. M., AND AGARWAL, D. A. 1994. Extended virtual synchrony. In Proceedings of the 14th IEEE International Conference on Distributed Computing Systems (ICDCS '94, Poznan, Poland, June). IEEE Computer Society Press, Los Alamitos, CA, 56-65.
• 46: L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , R. K. Budhia , C. A. Lingley-Papadopoulos, Totem: a fault-tolerant multicast group communication system, Communications of the ACM, v.39 n.4, p.54-63, April 1996 [doi>10.1145/227210.227226]
• 47: Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.248-262, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62588]
• 48: ORACLE. 1995. Concurrency control, transaction isolation and serializability in SQL92 and Oracle7. White paper.
• 49: ORACLE. 1997. Oracle8(TM) Server Replication: Concepts Manual.
• 50: 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
• 51: Fernando Pedone , Rachid Guerraoui , Andre Schiper, Transaction Reordering in Replicated Databases, Proceedings of the 16th Symposium on Reliable Distributed Systems (SRDS '97), p.175, October 22-24, 1997
• 52: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 53: Michael Rabinovich , Narain H. Gehani , Alex Kononov, Scalable Update Propagation in Epidemic Replicated Databases, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.207-222, March 25-29, 1996
• 54: SCHIPER, A. AND SANDOZ, A. 1993. Uniform reliable multicast in a virtually synchronous environment. In Proceedings of the 13th International Conference on Distributed Computing Systems (ICDCS '93, Pittsburgh, PA). 561-568.
• 55: Dennis Shasha, Lessons from Wall Street: case studies in configuration, tuning, and distribution, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.498-501, May 11-15, 1997, Tucson, Arizona, United States
• 56: Jeff Sidell , Paul M. Aoki , Adam Sah , Carl Staelin , Michael Stonebraker , Andrew Yu, Data Replication in Mariposa, Proceedings of the Twelfth International Conference on Data Engineering, p.485-494, February 26-March 01, 1996
• 57: STACEY, D. 1994. Replication: DB2, Oracle, or Sybase. Database Program. Des. 7, 12.
• 58: I. Stanoi , D. Agrawal , A. El Abbadi, Using Broadcast Primitives in Replicated Databases, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.148, May 26-29, 1998
• 59: STONEBRAKER, M. 1979. Concurrency control and consistency of multiple copies of data in distributed INGRES. IEEE Trans. Softw. Eng. SE-5, 3 (May), 188-194.
• 60: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]
• 61: WHITNEY, A., SHASHA, D., AND APTER, S. 1997. High volume transaction processing without concurrency control, two phase commit, SQL or C++. In Proceedings of the International Workshop on High Performance Transaction Systems (Asilomar, CA, Sept.).

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Transaction processing

General Terms:
Algorithms, Management, Performance, Reliability

Keywords:
database replication, fault-tolerance, group communication, isolation levels, one-copy-serializability, replica control, total error multicast