hash算法和hash一致性_分布式一致性hash

hash算法和hash一致性_分布式一致性hash一致性哈希算法(ConsistentHashing)最早在论文《ConsistentHashingandRandomTrees:DistributedCachingProtocolsforRelievingHotSpotsontheWorldWideWeb》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^

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

Jetbrains全系列IDE稳定放心使用

一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

hash算法和hash一致性_分布式一致性hash

  整个空间按顺时针方向组织。0和232-1在零点中方向重合。

  下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下:

 hash算法和hash一致性_分布式一致性hash 

接下来使用如下算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。

  例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:

hash算法和hash一致性_分布式一致性hash

根据一致性哈希算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:

hash算法和hash一致性_分布式一致性hash

此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X 。一般的,在一致性哈希算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器,其环分布如下,

hash算法和hash一致性_分布式一致性hash

此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

hash算法和hash一致性_分布式一致性hash

同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。


数据结构的选取

一致性Hash算法最先要考虑的一个问题是:构造出一个长度为232的整数环,根据节点名称的Hash值将服务器节点放置在这个Hash环上。

那么,整数环应该使用何种数据结构,才能使得运行时的时间复杂度最低?首先说明一点,关于时间复杂度,常见的时间复杂度与时间效率的关系有如下的经验规则:

O(1) < O(log2N) < O(N) < O(N * log2N) < O(N2) < O(N3)  < O(N!)

一般来说,前四个效率比较高,中间两个差强人意,最后一个后比较差(只要N比较大,这个算法就动不了了)。OK,继续前面的话题,应该如何选取数据结构,我认为有以下几种可行的解决方案。

1、解决方案一:排序+List

我想到的第一种思路是:算出所有待加入数据结构的节点名称的Hash值放入一个数组中,然后使用某种排序算法将其从小到大进行排序,最后将排序后的数据放入List中,采用List而不是数组是为了结点的扩展考虑。

之后,待路由的结点,只需要在List中找到第一个Hash值比它大的服务器节点就可以了,比如服务器节点的Hash值是[0,2,4,6,8,10],带路由的结点是7,只需要找到第一个比7大的整数,也就是8,就是我们最终需要路由过去的服务器节点。

如果暂时不考虑前面的排序,那么这种解决方案的时间复杂度:

(1)最好的情况是第一次就找到,时间复杂度为O(1)

(2)最坏的情况是最后一次才找到,时间复杂度为O(N)

平均下来时间复杂度为O(0.5N+0.5),忽略首项系数和常数,时间复杂度为O(N)。

但是如果考虑到之前的排序,我在网上找了张图,提供了各种排序算法的时间复杂度:

hash算法和hash一致性_分布式一致性hash

看得出来,排序算法要么稳定但是时间复杂度高、要么时间复杂度低但不稳定,看起来最好的归并排序法的时间复杂度仍然有O(N * logN),稍微耗费性能了一些。

2、解决方案二:遍历+List

既然排序操作比较耗性能,那么能不能不排序?可以的,所以进一步的,有了第二种解决方案。

解决方案使用List不变,不过可以采用遍历的方式:

(1)服务器节点不排序,其Hash值全部直接放入一个List中

(2)带路由的节点,算出其Hash值,由于指明了”顺时针”,因此遍历List,比待路由的节点Hash值大的算出差值并记录,比待路由节点Hash值小的忽略

(3)算出所有的差值之后,最小的那个,就是最终需要路由过去的节点

在这个算法中,看一下时间复杂度:

1、最好情况是只有一个服务器节点的Hash值大于带路由结点的Hash值,其时间复杂度是O(N)+O(1)=O(N+1),忽略常数项,即O(N)

2、最坏情况是所有服务器节点的Hash值都大于带路由结点的Hash值,其时间复杂度是O(N)+O(N)=O(2N),忽略首项系数,即O(N)

所以,总的时间复杂度就是O(N)。其实算法还能更改进一些:给一个位置变量X,如果新的差值比原差值小,X替换为新的位置,否则X不变。这样遍历就减少了一轮,不过经过改进后的算法时间复杂度仍为O(N)。

总而言之,这个解决方案和解决方案一相比,总体来看,似乎更好了一些。

3、解决方案三:二叉查找树

抛开List这种数据结构,另一种数据结构则是使用二叉查找树。对于树不是很清楚的朋友可以简单看一下这篇文章树形结构

当然我们不能简单地使用二叉查找树,因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等,这里使用红黑树,选用红黑树的原因有两点:

1、红黑树主要的作用是用于存储有序的数据,这其实和第一种解决方案的思路又不谋而合了,但是它的效率非常高

2、JDK里面提供了红黑树的代码实现TreeMap和TreeSet

另外,以TreeMap为例,TreeMap本身提供了一个tailMap(K fromKey)方法,支持从红黑树中查找比fromKey大的值的集合,但并不需要遍历整个数据结构。

使用红黑树,可以使得查找的时间复杂度降低为O(logN),比上面两种解决方案,效率大大提升。

为了验证这个说法,我做了一次测试,从大量数据中查找第一个大于其中间值的那个数据,比如10000数据就找第一个大于5000的数据(模拟平均的情况)。看一下O(N)时间复杂度和O(logN)时间复杂度运行效率的对比:


50000 100000 500000 1000000 4000000
ArrayList 1ms 1ms 4ms 4ms 5ms
LinkedList 4ms 7ms 11ms 13ms 17ms
TreeMap 0ms 0ms 0ms 0ms 0ms

因为再大就内存溢出了,所以只测试到4000000数据。可以看到,数据查找的效率,TreeMap是完胜的,其实再增大数据测试也是一样的,红黑树的数据结构决定了任何一个大于N的最小数据,它都只需要几次至几十次查找就可以查到。

当然,明确一点,有利必有弊,根据我另外一次测试得到的结论是,为了维护红黑树,数据插入效率TreeMap在三种数据结构里面是最差的,且插入要慢上5~10倍

 

Hash值重新计算

服务器节点我们肯定用字符串来表示,比如”192.168.1.1″、”192.168.1.2″,根据字符串得到其Hash值,那么另外一个重要的问题就是Hash值要重新计算,这个问题是我在测试String的hashCode()方法的时候发现的,不妨来看一下为什么要重新计算Hash值:

/**
 * 对于ip地址来说,前边的部分基本都相同,所以默认的hashcode分布不均匀
 * @author tanlk
 * @datetime  2017年8月4日 下午4:31:21
 */
public class StringHashCodeTest {
	public static void main(String[] args) {
		System.out.println("192.168.0.0:111的哈希值:" + "192.168.0.0:8181".hashCode());
		System.out.println("192.168.0.1:111的哈希值:" + "192.168.0.1:8181".hashCode());
		System.out.println("192.168.0.2:111的哈希值:" + "192.168.0.2:8181".hashCode());
		System.out.println("192.168.0.3:111的哈希值:" + "192.168.0.3:8181".hashCode());
		System.out.println("192.168.0.4:111的哈希值:" + "192.168.0.4:8181".hashCode());
	}
}

我们在做集群的时候,集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为:

192.168.0.0:111的哈希值:1846078841
192.168.0.1:111的哈希值:1874707992
192.168.0.2:111的哈希值:1903337143
192.168.0.3:111的哈希值:1931966294
192.168.0.4:111的哈希值:1960595445

这个就问题大了,[0,232-1]的区间之中,5个HashCode值却只分布在这么小小的一个区间,什么概念?[0,232-1]中有4294967296个数字,而我们的区间只有114516604,从概率学上讲这将导致97%待路由的服务器都被路由到”192.168.0.0″这个集群点上,简直是糟糕透了!

另外还有一个不好的地方:规定的区间是非负数,String的hashCode()方法却会产生负数(不信用”192.168.1.0:1111″试试看就知道了)。不过这个问题好解决,取绝对值就是一种解决的办法。

综上,String重写的hashCode()方法在一致性Hash算法中没有任何实用价值,得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。

 

不带虚拟节点的一致性Hash Java实现

 

import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 不带虚拟节点的一致性Hash算法
 * @author tanlk
 * @datetime  2017年8月4日 下午2:57:01
 */
public class ConsistentHashNoVirtualNode {

	//待加入hash环的服务器列表
    private static String[] servers = {"192.168.0.0:8081", "192.168.0.1:8081", "192.168.0.2:8081","192.168.0.3:8081","192.168.0.4:8081"};
    
    //key 服务器hash值,value服务器名称
    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer,String>();
    
	static {
		for(int i=0; i<servers.length; i++){
			int hash = getHash(servers[i]);
			System.out.println(servers[i] +"加入集合中,其Hash值为" +hash);
			sortedMap.put(hash, servers[i]);
			
		}
	}
	
	/**
	 * 使用FNV1_32_HASH算法计算服务器的hash值
	 * @param str
	 * @return
	 */
	private static int getHash(String str){
		final int p = 16777619;
		int hash =  (int) 2166136261L;
		for(int i = 0; i< str.length(); i++)
			hash = (hash ^ str.charAt(i)) * p;
		hash += hash << 13;
		hash ^= hash >> 7;
		hash += hash << 3;
		hash ^= hash >> 17;
		hash += hash << 5;
		// 如果算出来的值为负数则取其绝对值
		if (hash < 0)
		hash = Math.abs(hash);
		return hash;
	}
	
	/**
	 * 应该路由到哪台服务器
	 * @param node
	 * @return
	 */
	private static String getServer(String node){
		int hash = getHash(node);
		//得到大于该Hash值得所有Map
		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
		// 第一个Key就是顺时针过去离node最近的那个结点
		Integer i = subMap.firstKey();
		return subMap.get(i);
	}
	
	public static void main(String[] args) {
		String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "102.211.0.122:3333" , "238.226.0.1:2222", "221.211.0.122:3333"};
		for (int i = 0; i < nodes.length; i++)
			System.out
					.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
	}
}

带虚拟节点的一致性Hash Java实现


import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;/** * 带虚拟节点的一致性Hash算法 * @author tanlk * @datetime  2017年8月4日 下午4:08:20 */public class ConsistentHashHaveVirtualNode {	//待加入hash环的服务器列表    private static String[] servers = {"192.168.0.0:8081", "192.168.0.1:8081", "192.168.0.2:8081","192.168.0.3:8081","192.168.0.4:8081"};        //真实节点列表,因为服务器上下线很正常,添加删除比较多,用LinkedList会更好    private static List<String> realNodes = new LinkedList<String>();        //虚拟节点 key 服务器虚拟节点的hash值,value服务器名称    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer,String>();        //设置虚拟节点和真实节点的倍数,一个真实服务器有8个虚拟节点    private static final int V_NODE_NUM = 8;    	static {		for(int i=0; i<servers.length; i++){			realNodes.add(servers[i]);		}		for (String str : realNodes) {			for (int i = 0; i < V_NODE_NUM; i++){				String vNodeName = str +"&&VN" + i;				int hash = getHash(vNodeName);				System.out.println("虚拟节点[" + vNodeName + "]被添加, hash值为" + hash);				virtualNodes.put(hash, vNodeName);			}		}			}		/**	 * 使用FNV1_32_HASH算法计算服务器的hash值	 * @param str	 * @return	 */	private static int getHash(String str){		final int p = 16777619;		int hash =  (int) 2166136261L;		for(int i = 0; i< str.length(); i++)			hash = (hash ^ str.charAt(i)) * p;		hash += hash << 13;		hash ^= hash >> 7;		hash += hash << 3;		hash ^= hash >> 17;		hash += hash << 5;		// 如果算出来的值为负数则取其绝对值		if (hash < 0)		hash = Math.abs(hash);		return hash;	}		/**	 * 应该路由到哪台服务器	 * @param node	 * @return	 */	private static String getServer(String node){		int hash = getHash(node);		//得到大于该Hash值得所有Map		SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);		// 第一个Key就是顺时针过去离node最近的那个结点		Integer i = subMap.firstKey();		//获取虚拟节点		String vNodeName = subMap.get(i);				System.out.println(vNodeName);		//截取真实节点		return vNodeName.split("&&VN")[0];	}		public static void main(String[] args) {				String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "102.211.0.122:3333" , "238.226.0.1:2222", "221.211.0.122:3333"};		for (int i = 0; i < nodes.length; i++)			System.out					.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");	}}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185507.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Java中Scanner用法总结

    Java中Scanner用法总结最近在做OJ类问题的时候,经常由于Scanner的使用造成一些细节问题导致程序不通过(最惨的就是网易笔试,由于sc死循环了也没发现,导致AC代码也不能通过。。。),因此对Scanner进行了一些总结整理。Scanner类简介Java5添加了java.util.Scanner类,这是一个用于扫描输入文本的新的实用程序。它是以前的StringTokenizer和Matcher类之间的某种结合。由于任何

  • 用Python发免费短信的正确姿势

    用Python发免费短信的正确姿势前言今天带大家来玩一玩,如何用Python来实现免费短信。关于发短信,其实适用场景还挺多的。只有你想不到的场景,没有玩不转的场景!比如作为一个IT人员,经常会有监控服务器之说,那么自动告警的短信或者来电就显得非常重要了。再比如,你可以用发短信的功能,自己来实现一个温馨天气预报提示给你的爸爸妈妈。。。等等下面进入今天的主题-twilio网站。https://www.twilio.com/console准备工作先来介绍下这个网站主要用于发短信和来电,提供了完备的相关api。而

  • 最全静态网页模板网站下载_网页首页内容模板

    最全静态网页模板网站下载_网页首页内容模板前言最近好多人私信我:我学了不久前端,想要用一些项目实战来练练手。那么,我以后将定期更新静态网页实战,专用于提供初学者的练习。那么这次博客为大家提供一些模板网站,希望初学者借鉴和学习优质资源:以下网站对于初学者的作用:提供免费的静态网页下载提高自己的css+html5设计水平http://sc.chinaz.com/moban/“站长素材”网站中包括大量的免费模板,可任意下载。…

  • pycharm的虚拟环境

    pycharm的虚拟环境选中file==》closeproject退出项目进入下方的情况现在我们在桌面新创建一个文件test.py可以看到可以执行test.py右键选中test.py,选择pycharm的方式打开test.py,会发现无法调试,出现NoPythonInterpreter的错误,为什么命令行可以执行test.py,pycharm执行test.py文件就不可以了呢?这是为什么呢?我们新建一个项目来查看原因第一个location为你项目的路径,可以点击右边的文件夹进行选择。第二个locatio.

  • phpstorm 比较修改过的代码 version control

    phpstorm 比较修改过的代码 version control

    2021年11月10日
  • ubuntu下deb包安装方法_ubuntu安装下载文件

    ubuntu下deb包安装方法_ubuntu安装下载文件deb包是Debian,Ubuntu等Linux发行版的软件安装包,扩展名为.deb,是类似于rpm的软件包,Debian,Ubuntu系统不推荐使用deb软件包,因为要解决软件包依赖问题,安装也比较麻烦。如果Ubuntu要安装新软件,已有deb安装包(例如:linuxidc.deb),但是无法登录到桌面环境。那该怎么安装?答案是:使用dpkg命令。dpkg是Debianlinuxidc的简写,是为Debian专门开发的套件管理系统,方便软件的安装、更新及移除。所有源自Debian的Linux发行

    2022年10月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号