设计高效的线程安全的缓存--JCIP5.6读书笔记

[本文是我对Java Concurrency In Practice 5.6的归纳和总结. ?转载请注明作者和出处, ?如有谬误, 欢迎在评论中指正. ]?

几乎每一个应用都会使用到缓存, 但是设计高效的线程安全的缓存并不简单. 如:

public interface Computable<A, V> {     V compute(A arg) throws InterruptedException; } public class ExpensiveFunction         implements Computable<String, BigInteger> {     // 模拟一个耗时操作    public BigInteger compute(String arg) { // ...        return new BigInteger(arg);     } } public class Memorizer1<A, V> implements Computable<A, V> {     private final Map<A, V> cache = new HashMap<A, V>();     private final Computable<A, V> c;     public Memorizer1(Computable<A, V> c) {         this.c = c;     }     // 使用synchronized同步整个方法解决线程安全    public synchronized V compute(A arg) throws InterruptedException {         V result = cache.get(arg);         if (result == null) {             result = c.compute(arg);             cache.put(arg, result);         }         return result;     } }

Memorizer1使用HashMap缓存计算结果. 如果能在缓存中取出参数对应的结果, 就直接返回缓存的数据, 避免了重复进行代价昂贵的计算. 由于HashMap不是线程安全的, Memorizer1同步整个compute方法, 避免重复计算的同时, 牺牲了并发执行compute方法的机会, 此种设计甚至可能导致性能比没有缓存更差.

使用ConcurrentHashMap代替HashMap, 同时取消对compute方法的同步可以极大的改善性能:

public class Memorizer2<A, V> implements Computable<A, V> {     private final Map<A, V> cache = new ConcurrentHashMap<A, V>();     private final Computable<A, V> c;     public Memorizer2(Computable<A, V> c) { this.c = c; }     public V compute(A arg) throws InterruptedException {         V result = cache.get(arg);         if (result == null) {             result = c.compute(arg);             cache.put(arg, result);         }         return result;     } }?

ConcurrentHashMap是线程安全的, 并且具有极好的并发性能. 但是该设计仍存在问题: 无法避免所有的重复的计算. 有时这是可以的, 但对于一些要求苛刻的系统, 重复计算可能会引发严重的问题. Memorizer2的问题在于一个线程在执行compute方法的过程中, 其他线程以相同的参数调用compute方法时, 无法从缓存中获知已有线程正在进行该参数的计算的信息, 因此造成了重复计算的发生. 针对这一点, 可以改进缓存的设计:

public class Memorizer3<A, V> implements Computable<A, V> {     // 改为缓存Future    private final Map<A, Future<V>> cache             = new ConcurrentHashMap<A, Future<V>>();     private final Computable<A, V> c;     public Memorizer3(Computable<A, V> c) { this.c = c; }     public V compute(final A arg) throws InterruptedException {         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;     // 在计算开始前就将Future对象存入缓存中.            cache.put(arg, ft);             ft.run(); // call to c.compute happens here         }         try {     // 如果缓存中存在arg对应的Future对象, 就直接调用该Future对象的get方法.    // 如果实际的计算还在进行当中, get方法将被阻塞, 直到计算完成            return f.get();         } catch (ExecutionException e) {             throw launderThrowable(e.getCause());         }     } }?

Memorizer3中的缓存系统看起来已经相当完美: 具有极好的并发性能, 也不会存在重复计算的问题. 真的吗? 不幸的是Memorizer3仍然存在重复计算的问题, 只是相对于Memorizer2, 重复计算的概率降低了一些. cache.get(arg)的结果为null, 不代表cache.put(arg, ft)时cache中依旧没有arg对应的Future, 因此直接调用cache.put(arg, ft)是不合理的:

public class Memorizer<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 Memorizer(Computable<A, V> c) { this.c = c; }     public V compute(final A arg) throws InterruptedException {         while (true) {             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); // 使用putIfAbsent测试是否真的将ft存入了缓存, 如果存入失败, 说明cache中已经存在arg对应的future对象// 否则才进行计算.                f = cache.putIfAbsent(arg, ft);                 if (f == null) { f = ft; ft.run(); }             }             try {                 return f.get();             } catch (CancellationException e) { // 当计算被取消时, 从缓存中移除arg-f键值对                cache.remove(arg, f);             } catch (ExecutionException e) {                 throw launderThrowable(e.getCause());             }         }     } }?

至此才真正实现了高效且线程安全的缓存.

?

PS: 终于看完了JCIP的第五章, 这一章真是又臭又长...

?

1 楼 xnmjy 2012-04-12 Memorizer3中的缓存系统看起来已经相当完美: 具有极好的并发性能, 也不会存在重复计算的问题. 真的吗? 不幸的是Memorizer3仍然存在重复计算的问题, 只是相对于Memorizer2, 重复计算的概率降低了一些. cache.get(arg)的结果为null, 不代表cache.put(arg, ft)时cache中依旧没有arg对应的Future, 因此直接调用cache.put(arg, ft)是不合理的: 2 楼 coolxing 2012-04-12 xnmjy 写道Memorizer3中的缓存系统看起来已经相当完美...不合理的:
朋友, 你想表达什么? 是觉得我的叙述词不达意吗? 3 楼 sdslnmd 2012-04-28 if (f == null) { f = ft; ft.run(); } 这段。f.fun()和ft.run有什么区别吗？
最后获取的时候 f.get()和ft.get()是否也有区别呢？ 4 楼 sdslnmd 2012-04-28 sdslnmd 写道 if (f == null) { f = ft; ft.run(); } 这段。f.fun()和ft.run有什么区别吗？
最后获取的时候 f.get()和ft.get()是否也有区别呢？

是不是这样理解 ft.run()是在另一个线程中。f可以获取ft中运行的结果。
如果是ft.get的话会阻塞。 5 楼 coolxing 2012-04-28 @sdslnmd f是cache.putIfAbsent(arg, ft)的返回值, 如果f==null, 说明ft被存进cache时cache中仍然没有arg对应的FutureTask. 第21行中调用f.run和ft.run都是可以的, 因为此时f和ft指向一样的对象. 但是在24行只能调用f.get, ft在第24行已经超出了作用范围.第24行只有f才是cache中arg所对应的FutureTask对象