LRU和LFU缓存置换算法

作者: 康凯森

日期: 2016-05-05

分类: 算法

为什么需要Cache

  • 为了解决俩个存储介质之间的速度不匹配，比如CPU和内存，比如内存和磁盘，比如本地和服务端。
  • 依据程序访问的局部性原理，近期访问的数据，在将来很有可能会被访问

Cache是什么

可以简单认为是一个HashMap，是一个key-value 结构，用来加速访问。

Cache无处不在

缓存的种类：本地服务器缓存、网页缓存、硬盘缓存、一级高速缓存、二级高速缓存等

常用的Cache服务器

  • Memcache
  • Redis

为什么需要 Cache

因为Cache在内存中，所以存储效率高

为什么不全放在 Cache中

  • 内存的数据断电就会丢失
  • Cache比硬盘贵

为什么Cache需要置换

Cache工作原理要求它尽量保存最新数据，但是Cache一般大小有限，当Cache容量达到上限时，就会产生Cache替换的问题。最理想的情况是置换出未来短期内不会被再次访问的数据，但是我们无法预知未来，所以只能从数据在过去的访问情况中寻找规律进行置换。

LFU Cache置换算法

Least Frequently Used algorithm LFU是首先淘汰一定时期内被访问次数最少的页!

这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。

20150420105345_48639.png-56.1kB

代码如下：

/**
 * Created by kangkaisen on 16/5/4.
 */
import java.util.*;

public class LFUCache {
    private static final int DEFAULT_MAX_SIZE = 3;
    private int capacity = DEFAULT_MAX_SIZE;
    //保存缓存的访问频率和时间
    private final Map<Integer, HitRate> cache = new HashMap<Integer, HitRate>();
    //保存缓存的KV
    private final Map<Integer, Integer> KV = new HashMap<Integer, Integer>();

    // @param capacity, an integer
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        Integer v = KV.get(key);
        if (v == null) {
            if (cache.size() == capacity) {
                Integer k = getKickedKey();
                KV.remove(k);
                cache.remove(k);
            }
            cache.put(key, new HitRate(key, 1, System.nanoTime()));
        } else { //若是key相同只增加频率,更新时间,并不进行置换
            HitRate hitRate = cache.get(key);
            hitRate.hitCount += 1;
            hitRate.lastTime = System.nanoTime();
        }
        KV.put(key, value);
    }

    public int get(int key) {
        Integer v = KV.get(key);
        if (v != null) {
            HitRate hitRate = cache.get(key);
            hitRate.hitCount += 1;
            hitRate.lastTime = System.nanoTime();
            return v;
        }
        return -1;
    }
    // @return 要被置换的key
    private Integer getKickedKey() {
        HitRate min = Collections.min(cache.values());
        return min.key;
    }

    class HitRate implements Comparable<HitRate> {
        Integer key;
        Integer hitCount; // 命中次数
        Long lastTime; // 上次命中时间

        public HitRate(Integer key, Integer hitCount, Long lastTime) {
            this.key = key;
            this.hitCount = hitCount;
            this.lastTime = lastTime;
        }

        public int compareTo(HitRate o) {
            int hr = hitCount.compareTo(o.hitCount);
            return hr != 0 ? hr : lastTime.compareTo(o.lastTime);
        }
    }

    public static void main(String[] as) throws Exception {
        LFUCache cache = new LFUCache(3);
        cache.set(2, 2);
        cache.set(1, 1);

        System.out.println(cache.get(2));
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));

        cache.set(3, 3);
        cache.set(4, 4);

        System.out.println(cache.get(3));
        System.out.println(cache.get(2));
        System.out.println(cache.get(1));
        System.out.println(cache.get(4));

    }
}

LRU Cache置换算法

Least Recently Used algorithm LRU是首先淘汰最长时间未被使用的页面!

这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起来比较容易。 屏幕快照 2016-05-05 上午12.33.51.png-123.4kB

代码如下：

import java.util.HashMap;

/**
 * Created by kangkaisen on 16/5/5.
 */

//实现起来比较简单. 维护一个链表,每次数据新添加或者有访问时移动到链表尾,
//每次淘汰数据则是淘汰链表头部的数据.
//也就是最近最少访问的数据在链表头部,最近刚访问的数据在链表尾部    

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);
    // @param capacity, an integer
    public LRUCache(int capacity) {
        // write your code here
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    // @return an integer
    public int get(int key) {
        // write your code here
        if( !hs.containsKey(key)) {
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);

        return hs.get(key).value;


    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // write your code here
        if( get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hs.put(key, insert);
        move_to_tail(insert);
    }

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }

    public static void main(String[] as) throws Exception {
        LRUCache cache = new LRUCache(3);
        cache.set(2, 2);
        cache.set(1, 1);

        System.out.println(cache.get(2));
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));

        cache.set(3, 3);
        cache.set(4, 4);

        System.out.println(cache.get(3));
        System.out.println(cache.get(2));
        System.out.println(cache.get(1));
        System.out.println(cache.get(4));

    }
}

参考资料

九章算法

缓存中的算法-RAND算法,FIFO算法,LFU算法,LRU算法,OPT算法

缓存淘汰算法系列之2——LFU类

缓存淘汰算法 —— LFU-Aging（Java实现） 该算法不正确

LRU和LFU的区别

《OLAP 性能优化指南》欢迎 Star&共建

《OLAP 性能优化指南》

欢迎关注微信公众号

康凯森