System|缓存|Rethinking LRU

朝闻君

发布于 2021-11-22 10:48:47

8260

发布于 2021-11-22 10:48:47

文章被收录于专栏：用户9199536的专栏

LRU是常见的缓存淘汰策略，用于分布式系统的缓存、页表置换等场景。然而，经典的哈希链表实现事实上并不是很好的实现策略。

本文将从内存页、CPU缓存、分布式缓存等几个方面介绍它们所使用的LRU算法实现。

内存 - 时钟算法、工作集算法、2Q、Linux LRU
CPU - Tree-PLRU、 MRU、 QLRU
分布式 - Redis采样式LRU，Memcache分段式LRU

绝对LRU

时间戳排序

为每个缓存赋予时间戳，在访问时更新时间戳，使用优先队列按照时间戳排序，淘汰最小时间戳的缓存。这种算法时空的开销都很大。

哈希链表

哈希链表的关键在于，使用哈希映射链表节点，而不是用链表串联哈希入口。这是因为哈希扩容后原本的哈希映射全部打乱。

在查询时，我们简单地将链表节点从链表中删除，然后插入头节点即可，这样链表的尾结点必然是最早访问的缓存。看上去，不管是淘汰还是查询都是O(1)。

问题在于，插入头结点具备scalability么? 哈希链表最大的问题在于，将所有的读访问转换为对同一临界区的写访问，在多核下是完全没有可拓展性的！

绝对的LRU并不适合工程实践，一般工业界使用LRU的近似算法。思路在于: 我们并不一定要淘汰最早访问的缓存，只要淘汰相对最早访问的缓存即可。

内存页淘汰

Clock(NRU）

如同时钟一般，Clock将物理页环形存储，并在物理页维护reference bit(不能使用access bit，因为MMU对应虚拟页)，时钟的柄作为入口，当没有空物理页时，从柄开始查询。

reference bit为1(上个扫描周期中被访问) 清零access bit，前移表针
reference bit为0(上个扫描周期中未访问）淘汰，前移表针

某些优化会考虑物理页是否发生修改dirty bit，如果没有修改的话是可以不用刷回磁盘的，因此最适合淘汰。

显然，clock算法在读取时并不会导致竞争，只会修改本地的reference bit。

此外，clock算法还有一系列的变种，参考https://en.wikipedia.org/wiki/Page_replacement_algorithm#cite_note-9

工作集(Working Set)

工作集的意思是，进程在时间段（t - x, t)内使用的内存页集合，也有可能是(t,t+x)所访问的页集合，因此应该将它们尽可能保存在内存中。工作集的实现依赖于OS提供Page Aging的支持。

工作集时钟中断固定间隔发生，处理函数扫描内存页

access bit为1(此次tick中被访问) 记录上次使用时间为当前时间,并清零access bit
access bit为0(此次tick中未访问）Age = 当前时间 – 上次使用时间

若Age大于设置的x，则不在工作集，可以被淘汰。

工作集模型本身并不是页面置换算法，但是可以辅助页面置换算法作为淘汰的额外条件，例如WSclock算法就是基于Clock算法和Working Set算法而实现的。

2Q(Two Queue)

BlueStore的缓存策略，基于FIFO+LRU双队列实现，个人感觉不如Linux巧妙,这里的插入是实时+单向的。

FIFO链表

reference == 1，插入LRU表头
reference ==0，淘汰

LRU链表

reference== 1, 插入LRU表头；
reference==0，淘汰

感觉还是没法解决头结点竞争的问题，不知道最后用了啥优化。

Linux 双链表LRU

linux的想法是，一个链表存储活跃的页，另一个链表存储不活跃的页，通过active bit区分。插入表头的过程是惰性的，推迟到了淘汰时进行，因此避免了之前所说的并发读高度竞争。

转自兰新宇大佬

当我们想要从链表中移除页时(对inactive是进行淘汰，对active是补充inactive)

从链表末尾开始依次检测

活跃链表

reference == 1, 插入active表头；
reference==0，插入inactive表头。

不活跃链表

reference == 1，插入inactive表头
reference ==0，淘汰
如果在已经reference的情况下又进行了reference，插入active表头。

但是，虽然惰性的插入已经减少了很多插入表头，但是插入表头依然是竞争。因此Linux用了lru cache进行了batching，一次性处理多个插入表头以减少锁的获取。

同样地，因为采用了惰性，这种算法显然不是绝对的LRU，具体参照这篇文章

CPU缓存淘汰

对于硬件级别的缓存而言，每个缓存行的block数目固定且规模有限，因此不需要复杂机制也能判断，直接运用bit即可。硬件有很多LRU的近似实现。

CPU cache

Tree-PLRU

利用二叉树来确定LRU的位置，0表示左，1表示右。

在访问缓存的过程中，路径上的flag设置和查找方向相反(例如如果向左查找，那么设置成1)。

当miss时，二叉树根据flag查找到的block会被淘汰。

MRU(mostly)

实际上淘汰的是NRU, 每个block具备一个bit，访问block时该bit置0，其他block置1。当miss时，第一个bit为1的block会被淘汰。

QLRU(quad age)

MRU变种，每个block具备两个bit，代表年龄，初始为1, 0为LRU，3为MRU。当miss时，bit最小的block会被淘汰。Intel在PPT表示，给予初始时middle age能够有效帮助prefetch，使得新增加的数据不会立刻被淘汰。不过这货找不到论文，具体状态机没搞懂。

IPC Improvements

分布式缓存淘汰

Redis 采样式 LRU

实现位于evict.c中，通过近似算法来淘汰相对不经常使用的元素，其实就是之前时间戳排序的弱化版，淘汰的是采样部分的LRU。

第一步，采样

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];
    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
}

在dictGetSomeKeys中，随机挑选某个位置开始收集连续count个元素，如果均为空，那么再次随机挑选。这里复杂的地方在于Rehashing过程中会存在两张表，但是这和Redis机制太耦合，和LRU本身倒没啥关系。

第二步，计算Idle

维持一个全局的LRU时钟作为时间戳，如果刷新速度比服务器要求的刷新速度快，就用服务器缓冲的LRU，否则用实时的。

unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        lruclock = server.lruclock;
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

然后idle的时间就是当前时钟与上次访问时钟的差值

unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
                    LRU_CLOCK_RESOLUTION;
    }
}

第三步，按照idle排序并淘汰缓存

这里的优化在于eviction pool记忆之前LRU的幸存者，其实和数据流的Top-K算法比较类似。pool按照idle升序排列，通过插入排序来维护。如果满了，则把idle最小的给删除。

只有比幸存者最小idle更大的元素才可能加入eviction pool，淘汰的时候复用eviction pool中被淘汰的entry以减少分配开销。

        /* Try to reuse the cached SDS string allocated in the pool entry,
         * because allocating and deallocating this object is costly
         * (according to the profiler, not my fantasy. Remember:
         * premature optimizbla bla bla bla. */
        int klen = sdslen(key);
        if (klen > EVPOOL_CACHED_SDS_SIZE) {
            pool[k].key = sdsdup(key);
        } else {
            memcpy(pool[k].cached,key,klen+1);
            sdssetlen(pool[k].cached,klen);
            pool[k].key = pool[k].cached;
        }
        pool[k].idle = idle;
        pool[k].dbid = dbid;

Memcache分段式LRU

memcache采用分段的方式，没有将整体实现为哈希链表，而是每次以Slab为单位进行LRU，这样一来头结点的竞争就被均摊到了每个Slab上。淘汰的是局部的LRU，而不是全局的LRU。

static void do_item_link_q(item *it) { /* item is the new head */
    item **head, **tail;
    assert((it->it_flags & ITEM_SLABBED) == 0);

    head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];
    assert(it != *head);
    assert((*head && *tail) || (*head == 0 && *tail == 0));
    it->prev = 0;
    it->next = *head;
    if (it->next) it->next->prev = it;
    *head = it;
    if (*tail == 0) *tail = it;
    sizes[it->slabs_clsid]++;
#ifdef EXTSTORE
    if (it->it_flags & ITEM_HDR) {
        sizes_bytes[it->slabs_clsid] += (ITEM_ntotal(it) - it->nbytes) + sizeof(item_hdr);
    } else {
        sizes_bytes[it->slabs_clsid] += ITEM_ntotal(it);
    }
#else
    sizes_bytes[it->slabs_clsid] += ITEM_ntotal(it);
#endif

    return;
}

分为四种状态，每个item具有两个bit，fetched和active，即访问1次和访问2次

https://memcached.org/blog/modern-lru/