算法积累：LRU 算法

算法：LRU 算法

1. 什么是 LRU

LRU：Least Recently Used-最近最少使用算法，是一种内存数据淘汰策略。常用作当内存不足时，需要淘汰清理掉最近最少使用的数据。LRU 常用于缓存系统的淘汰策略。

2. LRU 的应用场景

在缓存系统中，一旦缓存的数据量过大，就会对应用节点内存的消耗就非常严重，而且对缓存数据的检索也会变得越来困难。那么就会存在以下问题：

• 内存消耗变大
• 检索效率变低

对于内存消耗变大，我们可以通过限制缓存的大小来缓解大量的缓存数据对内存造成的压力；对于数据检索效率的问题，我们可以将热点数据放在最前面，将长时间未使用或使用频率很小的数据放在缓存的最后面，即：对数据进行热度排序。

不论是内存的消耗还是检索的效率的问题均可以通过 LRU 来解决。

3. 手写实现 LRU

3-1. 使用链表结构实现 LRU

package com.kyrie.utils.dataStructure;

import java.util.LinkedList;
/***
 * @project: interface-common
 * @package: com.kyrie.utils.dataStructure
 * @description: 使用链表实现LRU算法
 * @author: kyrie
 * @mail: 18654169290@163.com
 * @createDate: 2021-04-04 13:51
 */
public class LRUByLinkedList {
    // 限制缓存大小，解决内存消耗大的问题
    private static final int MAX_CACHE_SIZE = 10;
    // 使用链表结构存储缓存
    private static final LinkedList<LRUCacheData> cacheData = new LinkedList<>();
    /**
     * 应用获取缓存使用
     * @param id 缓存ID
     */
    public LRUCacheData get(String id) {
        if (null == id || "".equals(id))
            throw new NullPointerException("CacheId is not be Null");
        LRUCacheData data = null;
        synchronized (cacheData) {
            // 遍历链表，查找缓存数据
            for (LRUCacheData item : cacheData) {
                if (id.equals(item.getCacheId())) {
                    data = item;
                    // 在链表中移除该缓存数据，再将其添加到表头位置
                    cacheData.remove(item);
                    cacheData.addFirst(data);
                    return data;
                }
            }
        }
        if (null == data)
            data = getDataFromDB(id);
        return data;
    }

    /**
     * 缓存不存在时，从DB获取数据并设置缓存头位置
     * @param id 数据ID
     */
    private LRUCacheData getDataFromDB(String id) {
        // get data from DB code here
        LRUCacheData data = new LRUCacheData();
        // put data in cache
        push(data);
        return data;
    }

    /**
     * 将缓存放在链表头节点，并判断缓存大小是否达到最大值，达到则清理尾节点数据
     * @param lruCacheData 缓存数据
     */
    private void push(LRUCacheData lruCacheData) {
        synchronized (cacheData) {
            if (cacheData.size() == MAX_CACHE_SIZE) {
                cacheData.removeLast();
            }
            cacheData.addFirst(lruCacheData);
        }
    }
}

上面已经通过 LinkedList 链表实现了简单的 LRU 算法，通过限制链表的长度来限制缓存的大小；通过将热点数据移动到链表表头实现热点数据的快速检索，自动清理链表尾部的数据。但仍存在这一些问题：

• 命中率问题：每次访问数据都需要从链表头开始遍历，这对于热点数据的访问效果很好（热点数据都聚集在链表头部附近，很快就能遍历到结果），可一旦数据分散较为均匀时，访问命中率急剧下降
• 性能损耗问题：每次命中数据后，都需要将数据重新移动至链表头部，存在相当大的性能损耗；
• 缓存污染问题：并非所有数据有必要缓存（可能整个应用运行过程中某些数据被访问的次数很少），但是算法实现过程没办法对热点数据（频繁访问的数据，这才是有价值进行缓存的）进行区分，使得缓存队列贬值