ConcurrentHashMap是如何提高并发时的吞吐性能（一）

ConcurrentHashMap是如何提高并发时的吞吐性能（一）
[e-mail]

为并发吞吐性能所做的优化
ConcurrentHashMap使用了一些技巧来获取高的并发性能，同时避免了锁。这些技巧包括：

• 为不同的Hash bucket（所谓hash bucket即不同范围的key的hash值）使用多个写锁；
• 利用JMM(Java Memory Model，java内存模型)的不确定性使得持有锁的时间最小化，或者从根本上避免使用锁。

ConcurrentHashMap为最常用的场景进行了优化，比如获取一个已经存在于Map中的值。事实上，绝大多数成功的get()操作在运行中根本就没有使用锁，这是因为利用了JMM的不确定性。

多个写锁
回忆一下HashTable的线程安全是因为使用了一个单独的全部Map范围的锁，这个锁在所有的插入、删除、查询操作中都会持有，甚至在使用Iterator遍历整个Map时也会持有这个单独的锁。当锁被一个线程持有时，就能够防止其他线程访问该Map，即便其他线程都处于闲置状态。这种单个锁的机制极大的限制了并发的性能。

而ConcurrentHashMap抛弃了仅仅使用整个Map范围的一个锁的机制，取而代之的是使用了32个锁，每个锁会负责hash bucket的一个子集（即负责一部分key的hash值范围）。而且这些锁仅仅被那些更改Map内容的操作使用，比如put(), remove()。拥有32个单独的锁意味时最多可以有32个线程同时修改Map，这并不是说如果有少于32个线程同时修改Map而没有线程被阻塞，32仅仅是理论上的并发写操作的极限，在实际中一般不一定会达到。在目前的软硬件条件下，对多数程序而言，32个锁总比一个锁要好。

Map范围的锁
32个独立的锁，每个锁负责hash bucket的一个子集，这意味着如果有些排他的访问操作，就需要获得全部的32个锁，比如rehashing（即扩充hash bucket的数量，当HashMap的key增长时重新分布key元素）就必须是排他的访问。但是JAVA语言本身没有提供一种简单的方式来获取变长的锁，由于这种操作不会频繁发生，那么ConcurrentHashMap是使用递归实现Map范围的锁。

JMM（Java内存模型）概览
JMM就是Java内存模型，它定义了Java的线程之间如何通过内存进行交互。简单说就是： JVM中存在一个主内存(Main Memory or Java Heap Memory)，JAVA中所有变量都储存在主存中，对于所有线程都是共享的。每个线程都有自己的工作内存(Working Memory)，工作内存中保存的是主存中某些变量的拷贝，线程对所有变量的操作都是在工作内存中进行，线程之间无法相互直接访问，变量传递均需要通过主存完成。工作内存里的变量, 在多核CPU的情况下, 将大部分储存于处理器高速缓存中, 高速缓存在不经过内存时, 所以线程之间也是不可见的。详细的关于JMM的介绍会在后面的文章中。

大家都知道，CPU尽量使用自己的寄存器内部的数据，这样会极大的提高性能。JAVA规范(JLS-Java Language Specification)中规定了一些内存操作不必立即被其他线程发现，并且还提供了两个语言层面的机制来确保在多个线程之间保持内存操作的一致性：synchronized和volatile。根据JSL中的描述"In the absence of explicit synchronization, an implementation is free to update the main memory in an order that may be surprising." （在没有显示的同步时，一个操作可以以一种令人惊讶的方式自由的更新主存。）这意思是说：没有同步时，在一个线程中写操作的操作顺序也许和另外一个线程的写操作顺序不一样，并且更新内存变量会在不确定的时间之后被其他线程发现。

而使用synchronized的最根本的原因就是确保线程访问关键代码段的原子性。synchronized实际上提供了三个功能atomicity, visibility, and ordering（原子性，可见性和顺序行）。所谓原子性很好理解也很直接，就是确保不同线程再次进入同一区域的互斥性，防止在同一时刻有多于一个线程可以访问到被保护的代码段。很不幸的是许多的文章只强调了synchronized的原子性方面，而不说其他两个方面。在JMM中，同步扮演了一个重要的角色，当获取和释放monitor（锁）的时候，同步操作使得JVM执行了内存屏障（execute memory barriers）。

当一个线程获取一个锁时，它便执行了一次内存读屏障（read barriers）——所谓内存屏障就是使得任何其他线程缓存的本地内存（CPU内部缓存或者CPU寄存器）无效，然后使得其他所有线程所在的CPU重新从主存（内存）读取这些变量的值。同样，在释放锁的时候，所有其他线程均执行了一次内存写屏障（write barriers）——Flush任何已经更改的变量到主存（内存）。互斥和内存屏障的结合意味着只要程序遵循正确的同步规则（这个同步规则就是：同步任何被写的变量会下次被另一个线程正确的读；或者是同步任何读一个下一次会被另一个线程正确的更改变量），每个线程都会看到它所使用的共享变量的正确值。

如果在访问共享变量时没有同步，你会碰到一些奇怪的事情，一些改变会很快的反应到其他线程里，而其他一些更改则需要花费一些时间才能反应到其他线程中。这样的结果就会使得你如果不用synchronized，那么你不能确保你看到一致的内存视图（即相关变量在不同的线程中的值会不一致，也许有一些值是脏数据）。通常的方法，也是推荐的方法去避免这些脏数据当然是正确采用synchronized。在这种情况下，比如在广泛使用的基础类ConcurrentHashMap中就值得使用一些额外的专门知识和功夫去开发，以获得高性能。

参考资料:
http://www.ibm.com/developerworks/java/library/j-jtp08223/
http://www.cs.umd.edu/~pugh/java/memoryModel/