Java面试题

题目

谈谈你对一致性 hash 的了解。讲讲他的原理和实践。

答案

分布式系统中对象与节点的映射关系，传统方案是使用对象的哈希值，对节点个数取模，再映射到相应的编号的节点，这种方案在节点个数变动时，绝大多数对象的映射关系会失效而需要迁移；而一致性 hash 算法中，当节点个数变动的时候，映射关系失效的对象非常少，迁移成本也非常小。

一致性 Hash 会首先计算出各个节点相应的 hash 值，然后将对应的值放在一个环上面。如下图

因为这边是一个环，所以当有一个节点挂的时候，会按照顺时针方式向后寻找服务节点，或者新增服务节点的时候，也会按照 hash 值插入到环中。然后获取节点的时候如果 hash 值对应的节点存在就调用相应的节点，如果不存在就按顺时针向下寻找。

拓展

这个时候面试官会继续问发生一些问题会怎么解决，比如一致性 hash 的倾斜。上图中有百分之八十的数据会打到节点 node2 上面，这个时候怎么处理？

增加虚拟节点，将每个节点引入一个虚拟节点然后将其 hash 值计算出来添加到环里面。就可以简单的理解为每个 node 有映射两个节点 hash 值。