cache 发展之路

HashMap

最开始可以使用 Java 自带的 Map 进行数据缓存，比如把数据库中最常使用的部分可以存在 HashMap 中

1
2
3
4
5
6
7
8
9
10
11
Map<String,String> map = new HashMap<>();
Mapper mapper;
public String getHotData(String name) {
    String result = map.get(name);
    if (result == null) {
        result = mapper.get(name);
        map.put(name, result);
    }
    return result;
}

这样做的一个问题就是缓存无法进行淘汰，只会无限增长，所以 HashMap 很快就被淘汰了。

当然可以使用弱引用解决内存一直增长的问题

虽然无法进行淘汰，但是在一些不需要淘汰机制的场景就可以使用 HashMap，比如实现一个简单的 IOC 容器的时候，就可以通过 bean 的名字把每个 bean 都缓存下来，就会比用顺序表好很多。

LRUHashMap

为了解决 HashMap 无法进行数据淘汰的问题，就有人提出了一些淘汰算法来实现，常见的有 FIFO, LRU, LFU 等

FIFO

  • 先进先出调度算法 。如果一个数据是最先进入的，那么可能认为它被访问的可能性很小，当空间满的时候，最先进入的数据（队首元素）会被最早淘汰掉，并把新加入的数据插入到队尾。

它的缺点：因为 FIFO 置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问或者没有给进程分配足够的页面，所以 FIFO 算法会使得一些页面频繁地被替换和重新申请内存，导致了缺页率增加。

LRU

  • 最近最久未使用调度算法。如果一个数据在最近一段时间没有被访问到，那么可认为它在未来被访问的可能性也很小，当空间满的时候，最久没有访问的数据最先被淘汰。

它的缺点：如果是偶尔的批量访问不同的数据时其命中率就会很低。比如我频繁的访问 A，接着访问不同的数据直到 A 被淘汰，此时我再访问 A，则不得不又再次把 A 加入到 Cache 中，显然这种方式是不合时宜的，因为 A 已经访问了很多次了，不应该将其淘汰而把一堆只访问一次的数据加入到 Cache 中。

LFU

  • 最近最不常用的调度算法 。应将这段时间内访问次数最少的数据替换出。为此给每个数据设置一个计数器，每访问一次，计数器的值+1。当发送冲突的时候，就找到当前计数器的值最小的那一个数据，把这个数据替换成新的元素。

上面的三种策略实现成本依次提高，命中率也是一个比一个好。

一般选择居中的方案即可，LRU 也是面试常问的问题，那么如何实现一个 LRUMap 呢？

在 Java 中，继承 LinkedHashMap，重写 removeEldestEntry 方法，即可完成一个简单的 LRUMap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LRUMap<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUMap(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    @Override
    public V get(Object key) {
        return super.get(key);
    }

    @Override
    public V put(K key, V value) {
        return super.put(key, value);
    }
}

LinkedHashMap 中维护了一个双向链表，根据构造方法中的第三个参数，我们设置按照访问顺序排序，每次 get 或者 put 时会把插入的的或者查询到的值放在链表末尾。

通过重写 removeEldestEntry，就可以保证不会进行扩容，这样就实现了一个 LRUMap。

Guava cache

LRUMap 可以用来进行缓存数据的淘汰，但是有几个问题:

  • 锁竞争严重，可以看见我的代码中，Lock 是全局锁，在方法级别上面的，当调用量较大时，性能必然会比较低。

  • 不支持过期时间

  • 不支持自动刷新

所以谷歌的大佬们对于这些问题，按捺不住了，发明了 Guava cache，在 Guava cache 中你可以如下面的代码一样，轻松使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void main(String[] args) {
    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;
        }
    };
}

手写 cache

接口定义

定义缓存接口，兼容 Map

1
2
public interface ICache<K, V> extends Map<K, V> {
}

接口实现

主要关注 put 实现

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public V put(K key, V value) {
    ICacheEvictContext<K, V> context = new CacheEvictContext<>();
    context.setKey(key);
    context.setSize(sizeLimit);
    context.setCache(this);
    evict.evict(context);
    if (isExceeded()) {
        throw new CacheRuntimeException("Cache size limit exceeded");
    }
    return map.put(key, value);
}

put 前检查缓存状态，然后执行淘汰策略。

淘汰策略

淘汰策略可以有多种实现，此处实现一个最基本的 FIFO。

以实现接口方式，便于后期灵活切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class FIFOEvict<K, V> extends AbstractEvict<K, V> {

    /**
     * 维护先入先出策略
     */
    private final Queue<K> queue = new LinkedList<>();

    @Override
    protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {
        ICacheEntry<K,V> result = null;
        ICache<K, V> cache = context.cache();
        if (cache.size() >= context.size()) {
            K evictKey = queue.remove();
            V evictValue = cache.remove(evictKey);
            result = CacheEntry.of(evictKey, evictValue);
        }
        final K key = context.key();
        queue.add(key);
        return result;
    }
}

使用一个队列，当队列超过最大元素限制时，删除最早的元素。

使用

为了方便使用，实现一个 Builder 类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public final class CacheBuilder<K, V> {

    private CacheBuilder() {
    }

    private Map<K, V> map = new HashMap<>();

    private int size = 2;

    private ICacheEvict<K, V> evict = new FIFOEvict<>();

    public ICache<K, V> build() {
        return new Cache<>(map, size, evict);
    }
}

测试使用

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    ICache<Object, Object> cache = new CacheBuilder<>().build();
    cache.put("1", "1");
    cache.put("2", "2");
    cache.put("3", "3");
    cache.put("4", "4");
    System.out.println(cache.keySet());
}

默认为 FIFO 策略，结果如下

结果
1
[3, 4]

评论区仅供交流，有问题请提 issue 反馈。