feat: implement reconciliation loop

coder · evgeniy-scherbina · Apr 17, 2025 · Mar 12, 2025 · Mar 13, 2025 · Mar 13, 2025
commit fe60b569ad754245e28bac71e0ef3c83536631bb
diff --git a/coderd/prebuilds/api.go b/coderd/prebuilds/api.go
@@ -0,0 +1,30 @@
+package prebuilds
+
+import (
+	"context"
+
+	"github.com/google/uuid"
+
+	"github.com/coder/coder/v2/coderd/database"
+)
+
+type ReconciliationOrchestrator interface {
+	Reconciler
+
+	RunLoop(ctx context.Context)
+	Stop(ctx context.Context, cause error)
+}
+
+type Reconciler interface {
+	// SnapshotState MUST be called inside a repeatable-read tx.
+	SnapshotState(ctx context.Context, store database.Store) (*ReconciliationState, error)
+	// DetermineActions MUST be called inside a repeatable-read tx.
+	DetermineActions(ctx context.Context, state PresetState) (*ReconciliationActions, error)
+	// Reconcile MUST be called inside a repeatable-read tx.
+	Reconcile(ctx context.Context, state PresetState, actions ReconciliationActions) error
+}
+
+type Claimer interface {
+	Claim(ctx context.Context, store database.Store, userID uuid.UUID, name string, presetID uuid.UUID) (*uuid.UUID, error)
+	Initiator() uuid.UUID
+}
diff --git a/coderd/prebuilds/noop.go b/coderd/prebuilds/noop.go
@@ -0,0 +1,29 @@
+package prebuilds
+
+import (
+	"context"
+
+	"github.com/coder/coder/v2/coderd/database"
+)
+
+type NoopReconciler struct{}
+
+func NewNoopReconciler() *NoopReconciler {
+	return &NoopReconciler{}
+}
+
+func (NoopReconciler) RunLoop(context.Context)     {}
+func (NoopReconciler) Stop(context.Context, error) {}
+func (NoopReconciler) SnapshotState(context.Context, database.Store) (*ReconciliationState, error) {
+	return &ReconciliationState{}, nil
+}
+
+func (NoopReconciler) DetermineActions(context.Context, PresetState) (*ReconciliationActions, error) {
+	return &ReconciliationActions{}, nil
+}
+
+func (NoopReconciler) Reconcile(context.Context, PresetState, ReconciliationActions) error {
+	return nil
+}
+
+var _ ReconciliationOrchestrator = NoopReconciler{}
diff --git a/coderd/prebuilds/reconcile.go b/coderd/prebuilds/reconcile.go
@@ -0,0 +1,88 @@
+package prebuilds
+
+import (
+	"time"
+
+	"github.com/google/uuid"
+	"golang.org/x/xerrors"
+
+	"github.com/coder/coder/v2/coderd/database"
+	"github.com/coder/coder/v2/coderd/util/slice"
+)
+
+// ReconciliationState represents a full point-in-time snapshot of state relating to prebuilds across all templates.
+type ReconciliationState struct {
+	Presets             []database.GetTemplatePresetsWithPrebuildsRow
+	RunningPrebuilds    []database.GetRunningPrebuiltWorkspacesRow
+	PrebuildsInProgress []database.CountInProgressPrebuildsRow
+	Backoffs            []database.GetPresetsBackoffRow
+}
+
+// PresetState is a subset of ReconciliationState but specifically for a single preset.
+type PresetState struct {
+	Preset     database.GetTemplatePresetsWithPrebuildsRow
+	Running    []database.GetRunningPrebuiltWorkspacesRow
+	InProgress []database.CountInProgressPrebuildsRow
+	Backoff    *database.GetPresetsBackoffRow
+}
+
+// ReconciliationActions represents the set of actions which must be taken to achieve the desired state for prebuilds.
+type ReconciliationActions struct {
+	Actual                       int32       // Running prebuilds for active version.
+	Desired                      int32       // Active template version's desired instances as defined in preset.
+	Eligible                     int32       // Prebuilds which can be claimed.
+	Outdated                     int32       // Prebuilds which no longer match the active template version.
+	Extraneous                   int32       // Extra running prebuilds for active version (somehow).
+	Starting, Stopping, Deleting int32       // Prebuilds currently being provisioned up or down.
+	Failed                       int32       // Number of prebuilds which have failed in the past CODER_WORKSPACE_PREBUILDS_RECONCILIATION_BACKOFF_LOOKBACK_PERIOD.
+	Create                       int32       // The number of prebuilds required to be created to reconcile required state.
+	DeleteIDs                    []uuid.UUID // IDs of running prebuilds required to be deleted to reconcile required state.
+	BackoffUntil                 time.Time   // The time to wait until before trying to provision a new prebuild.
+}
+
+func NewReconciliationState(presets []database.GetTemplatePresetsWithPrebuildsRow, runningPrebuilds []database.GetRunningPrebuiltWorkspacesRow,
+	prebuildsInProgress []database.CountInProgressPrebuildsRow, backoffs []database.GetPresetsBackoffRow,
+) ReconciliationState {
+	return ReconciliationState{Presets: presets, RunningPrebuilds: runningPrebuilds, PrebuildsInProgress: prebuildsInProgress, Backoffs: backoffs}
+}
+
+func (s ReconciliationState) FilterByPreset(presetID uuid.UUID) (*PresetState, error) {
+	preset, found := slice.Find(s.Presets, func(preset database.GetTemplatePresetsWithPrebuildsRow) bool {
+		return preset.ID == presetID
+	})
+	if !found {
+		return nil, xerrors.Errorf("no preset found with ID %q", presetID)
+	}
+
+	running := slice.Filter(s.RunningPrebuilds, func(prebuild database.GetRunningPrebuiltWorkspacesRow) bool {
+		if !prebuild.CurrentPresetID.Valid {
+			return false
+		}
+		return prebuild.CurrentPresetID.UUID == preset.ID &&
+			prebuild.TemplateVersionID == preset.TemplateVersionID // Not strictly necessary since presets are 1:1 with template versions, but no harm in being extra safe.
+	})
+
+	// These aren't preset-specific, but they need to inhibit all presets of this template from operating since they could
+	// be in-progress builds which might impact another preset. For example, if a template goes from no defined prebuilds to defined prebuilds
+	// and back, or a template is updated from one version to another.
+	// We group by the template so that all prebuilds being provisioned for a prebuild are inhibited if any prebuild for
+	// any preset in that template are in progress, to prevent clobbering.
+	inProgress := slice.Filter(s.PrebuildsInProgress, func(prebuild database.CountInProgressPrebuildsRow) bool {
+		return prebuild.TemplateID == preset.TemplateID
+	})
+
+	var backoff *database.GetPresetsBackoffRow
+	backoffs := slice.Filter(s.Backoffs, func(row database.GetPresetsBackoffRow) bool {
+		return row.PresetID == preset.ID
+	})
+	if len(backoffs) == 1 {
+		backoff = &backoffs[0]
+	}
+
+	return &PresetState{
+		Preset:     preset,
+		Running:    running,
+		InProgress: inProgress,
+		Backoff:    backoff,
+	}, nil
+}
diff --git a/coderd/prebuilds/state.go b/coderd/prebuilds/state.go
@@ -0,0 +1,167 @@
+package prebuilds
+
+import (
+	"math"
+	"slices"
+	"time"
+
+	"github.com/coder/quartz"
+
+	"github.com/coder/coder/v2/coderd/database"
+)
+
+func (p PresetState) CalculateActions(clock quartz.Clock, backoffInterval time.Duration) (*ReconciliationActions, error) {
+	// TODO: align workspace states with how we represent them on the FE and the CLI
+	//	     right now there's some slight differences which can lead to additional prebuilds being created
+
+	// TODO: add mechanism to prevent prebuilds being reconciled from being claimable by users; i.e. if a prebuild is
+	// 		 about to be deleted, it should not be deleted if it has been claimed - beware of TOCTOU races!
+
+	var (
+		actual                       int32 // Running prebuilds for active version.
+		desired                      int32 // Active template version's desired instances as defined in preset.
+		eligible                     int32 // Prebuilds which can be claimed.
+		outdated                     int32 // Prebuilds which no longer match the active template version.
+		extraneous                   int32 // Extra running prebuilds for active version (somehow).
+		starting, stopping, deleting int32 // Prebuilds currently being provisioned up or down.
+	)
+
+	if p.Preset.UsingActiveVersion {
+		actual = int32(len(p.Running))
+		desired = p.Preset.DesiredInstances.Int32
+	}
+
+	for _, prebuild := range p.Running {
+		if p.Preset.UsingActiveVersion {
+			if prebuild.Ready {
+				eligible++
+			}
+
+			extraneous = int32(math.Max(float64(actual-p.Preset.DesiredInstances.Int32), 0))
+		}
+
+		if prebuild.TemplateVersionID == p.Preset.TemplateVersionID && !p.Preset.UsingActiveVersion {
+			outdated++
+		}
+	}
+
+	// In-progress builds are common across all presets belonging to a given template.
+	// In other words: these values will be identical across all presets belonging to this template.
+	for _, progress := range p.InProgress {
+		num := progress.Count
+		switch progress.Transition {
+		case database.WorkspaceTransitionStart:
+			starting += num
+		case database.WorkspaceTransitionStop:
+			stopping += num
+		case database.WorkspaceTransitionDelete:
+			deleting += num
+		}
+	}
+
+	var (
+		toCreate = int(math.Max(0, float64(
+			desired-(actual+starting)), // The number of prebuilds currently being stopped (should be 0)
+		))
+		toDelete = int(math.Max(0, float64(
+			outdated- // The number of prebuilds running above the desired count for active version
+				deleting), // The number of prebuilds currently being deleted
+		))
+
+		actions = &ReconciliationActions{
+			Actual:     actual,
+			Desired:    desired,
+			Eligible:   eligible,
+			Outdated:   outdated,
+			Extraneous: extraneous,
+			Starting:   starting,
+			Stopping:   stopping,
+			Deleting:   deleting,
+		}
+	)
+
+	// If the template has become deleted or deprecated since the last reconciliation, we need to ensure we
+	// scale those prebuilds down to zero.
+	if p.Preset.Deleted || p.Preset.Deprecated {
+		toCreate = 0
+		toDelete = int(actual + outdated)
+		actions.Desired = 0
+	}
+
+	// We backoff when the last build failed, to give the operator some time to investigate the issue and to not provision
+	// a tonne of prebuilds (_n_ on each reconciliation iteration).
+	if p.Backoff != nil && p.Backoff.NumFailed > 0 {
+		actions.Failed = p.Backoff.NumFailed
+
+		backoffUntil := p.Backoff.LastBuildAt.Add(time.Duration(p.Backoff.NumFailed) * backoffInterval)
+
+		if clock.Now().Before(backoffUntil) {
+			actions.Create = 0
+			actions.DeleteIDs = nil
+			actions.BackoffUntil = backoffUntil
+
+			// Return early here; we should not perform any reconciliation actions if we're in a backoff period.
+			return actions, nil
+		}
+	}
+
+	// It's possible that an operator could stop/start prebuilds which interfere with the reconciliation loop, so
+	// we check if there are somehow more prebuilds than we expect, and then pick random victims to be deleted.
+	if extraneous > 0 {
+		// Sort running IDs by creation time so we always delete the oldest prebuilds.
+		// In general, we want fresher prebuilds (imagine a mono-repo is cloned; newer is better).
+		slices.SortFunc(p.Running, func(a, b database.GetRunningPrebuiltWorkspacesRow) int {
+			if a.CreatedAt.Before(b.CreatedAt) {
+				return -1
+			}
+			if a.CreatedAt.After(b.CreatedAt) {
+				return 1
+			}
+
+			return 0
+		})
+
+		for i := 0; i < int(extraneous); i++ {
+			if i >= len(p.Running) {
+				// This should never happen.
+				// TODO: move up
+				// c.logger.Warn(ctx, "unexpected reconciliation state; extraneous count exceeds running prebuilds count!",
+				//	slog.F("running_count", len(p.Running)),
+				//	slog.F("extraneous", extraneous))
+				continue
+			}
+
+			actions.DeleteIDs = append(actions.DeleteIDs, p.Running[i].ID)
+		}
+
+		// TODO: move up
+		// c.logger.Warn(ctx, "found extra prebuilds running, picking random victim(s)",
+		//	slog.F("template_id", p.Preset.TemplateID.String()), slog.F("desired", desired), slog.F("actual", actual), slog.F("extra", extraneous),
+		//	slog.F("victims", victims))
+
+		// Prevent the rest of the reconciliation from completing
+		return actions, nil
+	}
+
+	actions.Create = int32(toCreate)
+
+	// if toDelete > 0 && len(p.Running) != toDelete {
+	// TODO: move up
+	// c.logger.Warn(ctx, "mismatch between running prebuilds and expected deletion count!",
+	//	slog.F("template_id", s.preset.TemplateID.String()), slog.F("running", len(p.Running)), slog.F("to_delete", toDelete))
+	// }
+
+	// TODO: implement lookup to not perform same action on workspace multiple times in $period
+	// 		 i.e. a workspace cannot be deleted for some reason, which continually makes it eligible for deletion
+	for i := 0; i < toDelete; i++ {
+		if i >= len(p.Running) {
+			// TODO: move up
+			// Above warning will have already addressed this.
+			continue
+		}
+
+		actions.DeleteIDs = append(actions.DeleteIDs, p.Running[i].ID)
+	}
+
+	return actions, nil
+}