任务调度（主讲人：陶阳宇）在线视频

介绍完系统架构后

我接下来给同学们

详细的介绍一下

任务调度和资源调度

分别是如何实现的

首先我们先看任务调度

任务调度的问题

来源于在云计算时代

数据太多高维度的数据

消费数据 位置数据

运动数据以及用来参考的

周围环境的数据

那海量的数据

如何进行并行化处理

在单机器PC时代

无论使用多线程

还是多进程

都解决不了问题

那谷歌公司在2014年

OSDI上的一篇论文

将函数式编程中的

Map Reduce函数的思想

引入到了分布式计算当中

形成了海量数据处理的

经典范式

也就是我们今天看到的

Map Reduce框架

Map Reduce框架可以用

图中这个做汉堡的

流程图来给同学们解释一下

我们做汉堡的时候

首先会准备一些材料

比如像面包粉

还有像洋葱 菠菜

等一些基本的原材料

那第一道工序

我们可以称之为MAP

它做的事情就是将

每个原材料进行离散化

进行切片

比如将面包切成不同的片

将洋葱 白菜都切成

各自所需要的形态

第二道工序

我们称之为Reduce

它是一个归约合并的过程

通过将两片面包片

以及其他的一些食材

拼装起来就组合成了

我们最终所需要的汉堡

所以这个例子

可以很形象的帮助我们理解

Map Reduce它的

分布式处理的思想

它的思想可以总结为

两个点第一个就是化整为零

第二个就是数据切片

这个过程当中

MAP起的作用

主要是将问题进行分解

而Reduce阶段

则是进行聚合

将分解后的基本元素

聚合成我们最终想要的结果

我们再来看一个

word count的例子

word count是一个

非常经典的问题

假设我们现在有很多

文本的文档

我们的任务是要统计出

文本中每个单词

出现的总次数

首先我们可以通过MAP操作

依次读取每个文件

并统计出每个文件中

单词出现的次数

比如对于第一个文档

经过MAP操作处理之后

每个单词例如

菱形出现过一次

第二个菱形也出现过一次

圆形出现过一次

三角形出现过一次

这样将文档转换成

单词以及次数这样一个

中间状态

其他的文档

通过MAP的处理依此类推

因此经过MAP

这个操作之后

所有的文档转换成一个单词

与次数的中间状态

接着Map taske（音3：26秒）

将它的结果发往下游的

Reduce操作

这个发往过程中

也会进行一部分的合并

例如第一个文档中

菱形出现了两次

圆形出现了一次

三角形出现了一次

进行了部分的归约

其他的文档处理过程

依此类推

最后我们可以实现

一个Reduce操作

进行最终的归约和合并

Reduce操作将中间结果

进行累加起来

我们可以看到菱形在

第一个文档出现两次

在第二个文档出现一次

在第三个文档出现一次

经过合并之后

最终的输出结果中

菱形出现的总次数

就是2+1+1也就是4次

其他的单词依此类推

从而最终得到

我们的最终结果

Map Reduce框架

是一个伟大的发明

它对于解决大规模的

线性问题具有普适性

那么Map Reduce

在建模的时候

有一些大家要注意的要点

首先一个MAP设计是关键

因为MAP是分解操作

它是将输入数据

从数据的表征空间

向最终的解空间的一个转换

并且这个解空间

应该是线性空间具备可加性

而Reduce操作

则是对中间的解空间元素

也就是MAP的输出

进行归约合并的操作

除了刚才的word count例子

其实Map Reduce

可以帮助我们解决生活中

更到的很多问题

比如我们想对全部的

学生的成绩进行一个统计

统计出每个人的平均分

还有像我们想统计一下

图书馆中

所有有关于自然科学的书本

还有系统中经常使用的

日志分析以及大家经常

使用的网页搜索

它背后的Page Rank的

计算过程也是可以

用Map Reduce来实现的

还有例如我们要计算出

一个图当中某一个节点

到其他所有节点的距离

介绍完Map Reduce的

框架之后

接下来我给同学们介绍一下

伏羲在做任务调度时的

一些实现细节

在架构图中

已经给大家介绍了

任务调度时主要有

向个角色者参与

一个是计算框架所需要的

APP Master

以及若干个APP Worker

那APP Master的责任

首先一个是向Fuxi Master

申请或者是释放资源

在拿到Fuxi Master

分配的资源以后

会调度相应的APP Worker

到集群中的节点上

并分配Instance到

APP Worker
这里Instance就是指

数据切片

APP Master同时还要负责

APP Worker之间的数据传递

以及最终汇总生成

job运行的一个状态

我们称之为job status

同时为了达到容错效果

APP Master还要负责管理

APP Worker的生命周期

例如当发生故障之后

它要负责重启这个

APP Worker

而APP Worker的职责

相对比较简单

首先它需要接收APP Master

发来的Instance

并执行用户的计算逻辑

第二它需要不断的向

APP Master报告它的

执行进度等等一系列的

运行状态

当然最主要的它还要负责

读取输入数据

将计算结果写到输出文件

这里的Instance就是指

输入数据的切片

前面给同学们介绍了

伏羲任务调度的流程和细节

在线上生产实践中

有很多实现细节的地方

需要仔细打磨

这里给大家分享三个

主要的功能

数据的Locality

数据的Shuffle

以及Instance重试

和backup instance
数据Locality顾名思义

locali指的是亲近性

数据locality是指调度时

要考虑数据的亲近性

也就是说APP Worker

在处理数据时

尽量从本地的磁盘读取数据

输出也尽量写到本地磁盘

避免远程的读写

要做到这一点

在对任务进行调度时

就需要考虑尽量让Instance

也就是数据切片

分配到数据最多的节点上

所对应的APP Worker来执行

这里给大家展示一个例子

我们有三个Instance

每个Instance在三个节点上

都有各自的数据分布

例如一号Instance

在第一个节点上有

50%的数据分布

在第二个节点有30%

第三个节点20%依此类推

那么要做到数据Locality

最终在做调度的时候

调度器会尽量将Instance

分配到它数据分布最多的

节点上进行计算

也就是图中高亮显示的地方

那么最终形成的调度结果

就是一号Instance

被分配到一号节点进行计算

二号Instance被分配到

二号节点进行计算

三号Instance分配到

二号节点

这点在学术研究上

称之为

Date locality based

instance scheduling

下面给同学们介绍一下

数据Shuffle
Shuffle是交叉传输的意思

数据Shuffle指的就是

APP Worker之间的数据传递

在实际的运行过程当中

APP Worker之间

是有多种传递形态的

像图中给出的这个例子

可能会存在一对一的情况

也就是说一个MAP

产生数据直接发往下游的

一个Reduce

也可能存在一对N的模式

一个MAP的输出结果

需要传递给所有的Reduce

还有更一般的M到N的模式

有些MAP需要

将输出发送给所有的Reduce

有一些MAP可能只需要

发给其中的部分Reduce

这种不同形态的传输模式

如果让用户去处理

代价非常大

因此伏羲这个

分布式调度系统

将这种数据传递的过程

封装成了一个

SDK Lib的形势

我们称之为streamling

这样一来用户不用关心

数据传递的细节

首先MAP进行运算

将结果直接交给

streamline
streamline底层

会根据不同的配置

将数据传给下游

计算任务的streamline

然后streamline

将接到的数据

交给上层的计算任务

比如这里的Reduce

在Instance的运行过程中

可能有多种原因

导致Instance失败

比如APP Worker进程重启了

或者是运行时

机器发生故障了

磁盘发生故障了

或者是数据在读取时

随机性的失败

种种原因都可能导致

一个Instance在运行时

最终失败

另外APP Master

还会监控Instance的

运行速度如果发现Instance

运行非常缓慢

容易造成长尾

所谓长尾就是指

Instance当中

极个别Instance由于外界

数据的原因

或者自身所在机器的CPU

运行比较高

会导致该Instance的

执行时间远远超过

其他的Instance

APP Master需要处理

这种情况

所以它会监控Instance的

运行速度

发现有些Instance

非常缓慢之后

会在另外的APP Worker上

同时运行该Instance

也就是说

同时会有两个APP Worker

在处理同一份数据

APP Master会选取

最先结束那一份的结果

为最终结果

那么APP Master如何判断

一个Instance运行缓慢呢

有下列几种依据

第一点该Instance的

运行时间超过了其他

Instance的平均运行时间

第二点它的数据处理速度

低于其他的

Instance的平均值

第三个当然也要考虑

目前已完成的Instance比例

这个是防止

在整个任务运行初期的时候

可能会误判

这种技术称为

backup Instance

也就是有一份备份执行

以上我给同学们介绍了

飞天分布式调度系统

在解决任务调度时的

设计要点和技术细节

希望能帮助同学们

加深对分布式系统的理解

以及了解在真实的

生产环境中分布式系统

考虑问题的角度