https://github.com/xiazemin/balance/tree/master/balance/balance

ip hash 虽然能保证正常情况下同一个客户端ip的请求落在同一台机器上的问题,session等数据可以存在服务端本地,但是服务端增减机器的时候会出现大面积失效

所以需求一致性hash

一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某空间哈希函数H的值空间是0-2^32-1（即哈希值是一个32位无符号整形），
根据一致性哈希算法，数据A就被绑定到了server01上，D被绑定到了server02上，B、C在server03上，是按照顺时针找最近服务节点方法

这样得到的哈希环调度方法，有很高的容错性和可扩展性：

当一个服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什么问题, 但是当服务器数目发送增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成服务的不稳定. 为了解决类问题,一致性hash算法应运而生.

一致性hash算法特点
在分布式缓存中, 一个好的hash算法应该要满足以下几个条件:

均衡性(Balance)
均衡性主要指,通过算法分配, 集群中各节点应该要尽可能均衡.

单调性(Monotonicity)
单调性主要指当集群发生变化时, 已经分配到老节点的key, 尽可能的任然分配到之前节点,以防止大量数据迁移, 这里一般的hash取模就很难满足这点,而一致性hash算法能够将发生迁移的key数量控制在较低的水平.

分散性(Spread)
分散性主要针对同一个key, 当在不同客户端操作时,可能存在客户端获取到的缓存集群的数量不一致,从而导致将key映射到不同节点的问题,这会引发数据的不一致性.好的hash算法应该要尽可能避免分散性.

负载(Load)
负载主要是针对一个缓存而言, 同一缓存有可能会被用户映射到不同的key上,从而导致该缓存的状态不一致.

从原理来看,一致性hash算法针对以上问题均有一个合理的解决.

一致性hash的核心思想为将key作hash运算, 并按一定规律取整得出0-2^32-1之间的值, 环的大小为2^32，key计算出来的整数值则为key在hash环上的位置，如何将一个key，映射到一个节点， 这里分为两步.
第一步, 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.
第二步, 将缓存的key，用同样的方法计算出hash环上的位置，按顺时针方向，找到第一个大于等于该hash环位置的服务key，从而得到该key需要分配的服务器。

虚拟节点提高均衡性

如上图可看到， 由于节点只有3个，存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多，这样会导致集群中各节点负载不均衡，为解决这个问题，引入虚拟节点， 即一个实节点对应多个虚拟节点。缓存的key作映射时，先找到对应的虚拟节点，再对应到实节点。如下图所示， 每个节点虚拟出两个虚拟节点，从而提高均衡性。

一致性hash算法与其他算法对比
对于集群中缓存类数据key的节点分配问题，有这几种解决方法，简单的hash取模，槽映射，一致性hash。

hash取模
对于hash取模，均衡性没有什么问题，但是如果集群中新增一个节点时，将会有N／（N+1）的数据实效，当N值越大，失效率越高。这显然是不可接受的。

槽映射
redis采用的就是这种算法, 其思想是将key值做一定运算（如crc16， crc32，hash）， 获得一个整数值，再将该值与固定的槽数取模（slots）， 每个节点处理固定的slots。获取key所在的节点时，先要计算出key与槽的对应关系，再通过槽与节点的对应关系找到节点，这里每次新增节点时，只需要迁移一定槽对应的key即可，而不迁移的槽点key值则不会实效，这种方式将失效率降低到了 1／（N+1）。不过这种方式有个缺点就是所有节点都需要知道槽与节点对应关系，如果client端不保存槽与节点的对应关系的话，它需要实现重定向的逻辑。

一致性hash
一致性hash如上文所言，其新增一个节点的失效率仅为1／（N+1），通过一致性hash最大程度的降低了实效率。同时相比于槽映射的方式，不需要引人槽来做中间对应，最大限度的简化了实现。

2.1.1 环形空间
通常的哈希算法都是将value映射到一个32位的key值，也即是0 ~ 2^32-1次方的数值空间：

2.1.2 把对象映射到环形空间
现在假设有4个对象a，b，c，d，通过hash函数计算出的hash值key在环上的分布：
hash(a) = keya
hash(b) = keyb
hash(c) = keyc
hash(d) = keyd

2.1.3 把Cache映射到环形空间
一致性哈希的基本思想就是将对象和Cache都映射到同一个Hash空间中，并且使用相同的Hash算法。假设当前有A，B，C三台Cache，那么其映射结果将如下图所示，他们在Hash空间中，以对应的哈希值排列：
hash(A) = keyA
hash(B) = keyB
hash(C) = keyC

一般情况下，我们使用Cache 服务器的IP地址或机器名作为Hash函数的输入。

2.1.4 把对象映射到Cache
现在Cache和对象都已经通过同一个Hash算法映射到了Hash数值空间中，接下来要考虑的就是如何将对象映射到Cache上。

在这个环形空间中，如果沿着顺时针方向从对象的Key值出发，直到遇见一个Cache，那么就将该对象存储在这个Cache上，因为对象和Cache的哈希值是固定的，因此这个Cache必然是唯一和确定的。

根据上面的方法，对象a和d将被映射到Cache C上，对象b将被映射到Cache A上，对象C将被映射到Cache B上

2.1.5 添加或移除Cache
通过Hash求余的方法所带来的最大的问题就在于不能满足单调性，当Cache有所变动时，缓存会失效，进而对后台服务器造成巨大的冲击，接下来分析一下一致性哈希算法如何处理这个问题。

现在假设Cache B被移除了，根据上面的映射方法，这时受影响的仅是那些沿Cache B逆时针遍历到下一个Cache(Cache C)之间的对象，因此这里仅需要移动对象c，将其重新映射到Cache A上即可

假设再考虑添加一台Cache D的情况，假设在这个环形空间中，Cache D被映射到了对象a和d之间，这时受影响的将仅是那些沿着Cache D逆时针遍历到下一个Cache(Cache A)之间的对象，将这些对象移动到Cache D上即可

通过添加或移除Cache的分析，一致性哈希算法在保持了单调性的同时，还将数据的迁移量达到了最小，这样的算法对于分布式集群来说时非常合适的，避免了大量的数据迁移，减轻了服务器的压力。
2.2 平衡性
平衡性是指哈希的结果能够尽可能分散到所有的Cache中去，这样可以使得所有的缓存空间都能得到充分的利用。

哈希算法并不能保证100%的平衡性，如果Cache较少的话，对象并不能被均匀得映射到Cache上，比如在上面的例子中，仅部署Cache A和Cache B的情况下，在4个对象中，Cache A仅存储了对象b，而Cache B则存储了对象a，d，c，分布很不均匀。为了解决这个问题，一致性哈希算法引入了虚拟节点的概念，定义如下：

虚拟节点是实际节点在Hash空间中的复制品(replica)，实际节点对应了若干个虚拟节点，每个实际节点对应的虚拟节点个数称为复制个数，虚拟节点在Hash空间中以Hash值排列

仍以仅部署A和B的情况为例，现在我们引入虚拟节点，并设置复制个数为2，这就意味着一共会存在4个虚拟节点，Cache A1和Cache A2代表了Cache A，Cache B1和Cache B2代表了Cache B，假设一种比较理想的情况

此时映射关系变为：a –> Cache A2；b –> Cache B2；c –> Cache A1；d –> Cache B1，因此对象a和c都被映射到了A上，而b和d都被映射到了B上，平衡性有了很大提高。

引入虚拟节点后，映射关系就从对象 -> 节点变成了对象->虚拟节点，虚拟节点的Hash计算可以采用IP地址加数字后缀的方式。