Tashkent: uniting durability with transaction ordering for high-performance scalable database replication

ABSTRACT

In stand-alone databases, the functions of ordering the transaction commits and making the effects of transactions durable are performed in one single action, namely the writing of the commit record to disk. For efficiency many of these writes are grouped into a single disk operation. In replicated databases in which all replicas agree on the commit order of update transactions, these two functions are typically separated. Specifically, the replication middleware determines the global commit order, while the database replicas make the transactions durable.The contribution of this paper is to demonstrate that this separation causes a significant scalability bottleneck. It forces some of the commit records to be written to disk serially, where in a standalone system they could have been grouped together in a single disk write. Two solutions are possible: (1) move durability from the database to the replication middleware, or (2) keep durability in the database and pass the global commit order from the replication middleware to the database.We implement these two solutions. Tashkent-MW is a pure middleware solution that combines durability and ordering in the middleware, and treats an unmodified database as a black box. In Tashkent-API, we modify the database API so that the middleware can specify the commit order to the database, thus, combining ordering and durability inside the database. We compare both Tashkent systems to an otherwise identical replicated system, called Base, in which ordering and durability remain separated. Under high update transaction loads both Tashkent systems greatly outperform Base in throughput and response time.

REFERENCES

• 1: 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
• 2: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 3: Sameh Elnikety , Willy Zwaenepoel , Fernando Pedone, Database Replication Using Generalized Snapshot Isolation, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05), p.73-84, October 26-28, 2005 [doi>10.1109/RELDIS.2005.14]
• 4: Alan Fekete, Allocating isolation levels to transactions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065193]
• 5: Alan Fekete. Serialisability and snapshot isolation. In proceedings of the Australian Database Conference, pages 201--210, Auckland, New Zealand, January 1999.
• 6: Lars Frank, Evaluation of the basic remote backup and replication methods for high availability databases, Software—Practice & Experience, v.29 n.15, p.1339-1353, Dec. 25, 1999 [doi>10.1002/(SICI)1097-024X(19991225)29:15<1339::AID-SPE284>3.3.CO;2-W ]
• 7: Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil, and Dennis Shasha. Making snapshot isolation serializable. In proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 173--182, June 1996.
• 8: Lei Gao , Mike Dahlin , Amol Nayate , Jiandan Zheng , Arun Iyengar, Application specific data replication for edge services, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775217]
• 9: 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
• 10: K. Jacobs. Concurrency control, transaction isolation and serializability in SQL92 and Oracle7. Technical report number A33745, Oracle Corporation, Redwood City, CA, July 1995.
• 11: 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
• 12: 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
• 13: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 14: Yi Lin , Bettina Kemme , Marta Patiño-Martínez , Ricardo Jiménez-Peris, Middleware based data replication providing snapshot isolation, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066205]
• 15: Oracle parallel server for windows NT clusters. Online White Paper.
• 16: Data Concurrency and Consistency, Oracle8 Concepts, Release 8.0: Chapter 23. Technical report, Oracle Corporation, 1997.
• 17: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 18: Christian Plattner , Gustavo Alonso, Ganymed: scalable replication for transactional web applications, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 19: PostgreSQL, SQL compliant, open source object-relational database management system. http://www.postgresql.org/.
• 20: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, ACM SIGMOD Record, v.20 n.2, p.377-386, June 1991
• 21: Robbert van Renesse and Fred B. Schneider. Chain Replication for Supporting High Throughput and Availability. Sixth Symposium on Operating Systems Design and Implementation (OSDI '04), San Francisco, California, December 2004.
• 22: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 23: Transaction Processing Performance Council - http://www.tpc.org/.
• 24: Shuqing Wu , Bettina Kemme, Postgres-R(SI): Combining Replica Control with Concurrency Control Based on Snapshot Isolation, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.422-433, April 05-08, 2005 [doi>10.1109/ICDE.2005.108]
• 25: M. Wiesmann , F. Pedone , A. Schiper , B. Kemme , G. Alonso, Understanding Replication in Databases and Distributed Systems, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.464, April 10-13, 2000

INDEX TERMS

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

General Terms:
Design, Measurement, Performance, Reliability

Keywords:
database replication, generalized snapshot isolation