Skip to content

Latest commit

 

History

History
26 lines (15 loc) · 4.39 KB

常见的调度算法.md

File metadata and controls

26 lines (15 loc) · 4.39 KB

调度算法

DRF

在Mesos和YARN中,都用到了dominant resource fairness算法(DRF),它不同于hadoop基于slot-based实现的fair scheduler和capacity scheduler,论文阅读:Dominant Resource Fairness: Fair Allocation of Multiple Resource Types

考虑在一个包括多种资源类型(主要考虑CPU和MEM)的系统的公平资源分配问题,其中不同用户对资源有不同的需求。为了解决这个问题,伯克利的几位大牛提出了Dominant Resource Fairness(DRF),一种针对不同资源类型的max-min fairness。并且在Mesos的设计和实现中评估了DRF,显示了它可以比slot-based 公平调度算法得到更好的吞吐量。

max-min fairness

它是针对单一维度资源的常用公平办法。其中一种理解方式是,先把资源平均分给各个用户,如果有资源超过用户需求,则没用到的部分在其他用户之间再平均划分,如此类推。集群调度场景中,通常按任务的粒度进行调度,那么分配资源给当前使用资源最小的用户的下一个任务即可。这也是最大最小公平名字的来源,即最大化最小的用户分配。

在任何共享的计算机系统中,资源分配都是一个关键的构建模块。已经提出的最通用的分配策略是max-min fairness , 假设每一个用户都有足够地请求,这种策略会给予每个用户一份均等的资源。广义的Max-min fairness包括权重(weight)的概念,用户可以获得与它的权重成正比的那一份资源。

加权max-min fairness的吸引力源于它的一般性和它能提供性能隔离的能力。加权max-min fairness模型可以支撑许多其他资源分配策略,包括优先级、deadline based allocation等。此外,加权max-min fairness确保隔离,一个用户能确保收到它的那份资源,而不管其它用户的需求。 鉴于这些特征,不同精确度的加权或非加权max-min fairness毫不意外地被大量已经提出的算法实现,如round-robin、proportional resource sharing、weighted fair queuing。这些算法已经被应用于不同的资源,包括链路带宽、CPU、内存、存储。 尽管已经在公平分配上做了大量地工作和实践,但目前为止主要还是集中在单资源类型的场景下。甚至在多资源类型的环境下,用户有异质资源请求,典型的资源分配做法还是使用单类型资源抽象。比如hadoop和Dryad的公平调度器,这两种广泛使用集群计算框架,在资源分配时使用插槽(slot),slot就是对节点资源按照固定大小进行划分而产生的分区。然而事实是集群中不同的作业队CPU、内存和IO资源有着不同的需求。

DRF是一种通用的多资源的max-min fairness分配策略。DRF背后的直观想法是在多环境下一个用户的资源分配应该由用户的dominant share(主导份额的资源)决定,dominant share是在所有已经分配给用户的多种资源中,占据最大份额的一种资源。简而言之,DRF试图最大化所有用户中最小的dominant share。 举个例子,假如用户A运行CPU密集的任务而用户B运行内存密集的任务,DRF会试图均衡用户A的CPU资源份额和用户B的内存资源份额。在单个资源的情形下,那么DRF就会退化为max-min fairness。

DRF有四种主要特性,分别是:sharing incentive、strategy-proofness、Pareto efficiency和envy-freeness。DRF是strategy-proof,用户不能通过谎报其资源需求来获得更多的资源。DRF是Pareto-efficient,意思是符合规则的前提下,系统的分配已经最高效,如果要增大一个用户的分配,则必然减少另一个用户的分配。最后,DRF是envy-free,用户不会妒忌其他用户的分配,因为其他用户的分配并不能使该用户跑更多任务。

Sharing incentive

意思是用户把自己的机器贡献给共享集群,好过自己搭小集群。可以这样理解,用户能跑的任务数量由Dominant Share决定,而最坏情况的Dominant Share是1/n(总共n个用户),与自己的小集群能跑任务数量一样;但是更多情况下,不同用户的Dominant Resource不同,像上面例子,A是重内存,B是重CPU,那么Dominant Share很可能大于1/n,像上面是2/3(大于1/2),这样在共享集群能比自己小集群跑更多任务。