教育数字化知识图谱

策略之优先级和抢占

每个Job在提交时会带一个priority值（整数值），该值越小优先级越高；相同优先级按提交时间，先提交的优先级高；FuxiMaster在调度时，资源优先分配给高优先级的Job，剩余的资源继续分配给次高优先级Job。

如果临时有高优先级的紧急任务加入，FuxiMaster会从当前正在运行的任务中，从最低优先级任务开始强制收回资源，以分配给紧急任务，此过程称为“抢占”。抢占递归进行，直到被抢任务优先级不高于紧急任务，也就是不能抢占比自己优先级高的任务。

策略之公平调度

公平调度策略是指当有资源时Fuxi Master依次轮询地将部分资源分配给各个Job，它避免了较大Job抢占全部资源导致其他Job饿死现象发生。公平调度首先按优先级分组，同一优先级组内的平均分配，如果有剩余资源再去下一个优先级组进行分配，依此类推。

配额

配额是资源分配时的第三个策略，通常是按照不同的业务进行区分，多个任务组成一个组，例如淘宝、支付宝等；集群管理员会设立每一个组的资源上限，意味着这个组最多能使用这么多CPU、Memory、磁盘等，该上限值称为Quota；每个组的Job所分配的资源总和不会超过该组内的Quota，当然如果每一个组内没有用完的Quota是可以分享给其他组的，会按照Quota的比例进行均分。

容错机制

在大规模进程集群中故障是常态，这些常态会来自硬件，比如 主板、电源、 内存 条；也可能来自软件，比如进程有Bug导致进程Crash，机器故障导致性能慢。因此，分布式调度必须具有容错机制，以保证正在运行的任务不受影响，并对用户透明，能够从故障中恢复过来，保障系统的高可用。下面将从任务调度的Failover和资源调度的Failover两个方面介绍。

AppMaster 进程重启后的任务调度Failover

每个计算任务有自己的APP Master，如果APP Master进程发生了重启，那其重启之后的任务调度如何进行Failover呢？这里采用了Snapshot机制，它将Instance的运行进度保存下来，当APP Master重启之后会自动加载Snapshot以获取之前每个Instance的执行进度，然后继续运行Instance；当APP Master进程重启之后，从APP Worker汇报的状态中重建出之前的调度结果，继续运行Instance。

[b]FuxiMaster 进程重启后的资源调度Failover[/b]

另一种情况是Fuxi Master发生了Failover。Fuxi Master Failover起来之后需要重建内部状态，该状态通常分为两种：一是Hard State，主要是之前提交的Application配置信息，如不同的Job配置参数等，它们来自于Fuxi Master写的Snapshot；另一类是Soft State，Fuxi Master会收集来自各个Tubo以及APP Master的信息重建出自己的状态，这些信息包括机器列表、每个APP Master的资源请求以及之前的资源分配结果。

Fuxi Master 进程重启之后的资源调度过程如图4所示，首先会从Checkpoint中读取出所有Job的配置信息；同时会收集所有的Tubo以及APP Master上报上来的关于资源分配的结果，如CPU多少、Memory多少等等。

规模挑战

分布式系统设计主要目标之一就是横向扩展（scale-out），目前阿里云飞天在2013年时已支撑单个集群5000个节点、并发1万个任务。在做横向扩展设计时，需要注意两个要点：一是多线程异步；二是增量的资源调度。

多线程异步

多线程异步是编写分布式程序一个非常重要而且常用的技术手段。在网络通信模块中，每个APP Master都需要跟Fuxi Master进行资源通信，同时也需要跟多个Tubo进行通信以启动它们的APP Worker。APP Master处理网络通信的过程称之为RPC，RPC通信时必须采用线程池来处理。如图5中采用四个线程池来处理这些消息。由于Fuxi Master是一个中控节点，而Tubo的数量非常众多，如果将这些消息都在同一个线程池中处理，则Fuxi Master的消息有可能会被大量的Tubo消息阻塞（对头阻塞问题）。为了解决该问题，在伏羲系统当中设立了一个独立的线程池来处理Fuxi Master的消息；另外一个线程池来处理Tubo的消息，将线程池进行分开，也称之为泳道；独立的泳道能有效解决Fuxi Master的消息被对头阻塞的问题。

增量的资源调度

伏羲解决规模问题的另一个技术点是增量。目前，伏羲采用增量的消息通信和资源调度，下面通过具体例子，来介绍伏羲所采用的增量资源调度的协议。

图6左侧是中控节点Fuxi Master；右边为某一个APP Master，如果说APP Master需要1000份资源，最直接的一种实现方式是将“我要1000个资源”这样的消息直接发送给Fuxi Master；Fuxi Master在接到消息之后可能当前的剩余资源只有200份，它将会“我分配给你200”这样的消息发送给APP Master；那APP Master还会继续发送消息“我还要剩余的800”，Fuxi Master回复“此时没有资源，我分配0个给你”；则APP Master在下一次通信的时候需要继续发送“我还要剩余的800”……依此类推，可能某一个时刻Fuxi Master还能分一点资源下来。这就是最直观的全量消息通信，每一次APP Master提出请求时都要指明它总共需要多少。

而在伏羲的实现当中为了减小通信量和不必要的开销，采用了增量的语义。首先APP Master发送一个请求“我要1000个资源”，Fuxi Master收到之后将当时空闲的200个资源返回给APP Master；之后APP Master无需再提交请求说我还需要800，因为Fuxi Master会将这1000个请求记录下来等到某一时刻又有更多的资源，比如150个资源释放，它直接将150个分配结果发送给APP Master即可。这期间APP Master无需再发多余的网络通信。

安全与性能隔离

在分布式系统当中通常有多个用户在执行自己的计算任务，多个任务之间需要互相隔离、互相不影响。飞天伏羲实现了全链路的访问控制，采用了两种访问控制进行安全的验证，一种是Capability，指通信双方基于私钥进行解密并验证的一种方式；还有一种称为Token的方式，这种方式需要通信的双方临时生成基于私钥加密的口令，在通信时进行验证。

两种方式最大区别在于口令生成的时机，Capability方式是在通信之前就已经加密好；而Token是需要在通信时临时生成。

两种方式使用于不同的场景，如图7所示FuxiMaster与Tubo通信采用的是Capability方式，因为这两个角色在集群部署时就已启动，可以事先进行加密生成好Capability；FuxiMaster与APP之间是采用Token的方式，这是因为APP与FuxiMaster进行通信时，当每个任务执行完计算之后会退出；在进程与进程之间，伏羲采用了沙箱的方式将不同的进程进行隔离开、互不干扰。

除了安全的隔离之外，还需要考虑性能的隔离。目前伏羲采用的几种技术手段：Cgroup（Linux LXC）、Docker container、VM等。这几种技术的隔离性、资源配额/度量、移动性、安全性的比较如图8所示，不再一一叙述。

伏羲目前采用的隔离技术是基于Docker和LXC混合部署的方式，之所以抛弃虚拟机的方式，是因为其性能损耗太多。当运行计算任务时，如果完全放在虚拟机当中，它的IO以及CPU时间片会受到很大的影响，会降低任务的执行效率。在目前阿里的生产环境中，实践发现基于Docker和LXC的隔离技术已经可以很好地满足需求。

分布式调度的发展方向

随着计算能力和数据量的持续增长，分布式调度未来可能朝向以下几个方向发展：

在线服务与离线任务混跑。云计算最终的目的是降低IT成本，最大限度地利用单台PC的CPU处理能力，所以未来的趋势一定是在线服务与离线任务能够在同一物理集群上运行从而实现削峰填谷效果、最大化提高集群利用率。但是由于两种任务的特点不同，在线运用对于响应时间要求很高，而离线运用则对调度的吞吐率要求比较高，因此混跑会带来性能隔离与资源利用率之间的矛盾。

实时计算的发展，Map Reduce是一个很伟大的框架，但其是为数据量一定的批处理而设计的。随着云计算越来越普及，很多计算形态需要实时拿到计算结果，并且其输入数据可能是不间断的。目前，伏羲也已经开发出了实时的计算框架——OnlineJob，它可以提供更快的执行速度。

更大的规模，目前已能够支撑5000台的节点，随着计算量越来越大，客户的需求越来越多，需要进一步优化伏羲系统，能够支撑起1万、5万、10万等更大规模单集群，同时能够支撑更多的并发任务。