负载均衡原理及实现
什么是负载均衡 ？
负载均衡( LoadBalance )，顾名思义就是把任务压力进行平衡的分摊到集群中各个操作单元(或机器)上，使得避免集群中部分机器压力过大而部分机器过于空闲。经过负载均衡，使得每个机器获取适合自己的处理能力负载。
负载均衡的分类
负载均衡可分为硬件负载均衡和软件负载均衡。
硬件负载均衡比如F5.NETScaler等价格比较昂贵，一般开发中很难接触到。但软件负载均衡还是很容易接触到的，比如大家常见的Nginx、LVS等。
软件负载均衡又可以分为四层负载均衡和七层负载均衡。
所谓四层负载均衡就是在网络层基于IP+端口的负载均衡。也就是通过报文中的目标地址和端口，在加上负载均衡设备的选择方式从而选择最终对应的服务器。
所谓七层负载均衡就是在四层的基础上在应用层根据用户的http请求头和URL等信息将请求转发到特定的服务器上。LVS（linux Virtual Server）为四层负载均衡，Nginx可以做四层也可以做七层。
负载均衡的常见算法
对于软件中实现的负载均衡，常见的负载均衡算法有轮询（Round Robin）法、随机（Random）法、加权轮询（Weight Round Robin）法、加权随机（Weight Random）法、源地址哈希（Hash）法、一致性哈希（Consistent Hash）法等。
1、轮询（Round Robin）法
将接收到的请求按照顺序依次分配给各个服务器对外提供服务。
代码如下：
#include <stdio.h>
int position = 0;
int totalServer = 4;
pthread_mutex_t mut;//互斥锁
char * serverInfo[]=
{
"192.168.1.1",
"192.168.1.2",
"192.168.1.3",
"192.168.1.4",
};
char * getServerUrl()
{
char * ret = NULL;
pthread_mutex_lock(&mut);
if(position >= totalServer )
position = 0;
position++;
ret = serverInfo[position];
pthread_mutex_unlock(&mut);
return ret;
}
轮询就是对各个服务节点依次顺序遍历，当请求的次数 position 达到最大服务节点数量时，重新从0开始。
其实可以把服务节点列表想象成一个圆中的各个圆点，当访问请求次数到达最大值时也就循环是一周，然后在从0开始。
优点：对于各个服务节点对外提供服务的次数绝对均衡。
缺点：由于使用了 position 获取服务节点，因此对 position 的修改要做到互斥，所以对 性能会造成一定的影响，同时对于低承载能力的服务节点不友好，因为它要和高承载能力的服务节点接受同样的压力。
2、随机（Random）法
根据后端服务节点的个数，从中随机选择其中一个节点对外提供服务。
代码如下：
char * getServerUrl()
{
int i = rand() % totalServer;
return serverInfo[i];
}
优点: 算法实现简单，当请求的次数增大时，各个服务节点处理的请求数量近似于均衡。
缺点: 和轮训算法一样，对于低承载能力的服务节点不友好。
3、加权轮询（Weight Round Robin）法
上述的轮询法和随机法存在一个共同的缺点，就是各个服务器节点负载相对均衡，但是当各个服务器节点载能力不同时，会对低承载能力的服务器节点压力过大。
正是由于这个缺点，后续有了加权轮询法、加权随机法，该算法的实现就是给不同配置的服务器节点，配置不同的权重值，后续分配请求时，对权重高的服务器节点，多分配点，对权重低的服务器节点，少分配点。
如下实现了一个加权轮询算法：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IP_LEN 22
typedef struct {
int weight;
int cur_weight;//哪个server当权权重最大，就分配个谁
char ip[IP_LEN];
}serverInfo;
int getWeightSum(int *weight, int size)
{
int i = 0;
int total = 0;
for(i = 0; i < size; i++)
{
total += weight[i];
}
return total;
}
serverInfo * initServer(char **ips, int *weight, int size)
{
int i = 0;
serverInfo * servers = calloc(size+1, sizeof(serverInfo));
for(i = 0; i < size; i++)
{
servers[i].weight = weight[i];
memcpy(servers[i].ip, ips[i], IP_LEN);
servers[i].cur_weight = 0;
}
return servers;
}
/**该算法参看nginx中平滑的加权轮询算法，该算法会保证生成的序列比较均匀
而普通的加权轮询算法在某种权重下会出现不均匀的序列
*/
int getServerUrlIndex(serverInfo *s, int size)
{
int i=0;
int index = 0; //记录当前权重最大的server索引
int total = 0; //记录权重总和
for(i = 0; i < size; i++)
{
s[i].cur_weight += s[i].weight;
total += s[i].weight;
//记录权重最大的索引节点
if(s[index].cur_weight < s[i].cur_weight)
{
index = i;
}
}
//把当前权重最大的减去权重总和，这时候当前权重会减小，所以下次分配就不一定还是该server了
s[index].cur_weight -=total;
//返回当前权重最大的server索引
return index;
}
void getServerUrl(serverInfo *s, int *weight, int size)
{
int i = 0;
int index = 0;
int total = getWeightSum(weight, size);
for(i=0; i<total; i++)
{
index = getServerUrlIndex(s, size);
printf("get server is %s => %dn", s[index].ip, s[index].weight);
}
}
int main()
{
int i = 0;
int weight[] = {5,2,3};
char *ips[] = {"192.168.1.1", "192.168.2.2", "192.168.3.3"};
int size = sizeof(weight)/sizeof(int);
serverInfo *s = initServer(ips, weight, size);
for(i = 0; i < size; i++)
{
printf("server init is %s => %dn", s[i].ip, s[i].weight);
}
printf("getServerUrl:n");
getServerUrl(s, weight, size);
return 0;
}
//得到结果如下:
server init is 192.168.1.1 => 5
server init is 192.168.2.2 => 2
server init is 192.168.3.3 => 3
getServerUrl:
get server is 192.168.1.1 => 5
get server is 192.168.3.3 => 3
get server is 192.168.2.2 => 2
get server is 192.168.1.1 => 5
get server is 192.168.1.1 => 5
get server is 192.168.3.3 => 3
get server is 192.168.1.1 => 5
get server is 192.168.2.2 => 2
get server is 192.168.3.3 => 3
get server is 192.168.1.1 => 5
优点：加权轮询能够使用权重解决不同承载能力的服务器节点。
缺点 : 需要使用一定的机制解决某些情况下生成的序列是不均匀的问题。
4、源地址哈希（Hash）法
根据客户端的 ip 经过 hash 获取一个 hash 值，然后根据该 hash 值和服务器节点总数进行取模运算，取得对应的服务器节点。
char * getServerUrl()
{
int i = hashcode(clientIP) % totalServer;
return serverInfo[i];
}
优点 : 当服务器列表不变时，只要请求源地址不变，总会请求到相同的目标服务器，这样就可以在客户端-服务器之间构建一个有状态 session。
缺点 : 当有大量的获取客户端时，会造成部分服务器过于繁忙，导致负载不均衡。另外，当某个服务器节点挂掉后，后续 hash 到该节点的所有请求都会得不到响应。
5、一致性哈希（Consistent Hash）法
传统的hash算法一般就是 key 和节点总数进行 mod 运算 mod(key, n)，但这样会带来一个问题，就是当扩容或者缩容时，他们的映射关系就变成了mod (key, n+1) 或 mod (key, n-1),这会导致所有的 key 都会出现新的映射关系，因此很多 key 就会出现映射失败。
为了解决普通 hash 这种扩展能力和容错能力差的问题，就出现了一致性 hash（Consistent Hashing）的概念，采用一致性 hash 时，当出现扩容或者缩容时，影响的 key 只有少数部分，对全局影响不大。
一致性 hash 采用对每个服务节点进行计算 hash值，该hash值的范围在（0~2³²-1）中，我们把这些数字收尾相连构成一个范围在（0~2³²-1）的 hash 环中，然后把各个服务器节点经过 hash 运算得到对应的值，然后散列到 hash 环中，如下图，
当请求到来时，根据请求的唯一标志，比如请求的客户 IP 等经过 hash 运算得到一个 hash 值，然后根据该值从 hash 环上以顺时针的方向查找，得到一个离自己最近的服务器节点，该服务器节点也就是该请求对应的服务器。如下图，客户端请求经过 hash，从 hash 环中顺时针找到 node2 服务节点。
经过上述介绍我们可以发现一个问题，也就是当服务节点较少时，会出现数据倾斜问题，也就失去了平衡性，如下图，我们会发现很多都分配给了node2节点了。
为了防止这种数据倾斜，我们采用虚拟节点来保证平衡性。虚拟机节点其实就是服务器节点的复制，我们把一个服务器节点映射多个虚拟节点，当请求经过 hash 运算后从hash 环上以顺时针的方向查找到虚拟机节点时，我们就把虚拟节点对应的实际服务节点作为服务器。虚拟节点如下图
比如客户端请求到来，根据客户端的 key1 经过 hash 计算映射到 hash 环中如下图，从该点顺时针找到了服务器节点 3 的虚拟节点，因此把服务器节点 3 作为请求对应的服务器。
当某个服务节点宕机(比如服务节点2)，那么请求对象最终落到了服务节点 3，对于整个系统的影响也就是 key1 和 node2 之间的范围。如下图，
新增服务节点同理，当 key1 和 node3 之间新增了一个服务节点2，那么 key1 经过 hash 查找服务节点时会找到服务节点 2。
一致性hash的实现
本次分析一下开源项目 ketama 中的一致性 hash 算法的实现。
在 ketama 中为了平衡性也采用了虚拟机节点，同时为了不同的服务节点的承载 能力也使用了权重，因此权重高的，相应的虚拟机节点也就相应的多，服务器节点也就处理的请求多。
ketama 中使用如下结构记录服务节点信息。
typedef struct
{
unsigned int point; //圆环上的点
char ip[22]; //实际服务节点ip
} mcs;
// 服务器信息，主要记录服务器的ip地址和权重值
typedef struct
{
char addr[22]; //服务器ip地址
unsigned long memory; // 权重值
} serverinfo;
// 以下数据结构就是continuum环上的结点，环上的每个点其实代表了一个ip地址，该结构把点和ip地址一一对应起来。
typedef struct
{
int numpoints; //在环上的点的总数同时也是 array数组元素的总个数
void* modtime; // 更改时间
void* array; // mcs数组 该数组时以mcs中point从小到大排过序的，为了方便从环上找响应的服务节点
} continuum;
一致性hash环的创建
/*
一致性hash环的创建
该函数是创建continuum的核心函数，它先从配置文件中读取集群服务器ip和端口，以及权重信息。
创建continuum环，并把这些服务器信息和环上的数组下标对应起来。
*/
static int
ketama_create_continuum( key_t key, char* filename )
{
...
unsigned int numservers = 0; // 该变量来记录共从配置文件中共读取了多少个服务器
unsigned long memory; // 该变量是配置文件中所有服务器权重值的总和
serverinfo* slist; // 从配置文件中读取到的服务器信息，包括ip地址，端口，权重值
// 从配置文件filename中读取服务器信息，把服务器总数保存到变量numservers中，把所有服务器的权重值保存到memory中
slist = read_server_definitions( filename, &numservers, &memory );
/*
以下代码开始构建continuum环
平均每台服务器要在这个环上布160个点，这个数组的元素个数就是服务器个数*160。
具体多少个点，需要根据事情的服务器权重值进行计算得到。
为什么要选择160个点呢？主要是通过md5计算出来的是16个整数，把这个整数分成4等分，每份是4位整数。
而每进行一次hash计算，我们可以获得4个点。
*/
mcs continuum[ numservers * 160 ];
unsigned int i, k, cont = 0;
for( i = 0; i < numservers; i++ ) // 遍历所有服务器开始在环上部点
{
float pct = (float)slist[i].memory / (float)memory; // 计算服务器i在所有服务器权重的占比
/* 由于计算一次可以得到4个点，所有对每一台机器来说，总的计算只需要计算40*numservers次。
按权重占比进行划分，就是以下的计算得到的次数
*/
unsigned int ks = floorf( pct * 40.0 * (float)numservers );
//ks是每个ip地址对应的总点数
for( k = 0; k < ks; k++ ) // 计算出总次数，每次可以得到4个点
{
/* 40 hashes, 4 numbers per hash = 160 points per server */
char ss[30];
unsigned char digest[16];
// 通过计算hash值来得到下标值，该hash值是字符串："-n"，其中的n是通过权重计算出来的该主机应该部点的总数/4。
sprintf( ss, "%s-%d", slist[i].addr, k );
ketama_md5_digest( ss, digest ); // 计算其字符串的md5值，该值计算出来后是一个unsigned char [16]的数组，也就是可以保存16个字节
int h;
for( h = 0; h < 4; h++ )// 共有16个字节，可以处理4次，得到4个点的值
{
/*
把计算出来的连续4位的数字，进行移位。
把第一个数字移到一个整数的最高8位，后面的一次移动次高8位，后面一次补零，这样就得到了一个32位的整数值。
*/
continuum[cont].point = ( digest[3+h*4] << 24 )
| ( digest[2+h*4] << 16 )
| ( digest[1+h*4] << 8 )
| digest[h*4];
// 复制对应的ip地址到该点上
memcpy( continuum[cont].ip, slist[i].addr, 22 );
cont++;
}
}
}
free( slist );
/*Sorts in ascending order of "point"
以下代码对计算出来的环上点的值进行排序，方便进行查找
这里要注意：排序是按照point的值（计算出来的整数值）进行的，也就是说原来的数组下标顺序被打乱了。
*/
/* Sorts in ascending order of "point" */
qsort( (void*) &continuum, cont, sizeof( mcs ), (compfn)ketama_compare );
/*到这里算法的实现就结束了，环上的点(0^32整数范围内)都已经建立起来，每个点都是0到2^32的一个整数和ip地址的结构。
这样查找的时候，只是需要hash(key)，并在环上找到对应的数的位置，取得该节点的ip地址即可。
*/
...
return 1;
}
hash环的构建也很简单：
1、从配置文件中读取服务器信息列表，获取总的权重值。
2、创建numservers * 160 个point点也就是虚拟机节点，然后根据权重进行hash运算分配这些point点，权重高的分配的越多。同时对这些point点进行从小到大排序，为何后续查找方便。
在环上查找元素
//计算key的hash值的实现方法
unsigned int ketama_hashi( char* inString )
{
unsigned char digest[16];
// 对key的值做md5计算，得到一个有16个元素的unsigned char数组
ketama_md5_digest( inString, digest );
//取数组中的前4个字符，并移位，得到一个unsigned int的hash值
return (unsigned int)(( digest[3] << 24 )
| ( digest[2] << 16 )
| ( digest[1] << 8 )
| digest[0] );
}
//在环上查找相应的结点
mcs* ketama_get_server( char* key, ketama_continuum cont )
{
unsigned int h = ketama_hashi( key ); // 计算key的hash值，并保存到变量h中
int highp = cont->numpoints; // 该变量cont->numpoints是总的数组埋点数
mcs (*mcsarr)[cont->numpoints] = cont->array; // 数组结点的值
int lowp = 0, midp;
unsigned int midval, midval1;
// divide and conquer array search to find server with next biggest
// point after what this key hashes to
while ( 1 )
{
// 从数组的中间位置开始找
// 注意此时的数组是按照point的值排好序了
midp = (int)( ( lowp+highp ) / 2 );
// 若中间位置等于最大点数，直接绕回到0位置
if ( midp == cont->numpoints )
return &( (*mcsarr)[0] ); // if at the end, roll back to zeroth
// 取的中间位置的point值
midval = (*mcsarr)[midp].point;
/* 获取 midp 上限和下限， 若midp 为0 则midval1 为0 ，否则取midp-1的point，也即是
获取 h 在如下范围内 (*mcsarr)[midp-1].point < h < (*mcsarr)[midp]
*/
midval1 = midp == 0 ? 0 : (*mcsarr)[midp-1].point;
// 把h的值和取的两个值point值进行比较，若在这两个point值之间说明h值应该放在较大的那个point值的下标对应的ip地址上
if ( h <= midval && h > midval1 )
return &( (*mcsarr)[midp] );
if ( midval < h ) // 否则继续二分查找
lowp = midp + 1;
else
highp = midp - 1;
if ( lowp > highp ) // 若没有找到，直接返回0位置的值，这种情况应该很少
return &( (*mcsarr)[0] );
}
}
查找服务器节点如下：
1、根据请求的key进行hash得到一个整数。
2、根据该整数从环上查找到一个比该整数大最近虚拟机节点，获取到的服务器节点就是要找的服务器。
以上就是hash一致性算法的实现。
优点：具有较好的扩展性和容错性，同时保证了数据的平衡性。
缺点：当某个客户端发送很多请求，后端hash到同一个服务器节点，会导致服务器负载过大，也即是没有解决热点问题。
总结
- 负载均衡就是通过一定方式把客户端的请求分配到相应的服务节点上，保证各个服务器节点能够在自己的承载范围内提供服务。
- 负载均衡分为硬件负载均衡和软件负载均衡，一般接触到最多的是软件负载均衡，软件负载均衡有不同的负载均衡算法，各个负载均衡算法有各自的优缺点，可以根据适当的场景采用对应的算法。
