負載均衡算法及手段

• 從ACID到CAP到BASE

• 2PC到3PC到Paxos到Raft到ISR

• 復制、分片和路由

• 副本更新策略

• 負載均衡算法及手段

序

本文主要講述負載均衡的一些基本東西。

相關知識點

冷備與熱備

• 冷備份(cool standby)，指配備平時不運行的備用設備，當運行設備發生故障時，使用備用設備替換。

• 熱備份(hot standby)，指在設備運行的同時運行備用設備，當運行設備發生故障時，能夠自動替換備用設備。

fail-over與fail-back

• fail-over，在空余結構中，停止運行設備，使用備用設備進行工作的過程稱為替換，英文稱為fail-over或者switch-over。

• fail-back，替換后再次恢復到原來的運行設備，也就是從運行狀態的備用設備再切換到原來的運行設備的過程，稱為回退，英文稱為fail-back或switch-back。

冗余類型

• 1.主備方式(Active-Standby)準備兩臺路由器，其中一臺作為正常運行業務的活躍設備(active)，也可以稱為主設備(master)或者首要設備(primary)。另一臺作為發生故障時替換的備用設備(standby)，也可以稱為備機(backup)、從設備(slave)、必要設備(secondary)。活躍設備和備用設備必須共享關于設備的設置信息。

• 2.雙活方式(Active-Active)準備兩臺路由器，其中一臺作為首要設備(primary)，另一臺作為次要設備(secondary)，二者同時運行來組成冗余結構。這種方式可以通過與負載均衡設備并用或者設置DNS、客戶端一側的路由信息來達到負載均衡的目的。

• 3.集群方式(Cluster)在主備方式或雙活方式中，使用3臺以上的硬件協同組成冗余結構的方式。

L2與L3交換機

• L2基于數據鏈路層，L3基于網絡層，具有IP分組與路由選擇功能。

• L2可以通過使用VLAN分割廣播域，但終端之間的數據幀交換必須位于同一VLAN范圍內。 不同VLAN上的終端如有相互通信需求，則必須使用路由器。

• L3交換機與路由器均可以實現跨VLAN路由，但L3交換機多用于在以太網構筑的Intranet內部轉發分組，而路由器則大多作為連接互聯網與Intranet內網之間的網關來使用。

L4與L7交換機

• L4交換機能夠支持到TCP層級訪問控制的交換機，稱為L4交換機。

• L7交換機能夠基于HTTP和HTTPS這類應用層L7參數進行負載均衡等操作的產品，稱為L7交換機。

負載均衡器

可以是專用設備，也可以是在通用服務器上運行的應用程序。 分散請求到擁有相同內容或提供相同服務的服務器。 專用設備一般只有以太網接口，可以說是多層交換機的一種。 負載均衡器一般會被分配虛擬IP地址，所有來自客戶端的請求都是針對虛擬IP地址完成的。負載均衡器通過負載均衡算法將來自客戶端的請求轉發到服務器的實際IP地址上。

負載均衡算法

private Map<String,Integer> serverMap = new HashMap<String,Integer>(){{
        put("192.168.1.100",1);
        put("192.168.1.101",1);
        put("192.168.1.102",4);
        put("192.168.1.103",1);
        put("192.168.1.104",1);
        put("192.168.1.105",3);
        put("192.168.1.106",1);
        put("192.168.1.107",2);
        put("192.168.1.108",1);
        put("192.168.1.109",1);
        put("192.168.1.110",1);
    }};

1.隨機算法

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

public void random(){
        List<String> keyList = new ArrayList<String>(serverMap.keySet());
        Random random = new Random();
        int idx = random.nextInt(keyList.size());
        String server = keyList.get(idx);
        System.out.println(server);
    }

• WeightRandom

public void weightRandom(){
        Set<String> keySet = serverMap.keySet();
        List<String> servers = new ArrayList<String>();
        for(Iterator<String> it = keySet.iterator();it.hasNext();){
            String server = it.next();
            int weithgt = serverMap.get(server);
            for(int i=0;i<weithgt;i++){
                servers.add(server);
            }
        }
        String server = null;
        Random random = new Random();
        int idx = random.nextInt(servers.size());
        server = servers.get(idx);
        System.out.println(server);
    }

2.輪詢及加權輪詢

• 輪詢(Round Robbin)當服務器群中各服務器的處理能力相同時，且每筆業務處理量差異不大時，最適合使用這種算法。 輪循，按公約后的權重設置輪循比率。存在慢的提供者累積請求問題，比如：第二臺機器很慢，但沒掛，當請求調到第二臺時就卡在那，久而久之，所有請求都卡在調到第二臺上。

private Integer pos = 0;
public void roundRobin(){
        List<String> keyList = new ArrayList<String>(serverMap.keySet());
        String server = null;
        synchronized (pos){
            if(pos > keyList.size()){
                pos = 0;
            }
            server = keyList.get(pos);
            pos++;
        }
        System.out.println(server);
    }

• 加權輪詢(Weighted Round Robbin)為輪詢中的每臺服務器附加一定權重的算法。比如服務器1權重1，服務器2權重2，服務器3權重3，則順序為1-2-2-3-3-3-1-2-2-3-3-3- ......

public void weightRoundRobin(){
        Set<String> keySet = serverMap.keySet();
        List<String> servers = new ArrayList<String>();
        for(Iterator<String> it = keySet.iterator();it.hasNext();){
            String server = it.next();
            int weithgt = serverMap.get(server);
            for(int i=0;i<weithgt;i++){
               servers.add(server);
            }
        }
        String server = null;
        synchronized (pos){
            if(pos > keySet.size()){
                pos = 0;
            }
            server = servers.get(pos);
            pos++;
        }
        System.out.println(server);
    }

3.最小連接及加權最小連接

• 最少連接(Least Connections)在多個服務器中，與處理連接數(會話數)最少的服務器進行通信的算法。即使在每臺服務器處理能力各不相同，每筆業務處理量也不相同的情況下，也能夠在一定程度上降低服務器的負載。

• 加權最少連接(Weighted Least Connection)為最少連接算法中的每臺服務器附加權重的算法，該算法事先為每臺服務器分配處理連接的數量，并將客戶端請求轉至連接數最少的服務器上。

4.哈希算法

• 普通哈希

public void hash(){
        List<String> keyList = new ArrayList<String>(serverMap.keySet());
        String remoteIp = "192.168.2.215";
        int hashCode = remoteIp.hashCode();
        int idx = hashCode % keyList.size();
        String server = keyList.get(Math.abs(idx));
        System.out.println(server);
    }

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

5.IP地址散列

通過管理發送方IP和目的地IP地址的散列，將來自同一發送方的分組(或發送至同一目的地的分組)統一轉發到相同服務器的算法。當客戶端有一系列業務需要處理而必須和一個服務器反復通信時，該算法能夠以流(會話)為單位，保證來自相同客戶端的通信能夠一直在同一服務器中進行處理。

6.URL散列

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

負載均衡算法的手段( DNS->數據鏈路層->IP層->Http層 )

1、DNS域名解析負載均衡( 延遲 )

利用DNS處理域名解析請求的同時進行負載均衡是另一種常用的方案。在DNS服務器中配置多個A記錄，如：www.mysite.com IN A 114.100.80.1、www.mysite.com IN A 114.100.80.2、www.mysite.com IN A 114.100.80.3.

每次域名解析請求都會根據負載均衡算法計算一個不同的IP地址返回，這樣A記錄中配置的多個服務器就構成一個集群，并可以實現負載均衡。

DNS域名解析負載均衡的優點是將負載均衡工作交給DNS，省略掉了網絡管理的麻煩，缺點就是DNS可能緩存A記錄，不受網站控制。

事實上，大型網站總是部分使用DNS域名解析，作為第一級負載均衡手段，然后再在內部做第二級負載均衡。

2、數據鏈路層負載均衡( LVS )

數據鏈路層負載均衡是指在通信協議的數據鏈路層修改mac地址進行負載均衡。

這種數據傳輸方式又稱作三角傳輸模式，負載均衡數據分發過程中不修改IP地址，只修改目的的mac地址，通過配置真實物理服務器集群所有機器虛擬IP和負載均衡服務器IP地址一樣，從而達到負載均衡，這種負載均衡方式又稱為直接路由方式（DR）.

在上圖中，用戶請求到達負載均衡服務器后，負載均衡服務器將請求數據的目的mac地址修改為真是WEB服務器的mac地址，并不修改數據包目標IP地址，因此數據可以正常到達目標WEB服務器，該服務器在處理完數據后可以經過網管服務器而不是負載均衡服務器直接到達用戶瀏覽器。

使用三角傳輸模式的鏈路層負載均衡是目前大型網站所使用的最廣的一種負載均衡手段。在linux平臺上最好的鏈路層負載均衡開源產品是LVS(linux virtual server)。

3、IP負載均衡( SNAT )

IP負載均衡：即在網絡層通過修改請求目標地址進行負載均衡。

用戶請求數據包到達負載均衡服務器后，負載均衡服務器在操作系統內核進行獲取網絡數據包，根據負載均衡算法計算得到一臺真實的WEB服務器地址，然后將數據包的IP地址修改為真實的WEB服務器地址，不需要通過用戶進程處理。真實的WEB服務器處理完畢后，相應數據包回到負載均衡服務器，負載均衡服務器再將數據包源地址修改為自身的IP地址發送給用戶瀏覽器。

這里的關鍵在于真實WEB服務器相應數據包如何返回給負載均衡服務器，一種是負載均衡服務器在修改目的IP地址的同時修改源地址，將數據包源地址改為自身的IP，即源地址轉換（SNAT），另一種方案是將負載均衡服務器同時作為真實物理服務器的網關服務器，這樣所有的數據都會到達負載均衡服務器。

IP負載均衡在內核進程完成數據分發，較反向代理均衡有更好的處理性能。但由于所有請求響應的數據包都需要經過負載均衡服務器，因此負載均衡的網卡帶寬成為系統的瓶頸。

4、HTTP重定向負載均衡( 少見 )

HTTP重定向服務器是一臺普通的應用服務器，其唯一的功能就是根據用戶的HTTP請求計算一臺真實的服務器地址，并將真實的服務器地址寫入HTTP重定向響應中（響應狀態嗎302）返回給瀏覽器，然后瀏覽器再自動請求真實的服務器。

這種負載均衡方案的優點是比較簡單，缺點是瀏覽器需要每次請求兩次服務器才能拿完成一次訪問，性能較差；使用HTTP302響應碼重定向，可能是搜索引擎判斷為SEO作弊，降低搜索排名。重定向服務器自身的處理能力有可能成為瓶頸。因此這種方案在實際使用中并不見多。

5、反向代理負載均衡( nginx )

傳統代理服務器位于瀏覽器一端，代理瀏覽器將HTTP請求發送到互聯網上。而反向代理服務器則位于網站機房一側，代理網站web服務器接收http請求。

反向代理的作用是保護網站安全，所有互聯網的請求都必須經過代理服務器，相當于在web服務器和可能的網絡攻擊之間建立了一個屏障。

除此之外，代理服務器也可以配置緩存加速web請求。當用戶第一次訪問靜態內容的時候，靜態內存就被緩存在反向代理服務器上，這樣當其他用戶訪問該靜態內容時，就可以直接從反向代理服務器返回，加速web請求響應速度，減輕web服務器負載壓力。

另外，反向代理服務器也可以實現負載均衡的功能。

由于反向代理服務器轉發請求在HTTP協議層面，因此也叫應用層負載均衡。優點是部署簡單，缺點是可能成功系統的瓶頸。

參考

• 圖解網絡硬件

• 分布式環境中的負載均衡策略

• 負載均衡調度算法

• Tengine ngx_http_sysguard_module 過載保護模塊使用

• Nginx 簡單的負載均衡配置示例[原創]