JavaOne：Cliff Click 谈论可伸缩、非阻塞的编码方式 -- 不要发布

你的并发代码能有多快？早在 1967 年，Gene Amdahl 就指出了影响这一问题的主要限制。程序中只有一部分可以完全并行地运行，也只有这部分才能直接在拥有越来越多处理器内核的机器上获得良好的伸 缩性。程序的剩余部分则只能顺序执行。Amdahl 法则强调的主要问题是锁争夺，这个问题会随着处理器内核数的增加而逐渐恶化。多数共享存储器硬件的大型 CPU 控制系统都支持非常快速的并发读操作，但会限速于“1-cache-miss-per-write”或者“1-memory-bus- update-per-write”，因此避免所有 CPU 对同一位置进行写操作是非常关键的。即使利用读写锁，系统伸缩度也很难超越 50-100 个 CPU。多核处理器是一个正在发展的产业趋势，几乎全部硬件供应商都在不遗余力地朝着多核的方向努力。Azul 即将开发出可投入使用的 768 核的处理 器，Sun 的 Rock 拥有 64 核，就连基于 x86 的商用硬件也在增加核的数量。因此锁争夺的问题将成为程序员编写高性能代码的拦路虎。

Azul Systems 的资深工程师 Cliff Click 博士在今年的 JavaOne 大会上进行了演讲（下载幻灯片），介绍了一些可以帮助我们用Java 编写出可伸缩、非阻塞代码的技术。总体来说，他介绍的方法实现了一个非阻塞算法，这个算法可以保证停止某个特定线程并不会导致整体进程的停止。

Click 的演讲主要包括下面几部分：

1. 一个大型的、快速的包含所有数据的数组，该数组允许快速的并行数据读取，也允许并行的、递增的并发复制。
2. 数组元素的原子更新（需要使用 java.util.concurrent.Atomic.*）。在 Azul/Sparc/x86 处理器上，原子更新将使用“比较并交换（CAS）”原语实现，而在 IBM 的平台上，将使用“链接加载 / 条件存储（Load Linked/Store-conditional，LL/SC）”原语。
3. 从对每个数组元素的原子更新与逻辑上的复制操作中抽象出来的有限状态机（FSM）。FSM 支持数组的大小调整，并用于控制写操作。

有了这些基本概念和元素后，Click 接着将大量锁自由的 FSM 步骤（比如每个 CAS 步进）组合成一个非阻塞算法。每个 CAS 的成功都是局部成功，同时一个 CAS 的失败则意味着另一个 CAS 会继续。如果一个 CAS 成功，状态机就会前进，同时失败的 CAS 就会重试。

Click 已经实现了两个示例，分别是位向量（Bit Vector）和哈希表（Hash Table），它们的源代码可 以在SourceForge 上获得。同时Click 正在开发第三个示例（FIFO 队列）。让我们以哈希表为例来深入研究一些细节，哈希表是一个由键值对组 成的数组，其中Key 在偶数的位置上、Value 在奇数的位置上。每个元素都独立地进行CAS 操作，但是状态机会同时跨越两个元素，甚至在复制阶段包括来 自两个数组的不同元素。Click 实现的哈希表支持并发插入、移除测试（remove test）、重置大小，同时该实现还通过了ConcurrentHashMap 的Java 兼容性测试集（JCK）。在Azul 的768 核的硬件系统上，该 哈希表在每秒超过十亿次读操作、同时每秒超过千万次更新操作时，可以获得线性的伸缩性。

InfoQ 与 Click 博士还谈到了他目前研究工作的一些背景。在这次 JavaOne 的演讲期间，他特意强调了几个用 Java 编写哈希表时存在的问题，因 此在被问到 Java 做这样的工作有多合适时，他回答说：“事实上是非常合适的……它非常准确地应用了存储模型（并且实现得非常好）。但是它在细粒度控制上 存在不足，这些不足只带来很小的性能损耗，我可以忽略它们。缺乏细粒度控制（也就是直接 ASM 存取）可能会在 OS 设计或者设备驱动程序中带来问题，但是对 数据结构不会产生影响。”

InfoQ 还问他建议人们何时使用他实现的数据结构。Click 的回答是，在那些“久经考验”的实现变得太慢、难以使用之时：

“如果单独的数据结构被激烈争夺；而且你已经尝试过 java.util.concurrent.ConcurrentHashMap 等实现了。那么我的实现在没有负载的情况下并不会显著提升性能（也就没有什么理由使用它），但在下面的情况下，却完全不同了：

• 当有超过 32 个 CPU 同时争夺时，或者
• 写操作占读写操作总数的比例很高时。
  这种转变会带来很大的变化，因此，使用它以前要先进行测试。”

目前，围绕 Java 中的并发有很多动作，Click 博士的研究工作所解决的问题与 fork/join 框架基本类似，后者正被考虑加入 Java 7。尽管 Click 本人不是专家组的成员，但他经常向专家组提供帮助。

查看英文原文： JavaOne: Cliff Click on a Scalable Non-Blocking Coding Style