任务调度系统总结

解决什么问题

把任务分配给合适的机器执行

分类

业务上可以分为：

• 批处理任务调度
• “长服务”（例如VM，容器，to C的Web服务等)调度
• 定时任务调度
  个人理解，单机OS里进程调度可以理解为单机批处理任务调度。

架构上，按Worker集群的类型可以分为：

• 同构Worker（比如Hadoop集群中的Worker机器）
• 异构Worker（比如微服务集群中定时任务调度，不同的业务系统处理不同的任务，是不同的Worker）

按调度方式可以分为：

• 中心化调度
  按Google Omega论文的讲法又可以分为单体调度（master同时做资源管理和任务调度）、两层调度(master做资源管理，scheduler靠client自己实现，master回调每个scheduler、分配粗粒度的资源，类似Disruptor思想）、共享状态调度（把两层调度的悲观锁改成多个scheduler间通过乐观锁实现互斥）

• 去中心化调度

经典问题：

1. 当任务很多、Worker机器资源不足时，如何进行调度？
追求找到好的调度策略，使得任务的等待时间短、最大化利用硬件资源，或者追求公平性。
传统单机OS进程调度、分布式批处理任务调度都很关注这个问题，这里有不同算法的课程，例如FIFO,最短优先，轮询，Dominant Resource Fairness（就是百分比共产主义，每个任务的各种资源占总资源的百分比里，最大值大家都一样）等。
但是算法比较理想，实践中怎么量化集群中剩余多少资源，怎么量化预测一个没执行的任务将要吃多少资源、执行多少时间、从而找到最短的任务？

• 对于预测时间，没什么好办法，有一些估算的方法，比如按输入大小、程序大小，比如统计同一个job里其他task的时间。听起来就不准。
• 对于量化剩余硬件资源、基于预测任务需要的硬件资源进行调度的算法，vm调度的场景特别合适：已知集群剩16核CPU，80G内存，有VM job1需要2核6G，VM job2需要8核2G，请问如何调度？基于这些数据可以选择更有效的调度策略来优化目标指标，例如选DRF来优化公平性（不过这算法听起来有点扯，适合所有任务消耗的资源百分比差不多的场景）。当然这产生了另一个问题：一个4核物理机上跑3个2核VM，每个VM都吃满资源会超卖，那么是否允许超卖？允许的话怎么处理这种问题？如果是一个4核虚拟机上调度4个只占用1核的容器，会不会导致底层超卖？
• 批处理任务调度也是基于"预测"（任务向yarn申请CPU和内存资源），同时通过“限流”保证隔离性、公平性：比如Hadoop的调度，可以配置不同limit的queue，从而实现不同任务优先级，也允许在有的queue空的时候弹性调度；或者每个user一个pool，对所有pool限流、所有pool能吃的资源一样。
  那么怎么知道某个任务或者某个task/queue/pool吃了多少资源？难不成是基于监控统计？找到篇博客说yarn是基于线程监控。
  image.png
  能想到这种基于限流的算法会存在一个问题：如果一类大任务被投递到小queue，只要任务一运行就会超卖，那么这类任务岂不是永远不会得到运行？似乎有一些策略能在集群闲置的情况下把所有资源都给运行中的任务，但不闲的时候岂不是还是有这问题。

另一方面，业界（分布式）定时任务调度系统似乎都不怎么关注这个问题（用定时任务的场景来描述就是“0点到0点30分之间有海量定时任务先后触发，机器资源不够他们一起执行，那么如何调度这些定时任务、谁先谁后？还是轮流？”），个人理解有如下原因：

• 定时任务需要实时性，机器资源不够就要排队，排队就没有实时性了
• 定时任务调度的常见架构是异构Worker场景（集群有一个调度中间件master，通过rpc或者mq调不同的业务系统执行不同业务的定时任务），这样同一时间的任务数就少了很多、一定程度避免海量任务问题；且每个业务app自己负责自己的调度，自己加机器/自己放一个queue/自己改定时任务触发时间让任务错开执行/自己配任务分片策略。
  当然，实践中常有定时任务因为数据量大导致不能短时间内跑完的问题。遇到这种情况要想的倒不是“机器有限、任务太多，如何设计调度策略来获得更好的公平性/等待时间”，而是"定时任务不应该这么用，这个业务逻辑需要优化”。优化思路有几种：
• 去冗余
• 并行化（加线程/加机器）
• 时间上分摊（与其大任务每隔3个月执行一次，不如每天、每小时执行小任务，甚至流式计算）
  可以参考处理亿级数据的“定时任务”，如何缩短执行时间？

2. 当scheduler成为瓶颈时如何扩展
例如当调度逻辑复杂难以添加新的调度策略、调度算法耗时较长导致head-of-line blocking、集群机器规模大但scheduler吞吐量有限等问题出现时，scheduler成为瓶颈。Google的Omega论文有讨论这个问题。

3. 虽然集群里Worker机器总资源够，但是有的Worker负载很高有的很低，如何负载均衡？
面临问题1场景的系统应该不用担心该问题，因为不管FIFO还是啥调度算法，首要关注的是硬件资源占用率，会让整个集群所有Worker的负载都尽量满着。
能想到的第一种方法是“预防式（Preventive)”，任务执行前先申请、报备资源。
这同样面临上面的问题：怎么量化得知当前剩余资源、任务将要占用的资源？如果不能预测任务将要占用的资源怎么办？
那么，能否设计出Reactive的负载均衡方法？能想到的办法有：

• worker机器反馈监控指标
• 基于限流，每台机器配置限流，超出后拒绝任务、master尝试投递其他。这方法还是要人配，不够reactive