前言

在解决分布式系统中负载均衡问题的时候，我们可以使用Hash算法让固定的一部分请求落到同一台服务器上，这样每台服务器固定处理一部分请求（并维护这些请求的信息），进而起到负载均衡的作用。

但是普通的hash取模算法伸缩性很差，当新增或者下线服务器机器时候，用户id与服务器的映射关系会大量失效。这在分布式缓存系统中，是非常严重的问题。

例如我们原先有10台服务器，故而hash取模我们一般会这么算：hash(key)%10，从而得到一个在0-9之间的余数，确定请求由哪个服务器处理。

此时如果我们上线新服务器，或下线旧服务器，都会使服务器数量发生改变，这时候不论是hash(key)%11还是hash(key)%9，都会使近乎所有的key的hash取模结果和原先不一样，进而引发问题。比如缓存场景中的负载均衡，如果遇到这种情况，会使短时间内近乎所有的key失效，进而引发缓存雪崩。

为了解决这个问题，使得分布式系统可以自由且无顾虑的增减服务器，我们引入了一致性hash算法，利用hash环对其原本的hash取模算法进行了改进。

1 一致性hash算法

一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题。

一致性hash算法主要用于解决cache miss问题

一致性哈希算法是在哈希算法基础上提出的，在动态变化的分布式环境中，哈希算法应该满足的几个条件：

平衡性
- 是指hash的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
单调性
- 是指在新增或者删减节点时，不影响系统正常运行。
分散性
- 是指数据应该分散地存放在分布式集群中的各个节点(节点自己可以有备份)，不必每个节点都存储所有的数据。

1.1 算法概述

为了能直观的理解一致性hash原理，这里结合一个简单的例子来讲解，假设有4台服务器，地址为ip1,ip2,ip3,ip4。

一致性hash是首先计算四个ip地址对应的hash值
hash(ip1),hash(ip2),hash(ip3),hash(ip3)，计算出来的hash值是0~最大正整数（2^32）之间的一个值，这四个值在一致性hash环上呈现如下图：

hash环上顺时针从整数0开始，一直到最大正整数，我们根据四个ip计算的hash值肯定会落到这个hash环上的某一个点，至此我们把服务器的四个ip映射到了一致性hash环。

当用户在客户端进行请求时候，首先根据hash(userId)计算路由规则，然后看hash值落到了hash环的那个地方，根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip。

如上图可知，user1和user2由ip2的服务器处理，user3由ip3服务器处理，以此类推

0~2^32的区间导致了hash值数量远超过服务器数量，使得hash碰撞的概率降到了极低。

1.2 上线服务器

当新增一个ip5的服务器后，一致性hash环大致如下图：

根据顺时针规则可知之前user5的请求应该被ip5服务器处理，现在被新增的ip5服务器处理，其他用户的请求处理服务器不变，也就是说，新增服务器顺时针方向最近的服务器的一部分请求会被新增的服务器所替代。

1.3 下线服务器

当ip2的服务器挂了的时候，一致性hash环大致如下图：

根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理，而其它用户的请求对应的处理服务器不变，也就是只有之前被ip2处理的一部分用户的映射关系被破坏了，并且其负责处理的请求被顺时针下一个节点委托处理。

2 一致性hash倾斜问题

一致性hash可以做到每个服务器都进行处理请求，但是不能保证每个服务器处理的请求的数量大致相同，如下图：

服务器ip1,ip2,ip3经过hash后落到了一致性hash环上，从图中hash值分布可知ip1会负责处理大概80%的请求，而ip2和ip3则只会负责处理大概20%的请求，虽然三个机器都在处理请求，但是明显每个机器的负载不均衡，这样称为一致性hash的倾斜，我们可以使用设置虚拟节点的方式解决这个问题。

2.1 设置虚拟节点

当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题，一个解决方法是多加机器，但是加机器是有成本的，那么就加虚拟节点，比如上面三个机器，每个机器引入1个虚拟节点后的一致性hash环的图如下：

其中ip1-1是ip1的虚拟节点，ip2-1是ip2的虚拟节点，ip3-1是ip3的虚拟节点。命中ip3-1的请求，则会被导向到ip3服务器。

可知当物理机器数目为M，虚拟节点为N的时候，实际hash环上节点个数为M*N。比如当客户端计算的hash值处于ip2和ip3或者处于ip2-1和ip3-1之间时候使用ip3服务器进行处理。

当然，我们很难得到一个完美均衡的一致性hash环，但理论上虚拟节点数量的增加，和一致性hash环的均衡性呈正相关。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

3 一致性hash的优点

可扩展性。
- 一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销
更好地适应数据的快速增长。
- 采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。
- 虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多