DHT和一致性哈希算法总结

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Hash算法比较重要的考量点有两个：

1.单调性（新增或者减少映射节点时，尽量不影响原有映射关系） 2.平衡性（尽量均匀分布）

分布式领域常见负载均衡算法：

（1）取余法：%n

如果有3个节点，Hash之后取模求余  Hash（x）%3，

如果加一个节点，则 Hash（x）%4。

这种方法带来的问题：

1 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ； 2 由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ； 1 和 2 意味着什么？这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器； 再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。 有什么方法可以改变这个状况呢，这就是 consistent hashing…

 解释下为什么cache会失效：

  假如有6个数据分别是1，2，3，4，5，6，有3台机器，用取余算法%3。设定余数为0对应的是第一台机器，余数为1对应的是第二台机器，余数为2对应的是第三台机器。那么数据3和6存储在第一台机器，1和4存储在第二台机器，2和5存储在第三台机器。如果这时候增加一台机器变成4台，用取余算法%4实现，映射到某台机器的规则和之前的类似，那么数据4存储在第一台机器，数据1和5存储在第二台机器，数据2和6存储在第三台机器，数据3存储在第4台机器。

  原来3台机器： M1：（3，6） M2: （1，4）  M3: （2，5）

  变成4台机器：M1: （4） M2: （1，5） M3: （2，6） M4: （3） 

   可以看到1，2，3，4台机器的数据都将会有变化。

而如果采用一致性hash算法，则能减少数据变化的机器。

（2）一致性hash算法

  实现步骤：

第一步：采用一种hash算法，把服务器地址或者主机名映射到一个2的32次方的环上。为什么是2的32次方？IPv4的ip地址占4个字节，可以存储2的32次方比特位信息。

第二步：把要存储的key采用同样的hash算法映射到环上，如果命中某个服务器地址则存在该台服务器，如果在服务器1和服务器2的地址的中间，则按从小到大去搜索，找到的第一个服务器，就映射到该台服务器上。

好处：增加和减少节点时，只影响附近的一个节点，不会像取余法一样影响全部节点的数据。

改进：

另外，一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器，可能大量的数据都存在一台服务器，另一台服务器只存储了很少的数据。为了解决这种情况，可以增加虚拟环。

为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，注意，这里的多个哈希算法应该使得结果尽量分布均匀，才能最大程度减少数据倾斜的情况。每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。