作者 | 小 y

导读

广告检索系统的性能长尾影响 KPI，间接影响收入，极致优化成本和性能一直是检索端工程团队的重要工作。随着基于 SSD 分级存储在商业场景规模应用，在部分访盘量高的场景，为控制性能长尾退化，我们尝试引入缓存对标系统 PageCache 来解决。在引入过程，我们对业界经典的缓存算法，进行了针对性测评，将测评效果与大家分享，诚邀对存储和缓存技术有兴趣的伙伴们一起探讨。

全文 10162 字，预计阅读时间 31 分钟。

01 缓存的业务必要性

缓存是一种系统优化的“万金油”，多被应用在数据密集场景中。当目标服务的访问性能远远差于缓存服务，且访问模式具有显著局部性时[1,2]，缓存则作为一种临时存储数据的手段，通过减轻访问目标服务的频率，显著提高了数据检索速度，从而加速了业务处理过程。

△Berkery Interactive Version of Jeff Dean Latency Number

在前一篇《极致优化 SSD 并行读调度》[3]，我们提到，广告检索服务因为严苛的 KPI，长期以来采用内存检索，业务发展需要更大存储空间，需求量远超过内存可承受。广告检索 KPI 直接关系收入，检索过程引入基于 NVMe SSD 的分级存储，长尾控制尤其关键。然而，业界常见访盘优化手段，都以优化吞吐为目标，未能控制读长尾。过去几年持续涌现面向长尾控制的新硬件，但新硬件的引入、适配、推广周期较长。业务需求无法等待，需要先把检索池的存量 NVMe 用起来。广告检索业务有如下特点：读多写少，读 SLA 十分敏感。结合广告检索业务随机读顺序写的访盘特点，我们系统性评测了检索池占比 90+%的 NVMe 盘，得到每种盘的最佳读写负载理论配比。并以此为理论基础构建 SsdEngine。

为了规避系统缓存的干扰，我们采用 DIO 访盘，直接控制硬件访问，实现了长尾控制。叠加极致优化读调度，对于单 PV 访盘有限的场景，SsdEngine 基本打平了带系统缓存性能。但访盘较多的场景，单次长尾影响较大，SsdEngine 性能退化较可观，这时候就需要缓存技术，大幅降低访盘频率。

02 缓存算法的本质是淘汰顺序

缓存大小通常是有限的，为此，缓存应尽力保留未来访问概率最高的键，也就是淘汰未来不会访问或访问概率最低的键。可惜缓存无法预测未来，缓存通过定义淘汰顺序（或驱逐策略）来模拟/推理未来。比如假设通常访问模式不会突然发生很大变化，可能再次请求的键是最近经常请求的键，LRU 甚至把它简化为最近请求的键。

2.1 LRU - “最近最少使用”

△LRU Cache 示意图

LRU 通过维护访问历史记录，淘汰最近最少使用的数据。LRU 的不足之处在于它无法很好地适应访问分布不均匀的情况。可能因为业务上突发的稀疏访问，导致频繁使用的数据误被提前淘汰。一般情况下，会通过增加 LRU 的容量，足以容忍一定程度的突发情况，来规避这类问题。

从淘汰顺序视角，LRU 的典型实现方式是采用 std::list来维护数据的访问时间序。当调用get(key)方法时，如果该数据存在于缓存中，就将该数据移至最近使用的位置（move_to_head）。当调用put(key, value)方法时，如果该数据已存在于缓存中，就更新其值，并将数据移至最近使用的位置。如果数据不存在，就检查缓存是否已满。若缓存已满，则淘汰最近未使用的数据（最后一个元素），然后添加新数据，并将其置于最近使用的位置。

get(int key) {    // 找到list中的位置，如果不存在则返回    auto list_it = ...cache_it->second;    // 数据存在，将其移到最前，并返回值    list.splice(list.begin(), list, list_it); }
put(int key, int value) {    // 找到cache中的位置    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 都是通过锁保护。

2.2 LFU - “最不经常使用”

△LFU Cache 示意图

LFU 则根据数据被访问的频率，淘汰使用频率最低的数据，当记录全量数据时，相当于获得了“数据分布”。LFU 的不足之处，一方面是保存全量数据频率的高昂存储成本，另一方面是无法适应突发的数据访问模式变化，表现为：一个元素过去被频繁访问，但从某个时刻起已经不再被访问，却持续保留在缓存中，新晋热点无法胜出。一般情况下，会采用定期衰减的方法规避这个问题。

从淘汰顺序视角，LFU 需要维护的数据结构更复杂，兼顾了频率和时间序。数据结构包括数据频率和频率桶，频率桶代表一组相同访问频率的数据。当有新数据插入时，LFU 算法将新数据插入到频率为 1 的桶中。当缓存已满时，LFU 算法会淘汰访问频率最低的数据。每次数据被访问，就会更新其访问频率，并转到对应的频率桶。由于每次访问会换桶，换桶时候插头，淘汰时候除尾，所以整体是既考虑了频率顺序，也考虑了时间顺序。

典型的 LFU 实现，采用 std::map 组织频率桶，或者采用 std::priority_heap 组织数据。下面列的实现参考了 2010 年发表的 LFU 实现 [14]。

get(int key) {    // 找到cache中的位置，如果不存在则返回    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) {    // 找到cache中的位置    if (cache_it != cache_map.end()) { // 数据已存在，更新值，并移到最前（同上）        ...    } else {        // 数据不存在，检查缓存是否已满        if (_size >= _capacity) {            // 缓存已满，淘汰最久未使用的数据            pop_back(head->next);        }        // 如果没有频率为1的桶，则增加        if (head->next->freq != 1) {            ...        }        // 添加新数据，并将其置于频率为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 一样的缓存命中率。

2.3 Redis LRU - “近似”

△Redis Approx LRU 近似效果评测

Redis 起初并没有引入缓存，当业务需要引入缓存时候，Redis 慎重考量了两点：(1）缓存数据结构，带来内存容量；(2）move_to_head 操作的复杂度，增加性能损耗。为此 Redis 采用了近似的算法[3]，具体来说，Redis 采用 bit field 的方式，从已有的对象 robj 腾挪出 24bit 空间，用于记录访问时间。当对象被访问时候，更新被访问对象的访问时间（robj.lru）。在需要淘汰对象的时候，采样若干个对象，淘汰其中空闲时间最久的。

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or                            * LFU data (least significant 8 bits frequency                            * and most significant 16 bits access time). */    int refcount;    void *ptr;} robj;

当系统需要淘汰一个键时：准备一个容量为 M 的“死亡候选池”，候选池按空闲时间升序排列，也就是最右侧是需要被淘汰的。遍历每个 DB，对每个 DB 随机选择 N 个键，尝试按序加入“候选池”。当池子有空间时候，候选键直接加入，或者候选键大于池中键的空闲时间，才能被加入，并淘汰空闲时间最小的键。如果候选键不能被加入候选池，则说明这个候选键不被淘汰。

freeMemoryIfNeeded:    // 以下是淘汰一个key的算法    // 候选池，池子按照空闲时间升序排列    struct evictionPoolEntry *pool = ...    // 遍历所有db，构成全局的候选池    for (i = 0; i < server.dbnum; i++) {        // 加入pool：1）池子有空间，2）空闲时间更久        evictionPoolPopulate(i, ..., pool);    }    // 从后往前遍历，淘汰一个key    for (k = EVPOOL_SIZE-1; k >= 0; k--) {    ...

Redis LRU 算法，没有引入额外的链表，也不需要在访问过程加锁操作。通过随机选择 N 和候选池 M，兼顾全局视角和操作复杂度。实际上，Redis 不仅实现了近似的 LRU 算法，还用类似的方法实现了 LFU：（1）8 位记录频次 counter，16 位记录时间 timer，其中，timer 是为了周期性地衰减，感知业务访问模式变化；（2）淘汰时候，按频率的补，作为空闲时间排序。

void updateLFU(robj *val) {    // 周期性地衰减    unsigned long counter = LFUDecrAndReturn(val);    counter = LFULogIncr(counter);    // 更新timer 和counter    val->lru = (LFUGetTimeInMinutes()<<8) | counter;}

2.4 操作系统 PageCache

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

△Linux DoubleClock PageCache

显而易见，非活跃列表配额设置足够长，则给于充分时间积累访问。一个页面被首次访问时（Fresh Fault），加入到非活跃列表的尾部，如果非活跃列表的额度不足，在等到再次访问前，该页面会因为没有访问被回收掉（ReFault）。这种情况叫作抖动（thrashing）。

Linux3 时加入 Refault Distance 算法[11]，解决抖动问题。假设非活跃链表足够长，一个页面第二次访问（Refault）和首次访问（Fault）之间的页面数，叫作 Refault Distance。Refault Distance 可以被看成是一种衡量标准，把非活跃链表延长多少就可以避免抖动。如果它比总大小还长，那说明这个 Refault 是不可避免的，否则可以做策略。操作系统采用的策略是，把这个页面加入到活跃链表，避免后面持续 Fault。

当 Linux 引入 Refault 算法时候，有一句这样的评论：“How well all of this works is not yet clear”。这份工作理论上不错，但实际未经过充分数据论证。我们通过实际 benchmark，发现 SsdEngine PageCache 引入 Refault 算法并未带来实际提升。我们后续准备探索 mysql 已应用的 LIRS 算法。

03 解决方案

如在业务背景中所述，广告检索业务读 SLA 十分敏感，为此我们不在检索线程中规避竞争区。SsdEngine 在整体设计上，结合广告检索业务的特点，通过简化的 RCU 的方式实现面向读者友好的数据读写安全。在已有工作的基础上引入缓存，缓存的设计也要以面向读者友好作为第一原则。

△SsdEngine 整体架构

3.1  分层缓存

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

△缓存工作流程

TLS 缓存按照文件组织，也叫做 TLS FilePageTable。由于检索线程数较多，该层采用更加内存友好的数据结构，否则会随检索线程的增加，内存线性地放大。TLS 缓存采用了前缀树 Radix-Tree，并更进一步地，采用了更内存友好的 ART[6,7]。前缀树的路由采用文件中的 offset，限定最大 3bytes。大家都知道，ART 需要通过定期合并 compaction，来减少“变形”带来的操作损耗和控制内存，我们定义了一组参数（树大小、树利用率、频次）等控制合并损耗。

中心缓存用于线程在各自的 TLS 查不到的时候，穿透来访问。它的存储只和文件数相关，内存损耗相对可控，中心缓存的数据组织采用竞争更加打散的 Array，通过 CAS 操作页框实现线程间同步。特别说明：（1）除非在新建/删除文件操作环节有锁，其它 put/get 页面都是无锁的；（2）上面描述多个线程更新同一页框时，CAS 修改页框确保不丢失写，也不丢失冲突记录，否则会发生内存泄漏。

△存存储结构

3.2  Flying

接下来详细介绍 Flying，一次 pv 中，多次访问可能落在同一个页面，Flying PointerSwizzling 可减少单个线程对同一页面的重复拉取。具体来说，第一个 key 访问时，申请页面，并把 PointerSwizzling 后的页面地址填在 SsdTable TLS 页表。其它 key 访问时，看到正在拉取，不会重复拉取。当 poll 到页面拉取结束后，通过 PointerSwizzling，可以识别哪些是拉取到的页面，只把这些页加到中心页表。

高扇出服务必然遇到扇出带来的长尾，SSD 也是如此。评测发现，异步 IO 时随着读页面的增加，wait 耗时也会增加。对于小业务对象，Flying 可显著降低访盘的页面数，在凤巢物料服务，我们通过 Flying 减少了 60%的访盘 QPS。这是个有趣的优化方向，后续可以按缓存反应出的业务热点，按照热点重新组织数据，进一步提升 Flying 比例和降低访盘量。

fetch_page:    // 没有查到缓存，分配新内存页面，返回给scheduler拉取    page = _page_manager->alloc_page();    // mark the in-flight page for later to add fifo, see fetch_page_done    local_page_table->insert(        pageidx_key, reinterpret_cast<const char*>(reinterpret_cast<uintptr_t>(page) | 1));    return std::make_pair(page, true /* newpage */);
fetch_page_done:    const char* page = local_page_table->find(pageidx_key);    if (!(reinterpret_cast<uintptr_t>(page) & 1)) { // in-flight page        return 0;    }    local_page_table->remove(pageidx_key);    page = reinterpret_cast<const char*>(reinterpret_cast<uintptr_t>(page) & (~1));    // 加入到中心缓存

3.3 ARC

ARC[15]论文应用量高达 1300 次。在我们实现好整体框架和适配业务的时候，遇到的实际问题是，业务大部分情况下不知道如何划分初始队列和保护队列的比例。单纯地按照给足够大的非保护队列，积累多次访问概率，会导致保护队列的局部性无法发挥效果。ARC 论文虽然定位是解决动态流量下调参难的问题，但也恰好帮我们解惑了业务落地问题。

ARC 的核心原理是通过保留一倍数量的影子记录，帮助决策当前如何划分两段队列 p。具体来说，假定两段队列分别为 T1 和 T2，他们的影子队列分别为 B1 和 B2，如果查询请求命中了 B1，意味着我们应当把这次命中当作命中了 T1 来看，并且暗示了 |T1| 可能小了，没能将这次命中的数据存起来，此时就要调整 p。p 的调整是累计(0, 1]浮点数控制波动。原理非常直观。

若完全复现 ARC，则要打破缓存整体结构，初始队列和受保护队列直接淘汰到 DELETE，且带来影子存储的额外管理开销。为此我们实现的自适应版本是：优先受保护队列，在受保护队列未填满内存时候，允许初始队列增长。但值得注意的是，初始队列不能被过分挤压，否则无法累积请求。为此，我们额外设置初始队列的低水位，受保护队列的增长不能超过该水位。

△ARC 控制示例

3.4 业务隔离

一个业务进程拥有多个存储对象，页面缓存在存储对象级别独立配置。这里的业务对象，可以是一组表格、或者一组文件，以正排服务为例，正排服务实例中有多组存储对象：（1）广告换血的表格；（2）广告检索的表格组；（3）数据流的文件组等等。由于数据局部性和业务应用场景有别，不同业务存储对象一般采用不同的缓存配置。此时可以把它们拆分独立的 TableEnv/FileEnv，针对这些 Env 对象做独立缓存配置。关于 Env 的组织，请参见上面 SsdEngine 整体架构图。

一个存储对象，在启用缓存配置的模式下，也会有避让缓存的场景，以避免污染缓存。因此 Table/File 还提供了 read_disk 接口，可直接绕过缓存读盘。这一般用于优先级低的后台线程，比如加载线程、DUMP 线程、GC 线程等等。

业务切换缓存配置的过程，代码是自适应的。切换缓存配置主要影响的是业务 Buffer 如何引用内存页面 Page。使用 Buffer ReadOnly 模式，在打开缓存的情况下，引用方式使用页面，较操作系统的内核空间-用户空间的多次拷贝，有显著性能优化。在禁用掉缓存后，自动切换为 Buffer Owned 模式，拷贝数据到 Buffer 中。

3.5 逼近最优淘汰顺序

页面淘汰决策发生在中心缓存，下图是中心缓存淘汰算法的整体架构。我们整体上按照两段式的方式，初始链表是高性能的 TLS FIFO，受保护链表（protected）按不同算法采用不同数据结构，用于不同业务场景切换缓存算法。访盘得到的页面 CAS put 到 TLS 初始链表，页面一旦进入到初始链表，接下来被访问时候，记录该页面被访问过“SALVAGE”。当初始链表按照 FIFO 顺序准备被淘汰页面时，如果该页面被标记了 SALVAGE，则捞回到受保护队列，此处会根据缓存算法进入不同的缓存。受保护链表有不同的实现形式，比如轻量的 DoubleClock（=FIFO+FIFO），2Q（=FIFO+LRU），TinyLFU（=FIFO Doorman+TinyLFU）等。

△中心缓存淘汰算法整体架构

3.6 DoubleClock

△DoubleClock 算法整体架构

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

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

3.7 2Q'

△2Q 算法整体结构

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

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

3.8 TinyLFU'

△TinyLFU 算法整体结构

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

04 效果评估

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

4.1 评测环境

评测运行环境机型是 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。

4.2 评测内容

为了充分验证缓存效果，先导入一批数据（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

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

△cache hit: zipfian0.9  LRU vs DoubleClock

同时我们看到，由于缓存命中率提升，LRU 较 DoubleClock 在长尾访问上优势明显，以下是 9999 分位性能（单位 us）：

△9999 分位性能  LRU vs DoubleClock

场景二：

轮流访问（uniform）：每个数据项都具有相等的概率被选择。在这种数据分布下，LRU 较 DoubleClock 并没有优势，徒有算法的复杂性。

分布是 uniform，缓存大小分别是 4G、6G、8G、10G、12G 的缓存命中率：

△ cache hit: uniform  LRU vs DoubleClock

场景三：

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

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

05 业务应用和后续计划

SsdEngine 已在商业意图场景上线，通过对读写模式的控制，又引入缓存减少读盘并发，稳定住长尾性能，打破 SSD 独占成本和检索性能的折衷。当下的设计，已打开了对于不同“数据分布”场景下缓存算法的探索空间（Adaptive Cache Management）。随着应用范围扩大，我们会再深度挖掘更多更合适的缓存算法。

——————END——————

参考资料：

[1]. Software Engineering Advice fromBuilding Large-Scale Distributed Systems,2002

[2]. Berkeley Interactive Version Latency Number

[3]. 极致优化 SSD 并行读调度

[4]. Random notes on improving the Redis LRU algorithm

[5]. A Lockless Pagecache in Linux—Introduction,Progress, Performance,2006

[6]. Page Cache eviction and page reclaim

[7]. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases,2013

[8]. 凤巢倒排服务的优化

[9]. 2Q:  A Low Overhead High Performance BufferManagement Replacement Algorithm,1994

[10]. TinyLFU: A Highly Efficient Cache Admission Policy, 2017

[11]. Better active/inactive list balancing, 2012

[12]. Linux Spin Lock Cas Implementation

[13]. LevelDB sharded LRU Implementation

[14]. An O(1) algorithm for implementing the LFU cache eviction scheme, 2010

[15]. ARC: A Self-Tuning, Low Overhead Replacement Cache,2003

推荐阅读：

如何定量分析 Llama 3，大模型系统工程师视角的 Transformer 架构

微服务架构革新：百度Jarvis2.0与云原生技术的力量

技术路线速通！用飞桨让京剧人物照片动起来

无需业务改造，一套数据库满足 OLTP 和 OLAP，GaiaDB 发布并行查询能力

Tensor 索引的使用指南及学习心得