实现固定缓存大小 - zxlrise/cache GitHub Wiki
当我们项目流量比较大或者查询数据库特别频繁，这个时候为了缓解数据库压力，我们可以使用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中查询到了，就可以直接返回我们想要的结果。如果HashMap中查询不到，我们再在数据库中查询，之后将查询到的结果放入HashMap中。这样，我们就通过HashMap实现了一个简易版的缓存。
但是HashMap实现的缓存无法进行数据淘汰，因此内存会无限制的增长， 所以hashMap很快也被淘汰了。 同时HashMap也无法满足像Redis一样，存放一些热点数据。
尽管HashMap有很多缺点， 但其依旧可以在某些场景下作为缓存，当不需要淘汰机制的时候，比如我们利用反射，如果我们每次都通过反射去搜索 Method, Field，性能必定低效，这时我们用HashMap将其缓存起来，性能能提升很多。
缓存被写满是不可避免的，这个时候我们就需要把一些数据给淘汰掉。 接下来我们介绍几种常见的缓存淘汰算法， 分别是 FIFO，LRU，LFU 。
FIFO按照“先进先出（First In，First Out）”的原理淘汰数据，正好符合队列的特性，数据结构上使用队列Queue来实现。 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动，淘汰FIFO队列头部的数据。 优点： 实现简单，存贮成本低，复杂度低。 缺点： 无法根据数据的使用频次、时间等维度进行优化，会导致缓存命中率降低。
Least Recently used 最近未使用，通常被翻译为「最近最少使」
B 和 A 都在淘汰进程之前使用过，更新最新的使用时间。C 则一直没有被使用，虽然不是最久的数据，但是根据 LRU，它需要被淘汰。最近最少使用页面置换算法，也就是首先淘汰最长时间未被使用的页面。关键是看页面最后一次被使用到发生调度的时间长短。 优点： 热点缓存将被持久命中 缺点： 当所有缓存数据都变成热点后，将失去 LRU 的优点。
Least Frequently Used 最不常用淘汰算法，通常被翻译为「最近最不常用」
优点： 提高频繁使用的数据的命中效率。 缺点： 当所有数据都很频繁访问的时候，将失去优点。 对于这三种淘汰算法，实现成本是一个比一个高，同样的命中率也是一个比一个好。 在这里我们选择实现成本不是太高，而命中率也还行的LRU淘汰算法进行实现。 通过继承 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永远也走不到扩容的逻辑了 。
使用LRUMap来进行缓存数据的淘汰，会有几个问题:
- 锁竞争严重，在代码中，Lock是全局锁，在方法级别上面的，当调用量较大时，性能必然会比较低。
- 不支持过期时间。
- 不支持自动刷新。 因此出现了 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;
}
};
}定义缓存接口继承自 Map 接口
/**
* 缓存接口
* @author binbin.hou
* @since 0.0.1
*/
public interface ICache<K, V> extends Map<K, V> {
}
2.2、核心实现
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);
}先实现一个最基本的 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);
}
}/**
* 缓存引导类
* @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]