什么是負載均衡 ？
負載均衡( 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到同一個服務器節點，會導致服務器負載過大，也即是沒有解決熱點問題。
總結
- 負載均衡就是通過一定方式把客戶端的請求分配到相應的服務節點上，保證各個服務器節點能夠在自己的承載范圍內提供服務。
- 負載均衡分為硬件負載均衡和軟件負載均衡，一般接觸到最多的是軟件負載均衡，軟件負載均衡有不同的負載均衡算法，各個負載均衡算法有各自的優缺點，可以根據適當的場景采用對應的算法。
