⑴ 分布式系統常用的一致性演算法有哪些
在做伺服器負載均衡時候可供選擇的負載均衡的演算法有很多，包括： 輪循演算法（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實現。點擊下載
⑵ lvs負載均衡（簡介，三種工作模式，四種常用演算法）
一，lvs簡介
LVS是linux Virtual Server的簡稱，也就是Linux虛擬伺服器，是一個由章文嵩博士發起的自由軟體項目，官方站點是： http://www.linuxvirtualserver.org 。現在LVS已經是Linux標准內核的一部分，在Linux2.4內核以前，使用LVS時必須重新編譯內核以支持LVS功能模塊，但是從Linux2.4內核心之後，已經完全內置了LVS的各個功能模塊，無需給內核打任何補丁，可以直接使用LVS提供的各種功能。使用LVS技術要達到的目標是：通過LVS提供的負載均衡技術和Linux操作系統實現一個高性能，高可用的伺服器群集，它具有良好的可靠性、可擴展性和可操作性。從而以兄棚野低廉的成本實現最優的服務性能。
二，三種工作模式
1、基於NAT的LVS模式負載均衡
也就是網路地址翻譯技術實現虛擬伺服器，當用戶請求到達調度器時，調度器將請求報文的目標地址（即虛擬IP地址）改寫成選定的Real Server地址，同時報文的目標埠也改成選定的Real Server的相應埠，***將報文請求發送到選定的Real Server。在伺服器端得到數據後，Real Server返回數據給用戶時，需要再次經過負載調度器將報文的源地址和源埠改成虛擬IP地址和相應埠，然後把數據發送給用戶，完成整個負載調度過程。可以看出，在NAT方式下，用戶請求和響應報文都必須經過Director Server地址重寫，當用戶請求越來越多時，調度器的處理能力將稱為瓶頸。
2，基於TUN的LVS負載均衡
也就是IP隧道技術實現虛擬伺服器。它的連接調度和管理與VS/NAT方式一樣，只是它的報文轉發方法不同，VS/TUN方式中，調度器採用IP隧道技術將用戶請求轉發到某個Real Server，而這個Real Server將直接響應用戶的請求，不再經過前端調度器，此外，對Real Server的地域位置沒有要求，可以和Director Server位於同一個網段，也可以是獨立的一個網路。因此，在TUN方式中，調度器將只處理用戶的報文請求，集群系統的吞吐量大大提高。
用的很少，圖省略
3，基於DR的LVS負載均衡
也就是用直接路由技術實現虛擬伺服器。它的連接調度和管理與VS/NAT和VS/TUN中的一樣，但它的報文轉發方法又有不同，VS/DR通過改寫請求報文的MAC地址，將請求發送到Real Server，而Real Server將響應直接返回給客戶，免去了VS/TUN中的IP隧道開銷。這種方式是三種負載調度機制中性能最好的，但是必須要求Director Server與Real Server都有一塊網卡連在同一物理網段上。
三，LVS負載均衡調度演算法
上面我們談到，負載調度器是根據各 個伺服器的負載情況，動和或態地選擇一台Real Server響應用戶請求，那麼動態選擇是如何實現呢，其實也就是我們這里要說的負載調度演算法，根據不同的網路服務需求和伺服器配置，IPVS實現了如下 八種負載調度演算法，這里我們詳細講述最常用的四種調度演算法，剩餘的四種調度演算法請參考其它資料。
3.1 輪叫調度（Round Robin）
「輪叫」調度也叫1:1調度，調度器通過羨喊「輪叫」調度演算法將外部用戶請求按順序1:1的分配到集群中的每個Real Server上，這種演算法平等地對待每一台Real Server，而不管伺服器上實際的負載狀況和連接狀態。
3.2 加權輪叫調度（Weighted Round Robin）
「加 權輪叫」調度演算法是根據Real Server的不同處理能力來調度訪問請求。可以對每台Real Server設置不同的調度權值，對於性能相對較好的Real Server可以設置較高的權值，而對於處理能力較弱的Real Server，可以設置較低的權值，這樣保證了處理能力強的伺服器處理更多的訪問流量。充分合理的利用了伺服器資源。同時，調度器還可以自動查詢Real Server的負載情況，並動態地調整其權值。
3.3 最少鏈接調度（Least Connections）
「最少連接」調度演算法動態地將網路請求調度到已建立的鏈接數最少的伺服器上。如果集群系統的真實伺服器具有相近的系統性能，採用「最小連接」調度演算法可以較好地均衡負載。
3.4 加權最少鏈接調度（Weighted Least Connections）
「加權最少鏈接調度」是「最少連接調度」的超集，每個服務節點可以用相應的權值表示其處理能力，而系統管理員可以動態的設置相應的權值，預設權值為1，加權最小連接調度在分配新連接請求時盡可能使服務節點的已建立連接數和其權值成正比。
其它四種調度演算法分別為：基於局部性的最少鏈接（Locality-Based Least Connections）、帶復制的基於局部性最少鏈接（Locality-Based Least Connections with Replication）、目標地址散列（Destination Hashing）和源地址散列（Source Hashing），對於這四種調度演算法的含義，本文不再講述，如果想深入了解這其餘四種調度策略的話，可以登陸LVS中文站點 zh.linuxvirtualserver.org，查閱更詳細的信息。
⑶ 多台異地伺服器如何實現負載均衡
一般用的就用簡單的輪詢就好了
調度演算法
靜態方法：僅根據演算法本身實現調度；實現起點公平，不管伺服器當前處理多少請求，分配的數量一致
動態方法：根據演算法及後端RS當前的負載狀況實現調度；不管以前分了多少，只看分配的結果是不是公平
靜態調度演算法(static Sche)（4種）:
(1)rr (Round Robin) :輪叫,輪詢
說明：輪詢調度演算法的原理是每一次把來自用戶的請求輪流分配給內部中的伺服器，從1開始，直到N(內部伺服器個數)，然後重新開始循環。演算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。缺點：是不考慮每台伺服器的處理能力。
(2)wrr (Weight Round Robin) :加權輪詢(以權重之間的比例實現在各主機之間進行調度)
說明：由於每台伺服器的配置、安裝的業務應用等不同，其處理能力會不一樣。所以，我們根據伺服器的不同處理能力，給每個伺服器分配不同的權值，使其能夠接受相應權值數的服務請求。
(3)sh (Source Hashing) : 源地址hash實現會話綁定sessionaffinity
說明：簡單的說就是有將同一客戶端的請求發給同一個real server,源地址散列調度演算法正好與目標地址散列調度演算法相反，它根據請求的源IP地址，作為散列鍵（Hash Key）從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的並且沒有超負荷，將請求發送到該伺服器，否則返回空。它採用的散列函數與目標地址散列調度演算法的相同。它的演算法流程與目標地址散列調度演算法的基本相似，除了將請求的目標IP地址換成請求的源IP地址。
(4)dh : (Destination Hashing) : 目標地址hash
說明：將同樣的請求發送給同一個server,一般用於緩存伺服器，簡單的說，LB集群後面又加了一層，在LB與realserver之間加了一層緩存伺服器，當一個客戶端請求一個頁面時,LB發給cache1,當第二個客戶端請求同樣的頁面時，LB還是發給cache1,這就是我們所說的，將同樣的請求發給同一個server,來提高緩存的命中率。目標地址散列調度演算法也是針對目標IP地址的負載均衡，它是一種靜態映射演算法，通過一個散列（Hash）函數將一個目標IP地址映射到一台伺服器。目標地址散列調度演算法先根據請求的目標IP地址，作為散列鍵（Hash Key）從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的且未超載，將請求發送到該伺服器，否則返回空。
動態調度演算法(dynamic Sche)（6種）:
(1)lc (Least-Connection Scheling): 最少連接
說明：最少連接調度演算法是把新的連接請求分配到當前連接數最小的伺服器，最小連接調度是一種動態調度短演算法，它通過伺服器當前所活躍的連接數來估計伺服器的負載均衡，調度器需要記錄各個伺服器已建立連接的數目，當一個請求被調度到某台伺服器，其連接數加1，當連接中止或超時，其連接數減一，在系統實現時，我們也引入當伺服器的權值為0時，表示該伺服器不可用而不被調度。此演算法忽略了伺服器的性能問題，有的伺服器性能好，有的伺服器性能差，通過加權重來區分性能，所以有了下面演算法wlc。
簡單演算法：active*256+inactive (誰的小，挑誰)
(2)wlc (Weighted Least-Connection Scheling):加權最少連接
加權最小連接調度演算法是最小連接調度的超集，各個伺服器用相應的權值表示其處理性能。伺服器的預設權值為1，系統管理員可以動態地設置伺服器的許可權，加權最小連接調度在調度新連接時盡可能使伺服器的已建立連接數和其權值成比例。由於伺服器的性能不同，我們給性能相對好的伺服器，加大權重，即會接收到更多的請求。
簡單演算法：（active*256+inactive）/weight（誰的小，挑誰）
(3)sed (shortest expected delay scheling):最少期望延遲
說明：不考慮非活動連接，誰的權重大，我們優先選擇權重大的伺服器來接收請求，但會出現問題，就是權重比較大的伺服器會很忙，但權重相對較小的伺服器很閑，甚至會接收不到請求，所以便有了下面的演算法nq。
基於wlc演算法，簡單演算法：（active+1)*256/weight （誰的小選誰）
(4).nq (Never Queue Scheling): 永不排隊
說明：在上面我們說明了，由於某台伺服器的權重較小，比較空閑，甚至接收不到請求，而權重大的伺服器會很忙，所此演算法是sed改進，就是說不管你的權重多大都會被分配到請求。簡單說，無需隊列，如果有台real server的連接數為0就直接分配過去，不需要在進行sed運算。
(5).LBLC(Locality-Based Least Connections) :基於局部性的最少連接
說明：基於局部性的最少連接演算法是針對請求報文的目標IP地址的負載均衡調度，主要用於Cache集群系統，因為Cache集群中客戶請求報文的目標IP地址是變化的，這里假設任何後端伺服器都可以處理任何請求，演算法的設計目標在伺服器的負載基本平衡的情況下，將相同的目標IP地址的請求調度到同一個台伺服器，來提高伺服器的訪問局部性和主存Cache命中率，從而調整整個集群系統的處理能力。
(6).LBLCR(Locality-Based Least Connections with Replication) :基於局部性的帶復制功能的最少連接
說明：基於局部性的帶復制功能的最少連接調度演算法也是針對目標IP地址的負載均衡，該演算法根據請求的目標IP地址找出該目標IP地 址對應的伺服器組，按「最小連接」原則從伺服器組中選出一台伺服器，若伺服器沒有超載，將請求發送到該伺服器；若伺服器超載，則按「最小連接」原則從這個集群中選出一台伺服器，將該伺服器加入到伺服器組中，將請求發送到該伺服器。同時，當該伺服器組有一段時間沒有被修改，將最忙的伺服器從伺服器組中刪除， 以降低復制的程度。
⑷ 如何實現負載均衡，哪些演算法可以實現
1、輪詢調度
輪詢調度演算法就是以輪詢的方式依次將請求調度到不同的伺服器，即每次調度執行i = (i + 1) mod n，並選出第i台伺服器。演算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。
2、最小連接調度
最小連接調度演算法是把新的連接請求分配到當前連接數最小的伺服器。最小連接調度是一種動態調度演算法，它通過伺服器當前所活躍的連接數來估計伺服器的負載情況。
在實際實現過程中，一般會為每台伺服器設定一個權重值，這就是加權最小連接
3、 基於局部性的最少鏈接(LBLC)
基於局部性的最少鏈接調度(以下簡稱為LBLC)演算法是針對請求報文的目標IP地址的負載均衡調度，目前主要用於Cache集群系統，因為在Cache集群中客戶請求報文的目標IP地址是變化的。
LBLC調度演算法先根據請求的目標IP地址找出該目標IP地址最近使用的伺服器，若該伺服器是可用的且沒有超載，將請求發送到該伺服器; 若伺服器不存在，或伺服器超載或有伺服器處於其一半的工作負載，則用「最少鏈接」的原則選出一個可用的伺服器，將請求發送到該伺服器。
4、帶復制的基於局部性最少鏈接(LBLCR)
帶復制的基於局部性最少鏈接調度以下簡稱為LBLCR)演算法也是針對目標IP地址的負載均衡，目前主要用於Cache集群系統。它與LBLC演算法的不同之處是它要維護從一個目標IP地址到一組伺服器的映射，而LBLC演算法維護從一個目標IP地址到一台伺服器的映射。
LBLCR調度演算法將「熱門」站點映射到一組Cache伺服器(伺服器集合)，當該「熱門」站點的請求負載增加時，會增加集合里的Cache伺服器，來處理不斷增長的負載; 當該「熱門」站點的請求負載降低時，會減少集合里的Cache伺服器數目。
5、目標地址散列調度
目標地址散列調度演算法是針對目標IP地址的負載均衡，但它是一種靜態映射演算法，通過一個散列(Hash)函數將一個目標IP地址映射到一台伺服器。
目標地址散列調度演算法先根據請求的目標IP地址，作為散列從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的且未超載，將請求發送到該伺服器，否則返回空。
6、 源地址散列調度
和目標地址散列調度類似，唯一的區別是按照源地址為散列函數的散列鍵。
⑸ bbo有哪些負載均衡演算法怎麼實現的負載均衡演算法bbo有幾層
常見的有LVS、Nginx和HAProxy，者者介紹分別如下：
LVS：使用集群技術和Linux操作系統實現一個高性能、高可用的伺服器，它具有很好的可伸縮性（Scalability)、可靠性（Reliability)和可管理性（Manageability)，感謝章文嵩博士為我們提供如此強大實用的開源軟體。
LVS的特點是：
1、抗負載能力強、是工作在網路4層之上僅作分發之用，沒有流量的產生，這個特點也決定了它在負載均衡軟體里的性能最強的；
2、配置性比較低，這是一個缺點也是一個優點，因為沒有可太多配置的東西，所以並不需要太多接觸，大大減少了人為出錯的幾率；
3、工作穩定，自身有完整的雙機熱備方案；
4、無流量，保證了均衡器IO的性能不會收到大流量的影響；
5、應用范圍比較廣，可以對所有應用做負載均衡；
6、軟體本身不支持正則處理，不能做動靜分離。
Nginx的特點是：
1、工作在網路的7層之上，可以針對http應用做一些分流的策略；
2、Nginx對網路的依賴非常小；
3、Nginx安裝和配置比較簡單，測試起來比較方便；
4、可以承擔高的負載壓力且穩定，一般能支撐超過幾萬次的並發量；
5、Nginx可以通過埠檢測到伺服器內部的故障，比如根據伺服器處理網頁返回的狀態碼、超時等等；
6、Nginx僅能支持http和Email；
HAProxy的特點是：
1、HAProxy是支持虛擬主機的；
2、能夠補充Nginx的一些缺點比如Session的保持，Cookie的引導等工作；
3、支持url檢測後端的伺服器出問題的檢測會有很好的幫助；
4、它跟LVS一樣，本身僅僅就只是一款負載均衡軟體；
5、HAProxy可以對Mysql讀進行負載均衡，對後端的MySQL節點進行檢測和負載均衡，不過在後端的MySQL slaves數量超過10台時性能不如LVS；
6、HAProxy的演算法多；
⑹ 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/