专为流式数据设计的另一种缓存：流式缓存技术解读

1 前言

传统的缓存解决方案将每一个缓存项都当作一个不可变的数据块对待，这在重度追加的注入工作负载上会产生很多问题，而这种模式的负载在 Pravega 上却非常常见。每一个追加到流上的事件因此要么需要有它自己独立的缓存项，要么需要缓存提供昂贵的“读取-修改-写入”操作。

为了能够做到对大小事件的注入都保持高性能 [1]，同时提供近实时的尾端读取（Tail Read）和高吞吐量的历史读取（Historical Read），Pravega 需要一种特殊的缓存以便能够原生支持流式存储系统上常见的工作负载。

流式缓存（Streaming Cache），在 Pravega v0.7 [2]被首次引入，是一个从头设计的缓存。它专门针对流式数据并且为追加操作做了优化，同时将数据组织成一种有利于缓存淘汰和磁盘换出的结构。

并非所有的缓存都生来平等。而最重要的原则是选择适用于所应用系统的那种缓存，而这一原则对流式解决方案来说也不例外。在这篇文章中，我们会详细描述一种创新的缓存方案，它在流式用例上能够良好运作。

2 段存储如何缓存数据

段存储（Segment Store） [3]是 Pravega 中所有数据路径操作的核心。它处理所有注入事件，提供近实时的尾部读取和高吞吐量的历史读取。所有经过段存储的数据都最终路由经过读取索引（Read Index），它为一级存储和二级存储上的数据提供一种统一的视图。

在追加路径上 [1]，事件被持久化到一级存储，而后被加入读取索引。尾部读取的数据完全来自缓存，而历史读取的数据则从二级存储预取并按需暂存在读取索引中。读取索引的双重作用在于服务来自 EventStreamReader [4]的读请求和作为数据源将数据移动到二级存储上。因此，单从操作的数量上说，它必须能够并发处理大量的更新和查询，并尽可能减少 CPU 和内存的使用。

每一个活动的段都有它的读取索引，这是一种定制化的，位于内存中的平衡二叉树（AVL Tree） [5]，将段偏移映射到缓存项。我们需要一个有序索引帮助定位那些包含但并不以给定偏移起始的项，并且还需要一棵平衡树来确保插入和查询时间保持相对恒定。

图 1 经过读取索引的数据流。 1）追加数据在持久化到一级存储后被发送到读取索引；读取索引因此插入或更新缓存项。2）尾部的 Reader 从缓存读取；读取索引执行查询并获取数据。3）历史 Reader 可能引发缓存未命中，在这种情况下，一个较大范围的数据被从二级存储预取并插入缓存；后续的读取则有较大概率命中缓存。4）缓存管理器（Cache Manager）定位出 E8 为最近未使用项并将其淘汰；执行缓存移除操作。图例：在读取缓冲中，A…B: {C, D}表示偏移 A 到 B 被映射到缓存项 C，并具有代数 D（分代用于缓存淘汰）。

3 为何不使用传统的缓存

作为最低要求，读取索引需要一个缓存组件并支持插入，获取和删除操作。对这样一种缓存，感性上可以选择一种支持传统键/值 API 的数据结构。Pravega 直到 v0.7 之前也确实一直是这么做的。每个读取索引项都指向一个由一对键/值组成的缓存项。尽管从功能上说确实能够正确运行，但这样一种缓存实现在段存储工作负载下的性能却不尽如人意，已经成为整个系统上的一处瓶颈。

在流式处理中一个非常常见的操作就是将数据追加到某一个段上。理想情况下，我们需要更新读取索引，将事件的内容字节追加到最后一个缓存项上，而不是为每一次追加都创建一个新项。然而，读取索引项被一一映射到缓存项，如果缓存本身不允许修改已存在的项（不可变的特性简化了许多场景），那么这里几乎无法做进一步提升了。对追加操作我们仅有两种选择，要么创建一个新项，要么每次进行昂贵的“读取-修改-写入”操作（读取最后项的内容，为已有内容和追加内容分配一个新缓冲，然后把新缓冲重新插回缓存中）。这两种选择都会产生副作用，导致过量的内存和 CPU 开销，这都不是高性能系统所期望的。

所有的键/值缓存都需要实现某种索引以便把键映射到值。无论是基于简单哈希表的内存缓存，还是更复杂的使用 B+树 [6]或者 LSM 树 [7]的磁盘可换出缓存，维护这一索引都有开销。然而，如果我们后退一步看一下读取索引，我们就会注意到我们其实并不需要这些额外的数据结构：平衡二叉树已经把段偏移映射到缓存项了。根本没有必要再维护一个额外的索引来映射缓存项到缓存的内部。一个简单的内存指针就足够了。

当我们最初发布 Pravega 的时候，RocksDB [8]是我们对缓存的选择。尽管它是一个优秀的本地键/值存储并提供诸多特性，Pravega 并没有使用这些特性而仅仅将 RocksDB 用作一个堆外缓存，使得过量数据可以在必要时换出到磁盘。然而，在容器化环境中进行 Pravega 的基准测试时，我们发现了一些由于使用 RocksDB 作为缓存而直接导致的问题。其中最严重的一个问题就是无法为所使用的内存设定上界，这使得 Kubernetes [9]由于过量内存使用 [10]而终止我们的 POD。控制 RocksDB 内存用量的唯一办法就是配置读写缓冲的大小。增大读写缓冲使得在需要进行基于磁盘的压缩之前有更多的数据被缓存在内存中，而减小这个缓冲则更加频繁地触发压缩，因此也导致了更频繁和更长时间的写停顿，引起性能下降。

为摆脱物理驱动器的束缚，人们可以选择将 RocksDB 运行在内存存储上，但这也使得控制总体内存使用量变得更加困难。即便从一开始就关闭了预写日志（Write Ahead Log，WAL），我们尝试了调优所有已知的 RocksDB 参数，包括关闭布隆过滤器（Bloom Filter）和调整压缩策略，但都没有取得显著的效果。于是我们决定寻找这一核心系统部件的替代实现。

作为 Pravega v0.7 的一部分，我们提升了系统性能，并且花费了很多时间寻找和解决数据注入路径上的瓶颈。这些提升的核心就是流式缓存：来自流视角的一种创新的缓存方法。

4 设计流式缓存

我们想保持缓存数据位于堆外以避免 Java 的垃圾回收问题。这有助于减少垃圾回收引发的停顿，但它同时也意味着我们无法享受垃圾回收所提供的便利：内存压缩 [11]。当被调用时，内存分配器需要找到一块连续的内存（与所请求的大小相同），因此任意存储和删除不同大小的数组最终将导致内存不足的错误。Java 的垃圾收集器会移动堆上的对象以便减少内存碎片 [12]，但我们却无法使用。因此，我们需要一种设计能够以最小代价减少或消除这个问题带来的影响。

在例如 Kubernetes 这样的容器化环境中运行 Pravega，需要内存使用量的调优。由于缓存也是内存的一部分，我们必须控制缓存内存使用的上界，包括它的元数据和索引开销。任何缓存都会有这样的开销：即便一个简单的哈希表也需要同时存储键和值，以及那些未使用的数组单元。我们对 Pravega 在这种环境中进行了大量测试，我们发现用现有的开源解决方案很难解决此类内存使用问题。

为了解决内存碎片和元数据开销，我们从块存储上得到了启发。我们将缓存划分为相同大小的缓存块（Cache Block），其中每一个缓存块都可以用一个 32 位的指针唯一寻址，选取 4KB 作为块大小使得每缓存最大理论容量达到了 16TB，这对单节点缓存来说已经足够了。

缓存块被组织成链表形成了缓存项（Cache Entry）。每个缓存块都有一个指针指向链表中位于它之前的另一个缓存块。因为每个缓存块都有一个地址，我们可以选择链表中的最后一个缓存块的地址来表示整个缓存项的地址。这样我们就可以从读取索引中引用这一地址。尽管有一点点反直觉，指向最后一个缓存块使得我们可以立即定位它并进行追加操作，无论是直接像它写入（如果它还有空闲空间）还是找到一个新的空缓存块并将其加入链表。

类似缓存项中所使用的缓存块，空缓存块同样也被链接在一起，这使得定位一个可用缓存块成为一个复杂度为 O(1)的操作。当需要分配一个新缓存块时，我们所要做的就是在这个链表的尾端取一个，这使得它的后继成为下一个头指针。删除一个项将引起它的缓存块被重新加回这个链表以便将来复用。

图 2 缓存项由链状的缓存块组成，并且项的地址指向链表中的最后一个块。缓存项不必存储在连续的缓存块中。空闲缓存块同样被链接在一起，这将允许快速分配新项。

分别分配每一个缓存块并且使用专门的内存池并不能完全避免内存碎片问题，却让我们为了管理所有的块不得不引入大量的元数据（在堆上）。相反地，我们可以分配我们自己的内存池（其实就是一块连续的内存块）。仍然，因为内存块需要是连续的，我们很可能无法一次性分配。因此，我们将这个内存池分割成更小的，等大小的段，称作缓存缓冲（Cache Buffer）。

当初始化缓存时，我们事先分配所有我们需要的缓存缓冲，这保证我们为后续使用预留了足够的内存。每个缓存缓冲持有固定数目的缓存块。例如，每个 2MB 的缓存缓冲可以持有 512 个 4KB 的缓存块。

对于空缓存块，为所有缓存缓冲保留一个单一的块列表将会非常难维护（尤其对于较大的缓存），并且当我们对其进行修改操作的时候会很快遇到并发问题。我们因此选择对每一个缓存缓冲（更小的并发域）维护一个这样的空缓存块列表。对于跨缓冲的情况，我们使用另一种不同的方法。所有缓冲最开始都被加入一个队列。当我们需要使用一个新的缓存块时，我们从这个队列获取第一个缓冲，并使用来自它的一个缓存块。如果这会导致缓冲被填满，那么我们就将它从队列移除。因此，当释放一个缓存块时，一个满的缓冲则又会获得可用空间，我们将其加入队列的末端。

图 3 主要的缓存操作如图所示。尚未填满的缓存缓冲存储在一个队列中；当它们被填满时会被从队列移除，而当它们至少获得一个可用的缓存块时（缓存项被删除后）会被重新加回队列。

这个方法解决了由分配器碎片引起的内存浪费问题，但它又引入了其它问题：缓存项碎片。例如，在一系列涉及不同大小缓存项的插入和删除操作之后，空闲缓存块链表可能不再指向连续的块。如图 2 所示，如果我们想要插入一条需要 5 个块的项 E3（未在图中画出），它将被存储在块 1，4，6，7 和 14 上。因为这些块并不位于一块连续的内存，这种情况可能导致潜在的性能下降，尤其是对于内存换出系统。然而，我们期望 Pravega 能够被提供充足的内存，足以容纳整个缓存并且避免换出。这一配置通常对于随机访问表现良好。未来，我们可以通过提升我们的缓存项分配算法来缓解这一问题。

综上所述，流式缓存由一组大小相同的缓存缓冲组成，其中每个缓冲又由相同大小的缓存块组成。每个缓存缓冲的第一个块被保留用作记录该缓冲其它块的元数据。这些元数据包括块是否被使用，块内保存了多少内容，链表内的前一个块是什么（如果这是一个使用中的块），以及下一个空闲块是什么（如果这是一个空闲块）。

实际的存储开销相对较小：存储在 Java 堆上的唯一信息就是缓存缓冲的指针（本质上就是 ByteBuffer [13]），其它的元数据都存储在堆外。当有最大尺寸限制时，流式缓冲能确保元数据和实际缓存块都受限于这个最大值，因此它绝不会超过这个限制。额外开销同样很容易计算：使用 4KB 的缓存块和 2MB 的缓存缓冲允许我们使用每个缓冲 512 个块中的 511 个，结果就是一个常数 0.2%的额外开销（例如，4GB 的缓存有 8MB 的额外开销）。

让我们用一个实际的例子看看流式缓存时如何运作的，如下图（图 4）所示。

图 4 一个具有 4 个缓冲的缓存结构。为简单起见，每个缓冲只显示 8 个 4KB 的缓存块。

图 4 描绘了一个具有 4 个项的缓存。A 小节可视化地展示了缓冲布局，而 B 小节则用列表格式展示了相同的布局。项 E1 有 6 个块，全部在缓冲 0 上分配。因为最后一个块是 0-6（缓冲 0，块 6），它也被用作整个项的地址。项 E2 完全占据了从缓冲 1 到缓冲 2 的 5 个块。尽管还是空的，E3 是一个合法的缓存项，并且占用一个完整的块，但它尚未存储任何数据。

缓冲 0，1 和 2 的元数据分别如小节 C，D 和 E 所示。“Prev”列可用于重建某个项的完整链表结构。例如，项 E4 具有地址 1-4 并且“Prev”值为 0-7，并且再没有更多的“Prev”值了。因此，E4 的链结构为 0-7，1-4。“Next”列可用于定位空闲列表。缓冲 0（C 小节）已经没有空闲块了，但我们可以很容易地看出缓冲 1 包含块 5 作为它的第一个空闲缓冲（元数据块 0 的“Next”值为 5）。对于其它的缓存项和缓冲都可以做出类似的推断。对于空闲缓冲，例如缓冲 3，它的每一个块都指向右边的块形成未使用块的链表。

5 基准测试

通常，非常大的改动是不会进入 Pravega 的源码仓库的，除非它被证实有明确的性能提升。我们执行了几种类型的测试，从缓存本身，再到将其集成进段存储。

在我们继续之前需要进行一个快速说明。就像所有的性能基准测试那样，测试结果会随不同的硬件和操作系统以及 Pravega 版本的变化而变化。所有这些测试都在一台具有 8 颗因特尔 Core™ i7-6700 CPU，主频 3.4GHz，64GB 内存的戴尔 Optiplex™ 7040 桌面工作站上进行。操作系统是 Ubuntu 16.04，Pravega 版本是 v0.7。段存储相关测试使用单一段存储实例，并使用基于内存的一级和二级存储（目的是观测缓存的效果）。每项测试都会反复进行多次，并选取最好的成绩（为了尽可能接近真实的 CPU 时间）。根据所使用的硬件和操作系统的不同，基准测试可能输出不同的结果。

5.1 原始缓存的基准测试

这项测试的目的是观测流式缓存在进行各种典型操作时所花费的时间。基准测试执行如下几类操作：

• 顺序测试。1,000,000个10KB的项被插入，查询，然后从缓存中删除。

• 随机测试。执行总数为1,000,000个的操作，每个操作有60%的概率为插入操作，40%的概率为移除操作。每次，一个随机的项被选取并读取。这项测试在10KB和100KB大小的项上进行。

我们测试了 Java 的 HashMap 数据结构，之前使用的基于 RocksDB 的缓存实现，以及流式缓存。测试结果总结在下表中，展示了以微秒为单位的每操/测试作所花费的时间：

表 1 原始缓存的基准测试结果。结果展示了以微秒的每操作/测试所花费的时间。

在所有的测试中，流式缓存都比基于 RocksDB 的缓存表现更好，它甚至还超过了基于 HashMap 的缓存。让我们分别看一下这些用例：

• HashMap对put和get操作的时间复杂度都是O(1)，但因为它是泛型集合，它并不持有数据，它只保存指向数据的指针。因此，我们必须分配/回收/复制缓冲区才能进行存储。例如，如果数据最初来自某个套接字（Socket）的缓冲区，这个缓冲区可能很快会被释放，这样我们就只剩下一个指向非法内存的指针了。从另一方面说，如果我们提供了指向内部字节数组的指针，这将会允许外部代码在我们不知情的情况下对其进行修改。将数据复制移入/移出HashMap使得它的性能相对不如流式缓存。我们分别以两种模式运行这项测试：一种，我们进行如上所述的缓冲区复制操作，而另一种，我们不进行复制。后者所花费的时间只有前者的十分之一，额外的时间花费都是由字节数组的分配和数据复制引起的。

• RocksDB需要维护一些索引和其它数据结构以便提供它的功能。同时，当某些触发器满足条件时，也会开始向磁盘换出数据，这使得IO操作降速到后端磁盘的速度（这在100KB的随机测试中表现尤为明显）。HashMap缓存没有磁盘IO和复杂的数据结构，但这是以Java的垃圾回收为代价的。每个插入和读取缓存的调用都需要分配一个新的字节数组，如果此时需要垃圾收集器介入释放空间，那么就将引发停顿。更进一步，大量此类的分配和释放操作将产生碎片，使得垃圾收集器不得不压缩内存以解决碎片问题，这也会造成垃圾收集过程的停顿并最终拖慢整个程序。

• 流式缓存在所有这些测试中都表现良好，因为它是专门为了段存储的特殊需求而剪裁的。插入操作无需分配内存（缓存缓冲是事先分配好的），数据直接从Netty [14]缓冲复制进入缓存。读取操作返回缓存项的只读视图，这允许直接将内容复制到所需要的地方（二级存储的写缓冲或者Netty缓冲-客户端读取）。为公平起见，在读取操作之后我们已经模拟了这些复制动作，并且将其所花费的额外时间包含进流式存储的基准测试中去。HashMap唯一远超流式缓存的测试用例就是删除操作。这是因为流式缓存需要释放所有被引用的块，而HashMap只需要解引用字节数组，将真正的内存回收动作延后（通过垃圾回收）。

5.2 段存储的基准测试

接下来，我们将流式存储集成进段存储，再运行一些集成测试。几乎所有对 Pravega 所做的修改都可以在本地进行基准测试，甚至发生在开发者本地工作站推送源码之前。自测工具 [15]允许我们运行各种目标测试，只要运用得当，它可以展示某个提交的变更是否可以提升性能。

我们执行了一些测试，分别专注于段存储的不同方面。每个测试都有 100 个并行的生产者以每次 100 个的大小批量发送事件/更新。吞吐量以 MB/s 为单位进行统计，而延迟则以微秒为单位。在以下的测试中，“基线”表示未使用流式缓存的 Pravega v0.7（使用先前的基于 RocksDB 的缓存）。相对的，“流式缓存”表示使用流式缓存的 Pravega v0.7（唯一的区别就是缓存的实现）。

5.2.1 流式处理延迟

这项测试的目的是测量小尺（100 字节）寸追加操作的的延迟。

表 2 小尺寸（100 字节）追加操作的延迟，单位：毫秒。

自测参数：-Dtarget=InProcessStore -Dbkc=0 -Dcc=0 -Dssc=1 -Dc=1 -Ds=1 -Dsc=4 -Dp=100 -Dpp=100 -Dws=1000 -Do=2000000

5.2.2 流式处理吞吐量

这项测试的目的是测量中等尺寸（10KB）追加操作的吞吐量：

表 3 中等尺寸（10KB）追加操作的吞吐量，单位：MB/s。

自测参数：-Dtarget=InProcessStore -Dbkc=0 -Dcc=0 -Dssc=1 -Dc=1 -Ds=1 -Dsc=4 -Dp=100 -Dpp=100 -Dws=10000 -Do=1000000

6 总结

缓存机制在 Pravega 的进站和出站性能中起着关键作用。尾部读取的数据全部来自于缓存，而历史读取则用它存储预取数据：它们在从二级存储读出后被暂存在缓存中，直到被某个 Reader 所消费。几乎所有的用户操作都会以这样或那样的方式涉及到缓存。对缓存的选择可以成就也可能破坏 Pravega 的吞吐量和延迟。可能就是缓存的选取造成了一个能近实时响应的集群和一个在重负载下缓慢运行的集群之间的差异。通过消除某些典型缓存实现中的额外开销，流式缓存通过使用基于块结构的无索引布局，提供了一种快速有效的方法来暂存大量流式数据。采用流式缓存后，我们在数据注入路径上发现的一些瓶颈都得以解决，这也使得我们能够在搞吞吐量的重负载下显著降低尾部延迟。

7 致谢

感谢 Srikanth Satya 和 Flavio Junqueira 为本文提出宝贵的意见和建议。

8 References

[1] A. Paduroiu, “Events Big or Small - Bring Them On,” [Online]. Available: http://blog.pravega.io/2019/04/22/events-big-or-small-bring-them-on/.

[2] “Pravega Release 0.7,” [Online]. Available: https://github.com/pravega/pravega/releases/tag/v0.7.0.

[3] A. Paduroiu, “Segment Store Internals,” [Online]. Available: http://blog.pravega.io/2019/03/07/segment-store-internals/.

[4] “Java Doc for EventStreamReader,” [Online]. Available: http://pravega.io/docs/latest/javadoc/clients/io/pravega/client/stream/EventStreamReader.html.

[5] “AVL Tree,” [Online]. Available: https://en.wikipedia.org/wiki/AVL_tree.

[6] D. Comer, “Ubiquitous B-Tree,” ACM Computing Surveys, vol. 11, no. 2, pp. 123-137, 1979.

[7] P. O’Neil, E. Cheng, D. Gawlick and E. O’Neil, “The log-structured merge-tree (LSM-tree),” Acta Informatica, no. 33, p. 351–385, 1996.

[8] “RocksDB,” [Online]. Available: https://rocksdb.org/.

[9] “Kubernetes,” [Online]. Available: https://kubernetes.io/.

[10] “Memory usage in RocksDB,” [Online]. Available: https://github.com/facebook/rocksdb/wiki/Memory-usage-in-RocksDB.

[11] “Tuning the Compaction of Memory,” [Online]. Available: https://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/geninfo/diagnos/memman.html#wp1088193.

[12] “Fragmentation (computing),” [Online]. Available: https://en.wikipedia.org/wiki/Fragmentation_(computing).

[13] “Java Doc for ByteBuffer,” [Online]. Available: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/nio/ByteBuffer.html.

[14] “Netty,” [Online]. Available: https://netty.io/.

[15] “Local Stress Testing for Pravega,” [Online]. Available: https://github.com/pravega/pravega/wiki/Local-Stress-Testing.