如何仅通过本地缓存就将数据库查询量级从 71.7 万 / 秒降至 1.4 万 / 秒

原标题：利用空间局部性原理大幅优化数据库查询量级

¶ 局部性原理

程序的局部性原理是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行期间所访问的存储空间也局限于某个内存区域。

局部性原理又可分为：

• 时间局部性：是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。比如在函数调用的时候，前不久才使用过的函数参数或局部变量容易再度被调取使用。
• 空间局部性：是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。空间局部性比较常见于循环中，比如在一个数组中，如果第 3 个元素在上一个循环中使用，则本次循环中极有可能会使用第 4 个元素。

¶ 缓存

正是由于程序的局部性，将热点数据放置到更快的存储设备上，那么将极大的提升程序的执行效率，这便是缓存。其本质是用空间换时间，牺牲数据的实时性，以近端暂存的历史数据代替远端最新的数据，从而减少访问内存、网络 IO 等高开销操作，以提升程序的性能表现。

¶ 缓存友好性

由于缓存的有效性由程序的局部性来支持，因此衡量程序是否缓存友好，即衡量其局部性的强弱。

关于缓存友好性，有一个经典的案例：堆排序有着最强的理论性能一一最坏时间复杂度 ，但在实际应用性能表现通常却不如最坏时间复杂度 的快速排序，便是由于堆排序的访存空间局部性太差，导致其缓存友好性很差，进而在现代计算机体系结构中吃了大亏。

快速排序

可以发现其分治算法的特性会使得其对内存的访问局限在一定的范围，从而具备了较好的空间局部性。

堆排序

可以发现其对于内存的访问模式相对 “跳跃”，这导致了较差的空间局部性。

¶ 分布式系统中如何利用局部性原理

¶ 分布式系统的存储层次结构

¶ 在分布式系统中利用时间局部性

在了解如何在分布式系统中利用时间局部性之前，我们先来了解在单机的计算机体系结构层面是如何利用时间局部性的。

以 Apple M1 为例，其搭载了堪称豪华的超大规模、多级片上缓存：

其具备以下特点：

1. 代码指令和程序数据分离：在 L1 缓存中，由于代码指令和程序数据通常在体积层面差距较大，而 L1 缓存容量较小，如果不进行分离，那么可能导致绝大部分 L1 缓存被程序数据占据，导致代码指令的缓存命中率低下，从而影响性能。
2. 多级缓存：从 L1 到 L2 再到 SLC，速度依次下降，容量依次增大。数据的局部性越强，那么就越可能被更快的 L1、L2 命中。
3. 独占和共享相结合：L1 缓存为每个核心独占，L2 缓存在核心簇内共享，而 SLC 则在整个 SOC 层面共享（包括 CPU、GPU、NPU 等）。

我们来看如何将上述的策略运用到分布式系统集群中：

1. 代码指令和程序数据分离 —— 配置数据缓存与用户数据缓存甚至不同场景或不同用途的缓存都尽量分离。
2. 多级缓存策略 —— 单机缓存、分布式缓存等并用的多级缓存策略。
3. 独占和共享相结合 —— 本地缓存单机独占、分布式缓存集群共享。

通过上述缓存策略的合理运用，我们能够尽可能的挖掘程序中的时间局部性，同时能够平衡不同缓存在速度、容量、成本之间的差异。

¶ 在分布式系统中利用空间局部性

在了解如何在分布式系统中利用空间局部性之前，我们先来了解在单机的计算机体系结构层面是如何利用空间局部性的。

众所周知，内存 (RAM) 的最小寻址单元是字节 (byte)，也就是说字节是内存中原子单元，不可再细分。这也就是为什么布尔 (boolean) 类型明明只包含一个比特 (bit) 的信息，但一般也必须要用一个字节在内存中存储。

那么 CPU 中的 L1、L2 等高速缓存也是以字节为原子单元吗？

是也不是：

• 是：由于高速缓存一般对指令集透明，其必须要和内存保持一致的按字节寻址的特性，因此对于缓存的访问而言，其原子单元和内存一致，为字节。
• 不是：但对于缓存的加载而言，其原子单元却并不是和内存一致的字节，而是缓存行 (Cache Line)，以上面提到的 M1 处理器为例，其缓存行大小 (Cache Line Size) 为 128 字节。也就是说，如果出现缓存不命中，需要从内存中加载数据到缓存中时，即使我访问的只是内存中的一个字节，那么缓存也会把这个字节所在的缓存行，也就是 128 个字节的数据全部加载到缓存中。

那么为什么缓存在加载的时候不只加载所需的数据，而是要加载整个缓存行？这不会造成浪费吗？

具体原因大致为以下几点：

• 缓存行的设计可以充分利用现代 DRAM 的突发模式 (Burst mode) 特性，大幅提高访存吞吐量和减少延迟，这里不具体展开。
• 如果能提升系统的整体性能，一定程度的局部浪费是完全可以接受的。比如 CPU 中的分支预测特性也体现了类似的思路。
• 浪费的程度实际上取决于程序的空间局部性是否明显，局部性越明显，那么浪费就越小。
• 理论上缓存行的大小越大，那么对于局部性强的程序的性能提升也就越明显。当然，缓存行的大小还要受到其他各种物理因素的制约，并不能想多大就多大，也不是越大越好。

可以看到，缓存行的设计目标很大程度上就是为了挖掘程序的空间局部性以提升性能。又或者说鼓励程序的空间局部性，空间局部性强的程序在这套机制下会得到性能的提升，而空间局部性差的程序在这套机制下会得到性能惩罚，正如前面提到的快速排序和堆排序。

因此，要想利用空间局部性的关键就在于：在加载缓存数据的时候，不仅要加载当前所需的数据，还要把 “相邻” 的一部分数据也一并加载进来，即：缓存的数据加载粒度 > 缓存的数据查询粒度。

然而，当我们尝试将这种思路应用到分布式系统中时，会面临两大难题：

• 如何定义 “相邻”：内存的相邻很好定义，就是物理地址相邻，但是对于数据库中的数据而言，情况会复杂得多，甚至同一张表中的数据，在不同的使用场景下，其相邻的定义可能也不尽相同。
• 如何确定缓存加载的最小数据单位：也就是类似 CPU 高速缓存的缓存行大小。这个值太小对空间局部性的利用程度有限，这个值太大会对缓存的加载开销和空间占用造成较大的压力。

这两个问题没有一个通行的答案，而是需要根据自己的实际场景来权衡。下面，我将使用一个实际案例来为大家说明。

¶ 实践案例

¶ 背景与挑战

我所负责的一个面向消费者运营领域的无代码开发平台。其通过有向无环图来对消费者运营领域内的各种运营策略进行建模，来帮助运营直接实施各种体系化、精细化的运营措施。简称 “策略平台”。

策略平台除了利用有向无环图这一复杂模型以外，另一大特色便是其模型的有状态性。也就是说策略平台会记录每一个用户在每一个有向无环图的中所处的顶点等状态信息，这种有状态性进一步提升了模型的表达能力，因此能够支撑大量更加复杂的实际业务场景。

然而，天下没有免费的午餐，存储、写入、查询这些用户状态数据将会面临很多挑战，具体可分为以下几个方面：

• 需要存储的数据量巨大，预估数据量级将达 10 亿以上，后续会随平台使用情况、业务量级等因素持续增长。
• 需要写入的数据量巨大，预计写入 TPS 将达 1 万以上，同样会随平台使用情况、业务量级等因素持续增长。
• 需要查询的数据量更大，预计查询 QPS 将达 10 万以上，同样会随平台使用情况、业务量级等因素持续增长。

¶ 应对措施

针对数据量大的问题

• 在数据库选型阶段选择了 Lindorm（阿里云改良版 HBase）以支撑海量的数据。同时利用其表级、行级 TTL (Time To Live) 机制，可以很方便的实现历史数据的自动清理。
• 同时，为了节省成本，选择了共享集群，其按照实际的存储、写入、查询用量来计费。但共享集群会存在 “吵闹邻居 (Noisy neighbour)” 的问题，会面临一些偶发的抖动，因此需要做一些容错措施。

针对写入数据量大的问题

• Lindorm (HBase) 基于 LSM Tree 数据结构，其所有写入操作都是顺序写入，而无论是 SSD 还是 HDD，其顺序写入都是离散写入性能的数倍，因此可以提供显著的写入性能。
• 状态数据批量合并写入，对状态数据进行一定程度的合并处理再批量写入，以降低写入 TPS 并提升吞吐量。
• 状态数据裁剪，在写入前对状态数据进行过滤，仅保留有向无环图中被其他顶点依赖的顶点的状态数据，而非执行过程中涉及到的所有顶点的状态数据。经验证，此措施能大幅减少存储、写入、和查询的数据量。
• 另外，针对共享集群的偶发抖动，在数据库写入时采取了通过消息队列重试来进行容错，同时利用 Lindorm 所提供的时间戳多版本特性来解决重试导致的写入乱序而造成的数据不一致问题。

针对查询量级大这一最大挑战

毫无疑间，查询请求量大这个问题才是最大的挑战。并且仅依靠常见的缓存策略，即仅挖掘时间局部性，对于该问题的帮助不大，原因如下：

• 在一次请求处理过程中，反复访问同一个顶点的状态数据的情况有，但很少，因此可以预期的此缓存的命中率不会高。
• 在此基础上如果再引入多级缓存策略，无非就是将查询量级分摊一部分至 Redis 之类的存储，这将带来额外的成本、系统链路中的依赖增多导致进而导致 SLA 下降等问题。

因此，我不得不另辟蹊径，从另外两个思路出发：

1. 在数据写入时，我们可以采取批量合并的策略，将多次单条数据的写入请求合并为一次批量的写入请求来降低 TPS 提高吞吐量。那么在查询的时候，与之对应的策略是什么？
2. 请求通常是用户维度的，一次请求进来通常涉及多个有向无环图的执行，同时每个有向无环图执行时又涉及多个顶点。这里存在明显的放大效应，即：状态数据库的查询量级 = 请求量级 x 平均每个请求涉及的有向无环图数量 × 平均每个有向无环图涉及的顶点数量。

思路 1 如果走偏了会变成：单条数据的查询请求来了先阻塞住，等攒到了一定的数量或者达到一定的时间了再用一个批量查询请求到数据库。这样的确能够做到批量合并，但毫无疑问会确定性的增加请求延迟，并且一次能攒多少不好说，也就是代价是一定会付出的，但是效果不一定有保障。另外，这种方式攒的请求通常都属于不同的用户，在数据库中的物理分布会相对离散，将这样的请求合并到一起做批量查询对数据库查询性能到底是有益还是有害还真不好说… 至少索引的开销应该是节省不了太多，相比于查询一批相邻的数据来说。

最终，两个思路殊途同归，都指向一点：缓存的数据加载粒度 > 缓存的数据查询粒度。也就是我们前面所提到的 CPU 高速缓存中缓存行设计所体现的思路，以此来尝试挖掘状态数据查询请求的空间局部性。

表的主键结构以及缓存加载策略

由于 Lindorm 数据库中的状态表的主键（相当于 HBase 中的 Rowkey）的构成是：（用户 ID，有向无环图 ID，顶点 ID），即：(userld, graphld, vertexld)。同时 Lindrom 同 HBase 一样支持最左前缀匹配的范围查询。

要实现 “缓存的数据加载粒度> 缓存的数据查询粒度”，有两种选择：

1. 缓存加载粒度：(userld, graphld)。查询某个用户在某个有向无环图中的某个顶点的状态数据，将会触发将这个用户在这个有向无环图中的所有顶点的状态数据都一并加载到缓存中。
2. 缓存加载粒度：(userld)。查询某个用户在某个有向无环图中的某个顶点的状态数据，将会触发将这个用户在所有有向无环图中的所有顶点的状态数据都一并加载到缓存中。

当然，缓存的查询粒度取决于场景，必须保持完整的 (userld, graphld, vertexId) 不变。

几种缓存加载策略的对照如下：

¶ 初探空间局部性

由于在开发阶段就已经意识到用户状态的查询将会是系统中最大的性能热点，因此在平台上线之初就直接将此缓存的加载粒度配置到了 (userld, graphld) 的粒度，以此来挖掘一定程度的空间局部性，同时又避免带来过大的浪费和内存压力。当然，我们仍然可以通过监控缓存的原始查询量来估计以 (userld, graphld, vertexld) 为缓存加载粒度时甚至无缓存时数据库会面临的查询量级。

(userld, graphld) 方案上线后，指标如下：

均摊缓存查询耗时 *：指将总的缓存加载耗时均摊到总的缓存查询量级上。即：平均缓存加载耗时 x 缓存加载量级 ÷ 缓存查询量级

可以看到，通过挖掘空间局部性：

• 缓存加载量级，即数据库的查询量级，下降到仅为原来的 23.5%。
• 但由于每次加载的数据量增多，单次加载耗时增加到原来的 150%，但绝对值仍然处于非常优秀的水平。
• 另外，如果我们将总的加载耗时均摊到总的查询量级上，即均摊分析。均摊查询耗时下降到仅为原来的 35%。也就是说，在查询用户状态数据这个场景上的整体开销下降了 65% 之多。

¶ 推向极限

(userld, graphld) 方案上线后，经过一段时间的观察，我们发现内存压力和数据量级比预期中的小很多，完全处于可接受的水平。

因此，我们直接将这个方案推向极致 —— 缓存加载粒度来到 (userId)！

可以看到，将空间局部性的挖掘做到极致以后：

• 缓存加载量级，即数据库的查询量级，下降到仅相当于查询量级 4.12% 的水平！
• 由于每次加载的数据量更多，单次加载耗时增加到接近原来的 4 倍，但绝对值仍然处于可接受的水平。
• 均摊查询耗时下降到仅为原来的 16%。也就是说，在查询用户状态数据这个场景上的整体开销下降了 84% 之多！

¶ 长期表现

平台经过较长时间的发展以后，状态缓存的查询量级又上了好几层楼，同时得益于在写入侧所做的数据裁剪等优化，最新的指标如下：

通过最新的数据我们可以观察到：

• 缓存加载量级，即数据库的查询量级，仅相当于查询量级的 1.95%！
• 此缓存的命中率稳定维持在 97.95% 左右。
• 单次缓存加载耗时降至 1.17 毫秒 / 次！此指标下降主要得益于写入侧的数据裁剪等优化，导致数据库整体的数据量级下降，因此这里需要加载的数据量也有较大的下降，从而加载耗时也大幅减小。
• 均摊查询耗时下降到惊人的 0.02 毫秒 / 次。也就是说，在查询用户状态数据这个场景上的整体开销下降了 98% 之多！

在查询量级大幅上涨后，配合写入侧的优化措施，(userld) 方案表现出了更大的潜力，而这都得益于其对空间局部性的充分挖掘。

¶ 风险

看到这里，你肯定会担心，代价是什么？

• 这么激进的缓存加载策略，会不会把内存打爆？
• 会不会存在某个用户 ID 下有海量的数据？
• GC 压力如何？
• 内存要求会不会特别高？

这些担忧都是非常有必要的，因此我们基于 Prometheus 自定义监控指标和内部的监控系统，对相关指标进行了详细且完备的监控：

• 本地缓存使用数量、查询命中率、查询量级、加载量级、平均加载时长、加载失败率、驱逐量级等。
• 状态数据库表的批量写入大小和批量读取大小。用以监控单个用户名下数据量过大之类的风险。
• 单机的 JVM GC 表现，包括：每分钟 GC 频次、每分钟累计 GC 耗时、堆内存使用情况等。

需要声明的是：

• 状态缓存加载后仅 1 秒的有效期。
• 所有单机均为 4 核 CPU、8 GiB RAM 规格的 x86 容器。

而通过上述的监控指标可以观察到：

• 状态缓存的单机峰值利用率在 600 项左右，并不大，且距离 2048 的最大项数还有一定距离。
• 通过状态数据库表的批量查询监控观察到，批量查询的最大数据量在 12 条 / 批左右，且长期保持稳定，不存在任何尖刺。同时，从策略平台这个场景出发，也极不可能出现单用户名下数据量超多的情形。
• 单机的 GC 表现在 JDK 21 + G1 GC 的加持下，GC 频次在 2-5 次 / 分钟，GC 累计耗时在 40-130 毫秒 / 分钟（不是单次 GC 耗时），并且全是 Young GC。
• 单机 4 GiB 的堆内存，经过 Young GC 后能够下探到 20% 左右的水位。

即各项指标都处于非常健康的水平。

¶ 回顾

前文曾提到，要将能够挖掘空间局部性的缓存策略，即：缓存的数据加载粒度 > 缓存的数据查询粒度，应用到分布式系统中时，会面临两大难题：

1. 如何定义 “相邻”？
2. 如何确定缓存加载的数据粒度，即 “缓存行大小”？

那么在上述的案例中，这两个难题是如何解决的？

• 如何定义 “相邻”：在这个案例中，无论是按照 (userld, graphld) 还是 (userld) 的粒度来进行缓存加载，其都是符合数据库主键 (Rowkey) 的最左前缀匹配原则的。这意味着这些数据在实际存储时，在物理层面，也都是相邻的，这样在查询时能够很好的利用数据库乃至底层硬件的特性，减少索引开销，利用顺序读取等特性，从而优化批量查询时的性能开销，做到 1 + 1 < 2 的效果。
• 缓存加载的数据粒度：不同于 CPU 中的缓存行，其面临晶体管数量等严格的物理限制。在分布式系统中，我们面临的限制相比之下通常宽松得多，例如：内存大小。因此在这个案例中，我们得以以 (userld, graphld) 甚至 (userld) 这样的不定长粒度来作为缓存加载的数据粒度，从而将空间局部性挖掘到极致，这在 CPU 这类面临严苛物理限制的场景将是难以想象的。

当然，这个案例本身具有一定的特殊性，状态数据的分布总体而言是相对稀疏的，尤其对于裁剪后的状态数据。在更加普遍的场景中，我们还是建议对缓存加载数据量设置一个硬限制，比如：批量加载时最多加载 N 行数据。这样虽然对于空间局部性的挖掘不能到达极限，但能够很好的控制内存压力，能够适用于更加广泛的场景，例如：单用户名下的数据就超过内存承受极限的场景。也更加类似于 CPU 中的缓存行的做法。

另外，在缓存加载时，对于数据库中不存在的值，一定要设置空对象来占位，以防止缓存穿透。并且这种防穿透的效果，也能随着缓存加载粒度的扩大而被增强。