Fast Read Map

一．引言

我们在工作的过程中，经常遇到如下的需求：

用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低（一般只在初始化、或重新装装载的时候写入）。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。

本文介绍一种间接明朗的“快读Map”的实现思路和代码，既能避免读写冲突，又能够达到最高的读取速度。

该“快读Map”的最终代码的形成有赖于网友octfor的探讨和改进。整个讨论过程见

http://forum.javaeye.com/viewtopic.php?t=11315

下面详细介绍“快读Map”的历史背景、形成思路、代码实现。

二、Concurrent Map

Concurrent Map的最简单的实现方法是直接用java.util.HashTable类，或者用Collections.synchronizedMap() 修饰某个Map。

这样获得的Map能够保证读写同步，但是，并发读的时候，也必须同步，串行读取，效率很低。这个思路显然不适合。

Doug Lea提供了一个Concurrent工具包，

http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html

包括Lock, ReadWriteLock, CurrentHashMap, CurrentReaderHashMap等类。JDK1.5引入了这些类，作为java.util.concurrent Package。

我设想了一下，CurrentHashMap应该是采用ReadWriteLock实现读写同步。代码看起来应该像这个样子。

[code]

// my guess
class CocurrentHashMap
{
Private Map map = null;
final ReadWriteLock rwLock = new …. ;
final Lock readLock = rwLock.readLock();
final Lock writeLock = rwLock.writeLock();

// decorate the map as concurrent
public CocurrentHashMap(Map m){
map = m;
}

// all write method, like put, putAll, remove, clear
public void putAll(Map m){
writeLock.lock();
try{
map.putAll(m);
}finally{
writeLock.unlock();
}
}

// all read method. like get, containsKey, containsValue, entrySet()
public Object get(Object key){
readLock.lock();
try{
return map.get(key);
}finally{
readLock.unlock();
}
};

// as we can see, in such places it is convenient to use AOP here. :-)

[/code]

但看了CurrentHashMap 的代码，发现不是这样。其中的实现比较复杂，把Table分成段进行分别管理。那个内部类 Segment extends ReentrantLock。
里面的 readValueUnderLock 方法里面用了lock。

[code]

/**
* Read value field of an entry under lock. Called if value
* field ever appears to be null. This is possible only if a
* compiler happens to reorder a HashEntry initialization with
* its table assignment, which is legal under memory model
* but is not known to ever occur.
*/
V readValueUnderLock(HashEntry<K,V> e) {
lock();
try {
return e.value;
} finally {
unlock();
}
}

[/code]

我们再来看CurrentReaderHashMap， “A version of Hashtable that supports mostly-concurrent reading, but exclusive writing.”

http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/ConcurrentReaderHashMap.java

但是它的 read ( get, contains, size …) 方法里面用到了synchronized。还是要获得系统锁。

三、快读Map

Read Lock也是lock，也有overhead。能不能找到一种方法，保证读的时候，完全不用锁，而写的时候，也能保证数据结构和内容的正确？

基本思路就是让读和写操作分别在不同的Map上进行，每次写完之后，再把两个Map同步。代码如下：

[code]

/*

* Read Write Map

*

* Write is expensive.

* Read is fast as pure HashMap.

*

* Note: extra info is removed for free use

*/

package net.util;

import java.lang.Compiler;

import java.util.Collection;

import java.util.Map;

import java.util.Set;

import java.util.HashMap;

import java.util.Collections;

public class ReadWriteMap implements Map {

protected volatile Map mapToRead = getNewMap();

// you can override it as new TreeMap();

protected Map getNewMap(){

return new HashMap();

}

// copy mapToWrite to mapToRead

protected Map copy(){

Map newMap = getNewMap();

newMap.putAll(mapToRead);

return newMap;

}

// read methods

public int size() {

return mapToRead.size();

}

public boolean isEmpty() {

return mapToRead.isEmpty();

}

public boolean containsKey(Object key) {

return mapToRead.containsKey(key);

}

public boolean containsValue(Object value) {

return mapToRead.containsValue(value);

}

public Collection values() {

return mapToRead.values();

}

public Set entrySet() {

return mapToRead.entrySet();

}

public Set keySet() {

return mapToRead.keySet();

}

public Object get(Object key) {

return mapToRead.get(key);

}

// write methods

public synchronized void clear() {

mapToRead = getNewMap();

}

public synchronized Object remove(Object key) {

Map map = copy();

Object o = map.remove(key);

mapToRead = map;

return o;

}

public synchronized Object put(Object key, Object value) {

Map map = copy();

Object o = map.put(key, value);

mapToRead = map;

return o;

}

public synchronized void putAll(Map t) {

Map map = copy();

map.putAll(t);

mapToRead = map;

}

}

[/code]

这个Map读取的时候，和普通的HashMap一样快。

写的时候，先把内部Map复制一份，然后在这个备份上进行修改，改完之后，再让内部Map等于这个修改后的Map。这个方法是同步保护的，避免了同时写操作。可见，写的时候，开销相当大。尽量使用 putAll() method。