PaperlayerView exact revision on arXiv

Source-linked AI summary

Reliable Provisioning of Spot Instances for Compute-intensive Applications

William Voorsluys, Rajkumar Buyya

arXiv:1110.5969v1cs.DC

TL;DR

Intermittent spot-instance availability can prolong compute-intensive jobs or prevent them from meeting deadlines. The paper combines price and runtime estimation with fault-tolerance techniques in a provisioning policy, and reports that migration yields superior results in virtually all metrics when mechanisms are properly combined and tuned.

Abstract

from arXiv · show

Cloud computing providers are now offering their unused resources for leasing in the spot market, which has been considered the first step towards a full-fledged market economy for computational resources. Spot instances are virtual machines (VMs) available at lower prices than their standard on-demand counterparts. These VMs will run for as long as the current price is lower than the maximum bid price users are willing to pay per hour. Spot instances have been increasingly used for executing compute-intensive applications. In spite of an apparent economical advantage, due to an intermittent nature of biddable resources, application execution times may be prolonged or they may not finish at all. This paper proposes a resource allocation strategy that addresses the problem of running compute-intensive jobs on a pool of intermittent virtual machines, while also aiming to run applications in a fast and economical way. To mitigate potential unavailability periods, a multifaceted fault-aware resource provisioning policy is proposed. Our solution employs price and runtime estimation mechanisms, as well as three fault tolerance techniques, namely checkpointing, task duplication and migration. We evaluate our strategies using trace-driven simulations, which take as input real price variation traces, as well as an application trace from the Parallel Workload Archive. Our results demonstrate the effectiveness of executing applications on spot instances, respecting QoS constraints, despite occasional failures.

I. INTRODUCTION

Spot instances can reduce the cost of compute-intensive work, but their prices vary across markets and instances may be terminated when prices exceed users’ bids. Bid choices and fault mitigation therefore matter for balancing cost, reliability, and deadlines.

I. INTRODUCTION

  • Spot prices vary by datacenter, instance type, and operating system, and may exceed on-demand prices, complicating resource selection.On-demand prices can act as an upper bound for users who would rather lease a reliable instance at or above that price.Source: §I · p. 1, A. Bidding strategies and the need for… · p. 2

A. Bidding strategies and the need for fault tolerance

  • Out-of-bid terminations can make applications run longer or prevent them from meeting deadlines.The provider may terminate an instance without prior notice when its price rises above the user's bid.Source: §I · p. 1, A. Bidding strategies and the need for… · p. 2
  • The spot market is described as an auction with incentives for users to bid according to the value they place on the resource.The paper discusses a uniform-price auction model in which all winning users pay the lowest winning bid, while noting possible provider price intervention.Source: A. Bidding strategies and the need for… · p. 2
  • Bid choices reflect users’ reliability needs, price history, and willingness to wait, while low bids can save money at the cost of longer execution.Users may postpone non-urgent work for lower prices, and low bidding can exploit the unpaid partial hour before an out-of-bid termination.Source: §I · p. 1, A. Bidding strategies and the need for… · p. 2
  • Aggressive bidding can increase failures and lost work, undermining savings; price histories can inform more deliberate provisioning decisions.Spot-instance billing rules include hourly granularity and non-payment of the final partial hour when the provider terminates an instance.Source: A. Bidding strategies and the need for… · p. 2

B. Our contribution

The paper proposes a provisioning strategy for compute-intensive jobs on intermittent VMs, combining price-informed bidding with fault-tolerance mechanisms. It evaluates migration and job duplication alongside checkpointing.

B. Our contribution

  • The proposed approach combines bidding strategies and reliability mechanisms to maximize reliability while minimizing costs on a spot-instance platform.The strategy aims to run applications quickly and economically while tolerating sudden VM unavailability.Source: B. Our contribution · p. 2
  • A bidding mechanism estimates future spot prices to inform bidding decisions.The modeled architecture identifies runtime estimation as prior work and fault tolerance as the focus here.Source: B. Our contribution · p. 2, Figure 1 · p. 3
  • The paper evaluates migration and job duplication against an existing checkpointing-based approach.The contribution list identifies these as fault-tolerance techniques for the provisioning approach.Source: B. Our contribution · p. 2

II. RELATED WORK

Prior work studied bidding decisions and checkpointing for spot instances. This paper evaluates checkpointing alongside migration and job duplication.

II. RELATED WORK

  • Andrzejak et al. proposed a probabilistic model that uses past Amazon EC2 prices to recommend bids for meeting a budget or deadline.The model estimates achievable budget and deadline values at a specified confidence.Source: §II · p. 3
  • Yi et al. evaluated hourly and price-rise-triggered checkpointing policies, which tolerated failures and reduced costs relative to on-demand instances despite overhead.The present work implements a checkpointing mechanism based on that work for comparison with other fault-tolerance approaches.Source: §II · p. 3

III. RESOURCE PROVISIONING IN A SPOT INSTANCES-BASED COMPUTATIONAL PLATFORM

The paper summarizes a prior policy for assembling a spot-instance platform and scheduling deadline-constrained jobs. The policy estimates runtimes, considers job urgency and prices, and chooses whether to reuse, extend, start, or defer a VM lease.

III. RESOURCE PROVISIONING IN A SPOT INSTANCES-BASED COMPUTATIONAL PLATFORM

  • The modeled provider follows Amazon EC2 spot-market rules, including bid-based provisioning and termination and hourly pricing.A client specifies an instance type and bid; if no datacenter is specified, the provider chooses the most economical one.Source: §III · p. 3
  • Jobs are moldable across CPU cores but limited to one VM, with preferred instance types determined using estimated parallelism and runtime.The model uses Downey’s speedup model and the Cirne and Berman model to generate job parallelism parameters.Source: §III · pp. 3–4
  • At regular intervals, the algorithm estimates each job’s runtime on available instance types and first tries an idle VM with enough time remaining in the billing hour.If that fails, it can try a VM expected to become idle soon, using runtime estimates for its running jobs and the incoming job.Source: §III · p. 4
  • If a job remains unallocated, the policy chooses whether to extend a lease, start a VM, or postpone provisioning based on urgency and pricing conditions.The policy is designed for a stream of deadline-constrained jobs on a platform composed solely of spot instances.Source: §III · pp. 3–4
  • The urgency factor estimates how long a job can wait for provisioning to improve its chance of meeting the deadline; higher α makes the algorithm more conservative.The calculation uses deadline, current time, estimated runtime on the preferred instance type, and a fixed five-minute VM provisioning time.Source: §III · p. 4

IV. MECHANISMS TO ACHIEVE FAULT TOLERANCE

The policy combines price and runtime estimates with job urgency to guide bidding and resource start times, then adds fault-tolerance mechanisms for intermittent VMs. It targets price-triggered unavailability and assumes other failure types do not occur.

IV. MECHANISMS TO ACHIEVE FAULT TOLERANCE

  • The policy pairs price-based bidding and urgency-aware provisioning with checkpointing, migration, and job duplication to address spot-instance unavailability.The mechanisms target out-of-bid failures; hardware faults and network interruptions are excluded.Source: §IV · p. 4

A. Bidding strategies: estimating cost and jobs’ urgency

  • Bidding uses price and runtime estimates to balance failure risk and spending, while urgency helps choose when to start a machine for a job.This is intended to avoid provisioning non-urgent jobs too early or urgent jobs too late.Source: A. Bidding strategies: estimating cost… · p. 4
  • Runtime estimates use the average runtime of the same user’s two preceding jobs, a method selected based on prior comparisons.The earlier comparisons considered cost, deadline violations, and system utilization.Source: A. Bidding strategies: estimating cost… · p. 4
  • Five bidding strategies produce maximum hourly prices per instance, using a one-week price-history window where applicable and bid granularity G = 0.001.The history is specific to each instance-type, OS, and datacenter combination; urgency can override bids below the current price.Source: A. Bidding strategies: estimating cost… · p. 4

B. Hourly Checkpointing

Hourly checkpointing saves VM state at hour boundaries so computation can be restored after a failure. Under this approach, a checkpointed VM resumes only when its original fixed-bid request is in-bid again.

B. Hourly Checkpointing

  • The saved state restores computation after failure, and the approach assumes VM-level checkpointing captures the application state.The VM state includes memory and application and process state.Source: B. Hourly Checkpointing · pp. 4–5
  • Hourly checkpointing saves VM state at hour boundaries, limiting paid computation loss because failed partial hours are not charged.The paper treats checkpointing an application as saving the entire VM state; applications need not be modified, but provider support is required.Source: B. Hourly Checkpointing · p. 5
  • A checkpointed VM waits for its original request’s fixed bid and machine type to become in-bid again, rather than switching to another lease.The following migration approach instead relocates saved state to hasten job completion.Source: B. Hourly Checkpointing · p. 5

C. Migration of persistent VM state

Migration saves VM state to a global filesystem and, after an out-of-bid event, restores it on a newly leased instance. The lease choice weighs estimated completion cost against restoration overhead, including the higher overhead of moving across datacenters.

C. Migration of persistent VM state

  • After an out-of-bid event, migration restores a saved VM state on a newly leased instance instead of waiting for the original request to return in-bid.The state is saved frequently on a global filesystem.Source: C. Migration of persistent VM state · p. 5
  • The algorithm chooses the estimated cheaper option for the remaining job duration: a higher bid for the same type, a different type in the same datacenter, or a suitable VM in another datacenter.Cross-datacenter restoration is assumed to have higher overhead, which the relocation decision accounts for.Source: C. Migration of persistent VM state · p. 5
  • Snapshot creation pauses VM computation, and its saving overhead is modeled as the time to serialize memory to a global filesystem.The model uses memory size and rates from prior experiments; same-datacenter write and restore rates are 63.67 MB/s and 81.27 MB/s, respectively.Source: C. Migration of persistent VM state · p. 5

D. Duplication of long jobs

The paper evaluates task duplication as a simple fault-tolerance option for long jobs on spot instances. Each qualifying job receives a replica scheduled to avoid sharing the original job’s datacenter and instance type.

D. Duplication of long jobs

  • Task duplication requires neither application- nor provider-assisted techniques, unlike VM-based checkpointing and migration.The paper evaluates it as a simpler way to deploy applications on spot instances.Source: D. Duplication of long jobs · p. 5
  • Task duplication targets longer jobs, for which replicas can increase the chance of meeting deadlines amid frequent spot-price changes.The technique creates one replica for each job estimated to run for more than 1 hour.Source: D. Duplication of long jobs · p. 5
  • Each replica uses the regular scheduling policy but avoids the original job’s datacenter and instance-type combination.The paper states that two jobs using the same datacenter and instance type would fail together when the price rises.Source: D. Duplication of long jobs · p. 5

V. PERFORMANCE EVALUATION

The evaluation uses trace-driven discrete-event simulations to examine bidding, urgency-factor settings, and fault-tolerance mechanisms. It draws on historical spot prices and a bursty LHC Grid job stream, with generated runtime estimates and deadlines.

V. PERFORMANCE EVALUATION

  • The policy is evaluated using monetary cost, deadline violations, and dollars per useful computation, reflecting a trade-off between meeting deadlines and provisioning cost.Dollars per useful computation is a relative metric; cost and deadline violations are absolute metrics.Source: §V · p. 6

A. Experimental design

  • The experiments vary bidding strategy, urgency-factor modifier α, and fault-tolerance mechanism, with 5,952 configurations evaluated across an average of 31 simulation runs.Not every factor combination was simulated; High bidding was not paired with fault tolerance because it avoids failures.Source: A. Experimental design · p. 6
  • The modeled provider has four US-EAST datacenters and five standard or high-CPU instance types, using 100 days of spot-price traces from 2011.The traces span July 5 to October 15, 2011.Source: Cloud characteristics · p. 6
  • The workload contains 100,000 bursty, variable-length LHC Grid jobs submitted over seven simulated days.Job moldability parameters are assumed known by the broker.Source: Workload · p. 6
  • Runtime estimates are generated using the Tzafrir et al. model, and deadlines are set using a random multiplier from 1.5 to 4 times each estimate.Each deadline is the job’s submission time plus its maximum allowed runtime.Source: Workload · p. 6

B. Effects of bidding strategies and urgency factor

The evaluation finds that the best bidding, urgency, and fault-tolerance choices depend on the objective. Migration with Minimum bidding and α = 2 minimizes cost, while α = 8 yields the fewest deadline violations.

B. Effects of bidding strategies and urgency factor

  • Higher bids tend to perform better in cost and deadline violations; low-bid strategies experience more failures, lost work, and consequently higher costs.On-demand avoids failures from minor price increases and avoids the high-price costs incurred by the very high-bid High strategy.Source: B. Effects of bidding strategies and… · p. 7
  • α = 2 yields the lowest costs, but α values of 1 and 2 lead to many more deadline violations; conservative settings bring virtually none at significantly higher cost.For most bidding strategies, the cost difference between α = 1 and α = 2 is not statistically significant.Source: B. Effects of bidding strategies and… · p. 7

C. Migration, checkpointing, and job duplication

  • Migration performs better with lower bids such as Minimum and Current, whereas checkpointing benefits from higher bids such as Mean and On-demand.Migration can choose other instance types across datacenters after an out-of-bid event; checkpointing remains bound to a persistent request.Source: C. Migration, checkpointing, and job… · p. 7
  • Job duplication costs much more than using no fault tolerance, although it offers a simple option when an extra level of redundancy is required.The paper reports this cost pattern across the evaluated cases.Source: C. Migration, checkpointing, and job… · p. 7
  • Migration with Minimum bidding and α = 2 produced the lowest cost, while α = 8 yielded 30 deadline violations among 100,000 jobs.The results confirm a trade-off between cost and deadline violations.Source: Figure 4 · p. 7, C. Migration, checkpointing, and job… · p. 7
  • Migration combinations rank consistently superior among the 10 best by dollars per useful computation, making them candidates when strict deadline compliance is expected.The metric is total cost divided by the number of jobs finished within their deadlines.Source: Table III · p. 8, C. Migration, checkpointing, and job… · p. 8

VI. CONCLUSIONS AND FUTURE WORK

The paper proposes a multifaceted policy for provisioning intermittent spot instances, combining bidding strategies, urgency estimation, and fault tolerance. Simulations report cost savings and stricter deadline adherence, while the authors note that the short, low-variability price history limits the current setting.

VI. CONCLUSIONS AND FUTURE WORK

  • The policy combines five bidding strategies, an adjustable urgency factor estimator, and three fault-tolerance approaches.The fault-tolerance mechanism using migration of VM state providers superior results in virtually all metrics.Source: §VI · p. 8
  • Simulations show that combining and tuning policy mechanisms can achieve cost savings and stricter adherence to deadlines.The evaluations use realistic conditions reflecting Amazon EC2 behavior through its price history.Source: §VI · p. 8
  • The short history and relatively low variability of Amazon EC2 prices leave higher-variability price environments as a future challenge for the policy.The authors plan to devise bidding strategies for highly variable price levels and more frequent changes.Source: §VI · p. 8

Related papers

Loading 1110.5969v1…