网络算法 #04：Rendezvous Hashing

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

相关文章：Jump Consistent Hash · TCP 拥塞控制（CUBIC 与 BBR） · QUIC 丢包恢复与拥塞控制

目录

问题背景

取模哈希的缺陷

最简单的分片方案 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。
• 因此负载天然均匀，无需虚拟节点。

核心数据结构

完整伪代码

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 完全不受影响，无需任何迁移。

对比取模哈希

异常与边界场景

场景 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%。

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

处理方案：

1. 节点 ID 使用不可变的稳定标识（UUID、固定数字 ID），而非主机名或 IP。
2. 需要重命名时，先添加新 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 对比

三者对比总表

选择建议

与 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);

参考资料

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