Reduce函数的不可交换性检测

MapReduce是一种流行的编程模型,通过分而治之的思想很好地解决了许多并行计算问题。然而,在其广泛应用的背后还存在着非常严峻的考验。MapReduce程序可能因为输入数据到达Reduce函数的顺序不同而产生不确定的输出结果。为了使MapReduce程序的输出更加可靠,需要对Reduce函数的不可交换性进行检测。针对上述问题,提出了一种Reduce函数的不可交换性检测方法。首先,通过简化循环的符号执行方法及程序分析方法,生成具有针对性的原始测试用例;其次,通过一种能够快速改变记录行间相对位置的置换函数Ex生成后继测试用例;最后,通过比较原始测试用例及后继测试用例的执行结果是否相同,来检测Reduce函数的不可交换性。实验结果表明,该方法扩大了可以测试的Reduce函数种类,将测试用例集的大小从阶乘级别缩小到线性级别,降低了检测Reduce函数不可交换性的复杂度和难度。