Weichao Guo
ABSTRACT
Amazon EC2 has built the Spot Instance Marketplace and offers a new type of virtual machine instances called as spot instances. These instances are less expensive but considered failure-prone. Despite the underlying hardware status, if the bidding price is lower than the market price, such an instance will be terminated.
Distributed systems can be built from the spot instances to reduce the cost while still tolerating instance failures. For example, embarrassingly parallel jobs can use the spot instances by re-executing failed tasks. The bidding framework for such jobs simply selects the spot price as the bid. However, highly available services like lock service or storage service cannot use the similar techniques for availability consideration. The spot instance failure model is different to that of normal instances (fixed failure probability in traditional distributed model). This makes the bidding strategy more complex to keep service availability for such systems.
We formalize this problem and propose an availability and cost aware bidding framework. Experiment results show that our bidding framework can reduce the costs of a distributed lock service and a distributed storage service by 81.23% and 85.32% respectively while still keeping availability level the same as it is by using on-demand instances.
- O. Agmon Ben-Yehuda, M. Ben-Yehuda, A. Schuster, and D. Tsafrir. Deconstructing amazon ec2 spot instance pricing. ACM Trans. Econ. Comput., 1(3):16:1--16:20, Sept. 2013. Google Scholar
Digital Library
- Y. Amir and A. Wool. Optimal availability quorum systems: Theory and practice. Information Processing Letters, 65(5):223--228, 1998. Google ScholarDigital Library
- A. Andrzejak, D. Kondo, and S. Yi. Decision model for cloud computing under sla constraints. In Proceedings of the 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS '10, pages 257--266, Washington, DC, USA, 2010. IEEE Computer Society. Google ScholarDigital Library
- https://aws.amazon.com/about-aws/globalinfrastructure/.Google Scholar
- http://aws.amazon.com/ec2/instance-types/.Google Scholar
- http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/using-spot-limits.html.Google Scholar
- http://aws.amazon.com/ec2/sla/.Google Scholar
- J. Baker, C. Bond, J. C. Corbett, J. Furman, A. Khorlin, J. Larson, J.-M. Léon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, volume 11, pages 223--234, 2011.Google Scholar
- V. Barbu and N. Limnios. Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications: Their Use in Reliability and DNA Analysis. Springer Publishing Company, Incorporated, 1 edition, 2008. Google ScholarDigital Library
- W. J. Bolosky, D. Bradshaw, R. B. Haagens, N. P. Kusters, and P. Li. Paxos replicated state machines as the basis of a high-performance data store. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, pages 141--154, Berkeley, CA, USA, 2011. USENIX Association. Google ScholarDigital Library
- https://github.com/boto/boto.Google Scholar
- D. R. Brillinger, P. M. Guttorp, and F. P. Schoenberg. Point processes, temporal. In Encyclopedia of Environmetrics. John Wiley & Sons, Ltd, 2006.Google Scholar
- M. Burrows. The chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI '06, pages 335--350, Berkeley, CA, USA, 2006. USENIX Association. Google ScholarDigital Library
- B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, J. Haridas, C. Uddaraju, H. Khatri, A. Edwards, V. Bedekar, S. Mainali, R. Abbasi, A. Agarwal, M. F. u. Haq, M. I. u. Haq, D. Bhardwaj, S. Dayanand, A. Adusumilli, M. McNett, S. Sankaran, K. Manivannan, and L. Rigas. Windows azure storage: A highly available cloud storage service with strong consistency. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 143--157, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- N. Chohan, C. Castillo, M. Spreitzer, M. Steinder, A. Tantawi, and C. Krintz. See spot run: using spot instances for mapreduce workflows. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, pages 7--7. USENIX Association, 2010. Google ScholarDigital Library
- J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 251--264, Berkeley, CA, USA, 2012. USENIX Association. Google ScholarDigital Library
- G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, SOSP '07, pages 205--220, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- D. K. Gifford. Weighted voting for replicated data. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles, SOSP '79, pages 150--162, New York, NY, USA, 1979. ACM. Google ScholarDigital Library
- G. Grimmett and D. Stirzaker. Probability and random processes, volume 2. Oxford Univ Press, 1992.Google Scholar
- http://hadoop.apache.org.Google Scholar
- C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. Erasure coding in windows azure storage. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference, USENIX ATC'12, pages 2--2, Berkeley, CA, USA, 2012. USENIX Association. Google ScholarDigital Library
- B. Javadi, R. K. Thulasiramy, and R. Buyya. Statistical modeling of spot instance prices in public cloud environments. In Proceedings of the 2011 Fourth IEEE International Conference on Utility and Cloud Computing, UCC '11, pages 219--228, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- L. Lamport. Paxos made simple. ACM Sigact News, 32(4):18--25, 2001.Google Scholar
- H. Liu. Cutting mapreduce cost with spot market. In Proceedings of the 3rd USENIX Conference on Hot Topics in Cloud Computing, HotCloud'11, pages 6--6, Berkeley, CA, USA, 2011. USENIX Association. Google ScholarDigital Library
- M. Mao and M. Humphrey. A performance study on the vm startup time in the cloud. In Cloud Computing (CLOUD), 2012 IEEE 5th International Conference on, pages 423--430, June 2012. Google ScholarDigital Library
- S. Mu, K. Chen, Y. Wu, and W. Zheng. When paxos meets erasure code: Reduce network and storage cost in state machine replication. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing, HPDC '14, pages 61--72, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- D. Peleg and A. Wool. The availability of quorum systems. Information and Computation, 123(2):210--223, 1995. Google ScholarDigital Library
- L. Rizzo. Effective erasure codes for reliable computer communication protocols. SIGCOMM Comput. Commun. Rev., 27(2):24--36, Apr. 1997. Google ScholarDigital Library
- M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur. Xoring elephants: novel erasure codes for big data. In Proceedings of the 39th international conference on Very Large Data Bases, PVLDB'13, pages 325--336. VLDB Endowment, 2013. Google ScholarDigital Library
- http://aws.amazon.com/ec2/purchasing-options/spot-instances/.Google Scholar
- Y. Song, M. Zafer, and K.-W. Lee. Optimal bidding in spot instance market. In INFOCOM, 2012 Proceedings IEEE, pages 190--198. IEEE, 2012.Google ScholarCross Ref
- M. Spasojevic and P. Berman. Voting as the optimal static pessimistic scheme for managing replicated data. Parallel and Distributed Systems, IEEE Transactions on, 5(1):64--73, Jan 1994. Google ScholarDigital Library
- Z. Tong and R. Kain. Vote assignments in weighted voting mechanisms. In Reliable Distributed Systems, 1988. Proceedings., Seventh Symposium on, pages 138--143, Oct 1988.Google ScholarCross Ref
- S. Wee. Debunking real-time pricing in cloud computing. In Cluster, Cloud and Grid Computing (CCGrid), 2011 11th IEEE/ACM International Symposium on, pages 585--590, May 2011. Google ScholarDigital Library
- S. Yi, A. Andrzejak, and D. Kondo. Monetary cost-aware checkpointing and migration on amazon cloud spot instances. IEEE Transactions on Services Computing, 5(4):512--524, 2012. Google ScholarDigital Library
- S. Yi, D. Kondo, and A. Andrzejak. Reducing costs of spot instances via checkpointing in the amazon elastic compute cloud. In Cloud Computing (CLOUD), 2010 IEEE 3rd International Conference on, pages 236--243, July 2010. Google ScholarDigital Library
Index Terms
- Bidding for Highly Available Services with Low Price in Spot Instance Market
Recommendations
Perceptive bidding strategy for Amazon EC2 spot instance market
Spot pricing is an auction based market mechanism introduced by Amazon EC2 to sell available cloud resources at a low cost without any availability guarantee. Bid prices submitted by users directly affect reliability of the instance acquired. In ...
Interplay between Buy-It-Now price and last minute bidding on online bidding strategies
Sellers and buyers on online auction sites like eBay have the option of setting and executing auction parameters such as auction length, Buy-It-Now price, starting price, reserve price, etc. Understanding why bidders choose to execute the Buy-It-Now ...
False-name bidding in first-price combinatorial auctions with incomplete information
AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2False-name bids are bids submitted by a single agent under multiple fictitious names such as multiple e-mail addresses. False-name bidding can be a serious fraud in Internet auctions since identifying each participant is virtually impossible. It is ...
Comments