前言

互联网服务的后端使用集群来实现海量的服务请求，为了让集群中的节点均匀的处理服务请求，要用到负载均衡技术。
如果做到负载均衡，就达到了控制系统流量的目的。除了保证服务流量的合理分配，还能控制流量走向。

一、理论算法

1.1基本轮询

轮询就是根据后端有多少个服务节点要分配，按照顺序进行轮流分配，分配完最后一个节点后再轮流回到第一个节点进行分配。

缺点：后端不同节点的处理能力可能不同，简单的轮询可能会导致真正处理能力强的节点并没有完全发挥处理能力。
简单示例：比如后端只有两个服务器，其中一个内存和CPU配置很高，另一个很低，那么使用基本轮询的话，配置高的服务器无法完全发挥其作用。

图示：

伪代码：

// 返回值为服务器的序号，可以根据序号找到服务器的IP地址并转发
// 参数serverNum表示后端服务器的总数量
int RobinSelect(const int serverNum)
{
	static int curServer = 0;
	if (curServer == serverNum)
	{
		curServer = 0;
	}
	return curServer++;
}

1.2 加权轮询

加权轮询是对基本轮询的补充。是指给后端的每个节点都赋予权重，分配请求时，按照权重来决定轮询的个数。按照权重的总和来轮询，再根据每个权重所属的服务节点来决定将请求分配给哪个节点。

简单理解：权重高的节点，被请求次数增加；权重小的节点，被请求次数少。

图示：

伪代码：

// weight数组表示每个server的权重
// 返回分配到的服务器序号，从0开始
int weightRobin(int serverNum, int weight[])
{
	static int curSum = 0;
	static int curServerIndex = 0;
	++curSum;
	while (curSum > weight[curServerIndex])
	{
		curServerIndex += 1;
		curServerIndex %= serverNum;
		curSum = 1;
	}
return curServerIndex;
}

1.3 随机访问

随机访问也可以使用权重。具体做法是先计算全部权重的综合，每次“随机”一个小于或等于总和的数字。每次随机后，寻找随机的值落在哪个节点的权重上面。

但如果选区的随机算法不够随机，则会导致后端的请求不均匀。

图示：

伪代码：

int RandSelect(int serverNum)
{
	// getRand()返回[0,serverNum)之间整数的随机数
	int serverId = getRand(0, serverNum);
	return serverId;
}

1.4 源地址Hash

源地址Hash是根据客户端的IP地址，通过Hash函数的运算把IP地址转换为一个固定的数字。根据“Hash”后的数字，对服务器列表进行取模运算，得到服务器的序号。

优点：同一个IP地址所选择的服务器总是相同的。服务器本地缓存数据，对于有状态的服务来说，每次访问都会命中缓存。

图示：

伪代码：

int HashIPSelect(const string& IP, int serverNum)
{
	// 把源IP地址进行Hash运算，Hash函数可以根据业务特点选择
	int hash = getHashCode(IP);
	return hash % serverNum;
}

1.5 最小连接数

最小连接数算法会根据后端服务器当前连接情况来选择连接数量最小的服务器进行连接。从服务方的角度来说，每次都会选择有足够资源的服务器进行连接。

和轮询类似，除了最小连接数，还有加权最小连接数，保证能力强的服务器能够连接更多的客户端。

图示：

1.6 映射分配

无状态服务器可以采用轮询或随机算法，但有些服务是有状态的，例如一些存储或具有缓存的服务。
具有固定的Key的请求要落到固定的节点上，这时就要通过固定的静态分配来均衡分配请求。

1. 注册路由表
   建立路由表，存储的项目是Key和侯丹节点的IP地址，表示某个Key要落到后端哪个IP地址上。这种方法要求了解Key的数量和需要的后端资源。通常用于缓存或固定存储，每个节点Key的数量不能大于存储的容量。

   实际操作：
   1） 建立一个表格，存储Key的范围和对应的节点。例如：对于号码类的存储，存储的是各个区间段对应的IP地址。
   2） 把号码压缩，分成小的区间段。例如，100000个号码作为一个uint，然后对uint采用建立表格的方式进行路由。

2. 计算路由
   可以根据Key的值和后端节点的总数来计算Key落在哪个节点。在Nginx中可以根据IP地址进行Hash运算，然后用Key的值“模”后端Server的数量值，得到要服务的后端Server的IP地址，让固定的IP地址的请求总是被反向代理到对应的后端。

计算路由的好处是简单，只要保持后端节点数量不变即可，缺点是如果后端节点数量更新，则会增加缓存失效的比例。

1.7 一致性Hash

维基百科定义：

Consistent hashing is a special kind of hashing such that when a hash table is resized,
only K/n keys need to be remapped on average, where K is the number of keys, and n is
the number of slots. In contrast, in most traditional hash tables, a change in the number of
array slots causes nearly all keys tobe remapped because the mapping between the keys
and the slots is defined by a modular operation.

当哈希表更新节点数量时，只有K/n的关键字位置有变化，其他关键字的位置的映射关系不变。与一致性hash算法相比，其他算法的节点个数n变化后，更多的key关键字和节点的映射会发生变化。

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

一致性哈希算法详解

前提：
每个请求的key的范围为 [0, 2^32)，一共有k个Key；一共有n个节点，每个节点对应一个服务器。

1. 一致性哈希算法将整个哈希值空间理解成一个环，取值范围是0 ~ 2^32 - 1，共4G的整数空间（unsigned int）。

2. 将所有服务器进行哈希，最终落在这个一致性哈希环上。假设有A， B， C三台服务器，经过哈希后，位置为：

3. 进行负载时，先哈希输入值得到一致性哈希环上的一个哈希值，然后沿着顺时针，遇到的第一台服务器，就是最终负载到的服务器。如图：1号请求顺时针走，负载到A服务器上；2，3号请求负载到C服务器上；4号请求负载到B服务器上。

4. 容错性和可扩展性：有节点宕机了或增加新节点，都不会导致大量的哈希重定位。

如图，A节点挂了，本应该在B, C节点的请求仍然在相应的节点上，而如果是普通哈希的话，会因为节点个数的变化，导致大量请求负载到其他节点上。

如图，新增加一个节点D，那么只影响D节点逆时针方向到前一个节点之间的请求，甚至如果落到有些地方，什么都不影响。

5. 改进：增加虚拟节点

实际应用中会遇到问题：当节点数量（n）太少时，会导致n个节点所管辖的区间并不均匀。
那么n的数量太少，增加n的数量不行吗？
当然可以成倍的增加n的数量，可行的方法是：将一个实际的（物理）节点扩充为M倍的虚拟节点（M可以是100，150，200等），先查找每个Key属于哪个虚拟节点，再查看该虚拟节点属于哪个物理节点。

由于众多虚拟节点的引入，使得每个物理节点被分配到的Key的数量差距变小。
如图，增加节点A和节点B的虚拟节点后，把区间分得更细小，使每个物理节点被分配到的Key的数量更均匀。还可以通过设置权值，让不同处理能力的物理节点处理不同量级的Key。

一致性哈希代码实现

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
using namespace std;
#include "md5.h"

using uint = unsigned int;

// 前置声明
class PhysicalHost;

// 虚拟节点
class VirtualHost
{
public:
	VirtualHost(string ip, PhysicalHost* p)
		: ip_(ip)
		, physicalHost_(p)
	{
		md5_ = getMD5(ip_.c_str());
	}

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

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

	uint getMD5_() const
	{
		return md5_;
	}

	const PhysicalHost* getPhysicalHost() const
	{
		return physicalHost_;
	}
private:
	string ip_;					// 虚拟节点IP地址
	PhysicalHost* physicalHost_;	// 虚拟节点隶属的物理节点
	uint md5_;					// 虚拟节点在一致性哈希环上的位置
};

// 物理节点
class PhysicalHost
{
public:
	PhysicalHost(string ip, int vnumber)	// IP和虚拟节点个数
		: ip_(ip)
	{
		for (int i = 0; i < vnumber; ++i)
		{
			// 虚拟节点需要一个IP，和对应的物理节点
			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(PhysicalHost& host)
	{
		// 获取物理主机所有的虚拟节点列表
		auto list_ = host.getVirtualHosts();
		for (auto host : list_)
		{
			hashCircle_.insert(host);
		}
	}

	// 在一致性哈希环上删除物理主机的虚拟节点
	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();
			}
		}

		// 映射从0开始遇见的第一个虚拟节点
		return hashCircle_.begin()->getPhysicalHost()->getIP();
	}

private:
	set<VirtualHost> hashCircle_;	// 一致性哈希环
};

void showConsistentHash(ConsistentHash& chash);

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

	ConsistentHash chash;
	chash.addHost(host1);
	chash.addHost(host2);
	chash.addHost(host3);

	showConsistentHash(chash);

	// 模拟故障
	chash.delHost(host1);

	showConsistentHash(chash);

	return 0;
}

void showConsistentHash(ConsistentHash& chash)
{
	list<string> iplists{
		"192.168.1.12",
		"192.168.1.13",
		"192.168.1.23",
		"192.168.1.34",
		"192.168.1.25",
		"192.168.1.123",
		"192.168.1.54",
		"192.168.1.45",
		"192.168.1.67",
		"192.168.1.78",
		"192.168.1.89",
		"192.168.1.90"
	};

	map<string, list<string> > logMap_;
	for (auto clientip : iplists)
	{
		string host = chash.getHost(clientip);
		logMap_[host].emplace_back(clientip);
	}

	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;
}

这是三个节点的信息

模拟host1有故障：
那么之前在host1的请求就负载到了其他节点上。

一致性哈希算法总结

经过测试后，可以看出一致性哈希在节点失效后，对于整个后端系统的冲击力是最小的。加入虚拟节点后，优点也特别明显。但在实际应用中，一致性哈希算法还是有一些需要注意的地方。

1. 加入虚拟节点

能够解决分布不均的问题，但如何加入虚拟节点也是有技巧的。在加入虚拟节点时要利用搜索算法进行检测，保证每个物理节点的区间不能差异太大。必要时要回溯、剪枝，或者使用启发性搜索。最后检测所有虚拟节点负责的范围是否在允许的误差范围之内。

2. 节点配置同步

一个物理节点对应多少个虚拟节点并没有一个通用说法，有100个，150个等等。每当更新节点信息时，要保证更新的数据及时准备地同步到其他节点，而且要有检查功能。

二、常用组件

2.1 DNS（待补充。。。）

为了扩展侯丹的服务能力，我们会在一个域名下配置多个IP地址。在DNS上可以配置访问策略，按照运营商、地域进行优先选择，然后按照随机的方式分配被访问的节点。

2.2 Nginx

在HTTP服务器Nginx上也有实现负载均衡功能，只需简单的配置，就能够对后端服务进行负载均衡转发。
Nginx支持轮询、最小连接数和ip-hash三种负载均衡。

轮询：
如图，是在集群聊天服务器里配置Nginx基于TCP的负载均衡。
配置了两台服务器，依次把8000端口的请求转发给这两个服务器。weight是权重，默认是1，如果想换成按权重比的轮询，可根据服务器性能等方面配置权重。

最小连接数：
只需要加上least_conn即可。

	upstream myapp1 {
		least_conn;
		server srv1.example.com;
		server srv2.example.com;
		server srv3.example.com;
	}

源地址哈希：
Nginx根据客户端源地址进行哈希运算后转发，保证相同客户端的请求都能落到同一后端的server上。

	upstream myapp1 {
		ip_hash;
		server srv1.example.com;
		server srv2.example.com;
		server srv3.example.com;
	}

2.3 LVS