上个月去面字节后端二面面试官开门见山地问你来说说一致性哈希的虚拟节点和数据迁移。我心里一喜这题背过啊环形空间、顺时针寻址、虚拟节点防倾斜一套话术行云流水。结果他紧接着补了一句那你们线上加节点的时候数据迁移具体怎么做的我当场愣住了。说真的八股文里从来没人告诉我虚拟节点到底该建多少个加一台机器到底要把哪些数据搬到哪迁移过程中怎么保证读不到空数据。回来后我把这道题彻底捋了一遍从原理、代码到线上迁移方案全部重新实现了一次。这篇就是把整个过程复盘出来适合正在准备Java后端面试的同学也适合那些系统里已经用了一致性哈希、但还没真正动手做过扩容的人。1. 一致性哈希算法为什么取模哈希会被淘汰1.1 传统取模哈希的尴尬处境先说最基础的场景。假设你有4台缓存服务器编号从0到3路由规则很简单对key的hash值取模hash(key) % 4决定请求落在哪台机器上。这套方案在节点固定的情况下没有任何问题但凡你要扩容或者缩容麻烦立刻就来了。举个例子key的hash值分别是10和11在4台机器时代10 % 4 211 % 4 3两台机器分别处理。现在业务流量涨了你想把4台扩成5台路由规则被迫变成hash(key) % 5。你再看这两个key10 % 5 011 % 5 1。也就是说扩容之后原来在机器2上的key要跑到机器0上去原来在机器3上的key要跑到机器1上去。这不是个别现象是几乎所有key都要重新映射一遍。你可以算一笔账原来有N个节点对任意一个key它在新规则下的落点完全变了。从数学上讲一次节点数变化会导致大约(N1)/N比例的key发生迁移。比如4台扩容到5台约80%的key的所属节点发生变化。这带来的直接后果是这些key在旧节点上存储的缓存数据全部失效新节点上又没有数据数据库在瞬间被打满整个链路雪崩。这就是经典的“缓存风暴”。所以取模哈希的核心缺陷就两条第一节点增删时影响范围是全局性的第二数据分布完全依赖节点数量这个分母节点一变分母一变一切重来。线上系统最怕的就是这种“牵一发动全身”的方案所以我们需要一个增删节点只影响局部区域的路由算法。1.2 环形空间与顺时针寻址一致性哈希的思路非常巧妙它改变了“哈希值对节点数量取模”这个思路变成“套在环上的位置匹配”。具体做法分三步先把整个哈希空间组织成一个首尾相接的环通常用0到2^32-1相当于一个非常大的刻度盘然后把每台节点的标识比如IP地址或机器名也进行哈希得到环上的一个位置最后把数据的key哈希后在环上从当前位置出发顺时针找到第一个节点这个节点就是数据归属。你可以把它想象成一个大转盘盘子上有一圈刻度节点是插在刻度上的钉子每个key的哈希值指向盘子上某一个刻度这个刻度顺时针遇到的第一个钉子就是负责这台数据的节点。没有钉子的地方数据就继续绕圈直到遇到钉子。这个机制最核心的地方在于节点不是通过“数量”参与路由而是通过“位置”参与的。原来不管多少节点它们的哈希值都落在这同一个环上数据找节点是一场“物理上的临近匹配”而不是“数学上的除法余数”。这也是它能做到局部影响的关键。1.3 为什么节点增删只影响局部用具体数字来说话。假设环上有4个节点哈希值分别为A100B200C300D400它们把环大致切成了四段。数据key落在哪个区间就归区间的顺时针起点管。现在要加一个新节点E它的哈希值为250。那会发生什么只有C300到E250之间这一段的数据会受影响这段区域原来顺时针遇到的是C现在E加入了数据会被E截胡。其他所有区域包括100到200、200到250、250到300、300到400、400绕到100它们的下一个节点没有任何变化数据归属完全不变。同样如果删除节点B200只有A100到B200之间的数据会“顺延”到下一个节点C上其他两个节点的数据完全不动。这就是一致性哈希的核心价值节点数量变化时受影响的数据范围被约束在一个局部区间内而不是像取模那样全盘洗牌。这也就解释了为什么缓存系统、分布式存储、负载均衡器都愿意用一致性哈希。它牺牲了“完全均匀”这个理想状态换来了运维上的“可控性”——你加一台机器只需要迁一个区间的数据其余流量照常这对线上稳定性的意义太重要了。2. 虚拟节点数据倾斜的必修课2.1 没有虚拟节点会有什么后果一致性哈希解决了全局洗牌的问题但它自己也有个明显的毛病节点数太少的时候环上的点分布可能极不均匀。举个例子把哈希空间简化成0到99一共100个刻度。现在有4个节点它们的哈希值分别是10、45、80、90。你看看划分出来的区间有多大节点10到节点45之间占了35个刻度节点90绕回到节点10之间只有20个刻度。这意味着什么如果key随机分布落在10到45之间这段区域的概率是35%这35%的数据全部压到节点45上而节点80只管着10%的数据。四台机器一台扛着三台半的流量另外一台闲得慌这种热点的偏斜程度在真实业务里会直接造成机器被打爆、其他机器CPU吃不满。更麻烦的是节点的哈希值是不可控的。你以为四个节点会均匀散开实际上它们可能在环上扎堆也可能挤成一小段。哈希函数的随机性决定了节点分布本身具有很大的方差。节点数量越少这种分布不均的现象越明显。这也是为什么说“一致性哈希天然不均需要通过技术手段修正”。2.2 虚拟节点怎么解决倾斜虚拟节点的思路并不复杂既然一个点容易分布不均匀那我就给每个物理节点多复制出很多份让每个物理节点在环上拥有多个“影子”这些影子也参与路由并且最终都会映射到同一个物理节点上。具体做法是给每个物理节点生成150个哈希项比如node-0、node-1……一直到node-149分别哈希到环上。这样每个物理节点在环上不是孤零零的一个点而是散布在环上的150个点整个环被塞得密密麻麻的。当key在环上做顺时针查找时它遇到的最近的那个虚拟节点再对应回物理节点即可。这样做的效果非常好理解当虚拟节点大量覆盖环时任何一段区域内的虚拟节点数量都趋近于相同数据不管落在哪里都能近似均匀地分配到各个物理节点。而且如果某个物理节点挂了它的150个虚拟节点从环上消失这150个点之间的数据会被相邻的虚拟节点接管由于虚拟节点分布在整个环上所以对物理节点的影响也被“摊薄”了不会出现一个节点扛下一大片区域的极端情况。虚拟节点相当于用“数量换均匀”用“多副本换平滑”。真实场景中7台物理节点各自配上200个虚拟节点整体分布的离散系数可以从原来的0.3以上降到0.05以内效果非常明显。2.3 虚拟节点数量给多少合适面试官大概率会追问虚拟节点数量应该选多少你如果说“越多越好”那就掉坑里了。虚拟节点数量要平衡三个因素内存占用、建环成本、均匀度收益。从内存占用看如果用Java的TreeMap来实现环每个虚拟节点就是TreeMap里的一个Entry节点总数N乘以副本数M就是Entry的数量。100台物理节点、每台150个副本就是15000个Entry每个Entry至少有一个Integer和一个对象引用内存大约几百KB这个量级可以忽略。但如果是300个副本、1000台机器30万个Entry建环时的插入操作就是30万次虽然TreeMap的插入是O(logN)总耗时也就毫秒到几十毫秒级别但每次节点启动都要跑一遍能省则省。从均匀度收益看研究结论是副本数从1增加到150均匀度提升非常明显副本数超过150后继续增加均匀度提升的幅度就很小了边际收益递减。所以业界经验值一般是150到200个副本。节点总数少的时候取上限节点总数多的时候取下限。比如只有3台物理节点副本数可以给300让它把环填得更满有50台物理节点副本数给100就足够了。还有一个点是你自己实现时要注意的虚拟节点数量一定要在节点增减时保持一致。如果A节点180个副本、B节点120个副本那环上的位置份额就不对等数据分布会故意倾斜向副本多的节点。生产环境通常用统一的副本数量配置保证公平。3. 数据迁移扩容缩容的真正难点3.1 扩容新节点要接管哪些数据面试官问数据迁移的时候你要能说清楚一个加节点的完整动作。假设当前环上有A100、B200、C300、D400四个节点新上线了一台E哈希值为250。那E到底接管哪些数据答案非常明确E会接管从它的前驱节点到它自己之间的那段环。前驱是C300还是B200因为E是250顺时针往前找前驱节点是C300所以E接管C的前半段区域也就是落在(300, 250]这段的key统一从C迁移到E。老节点A、B、D的数据完全不动。如果你不想靠手算可以写代码算用TreeMap的lowerEntry(newHash)找到前驱ceilingEntry(newHash)找到后继迁移区间就是前驱到新节点之间。实际工程中你不需要遍历所有key来判断它是否属于迁移区间而是要结合存储系统的特性来做范围扫描。Redis Cluster的做法是把16384个hash slot分配好迁移时直接把slot从源节点搬到目标节点slot内的所有key一次性迁移自研的缓存系统则需要自己实现一个按前缀或者按时间分批扫描的任务把属于迁移区间的key读出来写入新节点。我补充一句扩容不是“加一行配置”就完事的数据不过来流量千万不能切。正确的顺序是先启动新节点让它从源节点同步数据数据完全到位并经过校验后再更新路由表。这个顺序反了用户请求就会落在空节点上缓存穿透全线打满数据库。3.2 缩容节点的数据到哪里去缩容场景要区分两种主动下线和故障宕机。主动下线流程很清晰节点B200要退役路由到B的数据是前驱A100到B200之间的key它们顺时针会遇到的下一个节点是C300所以这些key全部迁到C。迁移完成后再把B从环上摘除整个集群的容量降一档。故障宕机会麻烦得多。如果B直接宕机而B上没有任何副本那B负责的这100个刻度区间内的数据可能会永久丢失。一致性哈希这个路由算法本身不负责数据持久化它只负责路由数据安全是存储层或副本策略的事情。所以在实际架构中每个物理节点都会在另一台节点上存副本或者主从复制当B宕机后C作为顺时针的下一跳会承接这些数据的读取压力而数据可以从B的从节点或C的副本版本中恢复。这里有个很容易踩的坑有人以为“节点少了一台数据会自动出现在下一台节点上”于是不做任何处理直接摘节点。真相是一致性哈希只解决了“下一跳在哪里”并没有魔法般地把旧数据复制过去。你必须明确地做一次数据搬迁把源节点上属于被接管区间的key搬到新归属节点读请求才能打到数据。3.3 数据迁移的完整操作流程我整理过一套在真实缓存系统里落地过的迁移流程分为五步每一步都不能省。第一步确认迁移区间和迁移方向。新节点上线前用路由算法算出接管的前驱、后继生成一张“源节点-目标节点”的映射表。如果是加E250源节点是C目标节点是E如果是删B200源节点是B目标节点是C。第二步启动全量迁移。写一个扫描任务在源节点上读取属于迁移区间内的所有key分批写入目标节点。这里要注意batch size建议每批100到500个key避免一次性读取太多导致源节点内存和带宽被打满。迁移任务要支持断点续传至少记录下已经扫描到哪个边界hash值宕机后能接着跑。第三步增量同步。全量迁移期间源节点依然在接受新写入。所以光做全量搬运是不够的需要同时开启增量同步。对Redis可以用replicaof临时建立主从关系让新节点作为从节点实时追源节点的新写对自研系统一般用消息队列把写操作同步一份到新节点。第四步一致性校验。迁移完成的标志不是“key都搬运完了”而是“源和目标完全一致”。可以抽样统计两边key数量再对比部分key的value哈希值确保没有遗漏。线上常见的做法是先比数量再按10%的key抽样做CRC校验偏差超过阈值就回滚重跑。第五步切换路由并清尾。校验通过后更新客户端的路由配置或者代理层的虚拟节点表让新节点正式对外服务。切换后不要立刻删源节点数据保留一个观察期比如24到72小时确认没有回退需求再清理。3.4 迁移中的一致性保障迁移期间最怕的就是读到空数据或者不一致的数据。这个问题要在设计上就规避掉。缓存场景下一致性哈希迁移通常配合“失效重拉”策略迁移前把属于迁移区间的key在源节点上标记为“迁移中”查询请求来了打到源节点发现标记就转发到目标节点或者更简单直接让源节点把这些key删除客户端下次读取时发现缓存未命中重新写一份到新节点——这就是缓存预热的概念。如果是数据库分库分表场景要求就没那么宽松了。迁移期间最好采用双写方案应用写入时同时写老库和新库读请求仍然走老库等数据追平后再切换读流量。这个过程可以用专业的迁移工具来执行比如数据同步组件会监控binlog并实时应用到新库全量加增量最后切换全程对业务几乎无感。这里给一个我的个人经验千万不要默认“迁移工具会自动处理一切”。不管用什么工具最后那一下校验永远要人工再看一眼至少对比一下总量和几个关键唯一键。迁移失败不可怕可怕的是你觉得自己迁移成功结果用户数据丢了那才是事故。场景受影响区间数据去向其他节点新增节点E250(C300, E250]C 迁往 E不受影响删除节点B200(A100, B200]B 迁往 C不受影响新增节点E350(D400, E350]D 迁往 E不受影响4. 从八股到代码一致性哈希的Java落地4.1 面试官连珠炮这些追问才是重点只背概念不够面试官一定会往实现细节上挖。我遇到过至少这几个追问每个都值得提前准备第一个追问是“你用什么哈希函数为什么不用Java的hashCode()”。标准回答是String.hashCode()是31进制多项式计算分布质量在分布式场景下不够好而且某些版本存在碰撞率偏高的问题。业界常用的是FNV1_32_HASH、MD5结合位移或者Ketama算法。FNV哈希快而且散列均匀适合路由场景。第二个追问是“为什么用TreeMap作为环的数据结构”。答案是TreeMap支持有序键值访问它能天然地实现“顺时针寻找下一个节点”通过tailMap(hash)拿到大于等于某hash值的所有节点取第一个就是后继如果tailMap为空说明绕了一圈取firstKey回到环头。用数组或链表实现要么查找是O(N)要么维护成本高。TreeMap的查找复杂度是O(logN)3000个虚拟节点量级下单次路由耗时可以控制在微秒级别完全够用。第三个追问是“虚拟节点为什么选150有推导公式吗”。这就考你有没有真的算过。虚拟节点越多均匀度越好但内存和建环时间也越高。150到200是工程经验的甜点值过了200收益衰减。如果你能用Cube-Ring算法的公式或者实测数据回答案面试官会眼前一亮。第四个追问是“数据迁移时读请求怎么保证不读到空”。这就是我们在第3章聊过的内容先同步再切流量迁移期间用标记转发或者双写兜底切换后保留观察期回删源节点。4.2 TreeMap实现的一致性哈希核心代码我写了一个可直接运行的Java版本核心功能包括添加节点、删除节点、查询key归属、计算虚拟节点、输出迁移区间。代码不长但每个细节都能对上原理。import java.nio.charset.StandardCharsets; import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHashT { private final int numberOfReplicas; private final TreeMapInteger, T circle new TreeMap(); public ConsistentHash(int numberOfReplicas, CollectionT nodes) { this.numberOfReplicas numberOfReplicas; for (T node : nodes) { addNode(node); } } public void addNode(T node) { for (int i 0; i numberOfReplicas; i) { String virtualName node.toString() # i; circle.put(hash(virtualName), node); } } public void removeNode(T node) { for (int i 0; i numberOfReplicas; i) { String virtualName node.toString() # i; circle.remove(hash(virtualName)); } } public T get(String key) { if (circle.isEmpty()) { return null; } int hash hash(key); SortedMapInteger, T tailMap circle.tailMap(hash); Integer targetHash tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); return circle.get(targetHash); } public SortedMapInteger, T getTailMap(int fromHash) { return circle.tailMap(fromHash); } private int hash(String key) { // FNV1_32_HASH比 String.hashCode 分布更均匀 final int p 16777619; int hash (int) 2166136261L; for (int i 0; i key.length(); i) { hash (hash ^ key.charAt(i)) * p; } hash hash 13; hash ^ hash 7; hash hash 3; hash ^ hash 17; hash hash 5; return hash 0 ? -hash : hash; } public static void main(String[] args) { ConsistentHashString ch new ConsistentHash(200, List.of(192.168.0.1:6379, 192.168.0.2:6379)); System.out.println(ch.get(user:10001)); ch.addNode(192.168.0.3:6379); System.out.println(ch.get(user:10001)); ch.removeNode(192.168.0.2:6379); System.out.println(ch.get(user:10001)); } }这段代码有几个细节值得说hash(key)我用了FNV1_32_HASH而不是String.hashCode()就是前面提到的分布均匀性问题。FNV散列的碰撞概率在字符串场景下明显更低而且它的计算过程只涉及位运算和乘法性能非常好。tailMap(hash)是TreeMap提供的有序视图配合firstKey()取最小key正好模拟了“从当前刻度顺时针出发找到第一个节点”。如果tailMap为空就用firstKey()绕回环的起点这是环形空间的关键一步漏了这个回绕逻辑代码就是错的。每个节点生成的200个虚拟节点拼接方式是node.toString() # i这样保证每个虚拟节点的哈希值都不依赖顺序而且节点名固定时虚拟节点集合是确定的方便排查问题。4.3 其他实现方案与虚拟节点/slot的区别面试时如果能对比不同实现方案会显得你视野更宽。我先快速说一下常见的几种最简单的是自实现TreeMap环适合中小规模集群扩展性取决于你的代码水平我在上面已经给出了可以直接用的版本。Google Guava提供了Hashing.consistentHash()方法但它的适用场景是“节点数量基本固定”的负载均衡比如把流量平均分到几个固定的worker上不支持动态增删整个环所以工程上用它做一致性哈希环比较少。Redis Cluster用的是另一种思路提前划分16384个slot每个节点负责一段slot区间迁移的最小单位是slot而不是key。这里的slot本质上就是预分配的固定哈希空间段和虚拟节点的思想有相似之处但更偏“管理单元”不是随机分布的副本点。Redis Cluster的迁移命令是MIGRATE配合源节点、目标节点和slot范围执行批量key搬运。Memcached客户端常用的Ketama算法是虚拟节点方案的代表作。它用MD5生成虚拟节点哈希每个真实节点生成160个副本均匀撒到环上再通过tree.hh或者SortedMap维护路由。Ketama将虚拟节点数量固定在160是经过大量测试验证的经验值和我们在2.3说的150到200区间是一致的。方案数据结构节点增删方式适用场景TreeMap自实现TreeMapaddNode/removeNode中小集群、自定义业务Guava consistentHash固定桶不支持动态增减固定worker负载均衡Redis Clusterslot按slot迁移Redis集群、大规模缓存KetamaTreeMap虚拟节点增删Memcached客户端路由4.4 代码级细节路由时的回绕与边界写一致性哈希实现的时候有几个边界问题非常容易出错我每个都踩过单独拿出来讲。第一个是回绕问题。环形空间里hash值最大的点和hash值最小的点是相邻的。如果key的hash值是4000而环上最大的节点hash只有3900那tailMap(4000)是空的必须取firstKey()回到环的起点。这个回绕逻辑我最初没写导致有一部分key永远找不到节点直接NPE。第二个是边界区间的开闭。迁移区间到底是(前驱, 新节点]还是[前驱, 新节点)这个细节要统一。key的hash和节点的hash恰好相等的情况虽然罕见但一旦发生必须保证路由和迁移的逻辑自洽。建议统一采用左开右闭即区间起点不包含、终点包含并且路由查询时用tailMap(hash)包含等于保证一致。第三个是删节点时的虚拟节点删除完整性。如果removeNode里的虚拟节点名拼接规则和addNode不完全一致比如一个用#一个用-那么旧虚拟节点就会永久残留在环上形成幽灵节点。这个bug排查起来非常费劲因为大多数时候不影响路由只在特定key上偶尔出错。解决办法是写一个单元测试随机生成一批key加节点前后对比路由变化比例是不是符合预期。5. 面试追问与线上实战避坑实录5.1 面试高频问题速查把面试中容易被追问的问题整理成了速查表每个问题给一个核心回答思路你再结合自己的项目经验展开就行。问题核心回答要点加分项一致性哈希解决了什么问题节点增删只影响局部区域避免全局数据失效和缓存雪崩能对比取模哈希的全局洗牌比例虚拟节点怎么解决数据倾斜每个物理节点在环上生成多个哈希副本让分布近似均匀给出副本数量经验值150-200为什么用FNV比hashCode好字符串hashCode分布不均、碰撞率偏高FNV快且均匀贴出FNV的代码或者碰撞测试数据加节点数据迁移怎么做先算迁移区间再全量增量同步校验后切流量讲清迁移期间的防穿透方案一致性哈希能用于数据库分库分表吗可以用但要考虑范围查询、数据搬迁复杂度、跨库事务说明缓存场景首选关系型库慎选如果环上节点特别多性能会怎样TreeMap查找O(logN)虚拟节点总数是N*M量级可控给出实际压测数据比如1万个key路由平均耗时5.2 我在线上踩过的坑第一个坑是“加完节点命中率依然上不去”。当时是4台缓存扩到5台我用一致性哈希做了虚拟节点但副本数只配了30个。结果就是环上依然有大段空白区间部分key被均匀分到了新节点但整个key的分布因为副本不够离散度依然很高热点并没有被解决。后来把副本数调到200再观察分布曲线明显平滑了。这个教训就是虚拟节点数量不能拍脑袋给一定要根据你的key数量和节点数做实验用监控里的QPS离散度来判断。第二个坑是“迁移完数据读还是空的”。这是一个很隐蔽的问题我把数据都搬到了新节点也更新了服务端的路由表但客户端每个连接在启动时缓存了旧的hash环连接持有者压根不知道路由变了。所以在做节点扩容时不只是服务端要更新客户端也要能感知变化。我现在的做法是把版本号写进路由配置客户端定期拉取发现版本不一致就重建hash环。这一步不做到位数据搬了也白搬。第三个坑是“缩容时数据丢了一部分”。有次运维直接下线了一台节点想着“一致性哈希会自动把数据迁移到下一节点”结果下一节点的数据量和源节点对不上查了半天发现根因是源节点有大量的冷数据没有在目标节点上而目标节点只同步了热数据或者说是迁移任务的扫描范围漏掉了部分区域。从那以后我在任何节点操作前都会走一遍完整流程先算出影响区间再扫描key再增量同步再校验最后才切流量和下线节点。第四个坑是用String.hashCode()做路由哈希。这个问题在早期版本踩过线上发现某个节点的QPS显著高于其他节点后来排查到是哈希分布不均匀。换成FNV1_32_HASH之后再统计key的分布均匀度好了不少。你可以自己写个测试生成100万个user:10001到user:1010000分别用hashCode()和FNV计算散列值做个桶统计差距一目了然。5.3 排查思路怎么定位环上的倾斜和迁移异常如果线上真的出现了数据倾斜我一般按三步排查。第一步看监控里的节点QPS、内存增长曲线和CPU用量。如果某台节点的QPS明显高于平均且内存增长曲线也比别人陡基本可以判定它在环上占了过大的区域。这时候把它的哈希值打印出来再看看它的前后各有几个节点判断是不是“孤悬在大空档中间”。如果是优先加虚拟节点副本数而不是加物理节点。第二步抽样统计key的哈希分布。写一个小工具从访问日志里随机取几万个key计算它们命中的节点输出各节点的占比。如果和预期比例相差超过10%说明路由本身有问题可能是虚拟节点没生效或者某台节点的哈希值恰好扎堆。第三步做路由回归测试。这个方法在数据迁移后尤其重要用线上真实key的样本分别在迁移前、迁移后的hash环上计算归属节点对比变化比例。理论上一次加节点只应该影响约1/(N1)的key如果实际变化比例远高于这个值比如40%甚至更多那就说明实现有问题多半是虚拟节点没对齐或者环的构建逻辑有bug。说回面试这件事。当我真正把虚拟节点和数据迁移这套东西完整捋了一遍才明白为什么面试官要这么追问——一致性哈希在Java面试题里早已是标配真正拉开差距的就是能不能把理论落到线上。我个人的建议是别等面试才去背备一个私有化小项目自己用代码实现一遍一致性哈希然后模拟一次扩容把迁移流程真的跑一遍比刷二十个面试题都有用。那些在面试中能讲出“迁移怎么做”“校验怎么执行”“踩过什么坑”的候选人往往不是因为他记得更多而是真的在自己的系统里干过。