Algorithmic Support for Massive Scale Distributed Systems

大规模分布式系统中的资源调度是需求与供应匹配的过程。需求与执行工作负载的资源请求相关联，例如作业、任务和应用程序。分布式计算系统中的典型资源包括数据中心集群内的服务器。调度器的目标是实现几个目标，例如最大化系统吞吐量、最小化响应时间、优化能量使用等。这些目标可能冲突(例如吞吐量与延迟)，调度器需要根据用户的需求和目标做出适当的折衷。在具有数十万个分布式服务器的数据中心系统中，其巨大规模的特征是导致系统复杂性的许多因素：-集群中的服务器节点的数量、资源之间的互连和资源的异质性(不同类型的CPU、存储器、本地存储)；-系统中并发作业的数量和到达率；-作业的异构性(对CPU、内存和本地存储的不同要求；不同的资源使用模式，长时间运行的作业与短时间运行的作业；紧急作业与截止日期较短的作业)。对系统的关键要求是其可扩展性-系统能够维持所需的吞吐量水平(例如每秒操作)，同时将感知响应延迟限制在类似于中小型系统的水平。在我们的项目中，我们的目标是解决以下挑战：(A)规模化调度(快速做出快速调度决策)；(B)规模化资源利用(在保持高服务质量的同时提高资源利用率)；(C)规模化服务质量提供(以满足不同工作负载的需求)。为实际系统开发的现有调度算法通常主要基于经验知识、经验和最佳努力来设计。由于缺乏理论基础，这些算法的性能并不总是能得到保证。另一方面，理论界提出的调度算法通常基于过于简化的抽象系统模型。由于系统模型不能反映实际系统的实际复杂性，即使对系统模型进行微小的调整，使算法不再适用，因此理论上可靠的算法在保证精度和时间复杂性的情况下往往是不切实际的。在我们的项目中，理论和应用专家将联合努力进行跨学科研究，克服单独研究的缺点。总体而言，我们的项目是方法论驱动的，试图扩展最强大的数学优化技术的适用性；2)应用驱动，其中大规模分布式系统的挑战引发了调度方法的新发展；以及3)实践驱动，其中研究方向基于分布式系统专家的实践经验。

Resource scheduling in massive-scale distributed systems is the process of matching demand with supply. Demand is associated with requests for resources to execute workloads, such as jobs, tasks and applications. Typical resources in a distributed computing system include servers within a data centre cluster. A scheduler aims to achieve several goals, for example, to maximise system throughput, to minimise response time, to optimise energy usage, etc. These goals may conflict (e.g. throughput versus latency), and the scheduler needs to make a suitable compromise, depending on the user's needs and objectives.In a data centre system with hundreds of thousands of distributed servers, its massive scale is characterised by a number of factors that contribute to the system complexity:- the number of server nodes in the cluster, interconnections between resources and heterogeneity of resources (different types of CPUs, memories, local storages);- the number of concurrent jobs in the system and their arrival rate; - heterogeneity of jobs (different requirements of CPU, memory and local storage; different patterns of resource usage, long-running jobs vs short-alive jobs; urgent jobs vs jobs with loose deadlines).The key requirement for the system is its scalability - the ability of the system to sustain the required throughput level (such as operations per second) while confining the perceptional response latencies to a level similar to a small or medium size system. In our project, we aim to address the following challenges:(a) scheduling at scale (to make prompt scheduling decisions at a rapid rate);(b) resource utilisation at scale (to improve utilisation of resources while maintaining high quality of service);(c) Quality-of-Service provision at scale (to satisfy requirements of diverse workloads).Existing scheduling algorithms developed for practical systems are often designed largely based on empirical knowledge, experience, and best effort. Due to the lack of theoretical foundation, performance of those algorithms cannot be always guaranteed. On the other hand, scheduling algorithms proposed by the theoretical community are usually based on oversimplified abstract system models. Theoretically sound algorithms, with guaranteed accuracy and time complexity, are often impractical because system models do not reflect practical complexity of real systems, and even minor adjustments of system models towards real systems make algorithms no longer applicable.In our project, theoretical and applied experts will consolidate efforts to conduct jointly an interdisciplinary study, overcoming the shortcomings of isolated research. Overall, our project is 1) methodologically driven, attempting to extend the applicability of the most powerful techniques of mathematical optimisation; 2) application driven, where the challenges of massive-scale distributed systems invoke new developments of scheduling methodology; and 3) practice driven, where the research direction is based on hands-on experience of distributed systems specialists.