Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The widespread use of clusters and Web farms has increased the importance of data replication. In this article, we show how to implement consistent and scalable data replication at the middleware level. We do this by combining transactional concurrency control with group communication primitives. The article presents different replication protocols, argues their correctness, describes their implementation as part of a generic middleware, Middle-R, and proves their feasibility with an extensive performance evaluation. The solution proposed is well suited for a variety of applications including Web farms and distributed object platforms.

REFERENCES

• 1: D. A. Agarwal , L. E. Moser , P. M. Melliar-Smith , R. K. Budhia, The Totem multiple-ring ordering and topology maintenance protocol, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.93-132, May 1998 [doi>10.1145/279227.279228]
• 2: Amir, Y., Danilov, C., Miskin-Amir, M., Stanton, J., and Tutu, C. 2002. Practical wide area database replication. Tech. rep. CNDS-2002-1. Johns Hopkins University, Baltimore, MD.
• 3: Yair Amir , Ciprian Tutu, From Total Order to Database Replication, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.494, July 02-05, 2002
• 4: Amza, C., Cox, A. L., and Zwaenepoel, W. 2003. Distributed versioning consistent replication for scaling back-end databases for dynamic content Web sites. In Proceedings of ACM/IFIP/USENIX International Middleware Conference. Lecture Notes in Computer Science, vol. 2672. Springer, Berlin, Germany, 282--304.
• 5: 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 [doi>10.1145/276304.276347]
• 6: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 7: Philip A. Bernstein , David W. Shipman , James B. Rothnie, Jr., Concurrency control in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.18-51, March 1980 [doi>10.1145/320128.320131]
• 8: Kenneth P. Birman, Building Secure and Reliable Network Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1996
• 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 [doi>10.1145/304182.304191]
• 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: Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
• 12: Miguel Castro , Rodrigo Rodrigues , Barbara Liskov, BASE: Using abstraction to improve fault tolerance, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.236-269, August 2003 [doi>10.1145/859716.859718]
• 13: 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]
• 14: 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
• 15: Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004 [doi>10.1145/1041680.1041682]
• 16: Jean-Charles Fabre , Tanguy Pérennou, A Metaobject Architecture for Fault-Tolerant Distributed Systems: The FRIENDS Approach, IEEE Transactions on Computers, v.47 n.1, p.78-95, January 1998 [doi>10.1109/12.656088]
• 17: Pascal Felber , Rachid Guerraoui , André Schiper, The implementation of a CORBA object group service, Theory and Practice of Object Systems, v.4 n.2, p.93-105, April 1998 [doi>10.1002/(SICI)1096-9942(1998)4:2<93::AID-TAPO4>3.3.CO;2-E]
• 18: Friedman, R. and van Renesse, R. 1995. Strong and weak virtual synchrony in Horus. Tech. rep. TR95-1537. Computer Science Department, Cornell University, Ithaca, NY.
• 19: Gançarski, S., Naacke, H., Pacitti, E., and Valduriez, P. 2005. The Leganet system: Freshness-aware transaction routing in a database structure. Inform. Syst. To appear.
• 20: 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 [doi>10.1145/233269.233330]
• 21: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 22: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 23: Mark Hayden, The Ensemble System, Cornell University, Ithaca, NY, 1998
• 24: 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
• 25: JoAnne Holliday , Divyakant Agrawal , Amr El Abbadi, Using Multicast Communication to Reduce Deadlock in Replicated Databases, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.196, October 16-18, 2000
• 26: R. Jiménez-Peris , M. Patiño-Martínez , G. Alonso, Non-Intrusive, Parallel Recovery of Replicated Data, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.150, October 13-16, 2002
• 27: Ricardo Jiménez-Peris , Marta Patiño-Martínez , Gustavo Alonso , Sergio Arévalo, A Low-Latency Non-blocking Commit Service, Proceedings of the 15th International Conference on Distributed Computing, p.93-107, October 03-05, 2001
• 28: Jiménez-Peris, R., Patiño-Martinez, M., Alonso, G., and Kemme, B. 2002b. Scalable database replication middleware. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS, Vienna, Austria). IEEE Computer Society Press, Los Alamitos, CA, 477--484.
• 29: 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]
• 30: 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
• 31: 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]
• 32: Bettina Kemme , Alberto Bartoli , Özalp Babaoglu, Online Reconfiguration in Replicated Databases Based on Group Communication, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.117-130, July 01-04, 2001
• 33: Kemme, B., Pedone, F., Alonso, G., Schiper, A., and Wiesmann, M. 2003. Using optimistic atomic broadcast in transaction processing systems. IEEE Trans. Knowl. Data Eng. 15, 4, 1018--1032.
• 34: Kistijantoro, A. I., Morgan, G., Shrivastava, S. K., and Little, M. C. 2003. Component replication in distributed systems: A case study using Enterprise Java Beans. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Florence, Italy). IEEE Computer Society Press, Los Alamitos, CA, 89--98.
• 35: Maffeis, S. 1995. Adding group communication and fault-tolerance to CORBA. In USENIX Conference on Object-Oriented Technologies (Monterey, CA). USENIX, Berkeley, 135--146.
• 36: Graham Morgan , Santosh K. Shrivastava , Paul D. Ezhilchelvan , Mark C. Little, Design and implemantation of a CORBA fault-tolerant object group service, Proceedings of the IFIP WG 6.1 International Working Conference on Distributed Applications and Interoperable Systems II, p.361-374, June 28-July 01, 1999
• 37: 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]
• 38: P. Narasimhan , L. E. Moser , P. M. Melliar-Smith, Eternal: a component-based framework for transparent fault-tolerant CORBA, Software—Practice & Experience, v.32 n.8, p.771-788, 10 July 2002 [doi>10.1002/spe.458]
• 39: Balachandran Natarajan , Aniruddha Gokhale , Shalini Yajnik , Douglas C. Schmidt, DOORS: Towards High-Performance Fault Tolerant CORBA, Proceedings of the International Symposium on Distributed Objects and Applications, p.39, September 21-23, 2000
• 40: OMG. 2000. Fault Tolerant CORBA. Object Management Group, Needham, MA.
• 41: Esther Pacitti , Eric Simon, Update propagation strategies to improve freshness in lazy master replicated databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.305-318, February 2000 [doi>10.1007/s007780050010]
• 42: 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
• 43: Fernando Pedone Svend Frlund, Pronto: A Fast Failover Protocol for Off-the-Shelf Commercial Databases, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.176, October 16-18, 2000
• 44: 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
• 45: Fernando Pedone , Rachid Guerraoui , André Schiper, Exploiting Atomic Broadcast in Replicated Databases, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.513-520, September 01-04, 1998
• 46: 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]
• 47: António Sousa , José Pereira , Francisco Moura , Rui Oliveira, Optimistic Total Order in Wide Area Networks, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.190, October 13-16, 2002
• 48: PostgreSQL. 1998. v6.4.2. Go online to http://www.postgresql.com.
• 49: Yansong (Jennifer) Ren , David E. Bakken , Tod Courtney , Michel Cukier , David A. Karr , Paul Rubel , Chetan Sabnis , William H. Sanders , Richard E. Schantz , Mouna Seri, AQuA: An Adaptive Architecture that Provides Dependable Distributed Objects, IEEE Transactions on Computers, v.52 n.1, p.31-50, January 2003 [doi>10.1109/TC.2003.1159752]
• 50: Rodrigues, L., Miranda, H., Almeida, R., Martins, J., and Vicente, P. 2002. Strong replication in the GlobData middleware. In Proceedings of the International Workshop on Middleware-Based Systems (part of DSN). IEEE Computer Society Press, Los Alamitos, CA, G96--G104.
• 51: Dale Skeen , David D. Wright, Increasing availability in partitioned database systems, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588054]
• 52: 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
• 53: Pedro Vicente , Luís Rodrigues, An Indulgent Uniform Total Order Algorithm with Optimistic Delivery, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.92, October 13-16, 2002
• 54: 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
• 55: Wool. A. 1998. Quorum systems in replicated databases: Science or fiction? Data Eng. Bull. 21, 4, 3--11.
• 56: Wenbing Zhao , Louise E. Moser , P. Michael Melliar-Smith, Unification of Transactions and Replication in Three-Tier Architectures Based on CORBA, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.20-33, January 2005 [doi>10.1109/TDSC.2005.14]
• 57: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Reliability, availability, and serviceability; Fault tolerance

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

General Terms:
Algorithms, Performance, Reliability

Keywords:
Database replication, eager data replication, middleware, scalability