Copy On Write Hash Map (线程同步相关)

本文是继前两篇文章之后的有一篇线程数据结构相关文章.

线程同步
http://www.javaeye.com/topic/164905

线程同步模型, 生产者/消费者, 读写同步,线程池,concurrent map
http://www.javaeye.com/topic/174591


我以前写过这个Fast Read Map 数据结构的文章.
但是那个时候, 理解得并不是那么透彻, 这里重新整理再发一遍.

-------------------------

Copy On Write Hash Map
我们在工作的过程中，经常遇到如下的需求：
用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低，一般只在初始化、或重新装装载的时候写入。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。
我们可以采用Copy On Write的机制，来加强Map的读取速度。
Copy On Write是这样一种机制。当我们读取共享数据的时候，直接读取，不需要同步。当我们修改数据的时候，我们就把当前数据Copy一份副本，然后在这个副本上进行修改，完成之后，再用修改后的副本，替换掉原来的数据。这种方法就叫做Copy On Write。
Oracle等关系数据库的数据修改就采用Copy On Write的模式。Copy On Write模式对并发读取的支持很好，但是在并发修改的时候，会有版本冲突的问题。可能有多个线程同时修改同一份数据，那么就同时存在多个修改副本，这多个修改副本可能会相互覆盖，导致修改丢失。因此，Oracle等数据库通常会引入版本检查机制。即增加一个版本号字段，来检测是否存在并发修改。相似的版本控制机制存在于CVS、SVN等版本控制工具中。
在我们的Copy On Write Map中，我们只需要让新数据覆盖旧数据就可以了，因此不需要考虑版本控制的问题。这就大大简化了我们的实现。
基本思路就是让读和写操作分别在不同的Map上进行，每次写完之后，再把两个Map同步。代码如下：

/*
 * Copy On Write Map
 * 
 * Write is expensive.
 * Read is fast as pure HashMap.
 *
 * Note: extra info is removed for free use
 */
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;
	}
}

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

以前有看到这种说法，不过不明白内部结构乱掉是什么意思？比方说我的HashMap里面有一个"key" => "value"，然后用这个key写入新值("new value")时候，如果发生读写冲突，那么我再用相同key去取的时候会得到一个既不是"value"也不是"new value"的值？

没有仔细研究过 Hash Map的实现代码.
我想象一下,Hash Map 的内部存储结构应该是一个数组(or Tree, or Heap?).
每次 Remove/Put value 的时候, 内部结构都会重新组合.

如果正在遍历 Key 或者 Value 的时候, 内部结构发生了变化, Iterator(or Array Index?) 可能会指到空处,或者错处.这就产生了一个错误的 Iterator 结构.
getValue() 产生错误结构的可能性不大, 可能会获取错误的值.

Hash Map 本身的内部结构乱掉, 应该是两个线程同时 Remove / Put value 的时候, 才可能发生的情况.
比如, 一个线程刚把元素个数加了1, 另一个线程可能刚删除了几个元素. 元素计数和元素存储结构就对应不起来了.

上述臆测, 是简化成数组结构来猜想的.
真实情况如何, 还需要研究 Hash Map 的具体实现代码.

hashmap内部是散列表，需要制定大小，达到最大数量后，会对整张表进行 rehash。

concurrent hashmap是dynamic hash，不需要指定大小，会动态进行扩容。

COW本身不是这个意思吧，它指的是一种高效的内存分配机制，当数据没有修改时，不需要拷贝，这样可以节省内存并提高效率，真正修改数据时才拷贝。COW没有你这里说的“替换掉原来的数据”这个操作。

你这里描述的是另一种技术，名称我就不知道了，应该归类在lock-free吧，它和COW也没什么关系。COW只是你这里用到的实现技术。

真正修改数据时才拷贝...
修改的是原来数据, 还是拷贝数据?
如果修改的是拷贝数据,修改后的拷贝数据, 如何合并到原来那份数据?

我确实只是借用 Copy On Write 作为这种实现方式的代指. 具体的 COW 含义不是很了解.
Copy On Write 也可以算是一种 Design Pattern.

------------------
http://www.sansky.net/article/2007-05-13-snapshot-theory.html

目前有两大类存储快照，一种叫做即写即拷（copy-on-write）快照，另一种叫做分割镜像快照。

即写即拷快照可以在每次输入新数据或已有数据被更新时生成对存储数据改动的快照。这样做可以在发生硬盘写错误、文件损坏或程序故障时迅速地恢复数据。但是，如果需要对网络或存储媒介上的所有数据进行完全的存档或恢复时，所有以前的快照都必须可供使用。

即写即拷快照是表现数据外观特征的“照片”。这种方式通常也被称为“元数据”拷贝，即所有的数据并没有被真正拷贝到另一个位置，只是指示数据实际所处位置的指针被拷贝。在使用这项技术的情况下，当已经有了快照时，如果有人试图改写原始的LUN上的数据，快照软件将首先将原始的数据块拷贝到一个新位置（专用于复制操作的存储资源池），然后再进行写操作。以后当你引用原始数据时，快照软件将指针映射到新位置，或者当你引用快照时将指针映射到老位置。

------------------

从这里看, 好象是修改原本, 副本作为读取源.
我的实现是, 修改副本, 原本作为读取源.

网络问题，白打了半天，再来一遍。。

一般修改的都是拷贝的数据，原数据可能正在使用中。COW本身不考虑合并回去的问题，你这里的做法实际上是Lock-Free手法，假定前提是写操作比读要少的多，否则这样效率反而低。一些纯Lock-Free实现中，写操作不使用写锁，而是循环执行一个无锁的CAS(Compare And Swap)原子操作。

附：
COW在C++标准库字符串中有使用：

std::string a = "abc";
std::string b = a;
a[0] = 'd';

这个例子中，前两行执行完时a和b共享字符串，并且设置引用用计数为2。第三行执行时，字符串被复制并修改，原有字符串引用计数减为1。
（注：这种实现方式很多时候并不高效，在没有gc的情况下必须使用引用计数，需要线程互斥，效率影响较大，有些时候反而不如拷贝高效。）

COW在linux进程clone时也用到，进程复制如果拷贝内存则拷贝内容过多，内存占用较大，效率也非常低，COW非常有效。

JDK1.5里的ConcurrentHashMap应该就可以完全实现你的功能了。
不过读了一下你的代码，还是有收获，了解一下原理也不错。
顺便看了看JDK的ConcurrentHashMap的源码，它是用ReentrantLock的读写锁来实现的。

JDK本来就有copy on write array list

ConcurrentHashMap不是copy on write
它用了多个锁（默认是16个）

找了一下，有种说法是WRRM (“Write Rarely Read Many”)数据结构。