负载平衡（英语：load balancing）是一种电子计算机技术，用来在多个计算机（计算机集群）、网络连接、CPU、磁盘驱动器或其他资源中分配负载，以达到优化资源使用、最大化吞吐率、最小化响应时间、同时避免过载的目的。 使用带有负载平衡的多个服务器组件，取代单一的组件，可以通过冗余提高可靠性。负载平衡服务通常是由专用软件和硬件来完成。 主要作用是将大量作业合理地分摊到多个操作单元上进行执行，用于解决互联网架构中的高并发和高可用的问题。
这是[维基百科](负载均衡 - 维基百科，自由的百科全书)对负载均衡的定义。
按照我的理解，负载均衡主要就是为了两个目的：并行处理(A 忙不过来，B 一起上)、防止单点失败(A 忙废了，B 顶上)。分别对应了高并发、高可用的核心诉求。
负载均衡的算法有很多种，我尝试把我的理解表达出来。
陆游老先生曾经曰过：纸上得来终觉浅，绝知此事要躬行。所以，用 C++把它们实现一下。
1. 轮询 Round Robin
轮询，就是将请求逐个分发给后端的服务器，每个服务器都被平等对待。
具体实现，就是把所有的后端服务器放到一个数组里，并用一个变量来保存当前索引。每次过来一个新的请求，把当前索引前进一步，并对数组长度取模。
参考代码如下：
// Load Balance with Round Robin
#pragma once
#include <vector>#include <string>#include <unordered_map>#include <iostream>
class LoadBalanceRoundRobin{public: LoadBalanceRoundRobin() { current = -1; }
~LoadBalanceRoundRobin() { }
bool AddServer(const std::string& srv) { servers.push_back(srv); return true; }
// Simulate a new request bool NextRequest() { if(servers.empty()) { std::cout << "Please add servers first. " << std::endl; return false; }
// Move to next server current = (current + 1) % servers.size(); // Update stats stats[servers[current]]++;
return true; }
void PrintStats() const { std::cout << "Server Hit stats with round robin: "; for(auto x : stats) { std::cout << std::endl; std::cout << x.first << ": " << x.second; } std::cout << std::endl; }
private: // The servers to be balanced std::vector<std::string> servers; // Index of server hit int current; // Stats, key is the server, value is the hit count std::unordered_map<std::string, int> stats; };
复制代码
往这个 LB 添加 5 个服务器，然后发起一百万次请求：
void TestRoundRobin(){ LoadBalanceRoundRobin lb; lb.AddServer("192.168.1.10"); lb.AddServer("192.168.1.11"); lb.AddServer("192.168.1.12"); lb.AddServer("192.168.1.13"); lb.AddServer("192.168.1.14");
for(int i = 0; i < 1000000; i++) { lb.NextRequest(); }
lb.PrintStats();}
复制代码
可以看到，这些请求被均匀的分发给了每个服务器：
Server Hit stats with round robin:192.168.1.14: 200000192.168.1.13: 200000192.168.1.12: 200000192.168.1.11: 200000192.168.1.10: 200000
复制代码
Note 一下，本次内容重点在于试验负载均衡算法，不在于类的设计。所以，后面还会出现好几个相似的类，但我并没有去做任何的继承。实际工程应用的时候，需要考虑抽象、继承问题，以减少代码重复。
2. 加权轮询 Weighted Round Robin
后端的服务器，有些强劲、有些比较弱。可以给强劲的服务器分配较大的权重，给它分发更多的请求。
具体实现跟前面的轮询很像。主要的差别在于，添加后端服务器时，根据权重的数值 N，把对应的服务器添加 N 次到数组里面，这样使得该服务器被轮询到的次数比例，跟它的权重比例一样。
参考代码如下：
// Load Balance with Weighted Round Robin
#pragma once
#include <vector>#include <string>#include <unordered_map>#include <iostream>#include <algorithm>
class LoadBalanceWeightedRoundRobin{public: LoadBalanceWeightedRoundRobin() { current = -1; }
~LoadBalanceWeightedRoundRobin() { }
bool AddServer(const std::string& srv, int weight) { if(weight < 1) { std::cout << "Weight should be equal or greater than 1." << std::endl; return false; }
for(int i = 0; i < weight; i++) { // Add weight times to vector servers.push_back(srv); }
// Shuffle the vector so that servers will be out of order std::random_shuffle(servers.begin(), servers.end()); return true; }
// Simulate a new request bool NextRequest() { if(servers.empty()) { std::cout << "Please add servers first. " << std::endl; return false; }
// Move to next server current = (current + 1) % servers.size(); // Update stats stats[servers[current]]++;
return true; }
void PrintStats() const { std::cout << "Server Hit stats with weighted round robin: "; for(auto x : stats) { std::cout << std::endl; std::cout << x.first << ": " << x.second; } std::cout << std::endl; }
private: // The servers to be balanced std::vector<std::string> servers; // Index of server hit int current; // Stats, key is the server, value is the hit count std::unordered_map<std::string, int> stats; };
复制代码
往这个 LB 添加 5 个服务器，并给与不同的权重，然后发起一百万次请求：
void TestWeightedRoundRobin(){ LoadBalanceWeightedRoundRobin lb; lb.AddServer("192.168.1.10", 1); lb.AddServer("192.168.1.11", 2); lb.AddServer("192.168.1.12", 3); lb.AddServer("192.168.1.13", 4); lb.AddServer("192.168.1.14", 10);
for(int i = 0; i < 1000000; i++) { lb.NextRequest(); }
lb.PrintStats();}
复制代码
可以看到，每个服务器被分发的请求比例，跟它的权重比例是一样的：
Server Hit stats with weighted round robin: 192.168.1.13: 200000192.168.1.10: 50000192.168.1.12: 150000192.168.1.11: 100000192.168.1.14: 500000
复制代码
3. 随机 Random
随机算法也很好理解，每次过来一个请求，随机分发给某一台后端服务器即可。随着请求量的增加，每个后端服务器的请求总数会趋向一致。
参考代码如下：
// Load Balance with Random
#pragma once
#include <vector>#include <string>#include <unordered_map>#include <iostream>
class LoadBalanceRandom{public: LoadBalanceRandom() { }
~LoadBalanceRandom() { }
bool AddServer(const std::string& srv) { servers.push_back(srv); return true; }
// Simulate a new request bool NextRequest() { if(servers.empty()) { std::cout << "Please add servers first. " << std::endl; return false; }
// Pickup a random server int current = rand() % servers.size(); // Update stats stats[servers[current]]++;
return true; }
void PrintStats() const { std::cout << "Server Hit stats with random: "; for(auto x : stats) { std::cout << std::endl; std::cout << x.first << ": " << x.second; } std::cout << std::endl; }
private: // The servers to be balanced std::vector<std::string> servers; // Stats, key is the server, value is the hit count std::unordered_map<std::string, int> stats; };
复制代码
往这个 LB 添加 5 个服务器，然后发起一百万次请求：
void TestRandom(){ LoadBalanceRandom lb; lb.AddServer("192.168.1.10"); lb.AddServer("192.168.1.11"); lb.AddServer("192.168.1.12"); lb.AddServer("192.168.1.13"); lb.AddServer("192.168.1.14");
for(int i = 0; i < 1000000; i++) { lb.NextRequest(); }
lb.PrintStats();}
复制代码
可以看到，这些请求基本上被均匀的分发给了每个服务器：
Server Hit stats with random: 192.168.1.13: 200448192.168.1.10: 199584192.168.1.14: 199799192.168.1.11: 199495192.168.1.12: 200674
复制代码
4. 加权随机 Weighted Random
加权随机与加权轮询的思路类似，给强劲的后端服务器更大的权重(出现次数更多)，让它更容易被随机选中。
具体代码跟随机相比，差别只是在添加后端服务器时，根据它的权重值，添加对应的次数而已：
// Load Balance with Weight Random
#pragma once
#include <vector>#include <string>#include <unordered_map>#include <iostream>#include <algorithm>
class LoadBalanceWeightedRandom{public: LoadBalanceWeightedRandom() { }
~LoadBalanceWeightedRandom() { }
bool AddServer(const std::string& srv, int weight) { if(weight < 1) { std::cout << "Weight should be equal or greater than 1." << std::endl; return false; }
for(int i = 0; i < weight; i++) { // Add weight times to vector servers.push_back(srv); }
return true; }
// Simulate a new request bool NextRequest() { if(servers.empty()) { std::cout << "Please add servers first. " << std::endl; return false; }
// Pickup a random server int current = rand() % servers.size(); // Update stats stats[servers[current]]++;
return true; }
void PrintStats() const { std::cout << "Server Hit stats with weighted random: "; for(auto x : stats) { std::cout << std::endl; std::cout << x.first << ": " << x.second; } std::cout << std::endl; }
private: // The servers to be balanced std::vector<std::string> servers; // Stats, key is the server, value is the hit count std::unordered_map<std::string, int> stats; };
复制代码
往这个 LB 添加 5 个服务器，并给与不同的权重，然后发起一百万次请求：
void TestWeightedRandom(){ LoadBalanceWeightedRandom lb; lb.AddServer("192.168.1.10", 1); lb.AddServer("192.168.1.11", 2); lb.AddServer("192.168.1.12", 3); lb.AddServer("192.168.1.13", 4); lb.AddServer("192.168.1.14", 10);
for(int i = 0; i < 1000000; i++) { lb.NextRequest(); }
lb.PrintStats();}
复制代码
可以看到，每个服务器被分发的请求比例，跟它的权重比例是基本一样的：
Server Hit stats with weighted random: 192.168.1.13: 200290192.168.1.12: 149612192.168.1.11: 100060192.168.1.10: 50291192.168.1.14: 499747
复制代码
5. 源地址哈希 Source IP Hash
根据客户端的 IP 地址，通过 Hash 算出个数值后，对后端服务器的总数取模，然后把请求分发给取模得到的服务器。
这个代码也很简单，就不实现了。
前面的这五种算法，在选择分发到哪个服务器时，都依赖于服务器的总数。
而服务器总会有挂掉的时候。一旦某个服务器挂了，意味着可用的服务器总数发生了变化(虽然前面的例子，都没有实现 RemoveServer 的接口)，那么被选中的服务器都会发生变化。
这就带来了不一致的问题、每个请求都要重新计算。所以，后面的一致性哈希算法应运而生了。
题外话，技术也好、算法也好，都是为了解决某些具体的问题、场景而被发明出来的。
理解了问题，有助于更好的理解为什么会有这样的算法、解决方案。
6. 一致性哈希 Consistent Hashing
一致性哈希是现在用的比较广泛的算法，具体就不解释了，网上资料非常多。[维基百科](一致哈希 - 维基百科，自由的百科全书)的描述也很清楚：
一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。
参考代码如下：
// Load Balance with Consistent Hashing
#pragma once
#include <vector>#include <string>#include <sstream>#include <map>#include <unordered_map>#include <iostream>
class LoadBalanceConsistentHashing{public: LoadBalanceConsistentHashing(int vNum = 32) { virtualNum = vNum; }
~LoadBalanceConsistentHashing() { }
bool AddServer(const std::string& srv) { servers.push_back(srv);
// Insert virtual nodes for each real server for(int i = 0; i < virtualNum; i++) { // Compose name like: 192.168.1.10#1 std::stringstream srvName; srvName << srv << "#" << i; unsigned int hashKey = std::hash<std::string>{}(srvName.str()); nodes.insert({hashKey, srv}); }
return true; }
bool DeleteServer(const std::string& srv) { auto server = std::find(servers.begin(), servers.end(), srv); if(server == servers.end()) { std::cout << "Invalid server to delete. " << std::endl; return false; }
// Delete from real servers servers.erase(server);
// Delete virtual nodes for this real server for(int i = 0; i < virtualNum; i++) { // Compose name like: 192.168.1.10#1 std::stringstream srvName; srvName << srv << "#" << i; unsigned int hashKey = std::hash<std::string>{}(srvName.str());
// Find and delete auto it = nodes.find(hashKey); if(it != nodes.end()) { nodes.erase(it); } }
return true; }
// Simulate a new request bool NextRequest() { if(servers.empty()) { std::cout << "Please add servers first. " << std::endl; return false; }
// Find the node for this request int val = rand(); unsigned int hashKey = std::hash<std::string>{}(std::to_string(val)); auto node = nodes.lower_bound(hashKey); if(node == nodes.end()) { // Use the first node if not found node = nodes.begin(); }
// Update stats stats[node->second]++;
return true; }
void ResetStats() { stats.clear(); }
void PrintStats() const { std::cout << "Server Hit stats with Consistent Hashing: "; for(auto x : stats) { std::cout << std::endl; std::cout << x.first << ": " << x.second; } std::cout << std::endl; }
private: // Virtual nodes number for each real server int virtualNum; // The real servers std::vector<std::string> servers; // The virtual servers. Key is hash, value is the real server std::map<unsigned int, std::string> nodes; // Stats, key is the real server, value is the hit count std::unordered_map<std::string, int> stats; };
复制代码
往这个 LB 添加 5 个服务器，每个服务器默认的虚拟节点数为 32 个，然后发起一百万次请求：
LoadBalanceConsistentHashing lb; lb.AddServer("192.168.1.10"); lb.AddServer("192.168.1.11"); lb.AddServer("192.168.1.12"); lb.AddServer("192.168.1.13"); lb.AddServer("192.168.1.14");
for(int i = 0; i < 1000000; i++) { lb.NextRequest(); }
lb.PrintStats();
复制代码
可以看到，每个服务器被分发的请求总数比较均匀：
Server Hit stats with Consistent Hashing: 192.168.1.13: 200693192.168.1.14: 140848192.168.1.11: 180680192.168.1.12: 265031192.168.1.10: 212748
复制代码
我在代码里，用的是 C++自带的哈希函数。如果使用别的哈希算法，比如 Fowler-Noll-Vo，还能得到更加均匀的分布。
接下来，尝试把其中一个服务器删除，它附属的 32 个虚拟节点也会被删除。代码如下：
// Delete one server, and try again lb.DeleteServer("192.168.1.12"); lb.ResetStats(); for(int i = 0; i < 1000000; i++) { lb.NextRequest(); } lb.PrintStats();
复制代码
得到的输出，依然比较均匀：
Server Hit stats with Consistent Hashing: 192.168.1.14: 205757192.168.1.10: 292805192.168.1.11: 241764192.168.1.13: 259674
复制代码
7. 最小连接数法 Least Connection
检测所有后端服务器中，连接数最少的一个，然后把请求分发给它。连接数少，可以认为它处理的快，那么能者多劳，再多处理一点。
这个需要去统计、获取后端服务器的连接数，然后才能判断。就不实现了。
文章中的代码，全部上传在 GitHub，欢迎访问：GitHub - yuchuanwang/LoadBalance
评论