前言

之前也用過一些快取中間件，框架，也想著自己是不是也能用Java寫一個出來，于是就有了這個想法，打算在寫的程序中同步進行總結，

原始碼：weloe/Java-Distributed-Cache (github.com)

本篇代碼：

Java-Distributed-Cache/src/main/java/com/weloe/cache/outstrategy at master · weloe/Java-Distributed-Cache (github.com)

Java-Distributed-Cache/src/test/java/com/weloe/cache/outstrategy at master · weloe/Java-Distributed-Cache (github.com)

我們可以想想幾個問題，什么是快取？為什么需要快取？

什么是快取？將之前請求的資料暫存，遇到同樣的請求/狀況直接回傳，這就是快取，

為什么需要？同樣的情況下，直接回傳資料，無需其他操作，能加快服務器反應速度，減輕服務器壓力，

那么快取怎么存？簡單的快取為鍵值對，可以用Map存盤，這就完了嗎？如果我們一直往Map中存盤資料，占用的記憶體會越來越大，這時候怎么辦？

這就是本篇需要解決的問題，

要使用快取，就必然會面臨到快取使用空間達到上限的問題，這個時候就需要從已有的快取資料中淘汰一部分去維持快取的可用性，

LRU

力扣上的相關題 https://leetcode.cn/problems/lru-cache/

LRU，快取淘汰演算法，最近最少使用(Least Recently Used)，就是一種選擇淘汰資料的策略

原理：為最近被訪問的資料進行快取，淘汰不常被訪問的資料，

也就是說我們認為最近使用過的資料應該是有用的，很久都沒用過的資料應該是無用的，記憶體滿了就優先刪那些很久沒用過的資料，

舉一個我們最常見的例子，手機可用把軟體放到后臺運行，比如我們先后打開了日歷，設定，鬧鐘，后臺的順序是 日歷->設定->鬧鐘，如果這臺手機只能打開三個應用，再打開 應用商城 ，后臺的順序會變成 應用商城->日歷->設定，

從這個案例可以知道LRU的主要兩個操作的具體思路，一個資料結構存值，一個資料結構存盤后臺順序，

快取一般以key,value形式存盤，因此選擇map存盤，而存盤順序的資料結構由于要不斷改動節點順序，選擇雙向鏈表

public class LRUCache<K, V> implements CacheStrategy<K, V> {
    private Map<K, V> map;
    private int capacity;
    private Deque<K> queue;
    private Callback callback;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap();
        this.queue = new LinkedList();
    }
}

put(key,value)

如果關鍵字 key 已經存在，則變更其資料值 value ；如果不存在，則向快取中插入該組 key-value ，如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字，

   	public void put(int key, int value) {
        if (map.containsKey(key)) {
            queue.remove(key);
        }
        queue.addFirst(key);
        map.put(key, value);

        // 快取達到上限
        if (queue.size() > capacity) {

            // 移除
            K last = queue.removeLast();
            V removeValue = https://www.cnblogs.com/weloe/archive/2023/01/13/map.remove(last);

            // 回呼
            if (callback != null) {
                callback.callback(last, removeValue);
            }
        }
        return value;

    }

get(key)

如果關鍵字 key 存在于快取中，則回傳關鍵字的值，否則回傳 -1

    public V get(K key) {
        // 如果已經快取過該資料
        if (map.containsKey(key)) {
            queue.remove(key);
            queue.addFirst(key);
            return map.get(key);
        }
        return null;
    }

弊端，容易出現快取污染問題

（k1,v1) (k2,v2)，(k3,v3)，(k4,v4)

(k2,v2),(k4,v4),(k1,v1),(k3,v3)

LRU-K

LRU-K演算法是對LRU演算法的改進，將原先進入快取佇列的評判標準從訪問一次改為訪問K次，

LRU-K演算法有兩個佇列，一個是快取佇列，一個是資料訪問歷史佇列，當訪問一個資料時，首先先在訪問歷史佇列中累加訪問次數，當歷史訪問記錄超過K次后，才將資料快取至快取佇列，從而避免快取佇列被污染，同時訪問歷史佇列中的資料可以按照LRU的規則進行淘汰，具體如下：

public class LRUKCache<K, V> extends LRUCache<K, V> {

    // 進入快取佇列的評判標準
    private int putStandard;

    // 訪問資料歷史記錄
    private LRUCache<Object, Integer> historyList;

    public LRUKCache(int cacheSize, int historyCapacity, int putStandard) {
        super(cacheSize);
        this.putStandard = putStandard;
        this.historyList = new LRUCache(historyCapacity);
    }


    @Override
    public V get(K key) {
        // 記錄資料訪問次數
        Integer historyCount = historyList.get(key);
        historyCount = historyCount == null ? 0 : historyCount;
        historyList.put(key, ++historyCount);
        return super.get(key);
    }

    @Override
    public V put(K key, V value) {
        if (value =https://www.cnblogs.com/weloe/archive/2023/01/13/= null) {
            return null;
        }
        // 如果已經在快取里則直接回傳
        if (super.get(key) != null) {
            return super.put(key, value);
        }
        // 如果資料歷史訪問次數達到上限，則加入快取
        Integer historyCount = historyList.get(key);
        historyCount = (historyCount == null) ? 0 : historyCount;
        if (removeCache(historyCount)) {
            // 移除歷史訪問記錄，加入快取
            historyList.remove(key);
            return super.put(key, value);
        }

        return value;
    }

    private boolean removeCache(Integer historyCount) {
        return historyCount >= putStandard;
    }

    public void setPutStandard(int putStandard) {
        this.putStandard = putStandard;
    }

    @Override
    public void setCallback(Callback callback) {
        super.setCallback(callback);
    }

    public void setHistoryListCallback(Callback callback) {
        historyList.setCallback((Callback) callback);
    }

}

LRU-K能降低快取污染發生的概率，但是需要額外記錄物件訪問次數，記憶體消耗較大，

測驗

class LRUCacheTest {

    @Test
    void lru(){
        CacheStrategy<Integer, Integer> lruCache = new LRUCache<>(5);
        lruCache.setCallback((integer, integer2) -> System.out.println("淘汰"+integer+"="+integer2));
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        lruCache.put(6,6);
        List list = lruCache.list();
        System.out.println(list);
    }

}

淘汰1=1
[2=2, 3=3, 4=4, 5=5, 6=6]

class LRUKCacheTest {

    @Test
    void lrukCacheTest() {
        LRUKCache<Integer, Integer> lrukCache = new LRUKCache<>(2,3,1);
        lrukCache.setHistoryListCallback((integer, integer2) -> System.out.println("記錄佇列淘汰"+integer+"="+integer2));
        lrukCache.setCallback((integer, integer2) -> System.out.println("快取淘汰"+integer+"="+integer2));
        lrukCache.get(1);
        lrukCache.get(1);
        lrukCache.get(1);
        lrukCache.get(2);
        lrukCache.get(2);
        lrukCache.get(2);
        lrukCache.get(3);
        lrukCache.get(3);
        lrukCache.get(3);
        lrukCache.get(4);
        lrukCache.get(4);
        lrukCache.get(4);
        lrukCache.put(1,2);
        lrukCache.put(2,2);
        lrukCache.put(3,2);
        lrukCache.put(4,2);
        List list = lrukCache.list();
        System.out.println(list);
    }
}

記錄佇列淘汰1=3
快取淘汰2=2
[3=2, 4=2]

標籤：其他

上一篇：學習筆記——Mybatis逆向工程MBG；MyBatis逆向工程MBG使用步驟

下一篇：aBiu的筆記匯總