流式云服务作业调度文献综述

 2022-09-23 04:09

文献综述（或调研报告）：

国内外学者针对云计算中作业调度算法以及Storm默认调度策略的不足，提出过许多作业调度策略以及改进的Storm调度算法，兼顾用户的服务质量（QoS）的同时减少作业完成时间和所花费用、降低通信延迟、提高资源利用率等。本文分别对云计算中作业调度算法和Storm调度算法的进行说明。

一、关于云计算中作业调度算法，文献[1]提出了基于节点资源监控的RBS（Resource Based Schedule）任务调度算法和支持单节点的SNS(Single Node Schedule)任务调度算法。并在RBS算法和SNS算法的基础上，设计并实现了相应的Topology任务调度器。1.基于RBS算法的任务调度器可根据工作节点资源的使用情况，将工作进程调度到资源利用率较低的节点上；2.基于SNS算法的调度器可将一些只执行简单运算并且没有太多中间状态的Topology的多个工作进程调度到一个单一的物理节点上运行。针对Storm中控制节点的单点失效问题，通过Zookeeper协调服务实现主控制节点选举和主从控制节点之间的状态同步。侯明霞在论文[2]中提出了一种云计算环境下基于改进蚁群算法的作业调度算法：任务在虚拟机上的总成本值决定其调度顺序（总是被分配到总成本最小的虚拟机上）。该算法在实现该目标的同时,兼顾了用户的服务质量(QoS),如作业完成时间和所花费用,并考虑了云计算中虚拟机资源的负载均衡。对于作业请求数较多、数据中心资源不足的情况，提出了一种基于接入控制的作业调度策略：1.获得到来的作业请求QoS要求，计算作业的执行时间和成本；2.判断作业优先级实施抢占机制；3.利用惩罚机制，按照线性关系计算回报率；4.选择回报率最大的作业接收策略。文献[3]进一步提出了基于蚁群算法的资源感知任务调度算法（RSBA）：在调度过程中将工作节点的资源动态变化表示为蚂蚁运动所需的信息素，觅食的蚂蚁身上带着自身资源需求标签，任务调度过程类似蚂蚁觅食过程。步骤如下：1.计算每个topology的所有component的executor数量;2.对每种资源类型的component，分别计算权值;3.计算topology中各类资源所需要的worker数量;4.在运行周期内将topology中相互通信的executor对进行组合，增加一个新的executor队列并对应相应的资源;5.将工作节点上的资源状态转换为蚁群算法中的信息素，按浓度高低排列进行任务分配。

二、对Storm默认调度策略的改进，论文[4]中提出的算法首先计算Bolt的容量，然后分析消息队列拥塞度，最后改变拓扑的一些参数以动态消除性能瓶颈。工作流程如下：1.bolt的容量计算与bolt的消息队列拥塞度分析；2.在以上这些值的基础上相应地调整参数；3.executors到slots分配与slots到工作节点分配。所提出的方法使用bolt容量策略和bolt消息队列拥挤度分析逐步识别性能瓶颈。通过分析这些值，可以相应地调整性能参数，而无需停止拓扑（topology）。最后，优化拓扑。经过Storm拓扑动态优化算法后，消息处理延迟减少，整体系统吞吐量也得到提升。该调度器主要集中在以下几个方面：1.为了提高系统性能，降低负载均衡、消息处理延迟、提高系统吞吐量等因素，提出了Storm拓扑动态优化算法；2.为了解决节点间负载均衡的另一个问题，提出了一种综合考虑拓扑结构、工作节点负载均衡和节点间通信量的实时调度算法，对Storm调度器进行了改进。在文献[5]中不考虑拓扑优化，程序的算法分为两个步骤：第一步，根据拓扑图和节点间流量，将executors分配给slots以确保最小的交互流量；第二步，考虑工作节点负载，为slots分配选择最后一个负载节点。此调度算法考虑采用执行器调度。大多数调度算法只关注改进executors到slots的分配，如基于拓扑的调度算法，基于流量的调度算法等，此调度程序在两个步骤（executors到slots，然后slots到工作节点）中改进了调度程序。从executors到slots的分配这一部分中，Storm拓扑的依赖关系首先根据拓扑结构进行划分，然后根据executors间通信流量进行预处理，将预处理的executors分配给slots，然后进行 slots到工作节点分配。论文[6]提出的调度算法的核心思想是考虑executors之间的通信设计，这些executors试图将高频率通信的executors放置在同一个slot中。作者在此基础上提出了两种不同的算法：其一考虑组件在拓扑中是如何相互关联的，以确定应该将哪些executors分配给同一个slot；另一种方法是在运行时监督执行程序之间交换元组的通信量。其设计包括：1.离线调度器：此调度程序分析拓扑DAG，并通过查看它们的连接方式来识别要在同一节点上安排的可能的bolts集合；2.在线调度器：通过持续监视系统性能和重新安排运行时的部署来增加离线调度器的方法，以提高总体性能。自适应在线调度（Adaptive Online Scheduler）算法依赖于贪心方法，即将executors放置到节点上，以限制节点间的通信量，避免节点之间的负载不平衡。它由连续的两个阶段组成。在第一阶段中，每个拓扑的executors被分配给一批已经安排好拓扑的工作节点上以维持运行。部署主要关注限制特定工作节点的executors之间的通信量以及调整每个工作节点的总CPU请求。在第二阶段，必须将第一阶段交付的工作节点分配到集群中的可用slots。这种分配仍然需要同时考虑节点间通信量之间的关系，从而限制节点流量和节点负载，以满足负载限制约束。Boyang Peng等将R-Storm实现为Storm的自定义版本[7]，修改核心Storm代码，以允许物理机器节点将其资源可用性发送到用户调度拓扑。R-Storm的核心调度功能在定制版Storm中作为自定义调度程序实现。用户可以通过创建实现预定义接口的类来创建自定义调度程序，调度程序作为Storm守护程序的一部分运行。收集Storm群集中的统计信息，例如任务、组件和拓扑级别的吞吐量。采用独有模块存储群集中物理机的所有资源可用性信息以及所有已调度或需要调度的Storm拓扑的所有任务的资源需求信息，生成数据用于评估。通过运行各种微基准Storm拓扑以及Yahoo!使用的生产拓扑来评估R-Storm，吞吐量和CPU利用率R-Storm的性能表现明显优于默认结构。Jielong Xu等在论文[8]中提出T-Storm，通过监控任务负载、工作节点负载以及任务之间的流量负载完成任务的动态分配，具有以下优点：（1）在保证没有工作节点过载的情况下最小化网络传输开销；（2）针对运行在一个工作节点上的属于同一个拓扑的所有任务，T-Storm只为其分配一个工作进程，从而消除了进程间的通信开销；（3）T-Storm能在保证性能的前提下，减少启动的工作节点数量。不足：资源负载的度量方面较为单一，仅考虑了CPU负载，没有考虑内存、网络带宽负载。P-Storm[9]的优点：拓扑图划分为多个子集，划分过程中尽量减少子图之间的通信开销，时间复杂度低。缺点：（1）只考虑子图在各节点的调度（粒度太粗），没有考虑各个任务的资源占用和通信情况；（2）考虑的维度不够，仅考虑CPU，缺少对内存、网络带宽负载的考虑。相对这些调度算法改进的方向，在优化Storm调度上仍有许多探索的空间。文献[10]对7种不同的调度器，包括Storm的默认循环调度器进行了比较研究。

·参考文献

  1. 龙少杭. (0). 基于Storm的实时大数据分析系统的研究与实现. (Doctoral dissertation).
  2. 侯明霞. (0). 云计算环境下作业调度策略研究. (Doctoral dissertation).
  3. 刘梦青. (0). Storm平台下作业调度方法研究. (Doctoral dissertation).
  4. Li, C. , Zhang, J. , amp; Luo, Y. . (2017). Real-time scheduling based on optimized topology and communication traffic in distributed real-time computation platform of storm. Journal of Network and Computer Applications, 87, 100-115.
  5. Zhang, J. , Li, C. , Zhu, L. , amp; Liu, Y. . (2016). The Real-Time Scheduling Strategy Based on Traffic and Load Balancing in Storm. IEEE International Conference on High Performance Computing amp; Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science amp; Systems. IEEE.
  6. Aniello, L. , Baldoni, R. , amp; Querzoni, L. . (2013). Adaptive Online Scheduling in Storm. To appear Proceedings of the 7th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM.
  7. Peng, B. , Hosseini, M. , Hong, Z. , Farivar, R. , amp; Campbell, R. . (2015). R-Storm:Resource-Aware Scheduling in Storm. Middleware Conference. ACM.
  8. Xu, J. , Chen, Z. , Tang, J. , amp; Su, S. . (2014). T-Storm: Traffic-Aware Online Scheduling in Storm. 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society.
  9. Eskandari, L. , Huang, Z. , amp; Eyers, D. . (2016). P-Scheduler: adaptive hierarchical scheduling in apache storm. the Australasian Computer Science Week Multiconference. ACM.Middleware rsquo;08, pages 306–325, New York, NY, USA, 2008. Springer-Verlag New York, Inc.
  10. Avantika, D. , Jaytrilok, C. , amp; Singh, D. P. . (2018). Survey of apache storm scheduler. SSRN Electronic Journal.

资料编号：[179203]

剩余内容已隐藏，您需要先支付 10元 才能查看该篇文章全部内容！立即支付

以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章