原来这就是一致性哈希算法
写在最前
本来计划每周末至少一篇文章，上周末因为回了趟老家，不小心闪到腰，做了针灸和拔罐，整个周末都在老家修养！还好在老家好吃好住!又肥了一圈！
不过还是很抱歉没及时更新！
老规矩，先来一段音乐，听着音乐看文章容易消化！
好了，言归正传！
在分布式系统中，消费者是如何路由到下游服务，分布式缓存又如何选择节点。换句话说，如何将数据均匀分散到各个节点上，同时能在加减节点时将受到影响的数据降到最少！嗯，没错，今天讲讲负载均衡算法！
负载均衡，不就是DNS，F5，Nginx这些负载均衡设配或系统吗？这些确实也是负载均衡的一种，将用户请求分发到多个服务器处理，以提高网站、应用或者数据库的性能和可靠性。但我说的是在分布式架构下模块间的负载均衡算法实现，是动态平衡的过程！
1 随机算法
对于n个节点，每次都是随机选择，所以被选中的几率都一样！但随着服务节点压力增大或者硬件设配高低，各服务性能总不一致，随机算法无法动态感知！当然这个可以优化，加权重值。例如abc三个节点服务，a权重为60%，b为10%，c为30%，所以被选中的比值：6:1:3.
2 轮询算法
n个节点组成的循环列表，从第一个开始，依次轮询选择，保证每个都能被选中！跟随机算法一样，服务节点性能不一致，不适用，也可以加权重优化！
3 最小活跃调用算法
这个算法需要主动获取到节点的服务性能。例如a节点一分钟处理10万请求，b节点一分钟处理5万，那接下来更多请求会选择a，即响应快接收更多请求。
接下来讲重点
一致性哈希算法
第一次接触这个算法是五年前看过李智慧的“大型网站技术架构”。这本书可以说是我对分布式集群架构的启蒙书吧！哈
环形哈希空间
按照我们通用的哈希算法，将得到的key hash到一个具有2^32的空间里，即0～2^32-1范围内。将这些数字头尾相连，形成一个闭合的环形。如图：
我们有三个同等机器node1，node2，node3，通过hash算法得到对应key，映射到环中。一般情况下对机器的ip或者mac作为输入值进行hash。
hash(node1)=key1hash(node2)=key2hash(node3)=key3
现在我们有三个对象分别是object1，object2，object3，用个同样的hash算法算出key值，然后散列到环上
hash(oject1)=keyo1hash(object2)=keyo2hash(object3)=keyo3
下图展示object1在环对应位置上
object1对象是根据顺时针方向计算，找到离自己最近的机器节点，所以object1找到node1(key1)的节点。
所以我们发现在这种算法下，只要算出对象hash值就能快速定位找到机器，整体达到负载均衡的效果。
机器删除
节点node3机器故障，并不影响node1和node2节点的数据。
但会导致原来对象应该映射到node3的全部映射到node1，增加node1的压力。若node3是分布式缓存，则需要将node3节点的缓存全部迁移到node1中，这带来系统维护迁移的成本。
机器添加
添加节点node4，只影响部分node1的数据，将部分node1数据映射到node4机器上。这种情况，确实避免大量数据迁移，减少服务器压力！
但我们发现上面原来只有三个节点的图，node1和node3比node2更占用环的长度，毕竟节点hash是随机的，这不算均衡吧，而且上面也说删除节点存在一定服务维护成本，ok，带着疑问我们继续往下。
为了尽可能满足一致性hash算法的平衡性，该算法引入了虚拟节点。
——“虚拟节点”（ virtual node ）是实际节点（机器）在 hash 空间的复制品（ replica ），一实际个节点（机器）对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。
node1节点有三个虚拟节点：node1-1，node1-2，node1-3
node2节点有三个虚拟节点：node2-1，node2-2，node2-3
node3节点有三个虚拟节点：node3-1，node3-2，node3-3
上图可以看出引入每个节点引入三个虚拟节点后，分布就已经达到均衡了。
还是原来顺时针最近节点原则。实际操作如下图：
注：一个节点分三个虚拟节点画不下了，上图就只画两个了
虚拟节点怎么引入
hash("9.10.20.122")引入两个虚拟节点node1-1，node1-2，计算方式是：
hash("9.10.20.122#1-1")hash("9.10.20.122#1-2")
ok，一致性哈希算法就说到这里了！
还要赶早班车回深圳！苦逼的打工人！