一、资源调度策略

多用户多作业的环境下，如何将集群资源在它们之间进行分配，需要特定的策略。

• FIFO
• 公平调度器
• 能力调度器
• 延迟调度策略
• 主资源公平调度策略

1. FIFO

• 最简单的资源调度策略。
• 提交的作业，按照提交时间先后顺序，或者优先级次序，将其放入线性队列相应位置，先进先出调度和分配资源。
• 缺点：多用户场景下，新加入的作业容易出现长时间等待调度的现象。

2. 公平调度器

• Facebook为Hadoop开发的多用户多作业调度器。
• 用户的任务分配到多个资源池（pool）。
• 每个资源池设定资源分配的最低保障和最高上限。
• 管理员可以指定资源池的优先级。

• 调度过程：

                1. 根据每个资源池的最低保障，将部分资源分配。

                2. 按照资源池的指定优先级将剩余资源，按照比例分配给各个资源池。

                3. 各个资源池中，按照作业优先级或者公平策略，将资源分配给各个作业。

3. 能力调度器

• Yahoo为Hadoop开发的多用户多作业调度器。
• 与公平调度器相比，其更强调资源在用户之间，而非作业之间的公平性。
• 面向用户划分成多个队列，每个队列设定资源分配的最低保障和使用上限。
• 当一个队列的资源有剩余时，可以暂时将其分享给其他队列。
• 调度时，优先将资源分配给资源使用率最低的队列。
• 队列内部按照FIFO调度。

4. 延迟调度策略

• 不是一种独立的调度方式，作为其他调度策略的辅助措施来增加调度的数据局部性，以此增加任务执行效率。
• 对于当前要分配资源的任务i，如果当前资源不满足数据局部性，那么可以暂时放弃分配公平性，跳过i分配资源给其他任务。
• 如果i在被跳过k次后仍然等不到满足局部性的资源，则放弃数据局部性，启动i。

5. 主资源公平调度策略DRF

• Mesos中央调度器采用的公平调度策略，是最大最小公平算法的一个具体体现。
• 最大最小公平算法：最大化目前分配到最少资源的用户或者任务的资源量。用来对单个资源进行公平分配。
• DRF将其扩展到了多个资源的公平分配场景下。
• 对于每个用户计算分配给他的所有资源的各自分享量，一个用户各个资源分享量中的最大值被称为“主分享量”，对应的资源为“主资源”。
• DRF旨在使得不同用户的各自“主分享量”最大化地保持公平。

二、负载均衡

1. 概念：

• 含义：将负载（工作任务）进行平衡、分摊到多个操作单元上进行运行。
• 在并行系统中，使各个节点尽量均衡的分配工作任务的技术。
• 通过在处理机之间均衡的、合理的分配计算任务，以获得最大可能的执行速度。
• 通过调度程序实现。
• 调度的目的：通过将任务正确的分配给各个处理机，并使其按照一定顺序执行，以尽可能少的时间完成并行应用任务。
• 静态调度中，调度通常在编译时进行。并行程序的特点在程序执行之前都是已知的。
• 动态调度中，调度在程序执行时进行。并行程序的特点在程序执行之前知道的很少。使程序的执行时间和调度时间尽可能最小。

2. 静态负载均衡（平衡）

进程执行之前所进行的负载均衡称为静态负载均衡。

静态负载均衡的优点：

• 一般比动态负载均衡省时。
• 一般在每个处理机上仅生成一个进行，从而减少了进程建立、同步和终止的开销。
• 可用来评估并行算法的加速比和性能。

利用静态调度的并行程序可以由一个有向无回路图G =（V，E）来表示：

• 一个顶点表示一个子任务。
• 一条边表示任务间的依赖关系。
• 顶点的权值为计算开销。
• 有向边的权值为相邻点的通信开销。

 表调度

最优调度：对给定一个任务图和处理机数，使任务总的执行时间最小化的调度。

关于最优调度的结论：

• 如果所有子任务执行时间相同，且任务图是一个森林：算法可在多项式时间能找到最优调度。
• 如果所有任务执行时间不同，或有两个以上处理机：在最坏情况下，寻找最优调度的最好算法需要指数时间。

3. 动态负载均衡（平衡）

• 在进程的执行过程中完成的负载平衡。
• 通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，来消除系统中负载分布的不均匀性。
• 虽然会有额外开销，但在负载不易均衡的情况下，它比静态～更有效。

 一致性哈希算法

1997，麻省理工学院提出。

1. 把服务器通过hash算法映射到环上；
2. 把URL通过hash算法映射到环上，按顺时针方向找到处理该URL的服务器；
3. 服务器增删，对系统影响较小，架构扩展性强。

三、常用系统示例

当前较为有名的开源资源管理与调度系统：

• Mesos：Apache下的开源分布式资源管理框架，被称为是分布式系统的内核。最初是由加州大学伯克利分校的AMPLab开发的，后在Twitter得到广泛使用。
• YARN：hadoop 2.0的重要组成部分，也被称作MRV2，全称“另一种资源协调器”，是一个独立的资源管理系统。

1. Mesos

1.1 基本范型

• 基本框架：框架调度器+中央调度器 典型的两级调度器
• 中央调度器采取极简功能和极小接口，只根据一定策略决定分配给各个框架多少资源，将数据局部性保证等具体资源调度策略下推到各个框架。
• 一方面减少中央调度器的负载，增加调度效率；
• 另一方面使得中央调度器为了支持新出现的框架而改动最小化，增强可扩展性。

1.2 中央调度器部分

• 中央调度器由多个主控服务器（Master）构成，通过ZooKeeper来保证Master故障时备用主控服务器（Standby Master）可以快速接管工作，增加整个系统的健壮性。
• Master使用“资源供应”，来将集群内的资源分配给各个计算框架，代表集群内可用的资源列表，Master通过列表决定为每个框架提供多少资源，每个框架自身的二级调度器做更细致的任务间资源分配。
• 中央调度器的调度策略模块设置成可插拔的，系统管理者可以按需设置中央调度策略。

1.3 计算框架部分

• 每个计算框架需要向Mesos注册两个接口：框架调度器（scheduler）和执行器（Executor）。
• 框架调度器起到二级调度器中的第二级调度功能。
• 执行器从节点（Slave）中执行具体任务；执行器相互之间的资源隔离由Mesos通过Linux Container来获得保证。

 1.4 Mesos 数据局部性&Filter

问题：Mesos不支持计算框架指定资源要求或者约束条件，计算框架只能被动接受被分配的资源，这样很难保证数据局部性。

方案：框架在接收到“资源供应”后，可拒绝接受不满足需求的资源分配而等待后续资源分配。

——缺点：与框架的反复交互降低资源分配效率。

方案：

• Mesos中增加过滤器机制。
• 计算框架可以向中央调度器注册“过滤器”，过滤器对框架希望接收的资源做出了描述。
• 如“只从机器列表L中提供资源“。
• 增加中央调度器和二级调度器之间的交互效率。

2. YARN

 2.1 概念

• YARN是个典型的两级调度器。
• ResourceManager（RM）负责整个集群的资源管理功能，类似于中央调度器。
• 每个任务单独有一个ApplicationMaster负责完成任务所需资源的申请管理与任务生命周期管理功能，类似于二级调度器。
• AM负责向RM申请作业所需资源，并在作业的众多任务中进行资源分配与协调。