读友好的缓存淘汰算法_AI阅读总结 — 包阅AI

△LRU Cache示意图

get(int key) {        auto list_it = ...cache_it->second;        list.splice(list.begin(), list, list_it); }
put(int key, int value) {        if (cache_it != cache_map.end()) {         ...     } else {        if (_size >= _capacity) {                        list.pop_back();        }
                list.emplace_front(...);        cache_map.put(key, list.begin());    }}

为了LRU能够工作，一般还会配备std::unordered_map来实现O(1)查找。在list中，每个元素是value。unordered_map用于存储每个key对应在list中的迭代器，从而实现在O(1)时间内查找和移动元素。

LRU为了记录“最近”访问的淘汰顺序，需要不断的“move_to_head”。这给高性能实现带来挑战，操作链表中间元素，会显著提升无锁链表的实现复杂度。为此一般的LRU都是通过锁保护。

△LFU Cache示意图

get(int key) {        auto list_it = ...cache_it->second;    frenquency = list_it->second;        frenquency_bucket = list_it->parent;
    if (frenquency_bucket->next->freq == frenquency + 1) {       ...    } else {       ...    }}
put(int key, int value) {        if (cache_it != cache_map.end()) {         ...    } else {                if (_size >= _capacity) {                        pop_back(head->next);        }                if (head->next->freq != 1) {            ...        }                push_front(head->next, {value, 1});        cache_map.put(key, head->next->begin());    }}

为了LFU能够工作，也会配备std::unordered_map来实现O(1)查找。在频率桶list中，每个元素是一个std::pair，其中first存储value，second存储frequency。unordered_map用于存储每个key对应在list中的迭代器，从而实现在O(1)时间内查找和移动元素。

LFU较LRU显然更复杂，对每个频率都独立维护了List，List还会操作中间节点，这对高性能实现带来更多挑战。它的理论优势是，在较大的、没有显著局部性的动态负载下，LRU需要更多的空间来保持和LFU一样的缓存命中率。

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:LRU_BITS;     int refcount;    void *ptr;} robj;

freeMemoryIfNeeded:            struct evictionPoolEntry *pool = ...        for (i = 0; i < server.dbnum; i++) {                evictionPoolPopulate(i, ..., pool);    }        for (k = EVPOOL_SIZE-1; k >= 0; k--) {    ...

void updateLFU(robj *val) {        unsigned long counter = LFUDecrAndReturn(val);    counter = LFULogIncr(counter);        val->lru = (LFUGetTimeInMinutes()<<8) | counter;}

操作系统缓存的页面淘汰策略核心是Double Clock算法[5]。数据结构由两个列表构成，分别代表活跃列表和非活跃列表，活跃列表包含了最近经常使用的页面，非活跃列表包含了最近不使用页面。它们都采用FIFO（先进先出）的形式。新页面（Freshly Faulted）添加到非活跃链表的头部，随着页面被回收，非活跃链表中间的元素逐渐向链表的尾部移动。如果页面在非活跃列表，又被访问过一次，该页面会被升级到活跃列表，并清空页面的访问标记。当活跃列表满了，需要从尾部淘汰到非活跃列表。也就是说，DoubleClock并不是严格按照时间顺序来淘汰数据，而选择了是否访问过，从而降低了操作复杂度。具体来说是一组标记<is_active, is_referenced>。

从缓存算法章节可见，缓存本质是淘汰顺序，必然涉及到数据结构的调整。然而现代CPU往往是多核的，每个核心都有自己的高速缓存（L1、L2、甚至 L3），线程同步带来损耗，无法发挥硬件优势，为此，我们整体架构上引入分层缓存。大部分情况下，检索线程从TLS缓存中获取页面，极少情况下穿透到中心缓存区。TLS和中心缓存的协作过程，概述是这样的：读盘时，优先读取TLS缓存。如果TLS缓存未命中，再去中心缓存获取，如果获取到页面，则把该页面计入TLS，并返回取得页面。如果以上两级缓存都未命中，则发起读盘，并在TLS中记录本次读盘，我们把这一步叫做Flying。最终，多个线程可能同步获取同一页框对应的页面，这些线程把获取到的页面更新put到中心缓存，并清空Flying。中心缓存对同一页框收到若干页面，只记录CAS成功的一个，其他的页面被释放。随中心缓存淘汰算法运行，页面被清理时，也会对每个TLS缓存发起清空。

△缓存存储结构

fetch_page:        page = _page_manager->alloc_page();        local_page_table->insert(        pageidx_key, reinterpret_cast<const char*>(reinterpret_cast<uintptr_t>(page) | 1));    return std::make_pair(page, true );
fetch_page_done:    const char* page = local_page_table->find(pageidx_key);    if (!(reinterpret_cast<uintptr_t>(page) & 1)) {         return 0;    }    local_page_table->remove(pageidx_key);    page = reinterpret_cast<const char*>(reinterpret_cast<uintptr_t>(page) & (~1));    

标准的DoubleClock算法通过活跃链表和非活跃链表，组合考虑了页面的<is_active, is_referenced>，近似实现LRU。我们的缓存实现是类似的：当页面按照FIFO顺序从初始链表准备被淘汰的时候，首先，根据内存配额判断必须要淘汰的页面数量，接下来，一直弹出直到淘汰足够多的页面或者链表被清空。在弹出的过程，如果页面被访问过SALVAGE，则加入到受保护区，等待按受保护区FIFO的淘汰算法再处理。

该缓存算法的优势是操作简单，劣势是几乎只通过“访问过”识别顺序。这样的话，无法区分出轮流访问的页面和访问局部性的页面。在局部性很强的场景下，缓存淘汰较LRU差比较多。

标准2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。我们的实现中，初始链表可以看做2Q算法中的FIFO队列，LRU受保护链表作为2Q算法中的LRU队列。

LRU缓存引入了访问时间序，根据访问时间更加准确淘汰。这个好处带来了额外成本，LRU move_to_head操作复杂，一般用锁来保护LRU的操作。为了减少竞争区，我们的LRU实现采用了异步做法，在检索线程仅仅记录TLS getevent，在后台线程扫描所有线程的TLS getevent，批量操作LRU。

在仅仅按时间序淘汰的LRU之外，我们还参考了TinyLFU[10]，引入了基于频率准入的LRU增强，这样兼顾了时间和频次。我们通过如下两点得以实现对全量数据（而不只是LRU存储数据）的统计。第一点，直觉上好像有了FIFO+SALVAGE的方式，并不需要Doorkeerper，实际不然。这是因为SALVAGE也在不断淘汰，没有足够信息识别全量SALVAGE数据，为此继续保留Doorkeeper，和Count-Min Sketch配合以近似的方式刻画全量数据，并通过重置（reset)方法保持数据新鲜度。第二点，对于突发流量的频次积累，我们通过FIFO来实现get事件的积累，无需引入更复杂的W-TinyLFU，从LRU的视角来看，插入要保护在内存的新页面时候，对于来自SALVAGE的new，与超额要淘汰的victim，根据TinyLFU判定是否保留。

缓存的核心评价指标是命中率（Hit Ratio）。当一个数据项被访问时，如果它已经出现在缓存中，记为一次缓存命中。缓存命中的次数和数据访问的总次数之间的比率被称为命中率。因此，如果保存在缓存中的项能够“准确”预测未来的访问模式，那么缓存命中率会很高。

评测运行环境机型是CPU Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz，L1d cache: 32K，L1i cache32K，L2 cache 1024K，L3 cache 16896K，内核是 64 位 3.10 系。

SsdEngine引擎集成在单机RocksDB中，编译器是GCC12，编译优化选项是 -O2。

为了充分验证缓存效果，先导入一批数据（1000万键空间），每条数据平均占2个页面，再按照分布要求读取这些数据。我们针对这三种缓存算法，评测了局部访问和轮流访问这两种典型的数据访问分布。

场景一：

局部访问（zipfian）：在Zipfian分布中，数据项的选择概率与它们的排名成反比关系。具体来说，第i个数据项的选择概率与i的倒数成正比。这意味着排名靠前的数据项具有更高的选择概率，而排名靠后的数据项具有较低的选择概率。换句话说，Zipfian分布中的数据项呈现出“头重脚轻”的特点，即少数数据项被频繁选择，而大多数数据项被相对较少地选择，数据分布具备很强的“局部性”和“长尾性”。Zipfian幂指数参数s控制分布的陡峭程度。当s增大时，分布的头部会变得更加突出，即少数事件的频率会显著高于其他事件。在这种数据分布下，LRU较DoubleClock有优势，但缓存内存足够大的时候优势减弱。

分布是zipfan s=0.6，缓存大小分别为4G、6G、8G、10G、12G的缓存命中率：

△cache hit: zipfian0.6 LRU vs DoubleClock

场景三：

TinyLFU和LRU：TinyLFU以少量的内存增长，在任何分布下，都一定程度上提升了LRU的表现。下图择取的zipfan分布下的表现，可以看到，在缓存量相对Key空间较小的情况下，TinyLFU由于考虑了时间和频次，具有明显优势，但是随着缓存大小的上涨，TinyLFU和LRU缓存效果趋于相近。同时我们还发现TinyLFU要花更久的时间才能积累到缓存效果。

△cache hit: zipfian0.6 LRU vs DoubleClock & TinyLFU