对于一个Hadoop控制器,一个job控制器会把它分成m个规模类似的task,交给不同的物理节点(node)去执行,每个节点可以执行任意多(或不执行)task。总共有n个不同的物理节点。
现在需要一个策略,把这m个task,分给不同的节点,确定每个节点分配到多少个不同的task。这个过程叫做scheduling
这些task依赖的数据,存在某些node上。因此这些node,执行完一个task的时间就会比较短$C_{loc}$, 其它结点执行完的一个task时间$C_{rem}$就会更长(因为要把原来节点的数据复制过来)
基于上述原因,之前的调度算法(文献详见hadoop scheduling algorithms,其中除了BAR和SDN那篇之外都是综述),主要的目的有:
- 使得schedule的方案中,最后一个task执行完的时间最短(Minimum span problem, NP),于是就有了很多启发式的方法,例如BAR
- 使得平均完成时间最短
- Energy-saving
- 如果每个node的计算能力不等价该怎么搞(heterogeneous)
但是,它们都没有考虑到一个问题:网络情况。例如一个link的bandwidth是有限的,那么某种数据搬移都集中在这条link上的schedule就不太有效(迁移时间=数据总量 / BW)。基于这个原因,有人提出利用SDN监测带宽来进行调度(hadoop scheduling algorithms, Bandwidth-Aware Scheduling With SDN in Hadoop: A New Trend for Big Data)。其在schedule的时候探测一下每个link的剩余带宽,使得这个schedule在迁移数据时不会超过link的bandwidth,而且尽量利用带宽更大的路径。
其算法大致是:
When job comes:
Use current bandwidth to calculate residue time between nodes
assign tasks so that Min { Max{ Finish_time(node[i]) } }
而$finish_time = computation_time + data_movement_time = \ computation_time + data_size / \min{link_bandwidth_from_source_to_dest}$ 用了一个类似贪心的方法动态调整schedule。
但是,这样有一些问题:
- 每次只会选取bandwidth较多的一个node, 即使这个会造成bottleneck, 使得整体的完成时间增大
- 只考虑了一个task自身的影响,而没有考虑到task之间的相互作用
这些问题其实都是SDN QoS routing中的问题,可以见上周的slides
能不能将这些routing algorithm中考虑到的全局最优性融入schedule算法中?