P2P 与分布式存储 / 系统课时

一致性哈希为何减少数据迁移量

一致性哈希为何减少数据迁移量

从三台存储节点扩容到四台,如果直接按节点数量取模,许多对象会被重新分配。一致性哈希把对象和节点放到固定哈希空间中,使新增或移除节点通常只改变局部区间的归属。本篇用 Python 对比两种路由在扩容、缩容时的改派数量,并说明何时必须真的搬动数据。

学习目标

  • 解释普通取模与一致性哈希在节点增删时的路由差异。
  • 运行 10000 个对象的模拟,验证迁移比例。
  • 识别虚拟节点的作用以及在线迁移的安全边界。

取模为什么会重新分配大量对象

普通取模把对象键映射为 SHA256(key) % N,再用结果作为有序节点列表的下标。假设原列表为 storage-a、storage-b、storage-c,扩容时在末尾加入 storage-d。同一个对象的哈希值不变,但取模基数由 3 变成 4,原来的下标大多无法保持。

若对象键的哈希足够均匀,3→4 且前三个节点顺序不变时,约 75% 的键会更换归属节点;这比新节点理想接收的 25% 多得多。删除列表中间的节点也会改变后续节点的下标。这里统计的是路由结果变化,若存储系统没有自动转移数据,重新计算归属并不等于对象已经迁移。

哈希环如何将变化限制在局部

一致性哈希先把节点标记和对象键各自哈希到同一个环形空间。查询对象时,从对象坐标顺时针找到第一个节点标记;走到环尾还没找到,就回到环头。节点数量变化不会改变其余标记的坐标,因此未被新节点接管的对象无需改派。

例如把环坐标简化为 0~99,现有 A=20、B=50、C=80。位于 60 的对象原本归 C;新增 D=65 后,只有区间 (50,65] 的对象转归 D。若随后移除 B,原属 B 的 (20,50] 区间改由 D 接管,其他区间不变。

节点增删前后哈希环的区间归属与迁移范围

实际部署常把每台物理节点展开为多个虚拟节点,例如 storage-a#0 至 storage-a#127,再分别散列到环上。这样一台节点可占有许多分散的小区间,缓解仅有三个物理标记时的极端不均衡。等容量节点扩为四台时,理想情况下新节点接收约 25% 的键;真实比例由虚拟节点位置决定,并非固定值。

用 Python 量化扩容与移除的改派量

下面以 SHA-256 生成稳定哈希,对 obj-00000 至 obj-09999 这 10000 个键分别应用取模与一致性哈希。每台节点使用 128 个虚拟节点;先从 A/B/C 扩容到 A/B/C/D,再从四节点集合中移除 B。保存为 consistent_hash_demo.py,用 python consistent_hash_demo.py 运行。

python
import bisect
import hashlib

def h(value):
    return int.from_bytes(hashlib.sha256(value.encode("utf-8")).digest(), "big")

def make_ring(nodes, vnodes=128):
    # 将一台物理节点展开为散布在环上的多个虚拟坐标
    points = sorted((h(f"{node}#{i}"), node)
                    for node in nodes for i in range(vnodes))
    return [p for p, _ in points], [node for _, node in points]

def ring_owner(key_hash, ring):
    positions, owners = ring
    # 顺时针找后继;尾端回绕到第一个虚拟节点
    i = bisect.bisect_left(positions, key_hash)
    return owners[i % len(owners)]

def measure(old_nodes, new_nodes):
    old_ring, new_ring = make_ring(old_nodes), make_ring(new_nodes)
    moved_mod = moved_ring = 0
    for i in range(10000):
        # 两次路由必须使用同一个对象哈希值
        key_hash = h(f"obj-{i:05d}")
        moved_mod += old_nodes[key_hash % len(old_nodes)] != new_nodes[key_hash % len(new_nodes)]
        moved_ring += ring_owner(key_hash, old_ring) != ring_owner(key_hash, new_ring)
    return moved_mod, moved_ring

base = ["storage-a", "storage-b", "storage-c"]
expanded = base + ["storage-d"]
without_b = ["storage-a", "storage-c", "storage-d"]

for name, old, new in [("扩容 3→4", base, expanded), ("移除 B 4→3", expanded, without_b)]:
    mod, ring = measure(old, new)
    print(f"{name}: 取模 {mod} ({mod/100:.2f}%), 一致性哈希 {ring} ({ring/100:.2f}%)")

预期输出(Python 3.8+):

text
扩容 3→4: 取模 7494 (74.94%), 一致性哈希 2369 (23.69%)
移除 B 4→3: 取模 7539 (75.39%), 一致性哈希 2480 (24.80%)

两组对比都使用相同对象键、相同哈希函数和同一节点增删操作,因此差异来自路由规则。删除节点 B 时,一致性哈希的 2480 个改派对象应全部是移除前由 B 负责的对象;仍在其他节点上的对象不应被重新分配。换一批对象键或调整虚拟节点数量,具体百分比会变化。

迁移比例低不代表扩容自动完成

上述程序只计算新旧归属,没有复制任何对象字节。真实对象存储若先切换环版本,客户端可能被路由到尚未持有数据的新节点,出现读取失败。一次有计划的在线扩容可以按以下顺序实施:

  1. 固定旧路由版本 epoch=17,构造候选版本 epoch=18,比较两版虚拟区间归属,只对变化区间制定搬迁清单。
  2. 预拷贝这些区间的对象,并通过变更日志追赶迁移期间的写入;对照对象数量、版本与校验和检查是否完整。
  3. 在写入切换屏障或等效同步协议保证下发布新版本,确认读写已转向新归属后,再清理旧位置的数据。

虚拟节点取 128 是本实验参数,不是通用最优值。节点容量不同可调整虚拟节点权重;同时应监测每台节点的实际存储字节数与请求负载,因为哈希均匀分布的键数量并不保证对象大小或流量均匀。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

一致性哈希为何减少数据迁移量

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通