使用Java构建高伸缩性组件

核心提示： 从JDK 1.5以后，JDK包含了这些无锁算法，使用Java构建高伸缩性组件(5)，比如ConcurrentLinkedQueue、AtomicInteger等，它们的伸缩性通常比对应的基于锁的组件要好，取而代之的是采用一个双链表，其中的指针在更新时只需要一次存储操作，当我们在Amino库实现新

从JDK 1.5以后，JDK包含了这些无锁算法，比如ConcurrentLinkedQueue、AtomicInteger等。它们的伸缩性通常比对应的基于锁的组件要好。当我们在Amino库实现新组件时，我们会使用目前研究的最新无锁算法。这使得Amino数据结构扩展性和效率非常好。但是有时候，特别是在低核硬件上，无锁数据结构比基于锁数据结构的吞吐量差，但是一般来说，它们的吞吐量比较好。

尽可能减少比较—交换（CAS）操作

从JDK 1.5以后，JDK包含了由Doug Lea开发的位于java.util.concurrent包的无锁的FIFO（先进先出）队列。该队列采用的算法基于单链表的并发操作，最初由 Michael和Scott开发。它的出列操作需要一次比较—交换，而入列操作需要两次比较—交换。这对入列和出列操作来说太容易了。但是分析数据（图 2）显示比较—交换操作占用了大部分执行时间，同时入列操作需要两次交换—比较，这增加了失败的概率。在现代多处理器上，一次成功的比较—交换操作要比一次加载或者存储的时间长一个数量级，因为它们需要独立占用和冲刷处理器写缓存。

图2. CAS操作的执行时间

从图2可以看出，CAS操作执行时间的百分比为46.08%，几乎占了全部执行时间的一半。分析数据有一个操作的延迟。真正的时间是在"SETE AL"指令之后发生的。

Mozes和Shavit（MoS-queue）在它们的无锁队列算法中，提供了一种新颖的办法来降低入列操作时CAS的数量。其关键点在于替换单链表，因为其中的指针在插入时需要浪费一次CAS操作，取而代之的是采用一个双链表，其中的指针在更新时只需要一次存储操作，如果事件乱序导致双链表不一致则可以修复。