目录

Hash算法

Hash算法只是一个定义,并没有规定具体的实现

简述

把任意长度的输入,通过Hash算法变换成固定长度的输出,这个输出就是Hash值。哈希值的空间远小于输入的空间,所以可能会发生“哈希碰撞”,即两个不同的输入,产生了同一个输出。Hash算法常用于消息摘要的场景 MD5、SHA都属于Hash算法的实现。

简单使用

凡是涉及到分布式的系统,就会有负载均衡和数据分布的问题。为了让连接或者数据能够分布得更均匀,很多时候会使用到Hash算法

  • Hash取模(hash(requestId) % n)

    假设我们现在有3个服务器,想要做负载均衡,就可以对请求的ip地址或者用户的id等使用Hash函数,然后将计算得出的Hash值对3取模,余数为几,就把请求分配到相应的服务器上

    缺点: 如果新增服务器的时候,绝大多数请求基本上都需要重新映射到另一个节点。这种变动有时候是不能接受的。比如在Web负载均衡的场景下,session会保存在每个节点里。当然,如果你是“无状态”的服务,那不会存在这个问题,否则如果增加或者删除了一个节点,就会导致几乎所有的数据都需要重新迁移。

  • 一致性hash

    优点解决因为横向伸缩导致的大规模数据变动

    上面说到用节点的数量作为除数去求余。而一致性Hash的除数是$2^{32}$。从0到$2^{32} - 1$,首尾相连构成了一个环。我们先对服务器节点的IP进行Hash,然后除以$2^{32}$ 得到服务器节点在这个Hash环中的位置。如果有请求进来了,同样进行Hash然后处于$2^{32}$求余。如果落在Hash环上,然后顺时针找到第一个节点,这个节点就负责处理这个请求。一致性Hash算法在节点数量较少的时候,会出现分布不均匀的问题。解决这个问题的方案就是在Hash环上增加虚拟节点

解决Hash冲突

开放地址法

为产生冲突的地址H(key)求得一个地址序列:$H_0,H_1,H_2,…,H_s \quad 1 \le s \le m-1$

其中: $H_0 = H(key)$

$H_i = (H(key) + d_i) \quad MOD \quad m \qquad i = 1,2,…s$

其中 m 为表的长度 对增量$d_i$有三种取法

  1. 线性探测再散列

    $d_i = 1 , 2 , 3 , … , m-1s$

  2. 平方探测再散列

    $d_i = 1 , -1 , 2, -2 , 3 , -3 , … , k , -k$(取相应数的平方)

  3. 伪随机探测再散列

    $d_i$ 是一组伪随机数列

举例

https://gitee.com/lienhui68/picStore/raw/master/null/20200731105250.png

链地址法

链地址法的基本思想是:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向 链表连接起来,如: 键值对k2, v2与键值对k1, v1通过计算后的索引值都为2,这时及产生冲突,但是可以通道next指针将k2, k1所在的节点连接起来,这样就解决了哈希的冲突问题

https://gitee.com/lienhui68/picStore/raw/master/null/20200731105338.png

再hash法

再哈希法又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数 计算地址,直到无冲突。虽然不易发生聚集,但是增加了计算时间。

建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

一致性Hash

前言

可以参考上文中关于hash算法的简单实用

在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息),起到负载均衡的作用。

但是普通的余数hash(hash(比如用户id)%服务器机器数)算法伸缩性很差,当新增或者下线服务器机器时候,用户id与服务器的映射关系会大量失效。一致性hash则利用hash环对其进行了改进。

概述

为了能直观的理解一致性hash原理,这里结合一个简单的例子来讲解,假设有4台服务器,地址为ip1,ip2,ip3,ip4。

  • 一致性hash是首先计算四个ip地址对应的hash值 hash(ip1),hash(ip2),hash(ip3),hash(ip3),计算出来的hash值是0~最大正整数直接的一个值,这四个值在一致性hash环上呈现如下图:

    https://gitee.com/lienhui68/picStore/raw/master/null/20200731105746.png

  • hash环上顺时针从整数0开始,一直到最大正整数,我们根据四个ip计算的hash值肯定会落到这个hash环上的某一个点,至此我们把服务器的四个ip映射到了一致性hash环

  • 当用户在客户端进行请求时候,首先根据hash(用户id)计算路由规则(hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip.

    https://gitee.com/lienhui68/picStore/raw/master/null/20200731105849.png

    如上图可知user1,user2的请求会落到服务器ip2进行处理,User3的请求会落到服务器ip3进行处理,user4的请求会落到服务器ip4进行处理,user5,user6的请求会落到服务器ip1进行处理。

  • 下面考虑当ip2的服务器挂了的时候会出现什么情况?, 当ip2的服务器挂了的时候,一致性hash环大致如下图:

    https://gitee.com/lienhui68/picStore/raw/master/null/20200731105942.png

    根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理,而其它用户的请求对应的处理服务器不变,也就是只有之前被ip2处理的一部分用户的映射关系被破坏了,并且其负责处理的请求被顺时针下一个节点委托处理

  • 下面考虑当新增机器的时候会出现什么情况?当新增一个ip5的服务器后,一致性hash环大致如下图:

    https://gitee.com/lienhui68/picStore/raw/master/null/20200731110145.png

    根据顺时针规则可知之前user5的请求应该被ip5服务器处理,现在被新增的ip5服务器处理,其他用户的请求处理服务器不变,也就是新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代

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

一致性hash的特性

单调性(Monotonicity),单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理,又有新的服务器加入到系统中时候,应保证原有的请求可以被映射到原有的或者新的服务器中去,而不会被映射到原来的其它服务器上去。 这个通过上面新增服务器ip5可以证明,新增ip5后,原来被ip1处理的user6现在还是被ip1处理,原来被ip1处理的user5现在被新增的ip5处理。

增加新的节点,原有请求只会映射到原来的或者新的服务器上,不会映射到原来其他的服务器上

分散性(Spread):分布式环境中,客户端请求时候可能不知道所有服务器的存在,可能只知道其中一部分服务器,在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环,那么可能会导致,同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的,因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性hash具有很低的分散性

什么是分散性

在分布式环境中,客户端请求时可能不知道所有服务器的存在,只知道一部分服务器的存在,如果多个客户端都把部分服务器作为完整的hash环,可能导致相同的请求被映射到不同的服务器上,分散性是指以上情况发生的严重程度。

为什么一致性hash可以降低分散性

因为一致性hash的取模运算,是对 2^32-1 取模,不是对服务器的数量取模,所以一致性hash保证相同请求的映射地址都是一样的,和服务器的数量没关系。这样只要不同的客户端都能知道到存储该数据的服务器,都可以准确的找到该服务器,不用考虑客户端知道的服务器的数量。

一致性hash只要不同的客户端都能知道存储该请求数据的服务器存在,就可以得到正确的服务器地址。而普通的hash算法在知道存储该请求数据的服务器存在的情况下,hash运算之后,得到的可能也不是这个服务器地址

比如A客户端识别到编号为1,2,3的三台服务器,一致性hash地址分别是100,200,300。 B客户端识别到编号为2,3,4三台服务器,一致性hash地址分别是200,300,400。 A,B请求的数据做一致性hash运算都是160,做对服务器数量的hash运算都是2。 这么来看,A和B的请求采用一致性hash,定位到的服务器都是编号为2的服务器。 如果采用对服务器数量进行hash计算,定位到的服务器分别是2和3,造成不一致。

平衡性(Balance):平衡性也就是说负载均衡,是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求,但是不能保证每个服务器处理的请求的数量大致相同,如下图

https://gitee.com/lienhui68/picStore/raw/master/null/20200731110352.png

服务器ip1,ip2,ip3经过hash后落到了一致性hash环上,从图中hash值分布可知ip1会负责处理大概80%的请求,而ip2和ip3则只会负责处理大概20%的请求,虽然三个机器都在处理请求,但是明显每个机器的负载不均衡,这样称为一致性hash的倾斜,虚拟节点的出现就是为了解决这个问题。

虚拟节点

当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题,一个解决方法是多加机器,但是加机器是有成本的,那么就加虚拟节点,假设增加虚拟节点之前

https://gitee.com/lienhui68/picStore/raw/master/null/20200731120558.png

可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

https://gitee.com/lienhui68/picStore/raw/master/null/20200731120431.png

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

均匀一致性hash

上节我们使用虚拟节点后的图看起来比较均衡,但是如果生成虚拟节点的算法不够好很可能会得到下面的环:

https://gitee.com/lienhui68/picStore/raw/master/null/20200731110612.png

可知每个服务节点引入1个虚拟节点后,情况相比没有引入前均衡性有所改善,但是并不均衡。均衡的一致性hash应该是如下图:

https://gitee.com/lienhui68/picStore/raw/master/null/20200731110632.png

均匀一致性hash的目标是如果服务器有N台,客户端的hash值有M个,那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡

小结

在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。上文中,我们一步步分析了什么是一致性Hash算法,主要是考虑到分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来的情况,如何保证当系统的节点数目发生变化的时候,我们的系统仍然能够对外提供良好的服务,这是值得考虑的!

参考

深入浅出一致性Hash原理

解决Hash冲突四种方法

面试必备:什么是一致性Hash算法?