㈠ 分布式系統常用的一致性演算法有哪些
在做伺服器負載均衡時候可供選擇的負載均衡的演算法有很多，包括： 輪循演算法（Round Robin）、哈希演算法（HASH）、最少連接演算法（Least Connection）、響應速度演算法（Response Time）、加權法（Weighted ）等。其中哈希演算法是最為常用的演算法. 典型的應用場景是： 有N台伺服器提供緩存服務，需要對伺服器進行負載均衡，將請求平均分發到每台伺服器上，每台機器負責1/N的服務。 常用的演算法是對hash結果取余數 (hash() mod N)：對機器編號從0到N-1，按照自定義的hash()演算法，對每個請求的hash()值按N取模，得到余數i，然後將請求分發到編號為i的機器。但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；如果新增一台機器，會有N /(N+1)的伺服器的緩存數據需要進行重新計算。對於系統而言，這通常是不可接受的顛簸（因為這意味著大量緩存的失效或者數據需要轉移）。那麼，如何設計一個負載均衡策略，使得受到影響的請求盡可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都採用了Consistent Hashing演算法，可以說Consistent Hashing 是分布式系統負載均衡的首選演算法。 1、Consistent Hashing演算法描述 下面以Memcached中的Consisten Hashing演算法為例說明。 由於hash演算法結果一般為unsigned int型，因此對於hash函數的結果應該均勻分布在[0,232-1]間，如果我們把一個圓環用232 個點來進行均勻切割，首先按照hash(key)函數算出伺服器（節點）的哈希值， 並將其分布到0～232的圓上。 用同樣的hash(key)函數求出需要存儲數據的鍵的哈希值，並映射到圓上。然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器（節點）上。 Consistent Hashing原理示意圖 新增一個節點的時候，只有在圓環上新增節點逆時針方向的第一個節點的數據會受到影響。刪除一個節點的時候，只有在圓環上原來刪除節點順時針方向的第一個節點的數據會受到影響，因此通過Consistent Hashing很好地解決了負載均衡中由於新增節點、刪除節點引起的hash值顛簸問題。 Consistent Hashing添加伺服器示意圖 虛擬節點（virtual nodes）：之所以要引進虛擬節點是因為在伺服器（節點）數較少的情況下（例如只有3台伺服器），通過hash(key)算出節點的哈希值在圓環上並不是均勻分布的（稀疏的），仍然會出現各節點負載不均衡的問題。虛擬節點可以認為是實際節點的復製品（replicas），本質上與實際節點實際上是一樣的（key並不相同）。引入虛擬節點後，通過將每個實際的伺服器（節點）數按照一定的比例(例如200倍)擴大後並計算其hash(key)值以均勻分布到圓環上。在進行負載均衡時候，落到虛擬節點的哈希值實際就落到了實際的節點上。由於所有的實際節點是按照相同的比例復製成虛擬節點的州胡氏，因此解決了節點數較少的情況下哈希值在圓環上均勻分布的問題。 虛擬節點對Consistent Hashing結果的影響 從上圖可以看出，在節點數為10個的情況下，每個實際節點的虛擬節點數為實際做團節點的100-200倍的時候，結果還是很均衡的。 第3段中有這些文字：「但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法冊散得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；」 為何是 (N-1)/N 呢？解釋如下： 比如有 3 台機器，hash值 1-6 在這3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果掛掉一台，只剩兩台，模數取 2 ，那麼分布情況就變成： host 1: 1 3 5 host 2: 2 4 6 可以看到，還在數據位置不變的只有2個： 1，2，位置發生改變的有4個，占共6個數據的比率是 4/6 = 2/3這樣的話，受影響的數據太多了，勢必太多的數據需要重新從 DB 載入到 cache 中，嚴重影響性能 【consistent hashing 的辦法】 上面提到的 hash 取模，模數取的比較小，一般是負載的數量，而 consistent hashing 的本質是將模數取的比較大，為 2的32次方減1，即一個最大的 32 位整數。然後，就可以從容的安排數據導向了，那個圖還是挺直觀的。 以下部分為一致性哈希演算法的一種PHP實現。點擊下載
㈡ 負載均衡演算法 — 輪詢
在分布式系統中，為了實現負載均衡，必然會涉及到負載調度演算法，如 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}。對於神秘的平滑加權輪詢演算法，我將在後續文章中詳細介紹它的原理和實現。
輪詢演算法是最簡單的調度演算法，因為它無需記錄當前所有連接的狀態，所以它是一種 無狀態 的調度演算法，這些特性使得它應用較廣。
輪詢調度演算法並不能動態感知每個實例的負載，它完全依賴於我們的工程經驗，人為配置權重來實現基本的負載均衡，並不能保證服務的高可用性。若服務的某些實例因其他原因負載突然加重，輪詢調度還是會一如既往地分配請求給這個實例，因此可能會形成小面積的宕機，導致服務的局部不可用。
相關文章 »