一致性HASH的原理和实现

文章目录
  1. 1. HASH Function & HASH Table
  2. 2. 一致性HASH
    1. 2.1 单调性
    2. 2.2 平衡性(数据倾斜问题)
    3. 2.3 实现
  3. 参考

一致性HASH的概念在我们的工作中经常会用到,例如对于集群中一些有状态的服务,我们希望对于同一个玩家的请求总是由固定的服务器来处理,且不会因为该服务的扩缩容而导致请求失效,即转发到了其他服务器处理。那么为什么一致性HASH可以保证被映射到某个服务的请求持久有效呢?

一致性HASH(Consistent Hashing)(维基)定义:一种特殊的HASH,在HASH表大小发生变化时,只有$K/n$个key需要进行重新映射(K是总key的个数,n是节点个数)。在介绍一致性HASH之前先回顾一下HASH的相关知识。

1. HASH Function & HASH Table

HASH函数是指可以将任意长度数据映射到固定长度的值的函数的统称。HASH函数需要具有以下三个功能:

  • 将可变长度的key转换成固定长度的value,例如按word进行奇偶校验来对key进行折叠,像ADD/XOR操作。
  • 对输入的key进行置乱来使计算的value结果能够均匀分布
  • 将产生的HASH value映射到固定的table中。这是HASH table的要求。

HASH函数有以下几点基本特性:

  • 相同的key,生成的HASH value一定是相同的;
  • 不同的key,生成的HASH value有可能是相同的;
  • 不同的HASH value,对应的key一定是不同的;

一个好的HASH函数应该保证以下基本两点:

  • HASH value的计算过程要很快;
  • HASH value冲突的概率要小;

这两点在实际应用过程中是很重要的,就像平时看到的口号:”又快又好!”。

HASH表是通过HASH函数的返回值用来进行索引一个固定大小的table。它是HASH函数的一个主要应用。C++中提供的unordered_map就是HASH表的一个实现。

通过HASH函数来索引HASH表的过程称之为hashing即哈希法或散列法。hashing的目的就是通过HASH表将key/value对进行分散存储,以提高检索效率。对于一个给定的key,计算其索引的方式可以表示如下:

1
2
3
4
index = f(key, array_size)
//经常分为如下两步
hash_value = hashfunc(key)
index = hash_value % array_size

由上述HASH index的计算过程可以知道,在某个节点故障或者添加节点的时候,由于array_size发生变化,可能会导致所有key最终生成的index全部都发生变化,导致节点的映射发生变化。这对于一些分布式的服务中缓存的cache会失效,因为之前的请求可能会被转发到其他server,这会使系统的性能带来急剧的下降,这是我们不希望看到的。如下图所示ServerN的故障就会导致之前的key的映射关系发生变化:

ServerN故障后:

那有没有一个好的映射方法,能够保证在某个节点发生故障时,只会影响当前节点的映射关系,而不会影响到其他的节点的映射呢?

2. 一致性HASH

那就是一致性哈希(consistent hashing),这个算法是MIT的Karger在1997年发表的论文(Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web )中为了解决分布式缓存而设计的。一致性哈希的核心思想就是将每个服务节点与一个HASH值区间关联起来。然后一致性哈希会将每个请求对象通过同样的HASH将其映射到某个HASH值区间上,从而关联到对应的服务节点。当添加或删除节点时,变动的只有对应节点HASH值区间的对象需要变动,即只有$K/n$个key需要进行重新映射(K是总key的个数,n是节点个数)。

一致性HASH的四个重要特性如下:

  • Balance:平衡性,hash函数对于输入items能够均匀的映射到每个bucket。
  • Monotonicity:单调性,某个item映射到bucket A1,此时如果新加入了一个bucket A3,那么此item的映射关系可能从bucket A映射到bucket A3,但绝不会映射到旧的bucket A2中。
  • Spread:分散性,分布式的系统中,每个终端可能看到的bucket集群是不一致的,所以最终会导致相同的items被映射到不同的bucket中。这种情况是要避免,分散性要越低越好。
  • Load:负载,和Spread概念相似,只不过是用来描述bucket中被不同的用户映射为不同的item。负载也是越低越好。

2.1 单调性

Karger提出的一致性HASH算法的思想前面也说了就是:将每个服务节点与一个HASH值区间关联起来,为了能够让所有请求都能映射到一个服务节点,这就要求所有服务节点生成的HASH值区间必须是连续且是收尾相连的,其实就是一个环。Karger在其后的一片论文(Web Caching with Consistent Hashing)中阐述了一致性HASH的一种简单实现:采用的HASH函数将string的输入映射到一个数字区间[0, M],可以把该区间认为是一个单位圆,然后将所有服务节点都映射到圆上的某个点,然后将每个请求通过同样的HASH映射到该圆上的某个点,该请求item映射到圆上的点,以顺时针找到与之最近的服务节点。

如下图:三个服务节点S1,S2,S3通过HASH映射到圆上的三个点:

三个请求K1,K2,K3通过同样的HASH函数映射到圆上的三个点,然后通过逆时针找到最近的服务节点,如下所示:

上述两步一般的HASH算法都可以做到,那一致性hash的是为了解决什么呢?就是为了解决在HASH表大小发生变化时,只有$K/n$个key需要进行重新映射,即保证在某个节点发生故障时,只会影响当前节点的映射关系,而不会影响到其他的节点的映射!如下图,当S3服务节点出现故障时,请求K3会被转发到S2上:

同样对于新加入的服务节点S4让原有映射到S3的请求K3重新映射到了S4,对于新加入的节点只影响到了原有映射到S3部分区间,这就是一致性HASH的核心:单调性

2.2 平衡性(数据倾斜问题)

我们知道在HASH函数的应用中,对于HASH函数好坏判断的一个重要指标就是平衡性。很多比较常见的HASH函数:BKDR, DJB,FNV,CRC32其实都相对好的平衡性,同样一致性HASH平衡性也至关重要,既然很多HASH函数能够提供很好的平衡性,那么是不是一致性HASH就直接按上述的实现就可以了呢?

我们看上图中只有三个服务节点的情况下:假设三个请求被均匀的映射到了三个服务节点,在S3挂了之后,K3就会被映射到S2,你会发现有什么问题?本来三个服务节点各分担了33%的流量,但当S3挂了后,S1还是分担了33%的流量,而S2则分担了66%的流量

一致性HASH为了解决在服务节点少的情况下且遇到故障时不能平衡性的问题,作者Karger在论文中提出了:一致性HASH需要将C个服务节点拷贝k份,也就是大家说的构建虚拟节点。将每个节点拷贝100份,生成的HASH圆环简要信息如下:此时如果S3挂了,基本上可以保证S1和S2各承担50%的流量,保证了平衡性。

此时如果S3挂了,S3所有的虚拟节点都会失效,但是可以保证S1和S2各承担50%的流量,保证了平衡性。这在分布式系统设计中是很关键的,这样可以最大程度的减少由于部分节点失效所带来的系统不稳定性

但这里拷贝多少份呢?当建立的虚拟节点过多时就会影响一致性HASH的查找性能。

2.3 实现

下面一致性HASH的实现,主要有三个接口:

  • AddNode:添加服务节点;添加服务节点时都自动进行虚拟节点的创建;
  • DelNode:删除服务节点;
  • GetNode:根据请求数据获取映射的服务节点;
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
#include <string>
#include <map>
#include <cstdint>
#include <sstream>
#include <iostream>

template<typename T>
std::string ToString(const T & t)
{
std::ostringstream os;
os<<t;
return os.str();
}

template<typename Node, typename Data, typename Hash>
class ConsistentHash
{
public:
ConsistentHash(uint32_t _virtual_nodes = 100)
: hash_(Hash()), virtual_nodes_(_virtual_nodes)
{}

void AddNode(const Node & node)
{
std::string str_node = ToString(node);
for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
{
std::string key = str_node + "_" + ToString(loop_i);
uint64_t hash_value = hash_(key);
unit_circle_.insert(std::make_pair(hash_value, node));
}
}

void DelNode(const Node & node)
{
std::string str_node = ToString(node);
for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
{
std::string key = str_node + "_" + ToString(loop_i);
uint64_t hash_value = hash_(key);
unit_circle_.erase(hash_value);
}
}

const Node * GetNode(const Data & data) const
{
if(unit_circle_.empty())
return nullptr;

uint64_t hash_value = hash_(ToString(data));
auto itr = unit_circle_.lower_bound(hash_value);
if(itr == unit_circle_.end())
return &unit_circle_.begin()->second;
return &itr->second;
}

private:
std::map<uint64_t, Node> unit_circle_;
uint32_t virtual_nodes_;
Hash hash_;
};

在添加完所以节点后,可以通过计算每个节点对应区域在单位圆上的占比来统计一致性HASH的分布均匀性,如下计算方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void PrintBalacne() const
{
std::map<uint64_t, uint64_t> distribute_map;

uint64_t last_val = 0;
for(auto & val : unit_circle_)
{
auto itr = unit_circle_.upper_bound(val.first);
if(itr == unit_circle_.end())
distribute_map[val.second] += uint64_t(-1) - val.first + unit_circle_.begin()->first;

distribute_map[val.second] += itr->first - val.first;
}

for(auto & val : distribute_map)
std::cout<<val.first<<":"<<val.second<<":"<<val.second * 1.0 / uint64_t(-1)<<std::endl;
}

下面是通过CityHash进行的测试,主要是为了测试服务节点在某个节点下线后,数据映射均衡性问题:

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
ConsistentHash<uint32_t, uint32_t, CityHasher> consistent_hash;
for(uint32_t loop_i = 1; loop_i <= 5; ++loop_i)
consistent_hash.AddNode(loop_i);

consistent_hash.PrintBalacne();

consistent_hash.DelNode(3);

consistent_hash.PrintBalacne();
}

可以看到添加完5个节点后,整个HASH圆环每个节点的负载基本平衡,

当Node3出现故障下线后,其余4个节点也均衡的分担了Node3的流量。

参考

http://www.burtleburtle.net/bob/hash/doobs.html

https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

https://researchlab.github.io/2017/01/16/consistent-hashing-summary/

https://zhuanlan.zhihu.com/p/34985026

http://www.cs.columbia.edu/~asherman/papers/cachePaper.pdf

http://david.choffnes.com/classes/cs4700sp14/papers/akamai.pdf