LRU算法的应用

13.LRU算法的应用

题目

关于用户信息的需求

假定在一个复杂的系统中，需要抽象出一个用户系统，提供给其他子系统使用，该如何实现。子系统对用户信息的查询频率很高，要注意性能问题。

用户信息是存储在数据库里的，但是对于查询频率高的数据，不能每一次请求时都去查询数据库。

思路

哈希表

使用以用户id为key，用户信息为value的哈希表，作为缓存以提高性能。存在问题，如果只向哈希表中存储数据，而不移除数据的话，可能内存会溢出，导致服务器宕机。

LRU全称Least Recently Used，最近最少未使用，是一种内存管理算法，该算法最早应用于LinuxOS。

该算法，基于一种假设：长期不使用的数据，在未来使用的概率也不大。因此，当内存数据占内存达到一定阈值时，要移除最近最少使用的数据。

该算法，还基于一种，特殊的数据结构，哈希链表。

哈希表是由若干个K-V键值对的Node节点组成的。在此逻辑基础上，每个节点，加一个pre前驱和一个next后驱，将这些Node连接起来，想链表一样。

假设，使用哈希链表存储用户信息，001-User1<->002-User2<->003-User3<->004-User4。每次，对于未缓存的用户数据，都使用尾加法，加到链表的右边，对于使用到的链表中的数据，也将该节点移动到链表的末尾。这样链表的左侧，就是最近最少未使用的数据，移除就好。

代码

public class LRUCache {
    private Node head;
    private Node end;
    private int limit;


    private HashMap<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null)
            return null;
        refreshNode(node);
        return node.value;
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            if (hashMap.size() >= limit) {
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        } else {
            //如果key存在，则刷新key-value
            node.value = value;
            refreshNode(node);
        }
    }

    public void remove(String key){
        Node node = hashMap.get(key);
        refreshNode(node);
        hashMap.remove(key);
    }

    /**
     * 刷新被访问节点的位置
     *
     * @param node 被访问节点
     */
    private void refreshNode(Node node) {
        if (node == end)
            return;
        //移除节点
        removeNode(node);
        //重新插入节点
        addNode(node);
    }

    /**
     * 删除节点
     *
     * @param node 要删除的节点
     * @return
     */
    private String removeNode(Node node) {
        if (node == head && node == end) {
            //移除唯一节点
            head = null;
            end = null;
        } else if (node == end) {
            //移除尾结点
            end = end.pre;
            end.next = null;
        } else if (node == head) {
            //移除头节点
            head = head.next;
            head.pre = null;
        } else {
            //移除中间节点
            node.pre.next = node.next;//将当前节点的下一个，赋值给上一节点的下一个
            node.next.pre = node.pre;//将当前节点的前一个，赋值给上一节点的前一个
        }
        return node.key;
    }

    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null)
            head = node;
    }

    private static class Node {
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public Node pre;
        public Node next;
        public String key;
        public String value;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001","用户1信息");
        lruCache.put("002","用户2信息");
        lruCache.put("003","用户3信息");
        lruCache.put("004","用户4信息");
        lruCache.put("005","用户5信息");
        lruCache.get("002");
        lruCache.put("004","new用户4信息");
        lruCache.put("006","用户6信息");
        System.out.println(lruCache.get("001"));
        System.out.println(lruCache.get("006"));
    }

}

注意，该代码本质还是使用HashMap作为缓存，且如果多个线程共享一个LRUCache对象时，访问这些方法，是线程不安全的。这是可以给这些方法手动加锁，或者使用ConcurrentHashMap类占存数据。本demo中的，存储的用户使用String类型表示，只是为了演示LRU算法，实际使用中，可以使用泛型。

对于这种缓存高频访问的数据，一般都是用Redis这种NoSQL的内存数据库，其底层也实现了类似LRU的回收算法。该笔记只是展示LRU算法。而且使用缓存数据库，就一定存在一个数据一致性的问题，就是关系型数据库中存储的数据和缓存中的数据如何保持一致？后续有机会分享。

只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。