聊聊本地缓存

概述

本文介绍一些常见的缓存设计算法和思路。比如缓存淘汰的算法:LRU,SLRU,LFU,W-TinyLFU。实现入guava cache和caffeine。

LRU

LRU的全称是Least Recently Used,最近最少使用。如果缓存满了,把最近没有被使用到的数据移出。它的思想是:如果数据最近被访问过,将来被访问的概率也更高。

最简单的方式就是使用LinkedHashMap,几行代码就能实现。

public class LruCacheLinkedHashMapLazy<K, V> implements LruCache<K,V> {
    private LinkedHashMap<K, V> map;
    private final int CAPACITY;

    public LruCacheLinkedHashMapLazy(int capacity) {
        CAPACITY = capacity;
        map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CAPACITY;
            }
        };
    }
    @Override
    public V get(K key) {
        return map.getOrDefault(key, null);
    }
    @Override
    public void put(K key, V value) {
        map.put(key, value);
    }
}

LinkedHashMap通过hash表和双向链表维护数据,如果初始化时accessOrder=true,新加入或者访问的数据都会放到链表头部,这样,一直没被访问的node就会被顶到尾部,如果超出缓存大小,把链表尾部的数据删除即可。

也可以通过HashMapDoubley-Linked实现,这样更清晰看出怎么通过双向链表实现:

public class LRUCacheHashMapAndDoublyLinked<K, V> implements LruCache<K, V> {
    private class Node {
        K key;
        V value;
        Node prev, next;

        Node(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity, count;
    private Map<K, Node> map;
    private Node head, tail;

    public LRUCacheHashMapAndDoublyLinked(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    private void update(Node node) {
        remove(node);
        add(node);
    }

    private void add(Node node) {
        Node after = head.next;
        head.next = node;
        node.prev = head;
        node.next = after;
        after.prev = node;
    }

    private void remove(Node node) {
        Node before = node.prev, after = node.next;
        before.next = after;
        after.prev = before;
    }

    @Override
    public V get(K k) {
        Node n = map.get(k);
        if (null == n) {
            return null;
        }
        update(n);
        return n.value;
    }

    @Override
    public void put(K key, V value) {
        Node n = map.get(key);
        if (null == n) {
            n = new Node(key, value);
            map.put(key, n);
            add(n);
            ++count;
        } else {
            n.value = value;
            update(n);
        }
        if (count > capacity) {
            Node toDel = tail.prev;
            remove(toDel);
            map.remove(toDel.key);
            --count;
        }
    }
}

但是,上面两个示例都不是并发安全的,需要加锁,加锁后怎么提升性能呢,后面详细说明。

LFU

LFU(Least Frequently Used)即最近最不常用,它的核心思想是只缓存那些经常使用的。这个算法必须要维护数据的访问频次,按照频次排序,淘汰频次最低的数据。


比如上图,至少有4个数据结构才能实现了LFU。
LFU缺点:
1. 数据年龄问题。比如某网站首页数据展示,当天访问量大,但是之后可能再也不会被访问到了。所以,访问频率并不是绝对完美的判断标准。对于过时数据,需要降低他的访问频次,即“动态衰老最经常使用»。
2. 内存开销: 就是已经从cache中移除,也要保存访问频次的记录。我们可以设置一个最大值,但是这个最大值应该是多少,也不好评估。

Guava cache 实现SLRU

对上面的示例,要并发安全,只能加锁。为了改善加锁后开销,可以像ConcurrentHashMap一样,把table分到一个个segment下,每个segment对应一个锁,来分散全局锁带来的性能损失,GuavaCache就是这样的实现,如下图。

guava cache还维护两个队列,accesQueuewriteQueue,用来实现segement的局部LRU和过期时间。另外还有一个recencyQueue,它用来提高accessQueue更新锁消耗。如果每次访问都加锁更新accessQueue,影响性能,guava把访问的数据更新到recencyQueue,recencyQueue通过ConcurrentLinkedQueue实现,并发安全。等写入数据时,再加锁从recencyQueue更新到accesQueue。

另外,对于过期数据的清理,guava并不是另起一个线程,而是每次有访问的时候才清理。

W-TinyLFU

不管是LFU还是LRU,都是希望在缓存填满后,淘汰掉那些在短期内可能不会使用的数据,从而提升缓存的命中率。LRU和LFU都有他的局限性。因为LFU的问题,LRU是一个比较流行的算法,它什么问题?

它不是抗扫描的。比如cache的大小是N,缓存N+1个item(第一个会被淘汰),如果顺序发起N个请求。将导致没有一个命中缓存。

W-TinyLFU 是一个综合LRU和LFU优点的实现方式:

其中TinyLFU维护了近期访问记录的频率信息,作为一个过滤器,当新记录来时,只有满足TinyLFU要求的记录才可以被插入缓存。其中实现算法采用ount-Min Sketch算法。以LRU作为淘汰方式,TinyLFU作为许入过滤器。

CountMin Sketch 通过矩阵和多个hash函数实现:

一个key,通过不同的hash定位到数组index,值加1,最后取min(8,6,7,6)=6作为此key的访问次数记录。因为hash冲突的原因,值不一定准确,但对于LFU的实现,这个误差可以忽略。下面我们看它是怎么解决LFU缺点的。

因为使用矩阵,跟数据量大小没关系,很好地解决了LFU的内存开销问题。对于数据年龄,可以添加一个计数上线,一旦到达上线,所有记录的Sketch数据都除2,从而实现衰减效果,对于短暂热点数据,如果之后一直没有访问,count/2不断衰减,直至淘汰。

下图是另一种表达方式: sketch 作为过滤器(filter)。当新来的数据比要驱逐的数据高频时,这个数据才会被缓存接纳。

基于java8的库caffeine就是这样的实现。缓存命中表现:


参考文档:
[1]. A LRU Cache in 10 Lines of Java
[2]. TinyLFU: A Highly Efficient Cache Admission Policy
[3]. Approximating Data with the Count-Min Data Structure
[4]. On Window TinyLFU
[5]. Design Of A Modern Cache
[6]. go-tinylfu

CONTENTS