算法進階（12）-分布式系統常見負載均衡算法

負載均衡這個話題比較大，一篇估計說不完，今天先來第一篇。

 一、負載均衡介紹

【百度百科】負載均衡，英文名稱為Load Balance，其含義就是指将負載（工作任務）進行平衡、分攤到多個操作單元上進行運作，例如FTP伺服器、Web伺服器、企業核心應用伺服器和其它主要任務伺服器等，進而協同完成工作任務。

負載均衡建構在原有網絡結構之上，它提供了一種透明且廉價有效的方法擴充伺服器和網絡裝置的帶寬、加強網絡資料處理能力、增加吞吐量、提高網絡的可用性和靈活性。

1.負載均衡分類

軟體負載均衡：是指在一台或多台​​伺服器​​​相應的​​作業系統​​上安裝一個或多個附加軟體來實作負載均衡，如DNS Load Balance，CheckPoint Firewall-1 ConnectControl等，

硬體負載均衡：是直接在​​伺服器​​​和外部網絡間安裝負載均衡裝置，這種裝置通常稱之為​​負載均衡器​​​，由于專門的裝置完成專門的任務，獨立于​​作業系統​​，整體性能得到大量提高，加上多樣化的負載均衡政策，智能化的流量管理，可達到最佳的負載均衡需求。

2.部署方式

負載均衡有三種部署方式：路由模式、橋接模式、服務直接傳回模式。路由模式部署靈活，約60%的使用者采用這種方式部署；橋接模式不改變現有的網絡架構；服務直接傳回（DSR）比較适合吞吐量大特别是内容分發的網絡應用。約30%的使用者采用這種模式。

3.均衡技術

1、基于DNS的負載均衡

由于在DNS伺服器中，可以為多個不同的位址配置相同的名字，最終查詢這個名字的客戶機将在解析這個名字時得到其中一個位址，是以這種代理方式是通過DNS服務中的随機名字解析域名和IP來實作負載均衡。

2、反向代理負載均衡（如Apache+JK2+Tomcat這種組合）

該種代理方式與普通的代理方式不同，标準代理方式是客戶使用代理通路多個外部Web伺服器，之是以被稱為反向代理模式是因為這種代理方式是多個客戶使用它通路内部Web伺服器，而非通路外部伺服器。

3、基于NAT（Network Address Translation）的負載均衡技術（如Linux VirtualServer，簡稱LVS）

該技術通過一個位址轉換網關将每個外部連接配接均勻轉換為不同的内部伺服器位址，是以外部網絡中的計算機就各自與自己轉換得到的位址上的伺服器進行通信，進而達到負載均衡的目的。其中網絡位址轉換網關位于外部位址和内部位址之間，不僅可以實作當外部客戶機通路轉換網關的某一外部位址時可以轉發到某一映射的内部的位址上，還可使内部位址的計算機能通路外部網絡。

二、負載均衡（排程）算法

在分布式系統中，多台伺服器同時提供一個服務，并統一到服務配置中心進行管理，消費者通過查詢服務配置中心，擷取到服務到位址清單，需要選取其中一台來發起RPC遠端調用。如何選擇，則取決于具體的負載均衡算法，對應于不同的場景，選擇的負載均衡算法也不盡相同。

現有的負載均衡算法主要分為靜态和動态兩類。靜态負載均衡算法以固定的機率配置設定任務，不考慮伺服器的狀态資訊，如輪轉算法、權重輪轉算法等；動态負載均衡算法以伺服器的實時負載狀态資訊來決定任務的配置設定，如最小連接配接法、權重最小連接配接法等。

1.輪循(Round Robin)

這種方法會将收到的請求循環配置設定到伺服器叢集中的每台機器，即有效伺服器。如果使用這種方式，所有的标記進入虛拟服務的伺服器應該有相近的資源容量以及負載形同的應用程式。如果所有的伺服器有相同或者相近的性能那麼選擇這種方式會使伺服器負載形同。基于這個前提，輪循排程是一個簡單而有效的配置設定請求的方式。然而對于伺服器不同的情況，選擇這種方式就意味着能力比較弱的伺服器也會在下一輪循環中接受輪循，即使這個伺服器已經不能再處理目前這個請求了。這可能導緻能力較弱的伺服器超載。

2.權重輪循(Weighted Round Robin)

這種算法解決了簡單輪循排程算法的缺點：傳入的請求按順序被配置設定到叢集中伺服器，但是會考慮提前為每台伺服器配置設定的權重。管理者隻是簡單的通過伺服器的處理能力來定義各台伺服器的權重。例如，能力最強的伺服器A給的權重是100，同時能力最低的伺服器給的權重是50。這意味着在伺服器B接收到第一個請求之前前，伺服器A會連續的接受到2個請求，以此類推。

3.最少連接配接數(Least Connection)

以上兩種方法都沒有考慮的是系統不能識别在給定的時間裡保持了多少連接配接。是以可能發生，伺服器B伺服器收到的連接配接比伺服器A少但是它已經超載，因為伺服器B上的使用者打開連接配接持續的時間更長。這就是說連接配接數即伺服器的負載是累加的。這種潛在的問題可以通過"最少連接配接數"算法來避免：傳入的請求是根據每台伺服器目前所打開的連接配接數來配置設定的。即活躍連接配接數最少的伺服器會自動接收下一個傳入的請求。接本上和簡單輪詢的原則相同：所有擁有虛拟服務的伺服器資源容量應該相近。值得注意的是，在流量率低的配置環境中，各伺服器的流量并不是相同的，會優先考慮第一台伺服器。這是因為，如果所有的伺服器是相同的，那麼第一個伺服器優先，直到第一台伺服器有連續的活躍流量，否則總是會優先選擇第一台伺服器。

4.最少連接配接數慢啟動時間(Least Connection Slow Start Time)

對最少連接配接數和帶權重的最小連接配接數排程方法來說，當一個伺服器剛加入線上環境是，可以為其配置一個時間段，在這段時間内連接配接數是有限制的而且是緩慢增加的。這為伺服器提供了一個'過渡時間'以保證這個伺服器不會因為剛啟動後因為配置設定的連接配接數過多而超載。這個值在L7配置界面設定。

5.權重最少連接配接(Weighted Least Connection)

如果伺服器的資源容量各不相同，那麼"權重最少連接配接"方法更合适：由管理者根據伺服器情況定制的權重所決定的活躍連接配接數一般提供了一種對伺服器非常平衡的利用，因為他它借鑒了最少連接配接和權重兩者的優勢。通常，這是一個非常公平的配置設定方式，因為它使用了連接配接數和伺服器權重比例;叢集中比例最低的伺服器自動接收下一個請求。但是請注意，在低流量情況中使用這種方法時，請參考"最小連接配接數"方法中的注意事項。

6.基于代理的自适應負載均衡(Agent Based Adaptive Balancing)

除了上述方法之外，負載主機包含一個自适用邏輯用來定時監測伺服器狀态和該伺服器的權重。對于非常強大的"基于代理的自适應負載均衡"方法來說，負載主機以這種方式來定時檢測所有伺服器負載情況：每台伺服器都必須提供一個包含檔案，這個檔案包含一個0~99的數字用來标明改伺服器的實際負載情況(0=空前，99=超載，101=失敗，102=管理者禁用)，而伺服器同構http get方法來擷取這個檔案;同時對叢集中伺服器來說，以二進制檔案形式提供自身負載情況也是該伺服器工作之一，然而，并沒有限制伺服器如何計算自身的負載情況。根據伺服器整體負載情況，有兩種政策可以選擇：在正常的操作中，排程算法通過收集的伺服器負載值和配置設定給該伺服器的連接配接數的比例計算出一個權重比例。是以，如果一個伺服器負載過大，權重會通過系統透明的作重新調整。和權重輪循排程方法一樣，不正确的配置設定可以被記錄下來使得可以有效的為不同伺服器配置設定不同的權重。然而，在流量非常低的環境下，伺服器報上來的負載值将不能建立一個有代表性的樣本;那麼基于這些值來配置設定負載的話将導緻失控以及指令震蕩。是以，在這種情況下更合理的做法是基于靜态的權重比來計算負載配置設定。當所有伺服器的負載低于管理者定義的下限時，負載主機就會自動切換為權重輪循方式來配置設定請求;如果負載大于管理者定義的下限，那麼負載主機又會切換回自适應方式。

7.固定權重(Fixed Weighted)

最高權重隻有在其他伺服器的權重值都很低時才使用。然而，如果最高權重的伺服器下降，則下一個最高優先級的伺服器将為用戶端服務。這種方式中每個真實伺服器的權重需要基于伺服器優先級來配置。

8.權重響應(Weighted Response)

流量的排程是通過權重輪循方式。權重輪循中所使用的權重是根據伺服器有效性檢測的響應時間來計算。每個有效性檢測都會被計時，用來标記它響應成功花了多長時間。但是需要注意的是，這種方式假定伺服器心跳檢測是基于機器的快慢，但是這種假設也許不總是能夠成立。所有伺服器在虛拟服務上的響應時間的總和加在一起，通過這個值來計算單個服務實體伺服器的權重;這個權重值大約每15秒計算一次。

9.源IP哈希(Source IP Hash)

這種方式通過生成請求源IP的哈希值，并通過這個哈希值來找到正确的真實伺服器。這意味着對于同一主機來說他對應的伺服器總是相同。使用這種方式，你不需要儲存任何源IP。但是需要注意，這種方式可能導緻伺服器負載不平衡。