本论文发表于OSDI20, 主要对twitter线上的100多套内存缓存集群进行了详尽的各种指标分支，通过分析各个指标得出了缓存使用的一些最佳实践以及优化方法。通过参考这些分析数据，可以对自身的资源使用有更深入的了解。包括适用场景 性能优化 资源利用率提升等。(同时也印证了另一条道理，没有调查就没有发言权，该句话同样适用于开发和产品，少做些自以为牛逼的功能，少想当然做一些自以为用户会喜欢的产品)。

个人读后概要总结:

1. TTL!!! 最好一定要设置TTL，保证有效数据集的增长边界，不要企图把所有数据都放在缓存里， 命中率的提高是有边界收益效应的。同时通过TTL可以保证最终一致防止脏数据。
2. 尽量限制key的长度提高信息密度。在设计其他系统时也要考虑额外信息造成的信息密度下降。
3. 数据分析方法论，尽量避免采样导致的错误结论，分析数据一定要设置多样本避免单样本异常的偶然性。使用齐夫定律进行测试数据集构建。
4. 大道至简，有时候FIFO 并不比LRU查，可能实现开销还更小。
5. 多做数据分析，通过分析找到瓶颈在定优化方向。

下面为较为详细的半翻译阅读笔记，需要原滋原味的可以看原文: https://www.usenix.org/system/files/osdi20-yang.pdf

摘要

尽管以往已经有很多针对缓存生产系统负载分析，并且推动了提升内存缓存系统效率的研究，但是考虑到实际更加复杂的工业使用场景，这些分析的覆盖面还是不足的。基于此背景，twitter针对他们线上的100多套集群进行了更加详细的分析，包括 流量模式 ttl 流量分布 数据大小等。不同粒度的负载分析表明了使用场景的多样性。通过分析发现有些场景的写入比想象的高更多，流量倾斜也更加厉害。同时还观察到，ttl对工作负载起到重要的影响，同时FIFO 在某些场景写会有更好的性能表现。

简介

现代web服务主要通过内存缓存来提升用户的访问速度，减少对后端存储的请求，以及减少重复的计算。
对比过去多年的分析研究，对于那么多的工作负载场景依然是存在很大的gap的，此外内存缓存的发展也有了新的趋势，其次，有些缓存某些方面的特征受到很少的关注。比如ttl在以往的分析中很少被提及。最后，对比其他领域有完整的开源压测链路信息，内存方面的链路信息很不完善。人们往往依赖于kv存储的链路在进行分析，但是在kv的压测中，往往没有考虑key大小随时间的变化趋势，这个趋势会影响命中率和吞吐。

通过分析，该文主要有如下几个发现：

1. 内存缓存并不都是用于读高写少的场景，此处把写操作比率超过30%的集群定义为 写密集型，通过分析发现有超过35%的集群属于这种类型。
2. 必须合理使用TTL！通过设置ttl可以有效减少整个集群的大小，本文定义 工作集以及有效工作集两个概念，工作集表示集群所使用的总空间，有效集则表示有效的数据，在工作集里面，经常会有大量无用的垃圾数据。此外 必须把使用ttl进行删除放在比通过驱逐淘汰更高的优先级
3. 缓存负载遵循齐夫定律，并且有严重的流量倾斜。
4. 对象的大小并不是一成不变的，对象大小的改变对于memcache这种以slab进行分配的系统带来了额外的挑战。
5. 在缓存大小合理的情况下FIFO 有着与LRU 类型的性能，只有空间被严格限制的时候LRU 才有比较大的优势。

twitter的内存缓存系统

缓存服务架构

2011年twitter就已经使用了微服务架构，与此同时就在开发容器化解决方案，twitter的大部分服务几乎都跑在容器上，作为基础架构的核心组件，twitter在容器上总共部署了几PB的内存缓存以及几十万核的cpu。在twitter内部主要使用了两周缓存系统 Twemcache，memcache的内部fork版本。Nightawk，类似于redis支持丰富数据结构的系统。

Twemcache

Twemcache是由memcache fork衍生出来的并做了一些优化, 在同一个数据中心有接近200套Twemcache集群，tewmcache节点通常很小，一台物理机可以部署非常多的cache实例，每个集群的实例数取决于吞吐 错误容忍率。节点数根据木桶原理进行计算，然后在进一步考虑其他因素。线上的实例数量分布从20-1000都有。

Slab-based内存管理

堆内存分配通常使用ptmalloc或者jemalloc，则会带来内存碎片问题，对于小内存的容器，碎片的问题会被放大的更加厉害。为了避免这个问题，twemcache从memcache继承并优化了基于slab分配的内存管理算法。内存根据大小切分为不同的chunk class。和memcache的主要区别在于memcache的数据淘汰是基于slab内部的lru，而twemcache则是基于整个全局的slab进行淘汰。

slab-based

基于Slab-based的数据淘汰

当写入新数据的时候，twemcache会计算该对象的大小，然后寻找合适的slab，如果找不到合适的slab，则重新分配一个slab到这个slab class内部，当内存不足时，则进行slab的淘汰。

memcache每一个slab会有一个lru进行淘汰，当数据大小变化不大的时候该分配没啥问题，但是如果集群内存出现大量小value忽然变为大value，新的数据会被分配到更大的slab class当中。当时由于内存已经被分配给了小的slab class，导致出现slab 钙化。mc设计了一系列的slab均衡移动算法，然而这并不是最优的。

为了避免slab 钙化，twemcache直接对整个slab进行淘汰并可以直接归还给全局slab管理然后分配别其他的slab class。twemcache支持三种不同的slab淘汰策略，分别是 随机 slabLRU slabLRC。

此外slab based还减少了每个对象直接用户保存LRU信息的链表指针。

缓存使用场景

缓存使用场景主要包括：后端存储缓存 计算结果缓存 临时性数据

• 存储缓存层: 用于提升吞吐降低延时，也是在各种研究中最受关注的，主要关注点为提高缓存命中率，在集群中占比为30%，但是占据了65%的流量和60%的空间以及50%的cpu
• 计算结果缓存: 实时流计算以及机器学习存储中间计算结果。占集群数50%。占据26%的流量 31%的内存和40%的cpu
• 临时性数据: 这种数据没有后端存储，通常有较短的过期时间，允许数据丢失。通常用于限速，去重。占集群总数10%，占据9% 流量 8% 内存和10% cpu

resources consumed

分析方法

日志收集

使用内置的异步日志组件klog进行日志收集，默认的日志采样为1%，做该分析的时候关闭了每个集群两个节点的采样率，避免因为采样造成的分析误差，选择两个节点可以避免意外故障导致的偏差，屏蔽了缓存节点偶发故障的问题。 数据分析的时候要采样采样和缺乏对照组造成的误差

日志分析概览

总共从153个集群的306个节点采集了80T 的数据，请求量超过7000亿。其中最大的54个集群占据了90%的流量和70%的空间。后续的分析主要基于这54个大的集群。

负载分析

命中率

请求量最大的10个集群，有8个命中率超过95%，6个超过99%。除了一个写负载型的进群命中率低于30%。对比CDN缓存，内存缓存有着更高的命中率。

除了高命中率，命中率的稳定性也非常重要。最低的命中率决定了最大可能有多少流量穿透到后端存储。

高命中率与高稳定性对于在线系统的性能表现特别重要。然而，极高的命中率有时确是不鲁棒的，缓存的维护以及缓存故障很容易造成服务的中断。

qps以及热key

分析表明，qps和时间强相关，此外qps还有着严重的尖峰，因为前端服务和用户的所有行为都会直接反应到缓存层。

负载尖峰通常是由于热key导致，然而这并不总是对的。客户端的失败重试，周期性任务，以及外部流量的增长都可能导致qps尖峰。

qps尖峰往往表现的很不规则。社会热点，前端的bug或者内部压测都可能导致qps的尖峰毛刺。

作为基础架构的核心组件，缓存阻拦了大部分请求对后端的冲击。因此设计上缓存必须能容忍突发的异常流量导致的负载变化，减缓对后端的影响。

操作类型

支持set get cad cas delete incr等命令，但是get和set的占比超过90%

• 写比例 超过35%的我集群是写密集型，超过20%的集群写占比超过20%
• 频繁更新的数据 主要是缓存计算结果和临时性数据
• 概率预测填充 有些服务当用户需要的时候才去读取相关数据，预测模型可以提前将数据填充聚合到缓存，用户请求的时候直接返回集合，有点类似于磁盘的readahead机制。

TTL

使用场景

ttl的设置从分钟到天都有，超过25%的数据ttl短语20分钟，ttl超过2天的不到25，缓存中的ttl通常比dns短，但是比CDN长。如果把ttl超过12小时定义为long-TTL，那么超过66%的集群属于short-TTL集群。

设置缓存主要有以下几个优点

• 最终一致 业务更新缓存失败的时候通常不会重试，这可能导致缓存里的数据是未被更新的脏数据，如果设置了ttl，那么最终缓存数据会被淘汰重试数据最终一致。 twitter内部还是先了soft-ttl，实现为将ttl设置为value的一部分，读取的时候由业务解析ttl判断该数据是否还有效。当value里的ttl小于某个值时，业务可以继续使用这个数据直接响应同时后台异步去刷新该缓存。该方式在facebook之前的一篇论文 Scaling Memcache at Facebook 里提到过，不过facebook的实现为伪删除。
• 隐式删除 主要用户限流，每一个时间周期设置一个计算器用来做api限流
• 周期性刷新 对于一些推荐场景，需要保证推荐数据的新鲜度，通过过期来触发推荐系统更新推荐数据。

TTL与有效数据集

让大多数数据使用ttl可以限制有效数据集WSSe的边界，相反，如果不设置ttl那么总数据集WSSt则会无限增长，设置ttl的时候则可以有效控制缓存的规模。

通过设置ttl，可以让活跃用户的数据仍然留在缓存内，非活跃用户的数据则会被淘汰。数据表名，当缓存规模达到一定大小以后，命中率几乎不会继续增长，存在明显的边界效益。合理设置ttl可以提高缓存的性价比。

数据大小

在某些场景，对象的大小存在周期性的变化以及突变的情况。

• 对象大小分布 85%的集群value小于50字节，中位数小于38字节，有些集群key的大小比value还大。因此在设计缓存的时候，需要合理设计key的长度提高有效信息比。
• value大小的变化， value的大小变化可能导致slab分配导致slab钙化。

淘汰算法

介绍了FIFO LRU slabLRU slabLRC 以及随机五种淘汰算法，twemcache使用基于slab的淘汰算法，减少了内存碎片问题，同时也减少了metadata的开销。出乎意料的是，随机淘汰竟然有着不错的性能表现。

命中率对比

twemcache默认使用slab随机淘汰算法，大道至简而且还不需要metadata开销。

有意思的是，在某些场景，FIFO 表现的比LRU好。对于有些存在间隔性访问的场景，FIFO 可以防止一些数据被淘汰，比如定期发送邮件的场景。数据访问频次曲线越光滑，LRU 的性能会更好。同时，命中率和空间大小成正相关，因此减少metadata的提升存储率，对数据进行压缩等都可以提高数据存储量从而提高命中率

inter-arrival gap

当缓存空间没有被严格限制的时候FIFO和LRU 几乎没有区别，当空间严格受限的时候，LRU 表现的比FIFO更好。在大多数生产场景下，LRU表现的和FIFO 差不多,但是在FIFO 性能更好开销更好，比如在memcache的实现里，LRU 需要额外的元数据和锁，FIFO则不用。

启发

• 写负载优化: 写负载型缓存通常用于缓存计算的结果，随着机器学习和推荐场景的增多，写负载型的缓存将被用的更加频繁，目前针对这方面的研究比较少，然后确实不可或缺的一种场景
• TTL淘汰优化: 目前对于TTL过期的数据淘汰比较低效，除了在访问的时候判断是否过期主动淘汰，通常使用后台线程进行扫描，这样做淘汰的效率非常低，需要对淘汰周期进行权衡，主要需要综合考虑CPU 内存空间和内存带宽之间的平衡。针对这方面的优化应该是以后的一个研究方向。（注: Segcache: a memory-efficient and scalable in-memory key-value cache for small objects 这篇twitter随后2021发表在NSDI的论文详细介绍了针对这种场景的优化）
• 对象大小优化: 由于很多场景value的大小都很小，如果object本身的metadata较大，则信息存储信息密度则非常低，因此应该减少metadata的开销从而提高信息密度。同时，合理设计key减少key的长度也能有效提高信息密度。这一方面的优化同样也在随后的论文segcache实现了。

结论

1. 关注写负载型场景并进行优化调研
2. 使用ttl减少数据集大小，优先考虑使用ttl进行淘汰而不是根据空间进行驱逐
3. 读负载型的数据存在严重倾斜，需要针对热点进行优化
4. 数据大小是动态变化的，需要对slab-based分配算法的slab迁移进行优化
5. 对于相当数量的场景，FIFO有着与LRU相似的性能