高速缓存实现

   各位大虾,本人实现了一个高速缓存,实现方式中依赖java的concurrent包ConcurrendHashMap,贴出代码希望各位能够讨论一下如下的addElement()方法不加锁,会不会出现线程问题(依照本人的理解应该不会,由于本人才疏学浅,还望不吝赐教,另外该方法的实现是参考<<java并发编程实践>>)。

public class Cache<K, V> {
	
	private final ConcurrentHashMap<K, FutureTask<V>> cache = 
								new ConcurrentHashMap<K, FutureTask<V>>();
	
	private final ReadWriteLock lock = new ReentrantReadWriteLock();
	private final Lock readLock = lock.readLock();
//	private final Lock writeLock = lock.writeLock();
	
	public V addElement(final K key, final V value) {
		FutureTask<V> f = cache.get(key);
		while (true) {
			if (null == f) {
				Callable<V> eval = new Callable<V>() {

					@Override
					public V call() throws Exception {
						//此处实现比较简单,但是如果创建一个V的对象需要比较消耗性能的话,
						//这种缓存实现就有明显的优势
						return value;
					}
					
				};
				FutureTask<V> future = new FutureTask<V>(eval);
				f = cache.putIfAbsent(key, future);
				if (null == f) {
					f = future;
					future.run();
				}
			}
			
			try {
				return f.get();
			} catch (Exception e) {
				e.printStackTrace();
			}
		} 
	}
	
	public V getElement(K key) {
		try {
			readLock.lock();
			return cache.get(key).get();
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			readLock.unlock();
		}
		return null;
	}
}

   在具体实现中getElement()方法使用了读锁从而支持并发读,在addElement()方法中没有加任何锁依靠FutureTask和实现逻辑来实现线程安全。如上实现优势: 当线程进入addElement方法后，首先判断对应key的Futuretask是否已经存在，如果不存在表明是第一次添加,然后利用Callable和Futuretask来创建一个value对象(如果创建value对象的代价非常昂贵的话,更能体现该实现的优势).假如在第一个线程正在创建value的过程中,addElement方法进入第二个线程,此时第二个线程会首先判断key对应的Futuretask是否已经存在，如不存在则利用Callable和Futuretask来创建一个value对象。试想此时的最好实现就是第二个线程判断对象是否存在或者是否正在创建，如果存在或正在创建那么最好的办法就是等待第一个线程创建完成后直接来分享胜利的果实即可，不需要再进行创建后再依靠concurrentHashMap的putIfAbsent方法来判断是否需要加入Map中，这种实现最明显的优势就是节约了创建一个复杂对象的开销，这一点也是该实现的精华所在.
以上是本人对这个方法的理解，还望各位多多拍砖。。。。。。。。

评论

27 楼 coolboy09 2014-11-25  

java并发编程实战上有类似的例子。我有一个疑惑，现在提出来和博主讨论：f = cache.putIfAbsent(key, future);这一操作确实是原子操作，假设：第一个线程在执行完这个操作后，被CPU调度暂停，此时第二个再执行时，发现第一个已经创建，于是第二个线程将直接返回第一个线程创建的这个FutureTask对象，这没问题。依据代码，如果此时第一个线程仍然没有获得执行余下代码的机会，也就是博主代码的第26-29行，此时，第二个线程直接执行到第33行（return f.get()），而不会执行26-29行，那这个最后的结果不就是null了吗？因为，26-29行没有执行，所以，future没有run。

26 楼 znlyj 2014-08-25  

我同样关注，怎么更新缓存？
另外，如果我不想将计算结果放到进程内，想放到redis，怎么操作？

25 楼 sunson468 2010-06-10  

soongbo 写道

sunson468 写道

这个是不是对象产生器～～～不是所谓的缓存吧

你那个判断什么的是不是写反了啊，怎么先循环再判断是否为空啊，而且add操作是可以并发的，但是你的key-value是一对一的啊，这样的等待就一点都不高速了啊～～

可以考虑修改一下，变成一种对象池，缺少了就补充这样还实用点，事实上我们有某个项目就打算采取这个滴

针对你提出的问题，解释如下:
1.while循环是考虑在Futuretask在创建value过程中可能出现异常导致无法获得对应的value，这里是来做轮询的，只有成功创建了value并返回，从而结束轮询。
2.这样实现addElement的有一个很明显的优势就是:当第二个线程判断key在Map存在，且对应的Futuretask已经存在，那么第二个线程只需要等待创建该key对应的Futuretask的线程返回value，这样如果创建一个对象的性能开销很大的话，这个高速缓存就更能体现出"高速"吧。

1，没错，但是如果一直不被创建的呢？如何保证add线程的个数，采取线程池吗？那么整个线程池如何管理，还是说建立不同的线程池，你这个应该是通用组件，那么通用组件是否应该考虑一下你对整个应用无论是性能还是消耗上都得达到一定标准呢。似乎用阻塞队列都比这个无限循环要好很多吧，当然，可能我误解你的本意了。

2，也就是说你每次只会保存一个缓存，也就是说当我需要获取多个返回的时候也只能一个个等待。是这个意思吗？所以我提出池的概念，当然可能我没理解你这个key，它是否就是类似于spring的beanname一样的一种存在，事实上很多时候我们开销大的原因在于我们需要创建很多很多的这样的对象，而且都是不同的引用，而这些对象紧接着又都会被销毁，这个只要过度作用的对象的创建消耗才不被我们允许。

24 楼 soongbo 2010-06-09  

sunson468 写道

这个是不是对象产生器～～～不是所谓的缓存吧

你那个判断什么的是不是写反了啊，怎么先循环再判断是否为空啊，而且add操作是可以并发的，但是你的key-value是一对一的啊，这样的等待就一点都不高速了啊～～

可以考虑修改一下，变成一种对象池，缺少了就补充这样还实用点，事实上我们有某个项目就打算采取这个滴

针对你提出的问题，解释如下:
1.while循环是考虑在Futuretask在创建value过程中可能出现异常导致无法获得对应的value，这里是来做轮询的，只有成功创建了value并返回，从而结束轮询。
2.这样实现addElement的有一个很明显的优势就是:当第二个线程判断key在Map存在，且对应的Futuretask已经存在，那么第二个线程只需要等待创建该key对应的Futuretask的线程返回value，这样如果创建一个对象的性能开销很大的话，这个高速缓存就更能体现出"高速"吧。

23 楼 sunson468 2010-06-09  

这个是不是对象产生器～～～不是所谓的缓存吧

你那个判断什么的是不是写反了啊，怎么先循环再判断是否为空啊，而且add操作是可以并发的，但是你的key-value是一对一的啊，这样的等待就一点都不高速了啊～～

可以考虑修改一下，变成一种对象池，缺少了就补充这样还实用点，事实上我们有某个项目就打算采取这个滴

22 楼 soongbo 2010-06-09  

beneo 写道

soongbo 写道

beneo 写道

soongbo 写道

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

你提出的这个问题我个人觉得应该不会出现，因为在put前利用了putIfAbent来保证该key对应的FutureTask是第一次put到Map，如果不是第一次此时只需要等待已经put的FutureTask执行获得value的结果，然后分享胜利果实即可.

的确putIfAbent能够保证只有唯一一个key，不过可惜的是你在调用putIfAbent前，有可能多个线程一起计算同一个key的value

你觉得这个的开销大还是锁的开销大

看来你还没有看明白putIfAbsent()方法之前的代码，那里没有计算value，而是在putIfAbent判断了对应Key的FutureTask不存在后，在又FutureTask去执行创建Value的工作，所以这里没有性能开销。

嗯，是凭映像说的。

其实简单的说，好几个线程new Callable<T> 这种代价可以接受的话，你这样写是没有问题的

引用

因为在利用FutureTask生成Value的过程中，有可能出现异常，所以这里需要while(true)来做轮询，知道对应key有一个对应的FutureTask放入Map中。

如果有异常你循环，那么下次循环还不是异常么？还不如检测出异常放个异常值来的好


还有我调用addElement(final K key, final V value)，返回的都是最初计算出来的结果，这个是你想要的么
，换句话说，你的缓存怎么去更新？

这里的实现是没有考虑缓存更新的问题，因为缓存的更新其实是和业务逻辑挂钩的，具体需要根据业务逻辑是定制缓存策略。

21 楼 beneo 2010-06-09  

soongbo 写道

beneo 写道

soongbo 写道

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

你提出的这个问题我个人觉得应该不会出现，因为在put前利用了putIfAbent来保证该key对应的FutureTask是第一次put到Map，如果不是第一次此时只需要等待已经put的FutureTask执行获得value的结果，然后分享胜利果实即可.

的确putIfAbent能够保证只有唯一一个key，不过可惜的是你在调用putIfAbent前，有可能多个线程一起计算同一个key的value

你觉得这个的开销大还是锁的开销大

看来你还没有看明白putIfAbsent()方法之前的代码，那里没有计算value，而是在putIfAbent判断了对应Key的FutureTask不存在后，在又FutureTask去执行创建Value的工作，所以这里没有性能开销。

嗯，是凭映像说的。

其实简单的说，好几个线程new Callable<T> 这种代价可以接受的话，你这样写是没有问题的

引用

因为在利用FutureTask生成Value的过程中，有可能出现异常，所以这里需要while(true)来做轮询，知道对应key有一个对应的FutureTask放入Map中。

如果有异常你循环，那么下次循环还不是异常么？还不如检测出异常放个异常值来的好


还有我调用addElement(final K key, final V value)，返回的都是最初计算出来的结果，这个是你想要的么
，换句话说，你的缓存怎么去更新？

20 楼 soongbo 2010-06-09  

beneo 写道

soongbo 写道

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

你提出的这个问题我个人觉得应该不会出现，因为在put前利用了putIfAbent来保证该key对应的FutureTask是第一次put到Map，如果不是第一次此时只需要等待已经put的FutureTask执行获得value的结果，然后分享胜利果实即可.

的确putIfAbent能够保证只有唯一一个key，不过可惜的是你在调用putIfAbent前，有可能多个线程一起计算同一个key的value

你觉得这个的开销大还是锁的开销大

看来你还没有看明白putIfAbsent()方法之前的代码，那里没有计算value，而是在putIfAbent判断了对应Key的FutureTask不存在后，在又FutureTask去执行创建Value的工作，所以这里没有性能开销。

19 楼 beneo 2010-06-09  

soongbo 写道

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

你提出的这个问题我个人觉得应该不会出现，因为在put前利用了putIfAbent来保证该key对应的FutureTask是第一次put到Map，如果不是第一次此时只需要等待已经put的FutureTask执行获得value的结果，然后分享胜利果实即可.

的确putIfAbent能够保证只有唯一一个key，不过可惜的是你在调用putIfAbent前，有可能多个线程一起计算同一个key的value

你觉得这个的开销大还是锁的开销大

18 楼 soongbo 2010-06-09  

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

你提出的这个问题我个人觉得应该不会出现，因为在put前利用了putIfAbent来保证该key对应的FutureTask是第一次put到Map，如果不是第一次此时只需要等待已经put的FutureTask执行获得value的结果，然后分享胜利果实即可.

17 楼 soongbo 2010-06-09  

hankesi2000 写道

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

同意kazy的观点，在多个线程同时进入到null里的时候，eval 和future 可能会被创建很多个。
另外又看了一下putIfAbsent方法，大概意思是

if (!map.containsKey(key)) 
      return map.put(key, value);
  else
       return map.get(key);

如果这样的话，楼主首先使用有锁的map将future放入，保证此时map的future唯一，如果返回值是null说明是该线程首次放入，然后future做生成真正value的操作，这样感觉应该是可以的。

不过这样的话，是否一次就可以搞定value的值，而不需要while(true)了？

因为在利用FutureTask生成Value的过程中，有可能出现异常，所以这里需要while(true)来做轮询，知道对应key有一个对应的FutureTask放入Map中。

16 楼 soongbo 2010-06-09  

archerfrank 写道

关键点是LZ的cache是不能修改的吧。一旦put进去，就不会改了，其他线程只能分享胜利成果了。
所以线程安全了。

当然这里没有考虑到cache的修改问题，在实际应用中cache的修改问题是和业务场景挂钩的，也就所说的缓存策略的问题。

15 楼 archerfrank 2010-06-09  

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

这个要顶。不知道LZ的需求会不会break这一条

14 楼 archerfrank 2010-06-09  

关键点是LZ的cache是不能修改的吧。一旦put进去，就不会改了，其他线程只能分享胜利成果了。
所以线程安全了。

13 楼 hankesi2000 2010-06-09  

kazy 写道

从另外的地方抄个例子过来，

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
    String x = map.get(name); 
    if (x == null) { 
        x = new String(); 
        map.put(name, x); 
    } 
    return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，
你还是有可能违反原子操作的规则。

同意kazy的观点，在多个线程同时进入到null里的时候，eval 和future 可能会被创建很多个。
另外又看了一下putIfAbsent方法，大概意思是

if (!map.containsKey(key)) 
      return map.put(key, value);
  else
       return map.get(key);

如果这样的话，楼主首先使用有锁的map将future放入，保证此时map的future唯一，如果返回值是null说明是该线程首次放入，然后future做生成真正value的操作，这样感觉应该是可以的。

不过这样的话，是否一次就可以搞定value的值，而不需要while(true)了？

12 楼 soongbo 2010-06-08  

wkoffee说:"你addElement的原子性是基于putIfAbsent是原子的，所以你还是用了concurrentHashMap内部的锁了，没看出什么特别有价值的地方".
说明如下:这里主要是想说明即便此时出现了多线程的情况，当第二个线程来请求获得对应key的value时,只要发现已经有第一个线程在创建对应value后,只需要等待第一个线程的结果就行了，这也就是为什么要使用Futuretask的目的，这样就可以很好的避免在创建比较消耗性能的value对象的性能损失.

11 楼 soongbo 2010-06-08  

tyzqqq 写道

getElement没必要加线程锁吧，它仅仅是取值

getElement()的确不需要锁！

10 楼 wkoffee 2010-06-08  

你addElement的原子性是基于putIfAbsent是原子的，所以你还是用了concurrentHashMap内部的锁了，没看出什么特别有价值的地方

9 楼 tyzqqq 2010-06-08  

getElement没必要加线程锁吧，它仅仅是取值

8 楼 soongbo 2010-06-08  

wantofly_gj 写道

缓存么,就是要复用.你这里就是要复用每个key对应的value值,而你在Map中使用FutureTask而不是直接存value,只是为了占位(避免两个线程同时检查到key不存在,然后同时创建两个value).呵呵.我看了半天才明白:)
问题1:读写再入锁是没用的,putIfAbsent 方法其实就已经实现了防止同时写入的可能了(第一个线程占位之后,第二个线程就不可能再写入了).
问题2: while(true)实在没看明白??
问题3:之前beneo 说的 addElement 这个方法接口上面，final V value 应该改成 Callable<V> callable吧? 你传入的value值转了一圈就被直接返回了,没用啊

关于你提出的问题，入下说明：
1：读写锁在此吃是应该取消,因为concurrentHashMap中已经是线程安全的了。
2：putIfAbent方法防止了同时写的问题！这里主要是想说明即便此时出现了多线程的情况，当第二个线程来请求获得对应key的value时,只要发现已经有第一个线程在创建对应value后只需要等待第一个线程的结构就行了，这也就是为什么要使用Futuretask的目的，这样就可以很好的避免在创建比较消耗性能的value对象的性能损失.
3：while(true)的目的是实现轮询，如果在Futuretak执行创建value失败时轮询做该操作，知道成功推出。
4：至于将addElement方法中的value改Callable的实现，这一点只是实现方式的问题吧。