Rendezvous Hashing

发布于 2026-06-04 04:45 · 最后编辑于 2026-07-31 15:54 · 字数 4,561 👁 103 次阅读

Rendezvous Hashing（HRW）通过对每个候选节点计算 hash(key, node_id) 并选最高分实现分布式路由，无需虚拟节点即可天然均匀分布，被 Varnish Cache、Cassandra 和 CDN 边缘调度广泛采用。

rendezvous hashing

章节	说明
问题背景	取模哈希与一致性哈希的不足，Rendezvous Hashing 的定位
核心思想（Highest Random Weight）	Highest Random Weight 原理与核心数据结构
完整伪代码	select(key, nodes) 的逐步实现
执行追踪	key="user:42"，nodes=[A,B,C] 的具体数值演示
一致性与迁移保证	节点增删时的迁移量分析
异常与边界场景	hash 碰撞、节点 ID 变化、空节点列表等 3 个场景
与一致性哈希、Jump Hash 对比	时间、空间、灵活性三维度对比
实际应用	Varnish Cache、Cassandra、CDN 边缘节点选择
参考资料	论文与文档

问题背景

取模哈希的缺陷

最简单的分片方案 node = hash(key) % N，在节点数 N 变化时，几乎所有 key 的映射结果都改变，导致大规模数据迁移。

传统一致性哈希的不足

Karger 1997 年提出的一致性哈希解决了大规模迁移，但：

需要虚拟节点：为保证负载均匀，每个物理节点通常需要 100-200 个虚拟节点。
实现复杂：需要有序数据结构（红黑树）维护虚拟节点环，查找时需要二分搜索。
内存开销：O(N × 虚拟节点数) 的空间占用。

Jump Consistent Hash 的局限

Jump Consistent Hash（Google, 2014）实现极简、O(ln N) 查找，但要求节点编号连续，不支持任意节点删除（只能删末尾节点）。

Rendezvous Hashing 的定位

Rendezvous Hashing（Thaler & Ravishankar, 1996）解决的核心问题：

支持任意节点 ID（字符串、IP、UUID），不要求连续编号。
支持任意节点增删，无需虚拟节点即可保证天然均匀分布。
节点增删时只有最少量的 key 需要迁移，满足一致性哈希最优迁移代价。
实现极简，核心逻辑 5-10 行代码。

核心思想（Highest Random Weight）

算法原理

对于给定的 key，遍历所有候选节点，为每个节点计算一个得分：

score(key, node) = hash(key || node_id)

选得分最高的节点作为路由目标。这就是算法名称的由来：Highest Random Weight（HRW）。

为什么天然均匀？

对于随机 hash 函数：

任意两个节点的得分相互独立，均匀分布在 [0, 1)。
每个节点成为最高分的概率均等，均为 1/N。
因此负载天然均匀，无需虚拟节点。

核心数据结构

字段	类型	含义
`key`	`string`	路由键，如用户 ID、请求 URL、对象名
`node_id`	`string`	节点标识，如 IP:Port、主机名、UUID
`score`	`float64`	`hash(key + node_id)` 归一化到 [0, 1) 的得分
`best_score`	`float64`	当前遍历中的最高得分，初始为 -∞
`best_node`	`Node`	当前得分最高的节点，初始为 null

完整伪代码

select(key, nodes)

function select(key, nodes):
    if nodes is empty:
        raise Error("node list must not be empty")

    best_score = -∞
    best_node  = null

    for node in nodes:
        score = hash(key + node.id)      // 拼接后哈希，归一化到 [0, 1)
        if score > best_score:
            best_score = score
            best_node  = node

    return best_node

哈希函数选择

推荐使用高质量非加密哈希函数，输出归一化为 [0, 1)：

function hash(input) -> float64:
    raw = xxHash64(input)                // 64 位整数
    return raw / 2^64                    // 归一化到 [0, 1)

常用选择：xxHash64（速度最快）、MurmurHash3（广泛采用）、SipHash（防哈希洪水攻击）。

带权重的扩展版本

若节点有不同权重（如内存 32GB 的节点权重 2，16GB 权重 1），调整得分公式：

score = -weight / ln(hash(key + node.id))

权重越大，得分越高（负数绝对值越小），被选中概率约等于 weight / sum(all_weights)。

执行追踪

输入：key = "user:42"，nodes = [A, B, C]，节点 ID 分别为 "A"、"B"、"C"

初始状态：best_score = -∞，best_node = null

步骤 1：计算节点 A 的得分

input  = "user:42" + "A" = "user:42A"
score  = hash("user:42A") = 0.73
0.73 > -∞  → best_score = 0.73，best_node = A

步骤 2：计算节点 B 的得分

input  = "user:42" + "B" = "user:42B"
score  = hash("user:42B") = 0.91
0.91 > 0.73  → best_score = 0.91，best_node = B

步骤 3：计算节点 C 的得分

input  = "user:42" + "C" = "user:42C"
score  = hash("user:42C") = 0.45
0.45 < 0.91  → 不更新，best_node 仍为 B

结果：key="user:42" 路由到节点 B（得分 0.91 最高）。

新增节点 D（节点集合变为 [A, B, C, D]）：

score = hash("user:42D") = 0.65
0.65 < 0.91  → B 得分仍最高，key="user:42" 路由不变 ✅

此 key 不受影响，无需迁移。

假设新增节点 E 使得：

score = hash("user:42E") = 0.95
0.95 > 0.91  → best_node 变为 E

此 key 从 B 迁移到 E，只影响原本分配给「竞争范围」的少量 key。

删除节点 B（节点集合变为 [A, C, D]）：

只对原先路由到 B 的 key（约 1/N 总量）重新计算：
  hash("user:42A") = 0.73
  hash("user:42C") = 0.45
  hash("user:42D") = 0.65
→ best_node = A（0.73 最高），key="user:42" 迁移到 A

原本路由到 A、C、D 的 key 完全不受影响。

一致性与迁移保证

稳定性（节点集合不变）

当节点集合固定时，同一 key 的 hash 计算结果是确定性的，因此：

相同 key + 相同 nodes → 永远路由到相同节点

无需额外状态存储，天然满足路由一致性。

节点增加时的迁移量

增加节点 N_new（节点总数从 N 变为 N+1）：

对于任意 key，N_new 成为新最高分的概率为 1/(N+1)。
因此约 1/(N+1) 比例的 key 会迁移到 N_new。
原有 N 个节点均等分摊"贡献"，每个节点贡献约 1/(N(N+1)) 比例的 key。
最优迁移代价：恰好达到理论下界。

节点删除时的迁移量

删除节点 N_i（节点总数从 N 变为 N-1）：

原本路由到 N_i 的 key（约 1/N 总量）重新分配。
这些 key 均匀分散到剩余 N-1 个节点，每个节点接收约 1/(N(N-1)) 比例的 key。
其余 (N-1)/N 比例的 key 完全不受影响，无需任何迁移。

对比取模哈希

操作	取模哈希迁移比例	Rendezvous Hashing 迁移比例
增加 1 个节点	约 N/(N+1) ≈ 90%+	1/(N+1) ≈ 10%
删除 1 个节点	约 (N-1)/N ≈ 90%+	1/N ≈ 10%

异常与边界场景

场景 1：hash 碰撞（两个节点得分相同）

问题：当 hash(key+"A") == hash(key+"B") 时，最终选择哪个节点取决于遍历顺序，可能在不同实例上产生不一致的路由结果。

复现概率：64 位哈希的碰撞概率约为 2^(-64) ≈ 5.4×10^(-20)，极低但非零。

处理方案：增加 tie-breaking 规则——得分相同时按 node_id 字典序取最小（或最大），保证所有节点对该 key 的路由结果一致：

if score > best_score or (score == best_score and node.id < best_node.id):
    best_score = score
    best_node  = node

场景 2：节点 ID 变化（节点重命名）

问题：Rendezvous Hashing 的路由结果依赖节点 ID 字符串。如果将节点 ID 从 "server-01" 改为 "server-01.prod.example.com"，则所有经过该节点的 key 都会重新计算，导致全量重新路由，迁移量接近 100%。

后果：缓存失效、数据库连接风暴、请求路由到错误节点。

处理方案：

节点 ID 使用不可变的稳定标识（UUID、固定数字 ID），而非主机名或 IP。
需要重命名时，先添加新 ID 再删除旧 ID，通过两阶段切换降低冲击。

场景 3：空节点列表

问题：调用 select(key, []) 时，循环不执行，best_node 保持 null，直接返回 null 会导致 NullPointerException 或空指针崩溃。

处理方案：在函数入口做前置校验，快速失败：

function select(key, nodes):
    if nodes is empty:
        raise Error("node list must not be empty")
    ...

调用方应在业务层区分「无可用节点」（服务不可用）与「路由失败」（算法错误），分别返回 503 和 500。

与一致性哈希、Jump Hash 对比

三者对比总表

维度	Rendezvous Hashing	传统一致性哈希	Jump Consistent Hash
查找时间	O(N)，遍历所有节点	O(log N)，二分搜索	O(ln N)，迭代跳跃
空间复杂度	O(N)，仅存节点列表	O(N × 虚拟节点数)	O(1)，无存储
节点任意删除	支持，任意节点 ID	支持	不支持（只能删末尾）
节点任意添加	支持	支持	支持（追加末尾）
需要虚拟节点	不需要	需要（100-200 个/节点）	不需要
节点 ID 类型	任意字符串	任意（哈希到环位置）	仅连续整数 0..N-1
实现复杂度	极简，5-10 行	复杂，需有序数据结构	极简，5 行
迁移代价	最优 1/(N+1)	接近最优	最优 1/(N+1)
负载均匀性	天然均匀	取决于虚拟节点数量	理论最优

选择建议

场景	推荐算法	原因
节点频繁任意增删（服务发现）	Rendezvous Hashing	支持任意 ID，无虚拟节点
节点数量单调增长（存储分片）	Jump Consistent Hash	O(ln N) 查找最快，O(1) 空间
超大规模集群（数千节点）	传统一致性哈希	O(log N) 查找优于 Rendezvous 的 O(N)
CDN 边缘节点（动态上下线）	Rendezvous Hashing	动态 IP/主机名，支持任意节点 ID
需要防缓存踩踏（加权分配）	Rendezvous Hashing	原生支持加权版本

与 Jump Consistent Hash 的核心区别

Jump Consistent Hash：
  输入：(key: uint64, num_buckets: int)
  约束：节点编号必须是 0, 1, 2, ..., N-1 的连续整数
  优势：O(ln N) 时间、O(1) 空间

Rendezvous Hashing：
  输入：(key: string, nodes: []Node)，每个 Node 有任意字符串 ID
  约束：无，任意节点 ID，任意增删
  代价：O(N) 时间

实际应用

Varnish Cache——分布式缓存路由

Varnish Cache 使用 Rendezvous Hashing 将请求路由到后端缓存节点。当某台缓存服务器宕机时，只有原本路由到该节点的请求（约 1/N）需要回源，其余节点的缓存命中率不受影响。

# Varnish VCL 配置示例
sub vcl_backend_fetch {
    set bereq.backend = directors.rendezvous.backend();
}

节点动态上下线频繁时（如容器化环境），Rendezvous Hashing 无需维护虚拟节点环，节省大量配置管理开销。

Apache Cassandra——Token 分配变体

Cassandra 的 token-based 分区使用一致性哈希环，但在部分场景（如 VNODES 配置）中的均匀性优化借鉴了 HRW 的思想：对每个节点计算综合得分，选取最优分配，确保数据在节点间天然均匀分布，而无需手动调整虚拟节点数量。

CDN 边缘节点选择

CDN 调度系统需要将内容请求路由到最优边缘节点，节点动态上下线频繁：

def select_edge_node(content_id: str, edge_nodes: list[str]) -> str:
    best_score = -1.0
    best_node  = None
    for node in edge_nodes:
        score = xxhash.xxh64(content_id + node).intdigest() / 2**64
        if score > best_score:
            best_score = score
            best_node  = node
    return best_node

节点上线时，只有约 1/(N+1) 的内容迁移到新节点；节点下线时，只有约 1/N 的内容需要重新路由，其余节点缓存命中率完全不受影响。

数据库读写路由

在多主复制（Multi-Master）或读副本场景中，使用 Rendezvous Hashing 将同一 key 的读请求固定路由到同一副本，提高缓存局部性：

// 将 userId 的读请求路由到固定副本，提高读缓存命中率
String replicaHost = rendezvoussHash.select(userId, readReplicas);

参考资料

原始论文：Thaler, D., & Ravishankar, C. (1996). Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Transactions on Networking, 6(1), 1-14.
扩展论文：Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent Hashing and Random Trees. STOC 1997.
带权重版本：Schindelhauer, C., & Voecking, B. (1997). Weighted Distributed Hash Tables. SPAA 2005.
Varnish Cache 文档：Varnish Software. Director Modules: Rendezvous Hashing. https://varnish-cache.org/docs/trunk/reference/vmod_directors.html
Jump Consistent Hash 对比：Lamping, J., & Veach, E. (2014). A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294.
xxHash 哈希库：https://github.com/Cyan4973/xxHash

← 返回列表

暂无评论，来留下第一条吧。

登录或注册后才能发表评论