引用：Muhammad Ali Gulzar, Siman Wang, and Miryung Kim. 2018. BigSift: Automated Debugging of Big Data Analytics in Data-Intensive Scalable Computing. In Proceedings of the 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’18), November 4–9, 2018, Lake Buena Vista, FL, USA. ACM, New York, NY, USA, 4 pages. .

摘要

由于数据集的不纯净性质或对数据的错误假设，开发大数据分析通常涉及试错调试。当出现错误（例如程序崩溃，异常结果等）时，开发人员通常对查明错误的根本原因和解释异常的来源感兴趣。为了解决此问题，BigSift 以 Apache Spark 程序、用户定义的测试 oracle 函数和数据集作为输入，通过将增量调试的见解与数据来源相结合，输出能使错误再现的最小的一组输入记录。BigSift 的技术贡献是系统优化设计，使自动化调试更接近于数据密集型可扩展计算的现实。

​ BigSift 公开了一个交互式 Web 界面，用户可以在其中监视远程运行在云端的大数据分析作业，编写用户定义的测试 oracle 函数，然后触发自动调试过程。BigSift 还提供了一组预定义的测试 oracle 函数，可用于解释大数据分析中异常的常见类型，例如，查找与中位数相差超过k个标准偏差的输出值的起源。该演示视频可从获得。

1 简介

诸如 Google 的 MapReduce、Apache Spark 和 Apache Hadoop 之类的数据密集型可扩展计算（DISC）系统可以处理大量数据集。与其他软件开发平台类似，开发人员经常处理不干净的数据或对数据做出错误（或不完整）的假设。因此，至关重要的是要为这些开发人员配备工具箱，以更好地查明错误的根本原因。不幸的是，调试大数据分析目前是一个临时的、耗时的过程。数据科学家通常编写实现数据处理管道的代码，并使用从 TB 规模的数据仓库下载的小样本数据在本地开发工作站上对其进行测试。他们不由自主地希望程序可以在昂贵的生产云中运行。当工作失败或最终获得可疑的结果时，数据科学家通常必须通过挖掘事后日志来确定错误的来源。

​ 在这种情况下，程序员（例如，数据科学家）可能希望通过调查相应输入记录的子集来查明错误的根本原因。一种可能的方法是跟踪数据来源（在各个分布式工作节点中创建的输入输出记录映射）。但是，根据我们先前的研究 [1]，基于数据来源的向后跟踪发现了数百万个输入子集，对于开发人员来说，它仍然太大以致无法手动筛选。增量调试（DD）是一种众所周知的算法，它使用不同的输入记录子集重新执行同一程序 [10]。将 DD 算法简单地应用于大数据分析是不可扩展的，因为 DD 是一种通用的黑盒过程，它不考虑从单个数据流运算符生成的键值映射。因此，DD 不能通过考虑数据流运算符的语义来轻松修剪不相关的输入记录。

​ BigSift 的技术贡献有两个方面。首先，它将增量调试与数据来源相结合。其次，它实现了三个系统级的优化-（1）测试谓词下推，（2）向后跟踪优先级排序和（3）基于位图的备注（将在第 2 节中详细讨论），以提高调试性能。图 1 显示了 BigSift 的总体架构。

​ 我们的评估表明，与 Titian [4]的数据来源相比，BigSift 将错误定位的精确度提高了几个数量级（约 103 至 107 倍）。与单独使用 DD [1]相比，BigSift 将性能提高了 66 倍。对于每个错误输出，BigSift 都可以在不到原始作业运行时间的 62％的范围内定位引起错误的数据。

​ 本文建立在我们先前的工作之上 [1]，并着重于 BigSift 的工具功能和相应的实现细节。BigSift 与当前的 Apache Spark 基于 Web 的 UI 完全集成。用户可以直接检查原始输出记录，并即时编写一个 test oracle 函数，或者从预定义的 test oracle 函数中进行选择。 BigSift 通过交互式区域图将实时调试进度信息从远程集群流式传输到用户，并以表格格式显示当前设置的引发错误的输入记录。我们当前的实现针对 Apache Spark 2.1.1，使用 inScala 和 Java [9]编写的程序。

2 技术方案

BigSift 的贡献在于通过设计新的系统优化并串联数据来源来适应大数据分析的增量调试，这为 Apache Spark [4]提供了向前和向后的跟踪功能。 图 1 说明了我们的方法。如果不进行此类系统优化，则增量调试可能要花费数小时甚至数天。 这是因为输入数据集的大小很大，因此像增量调试这样的详尽的二进制搜索算法可能会花费大量时间。 在我们的评估中，BigSift 比 DD 快 66 倍。 下面，我们概括地概述了三种系统优化，其他详细信息在其他地方描述 [1]。

2.1 测试函数下推

在 map-reduce 编程范例中，组合器在将数据发送给 reducer 之前，对映射时的reduceByKey等运算符执行部分聚合，以最大程度地减少网络通信。由于增量调试使用用户定义的测试功能来检查每个最终记录是否有错误，因此我们的洞察力在于，在向后跟踪期间，我们应使用引起错误的中间输入隔离确切的分区，以进一步减小向后跟踪的搜索范围。

​ 在 Apache Spark 中，某些聚合运算符（例如reduceByKey）要求用户提供关联和交换函数作为参数。 BigSift 通过在上一阶段将用户定义的测试功能下推到分区来测试中间结果，从而实现了新的优化。当（1）程序以需要关联函数f1的聚合运算符（例如reduceByKey）结尾时，启用此优化。 （2）当f2是检验函数时，f1◦f2是关联的； （3）f1◦f2是故障单调。如果不满足此单调性属性（可以通过测试最终输出来验证），或者所有分区都没有通过测试功能，则 BigSift 会回滚到默认情况，即向后追溯最终的错误记录。

2.2 重叠向后跟踪

由于一些操作符（例如flatMap或join）能利用单个数据记录产生多个中间记录，从而导致多个错误的输出，相同的输入记录可能会导致多个错误的输出记录。因此，BigSift 在应用 DD 之前将导致多个输出的相同输入记录划分优先级。为了检查是否有资格进行此优化，BigSift 探索了程序的 DAG，以查找至少一个一对多或多对多运算符，例如flatMap和join。

​ 为了探索所有可能的重叠轨迹，BigSift 将两个最小的后向轨迹（例如t1和t2）重叠，以找到交点t1∩t2。如果在t1∩t2上评估的测试函数发现任何错误，则将 DD 应用于t1∩t2以及剩余的（潜在的）导致错误的输入t1 t2和t2 t1。否则，将在初始迹线t1和t2上执行 DD。如果在重叠中发现任何引起错误的输入，则可能由于不两次处理重叠的迹线而节省了时间。

2.3 基于位图的测试结果记忆

DD 无法检测相同输入配置的冗余试验，因此可能会多次测试相同输入配置。为了避免浪费计算资源，BigSift 使用测试结果记忆优化。简单的记忆策略将需要扫描输入配置的内容以检查其是否已经过测试；这样的基于内容的记忆将是耗时的并且不可扩展。而 BigSift 利用位图对输入数据集的偏移量进行紧凑编码，以引用子配置。

​ 因此，我们对 DD 的通用拆分函数进行了调整，以生成子配置及其相关的位图描述。 BigSift 维护已执行位图的列表，每个位图都指向在输入子配置上运行程序的测试结果。在处理输入子配置之前，BigSift 使用其位图描述在位图列表中执行查找。如果结果是肯定的，则查找将直接重用目标子配置的测试结果。否则，BigSift 测试子配置并将其位图和相应的测试结果注册到列表中。该技术避免了对相同输入子配置的冗余测试，并减少了总调试时间。 BigSift 使用压缩的 Roaring 位图表示来描述大规模数据集 [5]。

2.4 实现

为了实现大数据分析应用程序的自动调试，用户可以使用 SparkContext 和输入文件路径作为输入参数来实例化 BigSift 类，如图 3 所示。在内部，该类实例化 LineageContext 来启用 Titian 的工具来支持数据来源。有关 Titian 使用的更多详细信息，请参见我们之前的 VLDB 2016 论文 [4]。然后，用户可以使用测试 oracle 函数和 sparkProgram（一个有向非循环图（DAG）工作流，它接收输入的弹性分布式数据集（RDD，即分布式集合的抽象））并返回最终的 RDD 来调用runWithBigSift方法。作为外部 Java 库（jar），可以通过将 jar 文件导入运行有数据支持功能的 Spark 发行版（如 Titian [4]）上运行的 Spark 应用程序中进行部署。BigSift 的交互式 UI 可在 Spark 驱动程序节点上的端口 8989 上使用。图 2 显示了基于 Web 的用户界面。作业完成后，用户可以检查作业执行时间、原始输出等。用户可以编写自己的自定义 test-oracle 函数或从预定义的测试函数中进行选择。 BigSift 还显示一组输入记录以重现相同的测试失败。区域图报告实时调试进度信息。用户可以单击该图形以查看引起错误的输入的大小和样本。

3 演示场景

假设爱丽丝（Alice）是一名数据科学家，她在 Apache Spark 中编写了一个大数据应用程序，以分析包含美国乘客运输信息的大规模数据集。由于数据的大小为 TB，她收集了数据集的一小部分样本（例如 10MB），并在本地计算机中使用 Spark 建立了数据处理管道。爱丽丝希望找到在美国每个机场每小时飞行少于 45 分钟的所有乘客的总飞行时间。数据集中的一行以以下格式表示乘客的过境信息。

[日期，乘客，到达，出发，机场代码]

9/4/17，161413，6:52，8:22，MNN

​ 图 5 中的程序首先加载数据集（第 1 行）并扫描每一行以检索键值对。键由机场代码和旅客的到达时间组成，值是在机场（2-6 行）以分钟为单位的飞行时间（出发时间-到达时间）。 第 7 行对经过时间少于 45 分钟的乘客进行过滤。最后，该程序汇总每个到达小时每个机场的所有乘客的过境时间（第 8 行）。

​ 编写此应用程序之后，Alice 将作业提交到生产云，从而产生以下输出：

（（SEA，7），175080）

（（LAX，11），173460）

（（MNN，23），-27804120）

.....

然后，她意识到某些输出记录看起来可疑。例如，当 MNN 的总传输时间为-27804120 时，预计总传输时间为正值。爱丽丝想调查负责产生负值的确切输入记录。这项任务具有挑战性，因为大规模数据集无法手动检查，并且由于采用了用户定义功能的聚合步骤，因此在输入记录和输出记录之间没有一对一的映射。

​ Alice 决定使用 BigSift，它将其程序，输入数据集和一个测试 oracle 函数作为输入，并最终返回以下负责可疑负输出值的罪魁祸首输入记录。

11/9/12，141011，22:53，0:23，MNN

​

​ 下面逐步介绍 BigSift 工作流程。

​ 步骤 1：程序输出检查。图 2 显示了 BigSift 的登录页面。它在文本框中以记录数、作业处理时间、最终输出记录的形式显示输入数据集的大小，分别参见图 2 中的 ➊，➋ 和 ➌。为了更好地可视化输出记录，BigSift 使用直方图提供了键值对的交互式和动态可视化，从而使用户更容易直观地识别异常记录（图 4（a））。例如，Alice 可以使用直方图将任何负值标记为不正确，并记下该阈值以构建测试函数。

​ 步骤 2：通过定义 Test-Oracle 函数对可疑或错误的输出记录进行分类。 BigSift 使用户能够编写测试函数-应用于每个最终输出记录的谓词，以区分正确输出与错误或异常输出。BigSift 还使用户能够从预定义的测试谓词函数列表中进行选择（图 2（b）- ➍）帮助解释大数据分析中异常的常见类型：例如，（1）解释如何创建最小输出值，（2）解释如何创建最大输出值，（3）解释输出值如何大于 k 标准将创建与中位数的偏差，等等。一旦从单选按钮中进行选择，用户就可以按下 Run BigSift 按钮（图 2（b）-➏）。在内部，BigSift 选择相应的预定义测试功能以启动调试。

​ 步骤 3：可视化数据来源。为了帮助理解跨转换步骤的引起错误的中间输入记录的传播，BigSift 提供了基于饼图的 DAG 可视化工作流（图 4（b））。此图中的每个节点都表示为饼图，其中红色部分显示了引起错误的中间记录与该转换处理的记录总数的比率。通过在每次转换时查看数据比率，用户可以获得更深入的见解。

​ 步骤 4：自动 DISC 调试。当用户调用 BigSift 时，实时区域图将显示在 UI 上。在图 2（c）中，Y 轴表示由 BigSift 隔离的以日志为单位的错误引发输入记录的数量，X 轴表示调试时间。随着时间的流逝，BigSift 从云流式传输调试进度信息。用户可以在图表的任何部分上单击以在选定的时间查看示例错误产生的输入记录。鼠标悬停将显示引起错误的输入记录的数量。一旦 BigSift 找到了引起错误的输入记录的最小集合，BigSift 就会通过 pushnotification 通知总调试时间（图 2（c）-➐ 中的绿色容器） 。

5 评估与总结

我们正处于调试大数据分析的初期。本文展示了 BigSift，这是在数据密集型可伸缩计算（DISC）上下文中的自动化调试工具包，查找导致错误的输入仅仅是开始。我们看到了 DISC 应用程序自动调试的更多机会，例如自动数据清理和错误的代码本地化。

​ 在我们先前的工作中 [1]，我们在一个 16 节点的集群上评估了 BigSift，该集群具有 8 个主题程序，其中错误被注入到输入数据集或代码中。评估中使用的数据集范围从几 GB 到 80GB。与仅使用 DD 相比，BigSift 通过删去与错误输出无关的输入记录，减少了错误定位时间（多达 66 倍）。此外，我们的迹线重叠试探法将总调试时间减少了 14％，我们的测试记忆优化使调试时间减少了多达 26％。的确，每个错误输出的 BigSift 调试总时间平均比原始作业运行时间短 62％。