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

research-article

Ginseng: market-driven memory allocation

Authors:

Orna Agmon Ben-Yehuda,

Muli Ben-Yehuda,

Assaf Schuster,

Ahuva Mu'alemAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 7

Pages 41 - 52

https://doi.org/10.1145/2674025.2576197

Published: 01 March 2014 Publication History

Abstract

Physical memory is the scarcest resource in today's cloud computing platforms. Cloud providers would like to maximize their clients' satisfaction by renting precious physical memory to those clients who value it the most. But real-world cloud clients are selfish: they will only tell their providers the truth about how much they value memory when it is in their own best interest to do so. How can real-world cloud providers allocate memory efficiently to those (selfish) clients who value it the most?

We present Ginseng, the first market-driven cloud system that allocates memory efficiently to selfish cloud clients. Ginseng incentivizes selfish clients to bid their true value for the memory they need when they need it. Ginseng continuously collects client bids, finds an efficient memory allocation, and re-allocates physical memory to the clients that value it the most. Ginseng achieves a 6.2×--15.8x improvement (83%--100% of the optimum) in aggregate client satisfaction when compared with state-of-the-art approaches for cloud memory allocation.

References

[1]

O. Agmon Ben-Yehuda, M. Ben-Yehuda, A. Schuster, and D. Tsafrir. Deconstructing Amazon EC2 spot instance pricing. In IEEE Conf. on Cloud Computing Technology and Science (CloudCom), 2011.

Digital Library

[2]

O. Agmon Ben-Yehuda, M. Ben-Yehuda, A. Schuster, and D. Tsafrir. The resource-as-a-service (raas) cloud. In USENIX Conf. on Hot Topics in Cloud Computing (HotCloud), 2012.

Digital Library

[3]

M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. A view of cloud computing. Communications of the ACM, 53 (4): 50--58, 2010.

Digital Library

[4]

J. Bae, E. Beigman, R. Berry, M. L. Honig, and R. Vohra. An efficient auction for non concave valuations. In Int'l Meeting of the Society for Social Choice and Welfare, 2008.

[5]

M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, A. R. Karlin, C. Mathieu, and M. Schwarz. Greedy bidding strategies for keyword auctions. In ACM Conf. on Electronic Commerce (EC), pages 262--271, 2007.

Digital Library

[6]

J. S. Chase, D. C. Anderson, P. N. Thakar, A. M. Vahdat, and R. P. Doyle. Managing energy and server resources in hosting centers. In ACM Symposium on Operating Systems Principles (SOSP), 2001.

Digital Library

[7]

E. H. Clarke. Multipart pricing of public goods. Public Choice, 11 (1): 17--33, Sep 1971.

[8]

G. D'Alesandre. Updated app engine pricing faq! Web site, June 2011. http://tinyurl.com/D-Alesandre.

[9]

S. Dobzinski and N. Nisan. Mechanisms for multi-unit auctions. J. of Artificial Intelligence Research, 37: 85--98, 2010.

Digital Library

[10]

K. E. Drexler and M. S. Miller. Incentive engineering for computational resource management. In The Ecology of Computation, pages 231--266. Elsevier Science Publishers, 1988.

[11]

Z. Gong, X. Gu, and J. Wilkes. Press: Predictive elastic resource scaling for cloud systems. In Int'l Conf. on Network and Service Management (CNSM), pages 9--16, 2010.

[12]

A. Gordon, M. Hines, D. Da Silva, M. Ben-Yehuda, M. Silva, and G. Lizarraga. Ginkgo: Automated, application-driven memory overcommitment for cloud computing. In Runtime Environments/Systems, Layering, & Virtualized Environments Workshop (ASPLOS RESOLVE), 2011.

[13]

T. Groves. Incentives in teams. Econometrica, 41 (4): 617--631, Jul 1973.

[14]

C. Grzegorczyk, S. Soman, C. Krintz, and R. Wolski. Isla vista heap sizing: Using feedback to avoid paging. In Int'l Symposium on Code Generation and Optimization (CGO), pages 325--340, 2007.

Digital Library

[15]

J. Heo, X. Zhu, P. Padala, and Z. Wang. Memory overbooking and dynamic control of xen virtual machines in consolidated environments. In IFIP/IEEE Symposium on Integrated Management (IM), 2009.

Digital Library

[16]

M. Hertz, S. Kane, E. Keudel, T. Bai, C. Ding, X. Gu, and J. E. Bard. Waste not, want not: resource-based garbage collection in a shared environment. In Int'l Symposium on Memory Management (ISMM), 2011.

Digital Library

[17]

M. Hines, A. Gordon, M. Silva, D. D. Silva, K. D. Ryu, and M. Ben-Yehuda. Applications know best: Performance-driven memory overcommit with ginkgo. In IEEE Conf. on Cloud Computing Technology and Science (CloudCom), 2011.

Digital Library

[18]

S. T. Jones, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Geiger: monitoring the buffer cache in a virtual machine environment. In ACM Architectural Support for Programming Languages & Operating Systems (ASPLOS), 2006.

Digital Library

[19]

F. Kelly. Charging and rate control for elastic traffic. European Trans. on Telecommunications, 8: 33--37, 1997.

[20]

A. Kivity, Y. Kamay, D. Laor, U. Lublin, and A. Liguori. KVM: the Linux virtual machine monitor. In Ottawa Linux Symposium (OLS), pages 225--230, 2007.

[21]

A. Lazar and N. Semret. Design and analysis of the progressive second price auction for network bandwidth sharing. Telecommunication Systems--Special issue on Network Economics, 20: 255--263, 1999.

[22]

M. Levy and S. Solomon. New evidence for the power-law distribution of wealth. Physica A, 242: 90--94, 1997.

[23]

A. G. Litke. Memory overcommitment manager. website, 2011. https://github.com/aglitke/mom.

[24]

B. Lucier, R. Paes Leme, and E. Tardos. On revenue in the generalized second price auction. In Int'l World Wide Web Conf. (WWW), 2012.

Digital Library

[25]

D. Magenheimer. Memory overcommit... without the commitment. In Xen Summit. USENIX association, June 2008.

[26]

P. Maillé and B. Tuffin. Multi-bid auctions for bandwidth allocation in communication networks. In IEEE INFOCOM, 2004.

[27]

R. Nathuji, A. Kansal, and A. Ghaffarkhah. Q-clouds: Managing performance interference effects for qos-aware clouds. In ACM SIGOPS European Conf. on Computer Systems (EuroSys), 2010.

Digital Library

[28]

Z. Ou, H. Zhuang, J. K. Nurminen, A. Ylä-Jääski, and P. Hui. Exploiting hardware heterogeneity within the same instance type of amazon EC2. In USENIX Conf. on Hot Topics in Cloud Computing (HotCloud), 2012.

Digital Library

[29]

T.-I. Salomie, G. Alonso, T. Roscoe, and K. Elphinstone. Application level ballooning for efficient server consolidation. In ACM SIGOPS European Conf. on Computer Systems (EuroSys), pages 337--350, 2013.

Digital Library

[30]

Z. Shen, S. Subbiah, X. Gu, and J. Wilkes. Cloudscale: elastic resource scaling for multi-tenant cloud systems. In ACM Symposium on Cloud Computing (SOCC), 2011.

Digital Library

[31]

S. Soman, C. Krintz, and D. F. Bacon. Dynamic selection of application-specific garbage collectors. In Int'l Symposium on Memory Management (ISMM), 2004.

Digital Library

[32]

W. Souma. Universal structure of the personal income distribution. Fractals, 9 (04): 463--470, 2001.

[33]

B. Urgaonkar, P. Shenoy, and T. Roscoe. Resource overbooking and application profiling in a shared internet hosting platform. ACM Trans. Internet Technol., 9 (1), 2009.

Digital Library

[34]

W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J. of Finance, 16 (1), 1961.

[35]

C. Waldspurger, T. Hogg, B. A. Huberman, J. O. Kephart, and W. S. Stornetta. Spawn: a distributed computational economy. IEEE Trans. on Software Engineering, 18 (2): 103--117, 1992.

Digital Library

[36]

C. A. Waldspurger. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management. PhD thesis, Massachusetts Institute of Technology, 1995.

Digital Library

[37]

C. A. Waldspurger. Memory resource management in Vmware ESX server. In USENIX Symposium on Operating Systems Design & Implementation (OSDI), 2002.

Digital Library

[38]

T. Yang, E. D. Berger, S. F. Kaplan, and J. E. B. Moss. CRAMM: virtual memory support for garbage-collected applications. In USENIX Symposium on Operating Systems Design & Implementation (OSDI), pages 103--116, 2006.

Digital Library

[39]

W. Zhao and Z. Wang. Dynamic memory balancing for virtual machines. In ACM/USENIX Int'l Conf. on Virtual Execution Environments (VEE), pages 21--30, 2009.

Digital Library

[40]

W. Zhao, X. Jin, Z. Wang, X. Wang, Y. Luo, and X. Li. Low cost working set size tracking. In USENIX Annual Technical Conf. (ATC), 2011.

Digital Library

[41]

P. Zhou, V. Pandey, J. Sundaresan, A. Raghuraman, Y. Zhou, and S. Kumar. Dynamic tracking of page miss ratio curve for memory management. In ACM Architectural Support for Programming Languages & Operating Systems (ASPLOS), 2004.

Digital Library

Cited By

Gupta NNarayanan IHanda SChakraborti SThapar PShan BRao ALiu YWang PWu YGao QCheng CYou SHuang LFan JYu KLin KMu TMalani PWang HLu TZhang P(2024)Dynamic Idle Resource Leasing To Safely Oversubscribe Capacity At MetaProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698537(792-810)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698537
Di PSun ZCheng LHan MYang LYang L(2023)LED Light Irradiations Differentially Affect the Physiological Characteristics, Ginsenoside Content, and Expressions of Ginsenoside Biosynthetic Pathway Genes in Panax ginsengAgriculture10.3390/agriculture1304080713:4(807)Online publication date: 31-Mar-2023
https://doi.org/10.3390/agriculture13040807
Agmon SBen-Yehuda OSchuster ABreitgand DYadgar GPorter DEyal I(2018)Collusion in Cloud Computing AuctionsProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211911(113-113)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211911
Show More Cited By

Index Terms

Ginseng: market-driven memory allocation
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Main memory

Recommendations

Ginseng: market-driven memory allocation
VEE '14: Proceedings of the 10th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments

Physical memory is the scarcest resource in today's cloud computing platforms. Cloud providers would like to maximize their clients' satisfaction by renting precious physical memory to those clients who value it the most. But real-world cloud clients ...
Ginseng: market-driven LLC allocation
USENIX ATC '16: Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference

Cloud providers must dynamically allocate their physical resources to the right client to maximize the benefit that they can get out of given hardware. Cache Allocation Technology (CAT) makes it possible for the provider to allocate last level cache to ...
DMSS: A Dynamic Memory Scheduling System in Server Consolidation Environments
ISORCW '12: Proceedings of the 2012 IEEE 15th International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops

As the foundation of cloud computing, Server consolidation allows multiple computer infrastructures running as virtual machines in a single physical node. It improves the utilization of most kinds of resource but memory under x86 architecture. Because ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 7

VEE '14

July 2014

222 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2674025

Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Sarita Adve
University of Illinois at Urbana-Champ

Issue’s Table of Contents

VEE '14: Proceedings of the 10th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments
March 2014
236 pages
ISBN:9781450327640
DOI:10.1145/2576195
General Chair:
Martin Hirzel
IBM Research
,
Program Chairs:
Erez Petrank
Technion
,
Dan Tsafrir
Technion

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2014

Published in SIGPLAN Volume 49, Issue 7

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
492
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gupta NNarayanan IHanda SChakraborti SThapar PShan BRao ALiu YWang PWu YGao QCheng CYou SHuang LFan JYu KLin KMu TMalani PWang HLu TZhang P(2024)Dynamic Idle Resource Leasing To Safely Oversubscribe Capacity At MetaProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698537(792-810)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698537
Di PSun ZCheng LHan MYang LYang L(2023)LED Light Irradiations Differentially Affect the Physiological Characteristics, Ginsenoside Content, and Expressions of Ginsenoside Biosynthetic Pathway Genes in Panax ginsengAgriculture10.3390/agriculture1304080713:4(807)Online publication date: 31-Mar-2023
https://doi.org/10.3390/agriculture13040807
Agmon SBen-Yehuda OSchuster ABreitgand DYadgar GPorter DEyal I(2018)Collusion in Cloud Computing AuctionsProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211911(113-113)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211911
Li DDong MTang YOta K(2018)A novel disk I/O scheduling framework of virtualized storage systemCluster Computing10.1007/s10586-017-1363-9Online publication date: 14-Feb-2018
https://doi.org/10.1007/s10586-017-1363-9
Ben-David DSagy GAbboud AKeren DSchuster A(2018)Violation Resolution in Distributed Stream NetworksComputational Intelligence, Cyber Security and Computational Models. Models and Techniques for Intelligent Systems and Automation10.1007/978-981-13-0716-4_13(144-171)Online publication date: 11-Sep-2018
https://doi.org/10.1007/978-981-13-0716-4_13
Movsowitz DFunaro LAgmon SAgmon Ben-Yehuda ODunkelman O(2018)Why Are Repeated Auctions in RaaS Clouds Risky?Economics of Grids, Clouds, Systems, and Services10.1007/978-3-030-13342-9_4(39-51)Online publication date: 18-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-13342-9_4
Agmon SAgmon Ben-Yehuda OSchuster A(2018)Preventing Collusion in Cloud Computing AuctionsEconomics of Grids, Clouds, Systems, and Services10.1007/978-3-030-13342-9_3(24-38)Online publication date: 18-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-13342-9_3
Cidon ARushton DRumble SStutsman RSilva DFord B(2017)MemshareProceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference10.5555/3154690.3154722(321-334)Online publication date: 12-Jul-2017
https://dl.acm.org/doi/10.5555/3154690.3154722
Simão JEsteves SVeiga L(2017)SmartGC: Online Memory Management Prediction for PaaS Cloud ModelsOn the Move to Meaningful Internet Systems. OTM 2017 Conferences10.1007/978-3-319-69462-7_25(370-388)Online publication date: 20-Oct-2017
https://doi.org/10.1007/978-3-319-69462-7_25
Fonseca ASimão JVeiga L(2017)FairCloud: Truthful Cloud Scheduling with Continuous and Combinatorial AuctionsOn the Move to Meaningful Internet Systems. OTM 2017 Conferences10.1007/978-3-319-69459-7_5(68-85)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1007/978-3-319-69459-7_5
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents