前言

在现代互联网系统中，分布式架构已成常态，如何高效、平滑地将数据或请求映射到多个节点，是系统设计中的关键问题。**一致性哈希（Consistent Hashing）**正是为了解决这一挑战而提出的算法。

定义

Wiki定义如下：

Consistent hashing is a special kind of hashing such that when a hash table is resized, only k/n keys need to be remapped on average, where k is the number of keys and n is the number of slots.

简而言之：一致性哈希是一种能在节点数量变化时最大限度减少数据迁移的哈希算法。

工作原理

一句话：通过将节点和数据都映射到一个**哈希环（Hash Ring）**上，实现数据到节点的平稳映射与快速定位。

工作步骤简述：

  1. 对所有节点取哈希值，映射到环上。
  2. 对数据取哈希值，顺时针寻找最近的节点。
  3. 添加或删除节点时，只需影响邻近的一小部分数据。

属性与指标

一致性哈希关注的核心属性与性能指标如下：

  1. 平衡性（Load Balancing）：数据均匀分布在各个节点。
  2. 稳定性（Minimal Rehash）：节点变化时，尽量少的数据迁移。
  3. 单调性（Monotonicity）：增加节点不会改变已有节点的数据归属。
  4. 分布性（Distribution Uniformity）：避免热点节点产生。
  5. 虚拟节点（Virtual Nodes）支持：提高哈希环的均衡性。
  6. 查找复杂度：通常为 O(log N)，使用跳表或红黑树等结构优化。
  7. 扩展性（Scalability）：支持大规模节点动态上下线。

类型

基本一致性哈希

最简单的实现方式，即节点和数据直接映射到环上，无虚拟节点。

缺点：当节点数量较少或哈希不均时，数据分布容易不平衡。

虚拟节点（Virtual Nodes）

每个物理节点对应多个虚拟节点，虚拟节点均匀分布在哈希环上。

优点：

  • 提高数据分布的均衡性
  • 节点上下线时影响的数据更少

常用策略：一个节点对应 N 个虚拟节点，N 可根据节点负载能力动态设定。

带权一致性哈希

在引入虚拟节点基础上，根据节点的处理能力或资源配置，分配不同数量的虚拟节点。

例如：性能强的节点设置 300 个虚拟节点，性能弱的设置 100 个，实现负载按权重分配。

应用场景

一致性哈希的典型应用如下：

  1. 分布式缓存系统：如 Memcached 节点扩容或缩容时保持数据稳定性。
  2. 分布式存储系统：如 Amazon Dynamo、Cassandra 采用一致性哈希分布数据。
  3. 负载均衡服务：对后端服务节点进行请求均匀分发，避免迁移会话。
  4. 微服务注册中心：如 Eureka、Consul 使用一致性哈希实现服务发现。
  5. 日志收集系统：如 Kafka Partition 与 Consumer 分配策略。

常用库与实现

常见一致性哈希实现或工具库包括：

  1. ketama：最早由Twitter开源的Java实现，支持虚拟节点，广泛用于Memcached客户端。
  2. HashRing：Python实现的轻量哈希环库。
  3. ConsistentHashing-Go：Go语言的简洁实现，支持虚拟节点。
  4. LibKetama：C语言实现，适用于高性能系统。
  5. nginx_upstream_hash：用于基于请求字段做一致性哈希转发。