NEAL(Network-Aware Locality Scheduling)论文简要解读

Network-Aware Locality Scheduling是一种借助元启发式算法的共流（Coflow）调度方法，原文链接：

论文链接https://ieeexplore.ieee.org/abstract/document/9329172

1.共流调度的基本背景

在大数据处理过程中，通常存在聚合操作，比如MapReduce的Reduce操作，Spark的groupByKey等等。这些操作需要将相同键的值合并在一起，比如单词统计任务，可以将一堆文件分给不同节点单独处理，此时就会出现“单词-出现次数”的键值对。在reduce阶段将不同节点处理的结果合并在一起，属于同一个键的值加起来，就可以得到这堆文件中每个单词的出现次数。

当然，键值对不一定是key和单个值，也可能存在key-tuple的情况，设想有这么一个任务，需要统计不同人的消费记录，不同节点可以用来处理不同平台的消费记录，然后生成“ 用户-消费记录元组”的键值对，比如节点1统计外卖平台，生成键值对{用户1 : (消费记录1,消费记录2…)}、{用户2 : (消费记录1,消费记录2…)}等等。节点2可以用来统计网购平台数据、节点3统计游戏平台数据，诸如此类。那么在reduce的时候，需要将每个用户在不同平台的消费记录合并在一起，比如属于用户1的所有平台消费记录需要进行合并，那么这时就需要思考一个问题，这些数据如今分布在各个节点，究竟交给哪个节点来完成这个合并操作，这个节点为汇聚节点。

下面是三种分配策略，在我们这个例子中，节点1、2、3就是不同平台的消费数据，而$a^{b}$代表用户a（Key），b为消费记录的个数（或者说元组大小、数据量），比如$1^{3}$代表用户1，有三条消费记录：

在a中，根据简单的hash函数来决定汇聚节点。而b和c是其它的调度策略，区别在于用户2的汇聚节点不同（b选择汇聚到节点1，c选择汇聚到节点2）。这里的调度策略并不是重点，关键是如何去评价哪个调度策略是好的：

假如按照最小传输数据量来看，a、b、c传输的元组大小分别为8、7、6，那么SP2是最优的。

从另一个角度来看，SP2中节点1需要发送4个数据给节点2（Key为1的有3个数据，Key为2的有1个数据），节点2和节点3分别需要发送1个数据。这些在节点之间传输的数据流组成了共流（coflow），需要等待共流中的所有数据流都传输完毕后才能开始下一步的shuffle操作。这时节点1发送给节点2的数据太多，成为了瓶颈，相比之下，SP1中每个节点需要发送的数据分别为3、3、1。假如发送一个数据需要的通信时间为1，则SP2的通信时间为4，SP1的为3，从这个角度看SP1又好一点。

但是假如节点2的带宽减小为原来的一半，那么此时SP1的通信时间为6，而SP2不变（因为SP2的节点2只需要发送1个数据，带宽减半后需要2个时间，仍然比节点1的4个时间要短）。

这里可以进一步做一个带宽的调整，如下图所示：

对于SP2，由于节点1需要4个时间，其余两个节点只需要1个时间，那么可以将这两个节点的带宽缩小，使得它也需要4个时间才能完成传输。这样的好处在于给其它任务腾出了一些带宽，此外数据在同一个时刻到达也更加方便处理。

从上面几个情况可以得到，在选择汇聚节点时，需要考虑传输的数据量，以及可用的带宽。

查看节点之间的可用带宽，以及为节点之间的传输分配带宽，可以通过SDN的Openflow控制器来实现。

2.共流调度的一般情况

现在假设有n个节点，p个Key，如下图左边表格所示，格子里面的数字代表数据量，也就是前面说的元组大小，考虑到不是所有节点都会有某一个Key的数据，因此存在数据量为0的情况。

对于每一个Key来说，其都需要选择一个汇聚节点，如右上方表格所示，每一列只有一个1，其余为0，代表每一个Key有且只有一个汇聚节点，其它节点如果拥有该Key的数据，就需要发送给汇聚节点。这可以进一步简化为右下角的表格，对于Key1来说，其选择节点n为汇聚节点，而Key2选择节点1，Key_p选择节点2。

如此，这个问题就变成了一个NP难题，共有$n^{p}$种情况（一共p个Key，每个Key都有n种情况）。当然，这里每一列真的需要考虑n种情况吗？

如果对于Key_k来说，只有节点j拥有该Key的数据，那就可以直接确定汇聚节点为j，而不需要考虑放在其它位置。

但是只要有两个（或两个以上）节点拥有该Key的数据，就是n种情况了，因为它可以选择汇聚在这两个节点中的一个，也可以选择汇聚在其它节点，如同图1a的Key2一样，放在了节点3，即使节点3没有该Key的数据。为什么会出现这种情况呢？因为存在带宽的限制。对于星型拓扑来说（节点m<->Openflow交换机<->节点n），节点的带宽可分为输入带宽和输出带宽。假如节点1和节点2的输入带宽比较小（或者有其它数据也需要用到这部分带宽），而它们的输出带宽充足，同时节点3的输入带宽也充足，那么就可以选择将节点1和节点2的数据发送给节点3，这样也许比节点1发送给节点2或者节点2发送给节点1要快。

实际情况中node的数量可能很多，出现两个或者两个以上的节点拥有同一个Key的数据是很常见的，因此这确实是一个NP难题。

当每一个Key都确定了汇聚节点后，就可以开始计算它的传输时间了。

节点i的发送时间：
$$
\sum_{j=1,j\neq i}^n\sum_{k=1}^p\frac{h_{ik}}{r_i}x_{jk}\quad\forall i\tag{2.1}
$$

$\sum_{k=1}^p$指的是每一个Key的数据都需要考虑，$\sum_{j=1,j\neq i}^n $指的是传输到除了节点i的所有节点，$h_{ik}$指的是节点i中Key_k的数据，$x_{jk}$指的Key_k的数据是否传输给节点j。$\sum_{j=1,j\neq i}^n\sum_{k=1}^ph_{ik}x_{jk}$指的是需要发送给其它节点的数据量，而$r_i$指的是节点i的发送带宽（输出带宽）。

同理，节点j的接收时间为：
$$
\sum_{i=1,i\neq j}^n\sum_{k=1}^p\frac{h_{ik}}{r_j}x_{jk}\quad\forall j\tag{2.2}
$$

也就是每一个Key的数据都需要考虑是否以j为汇聚节点，如果是，那么其它所有拥有该Key数据的节点都需要发数据发给节点j，$r_j$指的是节点j的接收带宽（输入带宽）。

当然，两个节点之间的传输时间并不是发送时间+接收时间，因为发送和接收可以同时进行。

现在考虑最慢流传输时间$\tau$，所有节点都在$\tau$时间内完成发送，也在$\tau$时间内完成接收，即：
$$
\tau = max(\sum_{j=1,j\neq i}^n\sum_{k=1}^p\frac{h_{ik}}{r_i}x_{jk}\quad\forall i\quad,\quad\sum_{i=1,i\neq j}^n\sum_{k=1}^p\frac{h_{ik}}{r_j}x_{jk}\quad\forall j)\tag{2.3}
$$
通过带宽调整，使得所有流的传输时间都等于这个最大时间。