各位好，这是介绍阿里云伏羲(fuxi)调度器系列文章的第一篇，今天主要介绍多租户(QuotaGroup)管理的实现

一、FuxiMaster简介

FuxiMaster和Yarn非常相似，定位于分布式系统中资源管理与分配的角色：一个典型的资源分配流程图如下所示： 




作为调度器，目前FuxiMaster支持的功能主要有：

1、多租户管理（本文）

2、调度模型及FIFO/FAIR调度策略

3、针对在线服务保持资源强稳定

4、支持NodeLabel动态划分集群

5、支持多机房调度

6、支持基于优先级的交互式抢占

7、支持AllOrNothing调度

8、支持基于硬件ID化的调度

9、单Master目前支持2w台机器的规模

10、......

二、多租户管理的用户场景

在典型场景下，可以简单理解为一个部门拥有一个QuotaGroup，这个QuotaGroup下可以有多位开发同学，他们使用的总资源是受到限制的。  

下面介绍有关的几个定义：

1、每个QuotaGroup拥有MaxQuota的语义，即可使用资源的上限；

2、每个QuotaGroup拥有MinQuota的语义，语义是当资源请求（Request，下同）小于MinQuota时，FuxiMaster必须分配Request这么多的资源；当Request大于MinQuota时，至少分配MinQuota这么多的资源；

3、由于系统总资源是固定的，所以每个QuotaGroup可用的资源一定是有限的、相互竞争的，每个QuotaGroup可以配置权重(Ratio)，权重越大，分到的资源越多；

4、在某一时刻，有的QuotaGroup Request大，有的Request小；如果能够将Request小的QuotaGroup的Quota匀给Request大的QuotaGroup，那么系统的资源利用率会有明显提升；

5、最终QuotaGroup的Quota水位线我们称为RuntimeQuota；


用下图可以更好的描述上述概念：


假设系统中存在3个QuotaGroup组，为了简单，假设3个组的minQuota都为0； 左图中，蓝色部分是每个组的Request，红色部分是maxQuota，黄色虚线表示每个组按照ratio比列划分得出的可用quota水位线：
我们可以称之为RuntimeQuotaTmp，即:


然后我们发现，第一个组实际上request < RuntimeQuotaTmp，所以RuntimeQuotaTmp － request这部分可以匀给其他两个组使用；

在右图中，绿色虚线表示每个组最终的RuntimeQuota，可以看到对后面2个组，绿色虚线与黄色虚线的gap就是来自于第一个组的RuntimeQuotaTmp － request部分，分配的原则还是根据ratio比例:

由此可以总结出RuntimeQuota的计算公式：

三、一个典型的多租户管理的计算模型

根据上述描述，一个典型的计算模型为：

1、以各个QuotaGroup的ratio来分配集群总资源、得到RuntimeQuotaTmp；

2、当Request的总和小于集群总资源时，则每个用户的RuntimeQuota即是Request, 结束分配过程；

3、将用户分为两类，A类：Request小于RumtimeQuotaTmp；B类，Request大于RumtimeQuotaTmp；

4、对于A类用户，RumtimeQuotaTmp与Request的差可以分配给B类用户用；将这些差累计求和，记为系统中可以再分配的资源总量，记为∂

5、将∂按照ratio分配给B类用户，则B类用户新的RuntimeQuotaTmp ＝RuntimeQuotaTmp ＋ 新得到的quota，记为Ω

6、如果B类用户的Ω大于Request，则Ω与Request的差还可以分配给B类用户中Ω仍小于Request的QuotaGroup，算法跳转回步骤3进行迭代，直到可再分配资源总量∂＝0

这个算法有明显的缺点：时间复杂度是O(n²)

假设有n个用户，只有一个用户A的Request小于RuntimeQuotaTmp，更新可再分配资源总量∂，并分配给剩余n-1个用户后，假设只有一个用户B的新的资源配额Ω大于其Request，继续更新可再分配资源总量∂，并分配给剩余n-2个用户......如此反复，每次只有一个用户的RuntimeQuotaTmp大于其Request，那么则需要遍历n-1个用户才能完成分配过程，一次遍历时间复杂度是O(n)，算法整体时间复杂度既是O(n²)。

四、FuxiMaster使用的多租户管理计算模型

FuxiMaster使用的模型算法复杂度是 O(logN), 模型如下：

1、将每个用户视为一个盛水的桶，桶的底边是Ratio，面积是Request， 高既是用户的资源饱和度Req/Ratio。分配资源配额的过程就是将水(集群总资源)灌入到各个桶中的过程。将用户按照Req/Ratio进行排序：



2、将集群总资源按照ratio比例均匀的撒到每个组(往桶里面倒水)， 故所有桶的水面高度(h)一齐上升。 



3、若有的桶水面高度到顶且集群剩余可分配资源仍有剩余，则此桶的水面高度不再上升，继续向其他水面高度未到顶的桶中灌水，直到集群剩余可分配资源为0或者所有桶的水面均已到顶。

当集群剩余可分配资源为0后，我们需要找到Request得到满足和Request没有完全的满足的桶边界，在边界左边的桶的RuntimeQuota就是Request；而在边界右边的桶deRuntimeQuota是H * Ratio，其中H如下图所示。可知，如果能够计算出边界和H，那么每个用户的RuntimeQuota就是可知的。



判断边界的条件是：

Requst(A~D) + RequestE + (RequestE / RatioE) * (ratioF + ratioG) < TotalRes &&  Requst(A~D) + RequestE +(RequestF / RatioF)  * (ratioF + ratioG) >TotalRes

由于每个桶是按照Request/Ratio排序的，所以可以通过构建一颗自定义的旋转的红黑树，就可以以O(logN)的时间复杂度来找出边界点，找出边界点后，通过公式：



即可以求出H，进而得到每个Quota组的RuntimeQuota

4、如果考虑minQuota，则根据minQuota的定义将相应部分事先减去即可，如下图所示：




这个方法和典型方法从数学上可以推导对于runtimeQuota结果是保持一致的，由于比较复杂这里就不列出了，有兴趣的同学可以私下讨论

五、性能表现

我们同时实现了2种方法进行性能对比，其中组数是指QuotaGroup的个数；资源数是指资源维度的数目（资源分配是多维的），结果如下：





可以看到，FuxiMaster目前采用的方法与组数是对数关系，与资源数成线性关系，符合预期；相对于典型方法，性能提升巨大

下面进一步给出FuxiMaster方法在更大规模下面的表现：

欢迎加入“数加·MaxCompute购买咨询”钉钉群（群号： 11782920）进行咨询，群二维码如下：