負載均衡hash演算法

⑴ 負載均衡是怎麼做的~

1、服務直接返回：這種安裝方式負載均衡的LAN口不使用，WAN口與伺服器在同一個網路中，互聯網的客戶端訪問負載均衡的虛IP（VIP），虛IP對應負載均衡機的WAN口，負載均衡根據策略將流量分發到伺服器上，伺服器直接響應客戶端的請求。

2、橋接模式：橋接模式配置簡單，不改變現有網路。負載均衡的WAN口和LAN口分別連接上行設備和下行伺服器。LAN口不需要配置IP（WAN口與LAN口是橋連接），所有的伺服器與負載均衡均在同一邏輯網路中。

3、路由模式：路由模式的部署方式，伺服器的網關必須設置成負載均衡機的LAN口地址，且與WAN口分署不同的邏輯網路。因此所有返回的流量也都經過負載均衡。這種方式對網路的改動小，能均衡任何下行流量。

(1)負載均衡hash演算法擴展閱讀

負載均衡的演算法:

1、隨機演算法：Random隨機，按權重設置隨機概率。在一個截面上碰撞的概率高，但調用量越大分布越均勻，而且按概率使用權重後也比較均勻，有利於動態調整提供者權重。

2、哈希演算法：一致性哈希一致性Hash，相同參數的請求總是發到同一提供者。當某一台提供者掛時，原本發往該提供者的請求，基於虛擬節點，平攤到其它提供者，不會引起劇烈變動。

3、URL散列：通過管理客戶端請求URL信息的散列，將發送至相同URL的請求轉發至同一伺服器的演算法。

參考資料

網路-負載均衡

⑵ nginx 負載均衡之一致性hash，普通hash

哈希負載均衡原理
  ngx_http_upstream_hash_mole支持普通的hash及一致性hash兩種負載均衡演算法，默認的是普通的hash來進行負載均衡。
  nginx 普通的hash演算法支持配置http變數值作為hash值計算的key，通過hash計算得出的hash值和總權重的余數作為挑選server的依據；nginx的一致性hash(chash)演算法則要復雜一些。這里會對一致性hash的機制原理作詳細的說明。
一致性hash演算法的原理
一致性hash用於對hash演算法的改進，後端伺服器在配置的server的數量發生變化後，同一個upstream server接收到的請求會的數量和server數量變化之間會有變化。尤其是在負載均衡配置的upstream server數量發生增長後，造成產生的請求可能會在後端的upstream server中並不均勻，有的upstream server負載很低，有的upstream server負載較高，這樣的負載均衡的效果比較差，可能對upstream server造成不良的影響。由此，產生了一致性hash演算法來均衡。
   那麼為什麼一致性hash演算法能改善這種情況呢？這里引用網上資料的一致性hash演算法的圖例。
因為對於hash(k)的范圍在int范圍，所以我們將0~2^32作為一個環。其步驟為：
1，求出每個伺服器的hash（伺服器ip）值，將其配置到一個 0~2^n 的圓環上（n通常取32）。
2，用同樣的方法求出待存儲對象的主鍵 hash值，也將其配置到這個圓環上，然後從數據映射到的位置開始順時針查找，將數據分布到找到的第一個伺服器節點上。
其分布如圖：

除了上邊的優點，其實還有一個優點：對於熱點數據，如果發現node1訪問量明顯很大，負載高於其他節點，這就說明node1存儲的數據是熱點數據。這時候，為了減少node1的負載，我們可以在熱點數據位置再加入一個node，用來分擔熱點數據的壓力。
雪崩效應

接下來我們來看一下，當有節點宕機時會有什麼問題。如下圖：

如上圖，當B節點宕機後，原本存儲在B節點的k1，k2將會遷移到節點C上，這可能會導致很大的問題。如果B上存儲的是熱點數據，將數據遷移到C節點上，然後C需要承受B+C的數據，也承受不住，也掛了。。。。然後繼續CD都掛了。這就造成了雪崩效應。
上面會造成雪崩效應的原因分析：
如果不存在熱點數據的時候，每台機器的承受的壓力是M/2(假設每台機器的最高負載能力為M)，原本是不會有問題的，但是，這個時候A伺服器由於有熱點數據掛了，然後A的數據遷移至B，導致B所需要承受的壓力變為M（還不考慮熱點數據訪問的壓力），所以這個失敗B是必掛的，然後C至少需要承受1.5M的壓力。。。。然後大家一起掛。。。
所以我們通過上面可以看到，之所以會大家一起掛，原因在於如果一台機器掛了，那麼它的壓力全部被分配到一台機器上，導致雪崩。

怎麼解決雪崩問題呢，這時候需要引入虛擬節點來進行解決。
虛擬節點

虛擬節點，我們可以針對每個實際的節點，虛擬出多個虛擬節點，用來映射到圈上的位置，進行存儲對應的數據。如下圖：

如上圖：A節點對應A1，A2，BCD節點同理。這時候，如果A節點掛了，A節點的數據遷移情況是:A1數據會遷移到C2，A2數據遷移到D1。這就相當於A的數據被C和D分擔了，這就避免了雪崩效應的發送，而且虛擬節點我們可以自定義設置，使其適用於我們的應用。

ngx_http_upstream_consistent_hash
該模塊可以根據配置參數採取不同的方式將請求均勻映射到後端機器，比如：

指令
語法：consistent_hash variable_name
默認值：none
上下文：upstream

配置upstream採用一致性hash作為負載均衡演算法，並使用配置的變數名作為hash輸入。

參考文檔：
https://www.cnblogs.com/FengGeBlog/p/10615345.html
http://www.ttlsa.com/nginx/nginx-upstream-consistent-hash-mole/

⑶ 負載均衡演算法 — 輪詢

在分布式系統中，為了實現負載均衡，必然會涉及到負載調度演算法，如 Nginx 和 RPC 服務發現等場景。常見的負載均衡演算法有 輪詢 、 源地址 Hash 、 最少連接數 ，而 輪詢 是最簡單且應用最廣的演算法。

3 種常見的喚晌輪詢調度演算法，分別為 簡單輪詢 、 加權輪詢 、 平滑加權輪詢 。本文將用如下 4 個服務，來詳細說明輪詢調度過程。

簡單輪詢是輪詢演算法中最簡單的一種，但扒橋由於它不支持配置負載，所以應用較少。

假設有 N 台實例 S = {S1, S2, …, Sn}，指示變數 currentPos 表示當前選擇的實例 ID，初始化為 -1。演算法可以描述為：
1、調度到下一個實例；
2、若所有實例已被 調度 過一次，則從頭開始調度；
3、每次調度重復步驟 1、2；

調度過程，如下：

這里使用 PHP 來實現，源碼見 fan-hao/load-balance 部分。

首先，定義一個統一的操作介面，主要有 init() 和 next() 這 2 個方法。

然後，根據簡單輪詢演算法思路，實現上述介面：

其中， total 為總實例數量，春鏈猛 services 為服務實例列表。由於簡單輪詢不需要配置權重，因此可簡單配置為：

在實際應用中，同一個服務會部署到不同的硬體環境，會出現性能不同的情況。若直接使用簡單輪詢調度演算法，給每個服務實例相同的負載，那麼，必然會出現資源浪費的情況。因此為了避免這種情況，一些人就提出了下面的 加權輪詢 演算法。

加權輪詢演算法引入了「權」值，改進了簡單輪詢演算法，可以根據硬體性能配置實例負載的權重，從而達到資源的合理利用。

假設有 N 台實例 S = {S1, S2, …, Sn}，權重 W = {W1, W2, ..., Wn}，指示變數 currentPos 表示當前選擇的實例 ID，初始化為 -1；變數 currentWeight 表示當前權重，初始值為 max(S)；max(S) 表示 N 台實例的最大權重值，gcd(S) 表示 N 台實例權重的最大公約數。

演算法可以描述為：
1、從上一次調度實例起，遍歷後面的每個實例；
2、若所有實例已被遍歷過一次，則減小 currentWeight 為 currentWeight - gcd(S)，並從頭開始遍歷；若 currentWeight 小於等於 0，則重置為 max(S)；
3、 直到 遍歷的實例的權重大於等於 currentWeight 時結束，此時實例為需調度的實例；
4、每次調度重復步驟 1、2、3；

例如，上述 4 個服務，最大權重 max(S) 為 4，最大公約數 gcd(S) 為 1。其調度過程如下：

這里使用 PHP 來實現，源碼見 fan-hao/load-balance 部分。

其中， getMaxWeight() 為所有實例的最大權重值； getGcd() 為所有實例權重的最大公約數，主要是通過 gcd() 方法（可用 gmp_gcd() 函數）求得 2 個數的最大公約數，然後求每一個實例的權重與當前最大公約數的最大公約數。實現如下：

需要注意的是，在配置 services 服務列表時，需要指定其權重：

加權輪詢 演算法雖然通過配置實例權重，解決了 簡單輪詢 的資源利用問題，但是它還是存在一個比較明顯的 缺陷 。例如：

服務實例 S = {a, b, c}，權重 W = {5, 1, 1}，使用加權輪詢調度生成的實例序列為 {a, a, a, a, a, b, c}，那麼就會存在連續 5 個請求都被調度到實例 a。而實際中，這種不均勻的負載是不被允許的，因為連續請求會突然加重實例 a 的負載，可能會導致嚴重的事故。

為了解決加權輪詢調度不均勻的缺陷，一些人提出了 平滑加權輪詢 調度演算法，它會生成的更均勻的調度序列 {a, a, b, a, c, a, a}。對於神秘的平滑加權輪詢演算法，我將在後續文章中詳細介紹它的原理和實現。

輪詢演算法是最簡單的調度演算法，因為它無需記錄當前所有連接的狀態，所以它是一種 無狀態 的調度演算法，這些特性使得它應用較廣。

輪詢調度演算法並不能動態感知每個實例的負載，它完全依賴於我們的工程經驗，人為配置權重來實現基本的負載均衡，並不能保證服務的高可用性。若服務的某些實例因其他原因負載突然加重，輪詢調度還是會一如既往地分配請求給這個實例，因此可能會形成小面積的宕機，導致服務的局部不可用。

相關文章 »

⑷ 負載均衡的幾種常用方式

理解負載均衡，必須先搞清楚正向代理和反向代理。

註：

正向代理，代理的是用戶。

反向代理，代理的是伺服器

什麼是負載均衡

當一台伺服器的單位時間內謹陪畢的訪問量越大時，伺服器壓力就越大，大到超過自身承受能力時，伺服器就會崩潰。為了避免伺服器崩潰，讓用戶有更好的體驗，我們通過負載均衡的方式來分擔伺服器壓力。

我們可以建立很多很多伺服器，組成一個伺服器集群，當用戶訪問網站時，先訪問一個中間伺服器，在讓這個中間伺服器在伺服器集群中選擇一個壓力較小的伺服器，然後將該訪問請求引入該伺服器。如此以來，用戶的每次訪問，都會保證伺服器集群中的每個伺服器壓力趨於平衡，分擔了伺服器壓力，避免了伺服器崩潰的情況。

負載均衡是用反向代理的原理實現的。

1、輪詢（默認）

每個請求 按時間順序逐一分配 到不同的後端伺服器，如果後端伺服器down掉，能自動剔除。

upstreambackserver {server192.168.0.14;server192.168.0.15;}

2、weight

指定輪詢幾率，weight和訪問比率成正比，用於後端伺服器性能不均亂隱的

情況。

upstreambackserver {server192.168.0.14weight=3;server192.168.0.15weight=7;}

權重越高，在被訪問的概率越大，如上例，分別是30%，70%。

3、上述方式存在一個問題就是說，在負載均衡系統中，假如用戶在某台伺服器上登錄了，那麼該用戶第二次請求的時候，因為我們是負載均衡系統，每次請求都會重新定位到伺服器集群中的某一個，那麼已經登錄某一個伺服器的用戶再重新定位到另一個伺服器，其登錄信息將會丟失，這樣顯然是不妥的。

我們可以採用ip_hash指令解決這個問題，如果客戶已經訪問了某個伺服器，當用戶再次訪問時，會將該請求通過哈希演算法，自動定位到該伺服器。

每個請求按訪問ip的hash結果分配，這樣每個訪客固定訪問一個後端伺服器，可以解決session的問題。

upstreambackserver{ip_hash;server192.168.0.14:88;server192.168.0.15:80;}

4、fair（第三方）

按後端伺服器的響應時間來分配請求，響應時間短的優先分配。

upstreambackserver {serverserver1;serverserver2;fair;}

5、url_hash（第三方）

按訪問url的hash結果來分配請求，使每個url定向到同一個後端伺服器，後端伺服器為緩存時比較有效。

upstream backserver {    server squid1:3128;    server squid2:3128;    hash$request_uri;    hash_method crc32;}123456

每個設備的狀態設置為:

down 表示單前的server暫時不參與負載

weight 默認為1.weight越大，負載的權重就祥芹越大。

max_fails：允許請求失敗的次數默認為1.當超過最大次數時，返回 proxy_next_upstream模塊定義的錯誤

fail_timeout:max_fails次失敗後，暫停的時間。

backup： 其它所有的非backup機器down或者忙的時候，請求backup機器。所以這台機器壓力會最輕。

配置實例：

#user  nobody;worker_processes4;events {# 最大並發數worker_connections1024;}http{# 待選伺服器列表upstream myproject{# ip_hash指令，將同一用戶引入同一伺服器。ip_hash;        server125.219.42.4fail_timeout=60s;        server172.31.2.183;        }    server{# 監聽埠listen80;# 根目錄下location / {# 選擇哪個伺服器列表proxy_pass http://myproject;                }            }

摘自https://www.cnblogs.com/lcword/p/12513155.html

⑸ 哈希演算法從原理到實戰

引言 

       將任意長度的二進制字元串映射為定長二進制字元串的映射規則我們稱為散列（hash）演算法，又叫哈希（hash）演算法，而通過原始數據映射之後得到的二進制值稱為哈希值。哈希表（hash表）結構是哈希演算法的一種應用，也叫散列表。用的是數組支持按照下標隨機訪問數據的特性擴展、演化而來。可以說沒有數組就沒有散列表。

哈希演算法主要特點

        從哈希值不能反向推導原始數據，也叫單向哈希。

        對輸入數據敏感，哪怕只改了一個Bit，最後得到的哈希值也大不相同。

        散列沖突的概率要小。

        哈希演算法執行效率要高，散列結果要盡量均衡。

哈希演算法的核心應用

         安全加密 ：對於敏感數據比如密碼欄位進行MD5或SHA加密傳輸。

         唯一標識 ：比如圖片識別，可針對圖像二進制流進行摘要後MD5，得到的哈希值作為圖片唯一標識。

         散列函數 :是構造散列表的關鍵。它直接決定了散列沖突的概率和散列表的性質。不過相對哈希演算法的其他方面應用，散列函數對散列沖突要求較低，出現沖突時可以通過開放定址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高。反而更加關注的是散列的均勻性，即是否散列值均勻落入槽中以及散列函數執行的快慢也會影響散列表性能。所以散列函數一般比較簡單，追求均勻和高效。

        *負載均衡 ：常用的負載均衡演算法有很多，比如輪詢、隨機、加權輪詢。如何實現一個會話粘滯的負載均衡演算法呢？可以通過哈希演算法，對客戶端IP地址或會話SessionID計算哈希值，將取得的哈希值與伺服器列表大小進行取模運算，最終得到應該被路由到的伺服器編號。這樣就可以把同一IP的客戶端請求發到同一個後端伺服器上。

        *數據分片 ：比如統計1T的日誌文件中「搜索關鍵詞」出現次數該如何解決？我們可以先對日誌進行分片，然後採用多機處理，來提高處理速度。從搜索的日誌中依次讀取搜索關鍵詞，並通過哈希函數計算哈希值，然後再跟n(機器數)取模，最終得到的值就是應該被分到的機器編號。這樣相同哈希值的關鍵詞就被分到同一台機器進行處理。每台機器分別計算關鍵詞出現的次數，再進行合並就是最終結果。這也是MapRece的基本思想。再比如圖片識別應用中給每個圖片的摘要信息取唯一標識然後構建散列表，如果圖庫中有大量圖片，單機的hash表會過大，超過單機內存容量。這時也可以使用分片思想，准備n台機器，每台機器負責散列表的一部分數據。每次從圖庫取一個圖片，計算唯一標識，然後與機器個數n求余取模，得到的值就是被分配到的機器編號，然後將這個唯一標識和圖片路徑發往對應機器構建散列表。當進行圖片查找時，使用相同的哈希函數對圖片摘要信息取唯一標識並對n求余取模操作後，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。實際上海量數據的處理問題，都可以藉助這種數據分片思想，突破單機內存、CPU等資源限制。

        *分布式存儲 ：一致性哈希演算法解決緩存等分布式系統的擴容、縮容導致大量數據搬移難題。

         JDK集合工具實現 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map實現類源碼分析，詳見  https://www.jianshu.com/p/602324fa59ac

總結

        本文從哈希演算法的原理及特點，總結了哈希演算法的常見應用場景。

        其中基於余數思想和同餘定理實現的哈希演算法（除留取余法），廣泛應用在分布式場景中（散列函數、數據分片、負載均衡）。由於組合數學中的「鴿巢」原理，理論上不存在完全沒有沖突的哈希演算法。（PS:「鴿巢」原理是指有限的槽位，放多於槽位數的鴿子時，勢必有不同的鴿子落在同一槽內，即沖突發生。同餘定理：如果a和b對x取余數操作時a%x = b%x，則a和b同餘）

        構造哈希函數的常規方法有：數據分析法、直接定址法、除留取余法、折疊法、隨機法、平方取中法等  。

        常規的解決哈希沖突方法有開放定址法（線性探測、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是採用鏈表法解決哈希沖突的。鏈表法適合大數據量的哈希沖突解決，可以使用動態數據結構（比如：跳錶、紅黑樹等）代替鏈表，防止鏈表時間復雜度過度退化導致性能下降；反之開放定址法適合少量數據的哈希沖突解決。

⑹ 哈希（hash） - 哈希演算法的應用

通過之前的學習，我們已經了解了哈希函數在散列表中的應用，哈希函數就是哈希演算法的一個應用。那麼在這里給出哈希的定義： 將任意長度的二進制值串映射為固定長度的二進制值串，這個映射規則就是哈希演算法，得到的二進制值串就是哈希值 。
要設計一個好的哈希演算法並不容易，它應該滿足以下幾點要求：

哈希演算法的應用非常廣泛，在這里就介紹七點應用：

有很多著名的哈希加密演算法：MD5、SHA、DES...它們都是通過哈希進行加密的演算法。
對於加密的哈希演算法來說，有兩點十分重要：一是很難根據哈希值反推導出原始數據；二是散列沖突的概率要很小。
當然，哈希演算法不可能排除散列沖突的可能，這用數學中的 鴿巢原理 就可以很好解釋。以MD5演算法來說，得到的哈希值為一個 128 位的二進制數，它的數據容量最多為 2 ¹²⁸ bit，如果超過這個數據量，必然會出現散列沖突。
在加密解密領域沒有絕對安全的演算法，一般來說，只要解密的計算量極其龐大，我們就可以認為這種加密方法是較為安全的。

假設我們有100萬個圖片，如果我們在圖片中尋找某一個圖片是非常耗時的，這是我們就可以使用哈希演算法的原理為圖片設置唯一標識。比如，我們可以從圖片的二進制碼串開頭取100個位元組，從中間取100個位元組，從結尾取100個位元組，然後將它們合並，並使用哈希演算法計算得到一個哈希值，將其作為圖片的唯一標識。
使用這個唯一標識判斷圖片是否在圖庫中，這可以減少甚多工作量。

在傳輸消息的過程中，我們擔心通信數據被人篡改，這時就可以使用哈希函數進行數據校驗。比如BT協議中就使用哈希栓發進行數據校驗。

在散列表那一篇中我們就講過散列函數的應用，相比於其它應用，散列函數對於散列演算法沖突的要求低很多（我們可以通過開放定址法或鏈表法解決沖突），同時散列函數對於散列演算法是否能逆向解密也並不關心。
散列函數比較在意函數的執行效率，至於其它要求，在之前的我們已經講過，就不再贅述了。

接下來的三個應用主要是在分布式系統中的應用

復雜均衡的演算法很多，如何實現一個會話粘滯的負載均衡演算法呢？也就是說，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個伺服器上。

最簡單的辦法是我們根據客戶端的 IP 地址或會話 ID 創建一個映射關系。但是這樣很浪費內存，客戶端上線下線，伺服器擴容等都會導致映射失效，維護成本很大。

藉助哈希演算法，我們可以很輕松的解決這些問題：對客戶端的 IP 地址或會話 ID 計算哈希值，將取得的哈希值域伺服器的列表的大小進行取模運算，最後得到的值就是被路由到的伺服器的編號。

假設有一個非常大的日誌文件，裡面記錄了用戶的搜索關鍵詞，我們想要快速統計出每個關鍵詞被搜索的次數，該怎麼做呢？

分析一下，這個問題有兩個難點：一是搜索日誌很大，沒辦法放到一台機器的內存中；二是如果用一台機器處理這么大的數據，處理時間會很長。

針對這兩個難點，我們可以先對數據進行分片，然後使用多台機器處理，提高處理速度。具體思路：使用 n 台機器並行處理，從日誌文件中讀出每個搜索關鍵詞，通過哈希函數計算哈希值，然後用 n 取模，最終得到的值就是被分配的機器編號。
這樣，相同的關鍵詞被分配到了相同的機器上，不同機器只要記錄屬於自己那部分的關鍵詞的出現次數，最終合並不同機器上的結果即可。

針對這種海量數據的處理問題，我們都可以採用多機分布式處理。藉助這種分片思路，可以突破單機內存、CPU等資源的限制。

處理思路和上面出現的思路類似：對數據進行哈希運算，對機器數取模，最終將存儲數據（可能是硬碟存儲，或者是緩存分配）分配到不同的機器上。

你可以看一下上圖，你會發現之前存儲的數據在新的存儲規則下全部失效，這種情況是災難性的。面對這種情況，我們就需要使用一致性哈希演算法。

哈希演算法是應用非常廣泛的演算法，你可以回顧上面的七個應用感受一下。

其實在這里我想說的是一個思想： 用優勢彌補不足 。
例如，在計算機中，數據的計算主要依賴 CPU ，數據的存儲交換主要依賴內存。兩者一起配合才能實現各種功能，而兩者在性能上依然無法匹配，這種差距主要是： CPU運算性能對內存的要求遠高於現在的內存能提供的性能。
也就是說，CPU運算很快，內存相對較慢，為了抹平這種差距，工程師們想了很多方法。在我看來，散列表的使用就是利用電腦的高計算性能（優勢）去彌補內存速度（不足）的不足，你仔細思考散列表的執行過程，就會明白我的意思。

以上就是哈希的全部內容