亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

什么是負(fù)載均衡 ？

負(fù)載均衡( LoadBalance )，顧名思義就是把任務(wù)壓力進(jìn)行平衡的分?jǐn)偟郊褐懈鱾€操作單元(或機(jī)器)上，使得避免集群中部分機(jī)器壓力過大而部分機(jī)器過于空閑。經(jīng)過負(fù)載均衡，使得每個機(jī)器獲取適合自己的處理能力負(fù)載。

負(fù)載均衡的分類

負(fù)載均衡可分為硬件負(fù)載均衡和軟件負(fù)載均衡。

硬件負(fù)載均衡比如F5?.NETScaler等價格比較昂貴，一般開發(fā)中很難接觸到。但軟件負(fù)載均衡還是很容易接觸到的，比如大家常見的Nginx、LVS等。

軟件負(fù)載均衡又可以分為四層負(fù)載均衡和七層負(fù)載均衡。

所謂四層負(fù)載均衡就是在網(wǎng)絡(luò)層基于IP+端口的負(fù)載均衡。也就是通過報文中的目標(biāo)地址和端口，在加上負(fù)載均衡設(shè)備的選擇方式從而選擇最終對應(yīng)的服務(wù)器。

所謂七層負(fù)載均衡就是在四層的基礎(chǔ)上在應(yīng)用層根據(jù)用戶的http請求頭和URL等信息將請求轉(zhuǎn)發(fā)到特定的服務(wù)器上。LVS（linux Virtual Server）為四層負(fù)載均衡，Nginx可以做四層也可以做七層。

負(fù)載均衡的常見算法

對于軟件中實現(xiàn)的負(fù)載均衡，常見的負(fù)載均衡算法有輪詢（Round Robin）法、隨機(jī)（Random）法、加權(quán)輪詢（Weight Round Robin）法、加權(quán)隨機(jī)（Weight Random）法、源地址哈希（Hash）法、一致性哈希（Consistent Hash）法等。

1、輪詢（Round Robin）法

將接收到的請求按照順序依次分配給各個服務(wù)器對外提供服務(wù)。

代碼如下：

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

輪詢就是對各個服務(wù)節(jié)點依次順序遍歷，當(dāng)請求的次數(shù) position 達(dá)到最大服務(wù)節(jié)點數(shù)量時，重新從0開始。

其實可以把服務(wù)節(jié)點列表想象成一個圓中的各個圓點，當(dāng)訪問請求次數(shù)到達(dá)最大值時也就循環(huán)是一周，然后在從0開始。

優(yōu)點：對于各個服務(wù)節(jié)點對外提供服務(wù)的次數(shù)絕對均衡。

缺點：由于使用了 position 獲取服務(wù)節(jié)點，因此對 position 的修改要做到互斥，所以對 性能會造成一定的影響，同時對于低承載能力的服務(wù)節(jié)點不友好，因為它要和高承載能力的服務(wù)節(jié)點接受同樣的壓力。

2、隨機(jī)（Random）法

根據(jù)后端服務(wù)節(jié)點的個數(shù)，從中隨機(jī)選擇其中一個節(jié)點對外提供服務(wù)。

代碼如下：

char * getServerUrl()
{
int i = rand() % totalServer;
 return serverInfo[i]; 
}

優(yōu)點: 算法實現(xiàn)簡單，當(dāng)請求的次數(shù)增大時，各個服務(wù)節(jié)點處理的請求數(shù)量近似于均衡。

缺點: 和輪訓(xùn)算法一樣，對于低承載能力的服務(wù)節(jié)點不友好。

3、加權(quán)輪詢（Weight Round Robin）法

上述的輪詢法和隨機(jī)法存在一個共同的缺點，就是各個服務(wù)器節(jié)點負(fù)載相對均衡，但是當(dāng)各個服務(wù)器節(jié)點載能力不同時，會對低承載能力的服務(wù)器節(jié)點壓力過大。

正是由于這個缺點，后續(xù)有了加權(quán)輪詢法、加權(quán)隨機(jī)法，該算法的實現(xiàn)就是給不同配置的服務(wù)器節(jié)點，配置不同的權(quán)重值，后續(xù)分配請求時，對權(quán)重高的服務(wù)器節(jié)點，多分配點，對權(quán)重低的服務(wù)器節(jié)點，少分配點。

如下實現(xiàn)了一個加權(quán)輪詢算法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define IP_LEN  22

typedef struct {
    int weight;
    int cur_weight;//哪個server當(dāng)權(quán)權(quán)重最大，就分配個誰
    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中平滑的加權(quán)輪詢算法，該算法會保證生成的序列比較均勻
  而普通的加權(quán)輪詢算法在某種權(quán)重下會出現(xiàn)不均勻的序列
*/
int getServerUrlIndex(serverInfo *s, int size)
{
    int i=0;
    int index = 0; //記錄當(dāng)前權(quán)重最大的server索引
    int total = 0; //記錄權(quán)重總和

    for(i = 0; i < size; i++)
    {
        s[i].cur_weight += s[i].weight;
        total += s[i].weight;
        //記錄權(quán)重最大的索引節(jié)點
        if(s[index].cur_weight < s[i].cur_weight)
        {
            index = i;
        }
    }
    //把當(dāng)前權(quán)重最大的減去權(quán)重總和，這時候當(dāng)前權(quán)重會減小，所以下次分配就不一定還是該server了
    s[index].cur_weight -=total;
    //返回當(dāng)前權(quán)重最大的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;

}


//得到結(jié)果如下:
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

優(yōu)點：加權(quán)輪詢能夠使用權(quán)重解決不同承載能力的服務(wù)器節(jié)點。

缺點 : 需要使用一定的機(jī)制解決某些情況下生成的序列是不均勻的問題。

4、源地址哈希（Hash）法

根據(jù)客戶端的 ip 經(jīng)過 hash 獲取一個 hash 值，然后根據(jù)該 hash 值和服務(wù)器節(jié)點總數(shù)進(jìn)行取模運算，取得對應(yīng)的服務(wù)器節(jié)點。

char * getServerUrl()
{
int i = hashcode(clientIP) % totalServer;
return serverInfo[i]; 
}

優(yōu)點 : 當(dāng)服務(wù)器列表不變時，只要請求源地址不變，總會請求到相同的目標(biāo)服務(wù)器，這樣就可以在客戶端-服務(wù)器之間構(gòu)建一個有狀態(tài) session。

缺點 : 當(dāng)有大量的獲取客戶端時，會造成部分服務(wù)器過于繁忙，導(dǎo)致負(fù)載不均衡。另外，當(dāng)某個服務(wù)器節(jié)點掛掉后，后續(xù) hash 到該節(jié)點的所有請求都會得不到響應(yīng)。

5、一致性哈希（Consistent Hash）法

傳統(tǒng)的hash算法一般就是 key 和節(jié)點總數(shù)進(jìn)行 mod 運算 mod(key, n)，但這樣會帶來一個問題，就是當(dāng)擴(kuò)容或者縮容時，他們的映射關(guān)系就變成了mod (key, n+1) 或 mod (key, n-1),這會導(dǎo)致所有的 key 都會出現(xiàn)新的映射關(guān)系，因此很多 key 就會出現(xiàn)映射失敗。

為了解決普通 hash 這種擴(kuò)展能力和容錯能力差的問題，就出現(xiàn)了一致性 hash（Consistent Hashing）的概念，采用一致性 hash 時，當(dāng)出現(xiàn)擴(kuò)容或者縮容時，影響的 key 只有少數(shù)部分，對全局影響不大。

一致性 hash 采用對每個服務(wù)節(jié)點進(jìn)行計算 hash值，該hash值的范圍在（0~2³²-1）中，我們把這些數(shù)字收尾相連構(gòu)成一個范圍在（0~2³²-1）的 hash 環(huán)中，然后把各個服務(wù)器節(jié)點經(jīng)過 hash 運算得到對應(yīng)的值，然后散列到 hash 環(huán)中，如下圖，

當(dāng)請求到來時，根據(jù)請求的唯一標(biāo)志，比如請求的客戶 IP 等經(jīng)過 hash 運算得到一個 hash 值，然后根據(jù)該值從 hash 環(huán)上以順時針的方向查找，得到一個離自己最近的服務(wù)器節(jié)點，該服務(wù)器節(jié)點也就是該請求對應(yīng)的服務(wù)器。如下圖，客戶端請求經(jīng)過 hash，從 hash 環(huán)中順時針找到 node2 服務(wù)節(jié)點。

經(jīng)過上述介紹我們可以發(fā)現(xiàn)一個問題，也就是當(dāng)服務(wù)節(jié)點較少時，會出現(xiàn)數(shù)據(jù)傾斜問題，也就失去了平衡性，如下圖，我們會發(fā)現(xiàn)很多都分配給了node2節(jié)點了。

為了防止這種數(shù)據(jù)傾斜，我們采用虛擬節(jié)點來保證平衡性。虛擬機(jī)節(jié)點其實就是服務(wù)器節(jié)點的復(fù)制，我們把一個服務(wù)器節(jié)點映射多個虛擬節(jié)點，當(dāng)請求經(jīng)過 hash 運算后從hash 環(huán)上以順時針的方向查找到虛擬機(jī)節(jié)點時，我們就把虛擬節(jié)點對應(yīng)的實際服務(wù)節(jié)點作為服務(wù)器。虛擬節(jié)點如下圖

比如客戶端請求到來，根據(jù)客戶端的 key1 經(jīng)過 hash 計算映射到 hash 環(huán)中如下圖，從該點順時針找到了服務(wù)器節(jié)點 3 的虛擬節(jié)點，因此把服務(wù)器節(jié)點 3 作為請求對應(yīng)的服務(wù)器。

當(dāng)某個服務(wù)節(jié)點宕機(jī)(比如服務(wù)節(jié)點2)，那么請求對象最終落到了服務(wù)節(jié)點 3，對于整個系統(tǒng)的影響也就是 key1 和 node2 之間的范圍。如下圖，

新增服務(wù)節(jié)點同理，當(dāng) key1 和 node3 之間新增了一個服務(wù)節(jié)點2，那么 key1 經(jīng)過 hash 查找服務(wù)節(jié)點時會找到服務(wù)節(jié)點 2。

一致性hash的實現(xiàn)

本次分析一下開源項目 ketama 中的一致性 hash 算法的實現(xiàn)。

在 ketama 中為了平衡性也采用了虛擬機(jī)節(jié)點，同時為了不同的服務(wù)節(jié)點的承載 能力也使用了權(quán)重，因此權(quán)重高的，相應(yīng)的虛擬機(jī)節(jié)點也就相應(yīng)的多，服務(wù)器節(jié)點也就處理的請求多。

ketama 中使用如下結(jié)構(gòu)記錄服務(wù)節(jié)點信息。

typedef struct
{
unsigned int point; //圓環(huán)上的點
char ip[22]; //實際服務(wù)節(jié)點ip
} mcs;

// 服務(wù)器信息，主要記錄服務(wù)器的ip地址和權(quán)重值
typedef struct
{
char addr[22]; //服務(wù)器ip地址
unsigned long memory; // 權(quán)重值
} serverinfo;

// 以下數(shù)據(jù)結(jié)構(gòu)就是continuum環(huán)上的結(jié)點，環(huán)上的每個點其實代表了一個ip地址，該結(jié)構(gòu)把點和ip地址一一對應(yīng)起來。
typedef struct
{
int numpoints; //在環(huán)上的點的總數(shù)同時也是 array數(shù)組元素的總個數(shù)
void* modtime; // 更改時間
void* array; // mcs數(shù)組 該數(shù)組時以mcs中point從小到大排過序的，為了方便從環(huán)上找響應(yīng)的服務(wù)節(jié)點
} continuum;

一致性hash環(huán)的創(chuàng)建

/*
一致性hash環(huán)的創(chuàng)建
該函數(shù)是創(chuàng)建continuum的核心函數(shù)，它先從配置文件中讀取集群服務(wù)器ip和端口，以及權(quán)重信息。
創(chuàng)建continuum環(huán)，并把這些服務(wù)器信息和環(huán)上的數(shù)組下標(biāo)對應(yīng)起來。
*/
static int
ketama_create_continuum( key_t key, char* filename )
{


    ...
    unsigned int numservers = 0; // 該變量來記錄共從配置文件中共讀取了多少個服務(wù)器
    unsigned long memory; // 該變量是配置文件中所有服務(wù)器權(quán)重值的總和
    serverinfo* slist; // 從配置文件中讀取到的服務(wù)器信息，包括ip地址，端口，權(quán)重值

    // 從配置文件filename中讀取服務(wù)器信息，把服務(wù)器總數(shù)保存到變量numservers中，把所有服務(wù)器的權(quán)重值保存到memory中
    slist = read_server_definitions( filename, &numservers, &memory );


   /*
    以下代碼開始構(gòu)建continuum環(huán)
    平均每臺服務(wù)器要在這個環(huán)上布160個點，這個數(shù)組的元素個數(shù)就是服務(wù)器個數(shù)*160。
    具體多少個點，需要根據(jù)事情的服務(wù)器權(quán)重值進(jìn)行計算得到。
    為什么要選擇160個點呢？主要是通過md5計算出來的是16個整數(shù)，把這個整數(shù)分成4等分，每份是4位整數(shù)。
    而每進(jìn)行一次hash計算，我們可以獲得4個點。
   */
    mcs continuum[ numservers * 160 ];
    unsigned int i, k, cont = 0;

    for( i = 0; i < numservers; i++ ) // 遍歷所有服務(wù)器開始在環(huán)上部點
    {
        float pct = (float)slist[i].memory / (float)memory; // 計算服務(wù)器i在所有服務(wù)器權(quán)重的占比
        /* 由于計算一次可以得到4個點，所有對每一臺機(jī)器來說，總的計算只需要計算40*numservers次。
           按權(quán)重占比進(jìn)行劃分，就是以下的計算得到的次數(shù)
         */
        unsigned int ks = floorf( pct * 40.0 * (float)numservers );

        //ks是每個ip地址對應(yīng)的總點數(shù)
        for( k = 0; k < ks; k++ ) // 計算出總次數(shù)，每次可以得到4個點
        {
            /* 40 hashes, 4 numbers per hash = 160 points per server */
            char ss[30];
            unsigned char digest[16];

           // 通過計算hash值來得到下標(biāo)值，該hash值是字符串："-n"，其中的n是通過權(quán)重計算出來的該主機(jī)應(yīng)該部點的總數(shù)/4。
            sprintf( ss, "%s-%d", slist[i].addr, k );
            ketama_md5_digest( ss, digest ); // 計算其字符串的md5值，該值計算出來后是一個unsigned char [16]的數(shù)組，也就是可以保存16個字節(jié)


            int h;
            for( h = 0; h < 4; h++ )// 共有16個字節(jié)，可以處理4次，得到4個點的值
            {
                /*
                  把計算出來的連續(xù)4位的數(shù)字，進(jìn)行移位。
                  把第一個數(shù)字移到一個整數(shù)的最高8位，后面的一次移動次高8位，后面一次補(bǔ)零，這樣就得到了一個32位的整數(shù)值。
               */
                continuum[cont].point = ( digest[3+h*4] << 24 )
                                      | ( digest[2+h*4] << 16 )
                                      | ( digest[1+h*4] <<  8 )
                                      |   digest[h*4];

                // 復(fù)制對應(yīng)的ip地址到該點上
                memcpy( continuum[cont].ip, slist[i].addr, 22 );
                cont++;
            }
        }
    }
    free( slist );

    /*Sorts in ascending order of "point" 
      以下代碼對計算出來的環(huán)上點的值進(jìn)行排序，方便進(jìn)行查找
      這里要注意：排序是按照point的值（計算出來的整數(shù)值）進(jìn)行的，也就是說原來的數(shù)組下標(biāo)順序被打亂了。
     */
    /* Sorts in ascending order of "point" */
    qsort( (void*) &continuum, cont, sizeof( mcs ), (compfn)ketama_compare );
    /*到這里算法的實現(xiàn)就結(jié)束了，環(huán)上的點(0^32整數(shù)范圍內(nèi))都已經(jīng)建立起來，每個點都是0到2^32的一個整數(shù)和ip地址的結(jié)構(gòu)。
    這樣查找的時候，只是需要hash(key)，并在環(huán)上找到對應(yīng)的數(shù)的位置，取得該節(jié)點的ip地址即可。
    */

    ...

    return 1;
}

hash環(huán)的構(gòu)建也很簡單：

1、從配置文件中讀取服務(wù)器信息列表，獲取總的權(quán)重值。

2、創(chuàng)建numservers * 160 個point點也就是虛擬機(jī)節(jié)點，然后根據(jù)權(quán)重進(jìn)行hash運算分配這些point點，權(quán)重高的分配的越多。同時對這些point點進(jìn)行從小到大排序，為何后續(xù)查找方便。

在環(huán)上查找元素

//計算key的hash值的實現(xiàn)方法
unsigned int ketama_hashi( char* inString ) 
{
unsigned char digest[16];
// 對key的值做md5計算，得到一個有16個元素的unsigned char數(shù)組
ketama_md5_digest( inString, digest ); 

//取數(shù)組中的前4個字符，并移位，得到一個unsigned int的hash值
return (unsigned int)(( digest[3] << 24 )
| ( digest[2] << 16 )
| ( digest[1] << 8 )
| digest[0] );
}


//在環(huán)上查找相應(yīng)的結(jié)點
mcs* ketama_get_server( char* key, ketama_continuum cont )
{
unsigned int h = ketama_hashi( key ); // 計算key的hash值，并保存到變量h中
int highp = cont->numpoints; // 該變量cont->numpoints是總的數(shù)組埋點數(shù)
mcs (*mcsarr)[cont->numpoints] = cont->array; // 數(shù)組結(jié)點的值
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 )
{
// 從數(shù)組的中間位置開始找
// 注意此時的數(shù)組是按照point的值排好序了
midp = (int)( ( lowp+highp ) / 2 );
// 若中間位置等于最大點數(shù)，直接繞回到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 在如下范圍內(nèi) (*mcsarr)[midp-1].point < h < (*mcsarr)[midp]
*/
midval1 = midp == 0 ? 0 : (*mcsarr)[midp-1].point;
// 把h的值和取的兩個值point值進(jìn)行比較，若在這兩個point值之間說明h值應(yīng)該放在較大的那個point值的下標(biāo)對應(yīng)的ip地址上
if ( h <= midval && h > midval1 )
return &( (*mcsarr)[midp] );

if ( midval < h ) // 否則繼續(xù)二分查找
lowp = midp + 1;
else
highp = midp - 1;

if ( lowp > highp ) // 若沒有找到，直接返回0位置的值，這種情況應(yīng)該很少
return &( (*mcsarr)[0] );
}
}

查找服務(wù)器節(jié)點如下：

1、根據(jù)請求的key進(jìn)行hash得到一個整數(shù)。

2、根據(jù)該整數(shù)從環(huán)上查找到一個比該整數(shù)大最近虛擬機(jī)節(jié)點，獲取到的服務(wù)器節(jié)點就是要找的服務(wù)器。

以上就是hash一致性算法的實現(xiàn)。

優(yōu)點：具有較好的擴(kuò)展性和容錯性，同時保證了數(shù)據(jù)的平衡性。

缺點：當(dāng)某個客戶端發(fā)送很多請求，后端hash到同一個服務(wù)器節(jié)點，會導(dǎo)致服務(wù)器負(fù)載過大，也即是沒有解決熱點問題。

總結(jié)

• 負(fù)載均衡就是通過一定方式把客戶端的請求分配到相應(yīng)的服務(wù)節(jié)點上，保證各個服務(wù)器節(jié)點能夠在自己的承載范圍內(nèi)提供服務(wù)。
• 負(fù)載均衡分為硬件負(fù)載均衡和軟件負(fù)載均衡，一般接觸到最多的是軟件負(fù)載均衡，軟件負(fù)載均衡有不同的負(fù)載均衡算法，各個負(fù)載均衡算法有各自的優(yōu)缺點，可以根據(jù)適當(dāng)?shù)膱鼍安捎脤?yīng)的算法。