Hexo
0%

paper reading: The CacheLib Caching Engine: Design and Experiences at Scale

Posted on Edited on

Abstract

在过去每个团队都可能维护一套自己的特化的cache. 这样的方式无视了不同cache系统共有的问题, 极大增加了部署，维护以及扩容的成本.
本文主要介绍CacheLib——Facebook内部已经广泛应用在CDN，存储和应用数据cache上. 坐着阐述了各个生产环节workload的特质以及FB内部的应用场景如何影响着决策. 描述了FB内部cache如何演化的, 也讨论了对未来的cache研究和设计能带来哪些暗示.

Introduction

FB内部架构里大量的系统都使用了cache,包括CDB caches, key-value application caches, social-graph caches, storage cache, database cache, media caches等. 这些cache系统最初都是单独设计实现并维护的. 最初的思路是单独设计针对不同场景优化以此满足复杂的一致性协议，更好地利用定制化数据结构，并且对特定的硬件平台优化.

尽管各种cache有一些不同点，但他们也有很多相同的点: 都需要百万级的qps, cache set大到需要flash和DRAM都使用, 同时必须容忍系统更新引起的频繁重启(FB在Fail at Scale里提过他们更新部署是很频繁的). 随着FB的发展，这些cache系统也越来越多, 维护这么多系统的代价也是很高的. 很多重复的问题在不同的系统上被重复地解决多次. 同时这样多系统的维护也让很多系统上的系统调优知识无法有效共享. 因此FB在考虑了泛用性和特化的tradeoff之后选择了泛用性. 虽然这会在某些特殊的系统上丢失一部分特殊领域的优化，但是减轻了代码开发的负担也增加了系统协调性.

最后FB开启了CacheLib的开发. CacheLib作为一个C++库提供了cache功能所必需的核心功能, 包括: 高效的cache索引实现, 驱逐策略, 为DRAM和flash caches的稳定优化. 同时提供给用户简单，线程安全的接口.

Lessons Learned from CacheLib

**特化的cache系统可以同时也应该构建于通用的cache系统之上.**一方面一套统一的代码更利于维护和开发，另一个方面业务部门可以通过在core系统外围开启不同功能选择不同配置以定制化需求. 同时统一的系统的运维经验，调优经验，方便整理的文档也利于开发者分享(搞不好还利于减轻oncall的人的压力).

生产场景的workload需要大规模饿环境.以往的benchmark采用的是参数为.9的Zipf popularity model. 基于这个模型会认为DRAM-based缓存已经可以应对大多数场景. FB的场景里面cache系统需要能够应对massive request. 所以采用了flash.

Motivation: Caching Use Cases

这一章以6个FB内部的生产系统为例介绍不同的业务对cache的需求是什么

Hierarchical and geo-distributed caches

FB的CDN服务专注于为请求静态资源的HTTP请求服务. 使用CDN的目标之一是减少因为cache miss引起的跨区域网络传输(比如在亚洲要是需要请求到北美的服务器那延迟肯定很低). 在FB内部每台CDN都是使用local cache，同时包含flash和DRAM.

Application look-aside caches

web应用的cache需求非常广泛. 可能是某条db的查询结果(比如查询库存), 查询用户数据等. 这种需求一般是应用通过RPC访问一系列的共享cache服务. 每一个cache服务都由一个庞大的分布式cache系统组成(其实就很类似互联网应用中各种各样的cache, 不过一般可能都是使用的redis的服务, 可以看下FB关于memcached的论文).

in-process caches

也有很多应用无法忍受remote cache的网络开销. 这个时候cachelib也可以发挥类似caffeine的作用，以进程内cache的方式发挥作用.

Machine learning-model

面向用户的ml应用经常基于用户和推荐内容的互动来作为训练的输入. 用户和内容的互动会先cache住以方便ml程序快速做出预测(类似于将用户的行为记录counter缓存在cache中，用户的counter的更新也能通过write through cache的方式更新，之后训练程序直接读取cache肯定比去storage service里load更快). 另外相同的输入往往输出也相同，所以可以将相同输入对应的预测结果缓存在cache中.

Storage-backend cache

持久化数据会按照blocks的方式存储在FB内部的集群中的spinning disks上. 即使在block storage server前使用了多层存储还是存在部分热点block的请求次数超过目标磁盘的IOPS的情况. Storage server会使用flash来缓存热点block. 为了支持byte-range请求和append操作，这些flash cache会和storage system stack紧密整合.

Database page buffer

数据结构和小对象被存储在各种各样的数据库系统中. DB会利用page cache来提升吞吐并降低延迟, 为了保证一致性和事务性, page cache会和数据库logic紧密整合.

目前除了database page buffer以外上诉其他场景cachelib都在fb内部使用了.

Shared Challenges Across Caching Systems at Facebook

这一章介绍构建cache系统时普遍面临的问题.

Massive Working Sets

working set的定义是在一个workload中能够从caching里面收益的对象的集合. 如果要达到相同的hit ratio, working set越大则需要越大的cache. 为了测量working sets, 必须同时考虑随着时间变化被看到的popular data(Popularity)和随着时间变化数据的欢迎度改变的程度(Churn).

Popularity

表示每一个key在一定时间内在系统内所有objects间的相对受欢迎度.

TODO: 这里贴图

不恰当地说, 在Zipf分布里最受欢迎的20%的object接受了80%的请求. 但Zipf 分布的公式里第i受欢迎的object的相对频率是通过一个参数可以计算出来的. 相对的这个参数越低意味着更多的请求会发给popularity 分布的尾部，这也就需要更大的working set. (Lookaside系统的参数接近1， SocialGraph是0.55 CDN是0.7)

Churn

Churn表示随着新key的进入，working set的变化以及已经存在的key的popularity变化. churn会影响caching policy的设计。 高churn就增加了temporal locality的重要性. 也让caching police’s更难通过过去的access patten估计object的popularity.

这些发现也限制了设计一套通用cache系统时的设计空间. 许多现有的系统一个cacheline最多存储一个单独的object(64B). 对于SocialGraph系统(一般是10B到20B)这就会很浪费. 另一个挑战是经常用于作为flash里面系统的in-memory index. 每一个object在索引上的负担在现有系统上也是不同的(8B-100B都有。如LookAside系统, 这意味着需要80GB-1TB的DRAM来索引1TB的flash上的数据).

Size大小多变

Storage 和 CDN需求里常见的是64KB和128Kb的chunk，所以会把大的object拆分成chunk. 而Lookaside和SocialGraph里大小变化超过7个数量级.

Bursty Traffic

用户的请求数量存在激增的情况. 通常在system领域会采用Poisson分布来描述请求, 但FB内部的采集数据显示和实际上请求到达的速率还是有很大的区别的. Lookaside场景相对Poisson分布波动较小. SocialGraph和Storage场景会有20%到30%做有的波动, CDN场景则存在很尖锐的波动. 请求到达速率的多变性让cache系统在高压导入场景很难有效提供资源给cache服务.

Resource Management

cache系统需要注意不能将系统可用资源全部消耗,尤其是DRAM-based的cache系统. 以in-process场景的cache为例, 因为需要cache的对象的size也是多变的，所以cache的内存消耗也是很难预测的. 如果消耗了太多内存很容易导致系统OOM程序直接退出.

Computationally Costly Query for Empty Results

在追踪用户关系的数据库查询中经常会出现query返回了空的情况. 这种查询很浪费数据库资源. 在SocialGraph场景中FB发现有55.6%的查询都是这种空结果查询. 剩余的44.4%的请求都是有效的对象，对应的cache命中率是86.5%. 如果不能cache住空结果, 对应的cache命中率会显著降低.

Updating Cached Data Structures

Cache应该能够有效支持结构化数据. 特别是对in-process场景. 应用程序经常会希望能够在不反序列化整个cached数据的情况下更新其中的特定fields.

Frequent Restarts

最后，生产环境中的cache系统应该能过在频繁重启(可能是bug修复或者软件更新)的情况下稳定工作. 75%的Lookaside场景和95%的CDN场景的更新时间都小于7天. 即使是Storage和SocialGraph场景也会因为每月的维护需要重启cache进程. 大部分的cache系统是透明无感的，也就是说重启后就丢失了cache中的数据. 这对于大型的cache系统是很不友好的，可能需要很长的时间cache系统的命中率才能恢复到正常状态. 有的系统会采取warmup来缓解.

笔者吐槽: 其实cachelib在程序非正常退出的情况下 cache也全部会丢失… 只有优雅退出的场景能保留cache内容.

Design and Implementation

FB认为要解决前两章的问题则cache系统应该有如下的feature:

  • Thread-safe cache primitives: 以此简化应对bursty traffic的场景. 同时也简化了一致性和cache invalidation协议的实现.
  • Transparent hybrid caching: 为了能够满足large working sets的需求，cachelib支持混合使用DRAM和flash。 Hybrid cache能够在每台节点提供TB级的cache能力. cachelib提供给programmer的统一的byte-address的抽象，让programmer无需担心底层的存储介质.
  • Low resource overhead: Cachelib能够在占用低CPU和memory的情况下提供强劲的吞吐. 这使得其能够在和application混布的场景发挥作用(cache和application共享资源). 也让其在small objects很多的场景也能够顺利工作(不会出现前文中需要很大的资源才能维护cache index之类的情况).
  • Structured items: Cachelib提供了原生的array和hashmap的实现. 可以在不发起serialization的情况下高效cache和修改.
  • Dynamic resource monitoring, allocation, and OOM protection: cachelib会监控整个系统的内存使用.
  • Warm restarts: 在重启程序时依旧保留cache的状态.

API设计

所有的api设计都围绕着一个叫Item的概念, 用来表示被cache的对象的抽象. Item能够用byte-address的方式访问cache中的object, 无需关心是cache在DRAM还是在flash中. ItemHandle是Item的使用接口，每产生一个handle就会对Item的引用计数+1，销毁时则-1. 除非Item的引用为0，否则不会被evict. 如果某个引用计数不为0的item被删除或者超时expires了，现存的他的itemhandle还是有效的，但是不会有新的itemhandle产生了.

1
2
3
4
5
6
ItemHandle allocate(PoolId id, Key key, uint32_t size, uint32_t ttlSecs = 0);
bool insertOrReplace(const Itemhandle& handle);
ItemHandle find(Key key);
void* Item::getMemory();
void* Item::markNvmUnclean();
bool remove(Key key);

调用allocate时如果没有空间会先根据eviction policy来驱逐一个引用计数为0的Item. 新插入的Item可以设置TTL. 同时根据PoolId可以可以选择内存池以提供隔离性配置. 任何一个新的Item会在对对应的ItemHandle完成insertOrReplcae操作后才可见.

要访问Item需要通过find方法根据Key拿到ItemHandle. 之后可以通过getMemory方法以非同步地方式零拷贝访问Item相关的内存. 如果需要原子性地更新一个Item, 可以先使用allocate分配对应的ItemHandle，然后通过调用insertOrReplace让更新可见。 CacheLib会忠实地执行用户的markNvmUnclean方法指示任何的修改. 最后，remove会删除key指定的object，也会invalidation cache或者删除对应的底层的object.

1
2
3
4
5
struct MyType {
    int foo;
    char bar[10];
}
TypedHandleImpl<Item, MyType> typedHandle{cache->find(..)};

用户也可以如上面的代码一样自定义类型并使用CacheLib将他们cache起来. 也支持变长类型比如hashmap等.

Architecture Overview

CacheLib的设计目标是能够有足够的拓展性以及能够应对各种长度的size的object. 为了实现较低的per-object负载, 一个单独的CacheLib cache由多个子系统组成，每一个都对应一个特别的storage介质和object的size. CacheLib由一个DRAM cache和一个flash cache组成. Flash cache由LargeObjectCache(LOC, 为Item大于等于2KB的object服务)和SmallObjectSize(SOC, 为小于2KB的object服务).

allocate函数的作用是从DRAM空间分配内存，对应的就可能会被DRAM中的存在的Item驱逐到flash或者直接丢弃. find函数则会先找DRAM然后LOC然后SOC. 如果是在DRAM中找到则返回的ItemHandle立刻就能使用，如果是在flash中找到则需要异步拉取，对应的Cachehandle会在Item被加载进DRAM会变得可用. 当发生cache miss时会返回一个空的ItemHandle.

DRAM cache. CacheLib在DRAM cache中使用链式hash表进行查找, DRAM cache可以被切分成带有不同eviction policy的pool(在allocate的时候通过PoolId指定).

为了性能考虑cache 内存是通过伙伴系统来分配的. CacheLib使用4MB的slabs并且实现了自己的slab分配器. 每一个slab需要7B(3B给内部元数据，4B用来标识object大小). 对于不同业务来讲每一个slab ckass的大小是可以采用不同配置的(对于小于64B和大于4MB的情况在4.3节讨论对应的优化).

对于不同的Slab系统也可以配置不同的eviction policy(CacheLib也能自定义开发新的policy). CacheLib会在Item上额外使用31B来支持这些对应的policy的配置.

Item metadata DRAM overhead Data type
Eviction policy state 12B 14B timestamp, 24B pointers
Item creation timestamp 4B 4B timestamp
Expiration time(for TTLs) 4B 4B timestamp
Key size + object size 4B 4B size_t
Reference counting 2B 13b public ref count, 3b internal count
hash table chaining 4B 4B pointer
Flags 1B 8 binary flags

为了保证metadata操作的原子性, Cachelib使用了细粒度Lock, 用户空间mutexes, C++院子操作等优化. 比如在LRU场景中，传统的方式里一个object被访问后会被放到most-recently-used的位置(在FB的场景中也很容易发生). CacheLib里每个Item在一段时间T内同一个Item不会被移动到MRU位置. 只要T比object在LRU list里走到尾端(也就是成为最不常用的那个)的时间短，这个方式都能有效的减少移动操作带来的contention. 另外FB也采用了比如flat combining的方式优化.

Flash cache. 从DRAM中淘汰后除了直接删除也可能会写入flash. CacheLib还必须处理flash cell的有限的写寿命.

为了尽量减少写flash的速率，CacheLib会选择性地将object写回flash. 如果一个存在于flash的object在DRAM中没被修改过那么就不会写回flash. 否则CacheLib通过一个admission policy来决定是否写回flash. 默认配置是通过一个概率p来决定是否写回flash. 这个p可以通过对flash的写入速率进行控制.

另一个考虑的因素是写放大(比如在写falsh时除了object的内容还有元数据). 不只是应用层的写放大还有设备层的.

LOC存储的object大小都大于等于2KB，这个大小决定了在LOC中的独特的object的数量大概在百万级，所以可以通过一个内存中的B+树来进行索引. LOC使用分段B+树来存储flash中Item的位置. Items在LOC中的flash page里是4KB对齐的, 所以B+树中的flash location是一个4B的4KB对齐的地址. 也就是说LOC中最多能索引16TB的数据.

LOC使用cache也进一步限制了DRAM index的size. Keys被hash成8B. 前4B表示B+树的segment, 后4B用来在对应segment里查找. LOG 在flash中也会存储整个key的内容，用来在load进DRAM后与进行hash的key进行比较以确定是否找到了对应的Item. 而不同size的object在flash上被存储在不同的partition，所以可以根据flash location直接判断object的size，这样就不需要在元数据里存储object的size了. 为了减少DRAM里存储的address的size，每一个4KB的flash page最多存储一个单独的object和对应的元数据. 因为LOC只存储超过2KB的object，这个策略是很space-efficient的. 因为LOC的read和write都是page粒度的，任何application级别的碎片化都会导致写放大.

LOC的remove是按照region级别进行的。也就是说一下子可以删除一个region上的多个Item(顺序删除，提供删除的性能，也摊平flash erasure的开销). 默认情况下region是按照FIFO的方式进行严格顺序的erase的. 当然也可以采用类似LRU的方式进行region管理.

SOC. 因为SOC都是小于2KB的object，如果还是使用LOC那样的精确查找的方式会消耗非常多的内存，所以SOC采用的是近似索引. SOC将Key映射到不同的set. 每个set表示一个4KB的flash page. 一个flash page能存储多个objects. set中的objects是按照FIFO的顺序进行驱逐的. 为了加快查找效率，cachelib会给每个set在内存中维护一个8B的bloom filter.

在SOC中控制写放大时很有挑战性的. 因为写一条object在flash上就是下刷4KB. 所以SOC需要有先进的admit policy来控制对SOC的写入.

Implementation of Advanced Feature

structured items

CacheLib原生支持arrays和map类型. 同时因为能提供raw access访问cached memory, 平坦的数据结构可以直接用cachelib api访问.

caching large and small objects

大于4MB的object会通过链表的方式将多个Item链到一起组成一个逻辑上的大item(每个item会使用4B的next pointer).

针对小对象还有compact cache的功能用来存储小于cacheline的对象(一般64B或者128B). 相同key size，相同object size的objects会被存储在一个cache line之中. compact cache中每一个cacheline都是通过key hash索引的. cacheline之中会进行LRU. compact cache可以用来处理negative caching(后段查询返回空值的情况).

resource monitoring

Cachelib会监控系统内存使用，系统free内存不足时释放自己的内存.

warm restarts

Cachelib使用POSIX shared memory来满足warmup需要.

Experience and Discussion

New features are adopted by many system

之前为别的cache系统开发的功能越来越多地被移植到cachelib上

Performance improvements help many systems

因为是一套general的系统，在cachelib上的一点点改进在部署方都可能带来很大的收益.

Improved stability

Cachelib作为一个通用系统也避免了以前各种不同实现带来的不稳定性.

No single caching system dominates

Flash caching signals a paradigm shift

有的人可能觉得cache的命中率够高时通过flash增加cache的容量收益不会很大. flash cache和dram cache的混合部署能降低纯DRAM的成本.

另外传统的思路里认为cache只是用来节省磁盘访问时间的，但是考虑到现在的服务结构模式，除了磁盘访问延时以外还有更高的比如网络耗时，后端数据库执行耗时等, 使用flash缓存只要能避免这些耗时操作也是很有价值的.

CacheLib dose not always lead to performance gains

毕竟作为一个通用系统，在面对很多corner case的时候还是很难比经过专门设计和调优的专有系统强的. 但是专有系统的功能可以在之后被添加到cachelib中(.

CacheLib does not work for every use case

一些广告服务依赖于nested 数据结构，这是cachelib不能支持的.