好用的网站系统,网站推广怎么做,红杉树装饰公司口碑怎么样,低价自适应网站建设优化建站文章目录 前言正文一、抛砖引玉#xff0c;简单Hash算法的短板二、一致性Hash算法的基本概念2.1 一致性Hash算法本质也是取模2.2 便于理解的抽象#xff0c;哈希环2.3 服务器如何映射到哈希环上2.4 对象如何映射到哈希环上#xff0c;并关联到对应的机器 三、一致性Hash算法… 文章目录 前言正文一、抛砖引玉简单Hash算法的短板二、一致性Hash算法的基本概念2.1 一致性Hash算法本质也是取模2.2 便于理解的抽象哈希环2.3 服务器如何映射到哈希环上2.4 对象如何映射到哈希环上并关联到对应的机器 三、一致性Hash算法在增加或减少机器时的骚操作3.1 服务器数量减少3.2 服务器数量增加 四、数据倾斜、机器负载的处理4.1 数据倾斜的体现4.2 机器负载的体现4.3 处理方案增加虚拟节点 五、Java代码模拟算法5.1 定义哈希算法接口5.2 简单哈希算法5.3 一致性哈希算法不包含虚拟节点5.4 一致性哈希算法包含虚拟节点5.5 测试5.6 测试结果 六、一致性哈希算法的应用场景 前言
首先我们学习和了解一个知识时可能会先下意识搜索一下它的基本概念。所以我先百度了一下。
百度给出的概念可以说是很明确了 一致性哈希算法在1997年由麻省理工学院提出是一种特殊的哈希算法目的是解决分布式缓存的问题。 在移除或者添加一个服务器时能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。 一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash TableDHT) 中存在的动态伸缩等问题 。 正文
根据百度我们可以知道所谓一致性Hash算法是一种特殊的Hash算法。
那么学习的捷径就出来了我们可以对比学习先来看看Hash算法然后再去研究它对于解决动态伸缩问题上的短板究竟是什么。
一、抛砖引玉简单Hash算法的短板
我们先假设出这样一个场景 当前有3台机器 node1、node2 、node3是我们用来存储缓存的。业务数据缓存目前假设有100万个key。 我们的需求是将这100万个key 尽可能均匀的存储到这3台机器上。 效果图如下 当我们采取简单Hash算法时对所有的key值进行hash计算获取到一个hash值再取模于33台机器所以取模于3。
这样就能保证所有算出来的结果一定是 0、1、2 这3个数从而对应到我们的3台机器就可以解决以上的问题。如下图所示
那么问题来了在分布式场景中我们的机器会有数量调整的情况。 就好比电商相关的项目在618、双11等购物狂欢节时就需要临时增加机器然后等高峰期过后又需要减少节点。
这种时候对机器数量取模就不好使了。
假设原先有3台机器存值时使用的是取模于3在用的时候有一台挂了取值时取模于2如下图 这种时候由于node3挂掉取模模于2自然会有很多缓存无法命中也就是失效。
那么大量缓存同时失效就可以恭喜你了喜提缓存雪崩整个缓存系统不可用这也就是简单Hash算法无法处理的短板也正是一致性Hash算法所解决的问题之一。
二、一致性Hash算法的基本概念
它的基本概念其实就和我百度出来的相同。可以翻到本文前言再重新读一遍理解一下。
本小节内容主要是基于百度出来的基本概念进行图文讲解。
2.1 一致性Hash算法本质也是取模
一致性Hash算法本质上也是取模运算只是与简单Hash算法不同它是对 2 的 32 次方 取模。 原因如下 我们都知道IPv4地址是由 4 段 8位二进制组成的因为书写方便的问题将二进制转换为十进制例如如下地址 而这个地址的大小范围则是 [0, 2的32次方)所以取模的值可以固定下来能够保证每个IP地址有唯一的映射。 2.2 便于理解的抽象哈希环
上一小节提到IP地址的范围是 [0, 2的32次方)如果我们将所有的值抽象成环正上方为0以顺时针排列。 将所有的值抽象为圆周上的点那么可以获得如下的哈希环
2.3 服务器如何映射到哈希环上
假设现在有3台机器分别是 nodeA 、nodeB 、nodeC我们要把他们映射到哈希环中。
首先使用哈希算法对机器的IP地址进行计算随后再取模得到 A、B、C 这3个值。随后根据计算结果映射到哈希环上。
2.4 对象如何映射到哈希环上并关联到对应的机器
假设有4个对象需要存起来。
对象计算时的hash函数可以和服务器节点的函数不同但需要保证计算结果在环的范围内。 计算的结果分别是 H1H2H3H4将他们先映射到Hash环上。 然后从0开始顺时针转圈当对象计算出的结果蓝色H第一次遇到绿色机器就存到该机器上。关联后的结果如下 H2和H4存到了 B 机器上H1存到了C机器上H3存到了A机器上 本质是将原本单个点的Hash映射转变成了环上的某个片段的映射也就是百度百科中提到的
在移除或者添加一个服务器时能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
这一原理的实现也就在于此。我们接着往下看。
三、一致性Hash算法在增加或减少机器时的骚操作
3.1 服务器数量减少
比如C机器挂了H1会存到A机器上 3.2 服务器数量增加
比如增加机器DH2会存到D机器上 四、数据倾斜、机器负载的处理
但凡使用了Hash算法就可能存在数据倾斜的问题这里我们不考虑哈希冲突。上述例子中为了方便演示基本使用了比较均衡的散列示例。
这里我们需要考虑两个问题
数据倾斜也就是Hash散列不均匀可能给一个机器存储过多的对象数据而有的机器却一个都不存储机器负载不均衡在增加机器时不能很好的分摊机器负载或只分担很少机器的负载在现象上看其实勉强也算是一种数据倾斜的问题
4.1 数据倾斜的体现
很多对象集中映射到某一台或几台机器其他机器数据映射很少甚至于没有。 可以看到很多数据都映射到了B机器而A 、C 机器上映射的数据很少。
4.2 机器负载的体现
在数据倾斜发生时本身就是机器负载不均衡的一种体现但本小节提到的是另一种场景。
在我们增加机器时新增的机器不能很好的分担其他机器的负载这也是一个问题。
比如为了帮忙分担负载增加了机器D
但是D映射的位置比较尴尬没有帮助B 分担到负载。
又或者说另一种情况A 机器现在也有很多数据存储我们新增机器D D的出现帮B分担了部分压力但是对A没有任何影响。
4.3 处理方案增加虚拟节点
为了处理以上的两个问题可以引入虚拟节点的概念。 所谓虚拟节点就是针对每个实际机器计算多个映射点。 比如 针对nodeA 计算的虚拟节点有 A#1 、A#2 、A#3 实际节点是 A 针对nodeB 计算的虚拟节点有 B#1 、B#2 、B#3实际节点是 B 针对nodeC 计算的虚拟节点有 C#1 、C#2 、C#3实际节点是 C 他们分布在哈希环上之后就如下图所示 使用虚拟节点时可以看到当虚拟节点越多也就越不容易出现数据倾斜。
然后我们再依据虚拟节点对真实节点做一套转换即可。 也就是原先找节点的逻辑基本不变只是在找到虚拟节点时一律定位到实际机器上。
比如我们找到数据H3 在 A#2虚拟节点上就在此定位到A机器真实的节点A上。
五、Java代码模拟算法
Java 版本使用Java 9 涉及到的类文件有
5.1 定义哈希算法接口
定义接口用以实现3种哈希算法
package com.example.demo;import java.util.List;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;/*** 哈希算法接口** author feng*/
public interface HashAlgorithm {/*** 哈希算法** param clients 客户端集合* return 服务端地址和客户端地址列表的映射*/SortedMapString, ListString hash(SetString clients);/*** 服务器的编号、地址*/SortedMapInteger, String SERVER_ADDRESS_MAP new TreeMap();
}
5.2 简单哈希算法
package com.example.demo;import java.util.*;/*** 简单Hash算法** author feng*/
public class GeneralHashAlgorithm implements HashAlgorithm {private final int serverCount;public GeneralHashAlgorithm(int serverCount) {this.serverCount serverCount;}Overridepublic SortedMapString, ListString hash(SetString clients) {SortedMapString, ListString resultMap new TreeMap();for (String client : clients) {// 执行hash获取值int hashCode Math.abs(client.hashCode());// 计算索引int index hashCode % serverCount;// 获取选中的服务器地址String serverAddress SERVER_ADDRESS_MAP.get(index);System.out.printf(客户端%s 选中了服务端序号为%s地址为%s \r\n, client, index, serverAddress);ListString newArrayList resultMap.getOrDefault(serverAddress, new ArrayList());newArrayList.add(client);resultMap.put(serverAddress, newArrayList);}return resultMap;}
}5.3 一致性哈希算法不包含虚拟节点
package com.example.demo;import java.util.*;/*** 一致性哈希算法-不包括虚拟节点** author feng*/
public class ConsistencyExcludeVirtualNodeHashAlgorithm implements HashAlgorithm {Overridepublic SortedMapString, ListString hash(SetString clients) {SortedMapString, ListString resultMap new TreeMap();// 哈希散列服务端地址SortedMapInteger, String hashServerMap serverHash();// 处理客户端地址for (String client : clients) {int clientHashCode Math.abs(client.hashCode());// 从服务端地址中查找能够处理的服务器节点,tailMap表示返回此映射中键大于或等于key的部分的mapSortedMapInteger, String tempSortedMap hashServerMap.tailMap(clientHashCode);// 从当前节点顺时针转完一整圈回到0点仍未发现能够处理的服务器if (tempSortedMap.isEmpty()) {// 取哈希环中的第一个服务器Integer firstKey hashServerMap.firstKey();String firstAddress hashServerMap.get(firstKey);System.out.printf(客户端%s 选中了服务端序号为%s地址为%s \r\n, client, firstKey, firstAddress);ListString newArrayList resultMap.getOrDefault(firstAddress, new ArrayList());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);} else {// 从哈希环取符合条件的服务器Integer firstKey tempSortedMap.firstKey();String firstAddress hashServerMap.get(firstKey);System.out.printf(客户端%s 选中了服务端序号为%s地址为%s \r\n, client, firstKey, firstAddress);ListString newArrayList resultMap.getOrDefault(firstAddress, new ArrayList());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);}}return resultMap;}private SortedMapInteger, String serverHash() {SortedMapInteger, String hashServerMap new TreeMap();SERVER_ADDRESS_MAP.forEach((k, v) - {int serverAddressHashCode Math.abs(v.hashCode());hashServerMap.put(serverAddressHashCode, v);});return hashServerMap;}
}5.4 一致性哈希算法包含虚拟节点
package com.example.demo;import java.util.*;/*** 一致性哈希算法-包括虚拟节点** author feng*/
public class ConsistencyIncludeVirtualNodeHashAlgorithm implements HashAlgorithm {/*** 虚拟节点个数*/private final int virtualNodeCount;public ConsistencyIncludeVirtualNodeHashAlgorithm(int virtualNodeCount) {this.virtualNodeCount virtualNodeCount;}Overridepublic SortedMapString, ListString hash(SetString clients) {SortedMapString, ListString resultMap new TreeMap();// 哈希散列服务端地址增加虚拟节点映射SortedMapInteger, String hashServerMap serverHash();for (String client : clients) {int clientHashCode Math.abs(client.hashCode());// 从服务端地址中查找能够处理的服务器节点,tailMap表示返回此映射中键大于或等于key的部分的mapSortedMapInteger, String tempSortedMap hashServerMap.tailMap(clientHashCode);// 从当前节点顺时针转完一整圈回到0点仍未发现能够处理的服务器if (tempSortedMap.isEmpty()) {// 取哈希环中的第一个服务器Integer firstKey hashServerMap.firstKey();String firstAddress hashServerMap.get(firstKey);System.out.printf(客户端%s 选中了服务端序号为%s地址为%s \r\n, client, firstKey, firstAddress);ListString newArrayList resultMap.getOrDefault(firstAddress, new ArrayList());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);} else {// 从哈希环取符合条件的服务器Integer firstKey tempSortedMap.firstKey();String firstAddress hashServerMap.get(firstKey);System.out.printf(客户端%s 选中了服务端序号为%s地址为%s \r\n, client, firstKey, firstAddress);ListString newArrayList resultMap.getOrDefault(firstAddress, new ArrayList());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);}}return resultMap;}private SortedMapInteger, String serverHash() {SortedMapInteger, String hashServerMap new TreeMap();SERVER_ADDRESS_MAP.forEach((k, v) - {int serverAddressHashCode Math.abs(v.hashCode());hashServerMap.put(serverAddressHashCode, v);// 增加虚拟节点for (int i 0; i virtualNodeCount; i) {String virtualNodeName v # i;int virtualNodeHashCode Math.abs((virtualNodeName).hashCode());hashServerMap.put(virtualNodeHashCode, virtualNodeName);}});return hashServerMap;}
}
5.5 测试
package com.example.demo;import java.util.*;/*** 测试** author feng*/
public class Client {static {HashAlgorithm.SERVER_ADDRESS_MAP.put(0, 11.123.32.3);HashAlgorithm.SERVER_ADDRESS_MAP.put(1, 23.43.41.1);HashAlgorithm.SERVER_ADDRESS_MAP.put(2, 192.169.21.3);}public static void main(String[] args) {SetString set Set.of(10.78.12.3, 113.25.63.1, 126.12.3.8);SortedMapString, ListString hash;// 简单hash算法hash new GeneralHashAlgorithm(3).hash(set);hash.forEach((k, v) - System.out.printf(简单hash算法-客户端地址%s已经映射到服务端%s \r\n, v, k));System.out.println();// 一致性hash算法不包括虚拟节点hash new ConsistencyExcludeVirtualNodeHashAlgorithm().hash(set);hash.forEach((k, v) - System.out.printf(一致性hash算法不包括虚拟节点-客户端地址%s已经映射到服务端%s \r\n, v, k));System.out.println();// 一致性hash算法包括虚拟节点hash new ConsistencyIncludeVirtualNodeHashAlgorithm(3).hash(set);hash.forEach((k, v) - {// 截取真实服务端地址String realServer k;if (k.contains(#)) {realServer k.substring(0, k.indexOf(#));}System.out.printf(一致性hash算法包括虚拟节点-客户端地址%s已经映射到服务端%s ,真实的服务器地址是%s \r\n, v, k, realServer);});}
}5.6 测试结果
客户端113.25.63.1 选中了服务端序号为2地址为192.169.21.3
客户端10.78.12.3 选中了服务端序号为1地址为23.43.41.1
客户端126.12.3.8 选中了服务端序号为1地址为23.43.41.1
简单hash算法-客户端地址[113.25.63.1]已经映射到服务端192.169.21.3
简单hash算法-客户端地址[10.78.12.3, 126.12.3.8]已经映射到服务端23.43.41.1 客户端113.25.63.1 选中了服务端序号为1763606946地址为192.169.21.3
客户端10.78.12.3 选中了服务端序号为1763606946地址为192.169.21.3
客户端126.12.3.8 选中了服务端序号为47976546地址为23.43.41.1
一致性hash算法不包括虚拟节点-客户端地址[113.25.63.1, 10.78.12.3]已经映射到服务端192.169.21.3
一致性hash算法不包括虚拟节点-客户端地址[126.12.3.8]已经映射到服务端23.43.41.1 客户端113.25.63.1 选中了服务端序号为1139178415地址为23.43.41.1#2
客户端10.78.12.3 选中了服务端序号为632380315地址为11.123.32.3#0
客户端126.12.3.8 选中了服务端序号为47976546地址为23.43.41.1
一致性hash算法包括虚拟节点-客户端地址[10.78.12.3]已经映射到服务端11.123.32.3#0 ,真实的服务器地址是11.123.32.3
一致性hash算法包括虚拟节点-客户端地址[126.12.3.8]已经映射到服务端23.43.41.1 ,真实的服务器地址是23.43.41.1
一致性hash算法包括虚拟节点-客户端地址[113.25.63.1]已经映射到服务端23.43.41.1#2 ,真实的服务器地址是23.43.41.1 六、一致性哈希算法的应用场景
PC框架Dubbo用来选择服务提供者分布式关系数据库分库分表数据与节点的映射关系LVS负载均衡调度器memcached 路由算法redis 的hash槽
