『看看论文』是一系列分析计算机和软件工程领域论文的文章，我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文，这里不会事无巨细地介绍所有的细节，而是会筛选论文中的关键内容，如果你对相关的论文非常感兴趣，可以直接点击链接阅读原文。
本文要介绍的是 2021 年 NSDI 期刊中的论文 —— Segcache: a memory-efficient and scalable in-memory key-value cache for small objects1，该论文实现的 Segcache 使用基于数据段的设计存储和管理缓存数据。Segcache 使用数据段（Segment）组织缓存中的数据，它会在固定大小的数据段中存储数据并提供以下三个特性：
- 将创建时间和过期时间相似的对象分组存储；
- 将每个对象的元数据合并存储到数据段头中；
- 以数据段为维度执行批量过期和驱逐操作；
架构设计
Segcache 在架构设计上主要遵循如下所示的三大设计原则：
- 主动移除内存中过期的对象，提高内存的利用率；
- 在不同对象之间共享元数据，保证功能的同时减少元数据带来的额外开销；
- 在段的维度上批量过期或者驱逐对象，提高锁的粒度；
如下图所示，该系统主要由 TTL 桶、对象存储和哈希表三个部分组成：
图 1 - Segcache 架构设计
- TTL 桶：将对象可能的存活时间划分成不同的范围（
t1~t2），所有范围内的对象都会拥有t1的存活时间，这种方式可以保证所有的对象只会被提前回收，不会超过它的过期时间；每个 TTL 桶都会持有一组数据段，这些数据段会首尾相连并按照时间顺序进行排序； - 对象存储段：Segcache 使用数据段作为数据存储的基本组成单元，每个数据段中的对象都有着近似的存活时间，数据段中的数据不会更新，新的对象仅会追加到每个数据段的结尾，所有的数据段都会通过指针与前后的段相连接；
- 哈希表：每个哈希桶分配 64 字节的内存存储八个对象，其中的第一个槽会存储当前桶的信息，随后的六个槽存储对象信息，最后的槽会存储对象信息或者指向下一个哈希桶的指针；
从这三个不同组件的设计我们可以看出，这些不同的组件都在不同程度上使用了分组的理念，分组策略更利于批量处理系统中的对象，提高整体的吞吐量和水平扩展性。
元数据
常见的缓存系统为每个对象带来额外开销，例如 Twitter 的缓存系统会为每个对象引入 50 ~ 300 字节的开销。Segcache 在内存利用率方面也明显优于其他的缓存系统，它通过在对象之间共享元数据实现较低的元数据额外开销。该系统会在两个不同的组件中利用元数据的共享功能，也就是哈希表桶和数据段中。
- 同一个数据段中的对象会共享创建时间、存活时间、引用计数；
- 同一个哈希桶中的对象会共享最后访问的时间戳、自旋锁、
CAS值和哈希指针；
因为 Segcache 会以数据段为维度计算整个数据段的过期时间，所以它会基于整个数据段中最老的数据驱逐整个段，这也会导致部分对象会提前被清除，然而在生产环境中，这种提前过期的行为对缓存的丢失率没有明显的影响。按照数据段管理的方式不仅会影响对象的驱逐，缓存的过期和驱逐都发生在数据段的层面会使得 Segcache 将引用计数移到数据段层面进行管理。
过期和驱逐
Segcache 会通过过期和驱逐两种不同方式删除系统中的数据，这两种方式分别实现了不同的目的。
图 2 - 主动过期和段驱逐
- 主动过期：整个数据段中的数据过了约定的存活时间，系统会使用后台的线程扫描 TTL 桶中的数据段；
- 数据段驱逐：系统中的空间不足以分配新的数据，这时需要驱逐一些数据为新对象腾出空间；
主动过期
因为同一个数据段中对象都是线性写入的并且具有类似的存活时间，在这种情况下批量删除过期的数据会很合理。主动删除过期的对象会从头扫描 TTL 桶，而在链表最前面的数据段总是会最先过期。
Segcache 的主动驱逐机制会合理利用机器的内存资源，每次对内存的扫描都只会访问一小块连续的元数据，这种策略可以保证过期的对象能够被及时地、彻底地回收，提高内存的利用率。而在生产环境中，该策略对缓存丢失率造成的影响微乎其微。
数据段驱逐
数据段的驱逐能够为新的缓存制造出足够多的空间，因为 Segcache 不会原地更新缓存中的对象，它会创建新的对象并将原对象标记成删除，所以更好的驱逐策略会变得更加关键。
因为 Segcache 会以数据段为单位驱逐，所以会提高缓存的丢失率。为了解决这个问题，Segcache 会使用基于合并的驱逐算法，它会组合内存中的多个数据段、选择其中会经常访问的一小部分对象并驱逐余下的对象。
总结
我们可以发现批处理在 Segcache 起到了很关键的作用，该系统以数据段为单位组织缓存中的数据，数据的过期和驱逐都是以数据段为单位批量进行的，这种策略虽然牺牲数据过期时间的准确性，但是提高了系统的吞吐量以及水平扩展性。
Segcache 在生产环境中可以减少 22 ~ 60% 的内存使用，单线程提供的吞吐量也比 Memcached 好 40% 左右。与此同时，因为 Segcache 具有良好的水平扩展性，它在 24 线程下的性能会比 Memcached 好 8 倍。
推荐阅读
Mingyang Zhang, Radhika Niranjan Mysore, Sucha Supittayapornpong, and Ramesh Govindan. 2019. Understanding lifecycle management complexity of datacenter topologies. In Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation (NSDI'19). USENIX Association, USA, 235–254. ↩︎
转载申请
本作品采用知识共享署名 4.0 国际许可协议进行许可，转载时请注明原文链接，图片在使用时请保留全部内容，可适当缩放并在引用处附上图片所在的文章链接。
Go 语言设计与实现
各位读者朋友，很高兴大家通过本博客学习 Go 语言，感谢一路相伴！ 《Go语言设计与实现》 的纸质版图书已经上架京东，本书目前已经四印，印数超过 10,000 册，有需要的朋友请点击 链接 或者下面的图片购买。
