无阻塞 Java 并发编程实践——异步互斥量

王铭鑫

2017 年 7 月入职 Qunar，现国际机票基础搜索部门 Java 开发工程师，熟悉并发编程和多态编程领域，对架构设计、性能调优略有涉猎。工作之余，参与修订 ISO C++ 国际标准，发表过 ISO C++ 提案（WG21 论文） P0642, P0801 和 P0957，分别对应并发编程、编译时编程和多态编程领域。

一、高性能并发编程的挑战

在高速发展的互联网时代，“并发”程序无处不在，而“写出优质的并发程序”也成为了用人单位评价程序员个人能力的重要指标。但如果大家尝试写过并发程序的话，会发现写好它们并非易事，尤其是写出性能符合大家期望的并发程序——即使费尽心力地做完了正确性测试或从理论上证明了程序的正确性。

根据我们的经验，损耗并发程序性能的主要有两个方面，一个是对于原子操作和并发数据结构的滥用，另一个就是阻塞。

对于原子操作（对应 Java中类）和并发数据结构（对应 Java中类），很多同学学习过后认为这些技术高效，于是在代码中大量使用它们，导致程序可维护性较低、性能亦达不到预期；笔者的建议是，在大家完整评估过引入原子操作和并发数据结构对程序性能和扩展性影响之前，尽量避免在程序中直接使用它们；在这一方面，本文不展开叙述。

对于阻塞，最直接也通常是最高效的解决方案就是将阻塞当前程序运行的逻辑转发至其他执行资源（例如线程或线程池），也就是我们常说的“异步”。但根据我们的调研，在以下两种情况下我们通常很难做到异步而不得不面临阻塞：

当需要对多个无关的异步调用的结果或副作用（Side-effect）进行合并或归约时。这就好比我们自己组装电脑的情形：首先我们在不同商家订购不同的电脑配件，包括CPU、内存条、主板、机箱、显示器等，这就好比我们发起了多个无关的异步调用；当这些配件依次送达后，我们自己动手组装，这就可以类比为合并和规约的过程。

当多个相关异步调用存在共享临界区（Critical section）时。当我们去银行给其他人转账时，我们一定不希望转账的过程被关于我或者他账户余额的其他操作所破坏，导致我们转出成功，而对方的余额却没有增加。这个转账的过程就是关于我们和对方账户余额的临界区。

对于第一点，笔者曾经尝试过将多对一同步原语（对应 Java 语言中,,等类）异步化，并成功抽象出了“并发调用”的概念，现已是一篇 ISO C++ 提案，其中包括了对性能、易用性、扩展性等多方面的诸多考量和初步的技术标准。使用此模式即可在不增加运行时开销的前提下简单地实现“多个无关异步调用的合并和规约”类的需求；对于相关细节本文不展开讨论，感兴趣的同学可以前往 ISO C++ 官方网站获取所述提案。

（ISO C++ 提案P0642http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0642r1.pdf）

对于第二点，根据我们的调研，现在还很少有足够高效和通用的解决方案以避免阻塞，这就是后文所致力于解决的核心问题。

二、阻塞 —— 程序性能杀手

假如我们有一段程序，并且这段程序会修改一些由多线程共享的数据，作为 Java 程序员我们会怎么做呢？对，用类或关键字加锁，这可能是我们大多数人的直接想法，导致我们很可能会写出以下代码：

试想这样的一个场景：在一台高性能服务器上，我们构造了一个有个线程的线程池用以执行规约类任务（例如合并多个异步 RPC 回调的数据）。这些任务总共分组，每组分别有个任务，每个任务平均执行毫秒。根据我们的需求，每组的任务在执行时需两两互斥以避免竞争，任意两个不同组别的任务均可并发执行，那么执行完所有任务理论上总共需要多长时间呢？

这是一个简单的数学题，只需要用所有任务的总时间除以线程数量即可，即毫秒。但如果我们使用 Java 语言中的类模拟这一情形做一些测试的话，会发现实际需要的执行时间可能会比这个理论值多很多。例如，当时，理论上执行完所有任务只需要，但经过我们的测试 ，完成所有任务平均需要的时间，吞吐率仅为理论值的！

为什么会有如此大的差距呢？大家应该可以想到，是阻塞。很多情况下，正如这个例子中那样，阻塞给我们并发程序带来的性能损失都远远超出了我们的预期，所以我们认为避免大量的阻塞是维持并发程序高效性的重要手段。

三、队列化

那么如何避免这种由于竞争产生的阻塞呢？熟悉 GUI 编程的同学可能应该听说过“消息环（Event Loop）”的概念，使用消息环便可以串行地处理并发请求，以避免对于 GUI 绘制的竞争。

事实上，在2012 年的会议上，Herb Sutter 先生（现微软架构师，兼 C++ 标准委员会主席）给出了更通用的结论："You can turn blocking into non-blocking by replacing a mutex with a message queue." (将一个互斥量换成一个消息队列，就可以把阻塞程序变成非阻塞程序)。

Herb Sutter 也使用 C++ 语言给出了一个基本实现，我将其改写为 Java 语言如下（原程序中以命名，笔者认为此命名语义不够清晰，故在 Java 实现中修改为（异步管程）。为了减少篇幅，此处异常处理部分从简。如果大家不了解“管程”的概念的话可以参照 Wikipedia 中的介绍）：

很容易看出，这个程序使用了一个线程和一个阻塞队列将对于一个类型为的共享对象的同步操作转为了异步操作，用户只需要调用此类的方法并传入对共享对象的处理逻辑程序即可立即返回。但这个程序有两个不足之处：

从性能角度讲，如果在程序中大量使用此模型可能会创建和销毁大量的线程从而引入额外的开销，并且当竞争较少时，这些线程的利用率也不高；

从易用性角度讲，这个 API 不支持对于共享对象操作的后续逻辑，例如记录日志或监控服务运行情况。尽管我们可以将这部分逻辑异步化放至的逻辑中，这也不利于我们管理执行资源，且可能延迟执行后续临界区逻辑。

四、异步互斥量

基于以上动机，本文提出了“异步互斥量（Async Mutex）”的概念并首次使用 Java 语言实现。我们希望异步互斥量可以做到：

保持“异步管程”的异步特性，不阻塞临界区逻辑的调用方；

顺序执行用户指定逻辑，每部分逻辑均可由用户指定执行策略，相当于将线程资源从上述异步管程实现中解耦出来以增加对执行资源的复用；

允许用户指定对于临界区操作的后续逻辑。 根据我们的目标，我们不再需要阻塞任何程序的执行，所以实现中也没有必要继续依赖于阻塞队列了，并且从队列中取出数据的过程也不再需要保证其并发安全性。另外，由于 Java 语言的 GC 特性，在实现过程中应注意不能及时 GC 的情况，因为这有可能导致潜在内存泄漏的问题。

在设计 API 阶段中，由于“异步互斥量”与 Java 语言中 Lock 接口语义类似，我们原本希望令其实现 Lock 接口，但经调研我们发现，保留阻塞的、等方法会让用户感到困惑，难以在短时间内熟练使用这一技术；且实现这些方法会增加异步互斥量的运行时抽象开销，实际测试时性能也通常不及 Java 语言中的 ReentrantLock，故我们决定仅对此类开放一个异步非阻塞接口，草拟技术标准如下：

输入： 为执行临界区逻辑和退出临界区后续逻辑的执行资源， 为临界区逻辑， 为退出临界区后续逻辑。

效果：在可以进入临界区时使用 异步地执行 ，并以 执行的返回值为输入顺序地执行 。其中，对于 的所有 操作中对于 的调用操作顺序执行，对于 的调用操作可能并发执行。

异常：若将异步任务转发至 过程中抛出任何异常，该异常不应被扩散，且该次 操作所关联的 和 均不应被执行。若在执行 的过程中抛出任何异常，该异常不应被扩散，且该次 操作所关联的 不应被执行。若在执行 的过程中抛出任何异常，该异常不应被扩散。

目前 Java 语言中大部分使用了 接口的 / 方法或在未调用关于某对象 / 相关方法的情况下对该对象使用 关键字的情形中，通常可以使用异步互斥量避免阻塞问题。例如我们在前文中提及的代码片段：

借助 Java 8 及之后版本中的 lambda 表达式可以使用类简单地改写为：

其中， 可能是一个线程池，需要我们在外部管理。

那么， 的性能如何呢？我们在相同的条件下使用 重复了第二部分中的实验，平均运行时间为 ，吞吐率是使用 版本的近 倍！

当然，这个数据仍然比理论最小值多了近 。据我们分析，导致该结果一方面由于测试硬件为 核 CPU，并行能力有限；一方面由于测试任务量较大，不可避免地需要引入较多线程调度开销；另一方面，任务的入队操作也存在竞争，从而引入相应开销。

为保证测试的完整性，我们基于上一章中的测试模型，调整参数进行了更多的测试。测试结果表明，随着任务组数的上升，阻塞产生的副作用随之上升；当组数足够少时，使用 实现要略优于我们提出的 ，但通常不会产生性能瓶颈。例如，在所述测试模型中，取 时，测试结果显示 的平均运行时间是 ；而 平均需要 ，除去我们的测试逻辑外性能损耗稍低。但总体来说，在存在运行资源共享的场景中， 性能和可伸缩性比 更好。

在之前版本的实现中，我们采用了 Java 语言提供的 维护任务队列，但在性能测试中我们发现由于 内部维护了一些我们不关心的额外状态，且提供了额外的取出任务时的线程安全保证，导致在高并发下性能不符合我们的预期。经过评估，我们借助 在 内部实现了链表存储机制，经测试，添加任务的性能大约提升 。

以下代码是 AsyncMutex 的基本实现，希望可以辅助大家的理解。

五、跳出 JVM 看异步互斥量

本文通过分析并发程序设计中性能瓶颈产生原因，针对传统互斥量的阻塞问题提出了名为“异步互斥量”的解决方案并使用 Java 语言实现，实验结果显示其可伸缩性在大部分情况下均优于 Java 语言内置的锁机制。

受朱仕智同学的启发，笔者意识到不止在 Java / C++ 等这些定义在共享内存体系结构中的编程模型存在阻塞的问题；在分布式情形中这样的问题同样存在。如果我们将此思想应用于分布式情形中会得到像异步互斥量那样的可伸缩性提升吗？

一方面，笔者认为此编程思想与平台相关性通常不大。例如在一个服务集群中，一些热点数据常驻 Redis，而我们的服务可能会并发地修改这些数据。在这种情况下我们通常会采用分布式互斥量确保这类分布式事务的原子性；但如果阻塞时间过长，连接无法及时释放，客户端线程也处于阻塞状态，同样会产生性能瓶颈，所以异步互斥量的思想在理论上也适用于这类情况。

另一方面，由于不同系统架构的原语和 IO 模型的差异性，例如 Redis 中无 CAS 等原子操作原语，但支持 lua 脚本的原子化执行，所以对应的具体实现机制可能也与本文中对于异步互斥量的 Java 语言实现相去甚远。

注： 测试环境如下：