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 一致性哈希的四个性质一致性哈希需要满足以下四个性质性质英文含义平衡性Balance每个节点被选到的概率是 O(1/n)即请求在节点间大致均匀分布单调性Monotonicity新节点加入时请求只在老节点与新节点之间移动不在老节点之间迁移节点被删除时不影响落在其他节点上的请求分散性Spread当上游机器看到不同的下游列表时上线时及不稳定网络中较常见同一个请求尽量映射到少量节点上负载Load当上游机器看到不同的下游列表时保证每台下游分到的请求数量尽量一致2. 实现方式Hash Ring 与虚拟节点2.1 基本 Hash Ringbrpc 的实现思路是将所有 server 的 32 位哈希值映射到 32 位整数值域上构成一个哈希环Hash Ring。环上的每个区间与一个 server 唯一对应如果一个 key 落在某个区间内它就被分流到对应的 server 上。删除 server它对应的区间会归属于相邻的 server原属于它的所有请求都会转移到相邻节点增加 server它会分割某个 server 的区间并承载落在该区间上的所有请求。但单纯使用 Hash Ring 很难满足上一节提到的四个性质主要有两个问题在机器数量较少时各区间大小会很不平衡balance 差当一台机器故障时它的压力会完全转移到另一台机器后者很可能无法承载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::DoublyBufferedDatastd::vectorNode 存储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_md5Channel channel; ChannelOptions options; // ... 设置 options channel.Init(list://..., c_murmurhash, options); // 或 c_md53.2 设置请求的哈希码发起 RPC 时通过Controller::set_request_code(uint64_t)填入请求的 hash codeController 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 时直接返回EINVALRPC 失败同时要求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_replicas100该参数在源码中定义于 consistent_hashing_load_balancer.cppDEFINE_int32(chash_num_replicas, 100, ...)并在ConsistentHashingLoadBalancer构造函数中作为_num_replicas的初值见 L172-L177。4.2 按 Channel 覆盖replicasnum对于某些特殊场合需要对虚拟节点个数做自定义配置可以在load_balancer_name上追加replicasnum参数Channel channel; channel.Init(http://..., c_murmurhash:replicas150, options);该参数的解析实现在 SetParameterkey 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.cppMurmurHash32L59-L63封装butil::MurmurHash3_x86_32性能高、分布均匀MD5Hash32L35-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_ketamaketama 兼容的一致性哈希memcached 经典一致性哈希方案实现于KetamaReplicaPolicy见 consistent_hashing_load_balancer.cpp#L106-L150它要求虚拟节点数为 4 的倍数每个虚拟节点由一次 MD5 digest 派生出 4 个环上点保证与 libketama 生态的 key 分布兼容c_murmurhash_bl带负载上限的一致性哈希Consistent Hashing with Bounded LoadsMirrokni et al., CACM 2017。其哈希环与c_murmurhash完全相同但为每台服务器维护在途请求计数并设置容量上限ceil(load_factor * 平均在途请求数)当哈希命中的服务器已达上限时请求沿哈希环顺时针溢出到下一台有余量的服务器因此热点 key 不再压垮单台服务器且溢出请求总是落到环上固定的后继节点对缓存仍然友好。系数默认来自-chash_bounded_load_factor默认 1.25必须大于 1可按 channel 覆盖c_murmurhash_bl:load_factor1.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. 总结要点说明核心目的相同请求尽量落在同一后端扩容/缩容时只迁移部分请求避免缓存雪崩数据结构有序数组存储虚拟节点哈希环 二分查找定位Double Buffered Data 保证线程安全虚拟节点每 server 默认 100 个-chash_num_replicas可按 channel 覆盖replicasnum内置算法c_murmurhash性能好、分布均匀、c_md5兼容 memcached、c_ketama、c_murmurhash_bl带负载上限使用方式Init 时指定load_balancer_name 每次 RPC 前set_request_code()32 位无符号适合场景缓存集群、memcached/redis 客户端、需要 key 级亲和性的存储与检索服务掌握 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 一致性哈希的四个性质一致性哈希需要满足以下四个性质性质英文含义平衡性Balance每个节点被选到的概率是 O(1/n)即请求在节点间大致均匀分布单调性Monotonicity新节点加入时请求只在老节点与新节点之间移动不在老节点之间迁移节点被删除时不影响落在其他节点上的请求分散性Spread当上游机器看到不同的下游列表时上线时及不稳定网络中较常见同一个请求尽量映射到少量节点上负载Load当上游机器看到不同的下游列表时保证每台下游分到的请求数量尽量一致2. 实现方式Hash Ring 与虚拟节点2.1 基本 Hash Ringbrpc 的实现思路是将所有 server 的 32 位哈希值映射到 32 位整数值域上构成一个哈希环Hash Ring。环上的每个区间与一个 server 唯一对应如果一个 key 落在某个区间内它就被分流到对应的 server 上。删除 server它对应的区间会归属于相邻的 server原属于它的所有请求都会转移到相邻节点增加 server它会分割某个 server 的区间并承载落在该区间上的所有请求。但单纯使用 Hash Ring 很难满足上一节提到的四个性质主要有两个问题在机器数量较少时各区间大小会很不平衡balance 差当一台机器故障时它的压力会完全转移到另一台机器后者很可能无法承载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::DoublyBufferedDatastd::vectorNode 存储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_md5Channel channel; ChannelOptions options; // ... 设置 options channel.Init(list://..., c_murmurhash, options); // 或 c_md53.2 设置请求的哈希码发起 RPC 时通过Controller::set_request_code(uint64_t)填入请求的 hash codeController 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 时直接返回EINVALRPC 失败同时要求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_replicas100该参数在源码中定义于 consistent_hashing_load_balancer.cppDEFINE_int32(chash_num_replicas, 100, ...)并在ConsistentHashingLoadBalancer构造函数中作为_num_replicas的初值见 L172-L177。4.2 按 Channel 覆盖replicasnum对于某些特殊场合需要对虚拟节点个数做自定义配置可以在load_balancer_name上追加replicasnum参数Channel channel; channel.Init(http://..., c_murmurhash:replicas150, options);该参数的解析实现在 SetParameterkey 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.cppMurmurHash32L59-L63封装butil::MurmurHash3_x86_32性能高、分布均匀MD5Hash32L35-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_ketamaketama 兼容的一致性哈希memcached 经典一致性哈希方案实现于KetamaReplicaPolicy见 consistent_hashing_load_balancer.cpp#L106-L150它要求虚拟节点数为 4 的倍数每个虚拟节点由一次 MD5 digest 派生出 4 个环上点保证与 libketama 生态的 key 分布兼容c_murmurhash_bl带负载上限的一致性哈希Consistent Hashing with Bounded LoadsMirrokni et al., CACM 2017。其哈希环与c_murmurhash完全相同但为每台服务器维护在途请求计数并设置容量上限ceil(load_factor * 平均在途请求数)当哈希命中的服务器已达上限时请求沿哈希环顺时针溢出到下一台有余量的服务器因此热点 key 不再压垮单台服务器且溢出请求总是落到环上固定的后继节点对缓存仍然友好。系数默认来自-chash_bounded_load_factor默认 1.25必须大于 1可按 channel 覆盖c_murmurhash_bl:load_factor1.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. 总结要点说明核心目的相同请求尽量落在同一后端扩容/缩容时只迁移部分请求避免缓存雪崩数据结构有序数组存储虚拟节点哈希环 二分查找定位Double Buffered Data 保证线程安全虚拟节点每 server 默认 100 个-chash_num_replicas可按 channel 覆盖replicasnum内置算法c_murmurhash性能好、分布均匀、c_md5兼容 memcached、c_ketama、c_murmurhash_bl带负载上限使用方式Init 时指定load_balancer_name 每次 RPC 前set_request_code()32 位无符号适合场景缓存集群、memcached/redis 客户端、需要 key 级亲和性的存储与检索服务掌握 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考