Rightsizing Clusters for Time-Limited Tasks

Cloud computing has emerged as the preferred platform due to its flexibility in planning and provisioning computing clusters with resources for application deployment and scaling. An undersized cluster degrades performance, whereas an oversized cluster causes wastage and drives up cost. Rightsizing addresses this trade-off by constructing an optimal cluster that balances cost and capacity. Rightsizing has been well-studied over a wide spectrum from pre-deployment (cold-start) cluster provisioning to dynamic node provisioning (E.g. [17, 35, 37, 34, 24]).

Cold-start rightsizing is used as an effective technique to boot-strap an initial cluster based on the workload characteristics, for large public clouds. The capacity of these initial clusters are then managed using dynamic provisioning techniques such as auto-scalers [21]. Thus, the cold-start righsizing and dynamic provisioning techniques are complementary in nature.

Cold-start rightsizing also plays an important role in limited-resource settings where vast resource pools might not exist to support dynamic auto-scalers. In such scenarios, cold-start rightsizing could be the most suitable approach to shape the cluster to a given workload without incurring any capital expenses or logistical challenges. Examples of these scenarios include Telco clouds[1] which co-host computing clusters on base-stations and on-premise clouds dedicated to a single organization. In such infrastructure settings, installation cost on 5G base-stations could be $3\times$ [8] higher than the operational expenditure. Similar challenges exist in on-premise clouds and edge-clouds[20, 6, 4] which may not have huge resource pools and sufficient number of intra-organization tenants to enable arbitrary on-demand scaling.

This paper deals with cold-start rightsizing that sizes a cluster at the time of installation based on projected demands of the application(s) to be hosted on it. The aim is to address the cost-performance trade-off by constructing an optimal cluster that balances cost and capacity, for a given workload of tasks.

Cold-start Rightsizing. Consider a workload (set of tasks) consisting of $n$ tasks, where each task demands specific quantities of $D$ resources (e.g CPU cores, memory and disk space). The cloud environment offers $m$ types of compute nodes that differ in terms of cost and capacity on the $D$ resources, and a replica of a given node-type is a node. Both demands and capacities can be conveniently represented as $D$-dimensional vectors. The goal is to purchase a minimum cost cluster of nodes and place each task on a node such that the aggregate demand of tasks placed on any node does not exceed its capacity along any dimension (resource). We denote this problem as Rightsizing As discussed below (Prior Work), rightsizing has been well-studied in the contexts of cloud computing, virtual machine migration and bin packing.

Cold-start Rightsizing for Time-Limited Tasks. While the above formulation targets rightsizing purely based on resource-demands, real-world tasks are additionally characterized by timeline properties on when they run, how long they run and how much resources they consume at any given time.

These timeline characteristics are available as direct inputs for batch applications [29], for instance, batch jobs running at 1:00AM for few hours or a burst in service load during peak hours. Similarly, scheduled tasks with deadlines are encountered in edge  [10, 30]. Examples are applications that sample duty-cycled data-sources [36]; or adapting to platform activity (e.g. advanced sleeps modes of 5G New Radio which exploit stable user activity patterns [2]). Since the tasks are active only within a specific time-interval, resources could be reused by other tasks outside the interval. This time-limiting nature of tasks could be exploited in rightsizing the cluster leading to cost reduction. With the above motivation, we introduce and study the generalized cold-start rightsizing problem for time-limited tasks.

The problem, denoted TL-Rightsizing, starts with a set of tasks (with varying demands) and different nodes-types (with varying capacity and cost) as in Rightsizing. In addition, we assume a timeline divided into $T$ discrete timeslots, say a day divided into $T=24$ hours, and each task has start and end timeslots as an interval $[s,e]$. The objective of TL-Rightsizing is to purchase a minimum cost set of nodes and place the tasks on the nodes such that the aggregate demand of tasks placed on any node does not violate its capacity at any timeslot. Figure 1 illustrates TL-Rightsizing and its benefits over Rightsizing.

For scenarios where demand, start and completion times are not directly known, we could build on cloud-centric time-series analysis  [18, 13] to leverage historical traces of task resource consumption from existing production or test deployments. The resource-demand of the task for various time windows (e.g. hourly, daily, weekly) can be estimated from the traces and each window can be treated as an independent task with a specific start and ending time. For example, a task handling stock market quotes may require high resource regime during market hours and low resource-demand regime at other times. For a timeline that spans a week starting Monday 00:00 hours, we can model this work as six tasks as shown in Figure 2.

Prior Work. While TL-Rightsizing has not been studied in prior work, two streams of special cases, Rightsizing and interval coloring, have been well explored.

Rightsizing: The Rightsizing problem corresponds to the restricted setting where all the tasks are perpetually active, in other words, there is no consideration of timeline ($T=1$).

If tasks are items and nodes are bins, then the problem corresponds to multi-dimensional bin-packing over multiple bin-types. Since the problem is NP-hard, a polynomial time optimal solution is infeasible, unless NP=P. While exponential time integer programming [15] can produce optimal solutions, meta-heuristics such as genetic algorithms [14], particle swarm [27] and ant colony optimization [11] can handle only small problem sizes due to high running time.

Alternatively, fast and scalable heuristics have been developed by building on strategies from the bin packing domain. Working in the context of optimizing virtual machines, Panigrahy et al. [25] study the single node-type special case ($m=1$), called vector bin packing. They generalize bin packing heuristics (such as first and best-fit) and demonstrate that the heuristics produce near-optimal solutions in practice. Gabay and Zaourar [12] present similar procedures for multiple node-types with uniform costs. Other approaches for special cases and variations of Rightsizing have been proposed (e.g., [16, 22]) and we refer to [28] for a detailed discussion.

We build on the work of Silva et al. [28] and Patt-Shamir and Rawitz [26], who present algorithms for the general Rightsizing problem. The latter work proposes a two-phase procedure that first maps each task to an appropriate node-type by comparing demands and capacities, then solves for each node-type independently. They prove that the algorithm has an approximation ratio of $O(D)$.

From the theoretical perspective, Chekuri and Khanna [7] present an $O(\log D)$-approximation algorithm for the (single node-type) vector bin packing and Patt-Shamir and Rawitz [26] generalize the result to multiple node-types. However, the algorithms are based on an exponential size LP formulation and have a high running time of $n^{O(D)}$.

Interval Coloring (or task scheduling): Interval coloring with bandwidths [3] is equivalent to our setting with single dimensional resources ($D=1$) and single node-type ($m=1$). In this problem, the input is a set of intervals with bandwidth requirements and the objective is to color them with minimum number of colors such that the aggregate bandwidth of intervals of the same color does not exceed a fixed capacity at any timeslot. In our context, the intervals are tasks and the colors are nodes. The problem is studied in both online and offline settings (see survey [19]) and procedures with $O(1)$ approximation ratios have been designed.

Rightsizing for time-limited tasks: The TL-Rightsizing problem generalizes and combines elements from the above two streams: the notion of time-limited tasks from task scheduling, and the concepts of multi-dimensionality and multiple node-types from rightsizing.

Our Contributions. We introduce the TL-Rightsizing problem that reduces the cluster cost by exploiting the time-limited nature of tasks, and make the following contributions:

• •

  We first design a two-phase algorithm, denoted PenaltyMap, that serves as our baseline. The algorithms uses ideas from prior work on Rightsizing and task scheduling. It first maps each task to an appropriate node-type via a penalty-based heuristic and then solves each node-type separately. We present a detailed analysis and prove that the algorithm has an approximation ratio of $O(D\cdot\min(m,T))$.

• •

  While PenaltyMap algorithm performs reasonably well in practice, we identify certain deficiencies in the mapping strategy and develop an improved mapping based on linear programming, denoted LP-map.

• •

  The LP-map algorithm packs tasks mapped to each node-type in a maximal manner, but we observe that it may leave empty capacity that can be filled by tasks mapped to other node-types. We present a cross-node-type filling procedure that reduces the wastage and lowers the overall solution cost.

• •

  We design a scalable strategy (that can handle large inputs) for determining a lowerbound on the optimal cost and use it to measure the efficacy of our algorithms. Using synthetic and real-world traces, we demonstrate that: (i) compared to the baseline PenaltyMap, LP-map offers up to $150\%$ reduction in the cost (normalized with respect to the lowerbound); (ii) cross-node-type filling provides further improvement up to $8\%$, taking the solution closer to the optimal; (iii) the final algorithm (LP-map + cross node-type filling) generates solutions within at most $20\%$ of the lowerbound, and closer in most cases.

Problem Definition [TL-Rightsizing]. Let the timeline be divided into $T$ discrete timeslots numbered $1,2,\ldots,T$. Let $D$ be the number of resources (or dimensions). We have a set of $m$ node-types ${\cal B}$. Each node-type $B\in{\cal B}$ is associated with a price ${\tt cost}(B)$, and offers a capacity ${\tt cap}(B,d)$, along each dimension $d\in[1,D]$. The input consists of a set of $n$ tasks ${\cal U}$; each task $u\in{\cal U}$ is specified by a demand ${\tt dem}(u,d)$ along each dimension $d$ and a span $[s(u),e(u)]\subseteq[1,T]$, with $s(u)$ and $e(u)$ being the starting and the ending timeslots of $u$. We say that task $u$ is active at a timeslot $t$, if $t\in[s(u),e(u)]$ and denote it as ‘$u\sim t$’.

A $B$-type node refers to a replica $b$ having the same price and capacity: ${\tt cost}(b)={\tt cost}(B)$ and ${\tt cap}(b,d)={\tt cap}(B,d)$, for all $d\in[1,D]$. A feasible solution is to purchase a set of nodes $S$ and place each task in one of the nodes in $S$ such that for any node $b$, the total demand at any timeslot and any dimension does not violate the capacity offered by the node.

wherein $b$ is viewed as the set of tasks placed in it. We refer to the above as the capacity constraint. A solution may purchase multiple nodes of the same node-type. The cost of the solution is the aggregate cost of the nodes purchased: ${\tt cost}(S)=\sum_{b\in S}{\tt cost}(b)$. The goal is to compute a solution of minimum cost.

Timeline Trimming. While $T$ can be arbitrarily large, as is common in task scheduling (see e.g., [5]), it can trimmed by considering only the start timeslots of tasks and ignoring the rest so that $T\leq n$. It is not difficult to argue that the transformation does not change the set of feasible solutions.

We design a baseline algorithm, denoted PenaltyMap, by building on heuristics from prior work on the following two special cases: interval coloring [17], wherein number of node-types $m=1$ and dimensions $D=1$, and ${\sf Rightsizing}$ [28, 26], wherein there is no timeline ($T=1$).

Two Phase Framework. The intuition behind the algorithm is that each task must be placed on a node whose capacity matches the demand of the task. For instance, placing a task $u$ having high demand along a particular dimension $d$ to a node with low capacity along $d$ would block us from accommodating other tasks on the node, leading to capacity wastage along the other dimensions. The algorithm addresses the issue by using a two-phase framework. First, each task $u\in{\cal U}$ is mapped to a suitable node-type $B$ by comparing the demand of $u$ with the capacities of the node-types. The second phase partitions the tasks based on their node-types and solves each node-type separately, as in the single node-type setting, via a popular heuristic used in interval coloring.

Mapping Phase. For a task $u$, define the relative demand (or height) with respect to a node-type $B$ as:

Intuitively, $h_{\rm avg}(u|B)$ is a measure on the space occupied by $u$, if the task were placed in a node of type $B$. Taking the cost into consideration, define the penalty of $u$ relative to $B$ as:

We map $u$ to the node-type ${\tt B}^{*}_{\rm avg}(u)$, yielding the least penalty:

Placement Phase. We partition the tasks based on their node-types and process each group separately. Consider a node-type $B$ and let $V_{B}$ denote the set of tasks mapped to $B$. We process the tasks in $V_{B}$ in the increasing order of starting timeslots. Suppose we have processed a certain number of tasks and have purchased a set of nodes to accommodate them. Let $u$ be the next task. We check if $u$ can fit in some node $b$ purchased already without violating the capacity of the node. If so, among the feasible nodes, we place $u$ in the node purchased the earliest (first-fit). Otherwise, we purchase a new $B$-type node and place $u$ in it. Figure 3 shows a pseudocode.

Alternative Mapping and Fitting Policies. An alternative mapping policy (see [26]) is to define the relative demand as the maximum over the dimensions (as against average), and define the penalty and best node-type analogously:

An alternative to the first-fit policy is the more refined similarity-fit that emulates the best-fit strategy (adapted from a dot-product strategy [25, 12]). It tries to minimize the capacity wastage by selecting the node $b$ (among the feasible nodes) whose remaining capacity is most similar (dot-product shown below) to the demand of $u$.

where ${\tt rem}(b,d|t)$ is the remaining capacity of $b$ along dimension $d$ at timeslot $t$. We can derive cosine similarity via dividing the product by the norms of capacity-normalized demand and remaining capacity vectors involved in the above inner product. Then, the strategy is to place $u$ in the node offering the maximum cosine similarity value.

Time Complexity. Time taken for computing the mapping is $O(n\cdot m)$. Time required to test whether a task fits a node is $O(D\cdot T)$. Given that the number of nodes can be at most $|S|$, the total number of nodes purchased, overall running time of the algorithm is $O(n\cdot m+n\cdot|S|\cdot D\cdot T)$. Typically the last term of this bound dominates in practice.

For the special case of interval coloring ($m=1$, $D=1$), prior work [9] derives an $O(1)$ approximation ratio. Similarly, for the special case of ${\sf Rightsizing}$ ($T=1$), an $O(D)$ approximation ratio is implicit in existing literature [26]. We next present an analysis for the general TL-Rightsizing setting and prove that the PenaltyMap algorithm has an approximation ratio of $O(D\cdot\min(m,T))$. The result matches and generalizes both the prior special cases.

For the sake of concreteness, we focus on the $h_{\rm avg}$-based mapping and the first-fit strategy, but the analysis can easily be adapted to the combinations involving $h_{\rm max}$ and similarity-fit. We say that a task $u$ is small, if for all node-types $B$ and all dimensions $d$, ${\tt dem}(u,d)\leq{\tt cap}(u,B)/2$. We first work under the practically reasonable assumption that all the tasks are small and then discuss the general case.

Let $S_{\rm opt}$ and $S_{\rm pen}$ denote the optimal and PenaltyMap solutions, respectively. We derive a lower-bound on ${\tt cost}(S_{\rm opt})$ and an upper-bound on ${\tt cost}(S_{\rm pen})$, based on the notion of congestion, defined next. Given a subset of tasks $U\subseteq{\cal U}$, define the congestion induced by $U$ as the maxima over the timeline of the aggregate minimum penalties of tasks active at each timeslot:

The following lemma shows that ${\tt cost}({\tt opt})$ is at least the congestion induced by the entire task set ${\cal U}$.

While the penalty based mapping works reasonably well in practice, there are certain deficiencies in the strategy and we design an improved mapping based on linear programming.

We introduced the TL-Rightsizing problem that reduces cluster cost by exploiting the time-limited nature of real-life tasks. We designed a baseline two-phase algorithm with an approximation ratio of $O(D\cdot\min(m,T))$, an improved LP-based mapping strategy and a cross-node-type filling method for further cost reduction. Experiments on synthetic and real-life traces demonstrate that the final algorithm produces solutions within $20\%$ of a lowerbound on the optimal cost. We identify two avenues of fruitful research. First is to further bridge the gap between the lowerbound and the solutions on the hard instances. Secondly, improving the approximation ratio would be of interest from a theoretical perspective. We also intend to work on enhancing the scheduler and auto-scaling algorithms to better leverage the output from TL-Rightsizing