1.局部性原理

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

局部性原理又表现为：时间局部性和空间局部性。

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

2.缓存

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

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

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

快速排序：

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

堆排序：

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

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

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

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

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

其具备以下特点：

1）代码指令和程序数据分离：在 L1 缓存中，实施了代码指令和程序数据分离的策略。由于代码指令和程序数据通常在体积层面差距较大，L1 缓存容量较小，如果不进行分离，那么可能导致绝大部分 L1 缓存被程序数据占据，导致代码指令的缓存命中率低下，从而影响性能

2）多级缓存策略：从 L1 到 L2 再到 SLC，速度依次下降，容量依次增大。数据的局部性越强，那么就越可能被更快的 L1、L2 命中

3）独占和共享相结合：L1 缓存为每个核心独占，L2 缓存在核心簇内共享，而 SLC 则在整个 SoC 层面共享（包括 CPU、GPU、NPU 等）

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

1）代码指令和程序数据分离 → 配置数据缓存与用户数据缓存分离，甚至尽量将不同场景、不同用途的缓存都分离

2）多级缓存策略 → 单机缓存、分布式缓存并用的多级缓存策略

3）独占和共享相结合 → 本地缓存单机独占、分布式缓存集群共享通过上述缓存策略的合理运用，我们能够尽可能的挖掘程序中的时间局部性，同时能够平衡不同缓存在速度、容量、成本之间的差异。

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

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

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

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

• 是：由于高速缓存一般对指令集透明，其必须要和内存保持一致的按字节寻址的特性，因此对于缓存的访问而言，其原子单元和内存一致，为字节

• 不是：但对于缓存的加载而言，其原子单元却并不是和内存一致的字节，而是缓存行（Cache Line），以上面提到的 M1 处理器为例，其缓存行大小（Cache Line Size）为 128 字节。也就是说，如果出现缓存不命中，需要从内存中加载数据到缓存中时，即使我访问的只是内存中的一个字节，那么缓存也会把这个字节所在的缓存行，也就是 128 个字节的数据全部加载到缓存中。

那么为什么缓存在加载的时候不只加载所需的数据，而是要加载整个缓存行？这不会造成浪费吗？具体原因大致为以下几点：

• 缓存行的设计可以充分利用现在 DRAM 的突发模式（Burst mode）特性，大幅提高访存吞吐量和减少延迟，这里具体不展开。

• 如果能提升系统的整体性能，一定程度的局部浪费是完全可以接受的。比如 CPU 中的分支预测特性也体现了类似的思路。

• 浪费的程度实际上取决于程序的空间局部性是否明显，局部性越明显，那么浪费就越小。

• 理论上缓存行的大小越大，那么对于局部性强的程序的性能提升也就越明显。当然，缓存行的大小还要受到其他各种物理因素的制约，并不能想多大就多大，也不是越大越好。

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

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

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

• 怎么定义“相邻”：内存的相邻很好定义，就是物理地址相邻，但是对于数据库中的业务数据而言，情况会复杂得多，甚至同一张表中的数据，在不同的使用场景下，其相邻的定义也不尽相同；

• 缓存加载的最小数据单位怎么确定：也就是对应 CPU 高速缓存的缓存行大小。这个值太小对空间局部性的利用程度有限，这个值太大会对缓存的加载开销和空间占用造成较大的压力。

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

4.实践案例

4.1 背景与挑战

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

策略平台除了利用了有向无环图来实施运营策略建模以外，另一大特色便是其模型的有状态性。也就是说策略平台会记录每一个用户在每一个有向无环图的中所处的顶点等状态信息，以此来支撑大量更加复杂的实际业务场景。

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

• 数据量巨大：预估数据量级将达 10 亿以上，并且后续会随平台使用情况、业务量级等因素继续增长。

• 写入量级巨大：预计写入 TPS 将达 1 万以上，同样会随平台使用情况、业务量级等因素继续增长。

• 查询量级更大：预计查询 QPS 将达 10 万以上，同样会随平台使用情况、业务量级等因素继续增长。

4.2 应对措施

针对数据量大的问题：

• 在数据库选型阶段选择了 Lindorm 以支撑海量的数据，同时利用其 TTL 机制，可以很方便的实现历史数据的清理。

• 同时为了节省成本，选择了公共集群，但公共集群会存在“吵闹邻居（Noisy neighbour）”的问题，会面临一些偶发的抖动，需要做一些额外的容错措施。

针对写入数据量大的问题，在系统层面做了以下优化措施：

• Lindorm 数据库本身基于 LSM Tree 数据结构，此结构将全量的写入请求都转化为对硬盘的顺序写入操作。众所周知，无论是固态硬盘还是机械硬盘，其顺序写入性能都是其随机写入性能的数倍。因此，Lindorm 数据库本身可以提供强大的写入性能。

• 状态数据批量合并写入，对状态数据进行一定程度的合并处理再批量写入，以降低写入 TPS 提升吞吐量。

• 状态数据裁剪，在写入前对状态数据进行过滤，仅保留被其他节点依赖的节点的状态数据。

• 另外，针对公共集群的偶发抖动，在写入时采取了通过 MetaQ 重试，同时利用 Lindorm 的时间戳多版本特性来避免重试导致的写入乱序而造成的数据不一致。

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

• 在一次请求处理过程中，反复访问同一个节点的状态数据的情况有，但可以预期的此缓存的命中率不会高。

• 如果引入多级缓存策略，无非就是将查询 QPS 分摊一部分至 Tair 之类的存储，这将带来成本的上涨、链路依赖增多导致的 SLA 下降等问题。

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

1）在数据写入时，我们可以采取批量合并的策略，将多次单条数据的写入请求合并为一次批量的写入请求来降低 TPS 提高吞吐量，那么在查询的时候，与之对应的策略是什么？

2）请求通常是用户维度的，一次请求进来通常涉及多个运营策略的执行，同时每个运营策略执行时又涉及多个顶点，这里明显存在放大效应，即状态数据库的查询 QPS = 用户维度的请求 QPS × 平均运营策略数量 × 平均每个策略下的顶点数量。

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

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

由于我们的 Lindorm 数据库中的状态表的主键也就是唯一键的构成是 (用户 ID，有向无环图 ID，顶点 ID），即 (userId, graphId, vertexId)。同时 Lindrom 支持最左前缀范围查询。要实现“缓存的加载粒度 > 查询粒度”，我们有两种选择：

1）缓存加载粒度：(userId, graphId)。即查询某个用户在某个运营策略的某个节点上的状态，那么将触发将这个用户在这个运营策略上的所有节点的状态数据都加载进缓存中。

2）缓存加载粒度：(userId)。即查询某个用户在某个运营策略的某个节点上的状态，那么将触发将这个用户在所有运营策略上的所有节点的状态数据都加载进缓存中。

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

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

4.3 初探空间局部性

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

(userId, graphId) 方案上线后，效果如下：

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

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

• 我们将数据库的查询量级下降到仅原来的 23.5%。

• 但由于每次加载的数据量增多，单次加载耗时增加到原来的 150%，但绝对值仍然处于非常优秀的水平。

• 另外，如果我们将总的加载耗时均摊到总的查询量级上，均摊查询耗时下降到仅原来的 35%，也就是说，整体性能获得了 65% 的巨大提升。

4.4 推向极限

(userId, graphId) 的方案上线后，经过一段时间的观察，我们发现内存压力和数据量级比预期中的小很多。因此，我们直接将这个方案推向极致——缓存加载粒度来到 (userId)！

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

• 我们将缓存的加载量级下降到仅相当于查询量级 4.12% 的水平！

• 由于每次加载的数据量继续增多，单次加载耗时增加到接近原来的 4 倍，但绝对值仍然处于可接受的水平

• 同时，如果我们将总的加载耗时均摊到总的查询量级上，均摊查询耗时下降到仅原来的 16%，也就是说，整体的查询性能也获得了将近 84% 的巨大提升！

下图是从 (userId, graphId) 方案切换至 (userId) 方案时的线上数据库的监控截图，可以清楚看到 QPS 随发布的下降，以及 RT 的上涨：

4.5 长期表现

但这还不是 (userId) 方案的极限，平台经过较长时间的发展以后，状态缓存的查询量级又上了好几层楼，最新的指标如下：

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

• 缓存加载量级仅为查询量级的 1.95%，同时此缓存的命中率达 97.95%！

• 单次缓存加载耗时降至 1.17 毫秒/次！此指标下降主要得益于前文提到的写入侧的数据裁剪，导致数据库整体的数据量下降，因此这里需要加载的数据量也有较大的下降，从而加载耗时也大幅减小

• 将总的加载耗时均摊到总的查询量级上，均摊缓存查询耗时来到了惊人的 0.02 毫秒/次。

可以看到，在查询量级大幅上涨后，(userId) 方案表现出了更大的潜力，而这都得益于其对空间局部性的充分挖掘。

4.6 风险

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

• 这么激进的缓存加载策略，会不会把内存打爆？

• 会不会存在某个用户 ID 下有海量的数据？

• GC 压力如何？

• 对单机内存的要求会不会很高？

这些担忧都是非常有必要的，因此我们基于 Prometheus 对这部分指标进行了详细的监控：

• 本地缓存使用数量、查询命中率、查询量级、加载量级

• 本地缓存平均加载时长、加载失败率、驱逐量级

• 为了监控单个用户 ID 名下数据量过大之类的风险，我们还对数据库的批量写入大小和批量读取大小进行了监控

• 单机的 GC 表现

需要声明的是：

• 状态缓存的有效期为加载后 1 秒内。

• 所有单机的规格均为 4 核 CPU + 8 GiB RAM 的 x86 容器。

通过上面这些监控指标可以看到：

• 状态缓存的峰值利用率在单机最大 600 项左右，并不多，且距离 2048 的最大项数还有较大距离。

• 状态缓存在进行数据加载时，单用户名下的最大数据量通常在 12 条左右，并且长期保持稳定，不存在任何尖刺。

• 单机的 GC 表现在 AJDK 21 和 G1 GC 的配合下表现优异，每分钟 GC 次数为 2-5 次，单次 GC 耗时 20 毫秒左右，且均为 Young GC。

• 堆内存上限 4 GiB，Young GC 后堆内存使用率能下探到 20% 左右。

这些指标都非常的健康，表明上述风险都在可控范围内。

4.7 回顾

回到前文，我曾提到，要将能够挖掘空间局部性的缓存策略，即缓存加载粒度 > 缓存查询粒度，应用到分布式系统中时，会面临两大难题：如何定义“相邻”以及如何确定缓存加载的最小数据单位，那么在上述的案例中，这两个难题是如何解决的？

• 如何定义“相邻”：在这个案例中，无论是按照 (userId, graphId) 还是 (userId) 的粒度来进行缓存加载，其都是符合数据库主键的最左前缀匹配的，这意味着这些数据在实际存储时，在物理层面，也都是相邻的，这样在查询时能够很好的利用数据库的特性，减少索引开销，利用硬盘的顺序读取特性，从而优化批量查询时的性能开销

• 缓存加载最小数据单位：不同于 CPU 中的缓存行，面临晶体管数量等严格的物理限制，在分布式系统中，我们面临的物理限制通常来自于内存大小，而这类限制相比之下宽松得多。因此在这个案例中，我们可以以 (userId, graphId) 甚至 (userId) 这样的动态粒度来作为缓存加载的最小数据单位，从而将空间局部性挖掘到极致，这在 CPU 层面将是难以想象的。

当然，这个案例本身具有一定的特殊性，在更加普遍的场景中，我们还是建议对缓存加载粒度设置一个硬限制，比如批量加载时最多加载 N 行数据，这样虽然对于空间局部性的挖掘不能到达极限，但能够很好的控制内存压力，能够适用于更加广泛的场景，类似于 CPU 中的缓存行的做法。另外，在缓存加载时，对于数据库中不存在的值，一定要设置空对象来占位，以防止缓存穿透。并且这种防穿透的效果，也能随着缓存加载粒度的扩大而被增强。

来源  |  阿里云开发者公众号

作者  |  习索