开头
今天在学习负载均衡的时候有学到了哈希路由的方式用于将用户机与后端集群中的服务机进行关联，使得同一台用户机的多次请求都落在同一台服务机上。
所有今天我们就来聊一聊哈希路由。
概念
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
上文是摘抄百度百科对哈希的解释，下面咱们就用一个场景来试着解释说明一下。
现在我们有编号从一开始递增的小球（任意长度的输入），和编号一到三的三个容量无穷大的桶（固定长度的输出），先我们需要将小球放置到桶中但要求每个桶中的小球数目尽可能的平均。
在上述的场景中首先可以想到的就是按照桶的编号依次放入编号递增的小球，当三个桶都放了一遍小球后，又从编号为一的桶重新开始存放，即这样就是 1号小球放置在1号桶中，2号小球放置在2号桶中，3号小球放置在3号桶中，….. 5号小球放置在2号桶中，6号小球放置在3号桶中，7号小球放置在1号桶中。
即转化成数学语言就是 应放置的桶编号 = 小球编号 mod 5，这样小球就和桶之间建立了一种映射。
实际上在实际操作中，为了确保任意的输入在散列集中都能找到相应的映射关系，又因为散列值的数量通常是固定的，所有取模在哈希算法中常常被应用。
作用
在实际的负载均衡中，会设立若干台服务机来接收处理未知数量用户的请求，在处于应用最前端的负载均衡器就常常会有这样的要求：将请求尽可能平均的分发到服务机上，同一个用户发起的请求都会转发到相同的服务机上处理。
在接收到请求时，可以获取到请求的用户主机信息（如IP）然后通过主机信息和服务机进行哈希，两者建立映射关系，之后就可以将该请求转发至映射的服务机中处理，后续相同的用户发起的请求其请求中的主机信息也相同，就会映射到相同的服务机中，从而实现 同一个用户发起的请求都会转发到相同的服务机上处理，即哈希路由。
取模方式的缺陷
在上述负载均衡的场景中，在使用哈希路由方式进行转发请求，选择哪台服务机为用户请求提供服务时是通过 计算主机信息 mod 服务机数量 等到提供服务的机器编号，那用户请求就会转发到改服务机上。
但是当动态的添加一台服务器来缓解大量请求压力时，或者由于后台服务器崩溃了一台需要将请求分到其他服务器上提供服务即减少了一台服务器。由于服务器的数目发生了变化 即取模的分母发生了变化，那么在分子不变的情况下，那么计算得到的服务器编号绝大多数也会发生变化。
比如： 10 mod 3 = 1 在最开始的时候，10号用户将会访问 1号服务器，
那么在增加一台服务器之后: 10 mod 4 = 2，10号用户将会访问 2号服务器，同样这一去计算其他数值 绝大部分都会变化。这样就无法满足 同一个用户发起的请求都会转发到相同的服务机上处理 的需求。
一致性哈希
那么有没有可以改进地方呢？通过查看正确答案之后，发现可以通过一致性哈希算法可以解决上述问题。下面就讲讲一致性哈希算法是如何解决上述问题的。（通过正确答案返回来推到过程 (～￣▽￣)～）
既然是因为在取模时分母变化而导致的结果发生变化，那么尝试将分母固定成一个数值不就可以了么。但是在将分母固定了之后取模的结果又将怎么和散列值相关联了，毕竟之前是因为使用散列值数量取模，得出的结果范围与散列值数量刚好一致，所以可以通过编号一一对应。
既然之前是结果范围与散列值数量刚好一致，所以可以一对一，那么是不是可以将结果范围的与散列值形成多对一呢。
那么问题又来了应该怎么规定一个散列值应该占用那一部分的结果范围。
可以通过每个散列值也在固定分母上去取模，这样散列值也会在结果范围类有一个数值的映射，之后输入数据在取模之后得到的结果值，然后通过寻找第一个大于该值的散列值的结果映射，这样就将输入数据与散列值建立了映射关系。
PS: 需要取模的分母 大于 散列值数量。
哈希环
当需要增加一台服务器时，新的服务器也会在结果集存在一个映射 如下图：
影响的范围为红色一段，这样新增加的服务器仅仅只是帮助分摊了其中一台服务器的请求，其他的服务器没有影响所以也没有缓解其他服务器的压力。
我们可以通过为节点建立虚拟节点，让一个真实节点映射到多个位置上。
如图，新增的 Node3 节点就分别为 V01, V12, V22的虚拟节点分摊了请求，即为 Nod0,Node1,Node2 都分摊了请求。
