Google's Borg system is a cluster manager that runs hundreds of thousands of jobs, from many thousands of different applications, across a number of clusters each with up to tens of thousands of machines.

One of the key factors in selecting a good scheduling algorithm is using an appropriate metric for comparing schedulers. But which metric should be used when evaluating schedulers for warehouse-scale (cloud) clusters, which have machines of different types and sizes, heterogeneous workloads with dependencies and constraints on task placement, and long-running services that consume a large fraction of the total resources? Traditional scheduler evaluations that focus on metrics such as queuing delay, makespan, and running time fail to capture important behaviors - and ones that rely on workload synthesis and scaling often ignore important factors such as constraints. This paper explains some of the complexities and issues in evaluating warehouse scale schedulers, focusing on what we find to be the single most important aspect in practice: how well they pack long-running services into a cluster. We describe and compare four metrics for evaluating the packing efficiency of schedulers in increasing order of sophistication: aggregate utilization, hole filling, workload inflation and cluster compaction.

It is well-known that SRPT is optimal for minimizing flow time on machines that run one job at a time. However, running one job at a time is a big under-utilization for modern systems where sharing, simultaneous execution, and virtualization-enabled consolidation are a common trend to boost utilization. Such machines, used in modern large data centers and clouds, are powerful enough to run multiple jobs/VMs at a time subject to overall CPU, memory, network, and disk capacity constraints. Motivated by this prominent trend and need, in this work, we give the first scheduling algorithms to minimize weighted flow time on such capacitated machines. To capture the difficulty of the problem, we show that without resource augmentation, no online algorithm can achieve a bounded competitive ratio. We then investigate algorithms with a small resource augmentation in speed and/or capacity. Our first result is a simple (2 + ε)-capacity O(1/ε)-competitive greedy algorithm. Using only speed augmentation, we then obtain a 1.75-speed O(1)-competitive algorithm. Our main technical result is a near-optimal (1 + ε)-speed, (1+ε)-capacity O(1/ε3)-competitive algorithm using a novel combination of knapsacks, densities, job classification into categories, and potential function methods. We show that our results also extend to the multiple unrelated capacitated machines setting.