【数据结构与算法】⼀致性Hash算法及Java实践
  追求极致才能突破极限
⼀、案例背景
1.1 系统简介
  ⾸先看⼀下系统架构，⽅便解释：
  页⾯给⽤户展⽰的功能就是，可以查看任何⼀台机器的某些属性（以下简称系统信息）。
  消息流程是，页⾯发起请求查看指定机器的系统信息到后台，后台可以查询到有哪些server在提供服务，根据负载均衡算法（简单的轮询）指定由哪个server进⾏查询，并将消息发送到Kafka，然后所有的server消费Kafka的信息，当发现消费的信息要求⾃⼰进⾏查询时，就连接指定的machine进⾏查询，并将结果返回回去。
  Server是集架构，可能动态增加或减少。
  ⾄于架构为什么这么设计，不是重点，只能说这是符合当时环境的最优架构。
1.2 遇到问题
  遇到的问题就是慢，特别慢，经过初步核实，最耗时的事是server连接machine的时候，基本都要5s左右，这是不能接受的。
1.3 初步优化
  因为耗时最⼤的是server连接machine的时候，所以决定在server端缓存machine的连接，经过测试如果通过使⽤的连接缓存进⾏查询，那么耗时将控制在1秒以内，满⾜了⽤户的要求，不过还有⼀个问题因此产⽣，那就是根据现有负载均衡算法，假如server1已经缓存了到machine1的连接，但是再次查询时，请求就会发送到下⼀个server，如server2，这就导致了两个问题，⼀是，重新建⽴了连接耗时较长，⼆是，两个server同时缓存着到machine1的连接，造成了连接浪费。
1.4 继续优化
  ⼀开始想到最简单的就是将查询的machine进⾏hash计算，并除sever的数量取余，这样保证了查询同⼀个machine时会要求同⼀个server进⾏操作，满⾜了初步的需求。但是因为server端是集，机器有可能动态的增加或减少，假如根据hash计算，指定的 machine会被指定的server连接，如下图：
  然后⼜增加了⼀个server，那么根据当前的hash算法，server和machine的连接就会变成如下：
java技术介绍百度百科  可以发现，四个machine和server的连接关系发⽣变化了，这将导致4次连接的初始化，以及四个连接的浪费，虽然server集变动的⼏率很⼩，但是每变动⼀次将有⼀半的连接作废掉，这还是不能接受的，当时想的最理想的结果是：
当新增机器的时候，原有的连接分⼀部分给新机器，但是除去分出的连接以外保持不变
当减少机器的时候，将减少机器的连接分给剩下的机器，但剩下机器的原有连接不变
  简单来说，就是变动不可避免，但是让变动最⼩化。根据这种思想，就想到了⼀致性hash，觉得这个应该可以满⾜要求。
⼆、使⽤⼀致性Hash解决问题
  ⼀致性Hash的定义或者介绍在第三节，现在写出⼀致性Hash的Java的解决⽅法。只写出⽰例实现代码，⾸先最重要的就是Hash算法的选择，根据现有情况以及已有Hash算法的表现，选择了FNV Hash算法，以下是其实现：
public static int FnvHash(String key) {
final int p = 16777619;
long hash = (int) 2166136261L;
for (int i = 0,n = key.length(); i < n; i++){
hash = (hash ^ key.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return ((int) hash & 0x7FFFFFFF);
}
  然后是对能提供服务的server进⾏预处理：
public static ConcurrentSkipListMap<Integer, String> init(){
//创建排序Map⽅便后⾯的计算
ConcurrentSkipListMap<Integer,String> servers=new ConcurrentSkipListMap<>();
//获得可以提供服务的server
List<String> serverUrls=Arrays.asList("192.168.2.1:8080","192.168.2.2:8080","192.168.2.3:8080");
//将server依次添加到Map中
for(String serverUrl:serverUrls){
servers.put(FnvHash(serverUrl), serverUrl);
//以下三个是当前server的三个虚拟节点，Hash不同
servers.put(FnvHash(serverUrl+"#1"), serverUrl);
servers.put(FnvHash(serverUrl+"#2"), serverUrl);
servers.put(FnvHash(serverUrl+"#3"), serverUrl);
}
return servers;
}
  这段代码将能提供的server放⼊排序Map，键为其Hash值，值为server的主机和IP，接下来就要对每⼀个请求的要连接的machin计算需要哪⼀个server进⾏连接：
/**
* @param machine 要连接的机器
* @param servers 可提供服务的server
* @return
*/
private static String getServer(int machine, ConcurrentSkipListMap<Integer, String> servers) {
int left=Integer.MAX_VALUE;
int right=Integer.MAX_VALUE;
int leftDis=0;
int rightDis=0;
for(Entry<Integer, String> Set()){
int Key();
if(key<machine){
left=key;
}else{
right=key;
}
if(right!=Integer.MAX_VALUE){
break;
}
}
if(left==Integer.MAX_VALUE){
left=servers.lastKey();
leftDis=Integer.MAX_VALUE-left+machine;
}else{
leftDis=machine-left;
}
if(right==Integer.MAX_VALUE){
right=servers.firstKey();
rightDis=Integer.MAX_VALUE-machine+right;
}else{
rightDis=right-machine;
}
(rightDis<=leftDis?right:left);
}
  这个⽅法就是计算，具体逻辑可以在看完下⼀节有更深的了解。
  经过上⾯的三个⽅法就解决了上⾯提出的要求，经过测试也完美，或许算法还看不懂，也或许⼀致Hash算法还不知道是什么，虚拟节点是什么，但是现在应该了解需求是怎么产⽣的，已经通过什么满⾜了要求，现在唯⼀要做的就是了解⼀致性Hash了，下⾯进⾏介绍。
三、⼀致性Hash介绍
3.1 理论简介
  ⼀致性Hash的简介，摘⾃百度百科。
  ⼀致性哈希算法在1997年由⿇省理⼯学院提出，设计⽬标是为了解决因特⽹中的热点(Hot spot)问题。⼀致性哈希提出了在动态变化的Cache环境中，哈希算法应该满⾜的4个适应条件：
均衡性(Balance)：
  平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利⽤。很多哈希算法都能够满⾜这⼀条件。
单调性(Monotonicity)：
  单调性是指如果已经有⼀些内容通过哈希分派到了相应的缓冲中，⼜有新的缓冲区加⼊到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，⽽不会被映射到旧的缓冲集合中的其他缓冲区。（这段翻译信息有负⾯价值的，当缓冲区⼤⼩变化时⼀致性哈希(Consistent hashing)尽量保护已分配的内容不会被重新映射到新缓冲区。）
分散性(Spread)：
  在分布式环境中，终端有可能看不到所有的缓冲，⽽是只能看到其中的⼀部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从⽽导致哈希的结果不⼀致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发⽣的严重程度。好的哈希算法应能够尽量避免不⼀致的情况发⽣，也就是尽量降低分散性。
负载(Load)：
  负载问题实际上是从另⼀个⾓度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于⼀个特定的缓冲区⽽⾔，也可能被不同的⽤户映射为不同的内容。与分散性⼀样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
3.2 设计实现
  ⼀般的⼀致性Hash的设计实现都是按照如下⽅式：
  ⾸先所有的Hash值应该构成⼀个环，就像钟表的时刻⼀样，也就是说有明确的Hash最⼤值，环内Hash的数量⼀般为2的32次⽅：
  将server通过Hash计算映射到环上，注意选取能区别开server的唯⼀属性，⽐如ip加端⼝：
  然后所有的把所有的请求使⽤唯⼀的属性计算Hash值，然后请求到最近的server上⾯：
  假如有新机器加⼊时：
  新机器相邻的请求会被重新定向到新的server，如果有机器挂掉的话，挂掉机器的请求也会重新分配给就近的server：
  通过上⾯的图例讲解，应该可以看出环形设计的好处，那就是不管新增还是减少机器，变动的都是变动机器附近的请求，已有请求的映射不会变动到已有的节点上。
四、对⼀致性Hash的理解
4.1 应⽤场景
  通过⼀致性Hash的特性来看，⼀致性Hash极⼒保证变动的最⼩化，⽐较适⽤于有状态连接，如果连接是⽆状态的，那么完全没必要使⽤这种算法，轮询或者随机都是可以的。效率要⽐⼀致性Hash⾼，省去了每⼀次请求的计算过程。
4.2 环的Hash数量的选择
  本质上没有特殊的要求，选取的原则可以考虑以下⼏点：
1. Hash数量最好最够多，因为要考虑未来新增server的情况，以及虚拟节点的添加
2. Hash数量的最⼤值在int范围内即可，int最⼤值已经⾜够⼤，⼤于int的会相对增加计算和存储成本
3. Hash数量的最⼤值的另⼀个参考要点，就是选取Hash算法的最⼤值
  所以上⾯的例⼦，环Hash数量选择了2^32，恰好fnv Hash算法的最⼤值也是它，。
4.3 虚拟节点的作⽤
  看过上⾯代码的应该知道，对server进⾏Hash的时候，会同时创建server的⼏个虚拟节点，它们同样代表着它们的server，有如下作⽤：
1. 防⽌server的Hash重复，虽然Hash重复的概率少之⼜少，但是依然不能完全避免，所以通过使⽤多个虚拟节点，可以避免因server的
Hash重复导致server被完全覆盖掉
2. 有利于负载均衡，如果每个server只有⼀个节点，那么有可能分布的不均匀，这时候通过多个虚拟节点，可以增加均匀分布的可能性，
当然这依赖于Hash算法的选择
  ⾄于虚拟节点的数量，这个没有硬性要求，节点的数量越多，负载均衡越好，但是计算量也越⼤，如果考虑到server集的易变性，每⼀次请求都需要重新计算server及其虚拟节点的Hash值，那么节点的数量不要太⼤，不然也是⼀个性能的瓶颈。
4.4 Hash算法的选择
  Hash算法有很多种，上⾯fnv hash的可以参考⼀下，⾄于其他的，考虑以下⼏点就可以：
不要⾃⼰写Hash算法，⽤已有的就可以，出于学习的⽬的可以写，⽣产环境⽤已有的Hash算法
算法速度⼀定要快
同⼀个输⼊的值，要有相同的输出
Hash值⾜够散列，Hash碰撞概率低
  考虑以上⼏点就可以了，后续会针对Hash算法，写⼀篇博客。
4.5 ⼀致性Hash的替代
  不⽤⼀致Hash可不可以，能不能满⾜相同的需求，答案是可以的，那就是主动维护⼀个路由表。基本要做以下操作：
1. ⾸先获得当前提供服务的server
2. 当有请求来临时，先判断当前请求是否已有对应的server，若有交由对应的server，若⽆，选择负载最低的⼀个server，并存记录
3. 当server挂掉以后，新的请求重新⾛2步骤
4. 当有新的server加⼊时，可以主动负载均衡，也可以重新⾛2步骤
  优缺点简单说⼀下：
优点：
负载更加均衡，甚⾄可以保证完全的均衡，因为不依赖Hash的不确定性
整个分配过程⼈为掌握，当某些请求必须分配到指定的server上，修改更简单
缺点：
编码量⼤，需要严格测试
需要主动维护⼀个路由表，存储是⼀个需要考虑的问题
请求量⼤时，路由表容量会增⼤，可以考虑存⼊Redis中
  以上就是我对⼀致Hash的理解，以及我在项⽬中的应⽤，希望可以帮助到有需要的⼈。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。