缓存实战小项目

高性能缓存项目

目标:从0开始迭代,手把手一步步设计并实现

概述

缓存的用处:缓存在实际生产中是非常重要的工具,有了缓存之后,我们可以避免重复计算,提高吞吐量

虽然缓存乍一看很简单,不就是一个Map吗?最初级的缓存确实可以用一个Map来实现,不过一个功能晚辈、性能强劲的缓存,需要考虑的店就非常多了,我们从最简单的HashMap入手,一步步提高我们缓存的性能。

最初始版本

从最简单的案例开始

package imooccache;

import java.util.HashMap;
import java.util.concurrent.TimeUnit;

/**
 * 最简单的形式:HashMap
 */
public class IMoocCache {

		//v1.0
  //  private static  HashMap<String,Integer> cache = new HashMap<>();
		//v2.0  加入final后,该变量只能被被赋值一次
     private static final  HashMap<String,Integer> cache = new HashMap<>();

 //   public static Integer computer(String userId) throws InterruptedException {
 public synchronized Integer computer(String userId) throws InterruptedException {
        Integer result = cache.get(userId);
        //先检查HshMap里面有没有保存过之前的计算结果
        if(result==null){

                result = doCompute(userId);


            cache.put(userId,result);
        }

        return result;

    }


    private static Integer doCompute(String userId) throws InterruptedException {
        TimeUnit.SECONDS.sleep(5);

        return new Integer(userId);
    }


    public static void main(String[] args) throws InterruptedException {

        IMoocCache iMoocCache = new IMoocCache();
        System.out.println("开始计算了");
        Integer result = computer("13");

        System.out.println("第一次计算结果"+result);
      result =  IMoocCache.computer("13");

        System.out.println("第二次计算结果"+result);
    }
}

程序第二次计算结果将会远远快于第一次,因为程序将第一次计算结果存在了HashMap中,计算时先查询HashMap

但是V1.0版本的代码存在问题:程序中使用了hashmap,这是线程不安全的,这时候我们很容易想到利用synchronize关键字来修饰hashmap,以保证其线程安全性。但是使用synchronize关键字的V2.0同样会带来问题,如上所示,整个synchronize锁的范围过大,业务代码和非业务代码全部锁住了。这会导致程序运行效率低下,代码的复用性差,这时候考虑给hashmap加final关键字,并且使用装饰者模式把代码侵入的问题解决。

解决代码复用性差问题:

使用装饰者模式重构代码

这里我们假设ExpensiveFunction类是耗时计算的实现类,实现了Computable接口,但是其本身不具备缓存功能,也不需要考虑缓存的事情。

为了将业务代码compute方法解耦,写一个接口

package imooccache.computable;

/**
 * 有一个计算函数computer,用来代表耗时计算,每个计算器都要事先这个接口,这样就可以无情如实现缓存功能
 */

public interface Computable<A,V> {
    V compute(A arg) throws Exception; 

}

其实现类为:

package imooccache.computable;

public class ExpensiveFunction implements Computable<String, Integer> {


    @Override
    public Integer compute(String arg) throws Exception {
        Thread.sleep(5000);
        return Integer.valueOf(arg);
    }
}

具体代码如下:

package imooccache;

import imooccache.computable.Computable;
import imooccache.computable.ExpensiveFunction;

import java.util.HashMap;
import java.util.Map;

public class ImoocCache2<A,V> implements Computable<A,V> {


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

    private final Computable<A,V> c;

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

    @Override
    public synchronized V compute(A arg) throws Exception {
        System.out.println("进入缓存机制");
        //一旦进入缓存机制,那么需要查找值是否已经被计算过
        V result = cache.get(arg);

        if(result==null){
            //如果result没有被计算
            result = c.compute(arg);

            //计算了结果后就需要将它放入缓存中

            cache.put(arg,result);
        }

        return result;
    }


    public static void main(String[] args) {


        ImoocCache2<String, Integer> expensiveComputer = new ImoocCache2<>(
                new ExpensiveFunction());
        try {
            Integer result = expensiveComputer.compute("666");
            System.out.println("第一次计算结果"+result);
            result = expensiveComputer.compute("666");
            System.out.println("第二次计算结果"+result);
        } catch (Exception e) {
            e.printStackTrace();
        }





    }
}

##### 使用ConcurrentHashMap

​ 但是目前程序仍然存在问题:那就是性能差,不能并行计算,一开始尝试把synchronize的范围缩小,但是此时是写安全的,但是读仍然不安全,因此将hashmap换成concurrenthashmap

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

改为

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

但是ConcurrentHashMap也会带来新的问题,它会导致在计算完成前,另一个要求计算 相同值得请求到来的时候,会导致计算两边,这和缓存想避免多次计算的初衷恰恰相反,这是不可接受的。这个时候就要引入Future和Callable来避免重复计算的问题,修改后的代码如下:

package imooccache.computable;

import java.util.Map;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;

/**
 * 利用future避免重复计算
 * @param <A>
 * @param <V>
 */

public class ImoocCache7<A,V> implements Computable<A,V> {


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

    private final Computable<A,V> c;

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

    @Override
    public V compute(A arg) throws Exception {
        Future<V> f = cache.get(arg);

        if(f==null){
          Callable<V> callable= new Callable<V>() {
                @Override
                public V call() throws Exception {
                    return c.compute(arg);
                }
            };

            FutureTask<V> ft = new FutureTask<>(callable);
            //因为此时f为空,所以需要对f赋值
            f = ft;
            cache.put(arg,ft);
            System.out.println("从futureTask调用了计算函数");
            ft.run();

        }

        return f.get();

    }


    public static void main(String[] args) {


        ImoocCache7<String, Integer> expensiveComputer = new ImoocCache7<>(
                new ExpensiveFunction());
        try {
            Integer result = expensiveComputer.compute("666");
            System.out.println("第一次计算结果"+result);
            result = expensiveComputer.compute("666");
            System.out.println("第二次计算结果"+result);
        } catch (Exception e) {
            e.printStackTrace();
        }




    }
}

用原子操作消除重复计算

​ 上面的代码这个时候仍然会存在重复的可能,比如两个线程在时间上十分接近(可以看成同时)的运行相同的操作,那么仍然会创建两个任务去计算相同的值。这时候我们可以使用原子操作putIfAbsent来避免。

将上面代码中的put改成putIfAbsent

package imooccache;

import imooccache.computable.Computable;
import imooccache.computable.ExpensiveFunction;

import java.util.Map;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;

/**
 * 利用future避免重复计算
 * @param <A>
 * @param <V>
 */

public class ImoocCache8<A,V> implements Computable<A,V> {


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

    private final Computable<A,V> c;

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

    @Override
    public V compute(A arg) throws Exception {
        Future<V> f = cache.get(arg);

        if(f==null){
          Callable<V> callable= new Callable<V>() {
                @Override
                public V call() throws Exception {
                    return c.compute(arg);
                }
            };

            FutureTask<V> ft = new FutureTask<>(callable);
           // f = ft;
    /****/      f =  cache.putIfAbsent(arg,ft);

          if(f==null){
              f = ft;
              System.out.println("从futureTask调用了计算函数");
              ft.run();
          }


        }

        return f.get();

    }


    public static void main(String[] args) {


        ImoocCache8<String, Integer> expensiveComputer = new ImoocCache8<>(
                new ExpensiveFunction());
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("666");
                    System.out.println("第一次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("666");
                    System.out.println("第三次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("667");
                    System.out.println("第二次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();
    }
}

异常处理

对于一个高性能的缓存,我们还需要考虑针对各种异常的处理方法。

我们假设会出现异常

ImoocCache10<String, Integer> expensiveComputer = new ImoocCache10<>(new ExpensiveFunction());

改为

ImoocCache10<String, Integer> expensiveComputer = new ImoocCache10<>(new MayFail());

MayFail方法的具体代码如下:

package imooccache.computable;

import java.io.IOException;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * 描述:     耗时计算的实现类,有概率计算失败
 *
 */
public class MayFail implements Computable<String, Integer>{

    @Override
    public Integer compute(String arg) throws Exception {
        double random = Math.random();
        if (random > 0.5) {
            throw new IOException("读取文件出错");
        }
        Thread.sleep(3000);
        return Integer.valueOf(arg);
    }
}

将compute方法进行改造

 @Override
    public V compute(A arg) throws InterruptedException, ExecutionException {
        while (true) {
            Future<V> f = cache.get(arg);
            if (f == null) {
                Callable<V> callable = new Callable<V>() {
                    @Override
                    public V call() throws Exception {
                        return c.compute(arg);
                    }
                };
                FutureTask<V> ft = new FutureTask<>(callable);
                f = cache.putIfAbsent(arg, ft);
                if (f == null) {
                    f = ft;
                    System.out.println("从FutureTask调用了计算函数");
                    ft.run();
                }
            }
            try {
                return f.get();
            } catch (CancellationException e) {
                System.out.println("被取消了");
                cache.remove(arg);
                throw e;
            } catch (InterruptedException e) {
                cache.remove(arg);
                throw e;
            } catch (ExecutionException e) {
                System.out.println("计算错误,需要重试");
                cache.remove(arg);
            }
        }
    }
缓存过期

通常情况下,缓存不是数据库,因此,我们需要对缓存设置过期时间。所以我们给缓存添加过期功能

在这里我们写一个compute的重载方法,参数中包含超时时间

   public V compute(A arg, long expire) throws ExecutionException, InterruptedException {
        if (expire>0) {
            executor.schedule(new Runnable() {
                @Override
                public void run() {
                    expire(arg);
                }
            }, expire, TimeUnit.MILLISECONDS);
        }
        return compute(arg);
    }

其中的expire方法的具体代码如下:

 public synchronized void expire(A key) {
        Future<V> future = cache.get(key);
        if (future != null) {
            if (!future.isDone()) {
                System.out.println("Future任务被取消");
                future.cancel(true);
            }
            System.out.println("过期时间到,缓存被清除");
            cache.remove(key);
        }
    }

整体的代码如下:

package imooccache;

import imooccache.computable.Computable;
import imooccache.computable.MayFail;
import java.util.Map;
import java.util.concurrent.Callable;
import java.util.concurrent.CancellationException;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

/**
 * 描述:     出于安全性考虑,缓存需要设置有效期,到期自动失效,否则如果缓存一直不失效,那么带来缓存不一致等问题
 */
public class ImoocCache10<A, V> implements Computable<A, V> {

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

    private final Computable<A, V> c;

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

    @Override
    public V compute(A arg) throws InterruptedException, ExecutionException {
        while (true) {
            Future<V> f = cache.get(arg);
            if (f == null) {
                Callable<V> callable = new Callable<V>() {
                    @Override
                    public V call() throws Exception {
                        return c.compute(arg);
                    }
                };
                FutureTask<V> ft = new FutureTask<>(callable);
                f = cache.putIfAbsent(arg, ft);
                if (f == null) {
                    f = ft;
                    System.out.println("从FutureTask调用了计算函数");
                    ft.run();
                }
            }
            try {
                return f.get();
            } catch (CancellationException e) {
                System.out.println("被取消了");
                cache.remove(arg);
                throw e;
            } catch (InterruptedException e) {
                cache.remove(arg);
                throw e;
            } catch (ExecutionException e) {
                System.out.println("计算错误,需要重试");
                cache.remove(arg);
            }
        }
    }

    public V computeRandomExpire(A arg) throws ExecutionException, InterruptedException {
        long randomExpire = (long) (Math.random() * 10000);
        return compute(arg, randomExpire);
    }

    public final static ScheduledExecutorService executor = Executors.newScheduledThreadPool(5);

    public V compute(A arg, long expire) throws ExecutionException, InterruptedException {
        if (expire>0) {
            executor.schedule(new Runnable() {
                @Override
                public void run() {
                    expire(arg);
                }
            }, expire, TimeUnit.MILLISECONDS);
        }
        return compute(arg);
    }

    public synchronized void expire(A key) {
        Future<V> future = cache.get(key);
        if (future != null) {
            if (!future.isDone()) {
                System.out.println("Future任务被取消");
                future.cancel(true);
            }
            System.out.println("过期时间到,缓存被清除");
            cache.remove(key);
        }
    }
    public static void main(String[] args) throws Exception {
        ImoocCache10<String, Integer> expensiveComputer = new ImoocCache10<>(
                new MayFail());
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("666",5000L);
                    System.out.println("第一次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("666");
                    System.out.println("第三次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Integer result = expensiveComputer.compute("667");
                    System.out.println("第二次的计算结果:" + result);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();


        Thread.sleep(6000L);
        Integer result = expensiveComputer.compute("666");
        System.out.println("主线程的计算结果:" + result);
    }
}

上面代码中,我们还考虑了如果出现大量缓存同时过期,这会导致出现缓存击穿的情况,因此对过期时间进行随机设置。

测试性能
package imooccache;

import imooccache.computable.ExpensiveFunction;

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ImoocCache13 {

    static ImoocCache10<String,Integer> expensiveComputer = new ImoocCache10<>(new ExpensiveFunction());
    public static void main(String[] args) {
    //测试20000个线程执行的效率
        ExecutorService executorService = Executors.newFixedThreadPool(20000);


        for (int i = 0; i < 20000; i++) {
            executorService.submit(()->{
                Integer result = null;


                try {
                   result = expensiveComputer.compute("666");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } catch (ExecutionException e) {
                    e.printStackTrace();
                }

                System.out.println(result);
            });
        }

    }
}

性能测试优化

因为现成的提交时间还是不是完全同步的,因此我们需要利用CountDownLatch来实现线程的统一触发

package imooccache;

import imooccache.computable.ExpensiveFunction;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 描述:     TODO
 */
public class ImoocCache12 {

    static ImoocCache10<String, Integer> expensiveComputer = new ImoocCache10<>(
            new ExpensiveFunction());
    public static CountDownLatch countDownLatch = new CountDownLatch(1);

    public static void main(String[] args) throws InterruptedException {
        ExecutorService service = Executors.newFixedThreadPool(100);
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            service.submit(() -> {
                Integer result = null;
                try {
                    System.out.println(Thread.currentThread().getName()+"开始等待");
                    countDownLatch.await();
                    SimpleDateFormat dateFormat = ThreadSafeFormatter.dateFormatter.get();
                    String time = dateFormat.format(new Date());
                    System.out.println(Thread.currentThread().getName()+"   "+time+"被放行");
                    result = expensiveComputer.compute("666");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } catch (ExecutionException e) {
                    e.printStackTrace();
                }
                System.out.println(result);
            });
        }

        Thread.sleep(5000);
        countDownLatch.countDown();
        service.shutdown();
    }
}
class ThreadSafeFormatter {

    public static ThreadLocal<SimpleDateFormat> dateFormatter = new ThreadLocal<SimpleDateFormat>() {

        //每个线程会调用本方法一次,用于初始化
        @Override
        protected SimpleDateFormat initialValue() {
            return new SimpleDateFormat("mm:ss");
        }

        //首次调用本方法时,会调用initialValue();后面的调用会返回第一次创建的值
        @Override
        public SimpleDateFormat get() {
            return super.get();
        }
    };
}
上一篇:找出n个数中出现了奇数次的两个数


下一篇:AQS - 抽象同步队列:独占锁的实现