Max-Min Fairness算法

19 June 2022

调度系统中算法设计往往对资源利用率起着关键作用。软件设计没有银弹，算法的优劣往往依赖于对应的业务场景。
该系列文章将整理几种资源调度算法，并分析算法的特性，适用场景等，最后分享在边缘云调度场景中的应用。

1 前言

Max-Min Fairness（MMF）是一种兼顾公平的前提下，尽可能让更多人满意的资源分配算法。常用于单一共享资源的分配场景，如多路复用的通信系统中多任务共享信道传输。算法的优势在于有着较高的平均吞吐量和资源利用率，同时算法稳定性高，单一任务突发不容易影响其他任务¹。算法的劣势在于一般只适用于单一共享资源。

边缘计算场景中，边缘网络节点带宽上联有限，多应用共享上联时与多路复用通信系统类似，存在带宽资源争抢问题。本文结合边缘云调度在节点上混部多类型应用场景中节点共享带宽资源解决方案，介绍 MMF 算法的原理和应用。

2 Max-Min Fairness 算法

2.1 常规 MMF

问题描述： 在任务调度系统中，有一个共享资源（如：CPU、带宽等），它的容量是\(C\)（capacity），每个任务\(i\)对资源的需求量为\(r_i\)（Reqeust），问如何尽量公平地分配资源？

算法流程：

将资源平均分成\(n\)份，每份都是\(C/n\)，把每份分给相应的让任务\(r_i\)。
如果任务分配到的资源超过自己的需求量，回收超过这部分资源\(C/n-r_i\)。
将上一轮中回收的所有资源，再平均分给上一轮分配中未得到满足的任务。

举个例子²： 如下图所示，在网络系统中带宽上限为 C = 10 Mbps，有四个任务对带宽需求分别为[2, 2.6, 4, 5] Mbps，问如何分配带宽资源？算法流程：

将资源均分为4份，每份为10/4=2.5，依次将资源分给任务。
任务1需求2，分配到2.5，回收0.5；任务2到4需求空缺[0.1, 1.5, 2.5]。
将回收的资源0.5再分配给任务2到4，重复过程1-3，直到资源分配完，或者任务需求都满足。

max-min-fairness

2.2 加权 MMF

在MMF的基础上，我们再考虑一个复杂的场景，在调度系统中每个任务的重要性或者优先级都不一样，那么系统如何考虑优先级的情况下来分配资源呢？

问题描述： 在任务调度系统中，有一个共享资源（如：CPU、带宽等），它的容量是\(C\)（capacity），每个任务\(i\)对资源的需求量为\(r_i\)（Reqeust），权重为\(w_i\)（Weight），问考虑权重如何“公平”地分配资源？

算法流程：

令\(W=\sum_{i=1}^n{w_i}\)，将资源按照权重分成\(n\)份，每份分别为\(C*w_i/W\)，把每份分给对应的任务\(r_i\)。
如果任务分配到的资源超过自己的需求量，回收超过这部分资源\(C*w_i/W - r_i\)。
将上一轮中回收的所有资源，再分给上一轮分配中未得到满足的任务，重复过程1-3，直到资源分配完，或者任务需求都满足。

举个例子²： 如下图所示，在网络系统中带宽上限为 C = 10 Mbps，有四个任务对带宽需求分别为[3, 3, 4, 5] Mbps，权重分别为[1, 2, 1, 1], 问如何分配带宽资源？算法流程：

总权重W=5，将资源按照权重分为4份，分别为[2, 4, 2, 2]，依次将资源分给任务。
任务1需求3，分配到2，回收0，任务2需求3，分配到4，回收1等等；任务1-4需求空缺[1，0， 2， 3]。
将回收的资源1再按权重分配给任务1，3，4，重复过程1-3，直到资源分配完，或者任务需求都满足。

weighted-max-min-fairness

2.3 算法实现C++

// alloc_max_min_fairness MMF算法分配资源
// @cap：资源容量
// @reqs: 资源需求列表
// @w: 不同资源需求的权重

// @return: 资源分配列表
vector<double> alloc_max_min_fairness(double cap, vector<double> reqs, vector<double> w) {
    int n = reqs.size();
    const double eps = 1e-8;
    vector<double> allocs(n, 0.0);
    set<int> exist;
    for (int i = 0; i < n; i++) {
        exist.insert(i);
    }

	// 资源分配完或者需求都满足
    while (abs(cap) > eps && !exist.empty()) {
        double sum = 0;
        for (int i: exist) {
            sum += w[i];
        }
        // 按权重均分资源
        double unit = cap / sum;
        for (auto it = exist.begin(); it != exist.end();) {
            int i = *it;
            double alloc = unit * w[i];
            if (alloc + allocs[i] >= reqs[i]) {
	            // 分配超出需求，回收超过部分
                alloc = reqs[i] - allocs[i];
                exist.erase(it++);
            } else {
                it++;
            }
            cap -= alloc;
            allocs[i] += alloc;
        }
    }

    return allocs;
}

3 边缘云调度应用

相较于传统云计算业务的计算密集，边缘计算往往是流量带来了计算，流量是边缘云调度时重点关注的资源之一。相对于应用来说，云中心机房带宽能力基本可以认为是无限大，主要关注计算涉及的CPU、内存和存储等。边缘机房的特点是单节点能力小，数量多，分布广。以阿里云边缘云为例，全网平均2800个网络节点分布在全球，单节点服务能力小。

所以，考虑边缘节点多应用带宽复用时，就可以参考MMF算法进行设计，能达到很不错的效果。

4 总结

本文结合边缘计算场景，介绍了MMF算法及其应用。算法具备不错的平均吞吐量、资源利用率和稳定性，但是局限于单一共享资源的分配，如内存等无法共享的资源则不适用。