More Web Proxy on the site http://driver.im/

article

MIDDLE-R: Consistent database replication at the middleware level

Authors:

Marta Patiño-Martinez,

Ricardo Jiménez-Peris,

Gustavo AlonsoAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 23, Issue 4

Pages 375 - 423

https://doi.org/10.1145/1113574.1113576

Published: 01 November 2005 Publication History

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]

Agarwal, D., Moser, L., Melliar-Smith, P. M., and Budhia, R. 1998. The Totem Multiple-Ring Ordering and Topology Maintenance Protocol. ACM Trans. Comput. Syst. 16, 2, 93-- 132.

[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]

Amir, Y. and Tutu, C. 2002. From total order to database replication. In Proceedings of the IEEE Conference on Distributed Computer Systems (ICDCS, Vienna, Austria). IEEE Computer Society Press, Los Alamitos, CA, 494--506.

[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]

Anderson, T., Breitbart, Y., Korth, H. F., and Wool, A. 1998. Replication, consistency, and practicality: Are these mutually exclusive? In Proceedings of the ACM International Conference on Management of Data (SIGMOD, Seattle, WA). ACM Press, New York, NY, 484--495.

[6]

Bernstein, P. A., Hadzilacos, V., and Goodman, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, MA.

[7]

Bernstein, P. A., Shipman, D., and Rothnie, J. B. 1980. Concurrency control in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 5, 1, 18--51.

[8]

Birman, K. 1996. Building Secure and Reliable Network Applications. Prentice Hall, Englewood Cliffs, NJ.

[9]

Breitbart, Y., Komondoor, R., Rastogi, R., Seshadri, S., and Silberschatz, A. 1999. Update propagation protocols for replicated databases. In Proceedings of the ACM International Conference on Management of Data (SIGMOD, Philadelphia, PA). ACM Press, New York, NY, 97--108.

[10]

Breitbart, Y. and Korth, H. F. 1997. Replication and consistency: Being lazy helps sometimes. In Proceedings of the ACM International Conference on Principles of Database Systems (PODS, Tucson, AZ). ACM Press, New York, NY, 173--184.

[11]

Castro, M. and Liskov, B. 2002. Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20, 4, 398--461.

[12]

Castro, M., Rodrigues, R., and Liskov, B. 2003. BASE: Using abstraction to improve fault tolerance. ACM Trans. Comput. Syst. 21, 3 (Aug.), 236--269.

[13]

Chockler, G. V., Keidar, I., and Vitenberg, R. 2001. Group communication specifications: A comprehensive study. ACM Comput. Surv. 33, 4 (Dec.), 427--469.

[14]

Chundi, P., Rosenkrantz, D. J., and Ravi, S. S. 1996. Deferred updates and data placement in distributed databases. In Proceedings of the ACM International Conference on Data Engineering (ICDE, New Orleans, LA). IEEE Computer Society Press, New York, NY, 469-- 476.

[15]

Défago, X., Schiper, A., and Urbán, P. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36, 4, 372--421.

[16]

Fabre, J. C. and Perennou, T. 1998. A metaobject architecture for fault-tolerant distributed systems. IEEE Trans. Comput. Syst. 47, 1, 78--95.

[17]

Felber, P., Guerraoui, R., and Schiper, A. 1998. The implementation of a CORBA Object Group Service. Theor. Pract. Obj. Syst. 4, 2, 93--105.

[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]

Gray, J., Helland, P., O'Neil, P., and Shasha, D. 1996. The dangers of replication and a solution. In Proceedings of the ACM International Conference on Management of Data (SIGMOD, Montreal, P.Q., Canada). ACM Press, New York, NY, 173--182.

[21]

Gray, J. and Reuter, A. 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers, San Mateo, CA.

[22]

Hadzilacos, V. and Toueg, S. 1993. Fault-tolerant broadcasts and related problems. In Distributed Systems. Addison Wesley, Reading, MA, 97--145.

[23]

Hayden, M. 1998. The Ensemble system. Tech. rep. TR-98-1662. Department of Computer Science. Cornell University, Ithaca, NY.

[24]

Holliday, J., Agrawal, D., and Abbadi, A. E. 1999. The performance of database replication with group communication. In Proceedings of the IEEE International Conference on Fault-Tolerant Computing Systems (FTCS). IEEE Computer Society Press, Los Alamitos, CA, 158--165.

[25]

Holliday, J., Agrawal, D., and Abbadi, A. E. 2000. Using multicast communication to reduce deadlock in replicated databases. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Nuremberg, Germany). IEEE Computer Society Press, Los Alamitos, CA, 196--205.

[26]

Jiménez-Peris, R., Patiño-Martinez, M., and Alonso, G. 2002a. Non-intrusive, parallel recovery of replicated data. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Osaka, Japan). IEEE Computer Society Press, Los Alamitos, CA, 150--159.

[27]

Jiménez-Peris, R., Patiño-Martinez, M., Alonso, G., and Arevalo, S. 2001. A low-latency non-blocking atomic commitment. In Proceedings of the IEEE International Symposium on Distributed Computing (DISC, Lisbon, Portugal). Lecture Notes in Computer Science, vol. 2180. Springer, Berlin, Germany, 93--107.

[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]

Jiménez-Peris, R., Patiño-Martinez, M., Alonso, G., and Kemme, B. 2003. Are quorums an alternative for data replication? ACM Trans. Database Syst. 28, 3, 257--294.

[30]

Kemme, B. and Alonso, G. 2000a. Don't be lazy, be consistent: Postgres-R, a new way to implement database replication. In Proceedings of the International Conference on Very Large Databases (VLDB, Cairo, Egypt). Morgan Kaufmann Publishers, San Mateo, CA, 134--143.

[31]

Kemme, B. and Alonso, G. 2000b. A new approach to developing and implementing eager database replication protocols. ACM Trans. Database Syst. 25, 3 (Sept.), 333--379.

[32]

Kemme, B., Bartoli, A., and Babaoglu, O. 2001. Online reconfiguration in replicated databases based on group communication. In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN, Göteborg, Sweden). IEEE Computer Society Press, Los Alamitos, CA, 117--130.

[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]

Morgan, G., Shrivastava, S., Ezhilchelvan, P., and Little, M. 1999. Design and implementation of a CORBA fault-tolerant Object Group Service. In 2nd IFIP WG 6.1 International Working Conference on Distributed Applications and Interoperable Systems (DAIS, Helsinki, Finland). Kluwer Academic Publishers, Dordrecht, The Netherlands, 361--374.

[37]

Moser, L., Melliar-Smith, P., Agarwal, D., Budhia, R., and Lingley-Papadopoulos, C. 1996. Totem: A fault-tolerant multicast group communication system. Commun. ACM 39, 4 (Apr.), 54--63.

[38]

Narasimhan, P., Moser, L. E., and Melliar-Smith, P. M. 2002. Eternal---A component-based framework for transparent fault-tolerant CORBA. Softw. Pract. Exper. 32, 8, 771--788.

[39]

Natarajan, B., Gokhale, A., Yajnik, S., and Schmidt, D. C. 2000. DOORS: Towards high-performance fault-tolerant CORBA. In Proceedings of the IEEE International Symposium on Distributed Objects and Applications (DOA, Antwerp, Belgium). IEEE Computer Society Press, Los Alamitos, CA, 39--48.

[40]

OMG. 2000. Fault Tolerant CORBA. Object Management Group, Needham, MA.

[41]

Pacitti, E. and Simon, E. 2000. Update propagation strategies to improve freshness in lazy master replicated databases. VLDB J. 8, 3, 305--318.

[42]

Patiño-Martinez, M., Jiménez-Peris, R., Kemme, B., and Alonso, G. 2000. Scalable Replication in Database Clusters. In International Distributed Computing Conference (DISC, Toledo, Spain). Lecture Notes in Computer Science, vol. 1914. Springer, Berlin, Germany, 315-- 329.

[43]

Pedone, F. and Frolund, S. 2000. Pronto: A fast failover protocol for off-the-shelf commercial databases. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Nuremberg, Germany). IEEE Computer Society Press, Los Alamitos, CA, 176--185.

[44]

Pedone, F., Guerraoui, R., and Schiper, A. 1997. Transaction reordering in replicated databases. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Durham, NC). IEEE Computer Society Press, Los Alamitos, CA, 175--182.

[45]

Pedone, F., Guerraoui, R., and Schiper, A. 1998. Exploiting atomic broadcast in replicated databases. In Euro-Par International Conference (Southampton, U.K.). Lecture Notes in Computer Science, vol. 1470. Springer, Berlin, Germany, 513--520.

[46]

Pedone, F., Guerraoui, R., and Schiper, A. 2003. The database state machine approach. Distrib. Parall. Databases 14, 1, 71--98.

[47]

Pinto Ferreira de Sousa, A. L., Orlando Pereira, J., Moura, F., and Oliveira, R. C. 2002. Optimistic total order in wide area networks. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Osaka, Japan). IEEE Computer Society Press, Los Alamitos, CA, 190--201.

[48]

PostgreSQL. 1998. v6.4.2. Go online to http://www.postgresql.com.

[49]

Ren, J., Bakken, D. E., Courtney, T., Cukier, M., Karr, D. A., Rubel, P., Sabnis, C., Sanders, W. H., Schantz, R. E., and Mouna, S. 2003. AQuA: An adaptive architecture that provides dependable distributed objects. IEEE Trans. Comput. 52, 1, 31--50.

[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]

Skeen, D. and Wright, D. D. 1984. Increasing availability in partitioned database systems. In Proceedings of the ACM International Conference on Principles of Database Systems (PODS, Waterloo, Ont., Canada). ACM Press, New York, NY, 290--299.

[52]

Stanoi, I., Agrawal, D., and El Abbadi, A. 1998. Using broadcast primitives in replicated databases. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS, Amsterdam, The Netherlands). IEEE Computer Society Press, Los Alamitos, CA, 148--155.

[53]

Vicente, P. and Rodrigues, L. 2002. An indulgent uniform total order algorithm with optimistic delivery. In Proceedings of the IEEE International Symposium on Reliable Distributed Systems (SRDS, Osaka, Japan). IEEE Computer Society Press, Los Alamitos, CA, 92--101.

[54]

Weikum, G. and Vossen, G. 2001. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann Publishers, San Mateo, CA.

[55]

Wool. A. 1998. Quorum systems in replicated databases: Science or fiction? Data Eng. Bull. 21, 4, 3--11.

[56]

Zhao, W., Moser, L. E., and Melliar-Smith, P. M. 2005. Unification of transactions and replication in three-tier architectures based on CORBA. IEEE Trans. Depend. Secure Comput. 2, 1 (Jan.--March), 20--33.

[57]

Zhou, L., Schneider, F. B., and van Renesse, R. 2002. COCA: A secure distributed online certification authority. ACM Trans. Comput. Syst. 20, 4, 329--368.

Cited By

Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Kraft PLi QZhou XBailis PStonebraker MZaharia MYu X(2023)Epoxy: ACID Transactions across Diverse Data StoresProceedings of the VLDB Endowment10.14778/3611479.361148416:11(2742-2754)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611484
Coelho FAlonso AFerreira LPereira JOliveira R(2023)Loom: A Closed-Box Disaggregated Database SystemProceedings of the 12th Latin-American Symposium on Dependable and Secure Computing10.1145/3615366.3615424(30-39)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3615366.3615424
Show More Cited By

Index Terms

MIDDLE-R: Consistent database replication at the middleware level

Recommendations

SIPRe: a partial database replication protocol with SI replicas
SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

Database replication has been researched as a solution to overcome the problems of performance and availability of distributed systems. Full database replication, based on group communication systems, is an attempt to enhance performance that works well ...
Implementing database replication protocols based on O2PL in a middleware architecture
DBA'06: Proceedings of the 24th IASTED international conference on Database and applications

Database replication is a way to increase system performance and fault-tolerance of a given system. The price to pay is the effort needed to guarantee data consistency, and this is not an easy task. In this paper, we introduce a description of two 1-...
k-bound GSI: a flexible database replication protocol
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Several previous works have proven that there is no way of guaranteeing a snapshot isolation level in symmetrical replicated database systems without blocking transactions when they are started. As a result of this, the generalized snapshot isolation (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 23, Issue 4

November 2005

137 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/1113574

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2005

Published in TOCS Volume 23, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
1,558
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)7

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Kraft PLi QZhou XBailis PStonebraker MZaharia MYu X(2023)Epoxy: ACID Transactions across Diverse Data StoresProceedings of the VLDB Endowment10.14778/3611479.361148416:11(2742-2754)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611484
Coelho FAlonso AFerreira LPereira JOliveira R(2023)Loom: A Closed-Box Disaggregated Database SystemProceedings of the 12th Latin-American Symposium on Dependable and Secure Computing10.1145/3615366.3615424(30-39)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3615366.3615424
Pacheco LDotti FPedone F(2022)Strengthening Atomic Multicast for Partitioned State Machine ReplicationProceedings of the 11th Latin-American Symposium on Dependable Computing10.1145/3569902.3569909(51-60)Online publication date: 21-Nov-2022
https://dl.acm.org/doi/10.1145/3569902.3569909
Georgiou MPaphitis ASirivianos MHerodotou H(2022)Hihooi: A Database Replication Middleware for Scaling Transactional Databases ConsistentlyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.298756034:2(691-707)Online publication date: 10-Jan-2022
https://dl.acm.org/doi/10.1109/TKDE.2020.2987560
Jimenez-Peris RBurgos-Sancho DBallesteros FPatiño-Martinez MValduriez P(2022)Elastic scalable transaction processing in LeanXcaleInformation Systems10.1016/j.is.2022.102043108:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.is.2022.102043
Georgiou MPanayiotou MOdysseos LPaphitis ASirivianos MHerodotou HLi GLi ZIdreos SSrivastava D(2021)Attaining Workload Scalability and Strong Consistency for Replicated Databases with HihooiProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452746(2721-2725)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452746
Krechowicz ADeniziak SLukawski G(2021)Highly Scalable Distributed Architecture for NoSQL Datastore Supporting Strong ConsistencyIEEE Access10.1109/ACCESS.2021.30776809(69027-69043)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3077680
Cantarutti MPlebani PSalnitri M(2020)Fast Replica of Polyglot Persistence in Microservice Architectures for Fog ComputingService-Oriented Computing10.1007/978-3-030-65310-1_4(45-55)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65310-1_4
Zhao W(2019)Fault Tolerant Data Management for Cloud ServicesAdvanced Methodologies and Technologies in Network Architecture, Mobile Computing, and Data Analytics10.4018/978-1-5225-7598-6.ch014(191-201)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-7598-6.ch014
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents