软件工程（六）：一致性哈希算法

哈希算法

定义

哈希算法是一种将任意长度的输入（如字符串、文件等）转换为固定长度输出的算法，这个输出称为“哈希值”或“摘要”。

常见的哈希算法

应用场景

• 加密与签名（如MD5/SHA用于密码）
• 数据去重（快速比较两个文件是否相同）
• 哈希表中的键查找（如散列存储）
• 快速分片或定位资源

一致性哈希算法（Consistent Hashing）

背景与问题

在分布式系统中，如缓存（Redis/Memcached）、分布式数据库、CDN 中，经常面临这样的问题：

如果我们有 N 台节点，使用普通哈希对 key 取模分配数据：hash(key) % N。
当增加或减少节点时，几乎所有 key 的映射都会变化，导致大量缓存失效或数据迁移。

核心思想

一致性哈希解决了节点动态增删带来的大规模数据重映射问题。

一致性哈希的原理：

• 将整个哈希值空间组织成一个圆环（hash ring），如 0 ~ 2³²-1。
• 把每个节点映射到环上的一个位置（hash(node_id)）。
• 每个数据 key 也通过 hash 映射到环上的某个点（hash(key)）。
• key 被存储在顺时针方向上第一个遇到的节点中。

举例图示

环形空间（哈希环）：
       0
    ↗     ↘
  节点A    100
    ↑        ↓
 节点D ←──── key1
         250

加入/删除节点的影响小

• 只需迁移与该节点相关的一小部分数据，而不是全部重分布。
• 极大提高分布式系统的可扩展性与稳定性。

虚拟节点（Virtual Node）

为了解决节点分布不均衡的问题，引入虚拟节点机制：

• 每个真实节点对应多个虚拟节点（如A节点有A#1, A#2, A#3…），均匀分布在环上。
• key 映射到虚拟节点，再找到对应真实节点。
• 可以实现更好的负载均衡。

对比总结

典型应用场景