如何编写一个有效的缓存

9/6/2015来源:Java教程人气:922

如何编写一个有效的缓存

缓存作为计算机历史上最重要的发明之一,对计算机历史起到了举足轻重的作用,因为缓存可以协调两个速度不一致的组件之间的并行运作。内存作为CPU和非易失性存储介质之间的缓存,避免CPU每次读取指令,读取数据都去速度缓慢的硬盘读取。快速缓存作为内存和CPU之间的缓存进一步提高了CPU的效率,现在大部分CPU都支持指令预取,CPU会预测后面要执行的指令预取到快速缓存中。而我们平时也直接或间接地会用到缓存技术,那如果要自己实现一个线程安全的缓存,要注意哪些问题呢?我们一步步来探讨这个问题。

假设我们提供一个服务,客户端提供一个字符串,我们返回一个对应的Long数值(当然这只是为了演示方便举的简单例子),为了提高效率,我们不希望每次都重复计算,因此我们把计算结果保存在一个缓存里,如果下次有相同的请求过来就直接返回缓存中的数据。

首先我们把计算任务抽象成Compute接口:

public interface Compute<A,V>{ V compute(A args);}

一个不使用缓存计算的类:

public class NoCache implements Compute<String, Long>{    @Override   public Long compute(String args)   {     // TODO Auto-generated method stub      return Long.valueOf(args);   }}

这样每次都要重复计算,效率比较低,因此我们引入了一个Map来保存计算结果:

public class BasicCache1<A,V> implements Compute<A, V>{PRivate final Map<A, V> cache=new HashMap<>();private final Compute<A, V> c; public BasicCache1(Compute<A, V> c){   this.c=c;} @Overridepublic synchronized V compute(A args) throws Exception{   V ans=cache.get(args);   if(ans==null)   {     ans=c.compute(args);     cache.put(args, ans);   }    return ans;}}

这里因为HashMap不是线程安全的,因此计算方法被写成了同步方法,这样的话,每次请求最后实际都是串行执行的,大大降低了系统的吞吐量。就像下面这幅图表示的:

既然这样,我们就改用ConcurrentHashMap试试:

public class BasicCache2<A,V> implements Compute<A, V>{   private final Map<A,V> cache=new ConcurrentHashMap<>();   private final Compute<A, V> c;     public BasicCache2(Compute<A, V> c)   {     this.c=c;   }     @Override   public V compute(A args) throws Exception   {     V ans=cache.get(args);     if(ans==null)     {        ans=c.compute(args);        cache.put(args, ans);     }     return ans;   }}

这里没有同步compute操作,因此系统可以并发地执行请求,但是假如多个有相同参数的请求短时间内先后到达,这个时候先到达的请求还没来得及把结果写入缓存(因为计算耗时),后来的请求就会重复计算,降低了缓存的效率。一图胜前言:

因此我们就想,能不能先更新缓存再去计算呢,这样不就可以消除了重复计算吗?听起来不错,可是我们如何在更新了缓存后获取计算结果呢(因为这时计算还没有完成)?这里就要用到JDK提供的Future和Callable接口,Callable接口和Runnable接口一样,是线程任务的抽象接口,不同的是Callable的call方法可以返回一个Future对象,而Future对象的get方法会阻塞等待任务执行结果。既然有这么好的基础设施,那我们赶紧开撸:

public class BasicCache3<A,V> implements Compute<A, V>{   private final Map<A, Future<V>> cache=new ConcurrentHashMap();   private final Compute<A, V> c;   private ExecutorService executors=Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1);     public BasicCache3(Compute<A, V> c)   {     this.c=c;   }     @Override   public V compute(final A args) throws Exception   {     Future<V> ans=cache.get(args);     if(ans==null)     {        Callable<V> computeTask=new Callable<V>()        {           @Override           public V call() throws Exception           {             return c.compute(args);           }              };        ans= executors.submit(computeTask);        cache.put(args, ans);     }     return ans.get();   }} 

上面这段代码里把计算任务提交到线程池去执行,返回了一个结果句柄供后面获取计算结果。可是仔细观察后,我们发现似乎还是有点不对,这样似乎减小了重复计算的概率,但是其实只是减小了发生的窗口,因为判断是否在缓存中和put到缓存中两个操作虽然单独都是线程安全的,但是还是会发生先到达的请求还没来得及put到缓存的情况,而其本质原因就是先检查再插入这样的复杂操作不是原子操作,就好比++这个操作,CPU需要先取原值,再操作加数,最后写回原值也会出现后一次写入覆盖前一次的情况,本质都是因为复杂操作的非原子性。下图演示了这种情况:

因此JDK中的ConcurrentMap接口提供了putIfAbsent的原子操作方法,可是如果我们像前一个例子中一样先获取计算结果的Future句柄,即便是我们不会重复更新缓存,计算任务还是会执行,依然没达到缓存的效果,因此我们需要一个能够在任务还没启动就可以获取结果句柄,同时能够自由控制任务的启动、停止的东西。当然JDK里也有这样的东西(这里插一句,JDK的concurrent包的代码基本都是Doug Lea写的,老头子代码写的太牛逼了),就是FutureTask,既然如此,赶紧开撸:

public class BasicCache4<A,V> implements Compute<A, V>{private final ConcurrentMap<A, Future<V>> cache=new ConcurrentHashMap<>();private final Compute<A, V> c; public BasicCache4(Compute<A, V> c){   this.c=c;}@Overridepublic V compute(final A args) throws Exception{   Future<V> ans=cache.get(args);   if(ans==null)   {     Callable<V> computeTask=new Callable<V>()     {        @Override        public V call() throws Exception        {           return c.compute(args);        }     };     FutureTask<V> ft=new FutureTask<V>(computeTask);     ans=cache.putIfAbsent(args, ft);     if(ans==null)//     {        ans=ft;        ft.run();     }   }   return ans.get();}}

上面这段代码中,我们创建了一个FutureTask任务,但是并没有立即执行这个异步任务,而是先调用ConcurrentHashMap的putIfAbsent方法来尝试把结果句柄更新到缓存中去,这个方法的返回值是Map中的旧值,因此如果返回的是null,也就是说原来缓存中不存在,那我们就启动异步计算任务,而如果缓存中已经存在的话,我们就直接调用缓存中的Future对象的get方法获取计算结果,如果其他请求中的计算任务还没有执行完毕的话,get方法会阻塞直到计算完成。实际运行效果见下图:

至此,我们算是构建了一个有效线程安全的缓存了,当然这个版本其实还是会有很多问题,比如如果异步计算任务被取消的话,我们应该循环重试,但是一方面我们为了简单只考虑了正常情况,另一方面FutureTask是局部变量,在线程栈层面已经保证了其他线程或代码无法拿到该对象。最后用一张xmind图作为总结:

参考资料:《java Concurrency in Practice》