加一台机器缓存几乎全挂——这是很多线上事故的第一页设想你有一个缓存集群N台机器最自然的写法是hash(key) % N。简单、均匀、易懂。然后业务涨了你加一台机器N变成N1。这时几乎全部key的目标位置都变了。缓存全部miss请求像洪水一样毫无遮挡地冲向下游数据库——这就是缓存雪崩也是很多线上事故的剧本第一页。今天要解决的就是能不能让节点数量变化时只有尽可能少的key需要迁移答案就是1997年Karger等人提出的一致性哈希——把节点和key都映射到一个虚拟的哈希环上加一台机器只影响环上相邻的一小段key。我们还会处理它自带的两个副作用数据倾斜用虚拟节点解决和如何高效找后继用有序结构 二分。 问题描述系统设计题设计一个分布式缓存的路由方案满足均衡性key尽可能均匀分布在N个节点上单调性新增/下线节点时已有key 映射尽可能少地改变分散性客户端能自己算路由不需要中心节点容错性一台宕机流量分摊给剩下的机器而不是砸向某一台接口合约add_node(10.0.0.1) → 加入集群 remove_node(10.0.0.1) → 摘掉节点 get_node(user:10086) → 返回路由到的节点隐藏约束集群可能几百上千台key量级百亿。get_node必须 O(logN)且路由计算要在客户端本地完成。 核心思路把key和节点映射到同一个环第一步传统取模到底有多糟hash(key) % N分布很均匀但N从3变4时%3和%4的结果几乎对不上——理论迁移率N/(N1)3→4时约75%。实测数据10000个key方案3节点 → 4节点时迁移比例hash(key) % N74.86%一致性哈希带虚拟节点27.54%75% 的迁移意味着缓存命中率瞬间从95%掉到接近0数据库QPS放大几十倍。第二步核心洞察——映射到同一个哈希环定义值域[0, 2³²)首尾相接成一个圆环用同一个哈希函数把每个节点映射到环上的一个点用同一个哈希函数把每个key也映射到环上的一个点规则key顺时针往前走遇到的第一个节点就是它的归属0 / 2³² ● ┌───────────────┐ │ │ NodeA ● │ ● key9 │ │ │ ● NodeB │ ↑ ● key5 │ NodeC “顺时针第一个就是你”为什么迁移量小新节点NodeD落到某个位置。只有落在“NodeD的前驱”到“NodeD”这段弧上的key会变——它们原本顺时针遇到的是NodeD的后继现在先撞上NodeD。迁移量 ≈1/(N1)而不是N/(N1)单调性天然成立新增节点只“抢走”别人的一部分宕机同理只影响挂掉节点那段弧不会波及全局第三步副作用一——数据倾斜与虚拟节点节点少时它们的哈希位置可能挤在一起。实测3个节点NodeA 3669998473 NodeC 3687093430 NodeB 3783660063 ↑ 三者全挤在3.67~3.79e9这个窄区间后果剩下那条长达37亿的大弧全归NodeA管NodeA扛了97%的流量。解法虚拟节点Virtual Node——不要把一个物理节点映射成一个点而是映射成K个NodeA → hash(NodeA#0), hash(NodeA#1), ..., hash(NodeA#149)实测5 节点 / 50000 key虚拟节点数 K最大偏离理想 20%K 1±24.4个百分点K 20±6.4个百分点K 100±3.0个百分点K 300±1.7个百分点工程上常用K 100~300。虚拟节点还有一个隐藏好处给性能好的机器分配更多虚拟节点天然实现加权一致性哈希。第四步副作用二——O(logN)找后继环上的节点位置是有序的。“顺时针遇到的第一个节点”找 ≥ h的最小值lower bound没有就回绕到环首。这就是二分查找的直接应用语言容器 API复杂度JavaTreeMapLong, StringceilingEntry(h)O(log(KN))Pythonsorted_keysbisect_leftO(log(KN))Cstd::mapuint32_t, Nodelower_boundO(log(KN))️ 图解算法手把手走一遍环上先有3个节点按升序NodeA → NodeC → NodeB →回绕→ NodeA。各段弧归属弧顺时针归属节点(0 … NodeA]NodeA(NodeA … NodeC]NodeC(NodeC … NodeB]NodeB(NodeB … 2³²) ∪ (0 … ]回绕NodeA放入10个keykeyhash值归属key90.216e9NodeAkey30.909e9NodeAkey51.035e9NodeAkey81.565e9NodeAkey61.685e9NodeAkey22.030e9NodeAkey13.266e9NodeAkey43.405e9NodeAkey104.046e9NodeA回绕key74.187e9NodeA回绕注意这就是数据倾斜的真实模样——10个key全给NodeA这就是必须有虚拟节点的原因。现在加入NodeD 1,485,806,211。新环顺序NodeD → NodeA → NodeC → NodeB → 回绕 → NodeD谁要搬家keyhash加NodeD前加NodeD后是否搬家key90.216e9NodeANodeD✅key30.909e9NodeANodeD✅key51.035e9NodeANodeD✅key81.565e9NodeANodeA—key61.685e9NodeANodeA—key22.030e9NodeANodeA—key13.266e9NodeANodeA—key43.405e9NodeANodeA—key104.046e9NodeANodeD✅key74.187e9NodeANodeD✅搬家的5个 key正好是落在NodeD那段弧里的那些其余5个一字未改。这就是一致性哈希的全部价值——迁移量是“必须迁移的量”没有任何冤枉扩大。 代码实现Python JavaPython版importhashlibfrombisectimportbisect_leftclassConsistentHash:一致性哈希哈希环 虚拟节点 二分找后继def__init__(self,nodesNone,virtual_nodes150):self.vnodesvirtual_nodes self.ring{}# 虚拟节点hash - 物理节点名self.sorted_hashes[]# 排好序的hash列表self.nodesset()fornin(nodesor[]):self.add_node(n)staticmethoddef_hash(s:str)-int:把任意字符串映射到 [0, 2^32) 上的一个点returnint(hashlib.md5(s.encode(utf-8)).hexdigest()[:8],16)defadd_node(self,node:str)-None:ifnodeinself.nodes:returnself.nodes.add(node)foriinrange(self.vnodes):hself._hash(f{node}#{i})# 虚拟节点一个物理节点造K个分身self.ring[h]node self.sorted_hashessorted(self.ring)defremove_node(self,node:str)-None:ifnodenotinself.nodes:returnself.nodes.discard(node)forhin[kfork,vinself.ring.items()ifvnode]:delself.ring[h]self.sorted_hashessorted(self.ring)defget_node(self,key:str)-str:key 顺时针遇到的第一个节点ifnotself.sorted_hashes:returnNonehself._hash(key)idxbisect_left(self.sorted_hashes,h)# 第一个 h的位置ifidxlen(self.sorted_hashes):idx0# 越过环尾 → 回绕到环首returnself.ring[self.sorted_hashes[idx]]Java 版importjava.nio.charset.StandardCharsets;importjava.security.MessageDigest;importjava.util.*;publicclassConsistentHash{privatefinalTreeMapLong,StringringnewTreeMap();privatefinalSetStringnodesnewHashSet();privatefinalintvirtualNodes;publicConsistentHash(ListStringnodes,intvirtualNodes){this.virtualNodesvirtualNodes;for(Stringn:nodes)addNode(n);}privatelonghash(Strings){try{MessageDigestmdMessageDigest.getInstance(MD5);byte[]dmd.digest(s.getBytes(StandardCharsets.UTF_8));return((long)(d[0]0xFF)24)|((long)(d[1]0xFF)16)|((long)(d[2]0xFF)8)|((long)(d[3]0xFF));}catch(Exceptione){thrownewRuntimeException(e);}}publicsynchronizedvoidaddNode(Stringnode){if(!nodes.add(node))return;for(inti0;ivirtualNodes;i){ring.put(hash(node#i),node);}}publicsynchronizedvoidremoveNode(Stringnode){if(!nodes.remove(node))return;for(inti0;ivirtualNodes;i){ring.remove(hash(node#i));}}publicStringgetNode(Stringkey){if(ring.isEmpty())returnnull;longhhash(key);Map.EntryLong,Stringentryring.ceilingEntry(h);// h的最小键if(entrynull)entryring.firstEntry();// 回绕到环首returnentry.getValue();}}⚠️防坑提醒必看虚拟节点的 key 必须带不同后缀node#0…node#K-1否则全重叠成一个点。Java用long存哈希值——用int负数会打乱环顺序回绕逻辑直接失效。ceilingEntry返回 null 就取firstEntry()——这一步就是“环”的具象化。哈希函数选MD5/SHA取前若干位别用String.hashCode()分布质量差。⏱️ 复杂度分析面试必问操作时间空间get_nodeO(log(KN)) ≈ O(logN)—add_node/remove_nodeO(K·log(KN))—总空间—O(K·N)N1000、K200时20万个条目几MB内存放在每个客户端本地毫无压力。核心收益节点数从N变到N±1 时迁移比例约1/(N1)远优于取模的N/(N1)。 方案对比一致性哈希 vs 其他方案节点变化迁移量中心路由典型使用者hash % N≈ N/(N1)否早期/小规模一致性哈希 虚拟节点≈ 1/(N1)否Memcached、Dynamo、CassandraRedis Cluster 哈希槽精确可控轻量Redis ClusterRendezvous Hashing≈ 1/(N1)否GitHub GLB、Envoy 面试追问模拟提前准备惊艳全场Q1传统取模为什么不行hash(key) % N的分母N直接参与映射计算N一变几乎所有key全变3→4时迁移率75%实测74.86%。直接后果是缓存大面积失效请求穿透到数据库形成缓存雪崩。它也不满足单调性——想只挪 1% 流量都做不到。Q2虚拟节点解决了什么问题解决数据倾斜。节点少时位置随机可能扎堆实测 3 个节点全挤在一个窄区间导致NodeA独占大弧、承接97%的key。虚拟节点让每个物理节点在环上有K个散布的段大数定律生效后负载趋于均匀偏离度从±24pp降到±1.7pp。副作用是天然支持加权分配。Q3如何高效找后继环上的点有序这是标准的“找 ≥ h 的最小值”问题二分JavaTreeMap.ceilingEntryPythonbisect_leftCstd::map::lower_bound。返回空/越界时记得回绕到环首——忘了这一步环就退化成数轴。Q4Redis Cluster用的是一致性哈希吗不是它用哈希槽。固定16384个槽路由是CRC16(key) % 16384集群元数据维护“哪个槽归哪个主节点”。扩容时手动migrate槽迁移量精确可控。Redis追求的是可控性运维能精确指定搬哪些槽还能用ASK/MOVED做平滑过渡。Q5一致性哈希还有什么工程补丁①有界负载Google 2017 SOSP目标节点负载超平均(1ε)倍就跳过②虚拟节点按机器规格加权③故障转移虚拟节点按机架/可用区分组避免同机架同时宕机。 实战小技巧刷题党必备口诀节点key上同环顺时针找第一个虚拟节点治倾斜二分查找O(logN)。模板哈希环 TreeMap/sorted ceiling/lower_bound 回绕。防坑虚拟节点带后缀哈希值用long回绕别忘。 实际应用场景不止是刷题Memcached 客户端路由libketama经典实现Amazon Dynamo / Cassandra / Riak分区Nginx/Envoy 负载均衡hash $request_uri consistentCDN 边缘节点调度就近路由RPC 服务治理连接池选址分库分表路由规则 今日思考题K每台机器的虚拟节点数取多少合适提示工程常用100~300再往上收益递减。如果集群里有一台机器性能是别的两倍你会怎么改代码让它多扛一倍流量提示加权虚拟节点——给它分配2K个虚拟节点。
系统设计必考！一致性哈希：为什么加一台机器，75%的缓存瞬间失效？
加一台机器缓存几乎全挂——这是很多线上事故的第一页设想你有一个缓存集群N台机器最自然的写法是hash(key) % N。简单、均匀、易懂。然后业务涨了你加一台机器N变成N1。这时几乎全部key的目标位置都变了。缓存全部miss请求像洪水一样毫无遮挡地冲向下游数据库——这就是缓存雪崩也是很多线上事故的剧本第一页。今天要解决的就是能不能让节点数量变化时只有尽可能少的key需要迁移答案就是1997年Karger等人提出的一致性哈希——把节点和key都映射到一个虚拟的哈希环上加一台机器只影响环上相邻的一小段key。我们还会处理它自带的两个副作用数据倾斜用虚拟节点解决和如何高效找后继用有序结构 二分。 问题描述系统设计题设计一个分布式缓存的路由方案满足均衡性key尽可能均匀分布在N个节点上单调性新增/下线节点时已有key 映射尽可能少地改变分散性客户端能自己算路由不需要中心节点容错性一台宕机流量分摊给剩下的机器而不是砸向某一台接口合约add_node(10.0.0.1) → 加入集群 remove_node(10.0.0.1) → 摘掉节点 get_node(user:10086) → 返回路由到的节点隐藏约束集群可能几百上千台key量级百亿。get_node必须 O(logN)且路由计算要在客户端本地完成。 核心思路把key和节点映射到同一个环第一步传统取模到底有多糟hash(key) % N分布很均匀但N从3变4时%3和%4的结果几乎对不上——理论迁移率N/(N1)3→4时约75%。实测数据10000个key方案3节点 → 4节点时迁移比例hash(key) % N74.86%一致性哈希带虚拟节点27.54%75% 的迁移意味着缓存命中率瞬间从95%掉到接近0数据库QPS放大几十倍。第二步核心洞察——映射到同一个哈希环定义值域[0, 2³²)首尾相接成一个圆环用同一个哈希函数把每个节点映射到环上的一个点用同一个哈希函数把每个key也映射到环上的一个点规则key顺时针往前走遇到的第一个节点就是它的归属0 / 2³² ● ┌───────────────┐ │ │ NodeA ● │ ● key9 │ │ │ ● NodeB │ ↑ ● key5 │ NodeC “顺时针第一个就是你”为什么迁移量小新节点NodeD落到某个位置。只有落在“NodeD的前驱”到“NodeD”这段弧上的key会变——它们原本顺时针遇到的是NodeD的后继现在先撞上NodeD。迁移量 ≈1/(N1)而不是N/(N1)单调性天然成立新增节点只“抢走”别人的一部分宕机同理只影响挂掉节点那段弧不会波及全局第三步副作用一——数据倾斜与虚拟节点节点少时它们的哈希位置可能挤在一起。实测3个节点NodeA 3669998473 NodeC 3687093430 NodeB 3783660063 ↑ 三者全挤在3.67~3.79e9这个窄区间后果剩下那条长达37亿的大弧全归NodeA管NodeA扛了97%的流量。解法虚拟节点Virtual Node——不要把一个物理节点映射成一个点而是映射成K个NodeA → hash(NodeA#0), hash(NodeA#1), ..., hash(NodeA#149)实测5 节点 / 50000 key虚拟节点数 K最大偏离理想 20%K 1±24.4个百分点K 20±6.4个百分点K 100±3.0个百分点K 300±1.7个百分点工程上常用K 100~300。虚拟节点还有一个隐藏好处给性能好的机器分配更多虚拟节点天然实现加权一致性哈希。第四步副作用二——O(logN)找后继环上的节点位置是有序的。“顺时针遇到的第一个节点”找 ≥ h的最小值lower bound没有就回绕到环首。这就是二分查找的直接应用语言容器 API复杂度JavaTreeMapLong, StringceilingEntry(h)O(log(KN))Pythonsorted_keysbisect_leftO(log(KN))Cstd::mapuint32_t, Nodelower_boundO(log(KN))️ 图解算法手把手走一遍环上先有3个节点按升序NodeA → NodeC → NodeB →回绕→ NodeA。各段弧归属弧顺时针归属节点(0 … NodeA]NodeA(NodeA … NodeC]NodeC(NodeC … NodeB]NodeB(NodeB … 2³²) ∪ (0 … ]回绕NodeA放入10个keykeyhash值归属key90.216e9NodeAkey30.909e9NodeAkey51.035e9NodeAkey81.565e9NodeAkey61.685e9NodeAkey22.030e9NodeAkey13.266e9NodeAkey43.405e9NodeAkey104.046e9NodeA回绕key74.187e9NodeA回绕注意这就是数据倾斜的真实模样——10个key全给NodeA这就是必须有虚拟节点的原因。现在加入NodeD 1,485,806,211。新环顺序NodeD → NodeA → NodeC → NodeB → 回绕 → NodeD谁要搬家keyhash加NodeD前加NodeD后是否搬家key90.216e9NodeANodeD✅key30.909e9NodeANodeD✅key51.035e9NodeANodeD✅key81.565e9NodeANodeA—key61.685e9NodeANodeA—key22.030e9NodeANodeA—key13.266e9NodeANodeA—key43.405e9NodeANodeA—key104.046e9NodeANodeD✅key74.187e9NodeANodeD✅搬家的5个 key正好是落在NodeD那段弧里的那些其余5个一字未改。这就是一致性哈希的全部价值——迁移量是“必须迁移的量”没有任何冤枉扩大。 代码实现Python JavaPython版importhashlibfrombisectimportbisect_leftclassConsistentHash:一致性哈希哈希环 虚拟节点 二分找后继def__init__(self,nodesNone,virtual_nodes150):self.vnodesvirtual_nodes self.ring{}# 虚拟节点hash - 物理节点名self.sorted_hashes[]# 排好序的hash列表self.nodesset()fornin(nodesor[]):self.add_node(n)staticmethoddef_hash(s:str)-int:把任意字符串映射到 [0, 2^32) 上的一个点returnint(hashlib.md5(s.encode(utf-8)).hexdigest()[:8],16)defadd_node(self,node:str)-None:ifnodeinself.nodes:returnself.nodes.add(node)foriinrange(self.vnodes):hself._hash(f{node}#{i})# 虚拟节点一个物理节点造K个分身self.ring[h]node self.sorted_hashessorted(self.ring)defremove_node(self,node:str)-None:ifnodenotinself.nodes:returnself.nodes.discard(node)forhin[kfork,vinself.ring.items()ifvnode]:delself.ring[h]self.sorted_hashessorted(self.ring)defget_node(self,key:str)-str:key 顺时针遇到的第一个节点ifnotself.sorted_hashes:returnNonehself._hash(key)idxbisect_left(self.sorted_hashes,h)# 第一个 h的位置ifidxlen(self.sorted_hashes):idx0# 越过环尾 → 回绕到环首returnself.ring[self.sorted_hashes[idx]]Java 版importjava.nio.charset.StandardCharsets;importjava.security.MessageDigest;importjava.util.*;publicclassConsistentHash{privatefinalTreeMapLong,StringringnewTreeMap();privatefinalSetStringnodesnewHashSet();privatefinalintvirtualNodes;publicConsistentHash(ListStringnodes,intvirtualNodes){this.virtualNodesvirtualNodes;for(Stringn:nodes)addNode(n);}privatelonghash(Strings){try{MessageDigestmdMessageDigest.getInstance(MD5);byte[]dmd.digest(s.getBytes(StandardCharsets.UTF_8));return((long)(d[0]0xFF)24)|((long)(d[1]0xFF)16)|((long)(d[2]0xFF)8)|((long)(d[3]0xFF));}catch(Exceptione){thrownewRuntimeException(e);}}publicsynchronizedvoidaddNode(Stringnode){if(!nodes.add(node))return;for(inti0;ivirtualNodes;i){ring.put(hash(node#i),node);}}publicsynchronizedvoidremoveNode(Stringnode){if(!nodes.remove(node))return;for(inti0;ivirtualNodes;i){ring.remove(hash(node#i));}}publicStringgetNode(Stringkey){if(ring.isEmpty())returnnull;longhhash(key);Map.EntryLong,Stringentryring.ceilingEntry(h);// h的最小键if(entrynull)entryring.firstEntry();// 回绕到环首returnentry.getValue();}}⚠️防坑提醒必看虚拟节点的 key 必须带不同后缀node#0…node#K-1否则全重叠成一个点。Java用long存哈希值——用int负数会打乱环顺序回绕逻辑直接失效。ceilingEntry返回 null 就取firstEntry()——这一步就是“环”的具象化。哈希函数选MD5/SHA取前若干位别用String.hashCode()分布质量差。⏱️ 复杂度分析面试必问操作时间空间get_nodeO(log(KN)) ≈ O(logN)—add_node/remove_nodeO(K·log(KN))—总空间—O(K·N)N1000、K200时20万个条目几MB内存放在每个客户端本地毫无压力。核心收益节点数从N变到N±1 时迁移比例约1/(N1)远优于取模的N/(N1)。 方案对比一致性哈希 vs 其他方案节点变化迁移量中心路由典型使用者hash % N≈ N/(N1)否早期/小规模一致性哈希 虚拟节点≈ 1/(N1)否Memcached、Dynamo、CassandraRedis Cluster 哈希槽精确可控轻量Redis ClusterRendezvous Hashing≈ 1/(N1)否GitHub GLB、Envoy 面试追问模拟提前准备惊艳全场Q1传统取模为什么不行hash(key) % N的分母N直接参与映射计算N一变几乎所有key全变3→4时迁移率75%实测74.86%。直接后果是缓存大面积失效请求穿透到数据库形成缓存雪崩。它也不满足单调性——想只挪 1% 流量都做不到。Q2虚拟节点解决了什么问题解决数据倾斜。节点少时位置随机可能扎堆实测 3 个节点全挤在一个窄区间导致NodeA独占大弧、承接97%的key。虚拟节点让每个物理节点在环上有K个散布的段大数定律生效后负载趋于均匀偏离度从±24pp降到±1.7pp。副作用是天然支持加权分配。Q3如何高效找后继环上的点有序这是标准的“找 ≥ h 的最小值”问题二分JavaTreeMap.ceilingEntryPythonbisect_leftCstd::map::lower_bound。返回空/越界时记得回绕到环首——忘了这一步环就退化成数轴。Q4Redis Cluster用的是一致性哈希吗不是它用哈希槽。固定16384个槽路由是CRC16(key) % 16384集群元数据维护“哪个槽归哪个主节点”。扩容时手动migrate槽迁移量精确可控。Redis追求的是可控性运维能精确指定搬哪些槽还能用ASK/MOVED做平滑过渡。Q5一致性哈希还有什么工程补丁①有界负载Google 2017 SOSP目标节点负载超平均(1ε)倍就跳过②虚拟节点按机器规格加权③故障转移虚拟节点按机架/可用区分组避免同机架同时宕机。 实战小技巧刷题党必备口诀节点key上同环顺时针找第一个虚拟节点治倾斜二分查找O(logN)。模板哈希环 TreeMap/sorted ceiling/lower_bound 回绕。防坑虚拟节点带后缀哈希值用long回绕别忘。 实际应用场景不止是刷题Memcached 客户端路由libketama经典实现Amazon Dynamo / Cassandra / Riak分区Nginx/Envoy 负载均衡hash $request_uri consistentCDN 边缘节点调度就近路由RPC 服务治理连接池选址分库分表路由规则 今日思考题K每台机器的虚拟节点数取多少合适提示工程常用100~300再往上收益递减。如果集群里有一台机器性能是别的两倍你会怎么改代码让它多扛一倍流量提示加权虚拟节点——给它分配2K个虚拟节点。