细说调度
2021年02月03日 星期三, 发表于 东莞,中国
如果你对本文有任何的建议或者疑问, 可以在 这里提issues
[TOC]
近一个月来投入到分布式任务调度方向的工作,以下为最近工作和学习的一些总结。一家之言,如有不对,请指正。
简介
关于调度这个话题,大家一定不会陌生,其实在生活中,我们几乎都在实施调度这个事情。通俗一点说,如何高效地分配并完成自己的各项事务,收获预期的效果,这就是调度的本质。但是调度本身是一件非常有难度的事情,因为有些事务可能重要不紧急,有些事务紧急不重要,有些呢又重要又紧急。。。
日常大家经常都能遇到以下调度器:
- 红绿灯,红灯停、绿灯亮,红绿灯轮流变换
- 无处不在的排号机,特别是会员能插队,VIP有优先通道那种
- ……
以上种种都涉及到计算机科学中非常常见的调度算法,本文将会介绍大部分场景中使用的调度策略及算法,并结合近期学习的部分优秀大数据框架的调度策略及算法进行分析。
调度器的目标
调度器的设计目标一定是为了解决特定系统的需求,一个号称通用的设计很有可能什么问题都解决不了,或者什么问题都解决得不是很好。那么我们说面向不同的系统需求,自然就有不同的调度目标:
- 集群/本地资源得到合理、充分利用;
- 实时高效地完成任务;
- 任务之间公平地执行;
- 面对不同种类的任务,都能得到很好的执行;
- ……
当然对于我们本次的分布式项目来说,目标自然是批处理任务的高效完成,而且是多任务的高效执行。简而言之,快。
调度器的设计考量
在软件设计中,虽然不同的设计是为了解决不同的问题,但是对于分布式系统来说往往有很多共同的设计考量,那么对于一个分布式系统调度器而言,它的设计考量有以下几个方面:
- 负载均衡:尽可能将工作负载平均到不同节点,减少单点宕机造成的损失
- 可扩展性:当集群规模增大后,调度器不会成为系统的性能瓶颈点
- 高可用:调度集群化,任何一个调度器出现问题不会影响到整个集群的调度
- 灵活性:提供调度算法的可配置功能,满足不同用户不同的调度需求
- 资源的高效利用:调度器应尽可能地提供集群的资源利用率,合理分配各类资源(如CPU、内存、IO等),此时一般会配合一个全局的资源管理器来进行决策。
以上几点是在做调度器设计时的一些通用设计考量,但是不代表不需要考虑其他方面,例如结合任务的数据亲和性,调度时考虑数据局部性问题、计算密集型任务在调度时需要优先考虑CPU资源等。
常见调度策略及算法
调度算法是调度器的大脑,调度器只是调度算法的手脚。常见的调度算法有:队列调度算法SP、RR、WRR/DRR、TDM、WFQ等,进程调度算法FCFS,SJF,HRRN等;YARN调度的FIFO、Capacity、Fair等调度算法,以及流式计算平台的调度、Spark的调度算法等。不同的调度算法适用于不同的应用场景,具有不同的优缺点。
队列调度算法
1. Round-Robin (时间片轮询调度)
RR轮询调度以环形方式轮询多个队列,如果轮询队列不为空,则执行任务,如果为空,则直接跳过,调度器不等待,常用于分时系统,RR轮询调度的关键则在于时间片的大小设置上。
2. Deficit Round-Robin (差分轮询调度)
DRR差分轮询调度主要解决由于不同数据流的不同包长引起的对队列服务的不公平场景问题。实现方式上,给待调度的每个队列分配一个可配置的服务量额度(quantum),如果一个队列在当前轮询中的数据帧的帧长大于分配的服务量额度(quantum),那么该数据帧将不被发送。帧长和当前服务额度(quantum)的差值将加到该队列下一次的服务额度(quantum)中,作为队列下一次轮询的可用带宽。
DRR为每个队列设置一个计数器Deficit,Deficit初始化为一次调度允许的最大字节数,一般为接口MTU(Maximum Transmission Unit)。每调度一个报文出去,扣除相应的长度值。允许Deficit出现负值,可保证长报文也能被调度,但不能设置权重。
DRR按报文长度调度,而RR按报文个数进行调度。DRR调度避免了采用SP调度时低优先级队列中的报文可能长时间得不到服务的问题。但是DRR调度不能设置权重,也具有实时业务得不到及时调度的缺点。
3. Modified Deficit Round-Robin (改良DRR调度算法)
MDRR调度算法提供了以下两种模式:
-
严格优先级模式,特殊队列只要非空就必须得到服务
-
交替调度特殊队列和其他队列。例如队列A是特殊队列,队列B、C和D是普通队列,那么调度的顺序就是A-B-A-C-A-D,即总是先调度特殊队列后,再顺序调度普通队列。
MDRR SP模式
MDRR 交替模式
4. Weighted Round-Robin (加权轮询调度)
WRR算法为每个队列设置一个计数器。按报文数进行调度,调度出1个报文,计数器就减1。如果配置队列1:2:4,那么实际的流量比例也是1:2:4。因此,RR可以理解为WRR权重为1:1:1的调度。WRR的测试中,需明确是否调度的是完整的报文还是分片,从上层系统来看,一般是需要调度完整的报文。
算法资源(假设有N个带调度队列)
- 一个可以轮询N个队列号的计数器Rr_counter
- 每个队列一个权重配置值weight_config(N)
- 每个队列一个记录权重使用情况的计数器weight_counter(N)
WRR调度缺陷:按照报文个数进行调度,因此每个队列没有固定的带宽,同等调度机会下大尺寸报文获得的实际带宽要大于小尺寸报文获得的带宽,而用户一般关心的是带宽。低延时需求业务(如语音)得不到及时调度。
5. Deficit weighted Round-Robin (差分加权轮询调度)
DWRR为每个队列设置一个计数器Deficit,Deficit初始化为Weight * MTU,可以理解为按照权重和报文长度来进行调度。如果配置队列的权重为1:2:4,那么实际的bps流量比例也是为1:2:4。DRR相当于权重值为1的DWRR调度。当所有队列的权重都为1时,且每次减权重也是1时,就是RR调度。
DWRR调度原理及实现和WRR基本一致,只是权重代表的时一定的报文长度,以弥补WRR中报文长度不一致时的缺点。相对于WRR而言,解决了WRR只关心包数,同等调度机会下大包获得的实际带宽要小于小包获得的带宽问题,通过调度过程中考虑了包长的因素,从而达到调度的速率公平性。
DWRR调度避免了采用SP调度时低优先级队列中报文可能长时间得不到服务,也避免了个队列报文长度不等或变化比较大时,WRR调度不能按配置比例分配带宽资源。但DWRR调度仍具有实时需求业务得不到及时调度的缺点。
6.Weighted Fair Queue (加权公平队列)
WFQ算法时为了使流量分配更加公平,理论上按照bit来进行调度,实际以256B或其他粒度进行调度,以防止长报文比短报文获得更多的带宽,减少长短报文共存时的抖动。WRQ从原理上要比RR类调度性能优越,但它的实现要比RR类调度复杂、运算量大,在队列或流的数量很大时,一般不采用WRQ。
以带宽控制为例,WRQ按队列权重来分配每个流应占有出口的带宽,以bit为单位进行调度。但bit by bit调度模型只是理想化的模型,实际上路由器实现的WFQ是按照一定的粒度,比如256B、1KB,或其他粒度,具体与单板类型相关。
7. First In First Out (先进先出调度)
FIFO队列不对报文进行分类,当报文进入接口的速度大于接口能发送的速度时,FIFO按任务到达接口的先后顺序进入队列,同时,FIFO在队列的出口按进队的顺序出队,先到的任务将先出队,后到的任务将后出队,其实就和食堂排队打饭一个道理。
FIFO队列处理简单,开销小。但是FIFO不区分报文类型,采用尽力而为的转发模式,使对时间敏感的实时应用(如VoIP)的延迟得不到保证,关键业务的带宽也不能得到保证。
8. Strict Priority (严格优先级调度)
SP调度算法按照队列优先级的高低顺序进行调度。只有高优先级队列中的报文全部调度完毕后,低优先级队列才有调度机会。即高优先级的队列还未调度完,低优先级的队列时不会得到执行的。
SP算法实现简单,对优先级搞的业务提供有限服务,保证关键的业务得到优先处理。缺点时拥塞发生时,如果较高优先级队列中长时间有任务存在,那么低优先级队列中的任务就会由于得不到服务而“饿死”。
典型队列调度算法优缺点对比
算法 | RR | DRR | WRR | WDRR | FIFO | SP | WFQ |
---|---|---|---|---|---|---|---|
适用场景 | 端口间的输入带宽相同 | 变长包长的数据包队列调度 | 既要分优先级又要”防饿死” | 对带宽和演示都有要求 | 没有优先级要求,严格按顺序执行 | 服务分优先级,对优先级高的业务提供优先服务 | 队列数较少的业务场景 |
优点 | 实现简单,每个队列都有服务机会 | 在进行带宽分配时不用考虑不同流的平均包长 | 每个队列都有服务机会,按权重分配服务次数 | 有效分配带宽,保证特殊的队列的实时调度 | 实现简单,先到先得 | 实现简单,保证关键业务实时调度 | 通过配置权重来获得带宽的分配,保证大带宽有效的时延 |
缺点 | 未考虑每次调度差异,无法保证流量均匀 | 低时延要求的队列不能保证时延 | 未考虑每次调度差异,无法保证流量均匀 | 实现复杂,消耗资源较多 | 不能保证低时延要求的业务及时得到调度 | 低优先级的数据可能会”饿死” | 没有考虑调度单元的差异,实现复杂 |
进程的调度策略
进程调度有抢占式/非抢占式调度。非抢占式指进程正在运行时就会一直运行,直到该进程完成或发生某些事件而被阻塞,才会把CPU让给其他进程。而抢占式调度就是进程正在运行时可以被打断,使其把CPU让给其他进程。抢占的原则包括时间片原则、优先权原则以及短作业优先原则。
调度算法影响的是等待时间(进程在就绪队列中等待调度的总和),而不影响进程在使用CPU的时间和I/O时间。操作系统对于进程的调度策略有以下:
1. First Come First Served (先到先服务调度)
FCFS算法每次从就绪队列选择最先进入队列的进程,然后一直运行,知道进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。
如果一个长作业先运行了,那么后面的短作业等待的时间就会很长。FCFS算法对长作业有利,适用于CPU繁忙性作业的系统,而不适用于I/O繁忙型作业系统。
2. Shortest Job First (短作业优先调度)
SJF调度算法优先选择运行时间最短的进程来运行,有助于提供系统的吞吐量。
但是SJF调度算法很容易会导致长作业不断往后推,从而长期不被执行。
3. Highest Response Ratio Next (高响应比优先调度)
高响应比优先调度算法权衡了短作业和长作业。每次进行进程调度时,先计算响应比优先级,然后把响应比优先级最高的进程投入运行,响应比优先级的计算公式如下:
优先权 = (等待时间 + 要求服务时间) / 要求服务时间
- 如果两个进程的等待时间相同时,要求的服务时间越短,响应比就越高,这样短作业的进程容易被选中运行;
- 如果两个进程要求的服务时间相同时,等待时间越长,响应比就越高,这兼顾了长作业进程,进程响应比可随时间等待的增加而提高,当其等待时间足够长,其响应比便可升到很高,从而获得运行机会。
4. RR调度算法
同队列调度算法中所提RR调度算法
5. Highest Priority First(最高优先级调度)
RR调度算法让所有进程同等重要,运作时间一样。但多用户系统的调度有优先级,即希望调度程序能从就绪队列中选择最高优先级的进程进行运行,这就是HPF调度算法的本质。进程优先级可分为:
- 静态优先级:创建进程时候就已确定优先级,然后整个运行时间优先级都不会变化;
- 动态优先级:根据进程的动态变化调整优先级,如进程运行时间增加,则降低其优先级,如进程等待时间(就绪队列的等待)增加,则升高其优先级,即随着时间的推移增加等待进程的优先级。
两种处理优先级高的方法:
- 非抢占式:当就绪队列中出现优先级高的进程,运行完当前进程,再选择优先级高的进程。
- 抢占式:当就绪队列中出现优先级高的进程,挂起当前进程,调度优先级高的进程运行。
PS. 依然存在可能会导致低优先级的进程永远不会运行。
6. Multilevel Feedback Queue(多级反馈队列调度算法)
MFQ是RR调度算法和HRF调度算法的综合与发展。多级表示有多个队列,每个队列优先级从高到低,同时优先级越高时间片越短。反馈表示如有新的进程加入优先级高的队列时,立刻停止当前正在运行的进程,转而去运行优先级高的队列。
- 新的进程会被放入到第一级队列的末尾,按先来先服务的原则排队等待被调度,如果在第一级队列规定的时间片没运行完成,则将其转入到第二级队列的末尾,以此类推直至完成;
- 当较高优先级的队列为空才调度较低优先级的队列中的进程运行。如进程运行时有新进程进入较高优先级的队列,则停止当前运行的进程并将其移入到原队列末尾,接着让较高优先级的进程运行。
对于短作业可能可以在第一级队列很快被处理完。对于长作业,如在第一级队列处理不完,可以移入下级队列等待被执行,虽然等待时间变长了,但运行时间也会变长了,算法很好地兼顾了长短作业,同时有较好的响应时间。
YARN资源调度
YARN调度器根据容量、队列等限制条件(如每个队列分配一定的资源,最多执行一定数量的作业等),将系统中的资源分配给各个正在运行的应用程序。YARN中负责给应用分配资源的为Scheduler,提供了多种可配置的策略,如CapacityScheduler、FairScheduler。Scheduler不负责监控或跟踪应用程序状态,也不负责任务因为各种原因而需的重启(ApplicationMaster负责)。调度器根据应用程序的资源需求及集群机器的资源情况进行资源分配,而资源分配单位是Container,从而限定每个任务使用的资源量。
1. First In First Out Scheduler
FIFO Scheduler把应用按提交的顺序排成一个先进先出的队列,在进行资源分配的时候,先给队列中最前面的应用分配资源,当满足了最前面的应用需求后再给下一个分配,以此类推。FIFO Scheduler是最简单也是最容易理解的调度器,不需任何配置,但它并不适用与共享集群。大的应用可能会占用所有集群资源,这就导致其他应用被阻塞。在共享集群中,更适合采用CapacityScheduler或FairScheduler,这两个调度器都允许大任务和小任务在提交的同时获得一定的系统资源。
2. Capacity Scheduler
默认资源调度器,Capacity Scheduler以队列为单位划分资源,通俗一点来说就是一个个队列有独立的资源,队列结构和资源可以进行配置。对于Capacity调度器,有一个专门的队列用来运行小任务,但为小任务专门设置一个队列会预先占用一定的集群资源,这就导致大人物的执行时间会落后于使用FIFO调度器时的时间。
Default队列占50%资源,dev和report分别占30%和20%资源,default和dev各有两个子队列,子队列在父队列的基础上再分配。队列以分层方式组织资源,设计了多层级别的资源限制条件以更好的让多用户共享一个Hadoop集群,比如队列资源、用户资源、用户应用程序数目限制。队列里的应用以FIFO方式调度,每个队列可设定一定比例的资源最低保证和使用上限,同时每个用户也可设定一定的资源使用上限以防止资源滥用。而当一个队列的资源有剩余时,可暂时将剩余资源共享给其他队列。
Capacity Scheduler具有以下几个特性:
- 层次化的队列设计保证了子队列可以使用父队列设置的全部资源,通过层次化的管理更易合理分配和限制资源的使用。
- 容量保证,队列上都会设置一个资源的占比,这样可以保证每个队列都不会占用整个集群的资源。
- 安全,每个队列有严格的访问控制。用户只能向自己队列里提交任务,且不能修改或访问其他队列的任务。
- 弹性分配,空闲的资源可以被分配给任何队列。当多个队列出现争用的时候,则会按照比列进行平衡。
- 多租户租用,通过队列的容量限制,多个用户就可共享同一个集群,同时保证每个队列分配到自己的容量,提高利用率。
- 操作性,yarn支持动态调整容量、权限等的分配,可在运行时直接修改。管理界面可显示当前队列状况,管理员可在运行时添加一个队列但不能删除一个队列。还可在运行时暂停某个队列,这样可保证当前的队列在执行过程中,集群不会接受其它任务。例如一个队列被设置成stopped,那么就不能向它或子队列上提交任务了。
- 基于资源的调度,协调不同资源需求的应用程序,比如内存、CPU、磁盘等等。
3. Fair Scheduler
公平调度可以应用于一个队列或多个队列间,为所有的应用公平分配资源。不需要预先占用一定资源资源,每一个作业都是共享的,调度器会为所有运作的job动态的调度系统资源。当第一个大job提交时,此时它获得所有集群资源;如果再提交一个作业,那么第一个作业就会分给第二个作业一部分资源,第一个作业也就释放一部分资源。再提交其它作业时,同理,每一个作业进来都有机会获取资源。
例如用户A或B分别拥有一个队列,当A启动一个job而B没有任务时,A会获得全部集群资源;当B启动一个job后,A的job会继续运行,不过一会儿之后两个任务会各自获得一半的集群资源。如果此时B再启动第二个job并且其他job还在运行,则它将会和B的第一个job共享B这个队列的资源,即B的两个job会用四分之一的集群资源,而A的job仍然使用集群一半资源,资源最终在两个用户之间平等共享。
Fair Scheduler 与 Capacity Scheduler的区别:
- 调度策略灵活配置:Fair Scheduler允许为每个队列单独设置调度策略,支持FIFO、Fair或DRF三种策略为应用程序分配资源;
- 资源公平共享:默认每个队列采用平均分配策略分配集群资源;
- 支持资源抢占:当某个队列中有剩余资源时,调度器会将这些资源共享给其他队列,而当这个队列中有新的应用程序提交时,调度器要为它收回资源。为尽可能降低不必要的计算浪费,调度器采用了先等待再强制回收的策略,即如果等待一顿时候后尚有未归还的资源,则会进行资源抢占;从那些超额使用资源的队列中杀死一部分任务,进而释放资源;
- 负载均衡:Fair Scheduler提供了一个基于任务数的负载均衡机制,尽可能将系统中的任务均匀分配到各个节点。此外,用户也可根据需求设计负载均衡机制。
- 提高小应用程序响应时间:由于采用了最大最小公平算法,小作业可以快速获取资源并运行完成。
4. Dominant Resource Fair Scheduler
DRF 算法是为了解决在一个包括多种资源类型(主要考虑CPU和MEM)的系统的公平资源分配问题,其中不同用户对资源有不同的需求,属于公平调度策略的一种,也是最大最小算法的一个具体体现。
算法示例
考虑一个系统有<9CPU, 18G>资源,A任务需<1CPU,4G>,B任务需<3CPU,1G>。如何为这种情况构建一个公平分配策略?分配模型可转化为一定约束条件下的优化问题,下面x代表A任务的个数,y表示B任务的个数。最大化资源分配max(x,y),约束条件:(x+3y)<=9(CPU约束);(4x+y)<=18(内存约束); 4x/18==3y/9(主资源公平约束)。
伪代码说明
例子中用户A的CPU占总CPU1/9,MEM占总MEM的2/9,而用户B的CPU占1/3,MEM占2/9,所以A的主资源为内存,B的主资源为CPU。基于这点,DRF会最大化A的内存的最小化分配,并会最大化B的CPU的最小分配。
Weighted DRF换算方式
带权重的情况下每个用户的dominant share不再是那个占用总资源百分比最大,而是定义为Si=max{Ui,j/Wi,j},即那份占总权重最大的资源作为dominant share,代替上述例子中的dominant share进行运算。
DRF Scheduler有四种主要特征,分别是:
- sharing incentive :DRF是通过确保系统的资源在用户之间是静态和均衡地进行分配来sharing incentive,用户不能获得比其他用户更多的资源。
- strategy-proofness : 用户不能通过谎报其资源需求来获得更多的资源。
- Pareto efficiency :在满足其他特性的同时,分配所有可以利用的资源,不用取代现有的资源分配。
- envy-freeness :用户不会更喜欢其他用户的资源分配。
Spark 任务调度策略
术语表
- Job: 用户提交了spark程序到driver端,程序根据spark的action算子操作,将代码分为多个job,job串行执行。
- Stage: 一个job,提交至DAGScheduler,回执DAG图,根据RDD的依赖关系,可以分为宽依赖和窄依赖,根据宽依赖将DAG图分为多个stage。其中宽依赖一般涉及shuffle操作,所以也可以认为shuffle是stage的一个分割依据
- Task: stage根据数据的分区个数又可以具体分为多个task,task可以并行执行,所以stage又称为taskSet(工作集合)
- Worker: 集群中任何可以运行应用代码的节点
- Driver: 运行main函数并且创建SparkContext的程序
- Executor: 是在一个worker node上为某应用启动的一个进程,该进程负责运行任务,并且负责将数据存在内存或者磁盘上。每个应用都有各自独立的executor
Scheduling
spark任务调度涉及的模块以及流程图如下:
调度模式
spark应用程序的调度体现在两个地方,第一个是Yarn对spark应用间的调度,第二个是spark应用内(同一个SparkContext)的多个TaskSetManager的调度,这里暂时只对应用内部调度进行分析。
spark的调度模式分为两种:FIFO(先进先出)和FAIR(公平调度)。默认是FIFO,即谁先提交谁先执行,而FAIR支持在调度池中再进行分组,可以有不同的权重,根据权重、资源等来决定谁先执行。spark的调度模式可以通过spark.scheduler.mode进行设置。
Spark作业执行图
这个架构中有几个值得注意的地方:
1、每个 Spark 应用程序都有自己的 Executor 进程,整个应用程序生命周期内 Executor 进程都保持着运行状态,并且以多线程方式运行所接收到的任务。这样的好处是,可以隔离各个 Spark 应用程序,从调度角度来看,每个 Driver 可以独立调度本应用程序内部的任务,从 Executor 角度来看,来自不同 Spark 应用程序的任务将会在不同的 JVM 中运行。然而这也意味着无法在多个 Spark 应用程序(SparkContext 实例)之间共享数据,除非把数据写到外部存储系统中。
2、Spark 对底层的集群管理器一无所知。只要 Spark 能获取到执行器进程,并且能与之通信即可。这样即使在一个支持多种应用程序的集群管理器(如:Mesos 或 YARN)上运行 Spark 程序也相对比较容易。
3、Driver 程序在整个生命周期内必须监听并接受其对应的各个 Executor 的连接请求(参考:spark.driver.port and spark.fileserver.port in the network config section)。因此,Driver 程序必须能够被所有 Worker 节点访问到。
4、因为集群上的任务是由 Driver 来调度的,所以 Driver 应该在 Worker 节点附近运行,最好在同一个本地局域网内。如果你需要远程对集群发起请求,最好是开启到 Driver 的 RPC 服务并且让其就近提交操作,而不是在离集群 Worker 节点很远的地方运行 Driver。
Task数据本地性
- PROCESS_LOCAL –进程本地化,表示 task 要计算的数据在同一个 Executor 中。
- NODE_LOCAL –节点本地化,速度稍慢,因为数据需要在不同的进程之间传递或从文件中读取。分为两种情况:
- task 要计算的数据是在同一个 worker 的不同 Executor 进程中。
- task 要计算的数据是在同一个 worker 的磁盘上,或在 HDFS 上恰好有 block 在同一个节点上。
如果 Spark 要计算的数据来源于 HDFSD 上,那么最好的本地化级别就是 NODE_LOCAL。
RACK_LOCAL – 机架本地化,数据在同一机架的不同节点上。需要通过网络传输数据以及文件 IO,比 NODE_LOCAL 慢。
- NO_PREF –没有最佳位置,数据从哪访问都一样快,不需要位置优先。比如 Spark SQL 从 Mysql 中读取数据。
- task 计算的数据在 worker2 的 EXecutor 中。
- task 计算的数据在 work2 的磁盘上。
- ANY – 跨机架,数据在非同一机架的网络上,速度最慢。
Task运行预测
待研究,占位
Flink 任务调度策略
术语表
-
Job:一个Job既是一个作业,是提交的要完成的整个数据处理的总的任务。
-
Task: Job会被拆解成多个Task并分配到多个节点执行,Task是最小的执行单元,Task个数代表着作业的并发能力。
-
Slot: Slot槽是负责执行Task的载体,一个节点上会有多个Slot。
Job的并行能力可以通过设置parallelism进行配置,其表示同时可由几个Slot执行。一个节点的Slot不能无限增加,需要根据内存和CPU的情设置合理的slot数来限制同时执行Task的数量,保证不会因为同时执行的Task过多而导致故障,更多的任务进来将进入队列排队等待。如果作业需要更多并行数,可以通过资源管理申请更多的容器来使一个作业能够有更多的Slot参与计算。
Flink中每个TaskManager都有一个或多个Slot,每个Slot可以运行一个并行任务管道。管道由多个连续任务组成,例如MapFunction的第n个并行实例以及ReduceFunction的第n个并行实例。流处理应用为并行、连续任务模式,批处理程序也常为同样模式。例如一个带有数据源,MapFunction和ReduceFunction的程序,源和MapFunction的并行度为4,而ReduceFunction的并行度为3,则管道由Source-Map-Reduce组成,在具有2个TaskManagers且每个具有3个Slot的集群上,程序将按下图执行。
Scheduling
调度原则上,同一个operator的各个subtask不能分派在同一个ShareSlot中,例如FlatMap[1]和FlatMap[2]不能在同一个SharedSlot。另外,Flink按照拓扑顺序从Source一个一个调度到Sink。如WordCount(Source并行度为1,其他为2),那么调度的顺序依次是:Source -> FlatMap[1] -> FlatMap[2] -> KeyAgg -> Sink[1] -> KeyAgg -> Sink[2]。假设现有2个TaskManger,每个只有1个slot,那么slot的分配过程则如下图所示:
最后Source、FlatMap[1]、KeyAgg->Sink[1]这些subtask会部署到TaskManager1的Slot中,FlatMap[2]、KeyAgg->Sink[2]这些subtask被部署到TaskManager2的Slot中,并启动对应的线程,从而实现了Slot的共享。简单的情况下,一个Slot只持有一个Task,也就是SimpleSlot的实现。稍复杂的情况,一个Slot能共享给多个Task使用,也就是SharedSlot的实现,ShareSlot能包含其它的SharedSlot或SimpleSlot。所以一个SharedSlot能定义出一棵Slots树。
调度模式
Flink提供了两种调度模式:
- LAZY_FROM_SOURCES : Schedule tasks lazy from sources, Downstream tasks start once their input data are ready.
- EAGER:先调用allocateResourcesForAll来分配资源,然后才是把所有的task部署到对应的slot上。
LAZY_FROM_SOURCE可以理解为将每种operator逐个完成,比较适合批处理模式,这种模式使得每种operator都能最大限度地利用集群资源。而EAGER模式比较适用于流式数据处理,因为Task正常情况下不存在退出结束的行为。
JobManager
JobManager协调和管理程序的执行,负责任务安排、管理checkpoint、故障恢复等。集群种至少有一个master,负责调度Task、协调checkoupoints和容灾,可部署多个master来保证高可用,Active/standby模式;JobManager包含Actor system、Scheduler、Check pointing三个重要组件,跟踪分布式任务,决定何时安排下一个任务或一组任务,并对已完成的任务或执行失败做出反应。JobManager接受JobGraph,JobGraph是由运算符(JobVertex)和中间结果(IntermediateDataSet)自称的数据流的表示。每个算子都具有属性,如并行性和它的执行代码。此外,JobGraph还有一组附加库,这些库是执行算子代码所必需的。
在用户取消作业的情况下将进入取消状态(cancelling),会取消所有当前正在运行的任务。一旦所有运行的任务已经达到最终状态,该作业将转换到已取消状态。完成状态,取消状态和失败状态表示一个全局的终结状态,并且触发清理工作,而暂停状态(suspended)仅处于本地终止状态。意味着作业的执行在相应的JobManager上终止,但集群的另一个JobManager可从持久的HA存储中恢复这个作业并重新启动。因此,处于暂停状态的作业将不会被完全清理。
Flink作业执行图
流批一体的调度
调度系统的目标,在集群层面要提升集群实际利用率,即申请的资源和实际使用的资源差别越小越好,没有空闲的资源浪费。Flink流、批作业两者之间存在共同性,例如都有Java Framework及heap对象开销,包括shuffle service的开销等等。但对于流作业,由于作业一直运行,获得作业后就调度所有节点,后续无需关心调度问题。而批作业则对延迟要求不高。
- 当运行时资源不足,能以最小资源运行。
- 集群资源充足时,则需要能尽快运行,能够充分利用资源。
- 为提升实际资源利用率,要明确作业当前对资源的需求,对资源的实际需要。如果不需要则不占用当前用不上的资源。例如批作业很多有上下依赖关系,如果把后续的资源占用,实际下游的很多节点不一定能用得上,如此就造成了资源浪费。
总结
调度是个很大的话题,在学习不同调度器的时候要抓住几个关键点,则可以快速理解该调度器的设计想法:
- 调度器的设计目标
- 任务划分的逻辑
- 任务分配的策略
不过不管是调度算法还是整系统的调度策略,都有很强的“因地制宜”特色,从不同的问题域出发去理解不同的调度器设计往往可以一下子就抓住要点。同时在设计自己的调度器的时候首先要明确自己的设计目标,博采众长的同时要有针对性地解决本系统的核心问题。
未完待续,下节更精彩。