基于故障/非故障执行的最长公共前缀的分布式系统根因分析。

以前的根因分析方法几乎都依赖于统计分析。本文提出了一种不同的方法：如果我们将一个执行过程建模为一个完全有序的指令序列，那么根因分析可以通过故障执行与非故障执行的最长公共前缀确定。

Kairux需要三个输入：（1）重现故障的步骤，通常打包在单元测试中；（2）故障症状；（3）所有代码的单元测试。

Kairux输出：（1）拐点；（2）与故障指令序列有最长共同前缀的非故障指令序列；（3）以单元测试形式重现σp所需的步骤。

然而，Kairux并不试图列举所有可能的无故障序列，而是只考虑从系统的现有单元测试中获得的无故障序列。

Kairux用了一些技巧：

首先，它从序列中删除了与故障症状无关的指令。因此，它只对partially ordered的指令序列而不是totally ordered的指令序列进行操作。

然后，它将目标指令序列分离成属于不同线程的独立子序列，最初独立处理每一个子序列。 Kairux这样做的原因是：（1）真实的分布式系统的故障通常需要触发多个操作；（2）每个操作通常由自己的独立线程处理；以及（3）在大多数情况下，每个单元测试只测试几个操作。

此外，Kairux使用启发式方法来优先考虑最有可能与故障执行有共同指令序列的单元测试。当一个测试指令序列与故障序列不一致时，Kairux试图修改目标单元测试的输入参数，以减少分歧。

最后，它将多个线程和多个测试的子序列拼接起来，构建无故障序列。

Implementation

用3,473行的Java代码实现了Kairux。

使用Chord静态分析框架来执行静态和动态切片。

使用JVM工具接口（JVM TI）在字节码位置设置断点，记录指令序列。并enforce different thread schedulings by ordering the breakpoints

对于每条指令中使用的每个动态对象，Kairux还使用JVM TI分配了一个独特的标签。这使得Kairux能够区分同一源代码对象的不同运行时实例。

控制JVM TI的程序是用2,961行C++代码编写的。

还编写了Python程序来并行化单元测试的执行。

对于HDFS这个单元测试耗时最长的系统，能够将所有单元测试的运行时间从在普通文件系统上顺序运行时的6小时以上，减少到在tmpfs上并行运行时的10分钟以内。