这周花时间把Firmament剩余部分看完了，说实话有些失望。论文并没有想象中的那么好，因此决定简单的记录一下，就转去阅读Quincy。Firmament是Quincy的改进版，主要贡献在于结合调度的场景需求提高了MCMF的执行效率，让Flow-based的调度算法具备现实的工程意义。

Quincy的核心消耗是在对MCMF这个问题的求解上。MCMF问题，可以简单理解成这样：

有一堆的货物（上一篇中的\(T_{i,j}\)节点），要从一些地点运输到另外一些地方(上篇中的\(S\)，sink node)，其间需要经过许多”道路”(边)和”中转站”(中间结点)，选择每条路都有一定的cost、且道路允许通过的流量是有限的。那么问题就来了，如何用最小的代价(Min-cost)、运送最多的货物(Max-flow)？

这个是一个标准的图论问题，相信很多人都会猜到，这个问题和网络路由的场景是十分match的。许多人已经对这个问题有所研究，给出了五花八门的解法。

文章介绍了四个MCMF的算法，并将注意力集中到了其中的两个：Relaxation和Cost-scaling。Relaxation的大思路是先找到一个最小cost的解，而后迭代式的调整、满足MCMF的约束条件；而Cost-scaling相反，其基本思路是先找到一个满足约束条件的解，而后迭代式的去降低消耗的cost。文章中的剩余两个算法，感觉就是陪衬用的，用来突出这两个算法的好。

四个算法的算法复杂度如下图:

图中的数据上来看，貌似successive shortest path更好，但从实验的数据表明，大多数还是Relaxation比较好。可能是因为在调度的场景下，一般是节点数很大(N很大)、每个节点连接的边不会太多(虽然节点很多)，这个分布对Relaxation是有利的。但Relaxation算法在边界情况表现挺差的，对一个负载很重的集群来说，其中的”边”很多(M很大)，它的性能就会急剧下降。但与此同时，Cost-scaling的性能就表现出众了！因此，论文作者干脆提出：两个算法一起跑，谁先出结果就用谁的！暴力手段解决问题。

另外，文章还做了以下几个措施来缩短算法的执行时间：

• 根据调度场景变更不会太多的情况，在Relaxation和Cost scaling算法上都使用增量计算的算法，即尽可能使用前面计算结果。graph变更的时候，接着前面计算的结果而不是每次都重来。这样可以显著减少计算量。我想这也是为什么作者选用这两个算法的缘故，因为他们都有迭代计算的版本。
• 引入一些启发式的信息，减少计算量。论文里面提到了两个：首先，图中的边在迭代中选择哪条，其实是可以结合调度的场景、提供额外的提示信息给算法，让其优先选择。这个思路相当于剪枝，减少了不必要的计算；另一个想法是当任务结束的时候，将Task Node从图中挪走，尽量减少节点数。这两个算法，前者提速大概45%，后者大概提高10%。

最后，论文作者非常慷慨的给出了算法的源代码，大概有24,000行，其中的MCMF部分大概有8,000行，总体规模还是挺大的，对算法细节感兴趣的可以去阅读。

好了，这篇论文就简单介绍到这里。如文章开头所说，后面会去研读下Quincy，将更多的精力集中在对调度问题的建模上。也许当决定在现实场景中使用Quincy算法的时候，需要再回过头来重新强化阅读下这篇论文。由于这篇论文是OSDI’16的，很推荐大家关注下论文后面的引文，感觉质量都相当不错，后面有时间我也会逐步展开阅读。