哈希算法的衍化

发表于 分类于

哈希算法的变化,普通哈希,割环一致性哈希,跳跃一致性哈希,Maglev一致性

Hash算法

1
2
3
4
5
将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值
哈希值是一段数据唯一且极其紧凑的数值表示形式

思考一下,如果数据存储在分布式机器中,普通Hash还有效果么
数据是根据Key值对节点数取模分布的,当节点注册或注销集群,数据的映射就失效了

一致性Hash算法(割环)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
平衡性
    哈希的结果尽可能分布到所有的缓冲中,使所有的缓冲空间都得到利用
单调性
    当已有内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统
    那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中
分散性
    分布式环境,终端看不到所有缓冲,会导致哈希结果不一致,相同的内容被不同的终端映射到不同的缓冲区中
    好的哈希算法应尽量避免不一致的情况,即降低分散性
负载
    和分散性一样,不同的终端会将相同的内容映射到不同的缓冲区,
    对于特定的缓冲区,也可能被不同的用户映射为不同的内容
    也应该避免
平滑性
    缓存服务器数目与缓存对象的平滑改变是一致的

一致性Hash将整个Hash值空间组织成一个虚拟圆环,整个空间按顺时针方向组织
将各个服务器进行Hash(服务器IP/主机名),确定每台机器在哈希环上的位置
    如: A->B->C->D->A
数据按Key使用同样的Hash计算出Hash值,确定在环上的位置
数据沿着顺时针,第一台遇到的服务器就是被定位到的服务器

容错性
    假如C宕机,A,B不会受到影响,原本C的数据会被分配给D
    如:A->B->{-C}->D->A
扩展性
    假如加入一个节点E在AB之间,对A,C,D没有影响,原本B的数据会分配一部分给E
    如:A->{+E}->B->C->D->A
    
虚拟节点
    当节点数过少时,必定会出现一个节点会被放置大量数据
    一致性Hash引入虚拟节点机制,针对每一个服务节点计算多个哈希,每个计算节点都放置一个虚拟节点
    类似于服务器IP/主机名后添加编号的方式进行哈希
    虽然数据仍然在节点上,但是节点服务器内数据是分布均匀的
    如:A#1->A#2->A#3->B#1->B#2->B#3->A#1

跳跃一致性Hash算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
Google原论文中C++代码实现
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = -1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}
函数JumpConsistentHash是一个一致性哈希函数,将一个key一致性地映射到给定几个节点中的一个上
输入key和节点数量num_buckets,输出映射到的节点编号

推导
一致性哈希函数为fun(k,n),将K个数据k,映射到n个节点上
n = 1, fun(k, 1) = 0,都映射到节点0上
n = 2,每个节点映射K / 2个数据
...
n = n + 1,每个节点映射K / (n + 1)个数据
思考问题,均匀分配我们知道了,那么,新增或删除节点时,哪些数据保持不变呢,哪些需要重分配呢

针对上面的问题,新增节点时Google采取一个随机数决定数据k需不需要跳到新节点中去
对每一个k,利用这个k做随机数种子,得到一个关于k的随机序列
为了保证节点数由j变为j+1时,有1/(j+1)占比的数据会跳到新节点
采取条件C:random.next() < 1 / (j + 1)则跳,否则留下
伪代码:
int ch(int k, int n) {
    random.seed(k);
    int b = 0;  // This will track ch(k, j+1).
    for (int j = 1; j < n; j++) {
        if (random.next() < 1.0/(j+1)) b = j;
    }
    return b;
}

注意:
k一旦确定,随机序列就确定了,每次计算都会重新初始化随机数种子
这样for循环一直在遍历一个确定的序列而已
也就是k确定,给定一个n时,k的映射结果是唯一确定的,也就是一致的

优化:
上面代码可以看出,其实需要进行重分配的数据只有K/(j+1)
意味着只有少数的数据选择分配,for是一步一步来,产生加大步子,实现跳跃
int ch(int k, int n) {
  random.seed(k);
  int b = 0, j = 0;
  while (j < n) {
    if (random.next() < (b+1.0)/j) b = j;
    # 加大步子
    j += continuous_stays;
  }
  return b;
}
r=random.next()要满足(b+1.0)/j,那么j<(b+1)/r
也就是j最多移动到(b+1)/r才至于漏掉迭代,向下取整即为floor((b+1)/r)
int ch(int k, int n) {
  random.seed(k);
  int b = -1, j = 0;
  while (j < n) {
    b = j;
    r = random.next();
    j = floor((b+1) / r);
  }
  return b;
}

缺点:
从上面的推导和代码就可以看出来
1.节点编号从0开始,没法自定义
2.只能在尾部增删节点,在非尾部增删节点没有任何使用跳跃一致性算法的意义

Maglev一致性哈希算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
同样来自Google
要求映射均匀,尽量将节点变化时的映射变化降到最小,也就是避免全局重新映射

思路:
建立一个长度为M的节点查找表entry(Lookup Table),对k哈希取余,映射到表中的一个节点
i=hash(k)%M,节点为entry[i]

过程:
新建一张大小为M的空表entry作为查找表,再为每个节点生成一个偏好序列
每个节点轮流填充查找表,将偏好序列中的数字当做查找表的位置,将节点编号填充到目标位置
填充位置被占用,顺延到该序列编号的下一个填
后面我们会了解到偏好序列怎么产生
如,3个节点,查找表大小为7:
偏好序列
N0: 3,0,4,1,5,2,6
N1: 0,2,4,6,1,3,5
N2: 3,4,5,6,0,1,2
怎么填查找表entry呢
1.N0偏好序列为3,entry[3] = N0
2.N1偏好序列为0,entry[0] = N1
3.N2偏好序列为3,位置被占用,下一个偏好为4,entry[4] = N2
---下面开始简写
4.N0,0->4->1,entry[1] = N0
5.N1,2,entry[2] = N1
6.N2,4->5,entry[5] = N2
7.N0,5->2->6,entry[6] = N0
8.查找表填充满了
entry: N1,N0,N1,N0,N2,N2,N0

偏好序列如何产生
使用两个无关的哈希函数h1,h2,对节点IP/主机名b做哈希
offset=h1(b)%M
skip=h2(b)%(M-1)+1
依次计算出偏好序列permutation中的所有数字
permutation[j]=(offset + j*skip)%M

ps:(=-=学到这里我突然亿点点懵逼)
上面的论文提供的偏好序列已知的公式,怎么推出x,y
3 = x % 7
0 = (x +y) % 7
4 = (x + 2y) % 7
1 = (x + 3y) % 7
5 = (x + 4y) % 7
2 = (x + 5y) % 7
6 = (x + 6y) % 7

根据上面的知识,衍生出的问题,假如你生成的偏好序列,填充完了之后发现查找表还没填充满
有一个为空,咋办?填充一个占比小的,如果已经均匀分配则随机分配一个

增加删除节点
一样对应上面的偏好序列,然后重新分配一下,可以发现发生干扰的填充
增删操作必然会导致填充干扰,目的是将干扰降到最低
干扰: 查找表发生重新填充
联动干扰: 未删除或者原有节点之间产生的重新填充
如: N0,N1,N2删除N1,原先entry[0]是N0的被N2替换,则是联动干扰