前言在分布式缓存、分片存储、负载均衡里经常需要把某个键稳定地映射到一台服务器同一个用户 id无论请求打到哪个网关都应该落到同一台缓存节点。最直接的做法是hash(key) % NN 是节点数。它在节点不变时工作得很好一旦扩容或宕机N 改变几乎所有键的映射都会变缓存集体失效请求瞬间压到后端数据库。一致性哈希consistent hashing解决的正是「节点增减时尽量少迁移」的问题。它把哈希值空间首尾相接成一个环节点和键都映射到环上键顺时针找到的第一台节点就是归属。增加或删除一台节点只影响环上相邻的一段而不是全部。常见的误解有三个。第一以为一致性哈希能保证「每个节点负载完全均匀」实际上只靠物理节点映射分布可能相当偏斜需要虚拟节点来改善。第二以为哈希函数可以随便用std::hash但它的结果由标准库实现决定不同进程、不同版本、不同语言之间可能不一致跨进程路由会错乱。第三以为键迁移的数量有严格上界实际只能说「期望约为 1/N」具体分布仍是随机的不能拿来做容量承诺。本文实现一个带虚拟节点的一致性哈希环讲清楚查找、增删节点和哈希函数选择的要点。示例以 C17 为基准只使用标准库。一、哈希环与顺时针查找把 32 位无符号整数的取值空间想象成一个圆环0 和 2³²-1 首尾相连。每台物理节点用若干个哈希值放到环上每个键也计算一个哈希值从键的位置顺时针走遇到的第一个节点就是它的归属。如果走到环的末端还没有节点就回到环的起点。实现上不需要真的构造环形链表。用std::mapstd::uint32_t, std::string保存「哈希值 → 节点名」键有序查找时用lower_bound找第一个不小于键哈希的位置如果返回end()说明要绕回开头取begin()。这就是「顺时针」的全部含义。// 适用于 C17#include cstdint#include iostream#include map#include string#include string_viewclass ConsistentHash {public:explicit ConsistentHash(std::size_t virtual_nodes 100): virtual_nodes_(virtual_nodes) {}void add_node(const std::string node) {for (std::size_t i 0; i virtual_nodes_; i) {const std::string vnode node # std::to_string(i);ring_.emplace(fnv1a(vnode), node);}}void remove_node(const std::string node) {for (std::size_t i 0; i virtual_nodes_; i) {const std::string vnode node # std::to_string(i);ring_.erase(fnv1a(vnode));}}std::string locate(std::string_view key) const {if (ring_.empty()) return {};const std::uint32_t h fnv1a(std::string(key));auto it ring_.lower_bound(h);if (it ring_.end()) {it ring_.begin(); // 绕过环的末端回到起点}return it-second;}std::size_t ring_size() const { return ring_.size(); }private:static std::uint32_t fnv1a(const std::string s) {std::uint32_t h 2166136261u;for (unsigned char c : s) {h ^ c;h * 16777619u;}return h;}std::size_t virtual_nodes_;std::mapstd::uint32_t, std::string ring_;};这里用 FNV-1a 而不是std::hashstd::string原因是后者只保证同一进程内一致标准没有规定具体算法不同标准库、不同版本甚至不同编译选项都可能给出不同结果。如果客户端和服务端各自计算键的归属必须使用同一套确定性哈希否则同一个键会被路由到不同节点。FNV-1a 的实现只有几行结果确定适合演示生产环境通常选用分布更均匀的 64 位哈希或经过验证的哈希库具体以所用库的文档为准。lower_bound的语义是「第一个不小于 h 的位置」。如果环上恰好有一个节点的哈希等于 h键就归它如果没有归下一个更大的如果 h 比环上所有值都大归最小的那个。这三种情况合起来正好是「顺时针第一个」。二、虚拟节点让分布更均匀如果每台物理节点只在环上放一个点节点之间的弧长由哈希值随机决定。节点少的时候弧长差异可能很大某台节点可能负责环上一半的空间另一台只负责很小一段。键的数量一多负载就会明显倾斜。虚拟节点virtual node的做法是每台物理节点在环上放多个点每个点由「节点名 序号」哈希得到但都指向同一个物理节点。这样每台物理节点占据多段弧段与段分散在环上随机涨落相互抵消负载更接近平均。虚拟节点越多分布越均匀但环上的条目也越多内存占用与查找时的比较次数随之增加map查找是对数复杂度增加条目影响不大主要是内存。虚拟节点的数量没有标准答案。它取决于节点数、键数、哈希质量和对均匀性的要求。实践中的做法是先选一个经验值例如每台一百到几百个再用真实键样本统计各节点分到的键数观察最大值与最小值的比例如果不满意就增加虚拟节点或者换更好的哈希。不能凭空断言「多少个就一定均匀」因为分布依赖哈希函数与具体的键集合。虚拟节点还带来一个副作用删除节点时要把它的所有虚拟节点都从环上移除。示例里的remove_node按相同规则重新计算每个虚拟节点的哈希并erase因此add_node与remove_node必须使用完全一致的命名规则否则删不干净。命名规则一旦上线就不能随意改否则老数据会按旧规则落在旧位置新进程按新规则找不到。三、增删节点与迁移范围一致性哈希的核心承诺是增加一台节点只把环上「新节点逆时针到上一个节点」这一段原本属于后继节点的键迁移过来删除一台节点只把它负责的那一段交给后继。其余键的归属不变。这个性质不依赖于虚拟节点的数量虚拟节点只是把「一段」拆成「多小段」让迁移更分散。用示例中的环推演假设三台节点 A、B、C 各有若干虚拟节点键 k 的哈希落在 A 的某个虚拟节点与 B 的某个虚拟节点之间那么 k 归 B。加入节点 D 后如果 D 的某个虚拟节点恰好落在这个区间内k 改归 D否则仍归 B。也就是说只有落在「D 的虚拟节点与它的前驱之间」的键会迁移其他键不动。但「迁移范围小」不等于「迁移数量精确等于 1/N」。每台新节点分到的弧长是随机的可能多于平均也可能少于平均虚拟节点越多偏离平均的程度通常越小但仍然是随机变量。容量规划时应当留出余量并在扩容前用真实键分布做模拟而不是假设「一定只迁移 1/N」。查找的时间复杂度是 O(log M)M 是环上的虚拟节点总数增删一个物理节点是 O(V log M)V 是每台节点的虚拟节点数。空间复杂度是 O(M)。这些量级与键的数量无关因此一致性哈希适合键非常多、节点相对较少的场景。如果不想维护环还可以考虑 rendezvous hashing最高随机权重哈希对每个键与每台节点计算一个哈希分数取分数最高的节点。它不需要虚拟节点增删节点的迁移性质也很好代价是每次查找要对所有节点计算哈希节点数很大时不如环高效。两种方案没有绝对优劣取决于节点规模与实现复杂度。常见坑点坑点一用取模代替哈希环。❌node nodes[hash(key) % nodes.size()]节点数从 3 变成 4 时大多数键重新映射。✅ 用有序环 lower_bound增删节点只影响相邻区间。坑点二不给物理节点加虚拟节点。❌ 每台节点只放一个哈希点节点少时负载严重倾斜。✅ 每台节点放多个虚拟节点命名规则固定增删时保持一致。坑点三用std::hash做跨进程路由。❌ 客户端与服务端各自调用std::hashstd::string标准库实现不同则结果不同。✅ 使用固定的、跨平台一致的哈希算法并在协议中约定版本。坑点四lower_bound返回end()时不绕回。❌auto it ring_.lower_bound(h); return it-second;哈希最大的键访问end()UB。✅ 判断it ring_.end()后改为ring_.begin()环为空时提前返回。坑点五忽略哈希冲突。❌ 两个虚拟节点哈希相同emplace静默失败环上少一个点erase还可能删错节点。✅ 使用冲突可控的哈希与足够的位宽需要严格处理时用multimap或把节点名并入比较。坑点六增删节点的虚拟节点命名不一致。❌ 添加时用node # i删除时用node : i删不干净。✅ 把命名规则抽成一个函数添加与删除共用。坑点七重复添加同一台节点。❌ 节点重启后再次add_node同一批虚拟节点被重复插入或冲突覆盖环状态不确定。✅ 添加前检查节点是否已存在或让add_node具备幂等语义。坑点八把「期望迁移 1/N」当成硬保证。❌ 按精确的 1/N 做容量规划实际迁移量偏大导致带宽打满。✅ 用真实键样本模拟留出余量虚拟节点数量与哈希质量都要评估。总结主题要点数据结构有序map保存哈希值到节点查找lower_bound到末尾则回到begin虚拟节点每个物理节点多个哈希点改善均匀性增删只影响相邻区间其余键不动哈希函数必须确定性、跨进程一致复杂度查找 O(log M)增删 O(V log M)迁移量期望约 1/N非硬保证替代方案rendezvous hashing按节点数权衡一致性哈希的价值不是「让缓存永不失效」而是把「节点变化导致的全量重映射」缩小为「局部迁移」。实现时把环、虚拟节点、确定性哈希这三件事做对再用真实数据检查分布就能得到一个在扩容与故障时都不会引发雪崩的路由层。