基于在线优化的Hadoop YARN平台下资源分配机制研究

Hadoop YARN has emerged as a major Big Data Processing Platform for many IT companies including Microsoft and Tencent. Job Scheduling and Resource Allocation for Hadoop YARN are essential to the overall system performance. However, most existing resource allocation schemes under Hadoop mainly concern about the fairness between different users/applications and are designed based on simple heuristics. There is a lack of systematic analysis or reference study on how well or suboptimal these schemes are when comparing to the theoretical limits of various performance metrics such as overall job response time and system utilization. To tackle this issue, this project will redesign resource allocation algorithms from an optimization perspective. In particular, we will build a system model based on the Multi-dimensional Bin Packing problem, taking job response time, fairness and fault tolerance into consideration so as to optimize the overall job flowtime. We will adopt the Dual-fitting framework to solve the optimization problem and design corresponding algorithms. To demonstrate the practicality of our designs, this project will also implement the proposed algorithms as extensions of an open-source software platform, i.e., Apache Hadoop YARN. Moreover, we will compare our proposed solutions with other baseline schemes.

Hadoop YARN已经成为微软，腾讯等互联网公司部署大数据计算集群所采用的主流计算平台。在Hadoop YARN中，掌控好资源分配就抓住了整个平台的核心。现有的Hadoop YARN平台下的资源分配机制主要考虑的是不同租户之间的公平性问题，并且都是基于启发式算法设计的。这些机制缺乏系统的分析和论证，在作业执行时间和资源使用率这些性能指标上存在着很大的提升空间。本项目将设计一种基于在线优化理论的Hadoop YARN平台下的资源分配机制来保证租户公平性、提升系统容错能力、减小作业延迟。为了达到此目标，本项目将建立一个多维资源约束下的作业响应时间最优化模型，利用所熟悉的在线优化理论工具设计算法并且对提出的算法进行严格的理论分析。另外，本项目也会将设计的算法实现在Hadoop YARN开源平台下，并采用仿真与真实实验相结合的办法对所设计算法进行全面评估。

Hadoop YARN已经成为微软，腾讯等互联网公司部署大数据计算集群所采用的主流计算平台。现有Hadoop YARN平台下的资源分配机制主要考虑的是不同租户之间的公平性问题。这些公平性机制都是基于启发式算法设计，缺乏系统的分析和论证，并且在作业完成时间和资源使用率这些性能指标上表现很差。. 本项目设计了一种基于在线优化理论的Hadoop YARN平台下的资源分配机制来保证租户公平性、提升系统容错能力、减小作业延迟。为了达到此目标，本项目建立一个多维资源约束下的作业响应时间最优化模型，利用在线优化理论设计作业调度算法并且对算法进行了严格的理论论证。最后，本项目在Hadoop YARN平台上实现了资源调度算法，我们的算法相对现在主流资源管理方案可在保证一定公平性的前提下将作业完成时间大幅减小。. 该项目共发表9篇高水平论文，其中6篇发表在CCF 推荐的A类会议以及A类期刊上，包括IEEE Infocom, IEEE/ACM ToN, IJCAI, ICDE，一篇发表在SCI一区期刊IEEE TSG上，另外一篇在ICDCS会议上发表。这9篇论文至今Google Scholar引用次数超过200，并引起了国内外相关研究小组的积极讨论与跟进。在理论层面，这些研究结果首次证明了从在线凸优化的角度解决大规模复杂系统的多维资源调度问题是可行的。项目的研究方案摒弃了传统算法中组合最短作业优先以及公平性调度策略这些启发式思路，对云计算、分布式机器学习的资源管理研究具有较强的指导意义。更加重要的是，我们设计的在线凸优化方案能从理论上保证作业的的完成时间以及公平性等性能指标接近最优解的性能。此外，该项目也研究了如何运用在线凸优化技术来解决大数据集群由于机器性能不稳定而导致作业响应时间增加这一难题。在系统层面，我们对现有Hadoop YARN平台做了极大的改进。通过在YARN平台的资源管理模块实现项目设计的调度策略以及在作业管理模块部署任务资源预估算法， 该项目可将作业平均完成时间减小40%以上。