一个缓存设计的修改实例

概述

现有的服务器,或多或少的都使用到了缓存,利用缓存可以很好的提高系统的吞吐量,给服务器减小压力。但缓存的设计是一个很关键的问题,一个设计很好的缓存能够极大的提高系统的性能,相反,设计的不合理的话不仅不能提高性能,更糟的是可能会发生很多莫名其秒的错误。这里我们将设计一个高效缓存,用于改进一个耗时的操作。

一个操作耗时的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Computable<A,V> {
V compute(A arg) throws InterruptedException;
}

public class ExpensiveFunction implements Computable<String, BigInteger>{

@Override
public BigInteger compute(String arg) throws InterruptedException {
// TODO 这中间是一些很耗时的操作,我暂时用线程Thread.sleep代替
// 2秒计算时间
Thread.sleep(2000);
return new BigInteger(arg);
}

}

一个简单的缓存实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	public class HighEffectiveCache1<A,V> implements Computable<A, V> {

private final Map<A,V> cache = new HashMap<A,V>();
private final Computable<A,V> c;

public HighEffectiveCache1(Computable<A, V> c){
this.c = c;
}

@Override
public synchronized V compute(A arg) throws InterruptedException {
// TODO Auto-generated method stub
V result = cache.get(arg);
if(result == null){
result = c.compute(arg);
cache.put(arg, result);
}
return result;
}
}

这是缓存的一种简单实现,因为HashMap本身并不是线程安全的,所以对compute方法进行了加锁,但这种方法有一个很突出的缺点,就是慢。当一个线程在执行时,另外一个线程就得被阻塞很长时间,对于大并发量的访问来说,这显然不是我们想看到的。

利用ConcurrentHashMap进行改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HighEffectiveCache2<A,V> implements Computable<A, V> {

private final Map<A,V> cache = new ConcurrentHashMap<A,V>();
private final Computable<A,V> c;

public HighEffectiveCache2(Computable<A, V> c){
this.c = c;
}

@Override
public V compute(A arg) throws InterruptedException {
// TODO Auto-generated method stub
V result = cache.get(arg);
if(result == null){
result = c.compute(arg);
cache.put(arg, result);
}
return result;
}
}

ConcurrentHashMap是线程安全的,因此在访问底层的Map的时候,我们不需要进行同步,从而避免了在对compute方法访问时带来的串行性。但这在compute时也会有一个问题——导致计算相同的值。比如说某个线程开始执行compute,此时另一线程对result进行判断也为null,那么该线程会再次执行compute,所以这也并不是一个很好的缓存实现。

利用FutureTask改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class HighEffectiveCache3<A,V> implements Computable<A, V> {

private final Map<A,Future<V>> cache = new ConcurrentHashMap<A,Future<V>>();
private final Computable<A,V> c;

public HighEffectiveCache3(Computable<A, V> c){
this.c = c;
}

@Override
public V compute(final A arg) throws InterruptedException {
// TODO Auto-generated method stub
Future<V> f = cache.get(arg);
if(f == null){
Callable<V> eval = new Callable<V>(){
public V call() throws InterruptedException{
return c.compute(arg);
}
};

FutureTask<V> ft = new FutureTask<V>(eval);
f = ft;
cache.put(arg, ft);
ft.run();
}
try {
return f.get();
} catch (ExecutionException e) {
e.printStackTrace();
return null;
}
}
}

利用ConcurrentHash+FutureTask几乎完美的实现了缓存的功能,这里用Future替换了原来的V之后,HighEffectiveCache3会首先检查某个对应的计算是否已经开始(这里与上面不同的是,上面判断的是否完成),如果没有,那么就会创建一个FutureTask,并注册到Map中,然后启动计算。如果已经启动,那么等待现有的计算结果。但这里仍然会有一点小缺陷——仍然存在两个线程计算出相同值这样的一种情况,原因在于if( f == null )这一部分的代码仍然是非原子的,因此两个线程仍有可能在同一时间内调用compute来计算相同的值。不过个问题很好解决,利用ConcurrentHashMap本身就可以搞定。

最后的一点改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class HighEffectiveCache4<A,V> implements Computable<A, V> {

private final ConcurrentMap<A,Future<V>> cache = new ConcurrentHashMap<A,Future<V>>();
private final Computable<A,V> c;

public HighEffectiveCache4(Computable<A, V> c){
this.c = c;
}

@Override
public V compute(final A arg) throws InterruptedException {
// TODO Auto-generated method stub
Future<V> f = cache.get(arg);
if(f == null){
Callable<V> eval = new Callable<V>(){
public V call() throws InterruptedException{
return c.compute(arg);
}
};

FutureTask<V> ft = new FutureTask<V>(eval);
f = ft;
cache.putIfAbsent(arg, ft);
ft.run();
}
try {
return f.get(5000,TimeUnit.MILLISECONDS);
}catch (CancellationException e){
f.cancel(true);
cache.remove(arg,f);//当被取消时,把原来的值移除,以免造成污染
}catch (ExecutionException e) {
e.printStackTrace();
} catch (TimeoutException e) {
System.out.println("执行超时");
f.cancel(true);
cache.remove(arg,f);
}
return null;
}
}

到这里缓存的设计已经基本完成。
源码请参照我的github:

https://github.com/PassWarer/JavaConcurrency

Leo wechat
欢迎订阅公众号,建设中!