一致性哈希算法【图解理论 + 代码实现】

📖1. 普通哈希算法存在的问题

在介绍一致性哈希算法前，我们先来看两个场景：

场景一：

现在，假如有三个用户的请求，即三个ip地址，需要被负载均衡到这三台服务器上去，并且，我们使用这样的哈希算法，能够保证同一个客户端永远被映射到一台指定的server上，这样可以有效解决会话共享问题.

简单来说，就是比如现在我们来了一个用户请求，假如它叫张三，并被负载均衡到2号服务器上，那么2号服务器就保存了他的登录状态信息，但是如果下一次张三发出请求，他又被映射到了一号服务器上，但一号服务器上没有保存有关张三的会话信息，那么1号服务器怎么知道张三的登录状态呢？又怎么正确的对张三的请求做出处理呢？

所以，我们是需要让同一客户端每次被映射到一台指定的server上.

假如，现在有张三、李四、王五三个客户端，他们每次都被映射到一台指定的server上，现在，如果3号服务器突然挂掉：

场景二：

例如，服务端需要增删查看数据，如果服务端直接去数据库中查找，效率太低，所以我们需要将一些热点数据先缓存起来，以便下次查找时提高效率，假设现在我们以用户id作为key，用户信息作为value，如果第一次去查找时没找到，那就去数据库中查找，然后再将此次的查找结果保存在缓存中，以便以后再次查找时快速读取，如果找到，那么服务端直接从缓存中拿到数据并处理，并最终返回给客户端.

所以，综合上述的两个场景可以看出，普通的哈希算法是存在许多问题的，所以我们需要引入一致性哈希算法.

📖2. 一致性哈希算法概念

一致性哈希算法是分布式系统负载均衡的首选算法.

服务器负载均衡环境下，可以配置的负载均衡算法有很多种，比如：轮询算法，哈希算法，权重比算法，最少连接算法.

一个良好的分布式哈希方案应该具有良好的单调性，即服务器节点的增减不会造成大量哈希的重定位.

什么是一致性哈希算法？

那么还有一个问题：服务器经过一致性哈希处理之后，在哈希环上应该分散一些好，还是集中在一起好？

这种问题也叫哈希环的倾斜.

所以，在一致性哈希算法中，就采用了虚拟节点来解决这个问题：

即对每一台服务器节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称作虚拟节点. 一个实际的物理节点可以对应多个虚拟节点，虚拟节点越多，哈希环上的节点就越多，缓存/客户端被均匀分布的概率就越大，哈希环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射.

落在A1，A2，A3，A4上的节点，均负载到A服务器上，落在B1，B2，B3，B4上的节点，均负载到B服务器上.

📖3. 代码实现

#include
#include
#include
#include
#include
#include"md5.h"

using namespace std;

using uint = unsigned int;

class PhysicalHost;

//虚拟节点
class VirtualHost
{
public:
	VirtualHost(string ip, PhysicalHost* p)
		: ip_(ip)
		, physicalHost_(p)
	{
		//md5算法，用来将ip地址离散到哈希环上
		// 把32位的md5串，处理成unsigned int返回
		//unsigned int getMD5(const char* buf);

		md5_ = getMD5(ip_.c_str());
	}

	bool operator<(const VirtualHost& vhost) const
	{
		return md5_ < vhost.md5_;
	}

	bool operator==(const VirtualHost& vhost) const
	{
		return vhost.ip_ == ip_;
	}

	const PhysicalHost* getPhysicalHost() const
	{
		return physicalHost_;
	}

	uint getmd5() const
	{
		return md5_;
	}
private:
	string ip_; //虚拟节点的ip信息
	uint md5_;  //虚拟节点在哈希环上的位置
	PhysicalHost* physicalHost_;  //该虚拟节点所对应的物理节点
};

//物理节点
class PhysicalHost
{
public:
	PhysicalHost(string ip, int vnumber)
		:ip_(ip)
	{
		//添加虚拟节点
		for (int i = 0; i < vnumber; ++i)
		{
			virtualHosts_.emplace_back(ip_ + "#" + to_string(i), this);
		}
	}

	string getIP() const
	{
		return ip_;
	}

	const list<VirtualHost>& getVirtualHosts() const
	{
		return virtualHosts_;
	}
private:
	string ip_;  //物理机器的ip地址
	list<VirtualHost> virtualHosts_; // 存储物理节点对应的虚拟节点列表
};

//一致性哈希算法实现
class ConsistentHash
{
public:
	//在一致性哈希环上添加物理主机的虚拟节点
	void addHost(const PhysicalHost& host)
	{
		//获取物理主机的所有虚拟节点列表
		auto list = host.getVirtualHosts();
		for (auto vhost : list)
		{
			hashCircle_.insert(vhost);
		}
	}


	//在一致性哈希环上删除物理主机的虚拟节点
	void delHost(PhysicalHost& host)
	{
		auto list = host.getVirtualHosts();
		for (auto host : list)
		{
			auto it = hashCircle_.find(host);
			if (it != hashCircle_.end())
			{
				hashCircle_.erase(it);
			}
		}
	}

	//返回负载的真实物理主机的ip信息
	string getHost(string clientip) const
	{
		uint md5 = getMD5(clientip.c_str());

		for (auto vhost : hashCircle_)
		{
			if (vhost.getmd5() > md5)
			{
				return vhost.getPhysicalHost()->getIP();
			}
		}

		return hashCircle_.begin()->getPhysicalHost()->getIP();
	}
private:
	set<VirtualHost> hashCircle_;  //一致性哈希环
};

void ShowConsistentHash(ConsistentHash& chash)
{
	list<string> iplists ={
		"192.168.1.123",
		"192.168.1.12",
		"192.168.1.13",
		"192.168.1.23",
		"192.168.1.54",
		"192.168.1.89",
		"192.168.1.21",
		"192.168.1.27",
		"192.168.1.49",
		"192.168.1.145",
		"192.168.2.34",
		"192.168.6.78",
		"192.168.2.90",
		"192.168.4.5"
	};

	map<string, list<string>> logMap;

	for (auto client : iplists)
	{
		string host = chash.getHost(client);
		logMap[host].emplace_back(client);
	}

	for (auto pair : logMap)
	{
		cout << "物理主机：" << pair.first << endl;
		cout << "负载客户端的数量：" << pair.second.size() << endl;

		for (auto ip : pair.second)
		{
			cout << ip << endl;
		}

		cout << "------------------------" << endl;
	}

	cout << endl;
}

int main()
{
	PhysicalHost host1("10.117.124.10", 150);
	PhysicalHost host2("10.117.124.20", 150);
	PhysicalHost host3("10.117.124.30", 150);

	//在一致性哈希环上添加三台物理主机
	ConsistentHash chash;
	chash.addHost(host1);
	chash.addHost(host2);
	chash.addHost(host3);

	ShowConsistentHash(chash);

	//host1挂掉
	chash.delHost(host1);

	ShowConsistentHash(chash);

	return 0;
}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194