Priority Matters: Optimising Kubernetes Clusters Usage with Constraint-Based Pod Packing

Henrik Daniel Christensen, Saverio Giallorenzo, Jacopo Mauro · 2025

Read Priority Matters: Optimising Kubernetes Clusters Usage with Constraint-Based Pod Packing by Henrik Daniel Christensen, Saverio Giallorenzo, Jacopo Mauro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08373.txt.

Introduction

Henrik Daniel Christensen, Saverio Giallorenzo, and Jacopo Mauro improve pod placing by adding constraint coding as a fallback to the default placer. Kubernetes runs app parts as pods on cluster nodes, keeping rankings and resource requests. Its fast heuristic placer can fragment resources and leave deployable pods unplaced, above all higher priority ones, wasting cluster capacity.

Their plug in uses the OR-Tools solver to find optimal allocations when the default attempt fails. Within a one second window on small to mid sized clusters, it improves placing in many scenarios where the default placer fails and certifies optimality in others. A ten second window raises the improvement share substantially.

Catalog record

CREATORHenrik Daniel Christensen, Saverio Giallorenzo, Jacopo Mauro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08373

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Priority Matters: Optimising Kubernetes Clusters Usage with Constraint-Based Pod Packing Henrik Daniel Christensen, Saverio Giallorenzo, Jacopo Mauro Abstract Distributed applications employ Kubernetes for scalable, fault-tolerant deployments over computer clusters, where application components run in groups of containers called pods. The scheduler, at the heart of Kubernetes’ architecture, determines the placement of pods given their priority and resource requirements on cluster nodes. To quickly allocate pods, the scheduler uses lightweight heuristics that can lead to suboptimal placements and resource fragmentation, preventing allocations of otherwise deployable pods on the available nodes. We propose the usage of constraint programming to find the optimal allocation of pods satisfying all their priorities and resource requests. Implementation-wise, our solution comes as a plug-in to the default scheduler that operates as a fallback mechanism when some pods cannot be allocated. Using the OR-Tools constraint solver, our experiments on small-to-mid-sized clusters indicate that, within a 1-second scheduling window, our approach places more higher-priority pods than the default scheduler (possibly demonstrating allocation optimality) in over 44% of realisable allocation scenarios where the default scheduler fails, while certifying that the default scheduler’s placement is already optimal in over 19% of scenarios. With a 10-second window, our approach improves placements in over 73% and still certifies that the default scheduler’s placement is already optimal in over 19% of scenarios. Introduction The state-of-the-art paradigms for implementing distributed systems are microservices ( 8 ) and serverless ( 14 ) . These paradigms decompose a distributed application into components that one can replicate independently of each other, according to their workload, avoiding wasting resources on overprovisioned components. Practically, developers and platforms use containers ( 25 ) to package these components and simplify their deployment/replication and container orchestrators ( 13 ) to automate deployment, scaling, and management of containers on clusters of computation nodes. Nowadays, the main container orchestrator is Kubernetes ( 24 ) . In Kubernetes, the pod represents the smallest deployable unit, enclosing a group of containers that share an execution context (e.g., networking, storage). Figure 1: Example of Kubernetes scheduler suboptimal pod allocation problem – Node and Pod sizes represent their memory capacity/occupancy. Left: the heuristics place Pod 1 and Pod 2 on separate nodes, leaving insufficient memory on either node for Pod 3, despite the cluster having enough total resources. Centre: reallocation of the first two pods onto one node enables the (Right:) optimal placement of all pods. The scheduler, at the heart of Kubernetes’ architecture, determines pods’ placement according to their requirements and node resources. The scheduler determines allocations through heuristics that prioritise speed and scalability but neglect optimal resource usage, possibly leading to system degradation (some pods are not allocated) or overprovisioning (the inclusion of new cluster nodes to host the pods not allocated) and resource waste (money, energy, etc.) ( 4 ) . Recent studies ( 3 ) have shown that a staggering 99.94% of Kubernetes clusters are overprovisioned, where the average gap between provisioned and requested resources is 40% for CPU and 57% for memory. As an illustration of this phenomenon, shown in Figure 1 , let us consider a scenario with a 2-node cluster, each node with 4 GB of memory, where we want to deploy 3 pods in sequence, all with the same priority but requiring respectively 2, 2, and 3 GB of memory. When scheduling a pod, the scheduler heuristics use a LeastAllocated policy to rank nodes. Thus, it likely allocates the first two pods on one node each. When the scheduler receives the request for the last pod, it cannot find a node with 3 GB of memory available, leaving the allocation request pending, possibly requiring the addition of a new node to deploy the pod. The allocation (left of Figure 1 ) is suboptimal because the nodes have enough resources to host all pods. If we could reallocate one of two pods onto one node (centre of Figure 1 ), we would obtain the optimal allocation (right of Figure 1 ). Pod priorities further complicate the problem of finding the optimal schedule in Kubernetes. The scheduler must allocate high-priority pods preferentially, even if it means pre-empting queued lower-priority pods. Hence, the dynamic nature of workloads, which requires the frequent creation/deletion of pods with varying priorities, further complicates the task of making allocation decisions that optimise overall resource usage and performance. In the worst case, the default scheduler’s policy can lead to pod starvation. 1 1 1 https://github.com/kubernetes/kubernetes/issues/86373 Our contribution We tackle the shortcomings of the Kubernetes scheduler heuristics by identifying failed deployment attempts that could fit within the cluster resources and devising an optimal resource allocation that ensures efficient resource usage and wards off avoidable operational costs. In this instance, we focus our attention on the representative case of small and medium-size clusters, which are renownedly prone to overprovisioning ( 5 ) and where even saving single-node resources can significantly impact overall resource availability and costs, especially when leveraging the cloud infrastructure. Our proposal is a conservative one and works by complementing the heuristics of the Kubernetes scheduler. We let the default heuristics handle allocations as long as they can satisfy pod requirements. If scheduling requests become pending (signalling requirement unsatisfiability) but they can fit within the available resources, then we use a (complete) solver to possibly find a solution (within a fixed timeframe) that satisfies all the priority and resource constraints. To find a global optimum, we solve a series of optimisation problems on the possible pod allocations, given the pods’ priority. For every priority level, we guarantee the deployment of the maximum number of pods with that priority and minimise the total number of moved pods, to curtail overall system disruptions. The allocation problem is notoriously NP-hard ( 9 ) , which implies that finding an optimal solution may take a long time. Since we aim to have a scheduling decision within a useful timeframe (e.g., 10 sec.), we set a timeout for each priority level to provide either a proven optimum or, if the solver timed-out, the best feasible allocation found until the timeout. We evaluate feasibility and limitations of this approach using the state-of-the-art CP-SAT solver from OR-Tools ( 30 ) . We simulate scheduling decision requests for small-to-medium-sized clusters with up to 32 nodes and varying degrees of pod requests, resource demands, and priorities. Our findings demonstrate that our approach scales to medium-sized clusters and can usually find a better, if not optimal, solution in less than 1 seconds for cluster of up to 8 nodes, or in 10–20 seconds for clusters of up to 32 nodes. In particular, with 1 second timeouts (resp. 10 seconds), our approach finds better or optimal solutions in 44% (resp. 73%) of scenarios where the default scheduler can not allocate all the pods. Moreover, our approach proves that the solution of the default scheduler is already optimal and can not be improved in 19% (resp. 19%) cases. Structure of the paper We introduce Kubernetes and its scheduler in Preliminaries . In Implementation we detail our optimisation approach, its realisation, and integration as a Kubernetes plugin. In Evaluation we present the experiments conducted to evaluate our approach. We conclude by discussing Related Work and future directions. Preliminaries Kubernetes Kubernetes is the leading

Read the complete text