<返回更多

负载均衡原理及实现

2023-02-17  今日头条  Linux码农
加入收藏

什么是负载均衡 ?

 

负载均衡( 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到同一个服务器节点,会导致服务器负载过大,也即是没有解决热点问题。

 

总结

 

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>