一致性HASH算法一览

南风 2020年10月30日 87次浏览

一、HASH算法

 散列表又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。

1、散列函数

 散列表是以key-value形式存储的数据结构,它通过关键码值(key)来映射到表中的一个位置来访问记录(value),以便加快查找速度,这种映射关系就是散列函数。
常用的构造散列函数的方法:
  1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b,其中a和b为常数(这种散列函数叫做自身函数)
  2. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相 同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会 明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
  3. 平方取中法:取关键字平方后的中间几位作为散列地址。
  4. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。
  5. 随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。
  6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。
 

2、HASH算法种类

日常常用的经典HASH算法有以下几种:

  • (1) MD4
    MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。
  • (2) MD5
    MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好
  • (3) SHA-1 及其他
    SHA1是由NIST NSA设计为同DSA一起使用的,它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

3、HASH算法处理冲突方法

HASH算法通过不同的散列函数映射到值,其中必定存在冲突,假设你有100个的用户信息需要存储到HASH表中,你选用一个散列函数作为映射位置计算,假如你的存储桶有120个,使用求余函数(mod)作为散列函数,此时可能存在两个或多个用户信息映射到同一个桶里面的情景,这就是HASH算法所说的冲突,那么处理冲突的方法有几种呢?

  • 1、拉链法(separate chaining)
    拉链法就是当通过散列函数计算到已经存在值的桶位置时,用一个建表存储相同桶位置value,查询时先查到桶位置,获取链表再遍历得到值。
    JAVA的HashMap目前就是这个实现的,当链表过长时会自动转化成红黑树。
    拉链法
  • 2、线性探测法(linear probing)
    开放地址哈希表中最简单的方法叫做“线性探测”法:当碰撞发生时(当一个键的Hash值已经被另一个不同的键占用),我们直接检测哈希表中的下一个位置(将索引值加 1)。这样的线性探测可能会产生三种结果:
    a)命中,该位置的键和被查找的键相同;
    b)未命中,键为空(该位置没有键)
    c)继续查找,该位置的键和被查找的键不同。

我们用Hash函数找到键在数组中的索引,检查其中的键和被查找的键是否相同。如果不同则继续查找(将索引增大,到达数组结尾时折回数组的开头),直到找到该键或者遇到一个空元素。

  • 3、双散列函数法
     伪随机探查和二次探查都能消除基本聚集——即基地址不同的关键码,其探查序列的某些段重叠在一起——的问题。然而,如果两个关键码散列到同一个基地址,那么采用这两种方法还是得到同样的探查序列,仍然会产生聚集。这是因为伪随机探查和二次探查产生的探查序列只是基地址的函数,而不是原来关键码值的函数。这个问题称为二级聚集( secondary clustering )。
     为了避免二级聚集,我们需要使得探查序列是原来关键码值的函数,而不是基位置的函数。双散列探查法利用第二个散列函数作为常数,每次跳过常数项,做线性探查。

二、一致性HASH算法

一致性Hash算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot Spot)问题,初衷和CARP十分相似。一致性Hash修正了CARP使用的简单哈希算法带来的问题,使得分布式哈希(DHT)可以在P2P环境中真正得到应用。

一致性Hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:

1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布在所有的缓冲(Cache)中去,这样可以使得所有的缓冲空间得到利用。很多哈希算法都能够满足这一条件。

2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应该能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会映射到旧的缓冲集合中的其他缓冲区。

3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上去,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应该能够尽量避免不一致的情况发生,也就是尽量降低分散性。

4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射到不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

一致性HASH算法结构图

一致性HASH算法的基本思想是:将节点通过HASH算法散列在2的32次方的环上,当数据进来时也是做同样的HASH散列,此时应该顺时针选择离数据HASH位置最近的第一个节点

三、一致性HASH算法应用场景

一致性HASH算法多用于分布式节点选择的场景。如:

  • 1、memcached集群访问路由算法
  • 2、Redis分布式集群访问路由算法
  • 3、数据库分库分表散列算法
  • ...

四、什么解决一致性HASH算法分布数据不均匀问题?

当节点较少的情况下,必然会出现节点分布不均匀,导致访问节点HASH结果不均匀,如下图:
节点太少引发的问题
此时,我们应该增加虚拟节点,均匀分布,划定某几个连续的虚拟节点与真实的节点一一对应。

依我而言,我认为一致性HASH算法解决的最大问题是在增加或者减少节点的时候,数据最少迁移量。

(全文完)