事半功倍：Valkey 8 中的内存效率

Valkey 8.0 GA 即将发布，其中一个主题是提高整体内存效率。减少内存开销不仅能显著提高资源利用率，还会影响性能。通过最大限度地减少不必要的内存消耗，您可以用相同的硬件资源存储更多数据，并提高整体系统响应能力。本文将概述 Valkey 如何在内部管理数据及其内存开销。此外，本文还将介绍 Valkey 8.0 中两项主要改进，它们提高了整体内存效率。

概述

Valkey 有两种运行模式：单机模式和集群模式。单机模式允许一个主节点及其副本。为了水平分片数据并扩展以存储大量数据，集群模式提供了一种机制来设置多个主节点，每个主节点都有自己的副本。

无论是单机模式还是集群模式，Valkey 的主字典都是一个带有链式列表的哈希表：主要组件是桶（bucket）和字典条目（dictionary entry）。键被哈希到一个桶中，每个桶指向一个字典条目链表，并且每个字典条目由键、值和一个指向下一个的指针组成。每个指针占用 8 字节内存。因此，单个字典条目的最小开销为 24 字节。

在集群模式下，Valkey 使用一个名为哈希槽的概念来分片数据。集群中有 16,384 个哈希槽，为了计算给定键的哈希槽，服务器会计算键的 CRC16 并对 16,384 取模。键根据分配给每个主节点的这些槽进行分布。服务器需要维护额外的元数据用于簿记，即槽到键的映射，以便将槽从一个主节点移动到另一个主节点。为了维护槽到键的映射，每个字典条目中都存储了两个额外的指针slot-prev和slot-next（图 3）作为元数据，形成了一个给定槽中所有键的双向链表。这进一步增加了每个字典条目 16 字节的开销，即总计 40 字节。

改进

优化 1 - 每个槽一个字典

第一个优化是为每个槽（总共 16,384 个）分配一个字典，其中每个字典存储给定槽的数据。通过这种简化，Valkey 8 中不再需要维护槽到键映射的额外元数据开销。为了遍历给定槽中的所有键，引擎只需找到给定槽的字典并遍历其中的所有条目。这减少了每个字典条目 16 字节的内存使用量，同时每个节点只增加了大约 1 MB 的少量内存开销。由于集群模式通常用于存储大量键，避免每个键的额外开销使用户能够在相同内存量下存储更多键。

上述改进带来的一些有趣挑战是支持那些为整个键空间使用单一字典而优化的现有用例。这些用例包括

• 遍历整个键空间 - SCAN 等命令用于遍历整个键空间。
• 用于驱逐的随机键 - 服务器对键空间进行随机抽样，以找到理想的驱逐候选键。
• 查找随机键 - RANDOMKEY 等命令从数据库中检索随机键。

为了高效实现这些功能，我们需要能够找到非空槽，在扫描时跳过空槽，并能够根据槽拥有的键数量加权选择随机槽。这些要求需要一种提供以下功能的数据结构

1. 修改给定槽的值 - 如果添加或删除了键，则分别将给定槽的值递增或递减 1。
2. 每个槽的累积频率 - 对于一个介于 1 和总键数之间的数字（代表一个键），返回覆盖该特定键的槽。

如果采用朴素方法，前一个操作和后一个操作的时间复杂度将分别为 O(1) 和 O(N)。然而，我们希望最小化后一个操作的时间复杂度，并尽量减少前者的开销。因此，引入了树状数组（BIT）或 Fenwick 树，它以最小的内存开销（每个节点约 1 MB）提供上述功能，并且两个操作的时间复杂度都限制在 O(M log N)，其中 M = 修改次数，N = 槽数量。这使得在遍历键空间时能够高效地跳过空槽，并通过对树状数组维护的累积和进行二分查找，以对数时间找到给定键索引的槽。

另一个有趣的副作用是关于 rehash（重新哈希）操作。重新哈希操作是 CPU 密集型的。默认情况下，字典中会分配有限数量的桶，并根据使用情况动态扩展/收缩。在进行重新哈希时，所有数据都需要从旧字典移动到新字典。在 Valkey 7.2 中，由于所有槽共享一个全局字典，所有键都存储在一个字典下，每当填充因子（键数 / 桶数）超过 1 时，字典就需要迁移到一个更大的字典（2 的倍数）并移动大量键。由于此操作是即时执行的，因此在进行过程中会导致常规命令操作的延迟增加。通过每个槽一个字典的优化，重新哈希的影响被限制在正在处理的特定字典中，并且只需移动一部分键。

总的来说，采用这种新方法，好处如下：

1. 消除了集群模式中额外的内存开销：摆脱了每个键的两个指针（16 字节），以保留槽到键的映射。
2. 随着重新哈希操作分散到各个字典中，CPU 利用率也随之分散。

优化 2 - 将键嵌入字典条目

在每个槽一个字典的更改之后，集群模式下字典条目的内存布局如下：有三个指针（键、值和下一个）。键指针指向一个 SDS（简单动态字符串），其中包含实际的键数据。由于键是不可变的，在不引入太多复杂性的情况下，它可以嵌入到与键具有相同生命周期的字典条目中。

采用这种新方法，整体好处如下：

1. 每个键减少 8 字节的额外内存开销。
2. 消除了键的额外内存查找：通过访问字典条目，不再需要对键进行额外的随机指针访问，从而带来更好的缓存局部性和整体性能。

基准测试

设置

设置了一个包含 1 个主节点和 2 个副本的单分片集群。每个节点运行不同版本，以突出显示从 7.2 到 8.0 引入的各项优化所带来的内存改进，并表明无需额外配置即可实现内存效率。

• 节点 A：主节点运行在端口 6379，版本为 Valkey 7.2
• 节点 B：副本 1 运行在端口 6380，并启用了优化 1 - 每个槽一个字典
• 节点 C：副本 2 运行在端口 6381，并启用了优化 1 - 每个槽一个字典 和 优化 2 - 键嵌入 - 包含 Valkey 8 中的所有内存效率优化。

使用 valkey-benchmark 工具生成合成数据

src/valkey-benchmark \
 -t set \
 -n 10000000 \
 -r 10000000 \
 -d 16

内存使用情况

• 节点 A

127.0.0.1:6379> DBSIZE # command to retrieve number of keys.
(integer) 6318941
127.0.0.1:6379> INFO MEMORY # command to retrieve statistics about memory usage
# Memory
used_memory:727339288
used_memory_human:693.64M

• 节点 B

127.0.0.1:6380> DBSIZE # command to retrieve number of keys.
(integer) 6318941
127.0.0.1:6380> INFO MEMORY # command to retrieve statistics about memory usage
# Memory
used_memory:627851888
used_memory_human:598.77M

• 节点 C

127.0.0.1:6381> DBSIZE # command to retrieve number of keys.
(integer) 6318941
127.0.0.1:6381> INFO MEMORY # command to retrieve statistics about memory usage
# Memory
used_memory:577300952
used_memory_human:550.56M

总体改进

通过每个槽一个字典的更改，在相同数据集下，内存使用量从 693.64 MB 减少到 598.77 MB

• 下降百分比 1: ((693.64 - 598.77) / 693.64) * 100 = (94.87 / 693.64) * 100 ≈ 13.68%

此外，通过键嵌入，在相同数据集下，内存使用量从 598.77 MB 减少到 550.56 MB

• 下降百分比 2: ((598.77 - 550.56) / 598.77) * 100 = (48.21 / 598.77) * 100 ≈ 8.05%

总下降：从 693.64 MB 到 550.56 MB

• 总下降百分比: ((693.64 - 550.56) / 693.64) * 100 = (143.08 / 693.64) * 100 ≈ 20.63%

因此，从 Valkey 7.2 升级到 Valkey 8.0 后，给定节点的总体内存使用量大约下降了 20.63%。

结论

通过引入每个槽一个字典和将键嵌入字典条目所实现的内存效率，Valkey 8.0 的用户应该有额外的容量来存储每个节点更多的键（最高可达 20%，但这会因工作负载而异）。对于从 Valkey 7.2 升级到 Valkey 8.0 的用户，改进将自动生效，无需任何配置更改。您可以通过启动一个Valkey 集群来尝试，并加入我们的社区提供反馈。此外，目前正在讨论对主字典进行彻底改革，采用更紧凑的内存布局并引入开放寻址方案，这将显著提高内存效率。更多详细信息请参见问题 169：重新思考主哈希表。