论文笔记04：A Heterogeneity-Aware Task Scheduler for Spark

发表于2018

一、解决的问题

大数据平台的应用没有关注到多维度的异构场景，导致在调度资源的时候，应用和硬件特性之间存在着本质上的不匹配问题。

二、提出的方法

2.1 创新点

提出了一种异构感知的任务调度系统——RUPAM，同时考虑任务级别的资源特征和硬件层面的特征，还能够保持数据本地化。RUPAM使用一种简单但高效的启发式去决定主导型的调度因素，将一个任务放置到特定的stage上。

2.2 结果

RUPAM对于Spark标准的调度器来说提升了62.3%的性能

三、背景

Spark调度

当前的Spark分为两个级别的调度：

• 应用级别调度：通常使用一些集群管理器来实现，例如内置的standalone集群管理器和外部的Mesos、YARN等，这些管理器通常会抽象硬件属性为CPU核数和内存大小。最主要的局限性体现在这些资源管理器不能够动态地满足应用的需求。
• 任务级别调度：当前的任务调度器只是将一个任务分配给一个CPU的核上，只考虑了数据本地化的因素。现有的异构性感知调度程序仅关注底层节点的异构性，并且通常假设同一Map / Reduce阶段中的所有任务具有相同的特征，如我们所示，并不总是成立。

前置研究

为了评估当前Spark的调度器，进行了了一些实验，通过这些实验得到的结论：

• 在单个应用上的不同stage的资源利用率是不同的：当前Spark调度器只是静态地将CPU核和存储器的一部分分配给给定应用程序（如当前调度程序中的情况）而没有考虑所需资源中的这种多样性和不一致性。
• 单个stage存在任务偏差：当前异构感知调度器假设同一个stage上任务有着相似的特征，表现性能也是相同的。

这些实验表明，即使在应用程序生命周期内，Spark应用程序也可能需要不同的资源， 其中的任务也具有不同的特征。

四、设计

A. 系统架构

RUPAM是一种任务级别的调度器，与应用级别和作业级别的调度器一起工作。

• Resource Monitor(RM)：资源监控器，负责系统资源的实时监控。它有一个运行在Spark的Master和Worker的监视器，收集器报告每个节点上资源的使用情况，例如CPU、内存、网络、I/O和GPU等。监视器负责从这些节点上收集和记录这些信息。还能够拓展收集资源性能上的更多信息。
• Task Manager (TM)：任务管理器，跟踪任务资源使用情况以确定任务的任何资源瓶颈。
• Dispatcher：实现RUPAM的主要逻辑，例如决定启动每个节点上executor的大小，将每个任务匹配合适的节点，对于特定节点启动任务的数量，基于多个维度调度任务。

利用TM和Dispatcher来取代Spark内置的TaskScheduler，不单单考虑数据本地化，而是同时考虑任务和节点的资源特性来调度任务。

B. 实时资源监控和任务监控

对于同一个任务的运行每个阶段的瓶颈期可能是不一样的，这样在任务整个生命周期上跟踪节点的资源使用情况为了低延迟来决定将任务分配到最优的节点上进行执行。

1. 资源监控：

   RUPAM利用心跳机制周期性地获取更多维度的硬件信息，使用一个对每个类型资源的优先队列。RUPAM只需要将节点中的一小部分进行排序，并且在下一轮调度的时候清空队列。通过这样的方式，能够保持较小的队列来降低排序过程的时间复杂度。

2. 任务监控：

   为了给定的节点选择一个合适的任务，RUPAM也需要根据任务的特性来进行决策。RUPAM使用一个数据库来存储周期性的数据中心的任务特性。为了将分辨在同一个stage资源需求的不同，TM为每种类型的资源保持一个队列。为了解决如何管理频繁的数据库操作，RUPAM使用一个帮助线程来辅助。

C. 任务调度

优化目标是：最小化对所有机器的所有任务的总执行时间

当前最流行的解决方法是列表调度算法，这是一种贪心算法，可以将任务映射到可用的机器而不会引入空闲时间。由于列表调度提供了具有良好的理论界限的实际解决方案，RUPAM采取了一种基于贪心的启发式算法。考虑的因素有：

• 硬件节点的容量（SSD,GPU）
• 每个任务的资源消耗
• 节点中每个资源的资源争用
• 运行在同一节点的任务数量
• 数据本地化

1. 调度策略

Dispatcher在task队列和资源队列的帮助下匹配任务，在RM填充资源队列之后，RUPAM以轮询的方式一次从每个资源队列中取出一个节点，以确保没有任何单一资源类型的任务饥饿。这种启发式贪心策略找到一个具有最佳容量和最低争用资源R的节点N，然后将N调度到任务T，其中R作为其先前运行中的瓶颈，如今N为T提供了最佳位置。RUPAM没有尝试对每个任务寻找一个全局最优的调度策略，因为这样可能会造成一个比较大的调度延迟，效果可能适得其反。将任务“锁定”到提供最佳观察性能的节点上，还可以防止由于任务特征的临时波动而在节点之间来回移动任务。

2. 资源分配

Spark在启动executor的时候会为其设置一个固定的CPU核数和内存，这种静态的配置其实是低效的。

• 首先，在异构环境下，节点拥有不同的内存大小和CPU核数；
• 第二，基于一个节点上的CPU核数来决定任务的slot其实是不准确的；
• 通过超提交一些具有空闲资源的节点和用适当的任务匹配节点，RUPAM可以重叠具有不同资源需求的任务。

3. 落后的任务（Straggler）和任务的重定位

为了弥补Dispatcher可能存在的次优决策，RUPAM还与最近引入的Spark推测执行系统一起工作，以在可用节点中启动Straggler的副本。当完成的任务数量达到一个阈值（默认是总数的75%），该推测系统就会搜索那些耗时超过已完成任务平均执行时间的一个系数的任务并且将其标记为Straggler任务。Straggler的副本将会在下一个可用节点上进行计算。除了被Spark检测为标准Straggler之外，RUPAM同样也会根据异构环境检测Straggler。

为了避免JVM中的OOM异常，RUPAM还采取了一种激进地策略检测内存的straggler。首先，只要RM检测到一个节点的可用内存较低的时候，它就发送消息给TM，并且通过检测当前正在运行的任务，TM标记那些占用较多内存的任务为Straggler，并终止这些任务。在标记之后，将这些任务的副本发送到TM，TM会根据这些任务的特性来确定其瓶颈并且将其再次放入任务队列。Dispatcher又可以再次将这些任务分配到适合的闲置节点上。

五、目标和设定

设定

每台机器上处理任务的时间根据机器变化

优化目标

最小化最大完工时间

论文笔记06：Security and privacy aspects in MapReduce on clouds A survey

一、介绍

云计算提供三种类型的服务：

1. IaaS；
2. PaaS；
3. SaaS

云计算可以分为：

1. 公有云；
2. 私有云；
3. 混合云

MapReduce在最初设计的时候，并没有考虑到安全和隐私方面的问题。一个安全的MapReduce框架要解决以下几种攻击：

• 身份验证；
• 保密性（窃听和中间人攻击）
• 数据篡改
• 硬件篡改
• 软件篡改

安全性和隐私性之间的另外区别在于安全性更多是二元问题，即攻击成功与否，而在隐私设置中是关注于数据隐私与框架利用之间存在权衡。

二、挑战

对于带有安全和隐私方面的MapReduce存在着一些挑战：

• 输入的数据的大小和这些数据的存储：分布式的存储带来的数据存储隐患；
• MapReduce计算的高度分布式特性：更多的数据副本给数据安全带来更多的隐患，在MapReduce中识别带有攻击性的mapper或者reducer不是一件容易的事情。
• 数据流：根据数据的敏感性来不同地处理数据，数据会在存储节点和计算节点之间移动；MapReduce的不同计算阶段可能会在不同类型的云服务上进行计算；
• 公有云的黑盒特性支持着MapReduce
• 混合云：MapReduce是设计在单一云环境下使用的，对于敏感性数据和非敏感性数据的分配增加了MapReduce使用的挑战；
• 可扩展性，容错机制和透明性：安全和隐私方面的机制不应该影响MapReduce的效率、拓展性、容错机制，对于用户的使用应该是透明的。
• 经济问题：影响MapReduce在公有云上有三种因素，分别是存储、通信代价和计算时间，安全和隐私机制的也应该经济型地加入。
• 不可靠的数据接入：对于MapReduce的安全和隐私算法应该应对损坏的甚至是带有攻击性的代码，保护数据，并限制带有损坏性的Mappers和Reducers的数据接入。

三、要求

3.1 MapReduce的安全威胁

在公有云环境下，MapReduce处理的分布式的副本数据有着很大的被攻击的可能

• 冒充攻击：会造成数据泄露、计算篡改和在数据上的错误计算，会造成用户在资费上的损失；
• 拒绝服务（DoS）攻击：Dos攻击可能会使得节点的功能失效和无法访问，可能造成集群的网络过载和框架的失效；
• 重放攻击：通过恶意的欺诈性地重复或拖延正常的数据传输；
• 窃听：在未经批准的情况下，计算结果在中间被截获；
• 中间人攻击：数据在传输过程中会被恶意修改、毁坏；
• 拒绝：当节点的mapper或者reducer被错误地拒绝处理时，会发生拒绝攻击。

3.2 MapReduce中的安全要求

• Mappers和Reducers的身份验证，授权和访问控制：只有被授权的用户才能权限够处理这些mapper和reducer，对于授权的攻击是冒充攻击和重放攻击；
• 数据、mapper和reducer的可用性：数据、mapper和reducer对于授权的用户是没有延迟的可用性，对于这些方面的攻击对于处理时间都是有影响的；
• 计算和数据的保密性：为了确保机密性，在传输期间和在公共云本身上传输之后，不能拦截计算和数据。
• 计算和数据的完整性：计算的完整性是指公平传输（指的是从用户位置到计算位置的MapReduce计算）以及Mappers和Reducers的执行。
• 验证输出：验证确保了输出的完整性、正确性、及时性；
• 对计算和数据的核算和审核

3.3 对于MapReduce安全的对抗模型

• Honest-but-curious adversary：会增加一定的额外计算；
• Malicious adversary：应对窃取、毁坏、修改数据，可以分为两类：
  • non-collusive ：独立工作，不需要与其他的协作；
  • collusive：在给出输出之前要与其他所以的一起通信；
• Knowledgeable adversary：具有提升安全性的能力；
• Network and nodes access adversary：

3.4 MapReduce安全的解决方法

论文笔记05：SABA A security-aware and budget-aware workflow scheduling strategy in clouds

发表于2014.7

一、解决的问题

对于云环境下工作流的应用调度策略中，解决当前研究中忽视的带有安全要求和例如像内存，存储介质容量这些其他硬件资源的问题。

二、提出的方法

2.1 创新点

由于考虑了安全和花费提出了“不可移动数据集”的概念用来约束某些数据集的移动，基于这个概念，提出在了一种安全感知和预算感知的工作流调度策略，为用户提供更加端的完工时间和同样安全的云服务。

2.2 主要贡献

• 提出了SABA算法，在给定预算下在保证安全的基础上提供给用户更短的完工时间；
• 在安全约束下拓展了多维度的计算资源的考虑，例如网络带宽、内存、存储等；
• 提出了“不可移动数据集”的概念

三、相关研究

现有研究不能应用到带有安全约束的在云环境下的工作流应用的三点原因：

1. 资源竞争可能会对提交任务及其所需安全服务的计算时间和金钱成本的影响比较大；
2. 现有研究考虑的所有数据都是可移动的；
3. 现有云服务提供商都是共享基础资源的，与未知租户共享基础架构可能是某些工作流应用程序的主要风险，并且需要高度保证与逻辑分离的安全机制的强度。

发表于2018

一、存在的问题

Spark集群在存储介质（HDDs 和 SSDs）异构的问题，导致不同结点的读写速度不一致，没有充分地利用异构存储的优势。当前针对于异构环境下的调度，只考虑了计算资源，而忽视了存储设备异构性的问题。

二、提出的方法

2.1 创新点

考虑Spark集群上存储介质的不同对任务完成时间的影响，提出了对于异构存储介质集群存储感知的任务调度策略。

2.2 结果

实验结果显示，H-Scheduler能够降低Job 73.6%的执行时间。

三、背景&动机

• 支持异构存储介质的HDFS；
• 支持异构存储介质的HDFS和当前调度策略的匹配：
• 由于网速的提升，对于数据本地化的影响对于任务执行的影响在降低；

四、设计

H-Scheduler在调度决策同时考虑将数据本地化和存储介质类型这两个因素。

第一步 任务分类

H-Scheduler在调度之前应该知道处理每个任务的存储介质类型，根据任务的本地性和数据块存储介质的类型将任务进行分类，分为以下四种类型：

1. SSD task
2. remote SSD task
3. local HDD task
4. remote HDD task

四种类型的任务执行时间依次递增

将任务分成SSD中的任务和HDD中的任务两大类

第二步 任务优先级设置

根据四种任务类型来决定任务的执行顺序
任务的优先级为：

local SSD task > local HDD task > remote HDD task > remote SSD task.

第三步 节点的选择

在选择执行远程任务的时候，有以下三种策略：

1. 随机选择
2. 最多优先选择：选择拥有本地任务最多的节点
3. 最少优先选择：选择拥有本地任务最少的节点

五、算法

算法1

适合的两个场景：

1. 工作量是计算密集型的，任务数量很大；
2. 能耗低要求较高，对于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之间时间的比例

七、相关研究

任务调度在大数据处理平台上处理策略：

提升数据本地化程度

通过提升数据本地化的程度来提升大数据平台的处理性能

处理异构计算资源

发表于2018.7

一、解决的问题

Spark集群在反网络犯罪中的能耗问题

二、提出的方法

2.1 创新点

为了避免服务级别协议违反执行时间，提出了一种最优的任务调度算法，其具有通过权衡执行时间和能量消耗的最后期限约束，目的是去最小化大数据处理中的能耗问题。该最优算法能够找到接近最优的任务调度，以在小的shuffle分区中权衡消耗的能量和响应时间的优势。

2.2 结果

对比Spark内嵌的FIFO和FAIR算法，能耗上都有优化。

三、动机

• 对于数据中心，不需要一味降低任务的执行时间。而在是截止完成时间之前，只需要提供按需的服务，更多的关心是能耗上的优化。

四、相关工作

应对上述三个挑战的三种应对策略：

• Spark的executors为了及时满足它们资源预留应将被放置到合适的节点上，避免太长时间的等待和低资源利用率；
• 分配用于减少任务的资源应根据其随时间变化的需求进行重新平衡，以避免在将任何Spark应用程序提交到群集时浪费资源；
• 在考虑Spark和MapReduce应用程序的位置感知的时候,为了减少局部性感知的竞争,Spark和MapReduce应用程序的任务分配策略都应该优化。

五、算法

算法1

适合的两个场景：

1. 工作量是计算密集型的，任务数量很大；
2. 能耗低要求较高，对于SLA截止时间要求较低。

算法2

算法B权衡能耗和执行时间，特别对于小shuffle的分区的情况下。

在小分区的情况下，算法B将任务分配给集群中最佳的一半执行程序，并尝试平衡在执行程序的另一半中花费的执行时间。

算法3

算法3将所有任务分成两个集合：

• Set0：包含所有需要被探测的任务和当前p和e为0的任务；
• Distribute：包含那些不需要被探测的任务。

RunTimeEachExe：记录着最优部分的执行时间

六、实验

基于HiBench的基准实验，在三种工作负载上实验：

• Sort
• TeraSort
• PageRank

七、结果分析

算法B在保证有效降低能耗的前提下，优化了算法A的执行时间。因为基于贪心策略的算法A尽可能地将任务分配给评估标准的最佳过程，导致单个节点的过载并因此导致总体执行时间的增加。

算法B使得Shuffle分区的数量从10到40变化，确保可以使用集群中一半的执行程序。因此，算法B减少了单个节点上的负载，并且还加快了作业完成时间。

算法B的两点改进：

• 任务分配策略
• 不考虑数据局部性，以确保任务可以均匀地分布到最佳的一半过程

总而言之，算法B更加适合的场景：

• 工作负载更少的任务
• SLA的截止时间要求较高，节能要求较为宽松