Lucene 中的并发错误：如何修复乐观并发故障

您想要获得 Elastic 认证吗？了解下一次 Elasticsearch 工程师培训何时开始！您可以开始免费云服务试用，或立即在您的本地计算机上试用 Elastic。

没错，又是一个修复漏洞的博客。但这一次有一个转折，一位开源英雄突然出现，拯救了世界。

调试并发错误并非易事，但我们将着手进行。Fray 是 CMU PASTA 实验室推出的确定性并发测试框架，它能将不稳定的故障转化为可靠的可重现故障。得益于 Fray 聪明的阴影锁设计和精确的线程控制，我们追踪到了一个棘手的 Lucene bug，并最终将其解决。本篇文章将探讨开源英雄和工具如何让并发调试不再痛苦，让软件世界变得更加美好。

并发错误：软件工程师的克星

并发错误是最糟糕的。它们不仅难以修复，最难的是让它们可靠地失效。以这次测试失败为例，TestIDVersionPostingsFormat#testGlobalVersions 。它会产生多个文档编写和更新线程，这对 Lucene 的乐观并发模型提出了挑战。该测试暴露了乐观并发控制中的一个竞赛条件。也就是说，文件操作可能会谎称自己是一系列操作中的最新操作😱 。这意味着，在某些条件下，更新或删除操作可能会成功，而在乐观并发约束条件下，该操作本应失败。

向那些讨厌 Java 堆栈跟踪的人致歉。注意，删除并不一定意味着 "删除"。它还可以表示文档的 "更新"，因为 Lucene 的段是只读的。

Apache Lucene 通过DocumentsWriter 类管理每个写入文档的线程。该类将创建或重复使用线程进行文档编写，每个写入操作都在DocumentsWriterPerThread (DWPT) 类中控制其信息。此外，撰写人还会跟踪DocumentsWriterDeleteQueue (DWDQ)中删除了哪些文件。这些结构会将所有文档突变操作保存在内存中，并定期刷新，以释放内存资源并将结构持久化到磁盘上。

为了防止阻塞线程并确保并发系统的高吞吐量，Apache Lucene 只在非常关键的部分进行同步。虽然这在实践中可能很好，但就像任何并发系统一样，也有龙的存在。

一个虚幻的希望

初步调查显示，有几个关键部分没有适当同步。与特定DocumentsWriterDeleteQueue 的所有互动都受其外围DocumentsWriter 的控制。因此，虽然在DocumentsWriterDeleteQueue 中可能没有对单个方法进行适当的同步，但它们对世界的访问是同步的（或应该是同步的）。(我们暂且不去深究它是如何混淆所有权和使用权的--这是一个由众多贡献者共同完成的长期项目。少说两句吧）。

不过，我在冲洗过程中发现有一处没有同步。

这些操作不会同步为一个原子操作。也就是说，在创建newQueue 和调用getMaxSeqNo 之间，其他代码可能执行了documentsWriter 类中的序列号递增。我发现了错误！

但是，与大多数复杂的错误一样，找到根本原因并不简单。这时，一位英雄挺身而出。

战场上的英雄

我们的英雄登场了：李敖和他在 PASTA 实验室的同事们。我会让他解释他们是如何用 Fray 来拯救世界的。

Fray是由卡内基梅隆大学PASTA 实验室的研究人员开发的确定性并发测试框架。构建 Fray 的动机源于学术界和业界之间存在的一个明显差距：确定性并发测试在学术研究中已被广泛研究了 20 多年，但实践者们仍然依赖于压力测试--一种公认为不可靠且不稳定的方法--来测试他们的并发程序。因此，我们希望以通用性和实际应用性为首要目标，设计并实现一个确定性并发测试框架。

核心理念

Fray 的核心是利用一个简单而有力的原则：顺序执行。Java 的并发模型提供了一个关键特性--如果程序中没有数据竞赛，那么所有的执行都会在顺序上保持一致。这意味着程序的行为可以用一系列程序语句来表示。

Fray 以顺序方式运行目标程序：每一步都会暂停除一个线程之外的所有线程，从而使 Fray 能够精确控制线程调度。线程是随机选择的，以模拟并发性，但选择会被记录下来，以便随后进行确定性重放。为了优化执行，Fray 只在线程即将执行同步指令（如锁定或原子/易失性访问）时执行上下文切换。数据竞赛自由的一个很好的特性是，这种有限的上下文切换足以探索任何线程交错导致的所有可观察行为（我们的论文中有一个证明草图）。

挑战：控制线程调度

虽然核心理念看似简单，但实施 Fray 却面临着巨大的挑战。为了控制线程调度，Fray 必须管理每个应用程序线程的执行。乍一看，这似乎很简单--用定制的实现方法取代并发基元。然而，JVM 中的并发控制错综复杂，涉及字节码指令、高级库和本地方法的混合。

结果发现这是一个兔子洞：

例如，每条MONITORENTER 指令都必须在同一方法中具有相应的MONITOREXIT 。如果 Fray 将MONITORENTER 替换为对存根/模拟的方法调用，它还需要替换MONITOREXIT 。
在使用object.wait/notify 的代码中，如果替换了MONITORENTER ，也必须替换相应的object.wait 。该替换链可延伸至object.notify 及更远。
JVM 会在本地代码中调用某些与并发相关的方法（例如，当线程结束时，object.notify ）。替换这些操作需要修改 JVM 本身。
JVM 功能（如类加载器和垃圾收集 (GC) 线程）也使用并发基元。修改这些基元会导致与这些 JVM 函数不匹配。
在 JDK 中替换并发基元往往会导致 JVM 在初始化阶段崩溃。

这些挑战清楚地表明，全面替换并发基元是不可行的。

我们的解决方案：影子锁设计

为了应对这些挑战，Fray 使用了一种新颖的影子锁机制来协调线程执行，而无需替换并发基元。影子锁充当引导线程执行的中介。例如，在获取锁之前，应用线程必须与相应的影子锁交互。影子锁决定线程能否获取锁。如果线程无法继续执行，影子锁会阻止它，并允许其他线程执行，从而避免死锁，实现可控并发。这种设计使 Fray 能够透明地控制线程交错，同时保持并发语义的正确性。每个并发基元都在影子锁框架内进行了仔细建模，以确保合理性和完整性。更多技术细节可参见我们的论文。

此外，这种设计还旨在面向未来。通过只要求对并发基元的影子锁进行检测，它可以确保与较新版本的 JVM 兼容。这是可行的，因为 JVM 中并发基元的接口相对稳定，多年来一直保持不变。

测试

建立 Fray 之后，下一步就是评估。幸运的是，许多应用程序（如 Apache Lucene）已经包含并发测试。这种并发测试是常规的 JUnit 测试，会产生多个线程，执行一些工作，然后（通常）等待这些线程结束，然后断言一些属性。大多数情况下，这些测试都能通过，因为它们只进行了一次交织。更糟糕的是，如前所述，有些测试只是在 CI/CD 环境中偶尔失败，这使得这些失败极难调试。当我们使用 Fray 执行同样的测试时，我们发现了许多错误。值得注意的是，Fray 重新发现了以前报告过的由于缺乏可靠的重现而一直未修复的错误，包括本博客的重点：TestIDVersionPostingsFormat.testGlobalVersions 。幸运的是，有了 Fray，我们可以确定性地重放它们，并为开发人员提供详细信息，使他们能够可靠地重现和修复问题。

Fray 的下一步行动

我们非常高兴地听到 Elastic 的开发人员说，Fray 对调试并发错误很有帮助。我们将继续开发 Fray，让更多的开发者可以使用它。

我们的短期目标包括增强 Fray 确定性重放时间表的能力，即使在存在其他非确定性操作（如随机值生成器或使用object.hashcode ）的情况下也是如此。我们还致力于提高 Fray 的可用性，使开发人员无需任何人工干预即可分析和调试现有并发测试。最重要的是，如果您在调试或测试程序中的并发问题时遇到困难，我们很乐意听取您的意见。请随时在Fray Github 代码库中创建问题。

修复并发错误的时候到了

多亏了李敖和 PASTA 实验室，我们现在才有了这个测试的可靠失败实例！我们终于可以修好它了关键问题在于DocumentsWriterPerThreadPool 如何实现线程和资源的重复使用。

在这里，我们可以看到每个线程都是参照第 0 代的初始删除队列创建的。

然后，队列会在刷新时前进，正确查看队列中的前 7 个操作。

但是，在所有线程完成冲洗之前，又有两个线程被重新使用，用于处理另一个文件：

这将使seqNo 的增量超过假定的最大值，在冲洗过程中计算出的最大值为 7。请注意，_3 和段的额外numDocsInRAM 。 _0

这样，Lucene 就会错误地考虑冲洗过程中文档操作的顺序，从而导致测试失败。

就像所有优秀的错误修复一样，实际修复只需10 行代码。但两位工程师花了好几天才真正弄明白：

并非所有英雄都穿斗篷

是的，这是老生常谈，但却是事实。

并行程序调试非常重要。这些棘手的并发错误需要花费大量时间来调试和解决。虽然像 Rust 这样的新语言已经内置了一些机制来帮助防止类似的竞赛条件，但世界上大多数软件都是用Rust 以外的语言编写的。Java 经过这么多年的发展，仍然是最常用的语言之一。改进基于 JVM 语言的调试，让软件工程世界更美好。鉴于有些人认为代码将由大型语言模型编写，也许我们工程师的工作最终将只是调试糟糕的大型语言模型代码，而不是调试我们自己的糟糕代码。但是，无论软件工程的未来如何，并行程序调试对于维护和构建软件仍然至关重要。

感谢李敖和他的 PASTA 实验室同事们，是你们让这一切变得更加美好。