VLDB 2023 | Catalyst：优化大型内存键值系统的缓存管理

内存键值缓存系统（例如 Memcached 和 Redis）在当今的数据中心中至关重要。此类缓存系统的一个关键任务是识别最有价值的数据进行缓存。为了实现这一目标，需要跟踪每个键值项的访问，以实现最高的缓存命中率。然而，随着缓存容量的不断增加，管理大量小型键值项的开销上升到难以承受的水平。如何对此进行优化以实现更好的可扩展性呢？今天分享一篇数据库领域顶级会议VLDB的论文：《Catalyst: Optimizing Cache Management for Large In-memory Key-value Systems》

问题背景

近年来，我们目睹了前所未有的数据爆炸式增长，这其中有很大一部分数据是以键值形式存储的非结构化数据。为了提供高吞吐量和低延迟的服务，互联网服务提供商依赖于内存键值缓存如Memcached和Redis来处理大量的键值查询。内存键值缓存系统被广泛采用的一个重要原因是随着内存技术的快速发展，内存的价格已经显著下降。内存硬件技术的巨大飞跃使我们能够构建大型内存键值缓存系统，以容纳更多数据到内存中，实现高速数据访问。然而，它也给我们带来了一个关键的挑战——随着内存容量持续增长，我们该如何以高效的方式管理大量的小型键值项呢？

内存键值缓存系统的核心是缓存空间管理。它负责识别和缓存内存中最有可能被重用的（热）数据，同时排除不太可能再次被访问的冷数据。这个缓存决定对系统性能有直接影响。因此，实现高命中率是键值缓存系统设计中最重要的目标之一。为此，缓存系统密切跟踪每个键值项的访问历史，用以估计它们的重要性。然而，要实现这个目标会带来一定的开销。例如，Memcached采用了一个简单的基于LRU的替换策略。当缓存容量很小时，它工作得很好，但不幸的是，随着缓存容量的快速增加，即使是这样一个看似简单的方案也很难扩展。在作者的实验中，如图 1(a)所示，对于一个100GB的内存缓存系统，禁用LRU替换反而可以让性能提高3.3倍，这表明在大缓存容量下大量元数据的操作开销是不可忽视的。

图 1 内存缓存中的元数据操作开销

为了进一步研究这种不寻常的性能差距，论文接着具体分析了查询处理过程中各个操作的开销。图 1(b)统计了哈希表操作的平均时间、键值数据加载、LRU指针更新，以及锁等待时间。其中与LRU元数据操作相关的成本随着数据集的大小而急剧增加。尽管花在操作LRU指针上的时间仅从1.23𝜇s略微增加到1.46𝜇s，但由LRU结构操作引起的锁等待的时间增加了6.4倍，从0.9𝜇s增加到5.8𝜇s。因此，对缓存的元数据操作的高开销是影响最终效率的重要原因。除了延迟增加，有限的CPU资源也面临严重的竞争。在图 1(c)中，可以看到元数据操作会对CPU缓存命中率产生负面影响，使得已经稀缺的片上缓存空间更难被服务操作访问，其中服务操作主要负责处理客户端查询和检索所需的数据。

分析讨论

上述实验结果表明，键值缓存管理中的元数据操作对性能和可扩展性都有强烈的负面影响。这里，论文列出了当前高速缓存系统设计中的几个固有的关键问题：

1）关键路径上的元数据操作：为了区分热键值项和冷键值项，传统的缓存管理需要维护特定的元数据结构来跟踪每个项的访问。例如，维护一个全局LRU链表。在每次访问时，它需要对整个链表加锁以确保结构的完整性。随着数据集大小的扩大，每个LRU链表中包含的条目数量也会增加，频繁的结构变化自然地加剧了锁的争用。因此，元数据更新的成本迅速增加，更糟糕的是，这些非必要的、高成本的元数据操作都是同步的，导致这些延迟位于主服务操作的关键路径上。

2）元数据的串行操作：由于链表操作的性质，在每一轮更新中只能进行一次更改。因此，即使在系统中存在许多元数据操作，也必须串行地逐个执行对LRU链表的更新。这种结构从根本上就不能以并行的方式执行频繁的元数据操作。

3）内存资源开销。传统的缓存系统设计通过一种过于细粒度的方式，通过将每个单独的数据项附加到特定的元数据中来管理键值缓存项。假如每个项占256字节，在1TB内存缓存中，LRU元数据本身就需要超过64 GB的内存空间，这些空间完全可以用以容纳更有意义的数据。

4）计算资源开销。在内存中的键值缓存系统中，处理客户端查询和更新每个被访问项的元数据都会消耗CPU资源。在内存缓存中，每个键值项访问涉及对LRU元数据的更新至少涉及五个内存操作。相比之下，加载键值数据只需要一次内存访问。这些元数据操作不仅与服务操作竞争CPU周期，而且还争夺非常有限的片上缓存空间。

因此，论文提出了Catalyst，一种高效的内存键值缓存系统设计。1）Catalyst将高速缓存管理的元数据操作从关键路径中删除，允许查询在完成基本的服务功能（例如，索引和数据加载）后立即返回，与缓存相关的元数据操作以异步的方式执行。2）Catalyst将元数据组织在一个紧凑的并行结构中，可以并行更新和查询以获得高吞吐量。这确保了元数据操作不会随着缓存大小的增长而成为瓶颈。3）Catalyst将元数据操作（维护工作）与常规服务操作（真实工作）分离，将维护工作脱离CPU，以避免对有限的CPU资源的竞争，最大限度地减少干扰。4）也是最重要的一点，Catalyst放松了对高速缓存的精度要求，因为在一个非常大的键值缓存中，严格遵循寻找和驱逐“最冷”项的规则是过于昂贵和不必要的。而Catalyst的目标是仅仅确保热数据和较热的数据保存在缓存中。这种对缓存需求的放松使得Catalyst能够以较小的命中率损失来实现更高的效率。

方法介绍

在本节中，我们首先介绍一种新的数据结构，用于以低开销跟踪大量的键值项，使键值缓存能够在不降低性能的情况下进行扩展。然后介绍更新元数据结构的过程，以及如何执行一个替换算法来做出驱逐决策。

组织键值元数据的数据结构

一个大型键值缓存系统通常需要管理数十亿个键值项。试图准确识别“最冷”的数据是不现实的，也没有必要。因此，论文提出了一个紧凑的、可并行的结构来代替LRU算法，称为哈希计数器。受布隆过滤器启发，哈希计数器是一个基于哈希的位数组（见图 2），具有𝑁个哈希函数，每个键会被映射到位数组中的_N_个位。该位数组初始化为零。在访问时，键映射到的𝑁位被设置为1。给定一个键，如果它对应的𝑁位都被设为1，称这个键被“标记”。尽管哈希冲突的可能性非常小，但哈希计数器可能会报告假阳性结果（未被标记的键被错误地报告为已标记），但它保证不会出现假阴性（已被标记的密钥被报告为未标记）。

图 2 哈希计数器

哈希计数器结构虽然简单，但它有几个重要的优点，使它特别适合于处理元数据操作。首先，它摆脱了受锁保护的链表结构，这从根本上消除了锁争用问题和串行执行元数据操作的严格要求。第二，该结构与键值数据本身是分离的，这允许我们在更新元数据时无须读取键值数据块，从而异步和批处理元数据，从而将不必要的维护工作从关键路径移除。第三，该结构还显著地减少了元数据的内存开销。最后，独立的位数组和基于哈希函数的结构使我们能够轻松地将元数据操作从CPU移动到更合适的设备GPU上。

哈希计数器可以帮助我们区分相对热和冷的项目——在哈希计数器中有标记的项目是热的，而没有标记的项目是冷的。可以基于哈希计数器实现一种基本的高速缓存替换机制。然而，此时只能做出二元决策，因为我们只能确定数据项是热的或冷的，它不能进一步区分热的和暖的数据。因此还需要一个更细粒度的结构以有效地近似LRU替换。

Hitmap

论文接着引入了一种多层位数组，称为Hitmap，能更细粒度地区分键值项的温度。如图 3所示，Hitmap集成了𝑀层哈希计数器（图中为4），每个计数器都有不同的大小。

图 3 Hitmap以及Catalyst的结构

最初，所有的哈希计数器都被重置为零，当某个键被访问时，Catalyst将它从最低层到最高层的顺序插入（标记）到Hitmap中。首先检查第一层哈希计数器。如果所有的映射位均为0，这意味着该键从未被访问过，此时将对应所有映射位设置为1来标记访问；如果所有映射位都已被置为1，这意味着该键至少被访问过一次，那么继续进入下一层进行检查。这个过程不断重复，直到到达所有映射位均未被置1的层或最高层。

Hitmap基本上记录了被查询的键的访问计数（最高为𝑀）。例如，在一个4级Hitmap中，如果可以在第1级和第2级中找到该键，则它的访问计数为2。如果一个键在所有4个级别中都呈阳性，那么认为这个键至少被访问了4次。冷数据往往在较低的层，而热数据往往在高层。这时我们就能够做出更准确的驱逐决定，以保护热项目，同时驱逐冷项目。

Hitmap的一个简单组织方式是不同层的哈希计数器具有相同的大小。为了减少Hitmap结构的内存占用，Catalyst将多层Hitmap组织成“倒金字塔”形状，底层哈希计数器最小，顶层最大，每个级别的哈希计数器大小是它下面的级别的两倍。选择2：1的比例的原因将在下面介绍。

Rolling Compaction

填充率（位数组中1的占比）会影响Hitmap的效果。由于基于散列的位数组的性质，多个键可以映射到同一个位。因此，一旦将某位置1，就不能再将其置0。随着哈希计数器的填充率的增加，热项目和冷项目变得难以区分，这将影响做出适当的驱逐决定的能力。

该问题可以通过简单地通过定期重置哈希计数器来缓解。但是，在重置后，哈希计数器中的所有位变为零，丢失以前记录的所有访问历史，这是不可接受的。论文因此设计了一个rolling compaction方案来解决这一挑战。工作原理如下：

如前所述，多级Hitmap结构记录了键值项的访问计数。在第𝑚级哈希计数器中存在一个键表示该键已被访问至少𝑚次。在rolling compaction过程中，Catalyst将每个哈希计数器向下移动一级，并删除第1级哈希计数器。它本质上将每个键的访问数减少1，并驱逐所有访问次数为1的键。

该方案的挑战在于如何在不丢失访问信息的情况下，将一个较大的上层哈希计数器压缩成一个较小的下层哈希计数器。由于我们不能将一个哈希位反向映射到原始键，所以就不可能重新运行哈希映射过程来逐个设置这些位（即使这样做可行，成本也会太高）。

在之前介绍到，Catalyst将第𝑚级哈希计数器设置为第𝑚-1级哈希计数器的两倍大小。这是一个有意的设计，这样能够将哈希位项映射到更低的级别，而无需重新计算哈希值。由于Catalyst在所有层上使用相同的一组哈希函数，因此用于映射生成的哈希值是相同的，此时就可以将两个位使用OR操作合并为一个位，并在较低层的哈希计数器中置对应位为1。如图 4所示，Catalyst简单地将原来的2级位数组的前半和后半部分合并变成一个只有一半大小的新位数组。新的1级哈希计数器本质上是原来的2级哈希计数器的紧凑版本。它将较高级的哈希计数器缩小到较低级别，但仍然保留部分访问信息。

图 4 Rolling Compaction过程示例

在每一轮Rolling Compaction过程中，首先创建一个如上所述的2级哈希计数器的压缩版本，以替换当前的1级哈希计数器，然后进入第3级，重复相同的过程，直到达到顶层。最终顶层的哈希计数器将被重置，而较低层仍然保留从上层向下滚动的访问信息。

Catalyst中的元数据操作

在Catalyst中，处理Hitmap结构更新和查询的元数据操作是异步的，并与处理客户端请求的主服务操作分离。Catalyst采用GPU作为处理元数据操作的硬件加速器。主要有如下两点原因：首先，Hitmap结构基于位数组和散列映射，这使得元数据操作简单且可并行化，这种操作特别适合并可以高效地在GPU上运行。其次，将元数据操作移到到GPU在物理上将非必要的维护工作与服务操作分离，将有限的CPU资源用于“真正的”工作。在本节中，将介绍Catalyst中的三个主要操作，即在设备之间传输数据、更新Hitmap中的元数据，以及做出驱逐决策。

数据传输

在Catalyst中，客户端请求由主工作线程处理。每次访问都应该传递给GPU，以更新Hitmap，为稍后的驱逐决定做准备。一种简单的方法是将每个被访问的键分别发送到GPU。该策略存在如下三点问题：首先，系统需要在内存中固定一个内存页面（通常是4 KB），以便通过直接内存访问（DMA）将数据传输到GPU。然而，与页面大小相比，单个键的大小往往太小了。其次，缓存系统需要对每个设备间的数据传输进行系统调用，从而为CPU增加了更多的开销。最后，GPU是一种高吞吐量的计算设备。单独处理每个键并不能很好利用它并行计算的优势。

为了充分利用PCIe带宽和GPU的计算能力，Catalyst使用_reference pool_来收集一组被访问的键，批量发送给GPU。为了减轻内存传输中的开销，Catalyst将_reference pool_保存在指定的固定内存块中。每个_reference pool_都是一个固定在内存中的4kb的页面。因此，内存块随时准备好进行传输，这就避免了预处理的开销。另一个优化是不直接发送键，而是将键的散列信息发送到GPU。

Hitmap更新

在Catalyst中，键的访问信息被分批发送到GPU以更新Hitmap。当GPU接收到一批键后，它将作业均匀地分布在所有流多处理器（Sms）上，以并行更新元数据。具体的更新流程可参考图 3。

做出驱逐决定

在之前已经提到，热数据往往集中在Hitmap的较高层级，冷数据往往集中在较低层级。Catalyst根据键在Hitmap中的位置，将其划分为不同的温度区域。例如，一个4级的Hitmap，会被分为5个温度区域，从最热的（level 4）到最冷的（level 0）。如果在4层的哈希计数器中找到了一个键，则将其放置在区域4中；如果在任何级别中都未找到某个键，则将其放置在区域0中。Catalyst总是首先驱逐放在区域0中的键。

为了做出驱逐决定，Catalyst随机抽取一组键，并将它们与一批被访问的的键一起发送到GPU。抽样键的数量被设置为等于被访问键的数量，这是为了确保有足够数量的候选受害者被检查被驱逐。在所有操作完成之后，采样键及其温度信息被发送回主机CPU，然后主机CPU进行驱逐操作。

实验

实验平台：作者实现的Catalyst基于Memcached，运行在W2600CR服务器（两个8核英特尔Xeon E5-2690 2.90 GHz处理器，128GB内存，NVIDIA GTX 1050 Ti GPU）上。使用两台联想TS440服务器(4核Intel Xeon E3-1245 3.4 GHz处理器，16GB内存，1TB 7200RPM的希捷磁盘)作为客户端，每个服务器模拟64个并发客户端来发送查询。后端数据库为MongoDB 4.2，运行在戴尔T620服务器（6核英特尔Xeon E5-2630 2.3 GHz处理器，32GB内存，4TB 7,200 RPM的希捷硬盘）上。操作系统为Ubuntu 20.04。CUDA C代码使用nvcc在CUDA 9.2下编译。

数据集：键值数据的内容与该研究并不是十分相关，作者使用了随机数据。其分布遵循[2]中涉及的数据集APP、SYS和ETC的大小分布。

查询负载：使用YCSB[1]生成具有四种访问模式的工作负载：Zipfian、Hotspot，Latest和Uniform，以模拟不同的工作负载。

整体性能

如图 5所示，Catalyst是非常高效的，能够在很低的开销下达到与LRU相近的性能。对于给定的内存空间，Catalyst能够缓存比Memcached更多的键值项以获得更好的性能。如图 5(a-c)所示，在Zipfian工作负载下，Catalyst的命中率比Memcached高7.3%。即使在具有类似命中率的情况下，Catalyst也能够以更高的吞吐量处理请求（图 5(d-f)）。由于高效的元数据管理，Catalyst的吞吐量相对其它方案提高了23%-333%。图 5(g-i)显示了延迟的结果。与Memcached相比，Catalyst减少了第50百分位的总体延迟（由粗条表示）高达20.6%。第99百分位的总体延迟（由线条表示）没有显示出显著的差异，因为它主要由缓慢的后端数据库而不是缓存机制决定。

可扩展性

图 6展示了六个缓存系统的可扩展性的比较。数据集的大小范围从80 GB到1 TB，键值缓存配置为固定的10%缓存比，从8 GB到100 GB不等。尽管缓存比率是固定的，随着系统的扩展，命中率在很大程度上保持不变，但总体吞吐量发生了显著变化。

在该实验中，Memcached的吞吐量下降了50%，而Catalyst的吞吐量在Zipfian工作负载上只下降了5.1%，在Hotspot工作负载上下降了6.1%，显示了其更好的可扩展性，而MemC3和Redis的吞吐量分别下降了23.8%和38.9%。这清楚地表明，Catalyst可以随着数据量的增长而良好地扩展。

GPU硬件资源

Catalyst需要GPU硬件资源来处理元数据，以做出驱逐决策，本节主要介绍GPU的显存大小和计算能力对Catalyst性能的影响。CUDA提供了对统一内存的支持，因此在GPU显存不足时，可以使用系统内存作为补充。当GPU显存不足以容纳整个Hitmap时，这可能是有益的。如图 7(a)所示，使用统一内存的Catalyst表示为Catalyst-Uni。结果表明，在使用统一内存时，与在GPU内存中完全存储所有元数据相比，其吞吐量下降了7.5%，但仍然显著优于Memcached。

Catalyst展示了它通过低成本的入门级GTX 1050Ti GPU有效管理键值缓存元数据的能力，按照今天的标准，这是一个“过时的”设备。为了评估使用一个更强大的GPU的效果，作者用一个RTX 2080 Super取代了GTX 1050Ti。有趣的是，尽管CUDA核的数量从768个增加到3072个，但在图 7(a)中，两种设备之间的吞吐量差小于2.2%。尽管由于可用的核心增加，RTX 2080 Super的平均GPU使用率减少到25.2%，但GTX 1050 Ti上的计算资源也没有得到充分利用（使用显存时为68.7%，使用统一内存时为63.2%）。这些结果表明，Catalyst不需要昂贵的高端GPU。

总结

本文介绍了Catalyst，一个可以使用较低内存和CPU开销来有效管理内存键值缓存系统中大量元数据的方案。Catalyst通过轻量的Hitmap来缓解现有缓存方案过于细粒度的元据管理方式，并通过将Hitmap的更新等操作移动到GPU以进一步提升并行处理的能力以及与主服务进程分离。实验结果表明，Catalyst可以以较低的开销显著提高内存键值缓存系统的性能。

参考文献

[1] Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC ’10). 143–154.

[2] Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. 2012. Workload analysis of a large-scale key-value store. In Proceedings of ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’12). 53–64.