Fast Read Map

Fast Read Map

一．引言

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

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

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

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

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

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

二、Concurrent Map

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

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

 

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

http://gee.cs./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./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。