一致性哈希算法原理是什么
本篇内容主要讲解"一致性哈希算法原理是什么",感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习"一致性哈希算法原理是什么"吧!
【哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。[1] 】
理解起来稍稍有些吃力,没关系,用一个简单的hash算法来理解以下上面那段话:
int plusHash(String key, int cnt)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % cnt );
}
上面这段算法,通常称之为加法hash,输入:key=zhuganglie,cnt=23,输出:22
看看这段代码,基本上上面那段不太好理解的内容就相对容易一些了。
一致性哈希提出了在动态变化的Cache环境中,重点解决单调性的问题,单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 (请注意,以上是网上大多数技术文的说法,也不知道是来自于哪位大神的翻译,按照我的理解,所谓单调性应该指的是,当有新的缓冲区加入系统中的情况下,应该尽量保证原有已分配内容,不会被重新映射到新的缓冲区中去)
实际场景:现有n台服务器,构成一个服务器集群,现有算法是通过hash(obj) % n,来找到某一个请求对应的服务器,如果某一台服务器宕机了,就变成了 hash(obj) % n-1 ,显而易见,这时候会发生大量的访问错误,如果避免这种情况。
所谓一致性哈希,一致性究竟体现在什么地方,假设我们目前有4个对象和4个cache server,对这8个对象,采用统一的hash值空间,假定为1024。将此1024个值空间,想象成为一个环形结构。而4个对象和4个cache server,分别落在这1024个值当中的不同位置。
如上图所示,圆环是一个1024的值空间,我们把s1~s4这4台server和obj1~obj4这4个对象,分别落入这个值空间当中去,然后按照顺时针方向,为每一个obj,找到它所在的cache server。
对应结果是obj1~s2,obj2~s3,obj3~s4,obj4~s1。
考虑几种情况:
1、移除:s3发生了故障,上图变成了下面这个样子,新的对应关系变成了下面这个样子:
obj1~s2,obj2~s4,obj3~s4,obj4~s1。 我们看到,只有obj2的映射关系发生了变化。
2、添加:新增一个s5,新的结构如下所示,在这种情况下,映射关系甚至不会发生任何变化,如果s3和s5之间,有obj存在,也只是这一部分obj的映射关系发生了变化。
看到这里,单调性的问题,已经有了很好的解决方式。
下一步,还需要解决数据倾斜的问题,上面我们有了5台真实服务器,再把这个情况进一步极端化,我们只有2台真实服务器,我们是无法保证所有数据对象的hash值在环上均匀分布的,这样就会出现数据倾斜的问题。为了解决这一问题,我们还需要里另一个概念,虚拟节点。
首先是一个只有2台真实服务器的图,我们看到数据倾斜是比较严重的。
然后我们把2台真实服务器从环形结构当中拿掉,换成8个虚拟服务器,这8个虚拟服务器,交替的属于2台真实服务器,这样的话,数据倾斜问题,得到了极大地缓解。
到此,相信大家对"一致性哈希算法原理是什么"有了更深的了解,不妨来实际操作一番吧!这里是网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!