一致性哈希：分布式系统中的数据分布

当数据量或访问量超出单台机器的承载能力时，就需要把数据分散到多台机器上，这个过程称为分片（Sharding）或分区（Partitioning）。分片要回答一个基本问题：给定一个键，它应该存放在哪台机器上？

这个问题看似简单，但在机器数量会动态变化的分布式系统中，答案的质量直接决定了系统的扩展能力、负载均衡程度和故障恢复速度。本文从最直接的取模哈希出发，介绍一致性哈希的原理与改进，以及跳跃一致性哈希、最高随机权重哈希、范围分片等其他方案，并讨论它们在实际系统中的取舍。

一、分片要满足的目标

一个好的数据分布方案，通常需要同时考虑以下几项目标：

• 均衡性：数据和访问量应当尽量均匀地分布在各个节点上，避免某些节点过载而其他节点空闲；
• 单调性：当节点加入或离开时，只有尽可能少的数据需要迁移，已经分配好的数据不应被大规模打乱；
• 查找效率：给定一个键，能够快速计算出它所在的节点；
• 元数据开销：维护分布规则所需的信息量应当尽可能小；
• 支持范围查询：在某些场景下，相邻的键最好分布在同一个节点上，便于按范围扫描。

这些目标之间往往存在冲突，不同的方案在其中做出了不同的取舍。

二、取模哈希及其问题

最直接的方案是取模哈希：先对键计算哈希值，再对节点数量取模，结果就是数据所在节点的编号。

节点编号 = hash(key) mod N

只要哈希函数足够均匀，数据就能均匀地分布到 N 个节点上。计算简单，不需要任何额外的元数据，查找只需一次运算。

问题出在节点数量变化时。假设原来有 4 个节点，现在增加到 5 个。一个哈希值为 12 的键，原来位于 12 mod 4 = 0 号节点，现在位于 12 mod 5 = 2 号节点。

可以计算，当节点数从 N 变为 N+1 时，只有哈希值在两种取模下结果相同的键才能保持原位，这部分键约占 1/(N+1)。也就是说，几乎所有数据都需要迁移。

对于分布式缓存而言，这意味着扩容或某个节点宕机的瞬间，绝大部分缓存都会失效，大量请求直接穿透到后端数据库，可能引发连锁故障。对于分布式存储而言，这意味着每次扩容都要搬迁几乎全部数据，代价极其高昂。

取模哈希的根本问题在于：数据的位置依赖于节点总数，总数一变，全局重新分配。

三、一致性哈希

一致性哈希（Consistent Hashing）由 David Karger 等人于 1997 年提出，最初用于解决分布式网页缓存的问题。它的核心思想是：让数据的位置只依赖于相邻节点，而不依赖于节点总数。

哈希环

一致性哈希将哈希值的取值空间想象成一个首尾相接的环。例如，哈希函数输出 32 位无符号整数，取值范围从 0 到 2³²−1，将这个范围弯成一个圆环，0 与最大值相邻。

1. 放置节点：对每个节点的标识（例如名称或地址）计算哈希值，将节点放置在环上对应的位置；
2. 放置数据：对每个键计算哈希值，同样映射到环上的某个位置；
3. 确定归属：从键所在的位置出发，沿顺时针方向前进，遇到的第一个节点就是该键所属的节点。

换言之，每个节点负责环上从它的前一个节点（不含）到它自身（含）之间的这段弧所覆盖的所有键。

节点变化的影响

增加节点：新节点被放置在环上某个位置，它只会接管其顺时针方向下一个节点原本负责的一部分键，即从新节点的前一个节点到新节点之间的那段弧。其他所有节点负责的范围完全不变。

移除节点：被移除节点原本负责的键，全部转交给它顺时针方向的下一个节点。其他节点不受影响。

在 N 个节点的情况下，增加或移除一个节点，平均只有约 1/N 的数据需要迁移，这已经是理论上的最优：新节点要承担 1/N 的负载，至少就需要迁入这么多数据。

查找实现

实现上，通常将所有节点的哈希值存储在一个有序数组或平衡树中。查找一个键时，计算其哈希值，然后用二分查找找到第一个大于等于该值的节点位置；如果找不到，则回绕到第一个节点。查找的时间复杂度为 O(log N)。

四、负载不均与虚拟节点

基本的一致性哈希虽然解决了单调性问题，但在均衡性方面存在明显缺陷。

负载不均的原因

节点在环上的位置由哈希值决定，具有随机性。当节点数量较少时，各节点之间的间隔很可能差异很大。某个节点可能恰好负责了一段很长的弧，承担了远超平均水平的数据量。

理论分析表明，在 N 个节点随机分布的情况下，负载最大的节点所承担的数据量，大约是平均值的 O(log N) 倍。即使只有十个节点，最忙和最闲的节点之间也可能相差数倍。

此外，节点离开时，其全部负载都会转移给唯一的一个后继节点，导致该后继节点的负载突然翻倍，而其他节点无法分担。

虚拟节点

解决方法是引入虚拟节点（Virtual Node）：每个物理节点不再只在环上放置一个点，而是放置多个点，每个点称为一个虚拟节点。例如，物理节点 A 在环上对应 A#1、A#2、……、A#100 等 100 个位置。

数据的归属规则不变：找到顺时针方向的第一个虚拟节点，再映射到它所属的物理节点。

虚拟节点带来了几方面的改善：

• 负载更均衡：每个物理节点负责的是环上众多分散的小段弧之和。根据大数定律，虚拟节点越多，各物理节点负责的总长度越接近平均值。当每个物理节点拥有数百个虚拟节点时，负载偏差通常可以控制在百分之十以内；
• 故障负载分散：一个物理节点离开时，它的各个虚拟节点负责的弧段，分别转交给各自的后继虚拟节点，而这些后继分属于不同的物理节点。原本集中在一个节点上的负载，被分散到了多个节点上；
• 支持异构节点：性能更强、容量更大的节点可以分配更多的虚拟节点，从而承担更多的数据，按权重分配负载。

虚拟节点的代价是元数据量和查找开销的增加：环上的点数从 N 个变为 N 乘以每节点虚拟节点数。不过，即使有数万个虚拟节点，有序数组的二分查找依然非常快，内存占用也很小，在大多数场景下完全可以接受。

有界负载的一致性哈希

即使使用了虚拟节点，当某些键的访问量特别高时，承载这些键的节点仍可能过载。

有界负载的一致性哈希（Consistent Hashing with Bounded Loads）对此做了改进：为每个节点设置一个负载上限，例如平均负载的 1.25 倍。分配一个请求时，按正常规则找到目标节点；如果该节点已经达到负载上限，就沿环继续顺时针查找，直到找到一个未满的节点。

这种方法在保持较好单调性的同时，严格限制了单个节点的最大负载，适用于负载均衡器将请求分配给后端服务器等场景。

五、跳跃一致性哈希

跳跃一致性哈希（Jump Consistent Hash）是 2014 年提出的一种算法，它以极简的实现提供了接近完美的均衡性和单调性。

基本思路

考虑节点数从 1 逐步增加到 N 的过程。每增加一个节点，每个键都有一定概率"跳"到新节点上：

• 节点数从 1 增加到 2 时，每个键有 1/2 的概率迁移到新节点；
• 节点数从 2 增加到 3 时，每个键有 1/3 的概率迁移到新节点；
• 一般地，节点数从 n 增加到 n+1 时，每个键有 1/(n+1) 的概率迁移到新节点。

这样，每增加一个节点，恰好有 1/(n+1) 的数据迁移到新节点，各节点的负载始终保持均衡，且迁移量最小。

关键在于，每个键是否迁移的"随机"决策，必须由键本身确定性地决定，以保证同一个键每次计算都得到相同的结果。算法以键的哈希值作为伪随机数生成器的种子，按顺序生成随机数做决策。

逐个模拟 n 从 1 到 N 的过程需要 O(N) 的时间。跳跃一致性哈希的精妙之处在于，它直接计算出下一次跳跃发生在哪个节点数，跳过中间所有不迁移的步骤，使得计算的期望时间复杂度降为 O(log N)。

特点与局限

跳跃一致性哈希的优点非常突出：

• 实现只有短短几行代码；
• 不需要任何内存来存储环或节点列表；
• 负载分布几乎完全均匀；
• 迁移量达到理论最优。

但它有一个重要的限制：节点只能在编号末尾增加或删除。节点被编号为 0 到 N−1，算法只能处理节点数的增减，无法处理中间某个编号的节点单独下线。如果 3 号节点故障，无法直接将其移除而保持其他节点的映射不变。

因此，跳跃一致性哈希适合节点集合相对稳定、扩缩容按顺序进行的场景，例如存储系统中将数据分配到固定数量的分片上，而分片到物理机器的映射由另一层机制管理。它不适合直接用于节点可能随时故障下线的缓存集群。

六、最高随机权重哈希

最高随机权重哈希（Highest Random Weight，HRW），也称会合哈希（Rendezvous Hashing），是另一种实现一致性分布的方法，其提出时间甚至早于一致性哈希。

原理

对于一个键，分别将它与每个节点组合，计算一个哈希值作为该节点对这个键的"权重"：

weight(key, node_i) = hash(key, node_i)

权重最高的节点，就是该键的归属节点。

性质

• 均衡性：由于哈希函数的随机性，每个节点获得最高权重的概率相同，数据分布均匀，无需虚拟节点；
• 单调性：增加一个新节点时，只有那些新节点权重恰好最高的键会迁移到新节点，约占 1/(N+1)；移除一个节点时，只有原属于该节点的键需要重新分配，并且它们会均匀地分散到剩余各节点上，因为每个键会转到其权重第二高的节点，而这个节点对不同的键是随机的；
• 天然支持多副本：如果需要将数据存放到 k 个节点上，只需选择权重最高的前 k 个节点。当一个节点故障时，其他副本的位置保持不变；
• 无需额外元数据：只需知道节点列表即可计算。

代价

最高随机权重哈希的主要缺点是查找开销：每次查找都需要对所有 N 个节点计算哈希值，时间复杂度为 O(N)。当节点数量为几十甚至几百个时，这通常不成问题；但当节点数达到数千以上，查找开销就变得明显。

一种改进方式是将节点组织成树状层次结构，在每一层使用最高随机权重哈希选择一个分支，从而将复杂度降低到对数级别。

七、范围分片

前面介绍的方案都基于哈希，它们的共同特点是：相邻的键会被打散到不同的节点上。这对负载均衡有利，却使得范围查询变得低效。查询某个键区间内的所有数据时，需要访问所有节点，再合并结果。

范围分片（Range Partitioning）采用了不同的思路：按照键的顺序，将整个键空间切分为多个连续的区间，每个区间称为一个分片，分配给某个节点负责。

工作方式

• 分片的边界和分片到节点的映射关系记录在元数据中，通常由专门的元数据服务管理；
• 查找一个键时，在元数据中二分查找它所属的区间；
• 范围查询只需访问与查询区间重叠的少数几个分片。

动态分裂与合并

范围分片的一个关键机制是动态调整：

• 当某个分片的数据量或访问量超过阈值时，将其分裂为两个较小的分片，并可以将其中一个迁移到负载较低的节点上；
• 当相邻分片的数据量都很小时，可以将它们合并，减少元数据开销。

这种方式能够适应数据分布随时间的变化，自动进行负载均衡。许多分布式数据库和分布式表格存储都采用了这种方案。

热点问题

范围分片的主要风险是热点。如果键具有顺序性，例如以时间戳或自增编号作为键，那么最新写入的数据总是集中在最后一个分片上，导致该分片所在节点承受全部写入压力，其他节点闲置。

应对热点的常见方法包括：

• 加盐：在键的前面添加一个由哈希计算得到的前缀，将顺序写入打散到多个分片上。代价是范围查询需要同时查询所有前缀；
• 使用非顺序的键：例如使用随机生成的唯一标识代替自增编号；
• 预分裂：在写入之前预先创建多个分片，避免初期所有数据集中在一个分片上；
• 按负载分裂：不仅根据数据量，也根据访问量决定分裂时机，并选择合适的分裂点。

八、各方案对比

九、分层设计：分片与节点的解耦

在实际的大规模系统中，常见的做法是将数据到分片的映射，与分片到节点的映射分为两层：

1. 第一层：将键映射到固定数量的逻辑分片，例如 1024 或 16384 个。分片数量通常远大于节点数量，且在系统生命周期中保持不变或很少变化。这一层可以使用简单的取模哈希或跳跃一致性哈希；
2. 第二层：将逻辑分片分配给物理节点，这一映射关系记录在元数据中，可以灵活调整。

这种设计带来了多方面的好处：

• 迁移粒度可控：扩容时，只需将部分逻辑分片整体迁移到新节点，迁移以分片为单位进行，易于管理和监控；
• 负载均衡灵活：可以根据各节点的实际负载，有针对性地调整分片的分配，而不受哈希随机性的限制；
• 元数据规模有限：逻辑分片数量固定，元数据大小可控；
• 支持异构节点：性能较强的节点可以分配更多的分片。

许多分布式缓存集群和分布式数据库都采用了固定数量槽位或分片的设计。客户端或代理层通过元数据确定每个槽位所在的节点，当集群拓扑变化时，只需更新元数据并迁移受影响的槽位。

需要注意的是，第一层的分片数量一旦确定，后续很难修改。如果设置过小，单个分片可能变得过大，限制了扩展能力；如果设置过大，元数据和管理开销会增加。通常需要根据预期的最大集群规模提前规划。

十、副本放置

为了保证可用性，数据通常需要保存多个副本。分片方案需要同时决定副本放在哪些节点上。

一致性哈希中的副本：常见做法是将键存储在其顺时针方向的前 k 个不同物理节点上。使用虚拟节点时，需要跳过属于同一物理节点的虚拟节点，确保副本落在不同的机器上。

故障域感知：仅仅将副本放在不同的机器上可能还不够。如果多个副本位于同一个机架、同一个电源回路或同一个可用区，一次机架级或机房级的故障就可能导致所有副本同时不可用。因此，副本放置策略通常需要考虑故障域的层级结构，将副本分散到不同的机架、不同的可用区。一些分布式存储系统使用基于层级结构的伪随机放置算法，在计算数据位置的同时满足故障域约束，并允许按权重分配数据。

副本迁移的协调：节点增减导致数据迁移时，需要保证在迁移过程中数据仍然可读可写，并且副本数量不会低于要求。这通常需要先在新位置建立副本、同步数据，确认完成后再切换并删除旧副本。

十一、实践中的注意事项

选择合适的哈希函数。 用于数据分布的哈希函数需要具有良好的均匀性和雪崩效应，但通常不需要具备密码学安全性。应选择速度快、分布均匀的非加密哈希函数。需要注意的是，同一系统的所有客户端必须使用完全相同的哈希函数和参数，否则会计算出不同的结果。

关注热点键。 无论使用何种分布方案，单个访问量极高的键都会使其所在节点承受过大压力，分片方案对此无能为力。针对热点键，通常需要额外的手段，例如在客户端或代理层增加本地缓存、将热点键复制多份分散读取、对热点数据进行拆分等。

控制迁移速度。 数据迁移会占用网络带宽和磁盘 I/O，可能影响正常业务请求。迁移过程应当限速，并在业务低峰期进行。对于缓存系统，节点变化会导致部分缓存失效，需要评估后端能否承受由此产生的额外请求。

处理节点的短暂故障。 节点可能只是短暂地不可达，例如网络抖动或进程重启。如果每次短暂故障都立即触发数据迁移，会造成大量不必要的数据搬迁。通常需要设置一个宽限期，在节点长时间未恢复后才开始迁移，期间由其他副本暂时承担服务。

保持元数据的一致性。 在使用元数据记录分布关系的方案中，所有客户端和节点对元数据的视图需要保持一致或能够正确处理不一致的情况。常见做法是由节点在收到不属于自己的请求时返回重定向信息，客户端据此更新本地缓存的元数据并重试。

规划初始分片数量。 对于使用固定分片数量的系统，初始分片数应当为未来扩容留出足够空间，避免日后被迫进行代价高昂的重新分片。

结语

数据分布是分布式系统设计的基础问题之一。取模哈希简单直接，却在节点变化时引发全局性的数据迁移；一致性哈希通过哈希环将数据位置与节点总数解耦，使迁移量降至理论最优，再借助虚拟节点改善负载均衡；跳跃一致性哈希和最高随机权重哈希则从不同角度给出了更简洁或更灵活的实现；范围分片牺牲了天然的均衡性，换来了对范围查询的支持，并通过动态分裂与合并适应数据分布的变化。

这些方案并没有绝对的优劣，各自适用于不同的场景。在实际系统中，它们也常常被组合使用：用哈希将键映射到固定的逻辑分片，用元数据管理分片到节点的分配，再用故障域感知的策略放置副本。理解每种方案的原理和代价，才能根据系统对扩展性、均衡性、查询模式和运维复杂度的具体需求，做出合适的设计选择。