一致性 Hash

参考： simplezero  ：一致性hash  

概念

一致性hash算法主要应用在分布式缓存系统中，在增加或者删除服务器节点时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，也就是系统中的大多数历史缓存的存储服务器节点可以不变，解决了普通hash算法带来的动态伸缩性问题。

• 如上图，一致性hash定义了一个 0 ～ 2^32-1 hash环
• hash函数对数据并不是按照服务器节点的数量取模，而是按照 2^32 取模（hashcode % 2^32），这样请求的数据就会落在环上某个固定的位置。
• 服务器节点按照IP或域名进行hash，分配到hash环上，如图分配了4个服务器节点，分别在hash环的 10000、20000、30000、40000 位置（为了方便演示）
• 请求数据先通过hash函数（hashcode % 2^32）确定了在环上的位置，再沿着环顺时针查找，遇到的第一个节点就是命中的服务器节点。

• 新增节点E (25000)，按照一致性hash算法，只有B ～ E 之间的历史数据会受到影响，（之前是路由到C的，现在路由到 E ），即只有C的一部分数据需要迁移到E。
• 删除节点B，那么 A～ B 之间的历史数据丢失，并且新增数据会被插入到 C，其他的节点都不会受到影响。
• 可以看到一致性hash算法，节点的增删都只会影响了系统中的一小部分数据，容错性非常好。

问题

如果每个服务器在环上只有一个节点，那么当服务器宕机，它原本所负责的缓存数据将全部交由顺时针方向的下一个服务器节点处理。例如，当 B 退出时，它原本所负责的缓存将全部交给 C 处理。这就意味着 C 的访问压力会瞬间增大。设想一下，如果 C 因为压力过大而崩溃，那么更大的压力又会向 D 压过去，最终服务压力就像滚雪球一样越滚越大，最终导致缓存雪崩

一致性hash 通过引入虚拟节点解决了这个问题，每个实际节点映射多个虚拟节点，数据按照规则找到虚拟节点后，再储存到映射的实际节点上；因为虚拟节点可以在hash环上均匀分布，这意味着当一个真实节点失效退出后，它原来所承载的压力将会均匀地分散到其他节点上去，解决缓存雪崩问题。