2008-03-21
Copy On Write Hash Map (线程同步相关)
关键字: 线程 copy on write
本文是继前两篇文章之后的有一篇线程数据结构相关文章.
线程同步
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同步。代码如下：
这个Map读取的时候，和普通的HashMap一样快。
写的时候，先把内部Map复制一份，然后在这个备份上进行修改，改完之后，再让内部Map等于这个修改后的Map。这个方法是同步保护的，避免了同时写操作。可见，写的时候，开销相当大。尽量使用 putAll() method。
线程同步
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。
评论
corvallis
2008-04-26
再来挖一下坟。这个实现还可以有进一步的提高：那就是进一步提高写的效率。对于所有的有 ｌｏｃｋ 的 ｈａｓｈｔａｂｌｅ．一种基本的思路是ｐａｒｔｉｔｉｏｎ ｌｏｃｋ。也就是说可以把这一个ｈａｓｈｔａｂｌｅ分成若干个子ｔａｂｌｅ。 而同步（复制）操作仅发生在每一个子ｔａｂｌｅ上。这样可以减少每次ａｌｌｏｃａｔｉｏｎ的时间。对于 ｃａｃｈｅ 的 locality也较好。
这里要解决的一个问题是如何保证ｈａｓｈ ｋｅｙ 的ｕｎｉｆｏｒｍ ｄｉｓｔｒｉｂｕｔｉｏｎ．一种比较ｎａｉｖｅ的办法是， 基于ｊａｖａ 的ｈａｓｈｔａｂｌｅ 的大小总是２的幂。可以选择子ｔａｂｌｅ的数量为一个质数 比如3,5,7，11 ..,. 对于每个ｏｂｊｅｃｔ， 用key % size 来决定放入哪一个子ｔａｂｌｅ
这里要解决的一个问题是如何保证ｈａｓｈ ｋｅｙ 的ｕｎｉｆｏｒｍ ｄｉｓｔｒｉｂｕｔｉｏｎ．一种比较ｎａｉｖｅ的办法是， 基于ｊａｖａ 的ｈａｓｈｔａｂｌｅ 的大小总是２的幂。可以选择子ｔａｂｌｅ的数量为一个质数 比如3,5,7，11 ..,. 对于每个ｏｂｊｅｃｔ， 用key % size 来决定放入哪一个子ｔａｂｌｅ
liangwj72
2008-04-10
zgd 写道
CAS就是AtomicInteger之类的了，使用了CPU的交换指令，理论上比锁快，但是在高并发的环境一样会下降
CAS非常非常的快，比锁不是快一点半点。毕竟这是cpu原语级别的指令,jdk1.5中，这部分是native方式实现的，想模拟出让它性能大幅度下降的高并发环境很难。
标准的HashMap读的时候不会改动内部数据，楼主提出的问题似乎用ReentrantReadWriteLock就可以完美解决。
zgd
2008-03-26
copy on write array list
ConcurrentHashMap
ReentrantLock
ReentrantReadWriteLock
CAS
我都有在用，JDK内置
一直都想写一些关于它们的文章，不过始终太松散，而且我是知道原理然后直接用API而已
我随便说一些
楼主的copy on write模式是可取的，JDK很早就引入copy on write array list来处理Listener部分，在写入非常非常少的情况下，copy on write其实是很好的。至于楼主的实现好不好就不知道了
ConcurrentHashMap用了多个锁来处理，里面有一个一个的bucket来隔离锁，默认就是16个bucket&锁。但是它也有缺点，就是不能保证数据绝对准确，例如他的size就是不准确的。但是它肯定是线程安全的
ReentrantLock是可以代替synchronized的东西，除了写起来比synchronized难稍稍。默认是non-fair模式，比synchronized快很多，如果改成fair就会下降到跟synchronized差不多
ReadWriteLock很简单，read不互斥，write互斥
CAS就是AtomicInteger之类的了，使用了CPU的交换指令，理论上比锁快，但是在高并发的环境一样会下降
你们还是看一下JDK源代码和JavaDoc好过了，你们的讨论本来就有答案的
ConcurrentHashMap
ReentrantLock
ReentrantReadWriteLock
CAS
我都有在用，JDK内置
一直都想写一些关于它们的文章，不过始终太松散，而且我是知道原理然后直接用API而已
我随便说一些
楼主的copy on write模式是可取的，JDK很早就引入copy on write array list来处理Listener部分，在写入非常非常少的情况下，copy on write其实是很好的。至于楼主的实现好不好就不知道了
ConcurrentHashMap用了多个锁来处理，里面有一个一个的bucket来隔离锁，默认就是16个bucket&锁。但是它也有缺点，就是不能保证数据绝对准确，例如他的size就是不准确的。但是它肯定是线程安全的
ReentrantLock是可以代替synchronized的东西，除了写起来比synchronized难稍稍。默认是non-fair模式，比synchronized快很多，如果改成fair就会下降到跟synchronized差不多
ReadWriteLock很简单，read不互斥，write互斥
CAS就是AtomicInteger之类的了，使用了CPU的交换指令，理论上比锁快，但是在高并发的环境一样会下降
你们还是看一下JDK源代码和JavaDoc好过了，你们的讨论本来就有答案的
corvallis
2008-03-26
嗯 没错。 忽略了这是个为写操作很少的前提
写是用了同步，但这个结果跟CAS有什么不一样吗？如果有原子的CAS一样可以用。
这种实现方式面向的是读比写多得多，比如1000：1以上，但数据量又不是很大，可能数百条以内。它对读操作的优化是显而易见的。
qiezi 写道
写是用了同步，但这个结果跟CAS有什么不一样吗？如果有原子的CAS一样可以用。
这种实现方式面向的是读比写多得多，比如1000：1以上，但数据量又不是很大，可能数百条以内。它对读操作的优化是显而易见的。
buaawhl
2008-03-26
关于concurrent map, 也是在这里.
线程同步模型, 生产者/消费者, 读写同步,线程池,concurrent map.
http://www.javaeye.com/topic/174591
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。还是要获得系统锁。
线程同步模型, 生产者/消费者, 读写同步,线程池,concurrent map.
http://www.javaeye.com/topic/174591
buaawhl 写道
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。还是要获得系统锁。
buaawhl
2008-03-26
关于读写锁, 是在这里.
线程同步模型, 生产者/消费者, 读写同步,线程池,concurrent map.
http://www.javaeye.com/topic/174591
读写模型
读写模型是一个稍微复杂一些的模型。
一份共享资源允许多个读者同时读取。但是只要有一个写者在写这份共享资源，任何其他的读者和写者都不能访问这份共享资源。
读写模型实现起来，不仅需要信号量机制，还需要额外的读者计数和写者计数。
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.
http://www.javaeye.com/topic/174591
引用
读写模型
读写模型是一个稍微复杂一些的模型。
一份共享资源允许多个读者同时读取。但是只要有一个写者在写这份共享资源，任何其他的读者和写者都不能访问这份共享资源。
读写模型实现起来，不仅需要信号量机制，还需要额外的读者计数和写者计数。
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()。我的心情完全放松了下来。我的思路虽然粗糙，但大体的方向是正确的。
buaawhl
2008-03-26
帖子原文中的相关内容
Copy On Write Hash Map
我们在工作的过程中，经常遇到如下的需求：
用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低，一般只在初始化、或重新装装载的时候写入。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。
...
在我们的Copy On Write Map中，我们只需要让新数据覆盖旧数据就可以了，因此不需要考虑版本控制的问题。这就大大简化了我们的实现。
找了一下，有种说法是WRRM (“Write Rarely Read Many”)数据结构。
看来,这个 WRRM 更加贴切.
COW 好像应用在很多场合 (存储结构,内存分配,等等), 很容易引起歧义.
Copy on Write 这个词比较酷.Write Rarely Read Many 就没有那么酷了.
----------------------
读写锁控制, 还是需要在读取之前, 有一个获取 读锁 的动作.
这里的情况, 是为了让 Map 的读取非常快, 尽量避免 overhead.
写的效率确实很低. 不过, 这里的 Map 主要是为了读. 写的情况很少.
buaawhl 写道
Copy On Write Hash Map
我们在工作的过程中，经常遇到如下的需求：
用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低，一般只在初始化、或重新装装载的时候写入。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。
...
在我们的Copy On Write Map中，我们只需要让新数据覆盖旧数据就可以了，因此不需要考虑版本控制的问题。这就大大简化了我们的实现。
qiezi 写道
找了一下，有种说法是WRRM (“Write Rarely Read Many”)数据结构。
看来,这个 WRRM 更加贴切.
COW 好像应用在很多场合 (存储结构,内存分配,等等), 很容易引起歧义.
Copy on Write 这个词比较酷.Write Rarely Read Many 就没有那么酷了.
----------------------
读写锁控制, 还是需要在读取之前, 有一个获取 读锁 的动作.
这里的情况, 是为了让 Map 的读取非常快, 尽量避免 overhead.
写的效率确实很低. 不过, 这里的 Map 主要是为了读. 写的情况很少.
qiezi
2008-03-26
seen 写道
我们是在就事论事 楼主给出的上下文就是rwlock
rwlock的r和w是互斥的，w和w也一样。
这里的方式不一样，r和w同时进行，虽然不是操作同一个数据，但在做到相同结果的同时，写尽量减少对读的影响比如线程等待。rwlock有个严重的问题是读很频繁时，写很难lock住，所以这里虽然提高了成本，但在高并发环境下反而可能更快。
qiezi
2008-03-26
corvallis 写道
这个code本质还是 rwlock.所有的写操作用了sychronized， 还是lock. 另外每次写都要copy, 其实更差。按照cliff的测试。其实32个processor以下。ConcurrentMap足够。只有在更大的情况下。基于CAS的lockfree的数据结构才更有效
写是用了同步，但这个结果跟CAS有什么不一样吗？如果有原子的CAS一样可以用。
这种实现方式面向的是读比写多得多，比如1000：1以上，但数据量又不是很大，可能数百条以内。它对读操作的优化是显而易见的。
seen
2008-03-26
qiezi 写道
seen 写道
楼主 你该去看看rwlock是怎么实现的 至少看看是怎么用的
你这么闭门造车牵强附会不会有什么进步的
你这么闭门造车牵强附会不会有什么进步的
根本不是一码事。。你应该了解一下rwlock以外的东西。。Lock-Free和Wait-Free的概念
我们是在就事论事 楼主给出的上下文就是rwlock
XXXfree是另外一种解决锁的问题，但不是楼主的焦点
很明显，楼主想自己搞个rwlock，于是我建议他看看大家认可的做法而已
CAS嘛 如果不是CPU支持 还不是一样难搞 只是转移了问题而已
corvallis
2008-03-26
这个code本质还是 rwlock.所有的写操作用了sychronized， 还是lock. 另外每次写都要copy, 其实更差。按照cliff的测试。其实32个processor以下。ConcurrentMap足够。只有在更大的情况下。基于CAS的lockfree的数据结构才更有效
根本不是一码事。。你应该了解一下rwlock以外的东西。。Lock-Free和Wait-Free的概念
qiezi 写道
seen 写道
楼主 你该去看看rwlock是怎么实现的 至少看看是怎么用的
你这么闭门造车牵强附会不会有什么进步的
你这么闭门造车牵强附会不会有什么进步的
根本不是一码事。。你应该了解一下rwlock以外的东西。。Lock-Free和Wait-Free的概念
corvallis
2008-03-26
强烈推荐以下部分。 AZUL 应该是世界上最强的Java系统。 他们的JVM和JDK完全为高并发设计：
A Non-Blocking HashTable
http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html
A Non-Blocking HashTable, Part 2
http://blogs.azulsystems.com/cliff/2007/04/a_nonblocking_h.html
Engineering a Hash Table
http://blogs.azulsystems.com/cliff/2007/06/engineering_a_h.html
A Non-Blocking HashTable
http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html
A Non-Blocking HashTable, Part 2
http://blogs.azulsystems.com/cliff/2007/04/a_nonblocking_h.html
Engineering a Hash Table
http://blogs.azulsystems.com/cliff/2007/06/engineering_a_h.html
qiezi
2008-03-26
seen 写道
楼主 你该去看看rwlock是怎么实现的 至少看看是怎么用的
你这么闭门造车牵强附会不会有什么进步的
你这么闭门造车牵强附会不会有什么进步的
根本不是一码事。。你应该了解一下rwlock以外的东西。。Lock-Free和Wait-Free的概念
seen
2008-03-25
楼主 你该去看看rwlock是怎么实现的 至少看看是怎么用的
你这么闭门造车牵强附会不会有什么进步的
你这么闭门造车牵强附会不会有什么进步的
diggywang
2008-03-25
jigsaw 写道
又看了一遍楼主的理论 窃以为是误导初学者的典型例子
呵呵，就如n楼上的看家所言，ConcurrentHashMap可以快速简单地解决楼主所想解决的问题。
jigsaw
2008-03-24
又看了一遍楼主的理论 窃以为是误导初学者的典型例子
tinywind
2008-03-24
put一次就要复制整张表，代价太大了。
jigsaw
2008-03-23
偶来说2句COW
在fork（你要说clone也一样）的时候，子进程所有的内存空间都不做实际的mapping（从物理地址mapping到虚拟地址），而是把父进程的（同时也是子进程的）整个内存空间，每个页面都标上COW的标志，然后mapping到子进程空间。
然后父子各干各的，直到有任何一方要写一个页面了，kernel不得不从物理地址申请一个页面，mapping之，复制其内容，给另外（还没做写操作的）一个进程用。同时，把COW bit给mask了。
这样做的唯一理由是节省资源，时间的和空间的。跟线程同步没有任何关系。
在fork（你要说clone也一样）的时候，子进程所有的内存空间都不做实际的mapping（从物理地址mapping到虚拟地址），而是把父进程的（同时也是子进程的）整个内存空间，每个页面都标上COW的标志，然后mapping到子进程空间。
然后父子各干各的，直到有任何一方要写一个页面了，kernel不得不从物理地址申请一个页面，mapping之，复制其内容，给另外（还没做写操作的）一个进程用。同时，把COW bit给mask了。
这样做的唯一理由是节省资源，时间的和空间的。跟线程同步没有任何关系。
buaawhl
2008-03-23
zgd 写道
JDK本来就有copy on write array list
ConcurrentHashMap不是copy on write
它用了多个锁（默认是16个）
ConcurrentHashMap不是copy on write
它用了多个锁（默认是16个）
以前我还不知道这些.
zgd 可否详细讲讲?
-----------------------
qiezi -- WRRM (“Write Rarely Read Many”)数据结构。
WRRM也是一种 Pattern 了.
我以前写成 Fast Read.
COW 和引用计数有一定关系.
我搜索COW的时候,看到类似的内容.不过没有深入研究.
qiezi
2008-03-23
找了一下，有种说法是WRRM (“Write Rarely Read Many”)数据结构。
发表评论
提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则
buaawhl
- 浏览: 585665 次
- 性别:
- 来自: china
- 详细资料
搜索本博客
最近加入圈子
最新评论
-
网上银行的安全操作设计探 ...
有道理，不知道建设银行的UKey有啥用？
-- by sjz209 -
网上银行的安全操作设计探 ...
有道理，不知道建设银行的UKey有啥用？
-- by sjz209 -
网上银行的安全操作设计探 ...
1、据了解，动态口令采用的就是楼主说的第2种机制，所以动态口令发生器会有一个容错 ...
-- by jxb8901 -
谁说搞技术的没有幽默感？
yyliuliang 写道部门老大宣布放一年长假，大伙欢呼雀跃，连作三个俯卧撑表 ...
-- by hongfei3 -
谁说搞技术的没有幽默感？
幸存者 写道为什么我觉得不好笑？是因为我没有幽默感么？ bingoo
-- by roger
评论排行榜