title: 虚拟节点从 160 降到 40 之后最重的节点扛了 31% 的流量一致性哈希的分片账tags: 一致性哈希,分片,缓存,分布式,Javacategory: 后端一次省内存的改动引发的倾斜事情起于一次很普通的优化。我们的缓存客户端在本地维护一个哈希环每个真实节点挂 160 个虚拟节点。集群有 24 个 Redis 分片环上就是 3840 个条目用TreeMapLong, Node存。有同事在做内存分析时发现这个 TreeMap 在每个应用实例上占了几百 KB加上路由表刷新时的临时对象觉得虚拟节点 160 太多了改成了 40。改完压测没问题灰度也没问题全量上线后第三天监控报出一个分片的 CPU 到了 78%其他分片普遍在 20-30%。统计了一下 key 的分布最重的分片承担了 31.2% 的请求最轻的只有 1.4%。24 个分片理想值是每个 4.17%。我们把虚拟节点数和倾斜度的关系压测了一遍模拟 100 万个随机 key24 个物理节点虚拟节点数/物理节点环上条目数最重节点占比最轻节点占比标准差12418.7%0.3%4.82%409608.1%1.9%1.44%16038405.3%3.1%0.71%32076804.9%3.5%0.50%500120004.6%3.7%0.40%理想值 4.17%。可以看到虚拟节点数从 160 降到 40标准差翻了一倍。而线上比压测更糟31% vs 8.1%因为真实业务的 key 不是均匀随机的——我们有一批热点商品 ID 的 key 前缀高度相似哈希后落点也更集中。虚拟节点省下的那点内存和倾斜带来的容量浪费完全不成比例。3840 个条目的 TreeMap撑死几百 KB而 31% 的倾斜意味着为了扛住最重的节点整个集群要按 7.5 倍的平均值配容量。哈希环是怎么工作的先把最基础的实现写出来后面所有讨论都基于它public class ConsistentHashRouterT extends Node { private final TreeMapLong, VirtualNodeT ring new TreeMap(); private final HashFunction hashFunction; public ConsistentHashRouter(CollectionT nodes, int vNodeCount, HashFunction hf) { this.hashFunction hf; for (T node : nodes) { addNode(node, vNodeCount); } } public void addNode(T pNode, int vNodeCount) { // 从已有虚拟节点数继续编号支持动态追加 int existing countExistingReplicas(pNode); for (int i 0; i vNodeCount; i) { VirtualNodeT vNode new VirtualNode(pNode, i existing); ring.put(hashFunction.hash(vNode.getKey()), vNode); } } public void removeNode(T pNode) { IteratorLong it ring.keySet().iterator(); while (it.hasNext()) { Long key it.next(); if (ring.get(key).isVirtualNodeOf(pNode)) { it.remove(); } } } public T route(String objectKey) { if (ring.isEmpty()) { return null; } Long hashVal hashFunction.hash(objectKey); // 顺时针找第一个 hashVal 的节点 SortedMapLong, VirtualNodeT tail ring.tailMap(hashVal); Long nodeHash tail.isEmpty() ? ring.firstKey() : tail.firstKey(); return ring.get(nodeHash).getPhysicalNode(); } }逐段看第 3 行用TreeMap是因为要做顺时针找下一个红黑树的tailMap是 O(log n)。用数组加二分也行但动态增删节点时数组要整体搬移。第 15 行existing的处理是为了支持给已有节点追加虚拟节点。如果每次都从 0 编号追加时会算出重复的哈希值put覆盖掉原来的条目环上条目数对不上。第 37-38 行是环形的关键tailMap为空说明 key 的哈希值比环上所有节点都大此时要绕回环的起点取firstKey()。少了这一行最大哈希值之后的那一段 key 会全部路由失败。第 24-28 行删除节点时遍历整个环。24 个节点 × 160 个虚拟节点 3840 次遍历摘一个节点大概 0.2ms可以接受。VirtualNode的 key 生成方式很关键public class VirtualNodeT extends Node implements Node { private final T physicalNode; private final int replicaIndex; Override public String getKey() { // 形如 10.20.3.15:6379#37 return physicalNode.getKey() # replicaIndex; } public boolean isVirtualNodeOf(T pNode) { return physicalNode.getKey().equals(pNode.getKey()); } }第 8 行的拼接方式看着无所谓但它直接决定了虚拟节点在环上的分布。用ip:port#0到ip:port#159这种连续编号配合一个雪崩性好的哈希函数落点是均匀的如果哈希函数不好连续编号会导致落点也连续成团。哈希函数的选择比虚拟节点数更要命这是我们那次排查的第二个发现。原来的实现用的是String.hashCode()public long hash(String key) { return key.hashCode() 0x7fffffffL; // 取绝对值 }String.hashCode()的算法是s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]对相似字符串的输出高度相关。10.20.3.15:6379#0和10.20.3.15:6379#1的 hashCode 只差 1。这意味着一个物理节点的 160 个虚拟节点在环上几乎是挨着的 160 个点等于只有 1 个虚拟节点的效果。换成 MurmurHash3 之后同样 40 个虚拟节点的倾斜度就从 8.1% 降到了 5.9%。我们最终用的是 Guava 的实现public class Murmur3HashFunction implements HashFunction { private static final com.google.common.hash.HashFunction MURMUR Hashing.murmur3_128(0x9747b28c); // 固定 seed保证多实例一致 Override public long hash(String key) { return MURMUR.hashString(key, StandardCharsets.UTF_8).asLong() 0x7fffffffffffffffL; } }第 3 行的固定 seed 必须写死。如果用随机 seed同一个 key 在不同应用实例上会算出不同的哈希值路由到不同的 Redis 分片——缓存命中率会直接崩到接近 0。这个坑我们在测试环境撞过一次当时用的是Hashing.murmur3_128()无参版本其实它默认 seed 是 0是稳定的但另一个团队自己实现的版本用了System.nanoTime()当 seed两边混用时命中率诡异地掉到 40%。几种常见哈希函数在这个场景下的表现同样 24 节点 × 160 虚拟节点100 万 key哈希函数最重节点占比标准差单次计算耗时String.hashCode()12.4%3.10%约 8 nsMD5 取前 8 字节5.4%0.74%约 420 nsMurmurHash3 1285.3%0.71%约 35 nsxxHash645.3%0.70%约 22 nsCRC326.8%1.15%约 15 nsKetamamemcached 的经典实现用的是 MD5分布很好但计算慢。在客户端每次请求都要算一次哈希的场景下420ns 和 35ns 的差距在 10 万 QPS 下是每秒 38.5ms 的 CPU 时间不算大但也不必要。我的选择是 MurmurHash3分布接近 MD5速度接近 CRC32。扩容时到底迁移多少数据一致性哈希最常被引用的优点是扩容只迁移 1/N 的数据。这句话成立但有个前提新节点的虚拟节点要均匀插入环上。我们做过一次实测24 节点扩到 32 节点Test public void measureMigration() { ListCacheNode nodes24 buildNodes(24); ConsistentHashRouterCacheNode before new ConsistentHashRouter(nodes24, 160, new Murmur3HashFunction()); ListCacheNode nodes32 new ArrayList(nodes24); nodes32.addAll(buildNodes(24, 32)); ConsistentHashRouterCacheNode after new ConsistentHashRouter(nodes32, 160, new Murmur3HashFunction()); int moved 0; int total 1_000_000; for (int i 0; i total; i) { String key item: ThreadLocalRandom.current().nextLong(100_000_000L); if (!before.route(key).getKey().equals(after.route(key).getKey())) { moved; } } // 理论值 8/32 25%实测 24.7% System.out.printf(migration ratio %.2f%%%n, moved * 100.0 / total); }实测 24.7%和理论值 25% 基本吻合。作为对比如果用取模分片hash % 24改成hash % 32迁移比例是1 - 24/lcm(24,32)这类计算下来接近 96%——几乎全部要迁。但要注意一致性哈希的少迁移是相对取模而言的。25% 依然是 1/4 的数据要挪。如果这 25% 是缓存可以选择不迁移、让它自然过期重建代价是扩容后一段时间内缓存命中率下降如果是有状态的分片存储25% 的数据搬迁在 TB 级别下要跑好几个小时。分片策略24→32 扩容迁移量是否支持异构节点路由计算适合场景取模 hash%N约 96%否O(1)节点数固定一致性哈希约 25%是调虚拟节点数O(log n)缓存、无状态路由一致性哈希 有界负载约 27%是O(log n) 摊还有热点的缓存范围分片取决于切分点是O(log n)有序扫描需求槽位分片如 16384 槽精确可控是O(1)需要精细迁移控制我个人越来越倾向于最后一种——固定槽位。Redis Cluster 用 16384 个槽槽到节点的映射是一张显式的表。它的好处是迁移粒度可控想挪多少槽就挪多少可以一个一个槽慢慢搬随时暂停。一致性哈希的迁移是算出来的你没法说今天只迁 3%。一致性哈希更适合的是客户端路由、无中心协调的场景。我们的缓存客户端就是这样24 个 Redis 实例地址从配置中心下发客户端自己算环不需要任何中心节点维护槽表。热点 key 一致性哈希救不了那次事故还有第三层原因。即使我们把虚拟节点调回 160、换成 MurmurHash3最重的节点还是有 9% 的流量。查下来是几个爆款商品的详情 key单 key QPS 上万。一致性哈希是按 key 分布的同一个 key 永远落在同一个节点。单 key 的热点任何哈希策略都解决不了。我们的解法是在路由层加一层热点探测和本地缓存public class HotKeyAwareRouter { private final ConsistentHashRouterCacheNode router; // Caffeine 做本地缓存只放探测到的热点 private final CacheString, Object localCache; // 滑动窗口计数判断是否热点 private final LoadingCacheString, LongAdder counter; public Object get(String key) { Object local localCache.getIfPresent(key); if (local ! null) { return local; // 命中本地不走网络 } counter.get(key).increment(); Object value router.route(key).get(key); if (isHot(key)) { // 热点 key 放本地TTL 很短容忍短暂不一致 localCache.put(key, value); } return value; } private boolean isHot(String key) { LongAdder adder counter.getIfPresent(key); return adder ! null adder.sum() HOT_THRESHOLD; } }第 5 行的本地缓存我们配的是最大 5000 条、写后过期 3 秒。3 秒是和业务方谈出来的商品价格允许 3 秒的不一致库存不允许库存走另一条链路。第 14 行的计数器用LongAdder而不是AtomicLong高并发下分段累加的性能差距在我们的压测里是 3 倍以上。第 17 行只有判定为热点才放本地。全部放本地的话5000 条的容量会被冷 key 冲刷掉热点反而留不住。上线后最重节点的流量从 9% 降到 5.6%接近理想值。复盘数据完整修复虚拟节点 160、MurmurHash3、热点本地缓存之后指标事故期间修复后最重分片流量占比31.2%5.6%最重分片 CPU78%26%缓存整体命中率94.1%96.8%路由计算耗时单次约 9nshashCode约 37ns客户端环内存占用约 90KB约 350KB路由耗时涨了 28 纳秒环内存多占 260KB。这两个数字和最重节点 CPU 从 78% 降到 26%放在一起我觉得没什么可犹豫的。那位提出减少虚拟节点省内存的同事后来在复盘会上说了句让我印象很深的话他当时看到的是 TreeMap 在 heap dump 里排进前 50但没意识到这个数据结构的作用是换取整个集群的容量效率。局部的内存指标和全局的资源效率优化方向可能是相反的。我的建议虚拟节点数不要低于 150。Ketama 用 160、Dubbo 默认 160、Cassandra 早期用 256这些数字不是拍脑袋来的。内存代价是每个虚拟节点几十字节24 个节点也就几百 KB没有任何省的必要。哈希函数不要用String.hashCode()。这条我想强调一下因为网上很多一致性哈希的教学代码就是这么写的照抄进生产环境的人不在少数。如果你的分片是有状态存储不是缓存我更推荐槽位分片而不是一致性哈希。迁移可控这一点在真出问题需要紧急扩容时价值远超少迁移一点数据。最后一个问题留给评论区我们现在的热点探测是每个应用实例各自统计的一个 key 在实例 A 上是热点、在实例 B 上可能计数不够。要做全局热点探测就得引入上报和聚合链路变长、延迟变高。你们是接受实例级的近似判断还是搭了中心化的热点探测