Service-oriented data denormalization for scalable web applications

ABSTRACT

Many techniques have been proposed to scale web applications. However, the data interdependencies between the database queries and transactions issued by the applications limit their efficiency. We claim that major scalability improvements can be gained by restructuring the web application data into multiple independent data services with exclusive access to their private data store. While this restructuring does not provide performance gains by itself, the implied simplification of each database workload allows a much more efficient use of classical techniques. We illustrate the data denormalization process on three benchmark applications: TPC-W, RUBiS and RUBBoS. We deploy the resulting service-oriented implementation of TPC-W across an 85-node cluster and show that restructuring its data can provide at least an order of magnitude improvement in the maximum sustainable throughput compared to master-slave database replication, while preserving strong consistency and transactional properties.

REFERENCES

• 1: B. Abrahao, V. Almeida, J. Almeida, A. Zhang, D. Beyer, and F. Safai. Self-adaptive SLA-driven capacity management for internet services. In Proc. NOMS, Apr. 2006.
• 2: K. Amiri, S. Park, R. Tewari, and S. Padmanabhan. DBProxy: A dynamic data cache for Web applications. In Proc. ICDE, Mar. 2003.
• 3: C. Amza, E. Cecchet, A. Chanda, A. Cox, S. Elnikety, R. Gil, J. Marguerite, K. Rajamani, and W. Zwaenepoel. Specification and implementation of dynamic web site benchmarks. In Proc. Intl. Workshop on Workload Characterization, Nov. 2002.
• 4: C. Bornhövd, M. Altinel, C. Mohan, H. Pirahesh, and B. Reinwald. Adaptive database caching with DBCache. Data Engineering, 27(2):11--18, June 2004.
• 5: E. Cecchet. C-JDBC: a middleware framework for database clustering. Data Engineering, 27(2):19--26, June 2004.
• 6: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 7: I. Cunha, J. Almeida, V. Almeida, and M. dos Santos. Self-adaptive capacity management for multi-tier virtualized environments. In Proc. Intl. Symposium on Integrated Network Management, May 2007.
• 8: DAS3: The Distributed ASCI Supercomputer 3. http://www.cs.vu.nl/das3/.
• 9: A. Davis , J. Parikh , W. E. Weihl, Edgecomputing: extending enterprise applications to the edge of the internet, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013397]
• 10: Giuseppe DeCandia , Deniz Hastorun , Madan Jampani , Gunavardhan Kakulapati , Avinash Lakshman , Alex Pilchin , Swaminathan Sivasubramanian , Peter Vosshall , Werner Vogels, Dynamo: amazon's highly available key-value store, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 11: 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]
• 12: Charlene O'Hanlon, A conversation with Werner Vogels, Queue, v.4 n.4, May 2006 [doi>10.1145/1142055.1142065]
• 13: Steven D. Gribble , Eric A. Brewer , Joseph M. Hellerstein , David Culler, Scalable, distributed data structures for internet service construction, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.22-22, October 22-25, 2000, San Diego, California
• 14: Tobias Groothuyse , Swaminathan Sivasubramanian , Guillaume Pierre, Globetp: template-based database replication for scalable web applications, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242614]
• 15: Y. Huang and J. Chen. Fragment allocation in distributed database design. Information Science and Engineering, 17(3):491--506, May 2001.
• 16: Java TPC-W implementation distribution. http://www.ece.wisc.edu/pharm/tpcw.shtml.
• 17: L. Kazerouni and K. Karlapalem. Stepwise redesign of distributed relational databases. Technical Report HKUST-CS97-12, Hong Kong Univ. of Science and Technology, Dept. of Computer Science, Sept. 1997.
• 18: 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
• 19: S. Navathe, K. Karlapalem, and M. Ra. A mixed fragmentation methodology for initial distributed database design. Computer and Software Engineering, 3(4), 1995.
• 20: Shamkant B. Navathe , Mingyoung Ra, Vertical partitioning for database design: a graphical algorithm, ACM SIGMOD Record, v.18 n.2, p.440-450, June 1989
• 21: C. Olston, A. Manjhi, C. Garrod, A. Ailamaki, B. Maggs, and T. Mowry. A scalability service for dynamic web applications. In Proc. Conf. on Innovative Data Systems Research, Jan. 2005.
• 22: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 23: 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
• 24: M. Rabinovich, Z. Xiao, and A. Agarwal. Computing on the edge: A platform for replicating internet applications. In Proc. Intl. Workshop on Web Content Caching and Distribution, Sept. 2003.
• 25: M. Ronstrom and L. Thalmann. MySQL cluster architecture overview. MySQL Technical White Paper, Apr. 2004.
• 26: RUBBoS: Bulletin board system benchmark. http://jmob.objectweb.org/rubbos.html.
• 27: G. Sanders , S. Shin, Denormalization Effects on Performance of RDBMS, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 3, p.3013, January 03-06, 2001
• 28: Seung Kyoon Shin , G. Lawrence Sanders, Denormalization strategies for data retrieval from data warehouses, Decision Support Systems, v.42 n.1, p.267-282, October 2006 [doi>10.1016/j.dss.2004.12.004]
• 29: Swaminathan Sivasubramanian , Gustavo Alonso , Guillaume Pierre , Maarten van Steen, GlobeDB: autonomic data replication for web applications, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060756]
• 30: S. Sivasubramanian, G. Pierre, M. van Steen, and G. Alonso. GlobeCBC: Content-blind result caching for dynamic web applications. Technical Report IR-CS-022, Vrije Universiteit, Amsterdam, The Netherlands, June 2006.
• 31: Swaminathan Sivasubramanian , Guillaume Pierre , Maarten van Steen , Gustavo Alonso, Analysis of Caching and Replication Strategies for Web Applications, IEEE Internet Computing, v.11 n.1, p.60-66, January 2007 [doi>10.1109/MIC.2007.3]
• 32: W. D. Smith. TPC-W: Benchmarking an ecommerce solution. White paper, Transaction Processing Performance Council.
• 33: Niraj Tolia , M. Satyanarayanan, Consistency-preserving caching of dynamic database content, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242615]
• 34: TPC-W frequently asked questions, question 2.10: "Why was the concept of atomic set of operations added and what are its requirements?", Aug. 1999.
• 35: Bhuvan Urgaonkar , Abhishek Chandra, Dynamic Provisioning of Multi-tier Internet Applications, Proceedings of the Second International Conference on Automatic Computing, p.217-228, June 13-16, 2005 [doi>10.1109/ICAC.2005.27]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

General Terms:
Performance

Keywords:
data denormalization, scalability, web applications