|
DRF资源分配是一种改进的maxmin fairness算法，能在多资源类型的集群环境中进行资源的公平分配，DRF是一种基于“主导份额（Dominant Share）”的多资源公平分配策略[17]。DRF公平分配算法具有4个性质[20]： 1） 鼓励共享（Sharing Incentive）。即集群中的上层应用之间通过共享自己的资源而不是独占资源来达到更高的资源利用效率。如：在一个具有n个计算任务的集群节点中，每个计算任务最多只能分配1/n的资源。 2） 欺骗屏蔽（Strategyproofness）。DRF能够防止计算任务谎报资源需求量，企图通过欺骗的手段而获取更多资源的行为。 3） 无嫉妒性（Envyfreeness）[21]。任何的计算任务都不能在获得计算资源后，通过已有的资源，去获得（或交换）另一个任务的资源。 4） 帕累托效率性（Pareto Efficiency）。集群中的所有计算任务都不能够在不减少其他任务的资源拥有量的前提下增加自己的资源拥有量。 DRF算法的核心思想是根据每个计算任务的资源需求向量和系统资源总向量，求出各个计算任务的主导份额。该主导份额所对应的主导资源是该计算任务最重要的计算依据。通过平衡各个计算任务的主导份额，来确定每个计算任务的子任务数量，最终得到每个计算任务的资源配额向量。DRF算法描述如下： 1.2 DRF算法的不足 在实际的集群环境中，集群中的计算机可能不是同一时间采购，或者机器品牌及机器型号之间存在着差异。在实际的资源分配过程中，即使分配相同数量的资源，但是由于节点之间的性能差异，分配方案之间存在较大的差异，将会有悖公平性原则[12]。DRF算法并没有考虑这种因计算资源性能的差异而导致的资源分配不公平性的问题，即使分配相同数量的资源，性能高的资源在任务的执行效率上比性能差的资源高。但是在DRF分配算法中，主导份额的计算只与资源数量有关，而与资源的质量无关。计算任务i的主导份额如式（2）所示： 式中：j表示资源类别，k表示资源种类数量，Rj表示资源类别j的资源总量，Wi表示计算任务的权重，Rui， j表示计算任务i已分配的j类别资源总量。 根据式（2）可知计算任务i的主导份额为该计算任务已获得的各类型资源与系统中该类型资源总量的比值中的最大值，如果计算任务存在加权，则主导份额与权重成反比。式（2）中无法体现出集群中节点之间的性能区别。如果有一个计算任务拿到大量的优质资源，而另一个拿到大量的劣质资源，虽然它们主导份额相同，但任务实际的执行效率和运行时间却相差甚远，这将导致资源分配的不公平，这种情况违反了DRF算法的Envyfreeness性质。 2 meDRF分配算法 本文提出的meDRF分配算法，是在DRF算法基础上增加了机器性能评估影响因子，使得计算任务有均等的机会获得优质计算资源和劣质计算资源，而不是长期持有优质或劣质计算资源。本算法的核心思想是：首先给每个集群节点的计算机进行性能评估打分并按照所得分值从小到大排序，再计算出每个计算任务的主导份额并从小到大排序，然后交替使用优质资源、劣质资源为计算任务的子任务进行资源分配，尽可能地使所有计算任务的主导份额趋向于平衡。 假设集群环境中存在n个计算节点，Qk表示机器k的性能评估得分，ηk代表机器k的性能评估得分与平均得分之比，Si表示计算任务i的主导份额，Rkj表示机器k上j类型资源的总量，Ruki， j表示计算任务i在机器k上已经分配的j类型资源数量，Rck， j表示机器k上j类型资源可分配的数量，Wi表示计算任务i的权重。 在Mesos中，使用框架这一术语表示计算任务。图1中灰色区域代表各框架的主导份额，dS1表示框架2和框架1的主导份额差，dS2表示框架3和框架2的主导份额差。为均衡不同框架间的主导份额，框架1在执行第1次分配计算时，在资源足够的情况下分配资源给子任务使其主导份额增加dS1，此时与框架2的主导份额相等。然后框架1进行第2次分配计算时框架2将执行第1次分配计算，框架1和框架2都使它们各自的主导份额增加dS2，此时与框架3的主导份额相等。综上所述，meDRF分配算法的流程描述如下： 1） 对每个集群节点的计算机进行性能评估打分，并按分值从小到大排序，求得ηk值； 2） 计算每个框架的主导份额Si，并按从小到大排序； 3） 计算相邻框架之间的主导份额差dSi； 4） 主导份额最小的框架进行分配计算，如果是第奇数次分配计算则从性能评估分值高的机器分配资源，如果是第偶数次分配计算则从分值低的机器分配资源； 5） 反复执行步骤2）～4），当所有任务分配完毕或者所有资源分配完成时，分配流程结束。 3 实验结果 本实验的集群环境由4个计算节点组成，分别为2台性能较差的曙光服务器和2台性能较好的IBM服务器，共56核CPU和48GB内存，服务器硬件配置如表1所示。集群节点计算机的操作系统Linux版本为CentOS 7.0，Mesos采用最新的0.24.0版本。运行2个Hadoop框架，分别处理不同的任务。本实验选取WordCount，TeraSort、NutchIndex、Kmeans、Bayes及PageRank[22]6种作业进行实验，作业参数设置如表2所示。 对比实验中，框架1的子任务对资源的需求为〈2核CPU，1GB内存〉，框架2的子任务对资源的需求为〈1核CPU，2GB内存〉。本实验在mesos中分别采用DRF算法和修改源程序实现的meDRF算法进行测试。经过运行表2中的MapReduce任务，两个算法分配的资源分布分别如图2、3所示。 通过对比WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6种作业分别在DRF、meDRF、异构、同构4种条件下的任务完成时间（如表3所示）。可以发现：不论是DRF还是meDRF算法，同构环境下的任务执行时间都较短；meDRF与DRF算法相比，meDRF大部分情况下的执行时间与DRF算法相比，执行时间较短。这说明更加公平的资源调度策略在一定程度上能够减小作业的执行时间。 实验过程中，本文还对不同作业的执行过程中内存，磁盘及网络资源使用情况进行了监控，如图4所示。 通过图4可以看出不同的MapReduce作业在运行过程中对内存、磁盘与网络资源的利用存在较大的差异，并且相同作业在不同时间点的资源使用情况变化也很大。并且，在异构环境下，这些随时变化的资源需求，已有的DRF算法并不能很好地适应公平性的要求。 算法meDRF比DRF在MapReduce中执行效率较好的原因是：当前Hadoop中采用机架感知的数据存放策略，将数据文件切分为相同大小的数据块（Block）随机存储到集群DataNode节点中。在同构环境中，这种数据的切分与存储方法配合DRF算法的资源分配，能够满足系统可用性与负载分流的要求。但是，在异构环境中，由于集群中各节点的计算能力存在着差异，异构节点处理相同任务（任务数据集大小相同）的完成时间不同。因为只有当一个作业的Map任务成功完成的数量超过一定的阈值时，才能开始分配该作业的Reduce任务给某TaskTracker节点执行，所以对于计算机能力强的节点，DRF算法在异构环境容易造成大量的等待时延。MapReduce任务执行过程中任务之间并不是按照完全并行的方式进行的，Map与Reduce任务之间存在不同程度的执行顺序与数据调用的制约关系。当某任务处于等待其他任务的执行结果（或等待其他任务的执行完毕）才能继续往下执行而处于“被动等待”状态时，DRF算法的资源分配的缺点就显现出来。而meDRF算法则是适应了异构环境的资源分配，较DRF更能提高异构环境下作业的执行效率。 另外，本文对任务运行过程中的资源使用情况进行了监控，对于系统最核心的资源CPU，DRF与meDRF算法的平均CPU负载情况比对如图5所示。从图5可以发现，meDRF算法较DRF算法在120min的监控周期中，meDRF算法的CPU负载更加平稳，波动幅度控制能力更好。 4 结语 本文在研究mesos框架中的DRF多资源公平分配算法的基础上，设计并实现了增加机器性能评估影响因子的meDRF分配算法。实验测试结果表明：meDRF分配算法更能体现多资源分配的公平性，且资源分配具有更好的稳定性，能有效提高计算资源的使用率。通过选取WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6种作业进行实验，对比作业运行时间及资源的使用情况，证明了meDRF算法相对于DRF算法的优越性。在实际应用的场景中，不同框架运行的作业类型存在差异，有些框架侧重于分析，而有些侧重于计算。如何使侧重计算的框架获得更多的优质资源，而侧重分析的框架获得较多的劣质资源，进一步提高资源使用率，是下一步的工作目标。 |
|
核心期刊网（www.hexinqk.com）秉承“诚以为基，信以为本”的宗旨，为广大学者老师提供投稿辅导、写作指导、核心期刊推荐等服务。 核心期刊网专业期刊发表机构，为学术研究工作者解决北大核心、CSSCI核心、统计源核心、EI核心等投稿辅导咨询与写作指导的问题。 投稿辅导咨询电话：18915033935 投稿辅导客服QQ： 投稿辅导投稿邮箱：1003158336@qq.com |
| 你好，欢迎来到！ 设为首页 ｜收藏本站 | ||
|
