More Web Proxy on the site http://driver.im/

research-article

Dynamic partitioning of the cache hierarchy in shared data centers

Authors:

Gokul Soundararajan,

Mohamed A. Sharaf,

Cristiana AmzaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 1, Issue 1

Pages 635 - 646

https://doi.org/10.14778/1453856.1453926

Published: 01 August 2008 Publication History

Abstract

Due to the imperative need to reduce the management costs of large data centers, operators multiplex several concurrent database applications on a server farm connected to shared network attached storage. Determining and enforcing per-application resource quotas in the resulting cache hierarchy, on the fly, poses a complex resource allocation problem spanning the database server and the storage server tiers. This problem is further complicated by the need to provide strict Quality of Service (QoS) guarantees to hosted applications.

In this paper, we design and implement a novel coordinated partitioning technique of the database buffer pool and storage cache between applications for any given cache replacement policy and per-application access pattern. We use statistical regression to dynamically determine the mapping between cache quota settings and the resulting per-application QoS. A resource controller embedded within the database engine actuates the partitioning of the two-level cache, converging towards the configuration with maximum application utility, expressed as the service provider revenue in that configuration, based on a set of latency sample points.

Our experimental evaluation, using the MySQL database engine, a server farm with consolidated storage, and two e-commerce benchmarks, shows the effectiveness of our technique in enforcing application QoS, as well as maximizing the revenue of the service provider in shared server farms.

References

[1]

Transaction processing council. http://www.tpc.org.

[2]

A. C. Arpaci-Dusseau and R. H. Arpaci-Dusseau. Information and Control in Gray-Box Systems. In SOSP, 2001.

Digital Library

[3]

P. T. Barbara, B. Dragovic, K. Eraser, S. Hand, T. L. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In SOSP, 2003.

Digital Library

[4]

K. P. Brown, M. J. Carey, and M. Livny. Managing Memory to Meet Multiclass Workload Response Time Goals. In VLDB, 1993.

Digital Library

[5]

K. P. Brown, M. J. Carey, and M. Livny. Goal-Oriented Buffer Management Revisited. In SIGMOD, 1996.

Digital Library

[6]

D. Carney, U. Çetintemel, A. Rasin, S. B. Zdonik, M. Cherniack, and M. Stonebraker. Operator scheduling in a data stream manager. In VLDB, 2003.

Digital Library

[7]

F. W. Chang and G. A. Gibson. Automatic I/O Hint Generation Through Speculative Execution. In OSDI, 1999.

Digital Library

[8]

Z. Chen, Y. Zhang, Y. Zhou, H. Scott, and B. Schiefer. Empirical evaluation of multi-level buffer cache collaboration for storage systems. In SIGMETRICS, 2005.

Digital Library

[9]

Z. Chen, Y. Zhou, and K. Li. Eviction-based Cache Placement for Storage Caches. In USENIX Annual Technical Conference, General Track, 2003.

[10]

H.-T. Chou and D. J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. In VLDB, 1985.

Digital Library

[11]

F. J. Corbat. A Paging Experiment with the Multics System. MIT Press, 1969.

[12]

H. Drucker, C. J. C. Burges, L. Kaufman, A. J. Smola, and V. Vapnik. Support Vector Regression Machines. In NIPS, 1996.

[13]

A. Gulati, A. Merchant, and P. J. Varman. pClock: an arrival curve based approach for QoS guarantees in shared storage systems. In SIGMETRICS, 2007.

Digital Library

[14]

S. Jiang and X. Zhang. LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance. In SIGMETRICS, 2002.

Digital Library

[15]

T. Johnson and D. Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. In VLDB, 1994.

Digital Library

[16]

S. T. Jones, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Geiger: monitoring the buffer cache in a virtual machine environment. In ASPLOS, 2006.

Digital Library

[17]

D. G. Kleinbaum, L. L. Kupper, A. Nizam, and K. E. Muller. Applied Regression Analysis and Multivariable Methods (4th Edition). Duxbury Press, 2007.

Digital Library

[18]

A. Labrinidis, H. Qu, and J. Xu. Quality contracts for real-time enterprises. In BIRTE, 2006.

Digital Library

[19]

X. Li, A. Aboulnaga, K. Salem, A. Sachedina, and S. Gao. Second-Tier Cache Management Using Write Hints. In FAST, 2005.

Digital Library

[20]

S. Liang, S. Jiang, and X. Zhang. STEP: Sequentiality and Thrashing Detection Based Prefetching to Improve Performance of Networked Storage Servers. In ICDCS, 2007.

Digital Library

[21]

C. R. Lumb, A. Merchant, and G. A. Alvarez. Façade: Virtual Storage Devices with Performance Guarantees. In FAST, 2003.

Digital Library

[22]

E. J. O'Neil, P. E. O'Neil, and G. Weikum. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In SIGMOD, 1993.

Digital Library

[23]

O. Ozmen, K. Salem, M. Uysal, and M. H. S. Attar. Storage workload estimation for database management systems. In SIGMOD, 2007.

Digital Library

[24]

P. Padala, K. G. Shin, X. Zhu, M. Uysal, Z. Wang, S. Singhal, A. Merchant, and K. Salem. Adaptive control of virtualized resources in utility computing environments. In EuroSys, 2007.

Digital Library

[25]

R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed Prefetching and Caching. In SOSP, 1995.

Digital Library

[26]

J. Schindler, J. L. Griffin, C. R. Lumb, and G. R. Ganger. Track-aligned Extents: Matching Access Patterns to Disk Drive Characteristics. In FAST, 2002.

Digital Library

[27]

K. Shen, T. Yang, L. Chu, J. Holliday, D. A. Kuschner, and H. Zhu. Neptune: Scalable Replication Management and Programming Support for Cluster-based Network Services. In USITS, 2001.

Digital Library

[28]

G. Soundararajan, M. Mihailescu, and C. Amza. Context aware block prefetching at the storage server. In USENIX, 2008.

Digital Library

[29]

A. J. Storm, C. Garcia-Arellano, S. Lightstone, Y. Diao, and M. Surendra. Adaptive Self-tuning Memory in DB2. In VLDB, 2006.

Digital Library

[30]

A. Trossman. Virtualization capabilities of IBM Tivoli. In 1st Workshop on Virtualization and the Management of Information Services, 2007.

[31]

M. Wachs, M. Abd-El-Malek, E. Thereska, and G. R. Ganger. Argon: performance insulation for shared storage servers. In FAST, 2007.

Digital Library

[32]

T. M. Wong and J. Wilkes. My Cache or Yours? Making Storage More Exclusive. In USENIX Annual Technical Conference, General Track, 2002.

Digital Library

[33]

G. Yadgar, M. Factor, and A. Schuster. Karma: know-it-all replacement for a multilevel cache. In FAST, 2007.

Digital Library

[34]

P. Zhou, V. Pandey, J. Sundaresan, A. Raghuraman, Y. Zhou, and S. Kumar. Dynamic tracking of page miss ratio curve for memory management. In ASPLOS, 2004.

Digital Library

Cited By

Carra DNeglia GGavrilovska AZadok E(2020)Efficient miss ratio curve computation for heterogeneous content popularityProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489197(741-751)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489197
Zhang WLiu FFan R(2014)Cache matchingProceedings of the High Performance Computing Symposium10.5555/2663510.2663517(1-8)Online publication date: 13-Apr-2014
https://dl.acm.org/doi/10.5555/2663510.2663517
Li YFeng DShi Z(2014)Heterogeneous-aware cache partitioningParallel Computing10.1016/j.parco.2014.07.00640:10(710-721)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.parco.2014.07.006
Show More Cited By

Index Terms

Recommendations

Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

On-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
Dynamic Partitioning of Shared Cache Memory

This paper proposes dynamic cache partitioning amongst simultaneously executing processes/threads. We present a general partitioning scheme that can be applied to set-associative caches.
Since memory reference characteristics of processes/threads can ...
An adaptive chip multiprocessor cache hierarchy

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 1, Issue 1

August 2008

1216 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2008

Published in PVLDB Volume 1, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
431
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Carra DNeglia GGavrilovska AZadok E(2020)Efficient miss ratio curve computation for heterogeneous content popularityProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489197(741-751)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489197
Zhang WLiu FFan R(2014)Cache matchingProceedings of the High Performance Computing Symposium10.5555/2663510.2663517(1-8)Online publication date: 13-Apr-2014
https://dl.acm.org/doi/10.5555/2663510.2663517
Li YFeng DShi Z(2014)Heterogeneous-aware cache partitioningParallel Computing10.1016/j.parco.2014.07.00640:10(710-721)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.parco.2014.07.006
Li YFeng DShi ZSun XChen YRoth P(2013)Enhancing both fairness and performance using rate-aware dynamic storage cache partitioningProceedings of the 2013 International Workshop on Data-Intensive Scalable Computing Systems10.1145/2534645.2534650(31-36)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.1145/2534645.2534650
Soundararajan GGhanbari SLupei DChen JAmza CNg JJacobsen HZou Y(2012)Dynamic global resource allocation in shared data centers and cloudsProceedings of the 2012 Conference of the Center for Advanced Studies on Collaborative Research10.5555/2399776.2399779(11-26)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.5555/2399776.2399779
Ghanbari SSoundararajan GAmza C(2010)A query language and runtime tool for evaluating behavior of multi-tier serversACM SIGMETRICS Performance Evaluation Review10.1145/1811099.181105538:1(131-142)Online publication date: 14-Jun-2010
https://dl.acm.org/doi/10.1145/1811099.1811055
Ghanbari SSoundararajan GAmza CMisra VBarford PSquillante M(2010)A query language and runtime tool for evaluating behavior of multi-tier serversProceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems10.1145/1811039.1811055(131-142)Online publication date: 14-Jun-2010
https://dl.acm.org/doi/10.1145/1811039.1811055
Prabhakar RSrikantaiah SKandemir MPatrick CBoku TNakashima HMendelson A(2010)Adaptive multi-level cache allocation in distributed storage architecturesProceedings of the 24th ACM International Conference on Supercomputing10.1145/1810085.1810115(211-221)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.1145/1810085.1810115
Liu XAboulnaga ASalem KLi X(2009)CLICProccedings of the 7th conference on File and storage technologies10.5555/1525908.1525930(297-310)Online publication date: 24-Feb-2009
https://dl.acm.org/doi/10.5555/1525908.1525930
Soundararajan GLupei DGhanbari SPopescu AChen JAmza C(2009)Dynamic resource allocation for database servers running on virtual storageProccedings of the 7th conference on File and storage technologies10.5555/1525908.1525914(71-84)Online publication date: 24-Feb-2009
https://dl.acm.org/doi/10.5555/1525908.1525914
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents