Lucene 中的并发错误：如何修复乐观并发失败

作者：来着 Elastic Benjamin Trent 及 Ao Li

感谢 CMU PASTA 实验室开发的确定性并发测试框架 Fray，我们找到了一个棘手的 Lucene 漏洞并将其修复。

是的，另一个修复错误博客。但这个故事有一个转折，一位开源英雄突然出现并拯救了一切。

调试并发错误并非易事，但我们会深入研究它。进入 Fray，这是 CMU 的 PASTA 实验室推出的确定性并发测试框架，它将不稳定的故障转变为可靠的可重现的故障。得益于 Fray 巧妙的影子锁设计和精确的线程控制，我们追踪到了一个棘手的 Lucene 错误并最终将其消除。这篇文章探讨了开源英雄和工具如何让并发调试变得不再那么痛苦，并且让软件世界变得更加美好。

更多有关乐观并发的文章，请参考：

Elasticsearch：深刻理解文档中的 verision 及乐观并发控制
Elasticsearch：文档版本控制和乐观并发控制

软件工程师的祸根

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

org.apache.lucene.sandbox.codecs.idversion.TestIDVersionPostingsFormat > testGlobalVersions FAILED
    java.lang.AssertionError: maxSeqNo must be greater or equal to 7442 but was 7441
        at __randomizedtesting.SeedInfo.seed([B97A2BDBC7E40BF6:B4D76006D5101E6]:0)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.DocumentsWriterDeleteQueue.close(DocumentsWriterDeleteQueue.java:325)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.DocumentsWriter.flushAllThreads(DocumentsWriter.java:659)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.IndexWriter.getReader(IndexWriter.java:576)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.StandardDirectoryReader.doOpenFromWriter(StandardDirectoryReader.java:381)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.StandardDirectoryReader.doOpenIfChanged(StandardDirectoryReader.java:355)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.StandardDirectoryReader.doOpenIfChanged(StandardDirectoryReader.java:345)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.index.DirectoryReader.openIfChanged(DirectoryReader.java:170)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.search.SearcherManager.refreshIfNeeded(SearcherManager.java:144)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.search.SearcherManager.refreshIfNeeded(SearcherManager.java:52)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.search.ReferenceManager.doMaybeRefresh(ReferenceManager.java:167)
        at org.apache.lucene.core@10.0.0-SNAPSHOT/org.apache.lucene.search.ReferenceManager.maybeRefresh(ReferenceManager.java:213)

对于那些讨厌 Java 堆栈跟踪的人，我深表歉意。注意，delete 并不一定意味着 “delete”。它还可以指示文档 “update”，因为 Lucene 的段是只读的。

Apache Lucene 通过 DocumentsWriter 类管理每个写入文档的线程。该类会创建或重用线程进行文档写入，并且每个写入操作都会在 DocumentsWriterPerThread（DWPT）类中管理其信息。此外，写入器会在 DocumentsWriterDeleteQueue（DWDQ）中跟踪被删除的文档。这些结构在内存中维护所有文档变更操作，并会定期刷新，以释放内存资源并将数据持久化到磁盘。

为了防止阻塞线程（blocking threads ）并确保高吞吐量，在并发系统中，Apache Lucene 仅在非常关键的部分进行同步（synchronize）。虽然这种做法在实践中通常是有利的，但就像任何并发系统一样，其中仍然隐藏着潜在的风险和挑战。

虚假的希望

我最初的调查发现了一些关键部分，它们并没有被正确地同步。所有对 DocumentsWriterDeleteQueue 的交互都由其封闭的 DocumentsWriter 控制。因此，尽管 DocumentsWriterDeleteQueue 中的某些方法可能没有适当同步，但它们对外部世界的访问是（或者应该是）受控的。（我们暂且不深入讨论这如何影响所有权和访问控制 —— 毕竟，这是一个由许多贡献者长期维护的项目，得给它点宽容。）

然而，我在一次 flush 过程中发现了一个未同步的地方。

// Advance the queue, meaning create a new one to keep track of deletes
// Since we have been flushed, let's starting tracking again
DocumentsWriterDeleteQueue newQueue = documentsWriter.deleteQueue.advanceQueue(perThreadPool.size());
// OK, get the current new maximum sequence number for optimistic concurrency
seqNo = documentsWriter.deleteQueue.getMaxSeqNo();
// Reset to the new queue
documentsWriter.resetDeleteQueue(newQueue);

这些动作并未同步到单个原子操作（atomic operation）中。意思是，在创建 newQueue 和调用 getMaxSeqNo 之间，其他代码可以执行增加 documentsWriter 类中的序列号。我发现了错误！

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

Fray 中的英雄

我们的英雄登场了：来自 PASTA Lab 的 Ao Li 及其同事。我会让他来解释，他们如何用 Fray 挽救了局面。

Fray 是由 卡内基梅隆大学 PASTA Lab 研究人员开发的一款 确定性并发测试框架。构建 Fray 的动机来源于学术界与工业界之间的明显鸿沟：尽管确定性并发测试在学术研究中已经被深入研究了 20 多年，但在实际应用中，开发人员仍然主要依赖 压力测试 来测试并发程序。然而，压力测试普遍被认为不可靠且容易出错。因此，我们希望设计并实现一个以 通用性和实际可用性 为核心目标的 确定性并发测试框架。

核心思想

从本质上讲，Fray 利用了一个简单但强大的原则：顺序执行。 Java 的并发模型提供了一个关键属性 —— 如果程序没有数据争用，则所有执行都会显得顺序一致。这意味着程序的行为可以表示为一系列程序语句。

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

挑战：控制线程调度

尽管核心思想看似简单，但实施 Fray 却面临重大挑战。为了控制线程调度，Fray 必须管理每个应用程序线程的执行。乍一看，这似乎很简单 —— 用定制的实现取代并发原语。然而，JVM 中的并发控制非常复杂，涉及字节码指令、高级库和本机方法的混合。

结果，这变成了一个复杂且难以预见的难题：

例如，每条 MONITORENTER 指令必须在同一方法内有对应的 MONITOREXIT。如果 Fray 用一个存根（stub）或模拟（mock）方法替换 MONITORENTER，那么它也必须相应地替换 MONITOREXIT。
在使用 object.wait/notify 的代码中，如果 MONITORENTER 被替换，那么对应的 object.wait 也必须被替换，而这个替换链会进一步扩展到 object.notify 及其他相关操作。
JVM 在本地代码中调用某些与并发相关的方法（例如，当一个线程结束时，可能会调用 object.notify）。替换这些操作意味着需要修改 JVM 本身。
此外，JVM 的核心功能（如 类加载器 和 垃圾回收（GC）线程）也使用并发原语。修改这些原语可能会导致 JVM 的功能与自定义的实现不匹配。
更严重的是，替换 JDK 内的并发原语往往会导致 JVM 在初始化阶段崩溃。

这些挑战表明，全面替换并发原语并不是一个可行的方案。

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

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

此外，这一设计具有面向未来的特性。通过仅在并发原语周围插入影子锁的监控，它确保了与 JVM 新版本的兼容性。之所以可行，是因为 JVM 中并发原语的接口相对稳定，并且多年未发生变化。

测试 Fray

在构建完 Fray 后，接下来的步骤是评估。幸运的是，许多应用程序，如 Apache Lucene，已经包含了并发测试。这些并发测试通常是常规的 JUnit 测试，它们会启动多个线程，执行一些工作，然后（通常）等待这些线程完成，再断言某些属性。大多数情况下，这些测试通过了，因为它们仅测试了一个线程交替。更糟糕的是，一些测试只会在 CI/CD 环境中偶尔失败，正如前面提到的那样，这使得这些故障非常难以调试。当我们用 Fray 执行相同的测试时，我们发现了许多 bug。特别是，Fray 重新发现了一些以前报告的 bug，这些 bug 由于无法可靠地重现而一直没有修复，其中包括本博客重点提到的：TestIDVersionPostingsFormat.testGlobalVersions。幸运的是，通过 Fray，我们可以确定性地重放这些问题，并为开发人员提供详细信息，使他们能够可靠地重现并修复这些问题。

Fray 的下一步

我们很高兴听到 Elastic 的开发人员表示 Fray 对调试并发 bug 非常有帮助。我们将继续致力于 Fray 的开发，以便让更多开发者受益。

我们的短期目标包括增强 Fray 确定性重放调度的能力，即使在存在其他非确定性操作（如随机值生成器或使用 object.hashcode）的情况下，也能准确重现调度。此外，我们还计划提高 Fray 的可用性，使开发者能够分析和调试现有的并发测试，而无需手动干预。最重要的是，如果你在调试或测试程序中的并发问题时遇到困难，我们非常希望听到你的声音。请随时在 Fray 的 GitHub 仓库中创建问题。

是时候解决这个危险的事情了

感谢 Ao Li 和 PASTA 实验室，我们现在有了这个测试的可靠失败实例！我们终于可以解决这个问题了。关键问题在于 DocumentsWriterPerThreadPool 如何实现线程和资源重用。

1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_0, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t0 20 getNextSequenceNumber 1 called from stack:
<snip>...</snip>
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_1, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_5, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_2, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_6, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_3, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> new Writer: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_4, aborted=false, numDocsInRAM=0, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]

这里我们可以看到每个被创建的线程，引用第 0 代的初始删除队列。

然后，队列前进将在刷新时发生，正确看到队列中的前 7 个操作。

1> DWDQ: [ generation: 0 ] id: 245403753 tid: t020 advanceQueue called from stack with maxSeq 9 lastSeqNo: 1 maxNumPendingOps: 7:
<snip>...</snip>
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t525 getNextSequenceNumber 2 called from stack:
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t828 getNextSequenceNumber 3 called from stack:
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t727 getNextSequenceNumber 4 called from stack:
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t626 getNextSequenceNumber 5 called from stack:
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t424 getNextSequenceNumber 6 called from stack:
1> DWDQ: [ generation: 0 ] id: 245403753 tid: t323 getNextSequenceNumber 7 called from stack:

但是，在所有线程完成刷新之前，有两个线程会被重新用于处理另一个文档：

1> getAndLock: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_0, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]
1> getAndLock: DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_3, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds]

然后，这些将使 seqNo 增加到假定的最大值之上，该最大值在刷新期间计算为 7。请注意段 _3 和 _0 的额外 numDocsInRAM

1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_2, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_3, aborted=false, numDocsInRAM=2, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_6, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_4, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_5, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_1, aborted=false, numDocsInRAM=1, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove
1> DocumentsWriterPerThread [pendingDeletes=gen=0, segment=_0, aborted=false, numDocsInRAM=2, deleteQueue=DWDQ: [ generation: 0 ], 0 deleted docIds] checkout to remove

因此导致 Lucene 错误地解释刷新期间文档操作的顺序并引发此测试失败。

与所有好的错误修复一样，实际修复大约需要 10 行代码。但两位工程师花了几天时间才真正弄清楚：

并非所有英雄都披着斗篷

是的，这是陈词滥调 —— 但这是事实。

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

感谢 PASTA 实验室的 Ao Li 和他的同事们使它变得更加出色。

Elasticsearch 包含许多新功能，可帮助你为你的用例构建最佳的搜索解决方案。深入了解我们的示例笔记本以了解更多信息，开始免费云试用，或立即在本地机器上试用 Elastic。

原文：Concurrency bugs in Lucene: How to fix optimistic concurrency failures - Elasticsearch Labs