Are quorums an alternative for data replication?

ABSTRACT

Data replication is playing an increasingly important role in the design of parallel information systems. In particular, the widespread use of cluster architectures often requires to replicate data for performance and availability reasons. However, maintaining the consistency of the different replicas is known to cause severe scalability problems. To address this limitation, quorums are often suggested as a way to reduce the overall overhead of replication. In this article, we analyze several quorum types in order to better understand their behavior in practice. The results obtained challenge many of the assumptions behind quorum based replication. Our evaluation indicates that the conventional read-one/write-all-available approach is the best choice for a large range of applications requiring data replication. We believe this is an important result for anybody developing code for computing clusters as the read-one/write-all-available strategy is much simpler to implement and more flexible than quorum-based approaches. In this article, we show that, in addition, it is also the best choice using a number of other selection criteria.

REFERENCES

• 1: D. Agrawal , A. El Abbadi, Efficient solution to the distributed mutual exclusion problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.193-200, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72994]
• 2: D. Agrawal , A. El Abbadi, Exploiting logical structures in replicated databases, Information Processing Letters, v.33 n.5, p.255-260, January 1990 [doi>10.1016/0020-0190(90)90194-3]
• 3: 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
• 4: Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
• 5: D. Agrawal , A. El Abbadi, The generalized tree quorum protocol: an efficient approach for managing replicated data, ACM Transactions on Database Systems (TODS), v.17 n.4, p.689-717, Dec. 1992 [doi>10.1145/146931.146935]
• 6: M. Ahamad , M. H. Ammar, Performance Characterization of Quorum-Consensus Algorithms for Replicated Data, IEEE Transactions on Software Engineering, v.15 n.4, p.492-496, April 1989 [doi>10.1109/32.16608]
• 7: Y. Amir , A. Wool, Evaluating quorum systems over the Internet, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.26, June 25-27, 1996
• 8: Yair Amir , Avishai Wool, Optimal availability quorum systems: theory and practice, Information Processing Letters, v.65 n.5, p.223-228, March 13, 1998 [doi>10.1016/S0020-0190(98)00017-9]
• 9: 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
• 10: Bacon, J. 1997. Concurrency Systems. Addison-Wesley, Reading, Mass.
• 11: D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
• 12: Daniel Barbara , Hector Garcia-Molina , Annemarie Spauster, Increasing availability under mutual exclusion constraints with dynamic vote reassignment, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.394-426, Nov. 1989 [doi>10.1145/75104.75107]
• 13: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 14: 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]
• 15: 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]
• 16: Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988
• 17: 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
• 18: Mustaque Ahamad , Mostafa H. Ammar , Shun Yan Cheung, Multidimensional voting, ACM Transactions on Computer Systems (TOCS), v.9 n.4, p.399-431, Nov. 1991 [doi>10.1145/118544.118552]
• 19: B. Ciciani , D. M. Dias , P. S. Yu, Analysis of Replication in Distributed Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.247-261, June 1990 [doi>10.1109/69.54723]
• 20: George Coulouris , Jean Dollimore , Tim Kindberg, Distributed systems (3rd ed.): concepts and design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 21: Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983 [doi>10.1145/319989.319992]
• 22: Erdös, P. and Lovász, L. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. Colloq. Math. Soc. János Bolyai 10, 609--627.
• 23: 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]
• 24: 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
• 25: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 26: Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987 [doi>10.1145/22952.22953]
• 27: San-Yih Hwang , Keith K. S. Lee , Y. H. Chin, Data Replication in a Distributed System: A Performance Study, Proceedings of the 7th International Conference on Database and Expert Systems Applications, p.708-717, September 09-13, 1996
• 28: Availability Study of Dynamic Voting Algorithms, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.247, April 16-19, 2001
• 29: S. Jajodia , David Mutchler, Dynamic voting algorithms for maintaining the consistency of a replicated database, ACM Transactions on Database Systems (TODS), v.15 n.2, p.230-280, June 1990 [doi>10.1145/78922.78926]
• 30: Jiménez-Peris, R., Patiño-Martínez, M., Alonso, G., and Kemme, B. 2001. How to select a replication protocol according to scalability, availability, and communication overhead. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS) (New Orleans, La.). IEEE Computer Society Press, Los Alamitos, Calif., 24--33.
• 31: Jiménez-Peris, R., Patiño-Martínez, M., Alonso, G., and Kemme, B. 2002. Scalable database replication middleware. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (Vienna, Austria). IEEE Computer Users Society, Los Alamitos, Calif.
• 32: Kemme, B. 2000. Database Replication for Clusters of Workstations. Ph.D. dissertation. Dept. of Computer Science, Swiss Federal Institute of Technology Zurich.
• 33: 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
• 34: Chang S. Keum , Wan Choi , Eui Kyeong Hong , Won Y. Kim , Kyu-Young Whang, Performance Evaluation of Replica Control Algorithms in a Locally Distributed Database System, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.388-396, April 11-13, 1995
• 35: Kumar, A. 1990. Performance of a Hierarchical Quorum Consensus Algorithm for Replicated Objects. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (Paris, France). IEEE Computer Society Press, Los Alamitos, Calif., 378--385.
• 36: Akhil Kumar, Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data, IEEE Transactions on Computers, v.40 n.9, p.996-1004, September 1991 [doi>10.1109/12.83661]
• 37: Akhil Kumar , Arie Segev, Cost and availability tradeoffs in replicated data concurrency control, ACM Transactions on Database Systems (TODS), v.18 n.1, p.102-131, March 1993 [doi>10.1145/151284.151287]
• 38: Kumar, A., Rabinovich, M., and Sinha, R. K. 1993. A performance study of general grid structures for replicated data. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (Pittsburgh, Pa.), IEEE Computer Society Press, Los Alamitos, Calif., 178--185.
• 39: Arthur J. Bernstein , Michael Kifer, Databases and Transaction Processing: An Application-Oriented Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 40: Liu, M. L., Agrawal, D., and Abbadi, A. E. 1997. The performance of replica control protocols in the presence of site failures. Distrib. Syst. Eng. 4, 2 (June), 59--77.
• 41: Lovász, L. 1973. Coverings and colorings in hypergraphs. In Proceedings of 4th South Eastern Conference on Combinatorics, Graph Theory and Computing. Utilitas Math., Winnipeg, B.C., Canada, 3--12.
• 42: 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]
• 43: Moni Naor , Avishai Wool, The Load, Capacity, and Availability of Quorum Systems, SIAM Journal on Computing, v.27 n.2, p.423-447, April 1998 [doi>10.1137/S0097539795281232]
• 44: Matthias Nicola , Matthias Jarke, Performance Modeling of Distributed and Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.12 n.4, p.645-672, July 2000 [doi>10.1109/69.868912]
• 45: Paris, J. F. 1986. Voting with witnesses: A consistency scheme for replicated files. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (Cambridge, Mass.). IEEE Computer Society Press, Los Alamitos, Calif., 606--612.
• 46: Paris, J. F. 1989. Voting with bystanders. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (Newport Beach, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 394--405.
• 47: Jehan-François Pâris , Darrell D. E. Long, Voting with Regenerable Volatile Witnesses, Proceedings of the Seventh International Conference on Data Engineering, p.112-119, April 08-12, 1991
• 48: David Peleg , Avishai Wool, The availability of quorum systems, Information and Computation, v.123 n.2, p.210-223, Dec. 1995 [doi>10.1006/inco.1995.1169]
• 49: Peleg, D. and Wool, A. 1997. Crumbling walls: A class of practical and efficient quorum systems. Distrib. Comput. 10, 2, 87--97.
• 50: S. Rangarajan , P. Jalote , S. K. Tripathi, Capacity of Voting Systems, IEEE Transactions on Software Engineering, v.19 n.7, p.698-706, July 1993 [doi>10.1109/32.238570]
• 51: Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1271-1282, December 1995 [doi>10.1109/71.476168]
• 52: J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980 [doi>10.1145/320128.320129]
• 53: Debanjan Saha , Sampath Rangarajan , Satish K. Tripathi, An Analysis of the Average Message Overhead in Replica Control Protocols, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1026-1034, October 1996 [doi>10.1109/71.539734]
• 54: M. Spasojevic , P. Berman, Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.64-73, January 1994 [doi>10.1109/71.262589]
• 55: O. Theel , H. Pagnia-Koch, General design of grid-based data replication schemes using graphs and a few rules, Proceedings of the 15th International Conference on Distributed Computing Systems, p.395, May 30-June 02, 1995
• 56: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 57: Tong, Z. and Kain, R. Y. 1988. Vote Assignments in Weighted Voting Mechanisms. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS). (Columbus, Ohio). IEEE Computer Society Press, Los Alamitos, Calif., 138--143.
• 58: van Renesse, R. and Tanenbaum, A. S. 1988. Voting with ghosts. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS) (San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 456--462.
• 59: 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
• 60: Wool, A. 1996. Quorum systems for distributed control protocols. Ph.D. dissertation, The Weizmann Institute of Science, Rehovot, Israel.
• 61: Wool, A. 1998. Quorum systems in replicated databases: Science or fiction? Data Eng. Bull. 21, 4 (Dec.), 3--11.
• 62: Wu, C. and Belford, G. G. 1992. The triangular lattice protocol: A highly fault tolerant and highly efficient protocol for replicated data. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS). (Houston, Tex.). IEEE Computer Society Press, Los Alamitos, Calif., 66--73.
• 63: Philip S. Yu , Daniel M. Dias , Stephen S. Lavenberg, On the analytical modeling of database concurrency control, Journal of the ACM (JACM), v.40 n.4, p.831-872, Sept. 1993 [doi>10.1145/153724.153733]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Performance, Reliability

Keywords:
Data replication, availability, distributed transactions., quorums, scalability