网络算法 #10：Maglev Hashing

Maglev Hashing 通过预计算一张固定大小的查找表将路由操作降至 O(1)，同时保持与一致性哈希相同的最小迁移量（1/N），是 Google GFE（Google Frontend）负载均衡器的核心算法，也是 ECMP 路由的工业标准之一。

maglev lookup table

章节	说明
问题背景	为什么 Google 需要新的哈希方案
核心数据结构：查找表	M 大小的查找表，O(1) 查询
偏好序列生成	offset + skip 的双哈希构造
查找表填充算法	轮流填充，先到先得
扩缩容时的迁移	1/N 迁移量证明
与其他一致性哈希对比	四种方案横向比较
实际应用	GFE、ECMP、Katran
参考资料	论文与文档

问题背景

Google GFE 每秒处理数百万个连接，对负载均衡提出了苛刻要求：

极快的查询速度：经典一致性哈希 O(log N) 在百万 QPS 下仍有开销
最小连接迁移：服务器上下线时，只应迁移必要的连接（TCP 长连接不能断）
均匀分布：每台后端承受相同的负载

Jump Consistent Hash 满足 1 和 3，但不支持随机删除节点。经典一致性哈希满足 2 和 3，但查询较慢。Maglev 同时满足全部三点。

核心数据结构：查找表

Maglev 的核心是一张大小为 M 的数组 lookup[0..M-1]，每个槽位存储一个后端编号：

lookup = [B0, B1, B2, B0, B1, B2, B0]  // M=7，3个后端

查询：
  backend = lookup[hash(key) % M]       // O(1)，直接数组索引

M 的选择：必须是质数，且 M >> N（后端数量）。生产环境通常使用 M=65537。质数保证了偏好序列能均匀覆盖所有槽位，避免周期性分布。

偏好序列生成

每台后端服务器 b 都有一个长度为 M 的「偏好序列」（permutation），表示它希望占据的槽位顺序：

def generate_permutation(backend_name, M):
    # 双哈希：两个不同的哈希函数
    offset = hash1(backend_name) % M
    skip   = hash2(backend_name) % (M - 1) + 1   # skip ∈ [1, M-1]，保证遍历所有槽位

    permutation = []
    cur = offset
    for _ in range(M):
        permutation.append(cur)
        cur = (cur + skip) % M
    return permutation

数学保证：当 M 是质数时，任意 skip ∈ [1, M-1] 都能生成 0..M-1 的完整排列（费马小定理）。

示例（M=7）：

后端	offset	skip	偏好序列
B0	3	4	[3, 0, 4, 1, 5, 2, 6]
B1	0	2	[0, 2, 4, 6, 1, 3, 5]
B2	3	1	[3, 4, 5, 6, 0, 1, 2]

查找表填充算法

所有后端轮流按偏好序列填充查找表，已被占用的槽位跳过（先到先得）：

def build_lookup(backends, M):
    lookup  = [-1] * M
    filled  = 0
    ptrs    = [0] * len(backends)   # 每个后端当前偏好序列的指针

    while filled < M:
        for i, b in enumerate(backends):
            # 找到该后端偏好序列中第一个未被占用的槽位
            j = ptrs[i]
            while lookup[b.perm[j]] != -1:
                j += 1
            ptrs[i] = j + 1
            slot = b.perm[j]
            lookup[slot] = i
            filled += 1
            if filled == M:
                break
    return lookup

填充结果（M=7，3个后端）：

轮次1: B0→槽3, B1→槽0, B2→槽3(占用)→槽4
轮次2: B0→槽0(占用)→槽4(占用)→槽1, B1→槽2, B2→槽5
轮次3: B0→槽5(占用)→槽2(占用)→槽6, B1→槽6(占用)→...

lookup = [B1, B0, B1, B0, B2, B2, B0]
每个后端占 2~3 个槽位，分布均匀

时间复杂度：O(M × log M) 预处理，O(1) 查询。

扩缩容时的迁移

增加后端

新增后端 B3 后，重新计算查找表。由于 B3 会「抢占」原本属于其他后端的部分槽位，迁移量约为：

迁移比例 ≈ 1/(N+1)

与经典一致性哈希完全相同——这是理论最优值，不可能更少。

删除后端

删除某台后端后，其占用的槽位被重新分配给其他后端，迁移量约为 1/N。

⚠️ Maglev 不支持增量更新：每次拓扑变化都需要重新计算整张查找表（O(M × log M)）。M=65537 时计算耗时约 1ms，对生产系统可接受。

与其他一致性哈希对比

维度	经典一致性哈希	Jump CH	Rendezvous	Maglev
查询复杂度	O(log N)	O(ln N)	O(N)	O(1)
空间复杂度	O(NK)	O(1)	O(1)	O(M)（M≈65537）
支持随机删除	✅	❌	✅	✅（重建表）
负载均匀性	K 足够大时好	完美	好	非常好
迁移量	1/(N+1)	1/(N+1)	1/(N+1)	1/(N+1)
重建开销	无需重建	无状态	无状态	O(M log M)
适用场景	KV 集群	Google 内部	CDN	L4 负载均衡

实际应用

Google GFE

Google Frontend（GFE）是所有 Google 服务的入口负载均衡器。Maglev 用于：

将 TCP/UDP 连接哈希到后端 GFE 集群
保证同一客户端的多个连接路由到同一后端（连接亲和性）
服务器上下线时最小化连接重建

原始论文（2016 NSDI）报告：Maglev 在 10Gbps NIC 上以软件实现达到全线速转发。

Facebook Katran

Facebook 开源的 L4 负载均衡器 Katran 基于 eBPF，其哈希算法借鉴了 Maglev 的查找表思想：

在 XDP 层（数据包到达即处理）完成路由
延迟约 50μs，远低于用户态方案

ECMP 路由

ECMP（Equal-Cost Multi-Path）路由器使用 Maglev 风格的查找表对 IP 五元组做哈希，保证同一流的所有数据包经过同一条路径（避免乱序）。

参考资料

参考资料

Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer (NSDI 2016) — Maglev 原论文

Jump Consistent Hash（O(1) 空间，不支持随机删除）

经典一致性哈希（虚拟节点）（支持动态增删，查询 O(log N)）