Fast Read Map

一．引言

我們在工作的過程中，經(jīng)常遇到如下的需求：

用一個Map存放常用的Object，這個Map的并發(fā)讀取的頻率很高，而寫入的頻率很低（一般只在初始化、或重新裝裝載的時候?qū)懭耄?。讀寫沖突雖然很少發(fā)生，不過一旦發(fā)生，Map的內(nèi)部結(jié)構(gòu)就可能亂掉，所以，我們不得不為Map加上同步鎖。

本文介紹一種間接明朗的“快讀Map”的實現(xiàn)思路和代碼，既能避免讀寫沖突，又能夠達到最高的讀取速度。

該“快讀Map”的最終代碼的形成有賴于網(wǎng)友octfor的探討和改進。整個討論過程見

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

下面詳細介紹“快讀Map”的歷史背景、形成思路、代碼實現(xiàn)。

二、Concurrent Map

Concurrent Map的最簡單的實現(xiàn)方法是直接用java.util.HashTable類，或者用Collections.synchronizedMap() 修飾某個Map。

這樣獲得的Map能夠保證讀寫同步，但是，并發(fā)讀的時候，也必須同步，串行讀取，效率很低。這個思路顯然不適合。

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。

我設(shè)想了一下，CurrentHashMap應(yīng)該是采用ReadWriteLock實現(xiàn)讀寫同步。代碼看起來應(yīng)該像這個樣子。

[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 的代碼，發(fā)現(xiàn)不是這樣。其中的實現(xiàn)比較復(fù)雜，把Table分成段進行分別管理。那個內(nèi)部類 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。還是要獲得系統(tǒng)鎖。

三、快讀Map

Read Lock也是lock，也有overhead。能不能找到一種方法，保證讀的時候，完全不用鎖，而寫的時候，也能保證數(shù)據(jù)結(jié)構(gòu)和內(nèi)容的正確？

基本思路就是讓讀和寫操作分別在不同的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一樣快。

寫的時候，先把內(nèi)部Map復(fù)制一份，然后在這個備份上進行修改，改完之后，再讓內(nèi)部Map等于這個修改后的Map。這個方法是同步保護的，避免了同時寫操作。可見，寫的時候，開銷相當大。盡量使用 putAll() method。