关于redis:从零开始手写缓存之如何实现固定缓存大小

前段时间有一位共事体检，体检医生说他三高。

我打趣道，程序员三高不是高性能、高并发、高可用吗？你是哪三高？

每一个谋求性能的开发者，都对高性能手不释卷地谋求着，而缓存是咱们踏上这条高性能小道的必经之路。

小到 cpu 设计，大到服务分布式缓存，咱们每时每刻都在接触缓存，明天咱们就一起学习下缓存的倒退之路，以及如何如何手写一个能够指定大小的 cache。

当咱们利用有肯定流量之后或者查询数据库特地频繁，这个时候就能够祭出咱们的 java 中自带的 HashMap 或者 ConcurrentHashMap。

咱们能够在代码中这么写:

public class CustomerService {private HashMap<String,String> hashMap = new HashMap<>();
    private CustomerMapper customerMapper;
    public String getCustomer(String name){String customer = hashMap.get(name);
        if (customer == null){customer = customerMapper.get(name);
            hashMap.put(name,customer);
        }
        return customer;
    }
}

然而这样做就有个问题 HashMap 无奈进行数据淘汰，内存会无限度的增长，所以 hashMap 很快也被淘汰了。

比方以前查问，查问 redis，然而心愿能够本地缓存放一些热点数据，应用 HashMap 显然无奈满足这种需要。

当然，此处能够应用弱援用解决内存始终增长的问题。

当然并不是说他齐全就没用，就像咱们现代社会也不是所有的货色都是过期的，比方咱们中华名族的传统美德是永不过期的，

就像这个 hashMap 一样的能够在某些场景下作为缓存，当不须要淘汰机制的时候，比方咱们利用反射，如果咱们每次都通过反射去搜寻 Method, Field，性能必然低效，这时咱们用 HashMap 将其缓存起来，性能能晋升很多。

在现代社会中难住咱们的问题无奈进行数据淘汰，这样会导致咱们内存有限收缩, 显然咱们是不能够承受的。

有人就说我把一些数据给淘汰掉呗，这样不就对了，然而怎么淘汰呢？随机淘汰吗？

当然不行，试想一下你刚把 A 装载进缓存，下一次要拜访的时候就被淘汰了，那又会拜访咱们的数据库了，那咱们要缓存干嘛呢？

所以聪慧的人们就创造了几种淘汰算法，上面列举下常见的三种 FIFO,LRU,LFU（还有一些 ARC,MRU 感兴趣的能够自行搜寻）:

先进先出，在这种淘汰算法中，先进入缓存的会先被淘汰。这种堪称是最简略的了，然而会导致咱们命中率很低。

试想一下咱们如果有个拜访频率很高的数据是所有数据第一个拜访的，而那些不是很高的是前面再拜访的，那这样就会把咱们的首个数据然而他的拜访频率很高给挤出。

最近起码应用算法。

在这种算法中防止了下面的问题，每次拜访数据都会将其放在咱们的队尾，如果须要淘汰数据，就只须要淘汰队首即可。

然而这个仍然有个问题，如果有个数据在 1 个小时的前 59 分钟拜访了 1 万次 (可见这是个热点数据), 再后一分钟没有拜访这个数据，然而有其余的数据拜访，就导致了咱们这个热点数据被淘汰。

最近起码频率应用。

在这种算法中又对下面进行了优化，利用额定的空间记录每个数据的应用频率，而后选出频率最低进行淘汰。这样就防止了 LRU 不能解决时间段的问题。

下面列举了三种淘汰策略，对于这三种，实现老本是一个比一个高，同样的命中率也是一个比一个好。

而咱们一般来说抉择的计划居中即可，即实现老本不是太高，而命中率也还行的 LRU, 如何实现一个 LRUMap 呢？

咱们能够通过继承 LinkedHashMap，重写 removeEldestEntry 办法，即可实现一个简略的 LRUMap。

class LRUMap extends LinkedHashMap {
    private final int max;
    private Object lock;
    public LRUMap(int max, Object lock) {
        // 无需扩容
        super((int) (max * 1.4f), 0.75f, true);
        this.max = max;
        this.lock = lock;
    }

    /**
     * 重写 LinkedHashMap 的 removeEldestEntry 办法即可
     * 在 Put 的时候判断，如果为 true，就会删除最老的
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {return size() > max;
    }
    public Object getValue(Object key) {synchronized (lock) {return get(key);
        }
    }
    public void putValue(Object key, Object value) {synchronized (lock) {put(key, value);
        }
    }
   
    public boolean removeValue(Object key) {synchronized (lock) {return remove(key) != null;
        }
    }
    public boolean removeAll(){clear();
        return true;
    }
}

在 LinkedHashMap 中保护了一个 entry(用来放 key 和 value 的对象) 链表。在每一次 get 或者 put 的时候都会把插入的新 entry，或查问到的老 entry 放在咱们链表开端。

能够留神到咱们在构造方法中，设置的大小特意设置到 max*1.4，

在上面的 removeEldestEntry 办法中只须要 size>max 就淘汰，这样咱们这个 map 永远也走不到扩容的逻辑了，

通过重写 LinkedHashMap，几个简略的办法咱们实现了咱们的 LruMap。

在近代社会中曾经创造进去了 LRUMap, 用来进行缓存数据的淘汰，然而有几个问题:

锁竞争重大，能够看见我的代码中，Lock 是全局锁，在办法级别下面的，当调用量较大时，性能必然会比拟低。
不反对过期工夫
不反对主动刷新

所以谷歌的大佬们对于这些问题，按捺不住了，创造了 Guava cache，在 Guava cache 中你能够如上面的代码一样，轻松应用:

public static void main(String[] args) throws ExecutionException {LoadingCache<String, String> cache = CacheBuilder.newBuilder()
            .maximumSize(100)
            // 写之后 30ms 过期
            .expireAfterWrite(30L, TimeUnit.MILLISECONDS)
            // 拜访之后 30ms 过期
            .expireAfterAccess(30L, TimeUnit.MILLISECONDS)
            //20ms 之后刷新
            .refreshAfterWrite(20L, TimeUnit.MILLISECONDS)
            // 开启 weakKey key 当启动垃圾回收时，该缓存也被回收
            .weakKeys()
            .build(createCacheLoader());
    System.out.println(cache.get("hello"));
    cache.put("hello1", "我是 hello1");
    System.out.println(cache.get("hello1"));
    cache.put("hello1", "我是 hello2");
    System.out.println(cache.get("hello1"));
}

public static com.google.common.cache.CacheLoader<String, String> createCacheLoader() {return new com.google.common.cache.CacheLoader<String, String>() {
        @Override
        public String load(String key) throws Exception {return key;}
    };
}

当然，对于性能的谋求是无极限的。

还有：

Caffeine: https://houbb.github.io/2018/09/09/cache-caffeine

LevelDB: https://houbb.github.io/2018/09/06/cache-leveldb-01-start

这些性能更加优越的实现，咱们后续能够做一下深刻学习。

本文，咱们来看一下，如何实现一个固定大小的缓存。

为了兼容 Map，咱们定义缓存接口继承自 Map 接口。

/**
 * 缓存接口
 * @author binbin.hou
 * @since 0.0.1
 */
public interface ICache<K, V> extends Map<K, V> {}

咱们次要看一下 put 时的实现：

@Override
public V put(K key, V value) {
    //1.1 尝试驱除
    CacheEvictContext<K,V> context = new CacheEvictContext<>();
    context.key(key).size(sizeLimit).cache(this);
    cacheEvict.evict(context);
    //2. 判断驱除后的信息
    if(isSizeLimit()) {throw new CacheRuntimeException("以后队列已满，数据增加失败！");
    }
    //3. 执行增加
    return map.put(key, value);
}

这里咱们能够让用户动静指定大小，然而指定大小肯就要有对应的淘汰策略。

否则，固定大小的 map 必定无奈放入元素。

淘汰策略能够有多种，比方 LRU/LFU/FIFO 等等，咱们此处实现一个最根本的 FIFO。

所有实现以接口的形式实现，便于前期灵便替换。

public class CacheEvictFIFO<K,V> implements ICacheEvict<K,V> {

    /**
     * queue 信息
     * @since 0.0.2
     */
    private Queue<K> queue = new LinkedList<>();

    @Override
    public void evict(ICacheEvictContext<K, V> context) {final ICache<K,V> cache = context.cache();
        // 超过限度，执行移除
        if(cache.size() >= context.size()) {K evictKey = queue.remove();
            // 移除最开始的元素
            cache.remove(evictKey);
        }

        // 将新加的元素放入队尾
        final K key = context.key();
        queue.add(key);
    }

}

FIFO 比较简单，咱们应用一个队列，存储每一次放入的元素，当队列超过最大限度时，删除最早的元素。

为了便于用户应用，咱们实现相似于 guava 的疏导类。

所有参数都提供默认值，应用 fluent 流式写法，晋升用户体验。

/**
 * 缓存疏导类
 * @author binbin.hou
 * @since 0.0.2
 */
public final class CacheBs<K,V> {private CacheBs(){}

    /**
     * 创建对象实例
     * @param <K> key
     * @param <V> value
     * @return this
     * @since 0.0.2
     */
    public static <K,V> CacheBs<K,V> newInstance() {return new CacheBs<>();
    }

    /**
     * map 实现
     * @since 0.0.2
     */
    private Map<K,V> map = new HashMap<>();

    /**
     * 大小限度
     * @since 0.0.2
     */
    private int size = Integer.MAX_VALUE;

    /**
     * 驱除策略
     * @since 0.0.2
     */
    private ICacheEvict<K,V> evict = CacheEvicts.fifo();

    /**
     * map 实现
     * @param map map
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> map(Map<K, V> map) {ArgUtil.notNull(map, "map");

        this.map = map;
        return this;
    }

    /**
     * 设置 size 信息
     * @param size size
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> size(int size) {ArgUtil.notNegative(size, "size");

        this.size = size;
        return this;
    }

    /**
     * 设置驱除策略
     * @param evict 驱除策略
     * @return this
     * @since 0.0.2
     */
    public CacheBs<K, V> evict(ICacheEvict<K, V> evict) {
        this.evict = evict;
        return this;
    }

    /**
     * 构建缓存信息
     * @return 缓存信息
     * @since 0.0.2
     */
    public ICache<K,V> build() {CacheContext<K,V> context = new CacheContext<>();
        context.cacheEvict(evict);
        context.map(map);
        context.size(size);

        return new Cache<>(context);
    }

}

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(2)
        .build();
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
cache.put("4", "4");
Assert.assertEquals(2, cache.size());
System.out.println(cache.keySet());

默认为先进先出的策略，此时输入 keys，内容如下：

[3, 4]

到这里，一个简易版的能够指定大小的缓存就实现了。

残缺代码临时本我的项目还没开源，能够关注【老马啸东风】，后盾回复缓存，获取源码。

目前为止，这个缓存实现是比较简单的，显然难以满足咱们平时更加灵便的利用场景。

咱们下一节将一起学习一下如何实现一个能够指定过期的缓存。

关于redis:从零开始手写缓存之如何实现固定缓存大小

程序员的三高

cache 倒退之路

现代社会 – HashMap

近代社会 – LRUHashMap

FIFO

LRU

LFU

古代社会 – Guava cache

代码实现

接口定义

外围实现

淘汰策略

疏导类

测试应用

小结

Just My Socks（注册教程内含优惠码）

关于redis:从零开始手写缓存之如何实现固定缓存大小

程序员的三高

cache 倒退之路

现代社会 – HashMap

近代社会 – LRUHashMap

FIFO

LRU

LFU

古代社会 – Guava cache

代码实现

接口定义

外围实现

淘汰策略

疏导类

测试应用

小结

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）