CacheLib 原理说明

CacheLib 介绍

CacheLib 是 facebook 开源的一个用于访问和管理缓存数据的 C++ 库。它是一个线程安全的 API，使开发人员能够构建和自定义可扩展的并发缓存。

主要功能：

1. 实现了针对 DRAM 和 NVM 的混合缓存，可以将从 DRAM 驱逐的缓存数据持久化到 NVM，存于 NVM 上的缓存数据在被查找命中时会写到DRAM缓存，这些对用户都是透明的。
2. 支持缓存数据的持久化，使进程在重新启动后依然可以保持原有缓存数据不丢失。
3. 缓存可变大小的对象。
4. 提供零拷贝的并发访问。
5. 提供丰富的缓存算法，如 LRU、分段 LRU、FIFO、2Q 和 TTL。
6. 使用硬 RSS 内存限制以避免 OOM。
7. 智能和自动调整缓存以动态更改工作负载。

下面挑选在上述功能中挑选几个重要的着重说明一下。

CacheLib 混合缓存

CacheLib 通过混合缓存功能支持使用多种硬件介质。为了使这对用户透明，提供了统一的 CacheAllocator API 封装，让用户对具体的硬盘读写无感知。CacheLib 支持 SSD 作为混合缓存的 NVM 介质。Navy 是基于 SSD 优化的缓存引擎。为了与 Navy 交互，CacheAllocator 针对 NVM 的操作包装为NvmCache。CacheAllocator 将 Navy的查找、插入和删除的功能完全交给 NvmCache 来实现，并保证其是线程安全的。 NvmCache 实现处理 Item 与 NVM 之间的转换的功能。CacheAllocator 中没有全局键级锁来保证 DRAM 和 NVM 之间的同步，因此 NvmCache 采用乐观并发控制原语来保证数据的正确性。

前置知识：

CacheLib 支持的缓存特性

CacheTrait 是 MMType、AccessType 和 AccessTypeLock 的组合。

MMType：内存管理类型，它控制缓存项的生命周期（add/remove/evict/recordAccess），类型包括 MMLru、MM2Q、MMTinyLFU。

AccessType：访问控制类型，它控制缓存项的访问方式（find/insert/remove），类型包括 ChainedHashTable。

AccessTypeLock：是支持多个锁定原语的访问容器的锁类型，类型包括 SharedMutexBuckets、SpinBuckets。

RefcountWithFlags

记录缓存项的引用计数和标识符

|--------18 bits----------|--3 bits---|------11 bits------|
┌─────────────────────────┬───────────┬───────────────────┐
│         Access Ref      │ Admin Ref │       Flags       │
└─────────────────────────┴───────────┴───────────────────┘

Access Ref：记录缓存项的引用计数

Admin Ref：记录谁有权限管理缓存项，如 kLinked（MMContainer）、kAccessible（AccessContainer）、kMoving。

Flags：指示缓存项当前的状态，如 kIsChainedItem、kHasChainedItem、kNvmClean、kNvmEvicted、 kUnevictable_NOOP。

混合缓存初始化

在创建 Cache 实例时都是通过 CacheAllocator 来实例化，这里分为两种方式，一种是不支持缓存持久化的启动方式，另一种是支持缓存持久化的启动方式。支持持久化的方式比不支持持优化的方式会多一个入参 SharedMemNewT 或 SharedMemAttachT。

SharedMemNewT 会使 Cache 多一个 shmManager，利用 posix shm 来做缓存的持久化，一般会生成两个文件：metadata 和NvmCacheState，具体可以参考 ShmManager.h 和NvmCacheState.h。metadata 会存储内存相关的元信息包括 shm_info、shm_cache、shm_hash_table 和 shm_chained_alloc_hash_table；NvmCacheState 会存储 NVM 的状态信息，因为 NVM 的元信息已经在缓存文件中记录，不需要在额外持久化。

SharedMemAttachT 会在启动时尝试 attach 之前持久化的元数据，如果成功可以继续使用存在的缓存，如果失败会抛出异常，所以一般的用法如下：

 try {cache = std::make_unique<Cache>(Cache::SharedMemAttach, config);} catch (const std::exception& ex) {cache.reset();std::cout << "Couldn't attach to cache: " << ex.what() << std::endl;cache = std::make_unique<Cache>(Cache::SharedMemNew, config);default_pool = global_cache->addPool("default", 1024*1024*1024);}

Item 分配和淘汰

缓存在写入 CacheLib 时，会先写入 DRAM 中分配内存并将数据写入，写入后交由 MMContainer（缓存管理容器）进行管理。

insertInMMContainer(*(handle.getInternal()));

当 Item 满足淘汰策略要被淘汰时，有两种途径：一是直接从 CacheLib 中淘汰掉；二是从内存中淘汰掉进入 NVM。

因为 NVM 为了保证时刻都有着良好的性能，支持定制 Admission Policy，比如突然有过多的 kv 写入时可以按百分比拒绝掉部分 kv 写入请求。这样可以起到保护 NVM 的作用，同时在 CacheLib 淘汰的 key 就会直接被淘汰，不会写入 NVM。

当不满足阈值条件时，Item 就会被写入 NVM，如果 NVM 空间被占满同样也会触发淘汰机制。

这个 allocation 过程也就是insert的核心逻辑，对应 insert 还有一个实现是 insertOrReplace，insert 在写入时会因为有重复 key 导致写入失败，insertOrReplace 则会直接替换原先存在的 key，具体的实现就是在 check 后和写入前，将 NVM 做标记删除，具体可以参考createDeleteTombStone 函数。到此也引出一个逻辑就是，NVM 中的数据都是标记删除，并不会直接清空这部分数据，而是后续通过调用 removeAsync 完成异步删除。

混合缓存查找

在查找 key 时首先在内存中进行查找，为此 CacheLib 专门设计了下面这个函数，在找到 key 后会判断 key 是否过期，过期会标记为过期，并返回未找到。

auto handle = findFastImpl(key, mode);

如果内存中不存在，会尝试从 NVM 中查找，find 有同步的也有异步的实现，但 NVM 一般都异步的 find，性能会更好。

NVM 的 find 设计稍微有些复杂，首先为了避免磁盘的繁重搜索，加入了 enableFastNegativeLookups 功能，可以预先判断 Item 在内存中是不是肯定不存在。如果不确定存不存在，再进行 NVM 上的查找，其实这里就是一个 bloom 过滤器。

因为内存和磁盘的交互时间会比较长，从内存中驱逐到磁盘的过程（写 NVM ）就会相对比较长，所以为此设计了异步查找功能，通过 GetContext 来追踪整个查找过程，最后使用回调函数来通知通知用户查找完成。

在查找过程中有可能会有多个 find 并发请求，CacheAllocator 为了性能考虑，并没有使用真正意义的锁，而是利用乐观所机制来保证 DARM 和 NVM 中数据的一致性。NvmCache 是通过维护一个 PutTokens 结构来实现的，每个正在写入 NVM 的 key 都有一个属于自己的 putToken，只有在 putToken 有效的情况下才能执行 NVM 的写入，以此来控制 key 的可见性。

举个例子，当线程1有一个 find 请求要查找 key1，此时有可能线程2正在执行 key1 的 NVM 写入，key1 会持有一个有效的 putToken，当线程1执行 find 时，key1 就会被 LRU 等规则激活，就不需要被内存淘汰，也不再需要写入 NVM，所以会将 key1 的 putToken 置为无效，线程2的写入操作发现 putToken 无效则不再继续写操作，这样可以保证从 DRAM 到 NVM 查找的顺序一致性。这里的 putToken 只有在写入 NVM 时才会生成，在 find 和 eviction 等操作时会被置为无效，并没有很复杂的状态变更。

在 NVM 查找完成后，Item 并不是直接返回给用户，而是先写入到 DRAM，同 allocation 逻辑，此时通过 nvmClean（true） flag 标识 DRAM 和 NVM 中该 kv 是一致的，如果 Item 再次被淘汰，则不需要再次写入 NVM，因为 NVM 已经存在该 key。如果 key 所对应的 value 被修改，nvmClean 会被置为 false，标识为不一致。NVM 中这部分不一致的会被后台异步线程清理掉。

Navy实现原理

Navy 是基于 SSD 优化的缓存引擎。Navy 的特点：

1. 高效缓存 SSD 上的数十亿个小对象 (<1KB) 和数百万个大对象 (1KB - 16MB)。
2. 高效的点查找
3. 低 DRAM 开销

由于 Navy 是为缓存而设计的，因此在实现上选择牺牲数据的持久性。由于 Navy 是写密型的，NVM 写入寿命就成为一个关注点，Navy 也针对写入寿命进行了优化。

Navy整理架构

Navy 为用户提供了一个异步 API。Navy 使用 Small Item Engine 对小对象进行优化，使用 Large Item Engine 对大对象进行优化。每个引擎的设计都考虑了所需的DRAM开销，而不会影响读取效率。在下面，做了块设备的抽象，两个引擎都在块设备抽象之上运行。

Engine

Navy 针对 Item 的大小分别实现了 Small Item Engine 和 Large Item Engine，对应的具体实现分别是 BigHash 和 BlockCache，可以通过 Item 的大小控制 Item 是存储到 Small Item Engine 还是 Large Item Engine，在查询时会优先查询 Large Item Engine，如果不存在，再去查询 Small Item Engine。一般 Small Item Engine 都是存储 1K 以内的数据，大数量的缓存一般都是使用 Large Item Engine，Small Item Engine 也是可以通过配置禁用的。如果因为异常终止了还会进行重试。

BigHash 主要用于小对象，暂不做过多介绍。

BlockCache

Large Item Engine 的具体实现就是 BlockCache，下面是 BlockCache 的具体结构：

主要读写逻辑

1. 根据 ssd 配置 deviceMaxWriteSize 和 blockCacheRegionSize（默认16MB）将 Device 分为多个 Region，并存入 CleanList。

2. 写入流程：

   选择一个 Region，如果 Region 还未填满，则向该 Region 追加 Entry，如果当前 Region 已满，会向 CleanList 获取一个 Region。若 CleanList 为空，需要等待 eviction 和 gc 来释放 Region，最后更新 IndexMap。

3. 查询流程：

   根据 key 找到 RegionId 和 offset，再通过 RegionId 和 offset 定位到 Entry，解析读取数据。

4. 删除流程：

   只从 IndexMap 中删除，Entry 本身会被标记删除，等待 gc 异步处理。

5. 淘汰流程：

   根据淘汰策略进行淘汰，策略有 FIFO、LRU、LRU2Q，淘汰是以 Region 为单位进行淘汰，如果觉得粒度太大，可以配置 reinsertion 根据命中率或频率进行重插入来保留。

Job调度

这里的 job 包含4类；

JobType::Read：对于对应于 Navy 读取作业（查找）；

JobType::Write：对应于 Navy 写入作业，新的插入和删除都是以插入形式实现的；

JobType::Reclaim：执行内部淘汰操作；

JobType::Flush：执行任何内部异步缓冲写入；

Job是严格按顺序提交，保证写入和查询的顺序一致性，避免对同一个 key 同时执行多个操作。再遇到并发请求时，还是依赖NvmCache的乐观锁机制保证 DRAM 和 NVM 的数据一致性。

JobScheduler 提供两个线程池，一个负责读，另一个负责写。Job 会根据类型分配到两个线程池其中之一。并且在根据 key 分配到指定的线程上，每个线程都维护着一个 JobQueue，一般都是先入先出的，但是 JobType::Reclaim 和 JobType::Flush 会有更高的优先级，会优先执行。

为了使用线程池提高性能还要维持顺序一致性，引入了一个分片排序机制，首先通过配置参数可以指定分片的数量，一般为数百万个，提交的 Job 会根据 key hash 到不同的分片内，同一个 key 只会在一个分片内，保证对同一个 key 处理的顺序性，分配请求会从第一个分片开始遍历，一般一次只取一个 Job，如果连续的 Job 是不同的 key 没有冲突，可以一次取多个提交到线程池线程的 JobQueue 中，遍历到结尾处再次循环遍历，不断的完成 Job。

以上就是对 CacheLib 混合缓存原理的介绍。