什么是负载均衡 ？
负载均衡( 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到同一个服务器节点，会导致服务器负载过大，也即是没有解决热点问题。
总结
京公网安备 11010802035086号