欢迎做客泥烟の新站

本文链接

👉对QD-LP-FIFO的理解和简易代码实现 - 泥烟のMkdocs

对QD-LP-FIFO的理解和简易代码实现

我的理解:

LRU算法的核心思想是“最近最少使用”, 它假设最近被访问的数据在未来也很可能被访问。但是, LRU算法在每次数据被访问时都会更新数据的“最近性”, 这可能会导致一些其实并不那么“热门”的数据被错误地认为是“热门”的, 因为它们恰好在短时间内被频繁访问。

而FIFO算法加上懒惰提升（Lazy Promotion, LP的策略, 则是只在数据即将被移出缓存时, 才判断它是否真的“热门”。如果一个数据在缓存中时被多次请求, 这表明它很可能是一个真正受欢迎的对象, 那么在它即将被移出缓存的时候, FIFO算法会把它重新放回缓存的前面, 从而保留下来。这样的策略可以更准确地识别出那些真正需要被快速访问的数据, 而不是仅仅因为短时间内的频繁访问就被错误地保留在缓存中的数据。

懒惰提升的FIFO算法就像是在说：“我们不急于判断一个数据是否热门, 只有当它快要被移出缓存时, 我们才看看它是不是真的有很多人在用。如果是, 那就留下来；如果不是, 那就让出位置给可能更需要的数据。”这样的方法可以更有效地利用缓存空间, 存储那些真正被频繁使用的热门数据。

再加上快速降级（Quick Demotion, QD）,利用QD技术通过一个小的试探性FIFO队列来快速识别并驱逐不受欢迎的对象。这个队列作为过滤器, 使得那些在插入后不久没有被请求的对象可以快速被移除, 从而为更有可能被重复请求的对象腾出空间。

简化的QD-LP-FIFO缓存算法实现(java版)

QDLPFIFOCache.java

import java.util.*;


class QDLPFIFOCache {
	// 缓存条目类, 存储键、值和访问标记
    static class CacheEntry {
        int key;
        Object value;
        boolean accessed;

        public CacheEntry(int key, Object value) {
            this.key = key;
            this.value = value;
            this.accessed = false; // 默认未访问
        }
    }
	// 缓存映射, 存储键值对
    private Map<Integer, CacheEntry> cacheMap;
    // 试探性FIFO队列, 存储最近插入的键
    private Queue<Integer> probationaryQueue;
    // 幽灵集合, 存储被驱逐的键
    private Set<Integer> ghostSet;
    // 缓存的容量
    private int capacity;

    //  构造函数, 初始化缓存容量、映射、队列和集合
    public QDLPFIFOCache(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>();
        this.probationaryQueue = new LinkedList<>();
        this.ghostSet = new HashSet<>();
    }

    // 获取缓存项的方法, 如果键存在, 则将其标记为已访问并提升它
    public Object get(int key) {
        CacheEntry entry = cacheMap.get(key);
        if (entry != null) {
            entry.accessed = true; 	// 标记为已访问
            promote(entry.key);    	// 进行提升操作
            return entry.value;     // 返回值
        }
        return null;				// 如果键不存在, 返回null
    }

    // 向缓存中添加或更新数据的方法
    public void put(int key, Object value) {
        CacheEntry newEntry = new CacheEntry(key, value);
        if (cacheMap.containsKey(key)) {
            CacheEntry entry = cacheMap.get(key);
            entry.value = value;    // 更新值
            promote(key);          	// 进行提升操作
        } else {
            if (cacheMap.size() >= capacity) {
                evict();           	// 驱逐最老的未访问对象
            }
            cacheMap.put(key, newEntry); 	// 添加新项
            probationaryQueue.offer(key); 	// 将键添加到试探性队列
        }
    }

    // 驱逐操作, 移除并返回试探性队列的头部元素
    private void evict() {
        Integer keyToEvict = probationaryQueue.poll();
        if (keyToEvict != null && cacheMap.containsKey(keyToEvict)) {
            cacheMap.remove(keyToEvict); // 从缓存映射中移除
            ghostSet.add(keyToEvict);     // 添加到幽灵集合
        }
    }

    // 提升操作, 如果键在试探性队列中, 则将其移除, 表示它被提升
    private void promote(int key) {
        if (probationaryQueue.contains(key)) {
        	// 模拟懒惰提升, 这里不将key放回probationaryQueue, 而是直接移除
            probationaryQueue.remove(key);
        }
        // 如果ghostSet包含key, 移除它以反映快速降级, 表示它不再处于被驱逐状态
        ghostSet.remove(key);
    }

    // 打印当前缓存状态的方法
    public void printCacheState() {
        System.out.println(cacheMap);
    }
  
}

QDLPFIFOCacheTest.java

import java.util.*;

public class QDLPFIFOCacheTest {
    public static void main(String[] args) {
        // 创建容量为100的QDLPFIFOCache实例
        QDLPFIFOCache cache = new QDLPFIFOCache(100);

        // 模拟插入大量数据
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            int key = random.nextInt(500) + 1; // 随机生成1到500之间的键
            cache.put(key, "Value " + key);
        }

        // 随机获取数据并打印
        for (int i = 0; i < 10; i++) { // 假设随机获取10次数据
            int keyToGet = random.nextInt(500) + 1; // 随机生成1到500之间的键
            Object value = cache.get(keyToGet); // 获取对应的值
            System.out.println("Value for Key " + keyToGet + ": " + value);
        }

        // 打印当前缓存状态
        System.out.println("Current Cache State:");
        cache.printCacheState();

        // 验证频繁访问的数据是否被保留
        System.out.println("Frequently accessed data verification:");
        for (int key = 1; key <= 10; key++) {
            Object value = cache.get(key); // 获取频繁访问的数据
            System.out.println("Value for Key " + key + ": " + value);
        }
    }
}

输出

Value for Key 61: null
Value for Key 110: null
Value for Key 184: Value 184
Value for Key 27: Value 27
Value for Key 108: null
Value for Key 345: Value 345
Value for Key 367: null
Value for Key 39: null
Value for Key 153: null
Value for Key 463: null
Current Cache State:
{1=QDLPFIFOCache$CacheEntry@6d06d69c,2=QDLPFIFOCache$CacheEntry@7852e922, 259=QDLPFIFOCache$CacheEntry@4e25154f,266=QDLPFIFOCache$CacheEntry@70dea4e, 271=QDLPFIFOCache$CacheEntry@5c647e05,277=QDLPFIFOCache$CacheEntry@33909752, 278=QDLPFIFOCache$CacheEntry@55f96302,26=QDLPFIFOCache$CacheEntry@3d4eac69, 27=QDLPFIFOCache$CacheEntry@42a57993,285=QDLPFIFOCache$CacheEntry@75b84c92, 31=QDLPFIFOCache$CacheEntry@6bc7c054,291=QDLPFIFOCache$CacheEntry@232204a1, 292=QDLPFIFOCache$CacheEntry@4aa298b7,36=QDLPFIFOCache$CacheEntry@7d4991ad, 309=QDLPFIFOCache$CacheEntry@28d93b30,53=QDLPFIFOCache$CacheEntry@1b6d3586, 312=QDLPFIFOCache$CacheEntry@4554617c,313=QDLPFIFOCache$CacheEntry@74a14482, 318=QDLPFIFOCache$CacheEntry@1540e19d,66=QDLPFIFOCache$CacheEntry@677327b6, 70=QDLPFIFOCache$CacheEntry@14ae5a5,72=QDLPFIFOCache$CacheEntry@7f31245a, 74=QDLPFIFOCache$CacheEntry@6d6f6e28,76=QDLPFIFOCache$CacheEntry@135fbaa4, 332=QDLPFIFOCache$CacheEntry@45ee12a7,337=QDLPFIFOCache$CacheEntry@330bedb4, 82=QDLPFIFOCache$CacheEntry@2503dbd3,85=QDLPFIFOCache$CacheEntry@4b67cf4d, 86=QDLPFIFOCache$CacheEntry@7ea987ac,343=QDLPFIFOCache$CacheEntry@12a3a380, 345=QDLPFIFOCache$CacheEntry@29453f44,98=QDLPFIFOCache$CacheEntry@5cad8086, 103=QDLPFIFOCache$CacheEntry@6e0be858,361=QDLPFIFOCache$CacheEntry@61bbe9ba, 107=QDLPFIFOCache$CacheEntry@610455d6,364=QDLPFIFOCache$CacheEntry@511d50c0, 109=QDLPFIFOCache$CacheEntry@60e53b93,366=QDLPFIFOCache$CacheEntry@5e2de80c, 368=QDLPFIFOCache$CacheEntry@1d44bcfa,115=QDLPFIFOCache$CacheEntry@266474c2, 373=QDLPFIFOCache$CacheEntry@6f94fa3e,374=QDLPFIFOCache$CacheEntry@5e481248, 118=QDLPFIFOCache$CacheEntry@66d3c617,376=QDLPFIFOCache$CacheEntry@63947c6b, 377=QDLPFIFOCache$CacheEntry@2b193f2d,122=QDLPFIFOCache$CacheEntry@355da254, 384=QDLPFIFOCache$CacheEntry@4dc63996,132=QDLPFIFOCache$CacheEntry@d716361, 394=QDLPFIFOCache$CacheEntry@6ff3c5b5,139=QDLPFIFOCache$CacheEntry@3764951d, 146=QDLPFIFOCache$CacheEntry@4b1210ee,402=QDLPFIFOCache$CacheEntry@4d7e1886, 403=QDLPFIFOCache$CacheEntry@3cd1a2f1,404=QDLPFIFOCache$CacheEntry@2f0e140b, 408=QDLPFIFOCache$CacheEntry@7440e464,409=QDLPFIFOCache$CacheEntry@49476842, 156=QDLPFIFOCache$CacheEntry@78308db1,413=QDLPFIFOCache$CacheEntry@27c170f0, 414=QDLPFIFOCache$CacheEntry@5451c3a8,160=QDLPFIFOCache$CacheEntry@2626b418, 418=QDLPFIFOCache$CacheEntry@5a07e868,164=QDLPFIFOCache$CacheEntry@76ed5528, 422=QDLPFIFOCache$CacheEntry@2c7b84de,170=QDLPFIFOCache$CacheEntry@3fee733d, 426=QDLPFIFOCache$CacheEntry@5acf9800,428=QDLPFIFOCache$CacheEntry@4617c264, 172=QDLPFIFOCache$CacheEntry@36baf30c,430=QDLPFIFOCache$CacheEntry@7a81197d, 177=QDLPFIFOCache$CacheEntry@5ca881b5,179=QDLPFIFOCache$CacheEntry@24d46ca6, 181=QDLPFIFOCache$CacheEntry@4517d9a3,184=QDLPFIFOCache$CacheEntry@372f7a8d, 441=QDLPFIFOCache$CacheEntry@2f92e0f4,443=QDLPFIFOCache$CacheEntry@28a418fc, 188=QDLPFIFOCache$CacheEntry@5305068a,190=QDLPFIFOCache$CacheEntry@1f32e575, 447=QDLPFIFOCache$CacheEntry@279f2327,448=QDLPFIFOCache$CacheEntry@2ff4acd0, 196=QDLPFIFOCache$CacheEntry@54bedef2,455=QDLPFIFOCache$CacheEntry@5caf905d, 200=QDLPFIFOCache$CacheEntry@27716f4,203=QDLPFIFOCache$CacheEntry@8efb846, 459=QDLPFIFOCache$CacheEntry@2a84aee7,460=QDLPFIFOCache$CacheEntry@a09ee92, 204=QDLPFIFOCache$CacheEntry@30f39991,209=QDLPFIFOCache$CacheEntry@452b3a41, 469=QDLPFIFOCache$CacheEntry@4a574795,481=QDLPFIFOCache$CacheEntry@f6f4d33, 482=QDLPFIFOCache$CacheEntry@23fc625e,483=QDLPFIFOCache$CacheEntry@3f99bd52, 231=QDLPFIFOCache$CacheEntry@4f023edb,232=QDLPFIFOCache$CacheEntry@3a71f4dd, 233=QDLPFIFOCache$CacheEntry@7adf9f5f,489=QDLPFIFOCache$CacheEntry@85ede7b, 494=QDLPFIFOCache$CacheEntry@5674cd4d,239=QDLPFIFOCache$CacheEntry@63961c42, 245=QDLPFIFOCache$CacheEntry@65b54208,247=QDLPFIFOCache$CacheEntry@1be6f5c3, 250=QDLPFIFOCache$CacheEntry@6b884d57,252=QDLPFIFOCache$CacheEntry@38af3868}
Frequently accessed data verification:
Value for Key 1: Value 1
Value for Key 2: Value 2
Value for Key 3: null
Value for Key 4: null
Value for Key 5: null
Value for Key 6: null
Value for Key 7: null
Value for Key 8: null
Value for Key 9: null
Value for Key 10: null

从输出可以看出以下几点分析：

1.随机获取数据的部分：

• 随机获取的数据有些是存在于缓存中的（例如Key 27、Key 345）, 返回了相应的值。

• 有些随机获取的数据则是不存在于缓存中的（例如Key 61、Key 110）, 返回了null。

2.当前缓存状态的部分：

• 缓存状态输出了缓存中的部分键值对, 可以看到缓存中保存了多个键值对, 但并非全部。

• 这符合QDLPFIFOCache的特点, 因为当容量达到上限时, 会根据最近插入的数据进行驱逐, 所以缓存中的数据是不断变化的。

3.频繁访问的数据验证部分：

• 验证了一些频繁访问的数据, 例如Key 1和Key 2, 可以看到它们确实被保留在缓存中, 并且可以被正确获取到值。

• 其他频繁访问的数据（例如Key 3到Key 10）可能由于缓存的容量限制或者在驱逐过程中被移除, 所以返回了null。

输出结果符合QDLPFIFOCache的特点，即最近插入的数据有更高的保留优先级（懒惰提升），并且在缓存达到容量上限时会进行快速降级，驱逐最旧的未访问数据。