LRU Cache实现原理

原创
2021/01/24 13:00
阅读数 2.2K

一、简介

        LRU Cache是我们在平常使用非常多的一种缓存,在构建高并发服务时,Redis往往由于存在网络消耗而无法达到性能要求,这个时候常用数据的本地缓存就显得尤为重要。在项目中,我们常用的本地缓存工具就是guava Cache,不过其实现原理更为复杂,本文主要讲解常用的LRU Cache的实现原理,并且讲解如何在高并发条件下实现一个LRU Cache。

二、LRU Cache实现原理

        说到LRU,它的字面意思是最近最少使用,也就是说,在数据处理上,最近最少使用的数据将会被淘汰。由此可以看出,LRU具有如下几个特性:

  • 在访问数据时,如果一个数据先前被访问过,那么再次访问时,就能够实现对数据的快速获取;
  • 如果数据量达到了限制的大小,那么最先淘汰的就是最远未被访问的数据。

        由此我们可以总结LRU Cache的几个接口:

  • 创建一个LRU Cache,并且需要指定大小,比如LruCache(size)
  • 快速获取指定数据,比如T get(key)
  • 快速插入数据,比如void put(key, value)
  • 最近最少使用的数据将会被优先淘汰;

        对于一个类而言,其必然是高内聚,低耦合的,根据上面的接口说明,我们首先会想到,如果要快速获取一个数据,那么用Map是比较合适的,而如果需要最近最少使用的数据优先被淘汰,那么用List是比较合适的,在使用List的时候,如果一个数据被访问过,那么就将这个数据放到队列头部,当List达到指定大小时,就将队列尾部的数据淘汰掉。其实主要问题就是如何组织这个数据结构的问题,如果只是单纯的使用一个Map和一个List,那么在获取一个数据的时候,虽然可以通过Map快速获取,但是却需要遍历List,以找到目标元素,这在数据量比较大的时候,性能还是非常低的。如果能够在通过Map获取数据的时候,就知道该元素在List中的位置,这样就可以不用遍历List了,那么如何实现呢?首先我们需要明确的是,这里的List必然使用的是LinkedList,要不然就不容易实现快速的插入和删除了,既然是LinkedList,每个元素都是用一个Node包装的,而Node中则存有前一个元素和后一个元素的指针,如果Map的值指向的是这个Node,那么我们就可以实现在O(1)的复杂度内获取这个元素,并且把这个元素放到队列头部。如下是其数据结构:

        根据上面的介绍,我们可以画出get(key)put(key, value)的流程图如下:

        据此,我们可以实现LRU Cache代码如下:

import java.util.HashMap;
import java.util.Map;

public class LruCache<K, V> {
  private int size;
  private Map<K, Node<K, V>> map;
  private Node<K, V> head;
  private Node<K, V> tail;

  public LruCache(int size) {
    this.size = size;
    this.map = new HashMap<>();
    this.head = new Node<>();
    this.tail = new Node<>();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  public V get(K key) {
    Node<K, V> node = map.get(key);
    if (node == null) {
      return null;
    }

    removeNode(node);
    insertHead(node);
    return node.val;
  }

  public void put(K key, V val) {
    Node<K, V> node = map.get(key);
    if (null != node) {
      removeNode(node);
    } else {
      node = new Node<>();
      node.key = key;
    }

    node.val = val;
    if (map.size() == this.size) {
      map.remove(this.tail.prev.key);
      removeNode(this.tail.prev);
    }

    insertHead(node);
  }

  private void insertHead(Node<K, V> node) {
    this.head.next.prev = node;
    node.next = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    map.put(node.key, node);
  }

  private void removeNode(Node<K, V> node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.next = null;
    node.prev = null;
    map.remove(node.key);
  }

  private static final class Node<K, V> {
    private K key;
    private V val;
    private Node<K, V> prev;
    private Node<K, V> next;
  }
}

        由此我们就实现了一个可过期的LRU Cache,可以看到,其每一步操作都是在O(1)复杂度内实现的。

三丶高并发Lru Cache

        上面的LRU Cache虽然实现了基本的功能,但是在我们的实际环境中,Cache是作为一个公共的属性供多个线程读取的,这就存在一个问题:高并发情况下,如何既保证效率,又保证数据的一致性。很明显,如果单纯的在get()put()方法上加synchronized是无法实现高并发的,这里其实我们可以借鉴ConcurrentHashMap,对数据进行分段,如果每个段的数据比较均匀,并且段的数量足够多,那么在每个段里再加同步,其实效率也是非常高的。这里分段有两种方式:

  • 由于key会计算一个整型的hash值,因而我们可以将整型从零到Integer.MAX_VALUE进行分段,比如分成16等份,而每个段里则都是一个LruCache,我们只需要对这个LruCache加锁即可;
  • 直接利用hash算法,将key对分片数量取余,获取其所在的分片,然后再在该分片对应的LruCache中获取数据。

        从效率上讲,分片之后的LRU Cache冲突率是比较低的,整体上效率还是非常高的。

四、小结

        本文首先讲了如何实现一个LRU Cache,着重讲解了LRU Cache的数据结构,以及其所提供的接口的实现原理。然后讲解了如何实现一个高并发的LRU Cache。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部