Repository: superfly/flyctl
Pull request #3709 (2024-07-05 22:26:20)

Better recovery
### Change Summary

What and Why:
This PR focuses on trying to change how machine updates work. Instead of failing whenever one machine isn't able to update, we instead try again, making sure to not redo any work that we'd already completed. We do this by keeping track of 'app state', which is basically a list of all the machines we have in our app. This works great since it includes machine states, machine configs, and mounts.

Sometimes, certain errors aren't worth retrying. For example, if we aren't able to acquire a lease on your machine because it's already being held, then it's more likely than not that retrying won't do any good. In that case, we return an 'unrecoverable error', and choose to completely fail the deploy. In certain cases, we could try rolling back to how we were (for example, if health checks fail we could rollback), though I'm saving that implementation for a future PR

How:
We will continue to try to finish a deploy a few times, until either:
a. the deploy completes successfully, meaning we transitioned from the old app state to the new app state
b. we've exhausted a certain number of attempts to complete a deploy without success
c. we encountered an unrecoverable error, meaning that flyctl doesn't think it's worth attempting a retry

In the first case, flyctl is much more resilient to intermittent platform errors, which can happen pretty often. In the second case, it's likely that there's something wrong with either the user's environment or the platform itself. If it's the former, then @rugwirobaker 's work to move orchestration logic into a new fly machine will help with those cases in the future. If it's the latter, we're working on setting up alerting to try and learn about these cases sooner. In the third case, the goal in the future is to add suggestions to the user to help recover from these sorts of issues.

The bulk of the code is in `internal/command/deploy/plan.go`

Related to:
https://flyio.discourse.team/t/deployments-roadmap-discussion/6326
https://flyio.discourse.team/t/deployments-roadmap-redux/6451
https://flyio.discourse.team/t/deployment-recoverability/6441
---

### Documentation

- [x] Fresh Produce
- [ ] In superfly/docs, or asked for help from docs team
- [ ] n/a


billyb2: ^ btw i'm working on adding unit testing to plan.go now, I'll make sure to have it up and reviewed before I merge


Patch:
diff --git a/internal/appconfig/remote.go b/internal/appconfig/remote.go
index d82543dc3..fd40fd339 100644
--- a/internal/appconfig/remote.go
+++ b/internal/appconfig/remote.go
@@ -37,7 +37,7 @@ func getAppV2ConfigFromMachines(ctx context.Context, appName string) (*Config, e
 	if err != nil {
 		return nil, fmt.Errorf("error listing active machines for %s app: %w", appName, err)
 	}
-	machineSet := machine.NewMachineSet(flapsClient, io, activeMachines)
+	machineSet := machine.NewMachineSet(flapsClient, io, activeMachines, true)
 	appConfig, warnings, err := FromAppAndMachineSet(ctx, appName, machineSet)
 	if err != nil {
 		return nil, fmt.Errorf("failed to grab app config from existing machines, error: %w", err)
diff --git a/internal/command/deploy/deploy.go b/internal/command/deploy/deploy.go
index 36c609e22..b211fdac9 100644
--- a/internal/command/deploy/deploy.go
+++ b/internal/command/deploy/deploy.go
@@ -167,6 +167,11 @@ var CommonFlags = flag.Set{
 		Shorthand:   "s",
 		Description: "Signal to stop the machine with for bluegreen strategy (default: SIGINT)",
 	},
+	flag.String{
+		Name:        "deploy-retries",
+		Description: "Number of times to retry a deployment if it fails",
+		Default:     "auto",
+	},
 }
 
 type Command struct {
@@ -316,10 +321,14 @@ func DeployWithConfig(ctx context.Context, appConfig *appconfig.Config, userID i
 
 	// Fetch an image ref or build from source to get the final image reference to deploy
 	img, err := determineImage(ctx, appConfig, usingWireguard, recreateBuilder)
-	if err != nil && usingWireguard && httpFailover {
-		span.SetAttributes(attribute.String("builder.failover_error", err.Error()))
-		span.AddEvent("using http failover")
-		img, err = determineImage(ctx, appConfig, false, recreateBuilder)
+	if err != nil {
+		noBuilder := strings.Contains(err.Error(), "Could not find App")
+		recreateBuilder = recreateBuilder || noBuilder
+		if noBuilder || (usingWireguard && httpFailover) {
+			span.SetAttributes(attribute.String("builder.failover_error", err.Error()))
+			span.AddEvent("using http failover")
+			img, err = determineImage(ctx, appConfig, false, recreateBuilder)
+		}
 	}
 
 	if err != nil {
@@ -477,6 +486,28 @@ func deployToMachines(
 
 	status.FlyctlVersion = buildinfo.Info().Version.String()
 
+	retriesFlag := flag.GetString(ctx, "deploy-retries")
+	deployRetries := 0
+
+	switch retriesFlag {
+	case "auto":
+		ldClient := launchdarkly.ClientFromContext(ctx)
+		retries := ldClient.GetFeatureFlagValue("deploy-retries", 0.0).(float64)
+		deployRetries = int(retries)
+
+	default:
+		var invalidRetriesErr error = fmt.Errorf("--deploy-retries must be set to a positive integer, 0, or 'auto'")
+		retries, err := strconv.Atoi(retriesFlag)
+		if err != nil {
+			return invalidRetriesErr
+		}
+		if retries < 0 {
+			return invalidRetriesErr
+		}
+
+		deployRetries = retries
+	}
+
 	md, err := NewMachineDeployment(ctx, MachineDeploymentArgs{
 		AppCompact:            app,
 		DeploymentImage:       img.Tag,
@@ -504,6 +535,7 @@ func deployToMachines(
 		MaxConcurrent:         maxConcurrent,
 		VolumeInitialSize:     flag.GetInt(ctx, "volume-initial-size"),
 		ProcessGroups:         processGroups,
+		DeployRetries:         deployRetries,
 	})
 	if err != nil {
 		sentry.CaptureExceptionWithAppInfo(ctx, err, "deploy", app)
diff --git a/internal/command/deploy/machines.go b/internal/command/deploy/machines.go
index 3375f10f7..d32fc929e 100644
--- a/internal/command/deploy/machines.go
+++ b/internal/command/deploy/machines.go
@@ -72,6 +72,7 @@ type MachineDeploymentArgs struct {
 	VolumeInitialSize     int
 	RestartPolicy         *fly.MachineRestartPolicy
 	RestartMaxRetries     int
+	DeployRetries         int
 }
 
 type machineDeployment struct {
@@ -111,6 +112,7 @@ type machineDeployment struct {
 	processGroups         map[string]bool
 	maxConcurrent         int
 	volumeInitialSize     int
+	deployRetries         int
 }
 
 func NewMachineDeployment(ctx context.Context, args MachineDeploymentArgs) (_ MachineDeployment, err error) {
@@ -235,6 +237,7 @@ func NewMachineDeployment(ctx context.Context, args MachineDeploymentArgs) (_ Ma
 		maxConcurrent:         maxConcurrent,
 		volumeInitialSize:     args.VolumeInitialSize,
 		processGroups:         args.ProcessGroups,
+		deployRetries:         args.DeployRetries,
 	}
 	if err := md.setStrategy(); err != nil {
 		tracing.RecordError(span, err, "failed to set strategy")
@@ -375,12 +378,12 @@ func (md *machineDeployment) setMachinesForDeployment(ctx context.Context) error
 		}
 	}
 
-	md.machineSet = machine.NewMachineSet(md.flapsClient, md.io, machines)
+	md.machineSet = machine.NewMachineSet(md.flapsClient, md.io, machines, true)
 	var releaseCmdSet []*fly.Machine
 	if releaseCmdMachine != nil {
 		releaseCmdSet = []*fly.Machine{releaseCmdMachine}
 	}
-	md.releaseCommandMachine = machine.NewMachineSet(md.flapsClient, md.io, releaseCmdSet)
+	md.releaseCommandMachine = machine.NewMachineSet(md.flapsClient, md.io, releaseCmdSet, true)
 	return nil
 }
 
diff --git a/internal/command/deploy/machines_deploymachinesapp.go b/internal/command/deploy/machines_deploymachinesapp.go
index 1d2f143df..b03afc327 100644
--- a/internal/command/deploy/machines_deploymachinesapp.go
+++ b/internal/command/deploy/machines_deploymachinesapp.go
@@ -34,8 +34,6 @@ import (
 	"golang.org/x/sync/errgroup"
 )
 
-const rollingStrategyMaxConcurrentGroups = 10
-
 type ProcessGroupsDiff struct {
 	machinesToRemove      []machine.LeasableMachine
 	groupsToRemove        map[string]int
@@ -97,17 +95,90 @@ func (md *machineDeployment) DeployMachinesApp(ctx context.Context) error {
 	return err
 }
 
-// restartMachinesApp only restarts existing machines but updates their release metadata
-func (md *machineDeployment) restartMachinesApp(ctx context.Context) error {
-	ctx, span := tracing.GetTracer().Start(ctx, "restart_machines")
+func (md *machineDeployment) updateMachine(ctx context.Context, e *machineUpdateEntry, sl statuslogger.StatusLine) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_machine", trace.WithAttributes(
+		attribute.String("id", e.launchInput.ID),
+		attribute.Bool("requires_replacement", e.launchInput.RequiresReplacement),
+	))
 	defer span.End()
 
-	if err := md.machineSet.AcquireLeases(ctx, md.leaseTimeout); err != nil {
-		tracing.RecordError(span, err, "failed to acquire lease")
+	fmtID := e.leasableMachine.FormattedMachineId()
+
+	replaceMachine := func() error {
+		sl.Logf("Replacing %s by new machine", fmtID)
+		if err := md.updateMachineByReplace(ctx, e); err != nil {
+			return err
+		}
+		sl.Logf("Created machine %s", fmtID)
+		return nil
+	}
+
+	if e.launchInput.RequiresReplacement {
+		return replaceMachine()
+	}
+
+	sl.Logf("Updating %s", fmtID)
+	if err := md.updateMachineInPlace(ctx, e); err != nil {
+		switch {
+		case len(e.leasableMachine.Machine().Config.Mounts) > 0:
+			// Replacing a machine with a volume will cause the placement logic to pick wthe same host
+			// dismissing the value of replacing it in case of lack of host capacity
+			return err
+		case strings.Contains(err.Error(), "could not reserve resource for machine"),
+			strings.Contains(err.Error(), "deploys to this host are temporarily disabled"):
+			err := replaceMachine()
+			if err != nil {
+				span.RecordError(err)
+			}
+
+			return err
+		default:
+			span.RecordError(err)
+			return err
+		}
+	}
+	return nil
+}
+
+func (md *machineDeployment) waitForMachine(ctx context.Context, e *machineUpdateEntry, sl statuslogger.StatusLine) error {
+	lm := e.leasableMachine
+	// Don't wait for SkipLaunch machines, they are updated but not started
+	if e.launchInput.SkipLaunch {
+		return nil
+	}
+
+	if !md.skipHealthChecks {
+		if err := lm.WaitForState(ctx, fly.MachineStateStarted, md.waitTimeout, false); err != nil {
+			err = suggestChangeWaitTimeout(err, "wait-timeout")
+			return err
+		}
+
+		if err := md.runTestMachines(ctx, e.leasableMachine.Machine(), sl); err != nil {
+			return err
+		}
+	}
+
+	if err := md.doSmokeChecks(ctx, lm, true); err != nil {
 		return err
 	}
-	defer md.machineSet.ReleaseLeases(ctx) // skipcq: GO-S2307
-	md.machineSet.StartBackgroundLeaseRefresh(ctx, md.leaseTimeout, md.leaseDelayBetween)
+
+	if !md.skipHealthChecks {
+		// FIXME: combine this wait with the wait for start as one update line (or two per in noninteractive case)
+		if err := lm.WaitForHealthchecksToPass(ctx, md.waitTimeout); err != nil {
+			md.warnAboutIncorrectListenAddress(ctx, lm)
+			err = suggestChangeWaitTimeout(err, "wait-timeout")
+			return err
+		}
+	}
+
+	md.warnAboutIncorrectListenAddress(ctx, lm)
+	return nil
+}
+
+// restartMachinesApp only restarts existing machines but updates their release metadata
+func (md *machineDeployment) restartMachinesApp(ctx context.Context) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "restart_machines")
+	defer span.End()
 
 	machineUpdateEntries := lo.Map(md.machineSet.GetMachines(), func(lm machine.LeasableMachine, _ int) *machineUpdateEntry {
 		return &machineUpdateEntry{leasableMachine: lm, launchInput: md.launchInputForRestart(lm.Machine())}
@@ -157,6 +228,7 @@ func (md *machineDeployment) deployCanaryMachines(ctx context.Context) (err erro
 
 		// variable name shadowing to make go-vet happy
 		name := name
+		idx := idx
 		errors.Go(func() error {
 			var err error
 			lm, err := md.spawnMachineInGroup(ctx, name, nil,
@@ -179,7 +251,7 @@ func (md *machineDeployment) deployCanaryMachines(ctx context.Context) (err erro
 				}
 			}()
 
-			if err = md.runTestMachines(ctx, lm.Machine()); err != nil {
+			if err = md.runTestMachines(ctx, lm.Machine(), sl.Line(idx)); err != nil {
 				tracing.RecordError(span, err, "failed to run test machine for canary machine")
 				firstLine, _, _ := strings.Cut(err.Error(), "\n")
 				statuslogger.LogfStatus(ctx, statuslogger.StatusFailure, "Failed to run test machine for canary machine: %s", firstLine)
@@ -314,12 +386,6 @@ func (md *machineDeployment) deployMachinesApp(ctx context.Context) error {
 		}
 	}
 
-	if err := md.machineSet.AcquireLeases(ctx, md.leaseTimeout); err != nil {
-		return err
-	}
-	defer md.machineSet.ReleaseLeases(ctx) // skipcq: GO-S2307
-	md.machineSet.StartBackgroundLeaseRefresh(ctx, md.leaseTimeout, md.leaseDelayBetween)
-
 	processGroupMachineDiff := md.resolveProcessGroupChanges()
 	md.warnAboutProcessGroupChanges(processGroupMachineDiff)
 
@@ -429,43 +495,50 @@ func suggestChangeWaitTimeout(err error, flagName string) error {
 	return err
 }
 
-func (md *machineDeployment) waitForMachine(ctx context.Context, e *machineUpdateEntry) error {
-	lm := e.leasableMachine
-	// Don't wait for SkipLaunch machines, they are updated but not started
-	if e.launchInput.SkipLaunch {
-		return nil
-	}
-
-	if !md.skipHealthChecks {
-		if err := lm.WaitForState(ctx, fly.MachineStateStarted, md.waitTimeout, false); err != nil {
-			err = suggestChangeWaitTimeout(err, "wait-timeout")
-			return err
+func (md *machineDeployment) updateExistingMachines(ctx context.Context, updateEntries []*machineUpdateEntry) (err error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_machines", trace.WithAttributes(
+		attribute.String("strategy", md.strategy),
+	))
+	defer func() {
+		if err != nil {
+			tracing.RecordError(span, err, "update failed")
 		}
+		span.End()
+	}()
 
-		if err := md.runTestMachines(ctx, e.leasableMachine.Machine()); err != nil {
-			return err
-		}
+	if md.deployRetries > 0 {
+		return md.updateExistingMachinesWRecovery(ctx, updateEntries)
 	}
 
-	if err := md.doSmokeChecks(ctx, lm); err != nil {
-		return err
+	if len(updateEntries) == 0 {
+		return nil
 	}
 
-	if !md.skipHealthChecks {
-		// FIXME: combine this wait with the wait for start as one update line (or two per in noninteractive case)
-		if err := lm.WaitForHealthchecksToPass(ctx, md.waitTimeout); err != nil {
-			md.warnAboutIncorrectListenAddress(ctx, lm)
-			err = suggestChangeWaitTimeout(err, "wait-timeout")
-			return err
-		}
+	if err := md.machineSet.AcquireLeases(ctx, md.leaseTimeout); err != nil {
+		tracing.RecordError(span, err, "failed to acquire lease")
+		return err
 	}
+	defer md.machineSet.ReleaseLeases(ctx) // skipcq: GO-S2307
+	md.machineSet.StartBackgroundLeaseRefresh(ctx, md.leaseTimeout, md.leaseDelayBetween)
 
-	md.warnAboutIncorrectListenAddress(ctx, lm)
-	return nil
+	fmt.Fprintf(md.io.Out, "Updating existing machines in '%s' with %s strategy\n", md.colorize.Bold(md.app.Name), md.strategy)
+
+	switch md.strategy {
+	case "bluegreen":
+		// TODO(billy) do machine checks here
+		return md.updateUsingBlueGreenStrategy(ctx, updateEntries)
+	case "immediate":
+		return md.updateUsingImmediateStrategy(ctx, updateEntries)
+	case "canary", "rolling":
+		fallthrough
+	default:
+		return md.updateUsingRollingStrategy(ctx, updateEntries)
+	}
 }
 
-func (md *machineDeployment) updateExistingMachines(ctx context.Context, updateEntries []*machineUpdateEntry) (err error) {
-	ctx, span := tracing.GetTracer().Start(ctx, "update_machines", trace.WithAttributes(
+// The code duplication is on purpose here. The plan is to completely move over to updateExistingMachinesWRecovery
+func (md *machineDeployment) updateExistingMachinesWRecovery(ctx context.Context, updateEntries []*machineUpdateEntry) (err error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_existing_machines", trace.WithAttributes(
 		attribute.String("strategy", md.strategy),
 	))
 	defer func() {
@@ -481,16 +554,78 @@ func (md *machineDeployment) updateExistingMachines(ctx context.Context, updateE
 
 	fmt.Fprintf(md.io.Out, "Updating existing machines in '%s' with %s strategy\n", md.colorize.Bold(md.app.Name), md.strategy)
 
+	oldAppState, err := md.appState(ctx, nil)
+	if err != nil {
+		return err
+	}
+
+	newAppState := *oldAppState
+	newAppState.Machines = lo.Map(updateEntries, func(e *machineUpdateEntry, _ int) *fly.Machine {
+		newMach := e.leasableMachine.Machine()
+		if !e.launchInput.SkipLaunch {
+			newMach.State = "started"
+		}
+
+		if e.launchInput.RequiresReplacement {
+			newMach.State = "replacing"
+		}
+		newMach.Config = e.launchInput.Config
+		return newMach
+	})
+
 	switch md.strategy {
 	case "bluegreen":
+		if err := md.machineSet.AcquireLeases(ctx, md.leaseTimeout); err != nil {
+			tracing.RecordError(span, err, "failed to acquire lease")
+			return err
+		}
+		defer md.machineSet.ReleaseLeases(ctx) // skipcq: GO-S2307
+		md.machineSet.StartBackgroundLeaseRefresh(ctx, md.leaseTimeout, md.leaseDelayBetween)
+
 		// TODO(billy) do machine checks here
 		return md.updateUsingBlueGreenStrategy(ctx, updateEntries)
 	case "immediate":
-		return md.updateUsingImmediateStrategy(ctx, updateEntries)
-	case "canary", "rolling":
+		return md.updateMachinesWRecovery(ctx, oldAppState, &newAppState, nil, updateMachineSettings{
+			pushForward:          true,
+			skipHealthChecks:     true,
+			skipSmokeChecks:      true,
+			skipLeaseAcquisition: false,
+		})
+	case "canary":
+		// create a new app state with just a single machine being updated, then the rest of the machines
+		canaryAppState := *oldAppState
+		canaryAppState.Machines = []*fly.Machine{oldAppState.Machines[0]}
+
+		newCanaryAppState := newAppState
+		canaryMach, _ := lo.Find(newAppState.Machines, func(m *fly.Machine) bool {
+			return m.ID == oldAppState.Machines[0].ID
+		})
+		newCanaryAppState.Machines = []*fly.Machine{canaryMach}
+
+		if err := md.updateMachinesWRecovery(ctx, &canaryAppState, &newCanaryAppState, nil, updateMachineSettings{
+			pushForward:          true,
+			skipHealthChecks:     md.skipHealthChecks,
+			skipSmokeChecks:      md.skipSmokeChecks,
+			skipLeaseAcquisition: false,
+		}); err != nil {
+			return err
+		}
+
+		return md.updateMachinesWRecovery(ctx, oldAppState, &newAppState, nil, updateMachineSettings{
+			pushForward:          true,
+			skipHealthChecks:     md.skipHealthChecks,
+			skipSmokeChecks:      md.skipSmokeChecks,
+			skipLeaseAcquisition: false,
+		})
+	case "rolling":
 		fallthrough
 	default:
-		return md.updateUsingRollingStrategy(ctx, updateEntries)
+		return md.updateMachinesWRecovery(ctx, oldAppState, &newAppState, nil, updateMachineSettings{
+			pushForward:          true,
+			skipHealthChecks:     md.skipHealthChecks,
+			skipSmokeChecks:      md.skipSmokeChecks,
+			skipLeaseAcquisition: false,
+		})
 	}
 }
 
@@ -561,7 +696,7 @@ func (md *machineDeployment) updateUsingImmediateStrategy(parentCtx context.Cont
 
 		updatesPool.Go(func(_ context.Context) error {
 			statusRunning()
-			if err := md.updateMachine(eCtx, e); err != nil {
+			if err := md.updateMachine(eCtx, e, sl.Line(i)); err != nil {
 				tracing.RecordError(span, err, "failed to update machine")
 				statusFailure(err)
 				return err
@@ -696,12 +831,12 @@ func (md *machineDeployment) updateEntriesGroup(parentCtx context.Context, group
 				statusRunning()
 			}
 
-			if err := md.updateMachine(ctx, e); err != nil {
+			if err := md.updateMachine(ctx, e, sl.Line(startIdx+idx)); err != nil {
 				statusFailure(err)
 				tracing.RecordError(span, err, "failed to update machine")
 				return err
 			}
-			if err := md.waitForMachine(ctx, e); err != nil {
+			if err := md.waitForMachine(ctx, e, sl.Line(startIdx+idx)); err != nil {
 				tracing.RecordError(span, err, "failed to wait for machine")
 				statusFailure(err)
 				return err
@@ -725,45 +860,6 @@ func (md *machineDeployment) updateEntriesGroup(parentCtx context.Context, group
 	return updatePool.Wait()
 }
 
-func (md *machineDeployment) updateMachine(ctx context.Context, e *machineUpdateEntry) error {
-	ctx, span := tracing.GetTracer().Start(ctx, "update_machine", trace.WithAttributes(
-		attribute.String("id", e.launchInput.ID),
-		attribute.Bool("requires_replacement", e.launchInput.RequiresReplacement),
-	))
-	defer span.End()
-
-	fmtID := e.leasableMachine.FormattedMachineId()
-
-	replaceMachine := func() error {
-		statuslogger.Logf(ctx, "Replacing %s by new machine", md.colorize.Bold(fmtID))
-		if err := md.updateMachineByReplace(ctx, e); err != nil {
-			return err
-		}
-		statuslogger.Logf(ctx, "Created machine %s", md.colorize.Bold(fmtID))
-		return nil
-	}
-
-	if e.launchInput.RequiresReplacement {
-		return replaceMachine()
-	}
-
-	statuslogger.Logf(ctx, "Updating %s", md.colorize.Bold(fmtID))
-	if err := md.updateMachineInPlace(ctx, e); err != nil {
-		switch {
-		case len(e.leasableMachine.Machine().Config.Mounts) > 0:
-			// Replacing a machine with a volume will cause the placement logic to pick wthe same host
-			// dismissing the value of replacing it in case of lack of host capacity
-			return err
-		case strings.Contains(err.Error(), "could not reserve resource for machine"),
-			strings.Contains(err.Error(), "deploys to this host are temporarily disabled"):
-			return replaceMachine()
-		default:
-			return err
-		}
-	}
-	return nil
-}
-
 func (md *machineDeployment) updateMachineByReplace(ctx context.Context, e *machineUpdateEntry) error {
 	ctx, span := tracing.GetTracer().Start(ctx, "update_by_replace", trace.WithAttributes(attribute.String("id", e.launchInput.ID)))
 	defer span.End()
@@ -784,7 +880,7 @@ func (md *machineDeployment) updateMachineByReplace(ctx context.Context, e *mach
 		return err
 	}
 
-	lm = machine.NewLeasableMachine(md.flapsClient, md.io, newMachineRaw)
+	lm = machine.NewLeasableMachine(md.flapsClient, md.io, newMachineRaw, false)
 	defer lm.ReleaseLease(ctx)
 	e.leasableMachine = lm
 	return nil
@@ -861,7 +957,7 @@ func (md *machineDeployment) spawnMachineInGroup(ctx context.Context, groupName
 		return nil, fmt.Errorf("error creating a new machine: %w%s", err, relCmdWarning)
 	}
 
-	lm := machine.NewLeasableMachine(md.flapsClient, md.io, newMachineRaw)
+	lm := machine.NewLeasableMachine(md.flapsClient, md.io, newMachineRaw, false)
 	statuslogger.Logf(ctx, "Machine %s was created", md.colorize.Bold(lm.FormattedMachineId()))
 	defer lm.ReleaseLease(ctx)
 
@@ -876,7 +972,7 @@ func (md *machineDeployment) spawnMachineInGroup(ctx context.Context, groupName
 	}
 
 	// Otherwise wait for the machine to start
-	if err := md.doSmokeChecks(ctx, lm); err != nil {
+	if err := md.doSmokeChecks(ctx, lm, true); err != nil {
 		return nil, err
 	}
 
@@ -1063,36 +1159,76 @@ func (md *machineDeployment) warnAboutIncorrectListenAddress(ctx context.Context
 	fmt.Fprintf(md.io.ErrOut, "\n")
 }
 
-func (md *machineDeployment) doSmokeChecks(ctx context.Context, lm machine.LeasableMachine) (err error) {
+type smokeChecksError struct {
+	logs      string
+	machineID string
+	err       error
+}
+
+func (s smokeChecksError) Error() string {
+	return s.err.Error()
+}
+
+func (s smokeChecksError) Unwrap() error {
+	return s.err
+}
+
+func (s smokeChecksError) Suggestion() string {
+	var suggestion string
+	suggestion += fmt.Sprintf("Smoke checks for %s failed: %v\n", s.machineID, s.err)
+	suggestion += fmt.Sprintf("Check its logs: here's the last lines below, or run 'fly logs -i %s':\n", s.machineID)
+	suggestion += s.logs
+
+	return suggestion
+}
+
+func (md *machineDeployment) doSmokeChecks(ctx context.Context, lm machine.LeasableMachine, showLogs bool) (err error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "smoke_checks", trace.WithAttributes(attribute.String("machine.ID", lm.Machine().ID)))
+	defer span.End()
 	if md.skipSmokeChecks {
+		span.AddEvent("skipped")
 		return nil
 	}
 
-	if err = lm.WaitForSmokeChecksToPass(ctx); err == nil {
+	err = lm.WaitForSmokeChecksToPass(ctx)
+	if err == nil {
 		return nil
 	}
 
-	resumeLogFn := statuslogger.Pause(ctx)
-	defer resumeLogFn()
+	if showLogs {
+		resumeLogFn := statuslogger.Pause(ctx)
+		defer resumeLogFn()
+	}
 
-	fmt.Fprintf(md.io.ErrOut, "Smoke checks for %s failed: %v\n", md.colorize.Bold(lm.Machine().ID), err)
-	fmt.Fprintf(md.io.ErrOut, "Check its logs: here's the last lines below, or run 'fly logs -i %s':\n", lm.Machine().ID)
 	logs, _, logErr := md.apiClient.GetAppLogs(ctx, md.app.Name, "", md.appConfig.PrimaryRegion, lm.Machine().ID)
-	if fly.IsNotAuthenticatedError(logErr) {
+	if fly.IsNotAuthenticatedError(logErr) && showLogs {
+		span.AddEvent("not authorized to retrieve logs")
 		fmt.Fprintf(md.io.ErrOut, "Warn: not authorized to retrieve app logs (this can happen when using deploy tokens), so we can't show you what failed. Use `fly logs -i %s` or open the monitoring dashboard to see them: https://fly.io/apps/%s/monitoring?region=&instance=%s\n", lm.Machine().ID, md.appConfig.AppName, lm.Machine().ID)
 	} else {
 		if logErr != nil {
-			return fmt.Errorf("error getting logs for machine %s: %w", lm.Machine().ID, logErr)
+			err := fmt.Errorf("error getting logs for machine %s: %w", lm.Machine().ID, logErr)
+			span.RecordError(err)
+			return err
 		}
+		var log string
 		for _, l := range logs {
 			// Ideally we should use InstanceID here, but it's not available in the logs.
 			if l.Timestamp >= lm.Machine().UpdatedAt {
-				fmt.Fprintf(md.io.ErrOut, "  %s\n", l.Message)
+				log += fmt.Sprintf("%s\n", l.Message)
 			}
 		}
-	}
 
-	return fmt.Errorf("smoke checks for %s failed: %v", lm.Machine().ID, err)
+		err := &smokeChecksError{
+			err:       err,
+			machineID: lm.Machine().ID,
+			logs:      log,
+		}
+		span.RecordError(err)
+		return err
+	}
+	err = fmt.Errorf("smoke checks for %s failed: %v", lm.Machine().ID, err)
+	span.RecordError(err)
+	return err
 }
 
 func (md *machineDeployment) checkDNS(ctx context.Context) error {
diff --git a/internal/command/deploy/machines_releasecommand.go b/internal/command/deploy/machines_releasecommand.go
index bea0612ad..42dfe3d97 100644
--- a/internal/command/deploy/machines_releasecommand.go
+++ b/internal/command/deploy/machines_releasecommand.go
@@ -146,7 +146,7 @@ func (md *machineDeployment) createReleaseCommandMachine(ctx context.Context) er
 	}
 
 	statuslogger.Logf(ctx, "Created release_command machine %s", md.colorize.Bold(releaseCmdMachine.ID))
-	md.releaseCommandMachine = machine.NewMachineSet(md.flapsClient, md.io, []*fly.Machine{releaseCmdMachine})
+	md.releaseCommandMachine = machine.NewMachineSet(md.flapsClient, md.io, []*fly.Machine{releaseCmdMachine}, true)
 	return nil
 }
 
diff --git a/internal/command/deploy/plan.go b/internal/command/deploy/plan.go
new file mode 100644
index 000000000..c96ac1e0d
--- /dev/null
+++ b/internal/command/deploy/plan.go
@@ -0,0 +1,691 @@
+package deploy
+
+import (
+	"context"
+	"errors"
+	"fmt"
+	"math"
+	"strings"
+	"sync"
+	"time"
+
+	"github.com/google/go-cmp/cmp"
+	"github.com/samber/lo"
+	fly "github.com/superfly/fly-go"
+	"github.com/superfly/flyctl/internal/ctrlc"
+	mach "github.com/superfly/flyctl/internal/machine"
+	"github.com/superfly/flyctl/internal/statuslogger"
+	"github.com/superfly/flyctl/internal/tracing"
+	"github.com/superfly/flyctl/iostreams"
+	"go.opentelemetry.io/otel/attribute"
+	"go.opentelemetry.io/otel/trace"
+	"golang.org/x/sync/errgroup"
+)
+
+type AppState struct {
+	Machines []*fly.Machine
+}
+
+type machinePairing struct {
+	oldMachine *fly.Machine
+	newMachine *fly.Machine
+}
+
+func (md *machineDeployment) appState(ctx context.Context, existingAppState *AppState) (*AppState, error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "app_state")
+	defer span.End()
+
+	machines, err := md.flapsClient.List(ctx, "")
+	if err != nil {
+		span.RecordError(err)
+		return nil, err
+	}
+
+	if existingAppState != nil {
+		for _, machine := range machines {
+			if existingMachine, ok := lo.Find(existingAppState.Machines, func(m *fly.Machine) bool {
+				return m.ID == machine.ID
+			}); ok {
+				machine.LeaseNonce = existingMachine.LeaseNonce
+			}
+		}
+	}
+
+	// TODO: could this be a list of machine id -> config?
+	appState := &AppState{
+		Machines: machines,
+	}
+
+	return appState, nil
+}
+
+type healthcheckResult struct {
+	regularChecksPassed bool
+	smokeChecksPassed   bool
+	machineChecksPassed bool
+}
+
+var healthChecksPassed = sync.Map{}
+
+type updateMachineSettings struct {
+	pushForward          bool
+	skipHealthChecks     bool
+	skipSmokeChecks      bool
+	skipLeaseAcquisition bool
+}
+
+const rollingStrategyMaxConcurrentGroups = 16
+
+func (md *machineDeployment) updateMachinesWRecovery(ctx context.Context, oldAppState, newAppState *AppState, statusLogger statuslogger.StatusLogger, settings updateMachineSettings) error {
+	ctx, span := tracing.GetTracer().Start(
+		ctx, "update_machines_w_recovery",
+		trace.WithAttributes(attribute.Bool("push_forward", settings.pushForward)),
+		trace.WithAttributes(attribute.Bool("skip_health_checks", settings.skipHealthChecks)),
+		trace.WithAttributes(attribute.Bool("skip_smoke_checks", settings.skipSmokeChecks)),
+	)
+	defer span.End()
+	ctx, cancel := context.WithCancel(ctx)
+	ctx, cancel = ctrlc.HookCancelableContext(ctx, cancel)
+	defer cancel()
+
+	oldMachines := make(map[string]*fly.Machine)
+	for _, machine := range oldAppState.Machines {
+		oldMachines[machine.ID] = machine
+	}
+	newMachines := make(map[string]*fly.Machine)
+	for _, machine := range newAppState.Machines {
+		newMachines[machine.ID] = machine
+	}
+
+	machineTuples := make([]machinePairing, 0)
+	for _, oldMachine := range oldMachines {
+		// This means we want to update a machine
+		if newMachine, ok := newMachines[oldMachine.ID]; ok {
+			healthChecksPassed.LoadOrStore(oldMachine.ID, &healthcheckResult{
+				regularChecksPassed: settings.skipHealthChecks,
+				machineChecksPassed: settings.skipHealthChecks,
+				smokeChecksPassed:   settings.skipSmokeChecks,
+			})
+			machineTuples = append(machineTuples, machinePairing{oldMachine: oldMachine, newMachine: newMachine})
+		}
+	}
+
+	for _, newMachine := range newMachines {
+		if _, ok := oldMachines[newMachine.ID]; !ok {
+			// This means we should create the new machine
+			healthChecksPassed.LoadOrStore(newMachine.ID, &healthcheckResult{
+				regularChecksPassed: settings.skipHealthChecks,
+				machineChecksPassed: settings.skipHealthChecks,
+				smokeChecksPassed:   settings.skipSmokeChecks,
+			})
+			machineTuples = append(machineTuples, machinePairing{oldMachine: nil, newMachine: newMachine})
+		}
+	}
+
+	var sl statuslogger.StatusLogger
+	if statusLogger != nil {
+		sl = statusLogger
+	} else {
+		sl = statuslogger.Create(ctx, len(machineTuples), true)
+		defer sl.Destroy(false)
+	}
+
+	machPairByProcessGroup := lo.GroupBy(machineTuples, func(machPair machinePairing) string {
+		if machPair.oldMachine != nil {
+			return machPair.oldMachine.ProcessGroup()
+		} else if machPair.newMachine != nil {
+			return machPair.newMachine.ProcessGroup()
+		} else {
+			return ""
+		}
+	})
+
+	var poolSize int
+	switch mu := md.maxUnavailable; {
+	case mu >= 1:
+		poolSize = int(mu)
+	case mu > 0:
+		poolSize = int(math.Ceil(float64(len(machineTuples)) * mu))
+	default:
+		return fmt.Errorf("Invalid --max-unavailable value: %v", mu)
+	}
+
+	if !settings.skipLeaseAcquisition {
+		attempts := 0
+
+		defer func() {
+			span.SetAttributes(attribute.Int("lease_attempts", attempts))
+		}()
+
+		for {
+			err := md.acquireLeases(ctx, machineTuples, poolSize, sl)
+			if err == nil {
+				break
+			}
+			attempts += 1
+
+			var unrecoverableErr *unrecoverableError
+			if attempts > md.deployRetries || errors.As(err, &unrecoverableErr) || errors.Is(err, context.Canceled) {
+				span.RecordError(err)
+				return fmt.Errorf("failed to acquire leases: %w", err)
+			}
+		}
+
+		defer func() {
+			err := md.releaseLeases(ctx, machineTuples, sl)
+			if err != nil {
+				fmt.Fprintln(md.io.ErrOut, "Failed to release leases:", err)
+				span.RecordError(err)
+			}
+		}()
+	}
+
+	statusLines := map[string]statuslogger.StatusLine{}
+	for idx, machPair := range machineTuples {
+		if machPair.oldMachine != nil {
+			statusLines[machPair.oldMachine.ID] = sl.Line(idx)
+		} else if machPair.newMachine != nil {
+			statusLines[machPair.newMachine.ID] = sl.Line(idx)
+		}
+	}
+
+	pgroup := errgroup.Group{}
+	pgroup.SetLimit(rollingStrategyMaxConcurrentGroups)
+
+	// We want to update by process group
+	for _, machineTuples := range machPairByProcessGroup {
+		machineTuples := machineTuples
+		pgroup.Go(func() error {
+			err := md.updateProcessGroup(ctx, machineTuples, statusLines, poolSize)
+			if err != nil && strings.Contains(err.Error(), "lease currently held by") {
+				return &unrecoverableError{err: err}
+			}
+			return err
+		})
+	}
+
+	attempts := 0
+	if updateErr := pgroup.Wait(); updateErr != nil {
+		var unrecoverableErr *unrecoverableError
+		if !settings.pushForward || errors.As(updateErr, &unrecoverableErr) || errors.Is(updateErr, context.Canceled) {
+			span.RecordError(updateErr)
+			return updateErr
+		}
+
+		// if we fail to update the machines, we should push the state forward if possible
+		for {
+			defer func() {
+				span.SetAttributes(attribute.Int("update_attempts", attempts))
+			}()
+
+			if attempts > md.deployRetries {
+				fmt.Fprintln(md.io.ErrOut, "Failed to update machines:", updateErr)
+				span.RecordError(updateErr)
+				return updateErr
+			}
+
+			currentState, err := md.appState(ctx, oldAppState)
+			if err != nil {
+				span.RecordError(updateErr)
+				return fmt.Errorf("failed to get current app state: %w", err)
+			}
+			err = md.updateMachinesWRecovery(ctx, currentState, newAppState, sl, updateMachineSettings{
+				pushForward:          false,
+				skipHealthChecks:     settings.skipHealthChecks,
+				skipSmokeChecks:      settings.skipSmokeChecks,
+				skipLeaseAcquisition: true,
+			})
+			if err == nil {
+				break
+			} else if errors.Is(err, context.Canceled) {
+				span.RecordError(updateErr)
+				return err
+			} else {
+				if errors.As(err, &unrecoverableErr) {
+					span.RecordError(updateErr)
+					return err
+				}
+				fmt.Fprintln(md.io.ErrOut, "Failed to update machines:", err, "Retrying...")
+			}
+			attempts += 1
+			time.Sleep(1 * time.Second)
+		}
+	}
+
+	return nil
+}
+
+func (md *machineDeployment) updateProcessGroup(ctx context.Context, machineTuples []machinePairing, statusLines map[string]statuslogger.StatusLine, poolSize int) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_process_group")
+	defer span.End()
+
+	group := errgroup.Group{}
+	group.SetLimit(poolSize)
+
+	for _, machPair := range machineTuples {
+		machPair := machPair
+		oldMachine := machPair.oldMachine
+		newMachine := machPair.newMachine
+
+		group.Go(func() error {
+			checkResult, _ := healthChecksPassed.Load(machPair.oldMachine.ID)
+			machineCheckResult := checkResult.(*healthcheckResult)
+
+			var sl statuslogger.StatusLine
+			if oldMachine != nil {
+				sl = statusLines[oldMachine.ID]
+			} else if newMachine != nil {
+				sl = statusLines[newMachine.ID]
+			}
+
+			err := md.updateMachineWChecks(ctx, oldMachine, newMachine, sl, md.io, machineCheckResult)
+			if err != nil {
+				sl.LogStatus(statuslogger.StatusFailure, err.Error())
+				span.RecordError(err)
+				return fmt.Errorf("failed to update machine %s: %w", oldMachine.ID, err)
+			}
+			return nil
+		})
+	}
+
+	if err := group.Wait(); err != nil {
+		span.RecordError(err)
+		return err
+	}
+
+	return nil
+}
+
+func (md *machineDeployment) acquireLeases(ctx context.Context, machineTuples []machinePairing, poolSize int, statusLogger statuslogger.StatusLogger) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "acquire_leases")
+
+	leaseGroup := errgroup.Group{}
+	leaseGroup.SetLimit(poolSize)
+
+	for idx, machineTuple := range machineTuples {
+		machineTuple := machineTuple
+		idx := idx
+
+		leaseGroup.Go(func() error {
+			sl := statusLogger.Line(idx)
+
+			var machine *fly.Machine
+			if machineTuple.oldMachine != nil {
+				machine = machineTuple.oldMachine
+			} else if machineTuple.newMachine != nil {
+				machine = machineTuple.newMachine
+			} else {
+				return nil
+			}
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Acquiring lease for %s", machine.ID))
+
+			if machine.LeaseNonce == "" {
+				sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Waiting for job %s", machine.ID))
+			}
+
+			lease, err := md.acquireMachineLease(ctx, machine.ID)
+			if err != nil {
+				sl.LogStatus(statuslogger.StatusFailure, fmt.Sprintf("Failed to acquire lease for %s: %v", machine.ID, err))
+				return err
+			}
+
+			machine.LeaseNonce = lease.Data.Nonce
+			lm := mach.NewLeasableMachine(md.flapsClient, md.io, machine, false)
+			lm.StartBackgroundLeaseRefresh(ctx, md.leaseTimeout, md.leaseDelayBetween)
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Waiting for job %s", machine.ID))
+			return nil
+		})
+	}
+
+	if err := leaseGroup.Wait(); err != nil {
+		span.RecordError(err)
+		return err
+	}
+
+	return nil
+}
+
+func (md *machineDeployment) releaseLeases(ctx context.Context, machineTuples []machinePairing, statusLogger statuslogger.StatusLogger) error {
+	ctx = context.WithoutCancel(ctx)
+	ctx, span := tracing.GetTracer().Start(ctx, "release_leases")
+	defer span.End()
+
+	leaseGroup := errgroup.Group{}
+	leaseGroup.SetLimit(len(machineTuples))
+
+	for idx, machineTuple := range machineTuples {
+		machineTuple := machineTuple
+		idx := idx
+
+		leaseGroup.Go(func() error {
+			sl := statusLogger.Line(idx)
+
+			var machine *fly.Machine
+			if machineTuple.oldMachine != nil {
+				machine = machineTuple.oldMachine
+			} else if machineTuple.newMachine != nil {
+				machine = machineTuple.newMachine
+			} else {
+				return nil
+			}
+
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Clearing lease for %s", machine.ID))
+			if machine.LeaseNonce == "" {
+				sl.LogStatus(statuslogger.StatusSuccess, fmt.Sprintf("Cleared lease for %s", machine.ID))
+				return nil
+			}
+			err := md.clearMachineLease(ctx, machine.ID, machine.LeaseNonce)
+			if err != nil {
+				sl.LogStatus(statuslogger.StatusFailure, fmt.Sprintf("Failed to clear lease for %s: %v", machine.ID, err))
+				return err
+			}
+
+			sl.LogStatus(statuslogger.StatusSuccess, fmt.Sprintf("Cleared lease for %s", machine.ID))
+			return nil
+		})
+	}
+
+	if err := leaseGroup.Wait(); err != nil {
+		span.RecordError(err)
+		return nil
+	}
+
+	return nil
+}
+
+type unrecoverableError struct {
+	err error
+}
+
+func (e *unrecoverableError) Error() string {
+	return fmt.Sprintf("Unrecoverable error: %s", e.err)
+}
+
+func (e *unrecoverableError) Unwrap() error {
+	return e.err
+}
+
+func compareConfigs(ctx context.Context, oldConfig, newConfig *fly.MachineConfig) bool {
+	_, span := tracing.GetTracer().Start(ctx, "compare_configs")
+	defer span.End()
+
+	opt := cmp.FilterPath(func(p cmp.Path) bool {
+		vx := p.Last().String()
+
+		// ignore the flyctl version used for the deployment. this is mostly useful for testing
+		if vx == `["fly_flyctl_version"]` {
+			return true
+		}
+		return false
+	}, cmp.Ignore())
+
+	isEqual := cmp.Equal(oldConfig, newConfig, opt)
+	span.SetAttributes(attribute.Bool("configs_equal", isEqual))
+	return isEqual
+}
+
+func (md *machineDeployment) updateMachineWChecks(ctx context.Context, oldMachine, newMachine *fly.Machine, sl statuslogger.StatusLine, io *iostreams.IOStreams, healthcheckResult *healthcheckResult) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_machine_w_checks", trace.WithAttributes(
+		attribute.Bool("smoke_checks", healthcheckResult.smokeChecksPassed),
+		attribute.Bool("machine_checks", healthcheckResult.machineChecksPassed),
+		attribute.Bool("regular_checks", healthcheckResult.regularChecksPassed),
+	))
+	defer span.End()
+
+	var machine *fly.Machine
+	var lease *fly.MachineLease
+
+	var err error
+
+	machine, lease, err = md.updateOrCreateMachine(ctx, oldMachine, newMachine, sl)
+	// if machine is nil and the lease is nil, it means we don't need to check on this machine
+	if err != nil || (machine == nil && lease == nil) {
+		span.RecordError(err)
+		return err
+	}
+
+	lm := mach.NewLeasableMachine(md.flapsClient, io, machine, false)
+
+	shouldStart := lo.Contains([]string{"started", "replacing"}, newMachine.State)
+	span.SetAttributes(attribute.Bool("should_start", shouldStart))
+
+	if !shouldStart {
+		sl.LogStatus(statuslogger.StatusSuccess, fmt.Sprintf("Machine %s is now in a good state", machine.ID))
+		return nil
+	}
+
+	if !healthcheckResult.machineChecksPassed || !healthcheckResult.smokeChecksPassed {
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Waiting for machine %s to reach a good state", oldMachine.ID))
+		_, err := waitForMachineState(ctx, lm, []string{"stopped", "started", "suspended"}, md.waitTimeout, sl)
+		if err != nil {
+			span.RecordError(err)
+			return err
+		}
+	}
+
+	md.warnAboutIncorrectListenAddress(ctx, lm)
+
+	if !healthcheckResult.smokeChecksPassed {
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Running smoke checks on machine %s", machine.ID))
+		err = md.doSmokeChecks(ctx, lm, false)
+		if err != nil {
+			span.RecordError(err)
+			return &unrecoverableError{err: err}
+		}
+		healthcheckResult.smokeChecksPassed = true
+	}
+
+	if !healthcheckResult.machineChecksPassed {
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Running machine checks on machine %s", machine.ID))
+		err = md.runTestMachines(ctx, machine, sl)
+		if err != nil {
+			span.RecordError(err)
+			return &unrecoverableError{err: err}
+		}
+		healthcheckResult.machineChecksPassed = true
+	}
+
+	if !healthcheckResult.regularChecksPassed {
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Checking health of machine %s", machine.ID))
+		err = lm.WaitForHealthchecksToPass(ctx, md.waitTimeout)
+		if err != nil {
+			span.RecordError(err)
+			return &unrecoverableError{err: err}
+		}
+		healthcheckResult.regularChecksPassed = true
+	}
+
+	sl.LogStatus(statuslogger.StatusSuccess, fmt.Sprintf("Machine %s is now in a good state", machine.ID))
+
+	return nil
+}
+
+func (md *machineDeployment) updateOrCreateMachine(ctx context.Context, oldMachine, newMachine *fly.Machine, sl statuslogger.StatusLine) (*fly.Machine, *fly.MachineLease, error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_or_create_machine")
+	defer span.End()
+
+	if oldMachine != nil {
+		span.AddEvent("Old machine exists")
+		if newMachine == nil {
+			span.AddEvent("Destroying old machine")
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Destroying machine %s", oldMachine.ID))
+
+			err := md.destroyMachine(ctx, oldMachine.ID, oldMachine.LeaseNonce)
+			span.RecordError(err)
+
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Destroyed machine %s", oldMachine.ID))
+			return nil, nil, err
+		} else {
+			span.AddEvent("Updating old machine")
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Updating machine config for %s", oldMachine.ID))
+			machine, err := md.updateMachineConfig(ctx, oldMachine, newMachine.Config, sl, newMachine.State == "replacing")
+			if err != nil {
+				return oldMachine, nil, err
+			}
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Updated machine config for %s", oldMachine.ID))
+
+			return machine, nil, nil
+		}
+	} else if newMachine != nil {
+		span.AddEvent("Creating a new machine")
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Creating machine for %s", newMachine.ID))
+		machine, err := md.createMachine(ctx, newMachine.Config, newMachine.Region)
+		if err != nil {
+			return nil, nil, err
+		}
+
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Acquiring lease for %s", newMachine.ID))
+		lease, err := md.acquireMachineLease(ctx, machine.ID)
+		if err != nil {
+			return nil, nil, err
+		}
+		sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Acquired lease for %s", newMachine.ID))
+
+		return machine, lease, nil
+	} else {
+		// both old and new machines are nil, so just a noop
+		return nil, nil, nil
+	}
+}
+
+func (md *machineDeployment) destroyMachine(ctx context.Context, machineID string, lease string) error {
+	err := md.flapsClient.Destroy(ctx, fly.RemoveMachineInput{
+		ID:   machineID,
+		Kill: true,
+	}, lease)
+	if err != nil {
+		return err
+	}
+
+	return nil
+}
+
+func (md *machineDeployment) clearMachineLease(ctx context.Context, machID, leaseNonce string) error {
+	// TODO: remove this when the flaps retry work is done
+	attempts := 0
+	for {
+		err := md.flapsClient.ReleaseLease(ctx, machID, leaseNonce)
+		if err == nil {
+			return nil
+		}
+		attempts += 1
+		if attempts > 5 {
+			return err
+		}
+		time.Sleep(1 * time.Second)
+	}
+}
+
+// returns when the machine is in one of the possible states, or after passing the timeout threshold
+func waitForMachineState(ctx context.Context, lm mach.LeasableMachine, possibleStates []string, timeout time.Duration, sl statuslogger.StatusLine) (string, error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "wait_for_machine_state", trace.WithAttributes(
+		attribute.StringSlice("possible_states", possibleStates),
+	))
+	defer span.End()
+
+	ctx, cancel := context.WithTimeout(ctx, timeout)
+	defer cancel()
+
+	var mutex sync.Mutex
+
+	var waitErr error
+	numCompleted := 0
+	var successfulState string
+
+	for _, state := range possibleStates {
+		state := state
+		go func() {
+			err := lm.WaitForState(ctx, state, timeout, false)
+			mutex.Lock()
+			defer func() {
+				numCompleted += 1
+				mutex.Unlock()
+			}()
+
+			if successfulState != "" {
+				return
+			}
+			sl.LogStatus(statuslogger.StatusRunning, fmt.Sprintf("Machine %s reached %s state", lm.Machine().ID, state))
+
+			if err != nil {
+				waitErr = err
+			} else {
+				successfulState = state
+			}
+		}()
+	}
+
+	// TODO(billy): i'm sure we can use channels here
+	for {
+		mutex.Lock()
+		if successfulState != "" || numCompleted == len(possibleStates) {
+			defer mutex.Unlock()
+			if successfulState != "" {
+				span.SetAttributes(attribute.String("state", successfulState))
+			}
+
+			if waitErr != nil {
+				span.RecordError(waitErr)
+			}
+
+			return successfulState, waitErr
+		}
+		mutex.Unlock()
+
+		time.Sleep(1 * time.Second)
+	}
+}
+
+func (md *machineDeployment) acquireMachineLease(ctx context.Context, machID string) (*fly.MachineLease, error) {
+	leaseTimeout := int(md.leaseTimeout)
+	lease, err := md.flapsClient.AcquireLease(ctx, machID, &leaseTimeout)
+	if err != nil {
+		// TODO: tell users how to manually clear the lease
+		// TODO: have a flag to automatically clear the lease
+		if strings.Contains(err.Error(), "failed to get lease") {
+			return nil, &unrecoverableError{err: err}
+		} else {
+			return nil, err
+		}
+	}
+
+	return lease, nil
+}
+
+func (md *machineDeployment) updateMachineConfig(ctx context.Context, oldMachine *fly.Machine, newMachineConfig *fly.MachineConfig, sl statuslogger.StatusLine, shouldReplace bool) (*fly.Machine, error) {
+	ctx, span := tracing.GetTracer().Start(ctx, "update_machine_config")
+	defer span.End()
+	if compareConfigs(ctx, oldMachine.Config, newMachineConfig) {
+		return oldMachine, nil
+	}
+
+	input, err := md.launchInputForUpdate(oldMachine)
+	if err != nil {
+		return nil, err
+	}
+	input.Config = newMachineConfig
+	input.RequiresReplacement = input.RequiresReplacement || shouldReplace
+
+	lm := mach.NewLeasableMachine(md.flapsClient, md.io, oldMachine, false)
+	entry := &machineUpdateEntry{
+		leasableMachine: lm,
+		launchInput:     input,
+	}
+	err = md.updateMachine(ctx, entry, sl)
+	if err != nil {
+		return nil, err
+	}
+	return entry.leasableMachine.Machine(), nil
+}
+
+func (md *machineDeployment) createMachine(ctx context.Context, machConfig *fly.MachineConfig, region string) (*fly.Machine, error) {
+	machine, err := md.flapsClient.Launch(ctx, fly.LaunchMachineInput{
+		Config: machConfig,
+		Region: region,
+	})
+	if err != nil {
+		return nil, err
+	}
+
+	return machine, nil
+}
diff --git a/internal/command/deploy/strategy_bluegreen.go b/internal/command/deploy/strategy_bluegreen.go
index 94b08f1c7..f376d3bdf 100644
--- a/internal/command/deploy/strategy_bluegreen.go
+++ b/internal/command/deploy/strategy_bluegreen.go
@@ -159,7 +159,7 @@ func (bg *blueGreen) CreateGreenMachines(ctx context.Context) error {
 				return err
 			}
 
-			greenMachine := machine.NewLeasableMachine(bg.flaps, bg.io, newMachineRaw)
+			greenMachine := machine.NewLeasableMachine(bg.flaps, bg.io, newMachineRaw, true)
 			defer greenMachine.ReleaseLease(ctx)
 
 			lock.Lock()
diff --git a/internal/launchdarkly/launchdarkly.go b/internal/launchdarkly/launchdarkly.go
index 104df972e..df7afa2bd 100644
--- a/internal/launchdarkly/launchdarkly.go
+++ b/internal/launchdarkly/launchdarkly.go
@@ -13,6 +13,7 @@ import (
 	"github.com/launchdarkly/go-sdk-common/v3/ldcontext"
 	"github.com/superfly/flyctl/internal/logger"
 	"github.com/superfly/flyctl/internal/tracing"
+	"go.opentelemetry.io/otel/attribute"
 )
 
 const clientSideID string = "6557a71bbffb5f134b84b15c"
@@ -84,12 +85,18 @@ func (ldClient *Client) monitor(ctx context.Context) {
 }
 
 func (ldClient *Client) GetFeatureFlagValue(key string, defaultValue any) any {
+	_, span := tracing.GetTracer().Start(context.Background(), "get_feature_flag_value")
+	defer span.End()
+
+	span.SetAttributes(attribute.String("flag", key))
+
 	ldClient.flagsMutex.Lock()
 	defer ldClient.flagsMutex.Unlock()
 
 	if flag, ok := ldClient.flags[key]; ok {
 		return flag.Value
 	}
+	span.SetAttributes(attribute.Bool("default_flag", true))
 	return defaultValue
 
 }
diff --git a/internal/machine/leasable_machine.go b/internal/machine/leasable_machine.go
index 4a1a5582c..86909a7f1 100644
--- a/internal/machine/leasable_machine.go
+++ b/internal/machine/leasable_machine.go
@@ -13,8 +13,11 @@ import (
 	"github.com/superfly/flyctl/internal/ctrlc"
 	"github.com/superfly/flyctl/internal/flapsutil"
 	"github.com/superfly/flyctl/internal/statuslogger"
+	"github.com/superfly/flyctl/internal/tracing"
 	"github.com/superfly/flyctl/iostreams"
 	"github.com/superfly/flyctl/terminal"
+	"go.opentelemetry.io/otel/attribute"
+	"go.opentelemetry.io/otel/trace"
 	"golang.org/x/exp/maps"
 )
 
@@ -49,15 +52,18 @@ type leasableMachine struct {
 	leaseNonce             string
 	leaseRefreshCancelFunc context.CancelFunc
 	destroyed              bool
+	showLogs               bool
 }
 
-func NewLeasableMachine(flapsClient flapsutil.FlapsClient, io *iostreams.IOStreams, machine *fly.Machine) LeasableMachine {
+// TODO: make sure the other functions handle showLogs correctly
+func NewLeasableMachine(flapsClient flapsutil.FlapsClient, io *iostreams.IOStreams, machine *fly.Machine, showLogs bool) LeasableMachine {
 	return &leasableMachine{
 		flapsClient: flapsClient,
 		io:          io,
 		colorize:    io.ColorScheme(),
 		machine:     machine,
 		leaseNonce:  machine.LeaseNonce,
+		showLogs:    showLogs,
 	}
 }
 
@@ -156,7 +162,9 @@ func (lm *leasableMachine) Start(ctx context.Context) error {
 	if lm.HasLease() {
 		return fmt.Errorf("error cannot start machine %s because it has a lease", lm.machine.ID)
 	}
-	lm.logStatusWaiting(ctx, fly.MachineStateStarted)
+	if lm.showLogs {
+		lm.logStatusWaiting(ctx, fly.MachineStateStarted)
+	}
 	_, err := lm.flapsClient.Start(ctx, lm.machine.ID, "")
 	if err != nil {
 		return err
@@ -194,7 +202,9 @@ func (lm *leasableMachine) WaitForState(ctx context.Context, desiredState string
 		Factor: 2,
 		Jitter: true,
 	}
-	lm.logStatusWaiting(ctx, desiredState)
+	if lm.showLogs {
+		lm.logStatusWaiting(ctx, desiredState)
+	}
 	for {
 		err := lm.flapsClient.Wait(waitCtx, lm.Machine(), desiredState, timeout)
 		notFoundResponse := false
@@ -222,7 +232,9 @@ func (lm *leasableMachine) WaitForState(ctx context.Context, desiredState string
 			}
 			continue
 		}
-		lm.logStatusFinished(ctx, desiredState)
+		if lm.showLogs {
+			lm.logStatusFinished(ctx, desiredState)
+		}
 		return nil
 	}
 }
@@ -248,6 +260,9 @@ func (lm *leasableMachine) isConstantlyRestarting(machine *fly.Machine) bool {
 }
 
 func (lm *leasableMachine) WaitForSmokeChecksToPass(ctx context.Context) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "wait_for_smoke_checks")
+	defer span.End()
+
 	waitCtx, cancel := ctrlc.HookCancelableContext(context.WithTimeout(ctx, 10*time.Second))
 	defer cancel()
 
@@ -258,7 +273,9 @@ func (lm *leasableMachine) WaitForSmokeChecksToPass(ctx context.Context) error {
 		Jitter: true,
 	}
 
-	statuslogger.Logf(ctx, "Checking that %s is up and running", lm.colorize.Bold(lm.FormattedMachineId()))
+	if lm.showLogs {
+		statuslogger.Logf(ctx, "Checking that %s is up and running", lm.colorize.Bold(lm.FormattedMachineId()))
+	}
 
 	for {
 		machine, err := lm.flapsClient.Get(waitCtx, lm.Machine().ID)
@@ -275,12 +292,15 @@ func (lm *leasableMachine) WaitForSmokeChecksToPass(ctx context.Context) error {
 		case errors.Is(waitCtx.Err(), context.DeadlineExceeded):
 			return nil
 		case err != nil:
+			span.RecordError(err)
 			return fmt.Errorf("error getting machine %s from api: %w", lm.Machine().ID, err)
 		}
 
 		switch {
 		case lm.isConstantlyRestarting(machine):
-			return fmt.Errorf("the app appears to be crashing")
+			err := fmt.Errorf("the app appears to be crashing")
+			span.RecordError(err)
+			return err
 		default:
 			select {
 			case <-time.After(b.Duration()):
@@ -291,6 +311,8 @@ func (lm *leasableMachine) WaitForSmokeChecksToPass(ctx context.Context) error {
 }
 
 func (lm *leasableMachine) WaitForHealthchecksToPass(ctx context.Context, timeout time.Duration) error {
+	ctx, span := tracing.GetTracer().Start(ctx, "wait_for_healthchecks", trace.WithAttributes(attribute.Int("num_checks", len(lm.Machine().Checks)), attribute.Int64("timeout_ms", timeout.Milliseconds())))
+	defer span.End()
 	if len(lm.Machine().Checks) == 0 {
 		return nil
 	}
@@ -318,13 +340,16 @@ func (lm *leasableMachine) WaitForHealthchecksToPass(ctx context.Context, timeou
 		updateMachine, err := lm.flapsClient.Get(waitCtx, lm.Machine().ID)
 		switch {
 		case errors.Is(waitCtx.Err(), context.Canceled):
+			span.RecordError(err)
 			return err
 		case errors.Is(waitCtx.Err(), context.DeadlineExceeded):
+			span.RecordError(err)
 			return fmt.Errorf("timeout reached waiting for health checks to pass for machine %s: %w", lm.Machine().ID, err)
 		case err != nil:
+			span.RecordError(err)
 			return fmt.Errorf("error getting machine %s from api: %w", lm.Machine().ID, err)
 		case !updateMachine.AllHealthChecks().AllPassing():
-			if !printedFirst || lm.io.IsInteractive() {
+			if lm.showLogs && (!printedFirst || lm.io.IsInteractive()) {
 				lm.logHealthCheckStatus(ctx, updateMachine.AllHealthChecks())
 				printedFirst = true
 			}
@@ -334,7 +359,9 @@ func (lm *leasableMachine) WaitForHealthchecksToPass(ctx context.Context, timeou
 			}
 			continue
 		}
-		lm.logHealthCheckStatus(ctx, updateMachine.AllHealthChecks())
+		if lm.showLogs {
+			lm.logHealthCheckStatus(ctx, updateMachine.AllHealthChecks())
+		}
 		return nil
 	}
 }
@@ -349,7 +376,9 @@ func (lm *leasableMachine) WaitForEventType(ctx context.Context, eventType strin
 		Factor: 2,
 		Jitter: true,
 	}
-	statuslogger.Logf(ctx, "Waiting for %s to get %s event", lm.colorize.Bold(lm.FormattedMachineId()), lm.colorize.Yellow(eventType))
+	if lm.showLogs {
+		statuslogger.Logf(ctx, "Waiting for %s to get %s event", lm.colorize.Bold(lm.FormattedMachineId()), lm.colorize.Yellow(eventType))
+	}
 	for {
 		updateMachine, err := lm.flapsClient.Get(waitCtx, lm.Machine().ID)
 		switch {
diff --git a/internal/machine/machine_set.go b/internal/machine/machine_set.go
index 4bd653fa2..ae905e3cf 100644
--- a/internal/machine/machine_set.go
+++ b/internal/machine/machine_set.go
@@ -31,10 +31,10 @@ type machineSet struct {
 	machines []LeasableMachine
 }
 
-func NewMachineSet(flapsClient flapsutil.FlapsClient, io *iostreams.IOStreams, machines []*fly.Machine) *machineSet {
+func NewMachineSet(flapsClient flapsutil.FlapsClient, io *iostreams.IOStreams, machines []*fly.Machine, showLogs bool) *machineSet {
 	leaseMachines := make([]LeasableMachine, 0)
 	for _, m := range machines {
-		leaseMachines = append(leaseMachines, NewLeasableMachine(flapsClient, io, m))
+		leaseMachines = append(leaseMachines, NewLeasableMachine(flapsClient, io, m, showLogs))
 	}
 	return &machineSet{
 		machines: leaseMachines,


Test patch:
diff --git a/internal/command/deploy/machinebasedtest.go b/internal/command/deploy/machinebasedtest.go
index caa4af56e..533c176fd 100644
--- a/internal/command/deploy/machinebasedtest.go
+++ b/internal/command/deploy/machinebasedtest.go
@@ -3,7 +3,6 @@ package deploy
 import (
 	"context"
 	"fmt"
-	"strconv"
 	"time"
 
 	"github.com/cenkalti/backoff"
@@ -21,7 +20,26 @@ type createdTestMachine struct {
 	err  error
 }
 
-func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest *fly.Machine) (err error) {
+type machineTestErr struct {
+	testMachineLogs string
+	exitCode        int
+	machineID       string
+}
+
+func (e machineTestErr) Error() string {
+	return fmt.Sprintf("Error test command machine %s exited with non-zero status of %d", e.machineID, e.exitCode)
+}
+
+func (e machineTestErr) Description() string {
+	var desc string
+	desc += fmt.Sprintf("Error: test command failed running on machine %s with exit code %d.\n", e.machineID, e.exitCode)
+	desc += fmt.Sprintf("Check its logs: here's the last 100 lines below, or run 'fly logs -i %s':\n\n", e.machineID)
+	desc += e.testMachineLogs
+	return desc
+
+}
+
+func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest *fly.Machine, sl statuslogger.StatusLine) (err error) {
 	ctx, span := tracing.GetTracer().Start(ctx, "run_test_machine")
 	var (
 		flaps = md.flapsClient
@@ -34,9 +52,13 @@ func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest
 		span.End()
 	}()
 
+	if sl == nil {
+		return fmt.Errorf("bug: status logger is nil")
+	}
+
 	processGroup := machineToTest.ProcessGroup()
 	machineChecks := lo.FlatMap(md.appConfig.AllServices(), func(svc appconfig.Service, _ int) []*appconfig.ServiceMachineCheck {
-		matchesProcessGroup := lo.Contains(svc.Processes, processGroup)
+		matchesProcessGroup := lo.Contains(svc.Processes, processGroup) || len(svc.Processes) == 0
 		if matchesProcessGroup {
 			return svc.MachineChecks
 		} else {
@@ -55,11 +77,11 @@ func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest
 		var err error
 		defer func() {
 			if err != nil {
-				statuslogger.Failed(ctx, err)
+				sl.Failed(err)
 			}
 		}()
 
-		mach, err = md.createTestMachine(ctx, machineCheck, machineToTest)
+		mach, err = md.createTestMachine(ctx, machineCheck, machineToTest, sl)
 		return createdTestMachine{mach, err}
 	})
 
@@ -74,13 +96,13 @@ func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest
 	machineSet := machine.NewMachineSet(flaps, io, lo.FilterMap(machines, func(m createdTestMachine, _ int) (*fly.Machine, bool) {
 		if m.err != nil {
 			tracing.RecordError(span, m.err, "failed to create test machine")
-			statuslogger.LogStatus(ctx, statuslogger.StatusFailure, fmt.Sprintf("failed to create test machine: %s", m.err))
+			sl.LogStatus(statuslogger.StatusFailure, fmt.Sprintf("failed to create test machine: %s", m.err))
 		}
 		return m.mach, m.err == nil
-	}))
+	}), false)
 
 	// FIXME: consolidate this wait stuff with deploy waits? Especially once we improve the output
-	err = md.waitForTestMachinesToFinish(ctx, machineSet)
+	err = md.waitForTestMachinesToFinish(ctx, machineSet, sl)
 	if err != nil {
 		tracing.RecordError(span, err, "failed to wait for test cmd machine")
 		return err
@@ -89,7 +111,7 @@ func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest
 	for _, testMachine := range machineSet.GetMachines() {
 		md.waitForLogs(ctx, testMachine.Machine(), 10*time.Second)
 
-		statuslogger.Logf(ctx, "Checking test command machine %s", md.colorize.Bold(testMachine.Machine().ID))
+		sl.Logf("Checking test command machine %s", md.colorize.Bold(testMachine.Machine().ID))
 		lastExitEvent, err := testMachine.WaitForEventType(ctx, "exit", md.releaseCmdTimeout, true)
 		if err != nil {
 			return fmt.Errorf("error finding the test command machine %s exit event: %w", testMachine.Machine().ID, err)
@@ -100,27 +122,22 @@ func (md *machineDeployment) runTestMachines(ctx context.Context, machineToTest
 		}
 
 		if exitCode != 0 {
-			statuslogger.LogStatus(ctx, statuslogger.StatusFailure, "test command failed")
+			sl.LogStatus(statuslogger.StatusFailure, "test command failed")
 			// Preemptive cleanup of the logger so that the logs have a clean place to write to
 
-			fmt.Fprintf(md.io.ErrOut, "Error: test command failed running on machine %s with exit code %s.\n",
-				md.colorize.Bold(testMachine.Machine().ID), md.colorize.Red(strconv.Itoa(exitCode)))
-			fmt.Fprintf(md.io.ErrOut, "Check its logs: here's the last 100 lines below, or run 'fly logs -i %s':\n",
-				testMachine.Machine().ID)
 			testLogs, _, err := md.apiClient.GetAppLogs(ctx, md.app.Name, "", md.appConfig.PrimaryRegion, testMachine.Machine().ID)
-			if fly.IsNotAuthenticatedError(err) {
-				fmt.Fprintf(md.io.ErrOut, "Warn: not authorized to retrieve app logs (this can happen when using deploy tokens), so we can't show you what failed. Use `fly logs -i %s` or open the monitoring dashboard to see them: https://fly.io/apps/%s/monitoring?region=&instance=%s\n", testMachine.Machine().ID, md.appConfig.AppName, testMachine.Machine().ID)
-			} else {
-				if err != nil {
-					return fmt.Errorf("Error getting test command logs: %w", err)
-				}
+			if err == nil {
+				var logs string
 				for _, l := range testLogs {
-					fmt.Fprintf(md.io.ErrOut, "  %s\n", l.Message)
+					logs += l.Message + "\n"
 				}
+
+				return machineTestErr{machineID: testMachine.Machine().ID, exitCode: exitCode, testMachineLogs: logs}
 			}
+
 			return fmt.Errorf("Error test command machine %s exited with non-zero status of %d", testMachine.Machine().ID, exitCode)
 		}
-		statuslogger.LogfStatus(ctx,
+		sl.LogfStatus(
 			statuslogger.StatusSuccess,
 			"Test machine %s completed successfully",
 			md.colorize.Bold(testMachine.Machine().ID),
@@ -151,7 +168,7 @@ func (md *machineDeployment) waitForLogs(ctx context.Context, mach *fly.Machine,
 	}, backoff.WithContext(b, ctx))
 }
 
-func (md *machineDeployment) createTestMachine(ctx context.Context, svc *appconfig.ServiceMachineCheck, machineToTest *fly.Machine) (*fly.Machine, error) {
+func (md *machineDeployment) createTestMachine(ctx context.Context, svc *appconfig.ServiceMachineCheck, machineToTest *fly.Machine, sl statuslogger.StatusLine) (*fly.Machine, error) {
 	ctx, span := tracing.GetTracer().Start(ctx, "create_test_machine")
 	defer span.End()
 
@@ -165,7 +182,7 @@ func (md *machineDeployment) createTestMachine(ctx context.Context, svc *appconf
 		return nil, fmt.Errorf("error creating a test machine: %w", err)
 	}
 
-	statuslogger.Logf(ctx, "Created test machine %s", md.colorize.Bold(testMachine.ID))
+	sl.Logf("Created test machine %s", md.colorize.Bold(testMachine.ID))
 	return testMachine, nil
 }
 
@@ -195,7 +212,7 @@ func (md *machineDeployment) launchInputForTestMachine(svc *appconfig.ServiceMac
 	}, nil
 }
 
-func (md *machineDeployment) waitForTestMachinesToFinish(ctx context.Context, testMachines machine.MachineSet) error {
+func (md *machineDeployment) waitForTestMachinesToFinish(ctx context.Context, testMachines machine.MachineSet, sl statuslogger.StatusLine) error {
 	io := iostreams.FromContext(ctx)
 	colorize := io.ColorScheme()
 
@@ -224,7 +241,7 @@ func (md *machineDeployment) waitForTestMachinesToFinish(ctx context.Context, te
 		return m, err == nil
 	})
 	for _, mach := range machs {
-		statuslogger.Logf(ctx, "Test Machine %s: %s", colorize.Bold(mach.ID), mach.State)
+		sl.Logf("Test Machine %s: %s", colorize.Bold(mach.ID), mach.State)
 	}
 
 	return nil
diff --git a/internal/command/deploy/machines_test.go b/internal/command/deploy/machines_test.go
index 4c17523c9..c98e9bf84 100644
--- a/internal/command/deploy/machines_test.go
+++ b/internal/command/deploy/machines_test.go
@@ -21,7 +21,7 @@ func stabMachineDeployment(appConfig *appconfig.Config) (*machineDeployment, err
 		},
 		img:        "super/balloon",
 		appConfig:  appConfig,
-		machineSet: machine.NewMachineSet(nil, nil, nil),
+		machineSet: machine.NewMachineSet(nil, nil, nil, true),
 	}
 	return md, nil
 }
diff --git a/internal/command/deploy/plan_test.go b/internal/command/deploy/plan_test.go
new file mode 100644
index 000000000..1341d119a
--- /dev/null
+++ b/internal/command/deploy/plan_test.go
@@ -0,0 +1,460 @@
+package deploy
+
+import (
+	"context"
+	"sync"
+	"sync/atomic"
+	"testing"
+	"time"
+
+	"github.com/samber/lo"
+	"github.com/stretchr/testify/assert"
+	"github.com/superfly/fly-go"
+	"github.com/superfly/flyctl/internal/appconfig"
+	"github.com/superfly/flyctl/internal/flapsutil"
+	"github.com/superfly/flyctl/internal/mock"
+	"github.com/superfly/flyctl/internal/statuslogger"
+	"github.com/superfly/flyctl/iostreams"
+)
+
+func TestCompareConfig(t *testing.T) {
+	t.Parallel()
+	ctx := context.Background()
+
+	// Test that two identical configs are equal
+	config1 := &fly.MachineConfig{
+		Image: "image1",
+		Metadata: map[string]string{
+			"fly_flyctl_version": "v1",
+		},
+	}
+	config2 := &fly.MachineConfig{
+		Image: "image1",
+		Metadata: map[string]string{
+			"fly_flyctl_version": "v1",
+		},
+	}
+
+	assert.True(t, compareConfigs(ctx, config1, config2))
+
+	// Test that fly_flyctl_version is ignored
+	config2.Metadata["fly_flyctl_version"] = "v2"
+	assert.True(t, compareConfigs(ctx, config1, config2))
+
+	// Test that different images are not equal
+	config2.Image = "image2"
+	assert.False(t, compareConfigs(ctx, config1, config2))
+}
+
+func TestAppState(t *testing.T) {
+	t.Parallel()
+
+	machines := []*fly.Machine{
+		{
+			ID:    "machine1",
+			State: "started",
+		},
+		{
+			ID:    "machine2",
+			State: "started",
+		},
+	}
+
+	flapsClient := &mock.FlapsClient{
+		ListFunc: func(ctx context.Context, state string) ([]*fly.Machine, error) {
+			return machines, nil
+		},
+	}
+
+	ctx := context.Background()
+	md := &machineDeployment{
+		flapsClient: flapsClient,
+	}
+	appState, error := md.appState(ctx, nil)
+	assert.NoError(t, error)
+
+	assert.Equal(t, appState.Machines, machines)
+
+}
+
+func TestUpdateMachineConfig(t *testing.T) {
+	t.Parallel()
+
+	ctx := context.Background()
+	io := iostreams.System()
+	ctx = iostreams.NewContext(ctx, io)
+
+	oldMachine := &fly.Machine{
+		ID: "machine1",
+		Config: &fly.MachineConfig{
+			Image: "image1",
+			Metadata: map[string]string{
+				"fly_flyctl_version": "v1",
+			},
+		},
+		LeaseNonce: "hi",
+	}
+	newMachineConfig := &fly.MachineConfig{
+		Image: "image1",
+		Metadata: map[string]string{
+			"fly_flyctl_version": "v1",
+		},
+	}
+
+	statuslogger := statuslogger.Create(ctx, 1, false)
+	sl := statuslogger.Line(0)
+
+	badFlapsClient := &mock.FlapsClient{
+		UpdateFunc: func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+			return nil, assert.AnError
+		},
+	}
+	md := &machineDeployment{
+		flapsClient: badFlapsClient,
+		io:          io,
+		app: &fly.AppCompact{
+			Name: "myapp",
+		},
+		appConfig: &appconfig.Config{AppName: "myapp"},
+	}
+	_, err := md.updateMachineConfig(ctx, oldMachine, newMachineConfig, sl, false)
+	// updating a config with the same config should result in a noop, and shouldn't even use flaps
+	assert.NoError(t, err)
+
+	destroyedMachine := false
+	// recreate machines when we specify that
+	flapsClient := &mock.FlapsClient{
+		DestroyFunc: func(ctx context.Context, input fly.RemoveMachineInput, nonce string) (err error) {
+			destroyedMachine = true
+			return nil
+		},
+		UpdateFunc: func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+			return &fly.Machine{
+				ID:     builder.ID,
+				Config: builder.Config,
+			}, nil
+		},
+		LaunchFunc: func(ctx context.Context, builder fly.LaunchMachineInput) (out *fly.Machine, err error) {
+			return &fly.Machine{
+				ID:     builder.ID,
+				Config: builder.Config,
+			}, nil
+		},
+
+		ReleaseLeaseFunc: func(ctx context.Context, machineID, nonce string) error {
+			return nil
+		},
+	}
+
+	newMachineConfig.Image = "image2"
+	md.flapsClient = flapsClient
+
+	// ensure that we're actually creating a new machine when we replace it
+	machine, err := md.updateMachineConfig(ctx, oldMachine, newMachineConfig, sl, true)
+	assert.NoError(t, err)
+	assert.Equal(t, machine.Config, newMachineConfig)
+	assert.NotEqual(t, machine.ID, "machine2")
+	assert.True(t, destroyedMachine)
+
+	// just a regular machine update
+	machine, err = md.updateMachineConfig(ctx, oldMachine, newMachineConfig, sl, false)
+	assert.NoError(t, err)
+	assert.NotNil(t, machine)
+	assert.Equal(t, machine.Config, newMachineConfig)
+}
+
+func TestUpdateMachines(t *testing.T) {
+	t.Parallel()
+
+	ctx := context.Background()
+	io := iostreams.System()
+	ctx = iostreams.NewContext(ctx, io)
+
+	oldMachines := []*fly.Machine{
+		{
+			ID:    "machine1",
+			State: "started",
+			Config: &fly.MachineConfig{
+				Image: "image1",
+			},
+		},
+		{
+			ID:    "machine2",
+			State: "started",
+			Config: &fly.MachineConfig{
+				Image: "image1",
+			},
+		},
+		{
+			ID:    "machine3",
+			State: "started",
+			Config: &fly.MachineConfig{
+				Image: "image1",
+			},
+		},
+	}
+	newMachines := lo.Map(oldMachines, func(m *fly.Machine, _ int) *fly.Machine {
+		return &fly.Machine{
+			ID:    m.ID,
+			State: "started",
+			Config: &fly.MachineConfig{
+				Image: "image2",
+			},
+		}
+	})
+
+	acquiredLeases := sync.Map{}
+
+	flapsClient := &mock.FlapsClient{
+		AcquireLeaseFunc: func(ctx context.Context, machineID string, ttl *int) (*fly.MachineLease, error) {
+			if _, ok := acquiredLeases.Load(machineID); ok {
+				return nil, assert.AnError
+			}
+			acquiredLeases.Store(machineID, true)
+			return &fly.MachineLease{
+				Data: &fly.MachineLeaseData{
+					Nonce: "nonce",
+				},
+			}, nil
+		},
+		ReleaseLeaseFunc: func(ctx context.Context, machineID, nonce string) error {
+			return nil
+		},
+		UpdateFunc: func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+			return &fly.Machine{
+				ID:     builder.ID,
+				Config: builder.Config,
+				State:  "started",
+			}, nil
+		},
+		LaunchFunc: func(ctx context.Context, builder fly.LaunchMachineInput) (out *fly.Machine, err error) {
+			return &fly.Machine{
+				ID:     builder.ID,
+				Config: builder.Config,
+				State:  "started",
+			}, nil
+		},
+		WaitFunc: func(ctx context.Context, machine *fly.Machine, state string, timeout time.Duration) (err error) {
+			if state == "started" {
+				machine.State = "started"
+				return nil
+			} else {
+				return assert.AnError
+			}
+		},
+		ListFunc: func(ctx context.Context, state string) ([]*fly.Machine, error) {
+			return oldMachines, nil
+		},
+		StartFunc: func(ctx context.Context, machineID string, nonce string) (out *fly.MachineStartResponse, err error) {
+			return &fly.MachineStartResponse{}, nil
+		},
+		GetFunc: func(ctx context.Context, machineID string) (*fly.Machine, error) {
+			newMachine, _ := lo.Find(newMachines, func(m *fly.Machine) bool {
+				return m.ID == machineID
+			})
+			return newMachine, nil
+		},
+		GetProcessesFunc: func(ctx context.Context, machineID string) (fly.MachinePsResponse, error) {
+			return fly.MachinePsResponse{}, nil
+		},
+		RefreshLeaseFunc: func(ctx context.Context, machineID string, ttl *int, nonce string) (*fly.MachineLease, error) {
+			return &fly.MachineLease{
+				Data: &fly.MachineLeaseData{
+					Nonce: "nonce",
+				},
+			}, nil
+		},
+	}
+
+	ctx = flapsutil.NewContextWithClient(ctx, flapsClient)
+	md := &machineDeployment{
+		flapsClient: flapsClient,
+		io:          io,
+		app: &fly.AppCompact{
+			Name: "myapp",
+		},
+		appConfig:      &appconfig.Config{AppName: "myapp"},
+		waitTimeout:    10 * time.Second,
+		deployRetries:  5,
+		maxUnavailable: 3,
+	}
+
+	oldAppState := &AppState{
+		Machines: oldMachines,
+	}
+	newAppState := &AppState{
+		Machines: newMachines,
+	}
+	settings := updateMachineSettings{
+		pushForward:          true,
+		skipHealthChecks:     false,
+		skipSmokeChecks:      false,
+		skipLeaseAcquisition: false,
+	}
+
+	acquiredLeases = sync.Map{}
+	err := md.updateMachinesWRecovery(ctx, oldAppState, newAppState, nil, settings)
+	assert.NoError(t, err)
+
+	// let's make sure we retry deploys a few times
+	numFailures := 0
+	maxNumFailures := 3
+	flapsClient.UpdateFunc = func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+		if builder.ID == "machine2" {
+			numFailures++
+			if numFailures < maxNumFailures {
+				return nil, assert.AnError
+			}
+		}
+
+		return &fly.Machine{
+			ID:     builder.ID,
+			Config: builder.Config,
+			State:  "started",
+		}, nil
+	}
+	acquiredLeases = sync.Map{}
+	err = md.updateMachinesWRecovery(ctx, oldAppState, newAppState, nil, settings)
+	assert.NoError(t, err)
+	assert.Equal(t, 3, numFailures)
+
+	numFailures = 0
+	maxNumFailures = 10
+	acquiredLeases = sync.Map{}
+	err = md.updateMachinesWRecovery(ctx, oldAppState, newAppState, nil, settings)
+	assert.Error(t, err)
+
+	var sentUnrecoverable atomic.Bool
+	// we only return a single unrecoverable error, but that's enough to fail the deploy
+	flapsClient.UpdateFunc = func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+		if !sentUnrecoverable.Load() {
+			sentUnrecoverable.Store(true)
+			return nil, &unrecoverableError{err: assert.AnError}
+		} else {
+			return &fly.Machine{
+				ID:     builder.ID,
+				Config: builder.Config,
+				State:  "started",
+			}, nil
+		}
+	}
+	acquiredLeases = sync.Map{}
+	err = md.updateMachinesWRecovery(ctx, oldAppState, newAppState, nil, settings)
+	assert.Error(t, err)
+	var unrecoverableErr *unrecoverableError
+	assert.ErrorAs(t, err, &unrecoverableErr)
+}
+
+func TestUpdateOrCreateMachine(t *testing.T) {
+	t.Parallel()
+
+	ctx := context.Background()
+	io := iostreams.System()
+	ctx = iostreams.NewContext(ctx, io)
+
+	destroyedMachine := false
+	updatedMachine := false
+	createMachine := false
+
+	reset := func() {
+		destroyedMachine = false
+		updatedMachine = false
+		createMachine = false
+	}
+
+	flapsClient := &mock.FlapsClient{
+		AcquireLeaseFunc: func(ctx context.Context, machineID string, ttl *int) (*fly.MachineLease, error) {
+			return &fly.MachineLease{
+				Data: &fly.MachineLeaseData{
+					Nonce: "nonce",
+				},
+			}, nil
+		},
+		DestroyFunc: func(ctx context.Context, input fly.RemoveMachineInput, nonce string) (err error) {
+			destroyedMachine = true
+			return nil
+		},
+		UpdateFunc: func(ctx context.Context, builder fly.LaunchMachineInput, nonce string) (out *fly.Machine, err error) {
+			updatedMachine = true
+			return &fly.Machine{
+				ID:         builder.ID,
+				Config:     builder.Config,
+				State:      "started",
+				LeaseNonce: "nonce",
+			}, nil
+		},
+		LaunchFunc: func(ctx context.Context, builder fly.LaunchMachineInput) (out *fly.Machine, err error) {
+			createMachine = true
+			return &fly.Machine{
+				ID:         builder.ID,
+				Config:     builder.Config,
+				State:      "started",
+				LeaseNonce: "nonce",
+			}, nil
+		},
+	}
+
+	oldMachine := &fly.Machine{
+		ID: "machine1",
+		Config: &fly.MachineConfig{
+			Image: "image1",
+		},
+		LeaseNonce: "nonce",
+	}
+	newMachine := &fly.Machine{
+		ID: "machine1",
+		Config: &fly.MachineConfig{
+			Image: "image2",
+		},
+		LeaseNonce: "nonce",
+	}
+
+	md := &machineDeployment{
+		flapsClient: flapsClient,
+		io:          io,
+		app: &fly.AppCompact{
+			Name: "myapp",
+		},
+		appConfig: &appconfig.Config{AppName: "myapp"},
+	}
+
+	statuslogger := statuslogger.Create(ctx, 1, false)
+	sl := statuslogger.Line(0)
+
+	// destroy old machine
+	reset()
+	mach, lease, err := md.updateOrCreateMachine(ctx, oldMachine, nil, sl)
+	assert.NoError(t, err)
+	assert.True(t, destroyedMachine)
+	assert.Nil(t, mach)
+	assert.Nil(t, lease)
+
+	// update old machine
+	reset()
+	mach, lease, err = md.updateOrCreateMachine(ctx, oldMachine, newMachine, sl)
+	assert.NoError(t, err)
+	assert.True(t, updatedMachine)
+	assert.NotNil(t, mach)
+	assert.Nil(t, lease)
+	assert.Equal(t, mach.Config, newMachine.Config)
+
+	// create new machine
+	reset()
+	mach, lease, err = md.updateOrCreateMachine(ctx, nil, newMachine, sl)
+	assert.NoError(t, err)
+	assert.True(t, createMachine)
+	assert.NotNil(t, mach)
+	assert.NotNil(t, lease)
+	assert.Equal(t, mach.Config, newMachine.Config)
+
+	// new and old machines are nil, so noop
+	reset()
+	mach, lease, err = md.updateOrCreateMachine(ctx, nil, nil, sl)
+	assert.NoError(t, err)
+	assert.False(t, destroyedMachine)
+	assert.False(t, updatedMachine)
+	assert.False(t, createMachine)
+	assert.Nil(t, mach)
+	assert.Nil(t, lease)
+
+}