在 IaaS 云中基于复制执行使用竞价型实例的在线算法
An Online Algorithm Based on Replication for Using Spot Instances in IaaS Clouds
-
摘要:研究背景 目前，国内阿里云、国外亚马逊等云计算服务提供商通过提供多种计费方式的计算资源，满足不同需求的用户。如亚马逊EC2提供三种定价模式，分别为：按需定价实例、Spot实例与预留实例。Spot实例往往提供大幅度的折扣。在Spot实例中，用户可以自己定价，设定愿意接受的最高价格，来租用EC2服务的闲散资源。亚马逊会根据供需情况周期性的发布即时价格，当用户最高限价高于即时价格时，服务进行，且实际支付价格为系统即时价格。当用户最高限价低于即时价格时，系统自动终止服务。目的 对于Spot实例这类竞价型实例，价格极低，但同时带来了竞价失败而产生的诸多风险，用户必须仔细权衡Spot实例较低的成本与较差的可用性。因此，IaaS 用户现在面临的一个重要问题是，如何以较高性价比且低风险的方式使用Spot实例。本研究旨在设计一个可靠的在线算法，以保证使用Spot实例的经济性和可靠性。通过此算法，用户使用Spot实例具备高性价比且与使用按需实例一样稳定。方法 基于复制策略和检查点机制（容错机制），我们提出了一个副本在线终止算法，在确保实例运行稳定性的同时优化使用Spot实例的成本。我们通过理论证明，在大多数情况下，我们提出的在线算法的成本不会超过知道确切未来的最佳离线算法成本的两倍。通过大量的实验，我们验证我们的算法在大多数情况下的竞争比例不超2。在其他情况下，也可以达到保证的竞争比率。结果 通过本文提出的在线算法，可以引导云用户在不知道任何未来价格信息的情况下，决定是否终止亚马逊 EC2 Spot市场的备份。从理论上讲，我们证明这种在线算法可以达到一个有保证的竞争比例。此外，我们模拟了超过1 700 个 AWS Spot实例的历史价格，实验结果表明，与按需实例相比我们的在线算法比按需实例可平均节省30%以上的成本，与其它基准算法相比，也可以实现显著节省。结论 在本文中，我们设计了一个结合复制执行与检查点的容错机制，更好的保障了竞价型实例的稳定性；设计了一个确定性在线算法，动态终止副本来节省成本。与传统方法相比较，所提出的算法无需先验知识，且能显著节省成本。此外，本工作没有考虑的一个情况是在未知的工作负载下选择Spot实例，这意味着我们必须计算工作负载的预期运行时间。因此，我们未来的工作是研究新的在线算法，可以处理更复杂的情况，包括未知的工作负载。此外，我们会尝试更先进的检查点设置策略，以引导云用户稳定地使用Spot实例，并降低使用计算服务的成本。Abstract: Infrastructure-as-a-Service (IaaS) cloud platforms offer resources with diverse buying options. Users can run an instance on the on-demand market which is stable but expensive or on the spot market with a significant discount. However, users have to carefully weigh the low cost of spot instances against their poor availability. Spot instances will be revoked when the revocation event occurs. Thus, an important problem that an IaaS user faces now is how to use spot instances in a cost-effective and low-risk way. Based on the replication-based fault tolerance mechanism, we propose an online termination algorithm that optimizes the cost of using spot instances while ensuring operational stability. We prove that in most cases, the cost of our proposed online algorithm will not exceed twice the minimum cost of the optimal offline algorithm that knows the exact future a priori. Through a large number of experiments, we verify that our algorithm in most cases has a competitive ratio of no more than 2, and in other cases it can also reach the guaranteed competitive ratio.
下载: