Formalization of the optimal kubernetes autoscaling problem with pod startup delay

Abstract

Proactive Kubernetes autoscalers predict future workload and provision pods in advance; however, all existing systems share an implicit assumption that new capacity becomes available instantly or after a single fixed delay that is uniform across services. In polyglot deployments, however, startup delays can differ by an order of magnitude, making a single global time-shift correction inapplicable and creating a fundamental mismatch between the optimizer's decision and the actual availability of capacity. This paper formalizes Kubernetes autoscaling as a discrete optimization problem with dead-time constraints, where the startup delay enters the effective capacity model as a per-service parameter. For the single-service case, discrete convexity of the objective function in the scaling decision is proved. The multi-service variant with a cluster resource budget is classified as an NP-hard boundedknapsack problem, for which three solution approaches are proposed: a greedy algorithm ranked by marginal efficiency, budget-state dynamic programming, and LP relaxation with rounding. The connection to the M/M/k/setup queueing model analytically establishes the fundamental limitation of reactive scaling: the waiting-time penalty decays only polynomially with the number of servers, which makes it impossible to compensate for the startup delay after a demand peak has arrived. The structural asymmetry in the optimizer's response to forecast errors, induced by the deadtime constraint, is analyzed separately. It is shown that demand overestimation can be neutralized at decision time because the optimizer simply refrains from scaling, whereas the consequences of underestimation are irrecoverable: any corrective action takes effect only after the startup delay has elapsed, during which the system operates in a capacity deficit. This asymmetry is a structural property of the model and requires no modification of the objective function. The theoretical results obtained provide a formal foundation for designing practical proactive autoscalers adapted to the heterogeneous environment of polyglot microservice systems.

Keywords: autoscaling, Kubernetes, microservices, startup delay, discrete optimization, load forecasting, dynamic programming, asymmetric loss.