发表于2018
一、存在的问题
Spark集群在存储介质（HDDs 和 SSDs）异构的问题，导致不同结点的读写速度不一致，没有充分地利用异构存储的优势。当前针对于异构环境下的调度，只考虑了计算资源，而忽视了存储设备异构性的问题。
二、提出的方法
2.1 创新点
考虑Spark集群上存储介质的不同对任务完成时间的影响，提出了对于异构存储介质集群存储感知的任务调度策略。
2.2 结果
实验结果显示，H-Scheduler能够降低Job 73.6%的执行时间。
三、背景&动机
- 支持异构存储介质的HDFS；
- 支持异构存储介质的HDFS和当前调度策略的匹配：
- 由于网速的提升，对于数据本地化的影响对于任务执行的影响在降低；
四、设计
H-Scheduler在调度决策同时考虑将数据本地化和存储介质类型这两个因素。
第一步 任务分类
H-Scheduler在调度之前应该知道处理每个任务的存储介质类型，根据任务的本地性和数据块存储介质的类型将任务进行分类，分为以下四种类型：
- SSD task
- remote SSD task
- local HDD task
- remote HDD task
四种类型的任务执行时间依次递增
将任务分成SSD中的任务和HDD中的任务两大类
第二步 任务优先级设置
根据四种任务类型来决定任务的执行顺序
任务的优先级为：
local SSD task > local HDD task > remote HDD task > remote SSD task.
第三步 节点的选择
在选择执行远程任务的时候，有以下三种策略：
- 随机选择
- 最多优先选择：选择拥有本地任务最多的节点
- 最少优先选择：选择拥有本地任务最少的节点
五、算法
算法1
适合的两个场景：
- 工作量是计算密集型的，任务数量很大；
- 能耗低要求较高，对于SLA截止时间要求较低。
六、实验
四种典型的工作负载：
- Wordcount(500GB)：CPU密集型任务
- Sort(400GB)：Shuffle密集型任务
- Grep(600GB)：I/O密集型任务
- TPC-H：I/O密集型任务
三种调度策略进行对比：
- Original:只考虑了数据本地化而没有考虑存储介质的差异；
- Storage-type：只考虑了存储介质的差异而没有考虑数据本地化；
- H-Scheduler：既考虑了数据本地化又考虑了存储介质的差异。
分别评估了两种job：
- Single job on cluster:
- Multiple jobs on cluster：同时运行三个job
影响H-Scheduler的三个重要参数：
- SSD 任务的比例：比例越高，性能越好
- SSD的副本数目：
- SSD task，remote SSD task和HDD task之间时间的比例
七、相关研究
任务调度在大数据处理平台上处理策略：
提升数据本地化程度
通过提升数据本地化的程度来提升大数据平台的处理性能
| 处理方法 | 文章 |
|---|---|
| 通过延迟调度来获得更高的数据本地化程度 | [11] |
| 从随机网络的角度考虑map任务本地化的问题，并提出一种新的排队算法，以同时最大化吞吐量并最小化重负载条件下的延迟。 | [24] |
| 通过复制文件的方式 | [12],[16] |
处理异构计算资源
| 处理方法 | 文章 |
|---|---|
| 首次考虑异构问题并采取一种静态方法来计算任务的进度 | [17] |
| 探讨落后者/异常值的原因，并在其生命周期的早期发展原因和资源感知技术可以更智能地处理异常值。 | [19] |
| 利用历史信息来调整Map和Reduce阶段的权重，以便更准确地估计任务执行时间 | [18] |
| 使用K-means算法对历史数据进行分类，来提升对于任务阶段权重评估的准确性 | [25] |
| 使用动态负载重新平衡（更快的节点获取更多数据）来调度任务 | [20],[21] |