Improving the responsiveness of internet services with automatic cache placement

ABSTRACT

The backends of today's Internet services rely heavily on caching at various layers both to provide faster service to common requests and to reduce load on back-end components. Cache placement is especially challenging given the diversity of workloads handled by widely deployed Internet services. This paper presents TOOL, an analysis technique that automatically optimizes cache placement. Our experiments have shown that near-optimal cache placements vary significantly based on input distribution.

REFERENCES

• 1: Michael Abd-El-Malek , William V. Courtright, II , Chuck Cranor , Gregory R. Ganger , James Hendricks , Andrew J. Klosterman , Michael Mesnier , Manish Prasad , Brandon Salmon , Raja R. Sambasivan , Shafeeq Sinnamohideen , John D. Strunk , Eno Thereska , Matthew Wachs , Jay J. Wylie, Ursa minor: versatile cluster-based storage, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.5-5, December 13-16, 2005, San Francisco, CA
• 2: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 3: Eric Anderson , Michael Hobbs , Kimberly Keeton , Susan Spence , Mustafa Uysal , Alistair C. Veitch, Hippodrome: Running Circles Around Storage Administration, Proceedings of the Conference on File and Storage Technologies, p.175-188, January 28-30, 2002
• 4: Eric Anderson , Susan Spence , Ram Swaminathan , Mahesh Kallahalla , Qian Wang, Quickly finding near-optimal storage designs, ACM Transactions on Computer Systems (TOCS), v.23 n.4, p.337-374, November 2005 [doi>10.1145/1113574.1113575]
• 5: Paul Barham , Austin Donnelly , Rebecca Isaacs , Richard Mortier, Using magpie for request extraction and workload modelling, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.18-18, December 06-08, 2004, San Francisco, CA
• 6: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 7: D. C. Chu and J. M. Hellerstein. Automating Rendezvous and Proxy Selection. Technical Report UCB/EECS-2008-84, University of California Berkeley, 2008.
• 8: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, v.51 n.1, January 2008 [doi>10.1145/1327452.1327492]
• 9: Ronald P. Doyle , Jeffrey S. Chase, Model-based adaptive resource provisioning in a web service utility, Duke University, Durham, NC, 2003
• 10: C. Henderson. Scalable Web Architectures: Common Patterns and Approaches, September 2008.
• 11: Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 12: Kimberly Keeton , Dirk Beyer , Ernesto Brau , Arif Merchant , Cipriano Santos , Alex Zhang, On the road to recovery: restoring data after disasters, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
• 13: T. Kelly and D. Reeves. Optimal Web Cache Sizing: Scalable Methods for Exact Solutions. Computer Communications, 24: 163--173, 2001.
• 14: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 15: Microsoft. Microsoft PopFly, 2008. URL http://www.popfly.com/.
• 16: M.E.J. Newman. Power Laws, Pareto Distributions and Zipf's Law. Contemporary Physics, 46 (5): 323--351, 2005.
• 17: J. Rao and X. Su. A Survey of Automated Web Service Composition Methods, volume 3387 of Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 2005.
• 18: Patrick Reynolds , Charles Killian , Janet L. Wiener , Jeffrey C. Mogul , Mehul A. Shah , Amin Vahdat, Pip: detecting the unexpected in distributed systems, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.9-9, May 08-10, 2006, San Jose, CA
• 19: Adriana Iamnitchi , Aydan R. Yumerefendi , Jeffrey S. Chase, Model-Driven Placement of Compute Tasks and Data in a Networked Utility, Proceedings of the Second International Conference on Automatic Computing, p.344-345, June 13-16, 2005 [doi>10.1109/ICAC.2005.41]
• 20: Christopher Stewart , Terence Kelly , Alex Zhang , Kai Shen, A dollar from 15 cents: cross-platform management for internet services, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.199-212, June 22-27, 2008, Boston, Massachusetts
• 21: M. Szeredi. Filesystem in USEr space. 2005. http://fuse.sourceforge.net/.
• 22: Jia Wang, A survey of web caching schemes for the Internet, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505701]
• 23: Yahoo!, Inc. Yahoo! Pipes, 2008. URL http://pipes.yahoo.com/pipes/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

General Terms:
Algorithms, Design, Experimentation, Languages, Management, Performance

Keywords:
caching, cloud computing, dataflow model, internet services, optimization, simulation