Tashkent+: memory-aware load balancing and update filtering in replicated databases

ABSTRACT

We present a memory-aware load balancing (MALB) technique to dispatch transactions to replicas in a replicated database. Our MALB algorithm exploits knowledge of the working sets of transactions to assign them to replicas in such a way that they execute in main memory, thereby reducing disk I/O. In support of MALB, we introduce a method to estimate the size and the contents of transaction working sets. We also present an optimization called update filtering that reduces the overhead of update propagation between replicas.

We show that MALB greatly improves performance over other load balancing techniques -- such as round robin, least connections, and locality-aware request distribution (LARD) -- that do not use explicit information on how transactions use memory. In particular, LARD demonstrates good performance for read-only static content Web workloads, but it gives performance inferior to MALB for database workloads as it does not efficiently handle large requests. MALB combined with update filtering further boosts performance over LARD.

We build a prototype replicated system, called Tashkent+, with which we demonstrate that MALB and update filtering techniques improve performance of the TPC-W and RUBiS benchmarks. In particular, in a 16-replica cluster and using the ordering mix of TPC-W, MALB doubles the throughput over least connections and improves throughput 52% over LARD. MALB with update filtering further improves throughput to triple that of least connections and more than double that of LARD. Our techniques exhibit super-linear speedup; the throughput of the 16-replica cluster is 37 times the peak throughput of a standalone database due to better use of the cluster's memory.

REFERENCES

• 1: Cristiana Amza , Alan L. Cox , Willy Zwaenepoel, Conflict-aware scheduling for dynamic content applications, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.6-6, March 26-28, 2003, Seattle, WA
• 2: {ACZ03-2} C. Amza, A. Cox, and W. Zwaenepoel. Distributed Versioning: Consistent Replication for Scaling Back-end Databases of Dynamic Content Web Sites. In ACM/IFIP/Usenix International Middleware Conference, June 2003.
• 3: {ACC+02} C. Amza, E. Cecchet, A. Chanda, Alan L. Cox, S. Elnikety, R. Gil, J. Marguerite, K. Rajamani and W. Zwaenepoel. Specification and Implementation of Dynamic Web Site Benchmarks. WWC-5: The 5th Annual IEEE Workshop on Workload Characterization, Austin, Texas, USA, November 2002.
• 4: {BB97} A. Barak and A. Braverman. Memory Ushering in a Scalable Computing Cluster, In Proceedings of the IEEE Third International Conference on Algorithms and Architecture for Parallel Processing, Melbourne, 1997.
• 5: 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
• 6: {BCD+06} S. Bouchenak, A. Cox, S. Dropsho, S. Mittal, and W. Zwaenepoel. Caching Dynamic Web Content: Designing and Analysing an Aspect-oriented Solution. In Proceedings of Middleware 2006, Melbourne, Australia, November 2006.
• 7: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 8: Ludmila Cherkasova , Shankar R. Ponnekanti, Optimizing a 'Content-Aware' Load Balancing Strategy for Shared Web Hosting Service, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.492, August 29-September 01, 2000
• 9: {CS04} S. Kyun Cha and C. Song. P*TIME: Highly Scalable OLTP DBMS for Managing Update-Intensive Stream Workload. In Proceedings of 30^nd International Conference on Very Large Data Bases (VLDB 2004), Toronto, Canada, August 2004.
• 10: Khuzaima Daudjee , Kenneth Salem, Lazy Database Replication with Ordering Guarantees, Proceedings of the 20th International Conference on Data Engineering, p.424, March 30-April 02, 2004
• 11: Khuzaima Daudjee , Kenneth Salem, Lazy database replication with snapshot isolation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: Sameh Elnikety , Steven Dropsho , Fernando Pedone, Tashkent: uniting durability with transaction ordering for high-performance scalable database replication, Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 13: Sameh Elnikety , Erich Nahum , John Tracey , Willy Zwaenepoel, A method for transparent admission control and request scheduling in e-commerce web sites, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988710]
• 14: 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]
• 15: 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]
• 16: {F1-99} A. Fekete. Serialisability and Snapshot Isolation. In Proceedings of the Australian Database Conference, pages 201--210, Auckland, New Zealand, January 1999.
• 17: 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]
• 18: {FLO+96} A. Fekete, D. Liarokapis, E. O'Neil, P. O'Neil, and D. Shasha. Making Snapshot Isolation Serializable. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 173--182, June 1996.
• 19: 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]
• 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
• 21: Taliver Heath , Ana Paula Centeno , Pradeep George , Luiz Ramos , Yogesh Jaluria, Mercury and freon: temperature emulation and management for server systems, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 22: {J95} K. Jacobs. Concurrency Control, Transaction Isolation and Serializability in SQL92 and Oracle7. Technical report number A33745, Oracle Corporation, Redwoord City, CA, July 1995.
• 23: 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
• 24: 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
• 25: Magnus Karlsson , Per Stenström, An analytical model of the working-set sizes in decision-support systems, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.275-285, June 18-21, 2000, Santa Clara, California, United States
• 26: 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]
• 27: {L99} A. Lodi. Algorithms for Two-Dimensional Bin Packing and Assignment Problems. PhD thesis. Uiversita Degli Studi di Bologna. 1999.
• 28: 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]
• 29: {OW} ObjectWeb Consortium. Rice University bidding system. http://rubis.objectweb.org/.
• 30: {Ora97} Data Concurrency and Consistency, Oracle8 Concepts, Release 8.0: Chapter 23. Technical report, Oracle Corporation, 1997.
• 31: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 32: 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
• 33: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.205-216, October 02-07, 1998, San Jose, California, United States
• 34: {PG} PostgreSQL, SQL Compliant, Open Source Object-Relational Database Management System. http://www.postgresql.org/.
• 35: Marta Patiño-Martinez , Ricardo Jiménez-Peris , Bettina Kemme , Gustavo Alonso, MIDDLE-R: Consistent database replication at the middleware level, ACM Transactions on Computer Systems (TOCS), v.23 n.4, p.375-423, November 2005 [doi>10.1145/1113574.1113576]
• 36: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, ACM SIGMOD Record, v.20 n.2, p.377-386, June 1991
• 37: Robbert van Renesse , Fred B. Schneider, Chain replication for supporting high throughput and availability, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.7-7, December 06-08, 2004, San Francisco, CA
• 38: {RT04} M. Ronström and L. Thalmann. MySQL Cluster Architecture Overview. MySQL Technical White Paper, 2004.
• 39: 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]
• 40: {TPC} Transaction Processing Performance Council -- http://www.tpc.org/.
• 41: 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]
• 42: 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
• 43: Xiaolan Zhang , Michael Barrientos , J. Bradley Chen , Margo Seltzer, HACC: an architecture for cluster-based web servers, Proceedings of the 3rd conference on USENIX Windows NT Symposium, p.16-16, July 12-15, 1999, Seattle, Washington
• 44: {ZP06} V. Zuikeviciute and F. Pedone. Conflict-Aware Load-Balancing Techniques for Database Replication. USI Technical Report, 2006.

INDEX TERMS

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

General Terms:
Design, Measurement, Performance

Keywords:
database replication, load balancing