Abstract
Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the Database State Machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and alleviates the need for atomic commitment. Transaction commit is based on a certification test, and abort rate is reduced by the reordering certification test. The approach is evaluated using a detailed simulation model that shows the scalability of the system and the benefits of the reordering certification test.
Similar content being viewed by others
References
D. Agrawal, A.E. Abbadi, and R. Steinke, “Epidemic algorithms in replicated databases,” in Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Tucson, Arizona, May 1997, pp. 12–15.
D. Agrawal, G. Alonso, A.E. Abbadi, and I. Stanoi, “Exploiting atomic broadcast in replicated databases,” in Proceedings of EuroPar (EuroPar'97), Passau, Germany, Sep. 1997.
R. Agrawal, M. Carey, and M. Livny, “Concurrency control performance modeling: Alternatives and implications,” ACM Transactions on Database Systems, vol. 12, no. 4, pp. 609–654, Dec. 1987.
Y. Amir, L.E. Moser, P.M. Melliar-Smith, P.A. Agarwal, and P. Ciarfella, “Fast message ordering and membership using a logical token-passing ring,” in Proceedings of the 13th International Conference on Distributed Computing Systems, Pittsburgh, PA, May 1993, pp. 551–560.
P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987.
K. Birman, A. Schiper, and P. Stephenson, “Lightweight causal and atomic group multicast,” ACM Transactions on Computer Systems, vol. 9, no. 3, pp. 272–314, August 1991.
M.J. Carey and M. Livny, “Conflict detection tradeoffs for replicated data,” ACM Transactions on Database Systems, vol. 16, no. 4, pp. 703–746, Dec. 1991.
J.M. Chang and N. Maxemchuck, “Reliable broadcast protocols,” ACM Transactions on Computer Systems, vol. 2, no. 3, pp. 251–273, August 1984.
T.D. Chandra and S. Toueg, “Unreliable failure detectors for reliable distributed systems,” Journal of the ACM, vol. 43, no. 2, pp. 225–267, Mar. 1996.
A. Demers et al., “Epidemic algorithms for replicated database maintenance,” in Proceedings of the 6th Annual ACMSymposium on Principles of Distributed Computing, F.B. Schneider (Ed.), ACMPress: Vancouver, BC, Canada, Aug. 1987, pp. 1–12.
H. Garcia-Molina and A. Spauster, “Ordered and reliable multicast communication,” ACM Transactions on Computer Systems, vol. 9, no. 3, pp. 242–271, August 1991.
J.N. Gray, P. Helland, P. O'Neil, and D. Shasha, “The dangers of replication and a solution,” in Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Canada, June 1996.
J.N. Gray, R. Lorie, G. Putzolu, and I. Traiger, Readings in Database Systems, ch. 3, Granularity of Locks and Degrees of Consistency in a Shared Database, Morgan Kaufmann, 1994.
J.N. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993.
R. Guerraoui, R. Oliveira, and A. Schiper, “Atomic updates of replicated data,” in EDCC,European Dependable Computing Conference, LNCS 1050, Taormina, Italy, 1996.
R. Guerraoui and A. Schiper, “Software based replication for fault tolerance,” IEEE Computer, vol. 30, no. 4, pp. 68–74, April 1997.
V. Hadzilacos and S. Toueg, Distributed Systems, 2nd ed., ch. 3, Fault-Tolerant Broadcasts and Related Problems, Addison Wesley, 1993.
H.V. Jagadish, I.S. Mumick, and M. Rabinovich, “Scalable versioning in distributed databases with commuting updates,” in Proceedings of the 13th IEEE International Conference on Data Engineering, Apr. 1997, pp. 520–531.
R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling, John Wiley and Sons, Inc., New York, 1991.
I. Keidar, “Ahighly available paradigm for consistent object replication,” Master's thesis, Institute of Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel, 1994.
B. Kemme and G. Alonso, “A new approach to developing and implementing eager database replication protocols,” ACM Transactions on Database Systems, vol. 25, no. 3, pp. 333–379, Sept. 2000.
B. Kemme and G. Alonso, “Don't be lazy, be consistent: Postgres-r, a new way to implement database replication,” in Proceedings of 26th International Conference on Very Large Databases (VLDB), Cairo, Egypt, September 2000.
H.T. Kung and J.T. Robinson, “On optimistic methods for concurrency control,” ACM Transactions on Database Systems, vol. 6, no. 2, pp. 213–226, June 1981.
L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,”ACMTransactions on Programming Languages and Systems, vol. 4, no. 3, pp. 382–401, July 1982.
S.W. Luan and V.D. Gligor, “A fault-tolerant protocol for atomic broadcast,” IEEE Transactions on Parallel and Distributed Syst., vol. 1, no. 3, pp. 271–285, July 1990.
F. Pedone, R. Guerraoui, and A. Schiper, “Transaction reordering in replicated databases,” in 16th IEEE Symposium on Reliable Distributed Systems, Durham, USA, Oct. 1997.
F. Pedone, R. Guerraoui, and A. Schiper, “Exploiting atomic broadcast in replicated databases,” Lecture Notes in Computer Science, vol. 1470, pp. 513–520, 1998.
O.T. Satyanarayanan and D. Agrawal, “Efficient execution of read-only transactions in replicated multiversion databases,” IEEE Transactions on Knowledge and Data Engineering, vol. 5, no. 5, pp. 859–871, Oct. 1993.
A. Schiper and M. Raynal, “From group communication to transaction in distributed systems,” Communications of the ACM, vol. 39, no. 4, pp. 84–87, Apr. 1996.
F.B. Schneider, “Implementing fault-tolerant services using the state machine approach: A tutorial,” ACM Computing Surveys, vol. 22, no. 4, pp. 299–319, Dec. 1990.
D. Skeen, “Nonblocking commit protocols,” in Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, April 1981, pp. 133–142.
D. Stacey, “Replication: Db2, oracle, or sybase?” SIGMOD Record, vol. 24, no. 5, pp. 95–101, Dec. 1995.
R.H. Thomas, “A majority consensus approach to concurrency control for multiple copy databases,” ACM Transactions on Database Systems, vol. 4, no. 2, pp. 180–209, June 1979.
A. Thomasian, “Distributed optimistic concurrency control methods for high-performance transaction processing,” IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 1, pp. 173–189, Jan. 1998.
M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso, “Understanding replication in databases and distributed systems,” in Proceedings of 20th International Conference on Distributed Computing Systems (ICDCS'2000), Taipei, Taiwan, Apr. 2000, pp. 264–274.
M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso, “Database replication techniques: A three parameter classification,” in Proceedings of 19th IEEE Symposium on Reliable Distributed Systems (SRDS2000), Nürnberg, Germany, Oct. 2000, pp. 206–215
U. Wilhelm and A. Schiper, “A hierarchy of totally ordered multicasts,” in 14th IEEE Symposium on Reliable Distributed Systems (SRDS-14), Bad Neuenahr, Germany, September 1995, pp. 106–115.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pedone, F., Guerraoui, R. & Schiper, A. The Database State Machine Approach. Distributed and Parallel Databases 14, 71–98 (2003). https://doi.org/10.1023/A:1022887812188
Issue Date:
DOI: https://doi.org/10.1023/A:1022887812188