某些并发环境下Double-check模型的改进

简单场景：
        多线程环境，每个线程携带惟一的key去组装数据，相同的key会有相同的数据结果。为了提高响应速度，在线程访问的入口处设置缓存。线程根据key先从缓存中取数据，如果缓存中没有，线程就去做具体的逻辑处理。

        模型如下图：假定每个线程的key如A, B等，同时有多个携带同一key的线程进来。



        最基本的处理方式如此：

private static Map<String, Object> cache 
                      = new ConcurrentHashMap<String, Object>();
		
                //Entry
		public Object run(String key) {
			Object result = cache.get(key);
			if (result == null) {
				result = doHardWork(key);
				cache.put(key, result);
			}
			
			return result;
		}
		
		private Object doHardWork(String key) {
			Object result = null;
			//Concrete work
			return result; 
		}

        它的缺点很明显，同时会有多个相同key的线程在做事，资源浪费严重。

        先看段使用Double-check模式来完成相同功能的代码：

private static Map<String, Object> cache 
							= new ConcurrentHashMap<String, Object>();
		
		public Object run(String key) {
			Object result = cache.get(key);//First checking
			if (result == null) {
				synchronized (cache) {
					result = cache.get(key);//Second checking
					if (result == null) {
						result = doHardWork(key);
						cache.put(key, result);
					}
				}
			}
			
			return result;
		}
		
		private Object doHardWork(String key) {
			Object result = null;
			
			//Concrete work
			
			return result; 
		}

        假定某个线程T1的参数是A，如果它能从Cache中取到之前A的执行结果，就立马返回。否则在同步块外等待，期望此时在同步块中有另外一个参数也是A的线程T2正在运行，然后将运行结果放入缓存中，在T2执行完成退出同步块后，T1可以从Cache读取T2的执行结果，退出请求。Double-check模型有两次对Cache内容的check，一次在同步块外，一次在同步块里面。它的执行流程如图：


        系统初始时，假定有30个参数，每个参数有10个请求线程，那么同时会有300个线程从Cache中读数据，在没有读到任何数据时，只会有一个线程进入同步块，其它299个线程在外面等着。Double-check的好处在于，每个参数第一个进入同步块的线程才会去执行正式逻辑，其它拥有同样参数的线程只要从Cache中取数据即可，效率很高。如果参数A的某个线程之前执行过，其它参数A的线程在进入同步块后，能从Cache中取到数据，立马退出同步块。但同时它的缺点就是因为有同步块的存在，每个参数的第一个线程不能并行进入具体逻辑执行过程，得一个一个的来。如此30个参数，每个参数的第一个线程得依次串行进入具体逻辑。

        对于这样的应用场景，最好的流程是：相同参数的线程只有一个进入具体逻辑，其它线程等待这个参数的执行结果，在得到结果后，直接返回；不同参数的线程在具体逻辑阶段可以并发执行。期望的执行流程如下图：



        这篇帖子的目的是改进Double-check模型的这种缺点，但不是修改Double-check来满足需求。实现可以很简单，一是多个线程的数据共享，二是对于同样参数多个线程的通知。具体模型如下图：


        从代码来看：

   /**
	 * 用来标识当前参数有线程正在做具体逻辑
	 */
	public static Object lock = new Object();
   /**
	 * 假定参数为'A',系统初始时检查lockMap中‘A’的value是否为null，如果为null，那当前线程就得做具体逻辑，把'A'的value设置为固定的lock,其它线程看到有这个lock就什么事也不做，然后suspend。当有返回数据时，将value由lock替换为正式返回数据，以在多个线程间共享
	 */
private Map<String, Object> lockMap 
                         = new ConcurrentHashMap<String, Object>();
	
   /**
	 * 所有suspend的线程都要在这里注册，以便随后得到通知
	 */
	private Map<String, List<Thread>> caller = new ConcurrentHashMap<String, List<Thread>>();

	

        它的方法有:

/*
*返回值是lock时，做具体逻辑，返回值不为lock时，是真正的返回数据，线程得到这个数据，直接返回
*/
public Object runOrWait(String key);

/*
*做具体逻辑的那个线程在做完事后，需要把result写入共享空间，让其它线程看到。然后通知所有注册这个参数的线程知道
*/
public void releaseLock(String key, Object result)

        具体程序见附件，里面有一个测试类，用来模拟测试Case。然后列举了以上出现的几种cache Demo。这个程序只是用来验证这个处理策略，对于细节问题，值得商榷，欢迎提出意见，十分感谢！

评论

4 楼 langyu 2010-11-02  

tg008007x3 写道

将cache中的key构造称谓一个枚举集合，然后将下面的同步块中的参数
synchronized (cache) {  
                    result = cache.get(key);//Second checking  
                    if (result == null) {  
                        result = doHardWork(key);  
                        cache.put(key, result);  
                    }  
                }
cache改成相关的参数枚举参数，这样就能按照不同的参数key进行同步控制，从而使不同的key在第一次访问中也能够坐到异步控制。对同步的控制只与自己的key相关即可。
不知道这样做有没有错误，呵呵，随便想的。

呵呵，我这个砖头没白扔呀，果然砸出玉来。如果有枚举来控制不同参数的话，是可以实现我的要求：对相同参数，只有一个线程做具体逻辑；不同线程执行具体逻辑的线程可以并发。修改了下代码，看看是不是类似：

public static enum CacheKey {
		A, B, C, D
}

public static class EnumDemo extends Thread {
		private static Map<CacheKey, Object> cache 
					= new ConcurrentHashMap<CacheKey, Object>();
		
		public Object run(String key) {
			CacheKey cKey = CacheKey.valueOf(key);
			Object result = cache.get(cKey);//First checking
			if (result == null) {
				synchronized (cKey) {
					result = cache.get(cKey);//Second checking
					if (result == null) {
						result = doHardWork(key);
						cache.put(cKey, result);
					} 
				}
			}
			return result;
		}
		
		public void run() {
			run(this.key);
		}
	}
	
	

但这种方式存在的问题，如果前面请求的参数是后端不可预料的，那么怎么做?

顺着你的思路，我想到一种更好的方法: 既然要为相同的key加锁，那么相同的key的相同点在哪？string.intern()方法可以取出相同key的那个字符常量，做为加锁的条件：

public Object run(String key) {
			String cKey = key.intern();//literal key
			Object result = cache.get(cKey);//First checking
			if (result == null) {
				synchronized (cKey) {
					result = cache.get(cKey);//Second checking
					if (result == null) {
						result = doHardWork(key);
						cache.put(cKey, result);
					} 
				}
			}
			return result;
		}

3 楼 tg008007x3 2010-11-02  

将cache中的key构造称谓一个枚举集合，然后将下面的同步块中的参数
synchronized (cache) {  
                    result = cache.get(key);//Second checking  
                    if (result == null) {  
                        result = doHardWork(key);  
                        cache.put(key, result);  
                    }  
                }
cache改成相关的参数枚举参数，这样就能按照不同的参数key进行同步控制，从而使不同的key在第一次访问中也能够坐到异步控制。对同步的控制只与自己的key相关即可。
不知道这样做有没有错误，呵呵，随便想的。

2 楼 langyu 2010-11-01  

liugm1 写道

调用线程的suspend()和resume()不太安全
还有在EntityLock类中的runOrWait()方法，有对lockMap赋值
if (obj == null) lockMap.put(key, lock);
可能查询同一个key如'A'有多个线程执行到了这个地方，重复设置了lock,做了同样的hardWork是否又要双重检查，又回到了问题的原点。因为不排除put()方法还没执行完就跳到了下一个线程来获取值。
不知道提的是不是个问题，望楼主解答，谢谢！

首先感谢你提出的问题。
1. suspend()和resume()被认为不安全有特定的条件，在这段程序里不符合，暂时没有会出现死锁的机会。但可以对程序修改，以获得更高的安全性。

2. 会出现你所说的多个线程都可能去做具体逻辑。对于同一个参数，每个线程的执行结果是一致的，就是它们并行运行，也不会对执行结果有什么影响。这段程序的主要目的是想对于不同的参数至少并发运行一个线程。刚才修改了releaseLock()中的一行代码，对于每一个通知过的Thread，remove它，避免重复resume。

References:为什么Thread类中有这么多的Deprecated方法？

1 楼 liugm1 2010-11-01  

调用线程的suspend()和resume()不太安全
还有在EntityLock类中的runOrWait()方法，有对lockMap赋值
if (obj == null) lockMap.put(key, lock);
可能查询同一个key如'A'有多个线程执行到了这个地方，重复设置了lock,做了同样的hardWork是否又要双重检查，又回到了问题的原点。因为不排除put()方法还没执行完就跳到了下一个线程来获取值。
不知道提的是不是个问题，望楼主解答，谢谢！