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

这个code本质还是 rwlock.所有的写操作用了sychronized， 还是lock. 另外每次写都要copy, 其实更差。按照cliff的测试。其实32个processor以下。ConcurrentMap足够。只有在更大的情况下。基于CAS的lockfree的数据结构才更有效

我们是在就事论事 楼主给出的上下文就是rwlock

Copy On Write Hash Map
我们在工作的过程中，经常遇到如下的需求：
用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低，一般只在初始化、或重新装装载的时候写入。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。
...
在我们的Copy On Write Map中，我们只需要让新数据覆盖旧数据就可以了，因此不需要考虑版本控制的问题。这就大大简化了我们的实现。

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

读写模型

读写模型是一个稍微复杂一些的模型。
一份共享资源允许多个读者同时读取。但是只要有一个写者在写这份共享资源，任何其他的读者和写者都不能访问这份共享资源。
读写模型实现起来，不仅需要信号量机制，还需要额外的读者计数和写者计数。
public static final Object signal = new Object();
public static int readers = 0;
public static int writers = 0;

// 读者代码
… read() {

for(… ) { // 循环执行

synchronized(signal){
while( writers > 0 )
signal.wait(); // 如果有人在写，那么就放弃执行，进入待召队列

// 能够到达这里，说明没有人在写

readers ++ ; // 增加一个读者计数，表示本线程在读取
} // 这里出了synchronized范围,释放同步锁.以便其他线程读取.


// 进行一些读取操作

synchronized(signal){
readers --; // 读取完成，减少一个读者计数，表示本线程不在读取

signal.notifyAll(); // 通知待召队列里面的所有其他线程
}
}
}

// 写者代码
… write() {

for(… ) { // 循环执行

synchronized(signal){
while( writers > 0 || readers > 0)
signal.wait();// 如果有人在写或读，那么就放弃执行，进入待召队列

// 能够到达这里，说明没有人在写，也没有人在读

writers ++ ; // 增加一个写者计数，表示本线程在写

// 进行一些读取操作

writers --; // 读取完成，减少一个读者计数，表示本线程不在写

signal.notifyAll(); // 通知待召队列里面的所有其他线程
}
}
}

上述代码只是一段示意代码。实际应用中，人们通常抽取出来一个专门的读写同步锁。
interface ReadWriteLock {
… getReadLock();
… releaseReadLock();
… getWriteLock();
… releaseWriteLock();
}

具体的实现原理也是类似的信号量同步机制。
class RWLock {
… readers, writers;

… synchronized … getReadLock() { // 相当于synchronized(this)
…
while( writers > 0 )
this.wait(); // 这里我们把RWLock对象本身作为信号量
readers++;
}

…synchronized … releaseReadLock(){ //相当于synchronized(this)
readers--;
this.notifyAll(); // // 这里我们把RWLock对象本身作为信号量
}

…synchronized … getWriteLock(){// 相当于synchronized(this)
while( writers > 0 || readers > 0 )
this.wait(); // 这里我们把RWLock对象本身作为信号量

writers++;
}
…synchronized … releaseWriteLock(){// 相当于synchronized(this)
writers--;
this.notifyAll(); // // 这里我们把RWLock对象本身作为信号量
}
}

具体用法是
public static final RWLock lock = new RWLock();

… read() {
lock.getReadLock();
// 读取
lock.releaseReadLock();
}

… write() {
lock.getWriteLock();
// 读取
lock.releaseWriteLock();
}

这种用法要求在执行一些处理之前，一定要执行某项特殊操作，处理之后一定也要执行某项特殊操作。这种人为的顺序性，无疑增加了代码的耦合度，降低了代码的独立性。很有可能会成为线程死锁和资源操作冲突的根源。
这点一直让我不安，可是没有找到方法避免。毕竟，死锁或者资源操作冲突，是线程的固有问题。
很巧的是，正在我惴惴不安的时候，我的一个朋友提供了一个信息。Sun公司根据JCR，决定在jdk1.5中引入关于concurrency（并发）的部分。
以下这个网址是concurrency部分的util.concurrent一个实现。非常好的信息。对于处理多线程并发问题，很有帮助。
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html
里面提供了一个ReadWriteLock类，标准用法如下。
Standard usage of ReadWriteLock:
class X {
ReadWriteLock rw;
// ...
public void read() throws InterruptedException {
rw.readLock().acquire();
try {
// ... do the read
}
finally {
rw.readlock().release()
}
}
public void write() throws InterruptedException {
rw.writeLock().acquire();
try {
// ... do the write
}
finally {
rw.writelock().release()
}
}
}
我们可以看到，ReadWriteLock同样要求调用的顺序——aquire()和release()。我对自己的例子增强了一点信心。
我又查看了WriterPreferenceReadWriteLock类，看到里面成对的方法，startRead()，endRead()；startWrite()，endWrite()。我的心情完全放松了下来。我的思路虽然粗糙，但大体的方向是正确的。

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实现读写同步。代码看起来应该像这个样子。

Java代码
// 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. :-)


但看了CurrentHashMap 的代码，发现不是这样。其中的实现比较复杂，把Table分成段进行分别管理。那个内部类 Segment extends ReentrantLock。
里面的 readValueUnderLock 方法里面用了lock。
Java代码
/**
* 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();
}
}

我们再来看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。还是要获得系统锁。

写是用了同步，但这个结果跟CAS有什么不一样吗？如果有原子的CAS一样可以用。

这种实现方式面向的是读比写多得多，比如1000：1以上，但数据量又不是很大，可能数百条以内。它对读操作的优化是显而易见的。

CAS就是AtomicInteger之类的了，使用了CPU的交换指令，理论上比锁快，但是在高并发的环境一样会下降