随着多核处理器成为主流，应用开发人员对于如何编写高伸缩性的应用以利用底层硬 件的优势这个问题面临巨大的压力。此外，遗留系统不得不移植到新的架构上。保证应用 伸缩性的一种有效方式是使用高伸缩性组件构建应用。举例来说，在各种应用中， java.util.concurrent.ConcurrentHashMap可以替代同步的HashTable，使应用伸缩性更 好。因此，向应用直接提供一套高伸缩性构造块以引入并行是非常有用的。
我们创建了一套高伸缩性并发Java组件作为Amin库项目的一部分。在本文中，我们将 介绍一些创建该开源库的想法。
概述
作为软件工程师，我们不得不并行我们的应用使它们在多核机器上很好的伸缩。一种 并行方式是把它们分成若干子任务，其中每一个子任务与应用的其他子任务通信和同步。 这通常被称为基于任务的并发。我们可以基于子任务的通信模式将应用分类。
尴尬式并行——应用的子任务从不或者很少与其他子任务通信。通常情况下，每一个 任务只处理自己的私有数据。一些例子包括：
蒙特卡洛模拟程序
快速排序程序，使用fork/join模式很容易实现并发。当我们处理尴尬式并行应用时容 易得到很好的伸缩性。
粗粒度和细粒度式并行——这些应用的子任务需要互相通信。根据子任务之间的通信 频率可以把程序分为粗粒度和细粒度并行。一个例子是生产者/消费者问题。生产者产生 驱动消费者的数据。从生产者到消费者的数据发送需要通信。相比尴尬式并行应用，处理 子任务频繁交互的应用较难得到良好的伸缩性。
经过为伸缩性而优化的组件非常有益于解决这些困难问题。举例来说，如果存在一个 高伸缩性队列组件，那么实现生产者/消费者伸缩性相对容易些。本文中，我们提供了若 干通用技术提高软件组件的伸缩性。
针对伸缩性的分析
应用分析是开发过程的重要方面。分析是为了了解应用的运行特征。分析数据经常被 用于提高应用的性能和伸缩性。大多数分析器遵从一个简单的执行模式，其中有一个配置 阶段。在该阶段，根据信息获取的类型，会配置不同层次的计算堆栈。硬件计数器可以被 用来监控硬件事件。操作系统可以通过配置各种操作系统事件来监控。如果在计算层次中 还有虚拟机，那么需要配置以访问虚拟机的事件。最后，应用需要配置以得到真实应用的 事件。优秀的分析器能够在不要求应用重新编译的情况下完成这些配置。大多数分析器通 常都配置虚拟机和应用层。应用在配置之后运行时，会生成跟踪信息，例如函数运行时间 、资源使用情况、硬件性能参数、锁使用、系统时间、用户时间等等。不同的分析器会在 把跟踪信息输出到文件系统前做一些计算。最后，分析器会通过显示界面可视化这些数据 。
用于并发应用的分析器需要提供有关线程、锁竞争和同步点的详细信息。我们使用了 下面一些分析器作为Amino性能分析：
Java锁监控器（Java Lock MoniTor）——Java开发人员使用该工具分析应用中锁的使 用情况。在运行时，监控组件收集各种锁数据用于发现锁竞争。该工具能够通过表格展示 详细的锁和竞争信息。IBM Java Lock Analyzer (JLA)是另一个提供锁信息的工具。它与 JLA类似，只不是通过图形界面显示缩合竞争数据。两个工具都支持x86和Power平台。
THOR ——该工具用于详细分析Java应用的性能。它能够深入分析完整的执行栈，从硬 件到应用层。信息来自于栈的四个层面——硬件、操作系统、JVM和应用。用户可以看到 锁竞争的信息以及对应的代码、瓶颈、多核之间的线程迁移和竞争导致的性能下降。该工 具支持x86和Power平台。
AIX性能工具——IBM的AIX操作系统自带一套底层的性能分析和调试工具。其中包括：
Simple Performance Lock Analysis Tool (SPLAT) ——该工具是AIX系统上的一个锁 分析工具，可以通过命令行运行，用于分析各种内核级的锁。同时，它也可以分析和显示 用户级锁（读/写和mutex）的竞争。应用必须启用跟踪选项，SPLAT需要用到这些跟踪数 据。
XProfiler——该分析工具基于X—Windows，用于C语言应用的函数级分析，能够显示 在用户代码中计算敏感的函数。如果要使用XProfiler，代码需要使用特殊的标志（-pg选 项）编译。
prof、 tprof和gprofncbr——各种prof命令都可以用于分析用户应用。prof命令能够 得到所有应用中的外部符号和函数。gprof是 prof的超集，可以获得应用的调用关系图。 最后，tprof用于得到应用的宏观和微观的分析信息。tprof能够得到各个指令、子程序、 线程、进程的计时数据，还有用户模式函数、库函数、Java类、Java方法、内核函数、内 核扩展等的处理器使用情况。
减少热点
传统的性能调优方法，比如适用于顺序应用的方法也适用于并行应用。在完成传统调 优之后，我们需要检查共享数据是如何被多线程访问的。通过使用JLM或者JLA，我们能够 发现线程在访问共享资源时是如何竞争的。
举例来说，如果应用有100个线程，并且所有的线程都需要从一个 java.util.HashTable提取/存储元素，该应用的性能由于线程竞争会下降。每一个线程需 要在访问该HashTable之前等待很长时间。
如果我们使用类似JLM的工具就会发现，该Hash表关联的moniTor使用非常频繁。解决 这一问题的办法是使用能够替代HashTable的高扩展性 组件。在本例中，我们可以通过 java.util.concurrent.ConcurrentHashMap替换该hash表。 ConcurrentHashMap把它的内 部数据结构分成若干段。在应用中使用ConcurrentHashMap替换HashMap替换使线程针对多 个子组件竞争而不是单个大组件。使用ConcurrentHashMap的应用产生竞争的几率比之前 要小得多。
还有一种办法降低访问共享组件的竞争几率。如果一个组件具有相反语义的操作，如 栈的压入和弹出，这两种操作可以无需接触核心数据结构即可完成。这种技术最 早由 Danny Hendler、Nir Shavit和Lena Yerushalmi引入，已经在Amino库中实现。这种方法 的性能改善见图1。
图1.性能比较：EBStack和TreiberStack
使用无锁/无等待算法
传统上，大家都采用基于锁的方法来确保共享数据的一致性和对关键区域的互斥访问 。锁的概念易懂，但基于锁的算法引起了很多挑战。其中一些著名的问题包括死锁、活锁 、优先级倒置和锁竞争等。锁竞争会减少组件和算法的可扩展性。
无锁和无等待算法到现在已经存在二十多年了。它们被认为可以能够解决大部分与锁 有关的问题。这些算法支持在不使用任何锁算法的情况下更新共享数据结构，不仅如此， 还有助于创建扩展性良好的算法。最初，这些无锁和无等待的算法纯粹是理论兴趣。但是 ，随着算法社区的发展和新硬件的支持，无锁技术在现实产品中得到了越来越多的应用， 比如操作系统内核、虚拟机、线程库等。
从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操作，取而代之的是采用一个双链表，其中的指针在更新时只需要一次存储操作 ，如果事件乱序导致双链表不一致则可以修复。
我们做了一次基准测试来比较ConcurrentLinkedQueue（JSR166y）和Mos-Queue的性能 。结果在图3中显示。对于大量线程来说，Mos-Queue的性能优于JDK ConcurrentLinkedQueue。
图3. 性能比较：ConcurrentLinkedQueue和Mos-Queue
更多有关Mos-Queue的信息参见Mozes和Shavit的论文《An Optimistic Approach to Lock-Free FIFO Queues》。
减少内存分配
Java虚拟机拥有一套强大、有效的内存管理体系。垃圾回收器能够压缩现有对象，以 确保在垃圾回收之后Java堆里没有空隙。因为空闲空间在垃圾回收之后都是连续的，所以 内存分配不多是增加了一个指针而已。
这对多线程应用同样有效，如果内存使用不敏感的话。JVM为每一个线程分配了一个线 程范围的缓存。在内存分配时，线程范围的缓存首先被使用。只有在线程范围的缓存被耗 尽之后才会使用全局堆。
在线程范围内分配内存对应用性能非常有益，但是如果分配过于频繁，则会不起作用 。根据我们的经验，线程范围的缓存在分配频率高的情况下会很快耗尽。
如果在循环中需要暂时性的对象，则线程范围的类会比较有益。如果我们在线程本地 对象中存储临时对象，我们可以在每一次循环迭代中重用它。虽然，线程本地类会增加额 外的负担，但是大多数时候都比在内存中频繁分配内存要好。
图 4.性能比较：线程本地和分配
结论
在本文中，我们介绍了使用Java创建高扩展性组件的几个重要原则。一般来说，这些 原则通常很有帮助，但是它们无法替代谨慎的测试和性能调优。
而是深沉的意志恢弘的想象炙热的恋情；青春是生命的深泉在涌流。
