Generalized Cost-Based Job Scheduling in Very Large Heterogeneous Cluster Systems
Generalized Cost-Based Job Scheduling in Very Large Heterogeneous Cluster Systems
复制标题
超大异构集群系统中基于成本的广义作业调度
DOI：
10.1109/tpds.2020.2997771
复制
发表时间：
2020-05
影响因子：
5.3
通讯作者：
Wasiur R. KhudaBukhsh;Sounak Kar;Bastian Alt;Amr Rizk;H. Koeppl
中科院分区：
文献类型：
--
作者：
Wasiur R. KhudaBukhsh;Sounak Kar;Bastian Alt;Amr Rizk;H. Koeppl
我们研究了具有有限缓冲区的大型异构资源共享服务器集群中的作业分配。这种负载平衡问题在当今的通信和大数据系统中自然出现，例如Amazon Web Services、Network Service Function Chains和Stream Processing。到达的作业按照优化性能标准（如作业完成时间）的负载平衡策略分派到服务器。我们的贡献是一个随机的基于成本的调度（CBS）策略，其中的作业分配是由服务器队列长度的一般成本函数驱动的。除了现有的模式（如加入最短队列（JSQ）、$d$d或SQ（$d$d）的力量和容量加权JSQ）之外，CBS的概念还产生了新的特定于应用程序的策略，如混合本地统一JSQ。由于今天的数据中心集群有数千台服务器，因此对CBS策略进行精确分析非常繁琐。在本文中，我们推导了服务器数量增加时的扩展限制，便于比较各种CBS策略的瞬态和稳态行为。我们的推导的一个副产品是队列填充比例和服务器缓冲区大小之间的关系，这不能从无限缓冲区模型中得到。最后，我们提供了广泛的数值评估，并讨论了包括多级系统在内的几种应用。
We study job assignment in large, heterogeneous resource-sharing clusters of servers with finite buffers. This load balancing problem arises naturally in today's communication and big data systems, such as Amazon Web Services, Network Service Function Chains, and Stream Processing. Arriving jobs are dispatched to a server, following a load balancing policy that optimizes a performance criterion such as job completion time. Our contribution is a randomized Cost-Based Scheduling (CBS) policy in which the job assignment is driven by general cost functions of the server queue lengths. Beyond existing schemes, such as the Join the Shortest Queue (JSQ), the power of $d$d or the SQ($d$d) and the capacity-weighted JSQ, the notion of CBS yields new application-specific policies such as hybrid locally uniform JSQ. As today's data center clusters have thousands of servers, exact analysis of CBS policies is tedious. In this article, we derive a scaling limit when the number of servers grows large, facilitating a comparison of various CBS policies with respect to their transient as well as steady state behavior. A byproduct of our derivations is the relationship between the queue filling proportions and the server buffer sizes, which cannot be obtained from infinite buffer models. Finally, we provide extensive numerical evaluations and discuss several applications including multi-stage systems.