brpc 一致性哈希（Consistent Hashing）负载均衡：原理、源码实现与配置指南

brpc 一致性哈希（Consistent Hashing）负载均衡：原理、源码实现与配置指南

【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C++ Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. "brpc" means "better RPC".项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc

本文基于 brpc 官方文档《一致性哈希》整理扩充而成，并结合 consistent_hashing_load_balancer.cpp、hasher.cpp 等源码佐证实现细节。

1. 为什么需要一致性哈希

在访问缓存集群等场景中，我们希望同一种请求尽量落到同一台后端机器上，从而充分利用机器上已有的缓存，让不同机器承载不同的稳定 working set；而不是把请求随机散落到所有机器，那样会迫使每台机器都缓存全部内容，最终因容量不足形成颠簸，表现糟糕。

普通的取模哈希（modulo hashing）可以满足这个需求：当有 n 台服务器时，输入 x 总是发送到第hash(x) % n台服务器。但问题在于——当服务器数量从 n 变为 m 时，hash(x) % n与hash(x) % m往往不相等，几乎所有请求的发送目的地都会发生变化：

• 如果目的地是缓存服务，所有缓存将同时失效；
• 原本被缓存遮挡的数据库或计算服务将直接暴露在请求洪峰之下，引发请求风暴（request storm），进而触发雪崩。

一致性哈希（Consistent Hashing）是一种特殊的哈希算法：在增加服务器时，发向每个老节点的请求中只会有一部分转向新节点，从而实现平滑迁移。其概念最早由 Karger 等人在论文《Consistent Hashing and Random Trees》中提出。

1.1 一致性哈希的四个性质

一致性哈希需要满足以下四个性质：

2. 实现方式：Hash Ring 与虚拟节点

2.1 基本 Hash Ring

brpc 的实现思路是：将所有 server 的 32 位哈希值映射到 32 位整数值域上，构成一个哈希环（Hash Ring）。环上的每个区间与一个 server 唯一对应，如果一个 key 落在某个区间内，它就被分流到对应的 server 上。

• 删除 server：它对应的区间会归属于相邻的 server，原属于它的所有请求都会转移到相邻节点；
• 增加 server：它会分割某个 server 的区间，并承载落在该区间上的所有请求。

但单纯使用 Hash Ring 很难满足上一节提到的四个性质，主要有两个问题：

1. 在机器数量较少时，各区间大小会很不平衡（balance 差）；
2. 当一台机器故障时，它的压力会完全转移到另一台机器，后者很可能无法承载（load 差）。

2.2 虚拟节点（Virtual Node）

为了解决上述问题，brpc 为每个 server 计算 m 个哈希值，从而把 32 位整数值域划分为 n×m 个区间。当 key 落到某个区间时，分流到对应的 server 上。这些额外的哈希值使得区间划分更加均匀，被称为虚拟节点（Virtual Node）。

• 删除 server 时：它对应的 m 个区间会分别并入相邻的区间，该 server 上的请求会较为平均地转移到其他 server 上（而不是全部压到一台）；
• 增加 server 时：它会分割 m 个现有区间，从对应 server 上分别转移一些请求过来（平滑迁移，只影响部分请求）。

2.3 有序数组 + 二分查找的数据结构选择

由于节点故障和变化不常发生，brpc 选择了修改复杂度为 O(n) 的有序数组来存储 hash ring，每次分流使用二分查找选择对应的机器。因为存储是连续的，查找效率比基于平衡二叉树的实现更高。

从源码看，这个选择体现在 consistent_hashing_load_balancer.h 中：哈希环以butil::DoublyBufferedData<std::vector<Node> >存储，Node是一个有序结构体，包含hash、server_sock、server_addr三个字段，其operator<先按 hash 比较，再按 server_addr 和 tag 比较，以保证多客户端之间排序稳定。

在 consistent_hashing_load_balancer.cpp 的SelectServer中，使用std::lower_bound在有序数组上做二分查找定位第一个 hash 值不小于请求码的节点；若到达数组末尾，则回绕到begin()——这正是"环"的语义。此后沿环顺时针向后查找，跳过被ExcludedServers排除或不可用的节点（最后一跳兜底接受），从而在节点故障时也能把请求转移给环上的后继节点。

线程安全性由Double Buffered Data机制保证（读写分离的双缓冲，背景线程负责重建），详见 lalb.md 的 DoublyBufferedData 章节。

3. 使用方式

brpc 内置了分别基于murmurhash3和md5两种哈希算法的实现，使用需要做两件事：

3.1 指定负载均衡算法

在Channel.Init时，将load_balancer_name指定为"c_murmurhash"或"c_md5"：

Channel channel; ChannelOptions options; // ... 设置 options channel.Init("list://...", "c_murmurhash", &options); // 或 "c_md5"

3.2 设置请求的哈希码

发起 RPC 时，通过Controller::set_request_code(uint64_t)填入请求的 hash code：

Controller cntl; cntl.set_request_code(hash_of_request_key); // 例如主键的哈希值 channel.CallMethod(nullptr, &cntl, &request, &response, nullptr);

注意：request 的 hash 算法并不需要和负载均衡器的 hash 算法保持一致，只要 hash 的值域是 32 位无符号整数即可。例如用c_murmurhash算法，也可以用 MD5 计算请求码。

在源码层面，controller.h 中的set_request_code会设置_request_code并打上FLAGS_REQUEST_CODE标记；SelectServer 会首先校验in.has_request_code，未设置 request_code 时直接返回EINVAL，RPC 失败；同时要求request_code必须为 32 位（大于UINT_MAX同样返回EINVAL）。

3.3 算法选型建议

• 由于memcache 默认使用 MD5计算 key 的哈希值，访问 memcached 集群时请选择c_md5以保证兼容性（即请求码的计算方式与环上节点哈希的取值方式一致，保证同 key 同节点）；
• 其他场景可以选择c_murmurhash，以获得更高的性能和更均匀的分布（murmurhash3 为专为哈希表设计的快速非加密哈希，见 hasher.cpp 对MurmurHash3_x86_32的封装）。

4. 虚拟节点个数配置

4.1 全局默认值：-chash_num_replicas

通过 gflags 参数-chash_num_replicas可设置默认的虚拟节点个数，默认值为 100：

./your_server -chash_num_replicas=100

该参数在源码中定义于 consistent_hashing_load_balancer.cpp：DEFINE_int32(chash_num_replicas, 100, ...)，并在ConsistentHashingLoadBalancer构造函数中作为_num_replicas的初值（见 L172-L177）。

4.2 按 Channel 覆盖：replicas=<num>

对于某些特殊场合，需要对虚拟节点个数做自定义配置，可以在load_balancer_name上追加replicas=<num>参数：

Channel channel; channel.Init("http://...", "c_murmurhash:replicas=150", &options);

该参数的解析实现在 SetParameter：key == "replicas"时通过butil::StringToSizeT解析并写入_num_replicas，从而覆盖全局默认值。

虚拟节点如何生成？在 DefaultReplicaPolicy::Build 中，每个 server 按"<ip:port>-<i>"的字符串（i 从 0 到 num_replicas-1）计算哈希值，生成_num_replicas个节点并排序后合并进哈希环——这就是"一个 server 对应 m 个虚拟节点"的落地实现。若开启-consistent_hashing_enable_server_tag（默认 false，见 L39-L40），字符串会追加 server 的 tag，用于区分同一地址上的多个带 tag 的 server。

4.3 哈希函数的底层实现

两种内置哈希算法的 32 位取值实现在 hasher.cpp：

• MurmurHash32（L59-L63）：封装butil::MurmurHash3_x86_32，性能高、分布均匀；
• MD5Hash32（L35-L42）：对输入做 MD5 后取 digest 前 4 字节拼接为 32 位整数，与 memcached 的 key 哈希口径兼容。

5. 负载均衡器注册与更多算法

在 global.cpp 中，brpc 全局注册了多个一致性哈希相关负载均衡器：

LoadBalancerExtension()->RegisterOrDie("c_murmurhash", &g_ext->ch_mh_lb); LoadBalancerExtension()->RegisterOrDie("c_md5", &g_ext->ch_md5_lb); LoadBalancerExtension()->RegisterOrDie("c_ketama", &g_ext->ch_ketama_lb); LoadBalancerExtension()->RegisterOrDie("c_murmurhash_bl", &g_ext->ch_mh_bl_lb);

可以看到，除文档中提到的两种基础算法外，仓库还提供了：

• c_ketama：ketama 兼容的一致性哈希（memcached 经典一致性哈希方案），实现于KetamaReplicaPolicy（见 consistent_hashing_load_balancer.cpp#L106-L150），它要求虚拟节点数为 4 的倍数，每个虚拟节点由一次 MD5 digest 派生出 4 个环上点，保证与 libketama 生态的 key 分布兼容；
• c_murmurhash_bl：带负载上限的一致性哈希（"Consistent Hashing with Bounded Loads"，Mirrokni et al., CACM 2017）。其哈希环与c_murmurhash完全相同，但为每台服务器维护在途请求计数，并设置容量上限ceil(load_factor * 平均在途请求数)；当哈希命中的服务器已达上限时，请求沿哈希环顺时针溢出到下一台有余量的服务器，因此热点 key 不再压垮单台服务器，且溢出请求总是落到环上固定的后继节点，对缓存仍然友好。系数默认来自-chash_bounded_load_factor（默认 1.25，必须大于 1），可按 channel 覆盖：c_murmurhash_bl:load_factor=1.5。其SelectServer实现见 consistent_hashing_load_balancer.cpp#L525-L602。

更完整的负载均衡算法清单（rr、random、weighted_round_robin 等）可参考 client.md 的负载均衡章节。

6. 常见问题与排查建议

6.1 报错 "Controller.set_request_code() is required"

在 SelectServer 中，若in.has_request_code为 false，会打印Controller.set_request_code() is required并返回EINVAL。排查方法：确认发起 RPC 前调用了cntl.set_request_code()，且传入的 code 不大于UINT_MAX。

6.2 如何评估负载是否均衡

brpc 为一致性哈希负载均衡器实现了Describe方法（见 consistent_hashing_load_balancer.cpp#L349-L377），在 verbose 模式下会输出每个 server 占用的哈希环区间长度（归一化为 0~1 的负载比例）以及所有节点负载的标准差deviation，可用来量化评估当前副本数下各节点的负载均衡程度。

6.3 请求码与环哈希口径的一致性

一致性哈希只保证"哈希码相同的请求落到同一节点"。若要保证"同一业务 key 落到同一节点"，需要保证请求码的哈希算法与环节点哈希口径在目标场景下一致（例如 memcached 用c_md5）。这是使用一致性哈希最容易踩的坑，务必根据业务 key 的哈希口径选择合适的算法。

7. 总结

掌握 brpc 一致性哈希的上述原理与配置细节后，你可以在缓存集群、KV 存储访问等需要"同 key 同节点"的场景中正确选型并调优，同时理解其平滑迁移、故障转移（顺时针查找可用后继节点）与热点防护（bounded load 变体）的底层机制。

【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C++ Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. "brpc" means "better RPC".项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc