并发读写缓存实现机制(一)：为什么ConcurrentHashMap可以这么快？

　　大家都知道ConcurrentHashMap的并发读写速度很快，但为什么它会这么快？这主要归功于其内部数据结构和独特的hash运算以及分离锁的机制。做游戏性能很重要，为了提高数据的读写速度，方法之一就是采用缓存机制。因此缓存的性能直接影响游戏的承载量和运行流畅度，作为核心基础设施，缓存必须具备以下方面的功能：

  1.快速定位数据 2.并发变更数据 3.数据的过期控制与异步写入 4.高并发的情况下缓存数据的一致性   　　接下来，我就就几篇文章从上述几个方面来讲述下单服务器的缓存实现原理，本文的缓存是在guava的Cache基础上进一步扩展，原google缓存文档可参考：http://code.google.com/p/guava-libraries/wiki/CachesExplained   注意：本文是guava的Cache增强版，因此源码有稍许改动，详细源码请参考：https://github.com/cm4j/cm4j-all。   系列文章目录： 并发读写缓存实现机制(零)：缓存操作指南 并发读写缓存实现机制(一)：为什么ConcurrentHashMap可以这么快？ 并发读写缓存实现机制(二)：高并发下数据写入与过期 并发读写缓存实现机制(三)：API封装和简化

1.ConcurrentHashMap的数据结构

　　我们知道，一本书有着丰富的内容，那如何从一本书中找到我所需要的主要内容呢？自然而然我们就想到目录和子目录，首先，目录把书的内容分成很多个小块；其次，目录也是一个索引，通过目录我们就知道对应内容位于这本书的第几页，然后我们再按顺序浏览就能找到我们所需要的文章内容。   　　google的Cache借鉴了JDK的ConcurrentHashMap的设计思路，其本质就是基于上述流程设计的，翻看两者源码，有很大一部分是相同的，为了更好的理解缓存的高并发的实现，我们先来探索下ConcurrentHashMap的数据结构图：     　　由上图我们可以看出，首先ConcurrentHashMap先把数据分到0-16个默认创建好的数组中，数组里面的元素就叫segment，相当于书的大目录；每个segment里面包含一个名叫table的数组，这个数组里面的元素就是HashEntry，相当于书的一个子目录；HashEntry里面有下一个HashEntry的引用，这样一个一个迭代就能找到我们所需要的内容。   　　ConcurrentHashMap 类中包含两个静态内部类HashEntry和Segment。HashEntry用来封装映射表的 键/值对；Segment 用来充当数据划分和锁的角色，每个Segment对象守护整个散列映射表的若干个table。每个table是由若干个 HashEntry对象链接起来的链表。一个ConcurrentHashMap实例中包含由若干个Segment对象组成的数组。   a.HashEntry    清单1：HashEntry的定义 

1 2 3 4 5 6

static final class HashEntry {     final K key;     final int hash;     volatile AbsReference value;     final HashEntry next; }

      书本上同一目录和子目录下面可能包含许多个章节内容，同样的，在ConcurrentHashMap中同一个Segment中同一个HashEntry代表的位置上可能也有许多不同的内容，我们称之为数据碰撞，而ConcurrentHashMap采用“分离链接法”来处理“碰撞”，即把“碰撞”的 HashEntry 对象链接成一个链表，一个接一个的。     HashEntry的一个特点，除了value以外，其他的几个变量都是final的，这样做是为了防止链表结构被破坏，出现ConcurrentModification的情况，这种http://blog.csdn.net/guangcigeyun/article/details/8278346   c.Segment中get()方法     在定位到数据所在的segment，接下来我们看下segment中get()方法，这个方法是查找数据的主要方法。    清单5：Segment中get()方法 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

AbsReference get(String key, int hash, CacheLoader<String, AbsReference> loader, boolean isLoad) {     final StopWatch watch = new Slf4JStopWatch();     try {         if (count != 0) { // 先看看数量是否大于0             HashEntry e = getEntry(key, hash);             if (e != null) {                 // 这里只是一次无锁情况的快速尝试查询，如果未查询到，会在有锁情况下再查一次                 AbsReference value = getLiveValue(key, hash, now());                 watch.lap("cache.getLiveValue()");                 if (value != null) {                     recordAccess(e);                     return value;                 }             }         }         if (isLoad) {             // 对象为null或者对象已过期，则从在锁的情况下再查一次，还没有则从DB中加载数据             AbsReference ref = lockedGetOrLoad(key, hash, loader);             watch.lap("cache.lockedGetOrLoad()");             return ref;         }     } finally {         postReadCleanup();         watch.stop("cache.get()");     }     return null; }

      从上面代码不长，但我们可以看看4-15行，删除这几行代码对运行结果毫无影响，其存在的原因是为了提高数据查询效率，它的原理是在没有锁的情况下做一次数据查询尝试，如果查询到则直接返回，没查到则继续下面的流程；而第18行代码则是在有锁的情况下再查询数据，查不到则从DB加载数据返回。在大多数情况下，因为查询不需要对数据块加锁，所以效率有很大提升。   d.HashEntry定位    清单6：根据key和hash定位到具体的HashEntry

1 2 3 4 5 6 7 8

HashEntry getEntry(String key, int hash) {     // 首先拿到链头HashEntry，然后依次查找整个entry链     for (HashEntry e = getFirst(hash); e != null; e = e.next) {         if (e.hash == hash && key.equals(e.key)) {             return e;         }     }     return null; }

   清单5：链头HashEntry的定位 

1 2 3 4

HashEntry getFirst(int hash) {     AtomicReferenceArray tab = table;     return tab.get(hash & (tab.length() - 1)); }

      相较于Segment的复杂度，HashEntry则是正统的位运算定位方法，标准的 hash & [长度-1]。

总结

    至此我们可以了解缓存的整个数据查找的过程：     1.将key的hash进行二次hash     2.根据hash值定位到数据在哪一个segment中：segmentFor()     3.根据hash值定位到数据在table中的第一个HashEntry     4.根据HashEntry中的next属性，依次比对，直到返回结果       从上述过程中，我们可以理解缓存为什么这么快，因为它在查找过程中仅进行一次hash运算，2次位运算就定位到数据所在的数据块，而链式查找的效率也是比较高的，更关键的是绝大多数情况下，如果数据存在，缓存会首先进行查询尝试，以避免数据块加锁，所以缓存才能快速的查询到数据。 　　接下来我们会讲讲缓存的并发写入流程，敬请期待。   原创文章，请注明引用来源：CM4J 参考文章： Java多线程（三）之ConcurrentHashMap深入分析： http://blog.csdn.net/guangcigeyun/article/details/8278346