{'fraction_non_alphanumeric': 0.02951413722404997, 'fraction_numerical': 0.009083106851666429, 'mean_word_length': 4.333375715193897, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Flex: Closing the Gaps between Usage and Allocation

Data centers are giant factories of Internet data and services. Worldwide data centers consume energy and emit emissions more than airline industry. Unfortunately, most of data centers are significantly underutilized. One of the major reasons is the big gaps between the real usage and the provisioned resources because users tend to over-estimate their demand and data center operators often rely on users' requests for resource allocation. In this paper, we first conduct an in-depth analysis of a Google cluster trace to unveil the root causes for low utilization and highlight the great potential to improve it. We then developed an online resource manager Flex to maximize the cluster utilization while satisfying the Quality of Service (QoS). Large-scale evaluations based on real-world traces show that Flex admits up to 1.74x more requests and 1.6x higher utilization compared to tradition schedulers while maintaining the QoS.


Introduction
Data centers are becoming the factories of Internet data and services. There are millions of data centers in the world serving the digital demand from personal and industrial users, bringing great changes to our society. This comes at the cost of significant electricity consumption and environmental impacts. In total, data centers worldwide consume more than 3 percent of the world electricity and emit 2 percent of the global emissions. This is more than the airline industry [2]. While great advancements have been made regarding data center cooling and renewalble integration, it is critical to make full use of the costly data centers.
Unfortunately, data centers are inefficient in terms of both energy consumption and operation. Many data centers do not adopt the latest technologies. For instance, new CPUs can provide more computational power while using less electricity than previous generations. This is important as small and medium size data centers with old technologies are responsible for 49% of server electricity consumption in the United States [12]. Moreover, servers are reported to have as low utilization as 12% to 18% of their capacities [12]. One of the major reasons is that users often request more than they need [9]. One the other hand, data center operators oftentimes do not risk their business by allocating resources less than users' requests.
Existing cluster resource managers like Yarn [28] and Kubernetes [4] allocate resources based on users' requests. Since users rarely know their exact resource consumption when submitting their requests, the requested amount can be more or less than the real usage. In fact, our analysis of the Google cluster trace [3] show that the real usage is less than 45% the requested amount on average. Our trace analysis in §2.2 further highlights the great potential to increase cluster efficiency.
Due to the utmost importance of the problem, it is not surprising to see lots of efforts have been made to mitigate the gaps between resource usage and requested amount. In particular, oversubscription has been widely used in Yarn [28], Mesos [16], Aurora [1]. Specifically, overscription assumes demand peaks of different users are rarely collided and thus multiplexing negatively correlated applications on the same server can accommodate more requests and therefore help improve utilization [20]. Despite the benefits, server overloading may occur which results in performance degradation. Another popular approach is to fill the cluster with low-priority jobs, which is used in resource managers such as Kubernetes and Borg [4,24,29]. However, using multiple priorities is not a universal solution to all data centers, and it is often chanllenging to find enough low-priority jobs to fill in the cluster. Moreover, low-priority jobs may imply low value. Therefore, it is desirable to accommodate as many high-priority jobs as possible before using low-priority jobs to increase the utilization.
In this paper, we focus on improving the cluster utilization while maintaining the quality of service (QoS). Specifically, given a QoS target, we developed an online resource manager to maximize the cluster utilization while satisfying the QoS target. Our contributions are summarized as follows.
• In-depth Google trace analysis. We analyze 42 GB compressed data of a 29-day Google cluster trace to figure out why the cluster is underutilized. At the cluster level, the total average usage is 50% of the total capacity. At the server level, the utilization level varies significantly across servers. At the task level, users often overestimate their demand. Since the resource manager [29] in Google Cluster relies only on the requested amount for resource allocation and scheduling, it results in load imbalance and low utilization. • Solution approach. Unlike traditional scheduling problems, we formulate a load balancing problem that does not completely rely on requests. It additionally takes the real-time usage of each node into consideration. However, the usage of a node is uncertain and it is hard to have a perfect estimator or predictor. In the solution approach, we proposed an online load balancing algorithm Flex that learns from estimation errors and automatically self-adjusts to maintain the QoS above a given target. • Google trace based evaluation. We carry out the evaluation using a Kubernetes simulator on Google cluster trace. The evaluation shows that Flex increases the utilization by up to 1.6× and admits up to 1.74× more requests while maintains the QoS. Flex balances the load accross servers in the cluster and the utilization improvement is significant across a wide range of configurations.  [28], Aurora [1], Mesos [16], Spark [33], Kubernetes [4], etc. Based on resource requests from a task, the scheduler decides which server the task will be launched on.
Resource requests are commonly decided by users. Users estimate or randomly pick the resource requests. Hence, the resource requests can be more or less than the resource demands. Request vs. Demand. There are several reasons that existing task schedulers do not use resource demand for scheduling. One of the major reasons is that task demand is unknown beforehand. People may want to pick the maximum demand as resource request. Since demand happens in the future, precise predictions can be very challenging. For example, it is not easy to predict the number of users will use on a website before lauching a webserver. Another reason is performance guarantee. Schedulers can guarantee resources based on request but it is hard to guarantee resources based on demand because demand changes over time and resource preemption is expensive. Schedulers just ensure that the task receives enough resources that it requested.
Resource request as maximum limit. Some resource managers treat resource requests as maximum limit. Users can enable Yarn [28] and Mesos [16] to isolate resources using Cgroups [19]. For example, if an application reaches its limits, the exceeding demand of resources will be throttled. Fair schedulers like Yarn [28] and Mesos [16] prefer to use this because it can guarantee fairness among applications and users. However, it may under-utilize the nodes and it limits the performance of some applications.
Resource request as minimum guarantee. To improve the utilization and performance of clusters, Kubernetes treats requests as a minimum guarantee. Basically, an application can use more than resource requests if there are available resources in its allocated machine. When that application uses up too much resources, it leaves no free resource for other applications.
Less dependent on resource requests. Serverless compute platforms like AWS Lambda allow us to run tasks/applications without provisioning or managing servers. It reduces the overheads of server management and job configuration. In serverless computing, it relies less on all resource requests for function-level cloud computing. For example, the AWS Lambda framework requires only memory requests then it deicides other requests itself. AWS Lambda implicitly relies on resource requests that needs to deal with the same problem of using the requests.
In summary, We belive that future schedulers should not rely on requests because they are not the actual demand.

Google Trace Analysis
We analyze the Google cluster trace [3] to show that there is room for utilization improvement. We do analysis from the highest level (cluster level) to the lowest level (task level) to study the inefficiency of the Google cluster in details.
Google cluster trace [3] was collected in May 2011. The length of the trace is 29 days. Borg [29] is the cluster resource manager for the Google cluster. There are around 12500 servers and 25 million tasks. Most of tasks have both resource request and resource usage. We do not know exactly how many CPU cores or GB RAM that tasks have used because resource usages and requests are normalized to the node that has the largest capacity. Resource usage is randomly sampled from 5-minute usage.
Cluster. Figure 1 plots the total usage and request of the cluster. The usage and request are normalized to the capacity of the whole cluster. Both the total requests of CPU and memory are larger than the capacity sometime that means the cluster was over-subscripted. The average total request for CPU is 1.1 while the average total request for memory is 0.9. Memory is sensitive to applications so it is less over-subscripted than CPU. The average usage of CPU (0.43) and memory (0.5) are far under from their capacities 1. However, we believe that the total CPU and memory usages is not the complete proof to the inefficiency of the cluster. So, we need to look into the details of usage and request at machine level.      Machine. Figure 2 plots the CPU and memory usage on four machines. Machine 1 has the high load while Machine 2's load is low. This is not encouraged because the load is not evenly balanced among the servers. Machine 4 has much greater memory usage than CPU usage but it is opposite to Machine 1. When one of resources becomes the bottleneck on a server, we cannot allocate any more tasks to that server.
In Figure 3, we plot the cumulative density function (CDF) of the usage to request ratios and the usage to capacity ratios at machine level. Figure 3a shows that more than 50% resources are wasted in roughly 70% of time. More interestingly, resources are not used at all in 50% of time. In Figure 3b, the ratio of CPU usage to request is greater than 1, meaning the usage can be actually larger than the request. Some tasks (e.g. low priority tasks) must have increased their demand when machines have resource available.  Task. Figure 4 shows the analysis on tasks. Interestingly, the mean CPU usage can be much greater than its request while memory usages often stay under their requests (Figure 4a). In the traces, the tasks with usage more than request are usually the low-priority tasks. These tasks are submitted with small requests so they can easilly fit the remaining resources in the nodes. When nodes have more idle resources, Borg [29] allocates resources to the tasks in the best-effort manner so the resource usages go beyond their requests. The peaks of resource usage can be very high compared to the resource requests ( Figure 4b). In Figure 4c, we plot the CDF of the usage standard deviation (std) of task usage normalized to its mean. Both CPU and memory have a lot of variations. Although maximum CPU usages are sometime much larger than requests, the standard deviation shows that memory and CPU usages have similar variations.
We classify the tasks into batch jobs, production, and system based on priorities and do analysis on resource usage in Figure 5. The system tasks have the highest priorities. The batch jobs have the lowest priorities. On average, most of tasks use less resource than their requests like Figure 5(a) and (b). In terms of maximum usage, the system tasks can use much more resource than their requests like Figure 5 (c) and (d). The maximum usages of production tasks are mostly much smaller than their requests. While the memory usages of batch jobs are stable, their cpu usages are more aggressive.

Motivation
Request based scheduling. Many modern schedulers like Yarn [28], Mesos [16], Aurora [1], and Kubernetes [4] are based on requests. They often schedule tasks using First Fit or Least Fit. First Fit focuses on speeding up scheduling instead of improving utilization or performance. It just picks the first node satisfying the resource constraints. Meanwhile, Least Fit places the task on the node with the least requested resource. Since First Fit and Least Fit naively rely  the resource requests, they cannot reduce the gaps between resource usage and resource allocation.
From the Google trace analsis §2.2, we could see that the resource usage is far to their capacity. The major reason behind this is that the resource requests are often more than their resource usage.
Oversubscription. Cluster managers have used oversubscription to admit more requests by overclaiming the cluster capacity. Meaning, oversubscription tries to compensate the over-request. In the Google cluster trace, the ratios of demand to request can be distinct as our analysis. Oversubscription causes overloads on some nodes The vector of the resource demand from task j r j The resource request from task j s j Fair-share of remaining resource for task j x i j Placement decision to place task j on node i q j (t) Quality of service for task j at time t ρ j Quality of service target for task j Q(t) Quality of service for the whole cluster at time t ρ Quality of service target for the whole cluster P Estimation penalty α, β Estimation penalty update constants that have major of tasks with the ratios of usage to request close to or more than 1. Hence, this solution cannot give much improvement. We also observe in the Google traces [3] that people have used oversubsciption as well as best-effort scheduling to increase the utilization.
Overload detection and mitigation. There have been several efforts on virtual machine allocation that deal with overloads [6,22]. These approaches detect the hot physical nodes and try to move the virtual machines out. They work well with virtual machines because virtual machines can be live migrated. The migration overheads are relatively small compared to the life of virtual machines. However, this approach is not applicable to all tasks because migration often comes with large overheads. Schedulers like Yarn [28] and Kubernetes [4] do not support migration. Instead, they preempt the tasks and restart them somewhere else.
Problem statement. Given the requests with unknown future demand, how to maximize the utilization of a clusters while maintain the QoS target?

Problem Formulation
In this section, we formulate a scheduling problem for a cluster of nodes (servers). Given the number of nodes, the task scheduler tries to admit as many tasks as possible. To get the best performance, a scheduler often spreads the workload to all the nodes.
Cluster. There are N nodes in a cluster. We assume that all nodes have the same capacity C. It is straightforward to convert to a general problem with heterogeneous nodes. We can add pseudo load to the small nodes until their capacities equal to the maximum one. The total of requested resources on node i is R i . R i can be greater than C if the cluster is over-subscripted with the factor θ ≥ 1.
Meanwhile, the real load (usage) of node i at time t is L i . For the simplicity of presentation, we ignore the time t in notations. The real load L i is bounded by C.
Tasks. At time t, there are J pending tasks. Task j has the constant request r j and the future demand ì d j . The demand ì d j is unknown prior scheduling. ì d j varies from the time task j scheduled till finished. Resource allocation. As the resource allocation process happens after scheduling done, we do not go too much details on resource allocation formulation. We only consider the allocation for quality of service. Given demand d j and request r j , the resource allocation for task j at time t is r j + s j . s j is commonly a fair share (FS) or weighted fair share (WFS) of the remaining available resource. In this paper, we choose weighted fair share (WFS) as a computer often does weighted fair share for its running applications. s j can be negative when the real demand is less than its request. There are three cases. If the total demand on a node is less than or equal to the capacity, the resource allocation of each task is equal to its demand. If the total demand is greater than the capacity and the total request is less than the capacity, the allocator guarantees resources for all tasks based on their requests first and then splits remaining resources to all tasks using WFS. For example, if a task requests 5 CPU cores but demands 6 CPU cores, it receives 5 CPU cores as guaranteed and extra s j CPU cores using WFS. If the total demand and the total request are both greater than capacity, the allocator uses weighted fair share twice. It does WFS based on resource requests first, then does WFS again based on remained resource demand.
Placement. Let x i j be the decision variable for scheduling task j on node i. If the scheduler decides to place task j on node i, Request based load balancing (RLB)). Existing schedulers do the load balancing based on resource requests. It minimizes the total request on each node. We abstract the traditional load balancing optimization as follows.
i ∈N where x is the matrix representing for Clearly, RLB is inefficient because it uses only resource requests. As in our trace analysis §2.2, there are big gaps between resource usage and resource request that causes low utilization. If we increase the oversubscription factor θ to bridge the gaps, some of the nodes will be easily overloaded. We suggest not completely relying on resource requests and propose a load balancing based on node usage instead.
Node Usage based Load Balancing (ULB). The goal is to balance the actual load across all the nodes. Meaning, we minimize the maximum utilization U .
i ∈N whereL i is the load information on node i. As the future demand is unknown, we still use the request r j in the capacity constraint U ≥L i + j ∈J x i j r j . We note thatL i is not the instantenous load L i .L i should not be simply measured because the load may change overtime and the online optimization problem only captures a single snapshot. IfL i is too small, we can admit a lot of tasks to the same node but it will result in overloads. IfL i is too large, it causes low utilization. The key question here is to where to getL i before scheduling.
Load Estimation Penalty. In practice, load can be monitored, estimated, or predicted. We assume thatL i is an estimated load of node i at time t. However, we cannot just relyL i because we do not know how wellL i serves in U LB. To deal with underestimation or overestimation, we propose using estimation penalty P. The idea is to computeL i based on the estimated loadL i and the estimation penalty P as follows.
WhileL i gives us some information about the present and future load, we need to adjust the estimation penalty P to avoid quality of service (QoS) violations. If P is too large, U LB provides guaranteed QoS and low utilization. If P is too small, U LB achieves high utilization but violates QoS.
Quality of Service (QoS). Let q j be the QoS of job j at time t. q j = f (r j , d j , a j ) is defined based real resource usage (allocated) a j and the resource demand d j at time t. q j is non-decreasing on a j . Users requires q j greater or equal to the task quality target ρ j . QoS Q of the system at time t is computed as follows.
where I is the indicator function.
Challenges. U LB is an integer programming problem and well known as the NP complete problem. It is impossible to find a optimal solution for for scheduling as it needs to be done in subsecond for thousands of nodes and millilons of tasks. So, it requires an efficient and fast algorithm. Furthermore, we need to pick the estimation penalty P before solving U LB. Since we do not have prior-knowledge of task arrival times and task demands in the future, it is challenging to pick the right estimation penalty P.

Solution Approach
We break the solution approach into 2 phases: The first one in §4.1 assumes that load estimation is very accurate so we only focus on load balancing. In the second phase, we deal with the errors from load estimation. We combine the two phases in the proposed algorithm. The proposed online algorithm is compatiable with most task schedulers like Kubernetes [4], Aurora [1], or Yarn [28].

Load Balancing with Precise Load Estimation
We assume that the load of a node i is L i and it does not change until a new task lands in. The load balancing now is similar to the problem of parallel machine scheduling (PMS) problem [14]. PMS schedules a list of jobs into multiple identical machines to minimize the makespan. There are 3 key differences between our load balancing problem and PMS. First, our load balancing problem allows multiple tasks to run on a machine at the same time while PMS put tasks sequentially on a machine. Second, PMS minimizes the makespan while our problem minimizes the maximum load across the cluster. Third, PMS knows processing times but demand is uncertain in our problem. Since the load balancing is well known as an NP-complete problem, we are looking for an efficient online algorithm instead of optimal solutions.
When tasks arrive, they are queued up. Some schedulers like Kubernetes [4] prefer to do the scheduling whenever there is any task in the queue. Other task schedulers like Yarn [28] periodically do scheduling for the tasks on the queue.
FIFO Scheduler. FIFO Scheduler visits each task in a first-infirst-out manner and picks the node with lowest load for that task. In practice, we cannot monitor load in a real-time manner because frequent monitoring creates large overheads on the whole system. Since users often over-request their resource demand, we use their requests r j in capacity constraintsL i + r j ≤ C. Algorithm 1 FIFO Scheduler 1: function FIFOSCHEDULER(J tasks, N nodes) 2: x i j = 0 ∀i, j 3: for all task j in J do 4:î = arg min i L i

5:
ifL i + r j ≤ C then  PROOF. Let j is the last task with demand d j scheduled on node i. Prior to scheduling, node i has the lowest load L i − d j . We have the optimal load is L * ≥ L i − d j and d j ≤ L * . Hence, L i − d j + d j ≤ L * + L * = 2L * . In the worst case, FIFO produces no more than 2× the optimal solution. □ Largest Request First (LRF) Scheduler. The issue of FIFO Scheduler is not considering the size of pend tasks. If tasks can be ordered, we can match the node with the lowest usage with the task with the largest demand. Since resource demand is unknown, we use resource requests to order the tasks. We propose the largest request first (LRF) Scheduler in Algorithm 2.
Algorithm 2 sorts the pending tasks based on resource requests in the descending order. Then, it finds the node with the lowest load sort J tasks such that r 0 ≥ r 1 ≥ · · · ≥ r J . 3: x i j = 0 ∀i, j 4: for all job j in J do 5:î = arg min i L i

6:
ifL i + r j ≤ C then Return {x i j } 11: end function for each task. By this way, the task with the largest request is sent to the node with the lowest usage.
The computational complexity of LRF is O(Jloд(J )) or O(J N ). If there are too many pending tasks, LRF may be not efficient. Theorem 4.2 shows that LRF Scheduler achieves 4/3 of the optimal solution if the order of task requests is the same as the order of task demands. Meaning, it can achieve at least 75% of the optimal utilization. THEOREM 4.2. If the capacity C is infinite and the order of resource requests is the same order of resource demands, LRF scheduling is 4/3-approximation.
PROOF. Let us order j tasks such that their demands d 1 ≥ d 2 ≥ · · · ≥ d j . We can assume j causes the highest load L i + d j . If not, we keep removing j from the set until we find one. The removal does not change the solution of the algorithm but it decreases the optimal solution L * . Since the bound holds for the assumed case, it applies to other cases with larger L * . So the highest load is computed as Now we need to prove that either d j ≤ L * 3 or L i +d j is the optimal solution when d j > L * 3 . If d j ≤ L * 3 , the bound is clearly held. We use contradiction to prove the other case. We assume that d j > L * 3 and L i + d j is not the optimal solution. Assume task l is the first task that makes the load on node k greater than optimal, L k + d l > L * . We only consider the schedule for tasks from 1 to l − 1. There is at least one task on each node. d j is the smallest task, and d j > L * 3 so there are at most two tasks on each node. Assume that the algorithm schedules one task to m nodes and two tasks to N −m nodes. Clearly, let us call tasks on one-task nodes large tasks and tasks on two-task nodes small tasks. Task l cannot be scheduled with a large task because it would create a new load greater than the optimal solution. As task l is the smaller than other scheduled tasks, no small or large tasks can be scheduled with a large task. To not violate the optimal solution, m nodes schedule m large tasks while N −m nodes schedule 2(N − m) + 1 small tasks. This is impossible because each node has at most 2 tasks. So, if d j > L * 3 and L i + d j is the optimal solution. In summary, the solution is bound by 4 3 L * . □ Discussion. In the case of "task by task" online scheduling, LRF Scheduler behaves like FIFO Scheduler because there is only a single task for each scheduling. If there are multiple tasks in the queue, LRF Scheduler is expected to offer better utilization than FIFO Scheduler. However, LRF relies on the assumption that the order of requests is consistent with the order of demands.

Dealing with Estimation Errors
In practice, the current load L i of node i can be monitored but it is not very useful due to many two reasons. The first reason is that load may quickly change in the future. The second reason is that it is too expensive to monitor the load frequently. Since there are no perfect predictors or estimators, errors are unavoidable. When the load is underestimated, FIFO Scheduler or LRF Scheduler admit too many tasks into a node. Overload can be a fatal issue. For example, operation systems kill some of services if the memory is overloaded. In constrast, overestimation causes low utilization.
Instead of relying on the accuracy, we focus on how to deal with estimation errors. Estimation errors are unpredictable. An estimator works well on this workload but it may not work well on another workload. It is hard to know which error level the system can tolerate. The best error level at this time may not work at another time slot because the demands and systems are both dynamic.
Given any estimator, how to incorporate it into our solution approach? The idea is to adjust the estimation penalty P. We can pick the lower bound for P to prevent it from being too small P > P min . We do not adjust P according to estimation errors. It is because present errors are not very useful while the future errors are uncertain. Furthermore, small errors at a node do not mean that the estimator works well for another node. Instead, we learn from the QoS of the whole cluster. If the QoS is violated, it is a signal that the scheduler have to be less agressive.
We borrow this idea from the congestion control mechanisms in computer networks for controlling the estimation penalty P. The idea of updating rule for P is as follows. We keep monitoring the QoS of the whole system. If QoS is violated, we quickly reset P back to a larger penalty P = P + β(P − P min ) where β is positive. So, it stops the aggressiveness of admitting more tasks quickly. If QoS is acceptable, we keep reducing the penalty P = αP gradually where α ∈ (0, 1). §4.3 presents more details how we design the updating rule for online task schedulers.

Online Algorithm Design
We designed Flex algorithm for schedulers like Kubernetes [4]. When a user submit his tasks, they will be queued up in the queue. If there is a task in the task queue, it is immediately popped out for scheduling. If the task cannot be scheduled, Kubernetes scheduler sets the back-off time for scheduling retry.
In practice, there are multiple resources. For the sake of presentation simplicity, we considered only single resource scheduling in the problem formulation §3. It is straighforward to convert single resource scheduling to multiple resource scheduling. First, contraints have to be met for each resource dimension. For scheduling rules that cannot apply to all resource dimensions, we can pick one of the dimension instead. For instance, we can sort the tasks based on only memory request or the dominant resource.
We present pseudo code of Flex algorithm in Algorithm 3. OnJo-bArrival function processes the new arrival tasks. ScheduleOne is used in Kuberntes for scheduling tasks one by one from the pending queue. The scheduler runs PeriodicEstimationPenaltyUpdate periodically to update the estimation penalty P.
OnJobArrival function puts a new task into the pending queue. We can choose using FIFO or PriorityQueue. If we use FIFO queue, the algorithm is based on the FIFO Scheduler as in Algorithm 1. If we use PriorityQueue, the algorithm works like LRF Scheduler in Algorithm 2. Basically, we have two versions of Flex: FlexF (FIFO) and FlexL (LRF). FlexF does not order the tasks while FlexL uses the priority queue to order the tasks from the largest memory request to the smallest request.
If there is a task pending in the queue, the scheduler invokes ScheduleOne. It takes the first task from the queue. ScheduleOne filters out all the nodes that does not meet the capacity constraint PL i + r 0 ≤ C. If there are more than one nodes remaining, it scores each node. The rule is based on the load and the running tasks in each node. The rule prefers the node with low load. It also prefers the node with fewer tasks from the same source as the new task. It is because the tasks from the same source would more likely have peaks at the same time. To increase the speed of scheduling, we implement the filtering and scoring functions in a parallel manner. The parrallel implementation can speed up the algorithm p times. p depends on the computational power of the scheduler computing unit (e.g. CPUs or GPUs). Finally, ScheduleOne places the new task to the node with the highest score.
If we cannot find any node for the new task, the scheduler puts the task in the end of the queue or reports the failure error to the task owner.
Given the QoS targer ρ, PeriodicEstimationPenaltyUpdate periodically updates the estimation penalty P. When QoS is greater than ρ, it keeps reducing P = Pα gradually where α < 1. The value of α depends on how frequent we update P. If the updating period is very short, α has to be closer to 1. P is lower-bound by P min to avoid some special cases. For example, there are no new tasks in the queue so QoS keeps being great. Furthermore, it prevents underestimation from happening. We can pick P min > 1 if we expect that the estimator would not overestimate the load too much. When QoS is less than the target ρ and keeps decreasing, it is urgent to stop the aggressiveness of Flex. There are many ways to do this. For instance, it quickly increases: P = P + β(P − 1) where β is a constant greater than 0 and P min > 1. When β = 1, it doubles the overestimation, P = 1 + 2(P − 1).
The computational complexity of Flex algorithm: O(N /p) where N is the number of nodes and p is the number of parralel threads using in filtering and scoring.

Evaluation
In this section, we evaluate Flex using Google cluster trace [3] to show that it is better than existing modern schedulers in terms of utilization while maintains the QoS target.

Setup
Simulator. We extend Kubernetes Cluster Simulator [5] that is very close to the real Kubernetes code base. The simulator was designed to test customized schedulers before trying on the real Kubernetes cluster. Since the simulator APIs are shared with Kubernetes, developers can develop their own schedulers, plug it into the simulator for testing.
Configuration. There are 4000 nodes. Each node has 64 CPU cores and 128 GB RAM. We vary the number of nodes from 3000 to 4000 in the sensitivity analysis.
Workload trace. We submit tasks to the simulated cluster using the task requests and usages from Google Cluster Trace [3]. We submit around 714, 030 tasks within 24 hours to the simulator. Since Filter nodes: list nodes that meets capacity: PL i + r 0 ≤ C 8: if There are more than 1 filtered nodes then 9: Score nodes: based on load estimation and their current running tasks. 10: Pick node i with the highest score. Dequeue task 0 11: Dequeue task 0.

12:
Place task 0 on node i. 13: end if 14: if task 0 cannot be scheduled then 15: Dequeue task 0 and add back to the end of the queue. 16 if Q(t) > ρ then 21: Reduce penalty: P = max(Pα, P min ) 22: else if Q(t) < ρ and Q(t) < Q(t − 1) then 23: Increase penalty: P = P + β(P − 1) 24: end if 25: end function real demand of tasks are not available, we use their usage samples as resource demand.
• LeastFit allocates the job j to the node i in an online manner such that it minimizes the maximum of requested resources across the nodes. LeastFit are featured in Kubernetes [4] and Aurora [1]. • Oversub combines oversubscription and LeastFit. The oversubscription factor is 2 and does load balancing like LeastFit does. Most of modern resource managers like Yarn [28] and Mesos [16] support oversubscription. • FlexF and FlexL are the two versions of the proposed algorithm 3. FlexF uses FIFO queue while FlexL uses Priority Queue to prioritize the tasks with larger memory requests first. They start with prediction penalty P = 1.5, P min = 1.
Quality of Service (QoS). We assume that users require a j ≥ d j or a j ≥ r j for each job. If one of aforementioned conditions satisfied at time t, q j (t) = 1. The QoS of the cluster is Q(t) ≥ 0.99.
Estimator. We use a simple load estimator in this evaluation. We assume that the future demand does not change much. Meaning, we monitor and use the current resource usage for scheduling. We show that our proposed algorithm works well even with this simple estimator.
Metrics. We use resource utilization and QoS as the main metrics for the evaluation.

Resource Utilization
To evaluate the resource utilization of four methods, we compute the request and usage of the whole cluster. They are normalized to the total cluster capacity. While request represents for the amount of workload the cluster handles, usage is the actual utilization of the cluster. Figure 6 plots the requestÂȃand usage of the four methods. FlexF and FlexL admit the most requests and are similar to the Oversub with oversubscripting 2× of the cluster capacity. Since they admit more 74% than LeastFit, FlexF, and FlexL handle more demand and increase the utilization of cluster up to 1.6×.

Quality of Service (QoS)
To evaluate the Quality of Service (QoS), we plot the cumulative density function (cdf) of QoS over time and the percentage of QoS violations in Figure 7. In Figure 7a, FlexF and FlexL are better than Oversub although they have the same utilization. Clearly, LeastFit has the least utilization but it is the best in terms of QoS because it does not over-admit requests. Figure 7b shows the average percentage of QoS violations. Both FlexF and FlexL are 3.7× better than Oversub.

Estimation Penalty
To understand why FlexF and FlexL are better than Oversub in terms of QoS, we plot the QoS and the estimation penalties over time in Figure 8. The QoS of Oversub suffers from large drops but cannot quickly recover. Meanwhile, the QoS of FlexF and FlexL also have some drops but they quickly recover to maintain the QoS target. The changes of estimation penalty explain this. For example, when there is a QoS is less than target (99%) at around 1 hour, the estimation penalty immediately goes up to stop the aggressiveness of admitting more requests. It stops making QoS worse and waits until QoS is better.

Load Balancing
To evaluate how well FlexF and FlexL do load balancing, we compute the standard deviation (std) of memory usage across nodes over time in Figure 9. The standard deviation is normalized to the usage mean. Small standard deviations mean the load are spread well to all nodes. The standard deviations FlexF and FlexL are less than standard deviations of LeastFit and Oversub. Meaning, FlexF and FlexL maintains the best load balance among the four methods.
Oversub is the worst because it admits more requests into a node than LeastFit.

Sensitivity Analysis
In this section, we carry out the sensitivity analysis on cluster size and the ratios of demand to request, Cluster size. To study the impact of low load or high load on utilization and QoS, we vary the cluster size from 3000 to 4000 nodes. Figure 10 shows that the utilization of both FlexF and FlexL work well and similar to Oversub. In terms of QoS, Oversub is the one suffering the most at the small cluster size (3000). Under high load, Oversub tries to pack more tasks into nodes than it can handle so overloads more often. Both proposed algorithms do not suffer much from the change of cluster size. FlexF is better than FlexL because FlexL prefer tasks with larger requests which have larger variations in demand.
Ratios of demand to request. To study the impact of ratios of demand to request on performance, we scale up and down the demand but do not change the request in Figure 11. The goal is to simulate the cases that users estimate their requests differently. Since Oversub does not consider the real demand, it suffers the most from the QoS violation when we scale up the demand (1.5). In contrast, FlexF and FlexL are less aggressive on admitting more requests when the demand scale is high. Meaning, FlexF and FlexL are less dependent on the ratios of demand to request. Hence, FlexF and FlexL still maintain the small percentages of QoS violation.

Related Work
Request based Schedulers. Existing schedulers in Yarn [28], Mesos [16], and Kubernetes [4] rely on resource requests for scheduling. As in the Google trace [3], requests are often overestimated that leads to low utilization. Supprisingly, most of modern schedulers like DRF [13], Carbyne [15], HUG [10], a nd BoPF [17] still rely on requests. Some other systems like AlloX [18] estimate the requested resource themselves. However, estimating resource usage is still very challenging to apply to all types of workloads.
Multiple priorities. Data centers classify workload into multiple priorities. The goal is to not only guarantee resources but also improve the utilization of the whole cluster. Schedulers treat the low priority and long tasks like analytics in a best-effort manner. For example, Kubernetes [4] or Borg [29] can allocate more resource than requests to tasks when the nodes have free resources. To utilize the idle resource, Rose [24] consolidates the low utilization machines with low priority workload like speculative tasks.
Oversubscription was proposed to deal with over-estimate use of resources [7,26,30]. Clusters can take more virtual resources than the physical resources. These approaches assume that applications can tolerate some degrees of oversubscription so a node can be allocated with more requests. Oversubscription may cause the overload on some nodes and fail to provide performance guarantee.  Multiplexing. Multiple VMs can be multiplexed in the same physical machine when their usage peaks do not collide [8,20,21,25]. The idea is to pick the best set of VMs with negative correlation of resource usages to be placed in the same physical machine. However, this requires statistic knowledge of the VM resource usage which is commonly unknown. It is even harder for acquiring the resource usage of computing tasks ahead.
Overload detection. There are many techniques dealing with overloads in virtual machine allocation. Since the resource usage of VMs are uncertain, overload detection and mitigation are commonly used in VM oversubscription [6,22]. Detecting overload is based on monitoring and predicting. Wood proposed Black-box detects hotspot by using thresholds and Gray-box predict hotspots by linear regression [31]. Similarly other prediction methods are used like exponentially weighted moving average (EWMA) [32]. CloudScale [23] assumes the resource usages of applications in a VM is known so it can predict the overload can happen.
Overload mitigation. Overload mitigation can be done by shutting down VMs or live migration. Shutting down VMs is expensive for old VMs while live migration is more acceptable because VMs live a long time [11,27]. The live migration overhead could be large if they use a lot of disk and memory. If the VMs use network drives, the overhead is much smaller. Although there have been several efforts on overload mitigation, it is still not applicable for all workloads such as short tasks.

Conclusion
In this paper, we developed an online resource manager Flex to maximize the cluster utilization while maintaining the QoS. Our Google trace analysis shows that the Google cluster has low utilization although the cluster is already oversubcripted. Instead of relying on users' requests, we formulate an online scheduling problem based on load estimation and developed Flex that combines both load balancing and feedback control. Google trace driven evaluations show that Flex achieves significantly higher resource utilization compared to conventional schedulers while maintaining the QoS.