深入淺出負載均衡

作者:vivo 互聯網團隊 - Zhang Peng

一、負載均衡簡介

1.1. 大型網站面臨的挑戰

大型網站都要面對龐大的用戶量,高併發,海量數據等挑戰。爲了提升系統整體的性能,可以採用垂直擴展和水平擴展兩種方式。

垂直擴展:在網站發展早期,可以從單機的角度通過增加硬件處理能力,比如 CPU 處理能力,內存容量,磁盤等方面,實現服務器處理能力的提升。但是,單機是有性能瓶頸的,一旦觸及瓶頸,再想提升,付出的成本和代價會極高。這顯然不能滿足大型分佈式系統(網站)所有應對的大流量,高併發,海量數據等挑戰。

水平擴展:通過集羣來分擔大型網站的流量。集羣中的應用服務器(節點)通常被設計成無狀態,用戶可以請求任何一個節點,這些節點共同分擔訪問壓力。水平擴展有兩個要點:

1.2. 什麼是負載均衡

負載均衡(Load Balance,簡稱 LB)是高併發、高可用系統必不可少的關鍵組件,目標是 盡力將網絡流量平均分發到多個服務器上,以提高系統整體的響應速度和可用性。

負載均衡的主要作用如下:

**高併發:**負載均衡通過算法調整負載,盡力均勻的分配應用集羣中各節點的工作量,以此提高應用集羣的併發處理能力(吞吐量)。

**伸縮性:**添加或減少服務器數量,然後由負載均衡進行分發控制。這使得應用集羣具備伸縮性。

**高可用:**負載均衡器可以監控候選服務器,當服務器不可用時,自動跳過,將請求分發給可用的服務器。這使得應用集羣具備高可用的特性。

**安全防護:**有些負載均衡軟件或硬件提供了安全性功能,如:黑白名單處理、防火牆,防 DDos 攻擊等。

二、負載均衡的分類

支持負載均衡的技術很多,我們可以通過不同維度去進行分類。

2.1 載體維度分類

從支持負載均衡的載體來看,可以將負載均衡分爲兩類:硬件負載均衡、軟件負載均衡

2.1.1 硬件負載均衡

硬件負載均衡,一般是在定製處理器上運行的獨立負載均衡服務器,價格昂貴,土豪專屬。硬件負載均衡的主流產品有: F5 和 A10。

硬件負載均衡的 優點:

硬件負載均衡的 缺點:

2.1.2 軟件負載均衡

軟件負載均衡,應用最廣泛,無論大公司還是小公司都會使用。

軟件負載均衡從軟件層面實現負載均衡,一般可以在任何標準物理設備上運行。

軟件負載均衡的 主流產品 有:Nginx、HAProxy、LVS

軟件負載均衡的 優點:

軟件負載均衡的 缺點:

2.2 網絡通信分類

軟件負載均衡從通信層面來看,又可以分爲四層和七層負載均衡。

  1. 七層負載均衡:就是可以根據訪問用戶的 HTTP 請求頭、URL 信息將請求轉發到特定的主機。
  1. 四層負載均衡:基於 IP 地址和端口進行請求的轉發。

2.2.1 DNS 負載均衡

DNS 負載均衡一般用於互聯網公司,複雜的業務系統不適合使用。大型網站一般使用 DNS 負載均衡作爲 第一級負載均衡手段,然後在內部使用其它方式做第二級負載均衡。DNS 負載均衡屬於七層負載均衡。

DNS 即 域名解析服務,是 OSI 第七層網絡協議。DNS 被設計爲一個樹形結構的分佈式應用,自上而下依次爲:根域名服務器,一級域名服務器,二級域名服務器,... ,本地域名服務器。顯然,如果所有數據都存儲在根域名服務器,那麼 DNS 查詢的負載和開銷會非常龐大。

因此,DNS 查詢相對於 DNS 層級結構,是一個逆向的遞歸流程,DNS 客戶端依次請求本地 DNS 服務器,上一級 DNS 服務器,上上一級 DNS 服務器,... ,根 DNS 服務器(又叫權威 DNS 服務器),一旦命中,立即返回。爲了減少查詢次數,每一級 DNS 服務器都會設置 DNS 查詢緩存。

DNS 負載均衡的工作原理就是:基於 DNS 查詢緩存,按照負載情況返回不同服務器的 IP 地址。

圖片

DNS 重定向的 優點:

使用簡單:負載均衡工作,交給 DNS 服務器處理,省掉了負載均衡服務器維護的麻煩

提高性能:可以支持基於地址的域名解析,解析成距離用戶最近的服務器地址(類似 CDN 的原理),可以加快訪問速度,改善性能;

DNS 重定向的 缺點:

可用性差:DNS 解析是多級解析,新增 / 修改 DNS 後,解析時間較長;解析過程中,用戶訪問網站將失敗;

擴展性低:DNS 負載均衡的控制權在域名商那裏,無法對其做更多的改善和擴展;

維護性差:也不能反映服務器的當前運行狀態;支持的算法少;不能區分服務器的差異(不能根據系統與服務的狀態來判斷負載)。

2.2.2 HTTP 負載均衡

HTTP 負載均衡是基於 HTTP 重定向實現的。HTTP 負載均衡屬於七層負載均衡。

HTTP 重定向原理是:根據用戶的 HTTP 請求計算出一個真實的服務器地址,將該服務器地址寫入 HTTP 重定向響應中,返回給瀏覽器,由瀏覽器重新進行訪問。

圖片

HTTP 重定向的優點:方案簡單。

HTTP 重定向的 缺點:

性能較差:每次訪問需要兩次請求服務器,增加了訪問的延遲。

降低搜索排名:使用重定向後,搜索引擎會視爲 SEO 作弊。

如果負載均衡器宕機,就無法訪問該站點。

由於其缺點比較明顯,所以這種負載均衡策略實際應用較少。

2.2.3 反向代理負載均衡

反向代理(Reverse Proxy)方式是指以 代理服務器 來接受網絡請求,然後 將請求轉發給內網中的服務器,並將從內網中的服務器上得到的結果返回給網絡請求的客戶端。反向代理負載均衡屬於七層負載均衡。

反向代理服務的主流產品:Nginx、Apache

正向代理與反向代理有什麼區別?

正向代理:發生在 客戶端,是由用戶主動發起的。翻牆軟件就是典型的正向代理,客戶端通過主動訪問代理服務器,讓代理服務器獲得需要的外網數據,然後轉發回客戶端。

反向代理:發生在 服務端,用戶不知道代理的存在。

圖片

反向代理是如何實現負載均衡的呢?以 Nginx 爲例,如下所示:

圖片

首先,在代理服務器上設定好負載均衡規則。然後,當收到客戶端請求,反向代理服務器攔截指定的域名或 IP 請求,根據負載均衡算法,將請求分發到候選服務器上。其次,如果某臺候選服務器宕機,反向代理服務器會有容錯處理,比如分發請求失敗 3 次以上,將請求分發到其他候選服務器上。

反向代理的 優點:

  1. 多種負載均衡算法:支持多種負載均衡算法,以應對不同的場景需求。

  2. 可以監控服務器:基於 HTTP 協議,可以監控轉發服務器的狀態,如:系統負載、響應時間、是否可用、連接數、流量等,從而根據這些數據調整負載均衡的策略。

反向代理的 缺點:

  1. 額外的轉發開銷:反向代理的轉發操作本身是有性能開銷的,可能會包括創建連接,等待連接響應,分析響應結果等操作。
  1. 增加系統複雜度:反向代理常用於做分佈式應用的水平擴展,但反向代理服務存在以下問題,爲了解決以下問題會給系統整體增加額外的複雜度和運維成本:

2.2.4 IP 負載均衡

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

圖片

如上圖所示,IP 均衡處理流程大致爲:

客戶端請求 192.168.137.10,由負載均衡服務器接收到報文。

負載均衡服務器根據算法選出一個服務節點 192.168.0.1,然後將報文請求地址改爲該節點的 IP。

真實服務節點收到請求報文,處理後,返回響應數據到負載均衡服務器。

負載均衡服務器將響應數據的源地址改負載均衡服務器地址,返回給客戶端。

IP 負載均衡在內核進程完成數據分發,較反向代理負載均衡有更好的從處理性能。但是,由於所有請求響應都要經過負載均衡服務器,集羣的吞吐量受制於負載均衡服務器的帶寬。

2.2.5 數據鏈路層負載均衡

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

圖片

在 Linux 平臺上最好的鏈路層負載均衡開源產品是 LVS (Linux Virtual Server)。LVS 是基於 Linux 內核中 netfilter 框架實現的負載均衡系統。netfilter 是內核態的 Linux 防火牆機制,可以在數據包流經過程中,根據規則設置若干個關卡(hook 函數)來執行相關的操作。

LVS 的工作流程大致如下:

當用戶訪問 www.sina.com.cn 時,用戶數據通過層層網絡,最後通過交換機進入 LVS 服務器網卡,並進入內核網絡層。

進入 PREROUTING 後經過路由查找,確定訪問的目的 VIP 是本機 IP 地址,所以數據包進入到 INPUT 鏈上

IPVS 是工作在 INPUT 鏈上,會根據訪問的 vip+port 判斷請求是否 IPVS 服務,如果是則調用註冊的 IPVS HOOK 函數,進行 IPVS 相關主流程,強行修改數據包的相關數據,並將數據包發往 POSTROUTING 鏈上。

POSTROUTING 上收到數據包後,根據目標 IP 地址(後端服務器),通過路由選路,將數據包最終發往後端的服務器上。

開源 LVS 版本有 3 種工作模式,每種模式工作原理截然不同,說各種模式都有自己的優缺點,分別適合不同的應用場景,不過最終本質的功能都是能實現均衡的流量調度和良好的擴展性。主要包括三種模式:DR 模式、NAT 模式、Tunnel 模式。

三、負載均衡算法

負載均衡器的實現可以分爲兩個部分:

根據負載均衡算法在候選服務器列表選出一個服務器;

將請求數據發送到該服務器上。

負載均衡算法是負載均衡服務核心中的核心。負載均衡產品多種多樣,但是各種負載均衡算法原理是共性的。負載均衡算法有很多種,分別適用於不同的應用場景,本文僅介紹最爲常見的負載均衡算法的特性及原理:輪詢、隨機、最小活躍數、源地址哈希、一致性哈希

**注:**負載均衡算法的實現,推薦閱讀 Dubbo 官方負載均衡算法說明 ,源碼講解非常詳細,非常值得借鑑。

3.1 隨機

3.1.1 隨機算法

隨機(Random) 算法將請求隨機分發到候選服務器。

隨機算法 適合服務器硬件相同的場景。學習過概率論的都知道,調用量較小的時候,可能負載並不均勻,調用量越大,負載越均衡。

圖片

【示例】隨機算法實現示例

負載均衡接口

public interface LoadBalance<N extends Node> {
    N select(List<N> nodes, String ip);
}

負載均衡抽象類

public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
    @Override
    public N select(List<N> nodes, String ip) {
        if (CollectionUtil.isEmpty(nodes)) {
            return null;
        }
        // 如果 nodes 列表中僅有一個 node,直接返回即可,無需進行負載均衡
        if (nodes.size() == 1) {
            return nodes.get(0);
        }
        return doSelect(nodes, ip);
    }
    protected abstract N doSelect(List<N> nodes, String ip);
}

服務器節點類

public class Node implements Comparable<Node> {
    protected String url;
    protected Integer weight;
    protected Integer active;
    // ...
}

隨機算法實現

public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = new Random();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        // 在列表中隨機選取一個節點
        int index = random.nextInt(nodes.size());
        return nodes.get(index);
    }
}

3.1.2 加權隨機算法

加權隨機(Weighted Rando****m) 算法在隨機算法的基礎上,按照概率調整權重,進行負載分配。

【示例】加權隨機算法實現示例

public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = ThreadLocalRandom.current();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        AtomicInteger totalWeight = new AtomicInteger(0);
        for (N node : nodes) {
            Integer weight = node.getWeight();
            totalWeight.getAndAdd(weight);
        }
        if (totalWeight.get() > 0) {
            int offset = random.nextInt(totalWeight.get());
            for (N node : nodes) {
                // 讓隨機值 offset 減去權重值
                offset -= node.getWeight();
                if (offset < 0) {
                    // 返回相應的 Node
                    return node;
                }
            }
        }
        // 直接隨機返回一個
        return nodes.get(random.nextInt(length));
    }
}

3.2 輪詢

3.2.1 輪詢算法

**輪詢(Round Robin)**算法的策略是:將請求依次分發到候選服務器。

如下圖所示,負載均衡器收到來自客戶端的 6 個請求,(1, 3, 5) 的請求會被髮送到服務器 1,(2, 4, 6) 的請求會被髮送到服務器 2。

圖片

該算法適合場景:各服務器處理能力相近,且每個事務工作量差異不大。如果存在較大差異,那麼處理較慢的服務器就可能會積壓請求,最終無法承擔過大的負載。

圖片

【示例】輪詢算法示例

輪詢負載均衡算法實現

public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final AtomicInteger position = new AtomicInteger(0);
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        // 如果位置值已經等於節點數,重置爲 0
        position.compareAndSet(length, 0);
        N node = nodes.get(position.get());
        position.getAndIncrement();
        return node;
    }
}

3.2.2 加權輪詢算法

**加權輪詢(Weighted Round Robbin)**算法在輪詢算法的基礎上,增加了權重屬性來調節轉發服務器的請求數目。性能高、處理速度快的節點應該設置更高的權重,使得分發時優先將請求分發到權重較高的節點上。

如下圖所示,服務器 A 設置權重爲 5,服務器 B 設置權重爲 1,負載均衡器收到來自客戶端的 6 個請求,那麼 (1, 2, 3, 4, 5) 請求會被髮送到服務器 A,(6) 請求會被髮送到服務器 B。

圖片

【示例】加權輪詢算法實現示例

以下實現基於 Dubbo 加權輪詢算法做了一些簡化。

public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    /**
     * 60秒
     */
    private static final int RECYCLE_PERIOD = 60000;
    /**
     * Node hashcode 到 WeightedRoundRobin 的映射關係
     */
    private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
    /**
     * 原子更新鎖
     */
    private AtomicBoolean updateLock = new AtomicBoolean();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;
        // 獲取當前時間
        long now = System.currentTimeMillis();
        N selectedNode = null;
        WeightedRoundRobin selectedWRR = null;
        // 下面這個循環主要做了這樣幾件事情:
        //   1. 遍歷 Node 列表,檢測當前 Node 是否有相應的 WeightedRoundRobin,沒有則創建
        //   2. 檢測 Node 權重是否發生了變化,若變化了,則更新 WeightedRoundRobin 的 weight 字段
        //   3. 讓 current 字段加上自身權重,等價於 current += weight
        //   4. 設置 lastUpdate 字段,即 lastUpdate = now
        //   5. 尋找具有最大 current 的 Node,以及 Node 對應的 WeightedRoundRobin,
        //      暫存起來,留作後用
        //   6. 計算權重總和
        for (N node : nodes) {
            int hashCode = node.hashCode();
            WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode);
            int weight = node.getWeight();
            if (weight < 0) {
                weight = 0;
            }
            // 檢測當前 Node 是否有對應的 WeightedRoundRobin,沒有則創建
            if (weightedRoundRobin == null) {
                weightedRoundRobin = new WeightedRoundRobin();
                // 設置 Node 權重
                weightedRoundRobin.setWeight(weight);
                // 存儲 url 唯一標識 identifyString 到 weightedRoundRobin 的映射關係
                weightMap.putIfAbsent(hashCode, weightedRoundRobin);
                weightedRoundRobin = weightMap.get(hashCode);
            }
            // Node 權重不等於 WeightedRoundRobin 中保存的權重,說明權重變化了,此時進行更新
            if (weight != weightedRoundRobin.getWeight()) {
                weightedRoundRobin.setWeight(weight);
            }
            // 讓 current 加上自身權重,等價於 current += weight
            long current = weightedRoundRobin.increaseCurrent();
            // 設置 lastUpdate,表示近期更新過
            weightedRoundRobin.setLastUpdate(now);
            // 找出最大的 current
            if (current > maxCurrent) {
                maxCurrent = current;
                // 將具有最大 current 權重的 Node 賦值給 selectedNode
                selectedNode = node;
                // 將 Node 對應的 weightedRoundRobin 賦值給 selectedWRR,留作後用
                selectedWRR = weightedRoundRobin;
            }
            // 計算權重總和
            totalWeight += weight;
        }
        // 對 weightMap 進行檢查,過濾掉長時間未被更新的節點。
        // 該節點可能掛了,nodes 中不包含該節點,所以該節點的 lastUpdate 長時間無法被更新。
        // 若未更新時長超過閾值後,就會被移除掉,默認閾值爲60秒。
        if (!updateLock.get() && nodes.size() != weightMap.size()) {
            if (updateLock.compareAndSet(false, true)) {
                try {
                    // 遍歷修改,即移除過期記錄
                    weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
                } finally {
                    updateLock.set(false);
                }
            }
        }
        if (selectedNode != null) {
            // 讓 current 減去權重總和,等價於 current -= totalWeight
            selectedWRR.decreaseCurrent(totalWeight);
            // 返回具有最大 current 的 Node
            return selectedNode;
        }
        // should not happen here
        return nodes.get(0);
    }
    protected static class WeightedRoundRobin {
        // 服務提供者權重
        private int weight;
        // 當前權重
        private AtomicLong current = new AtomicLong(0);
        // 最後一次更新時間
        private long lastUpdate;
        public long increaseCurrent() {
            // current = current + weight;
            return current.addAndGet(weight);
        }
        public long decreaseCurrent(int total) {
            // current = current - total;
            return current.addAndGet(-1 * total);
        }
        public int getWeight() {
            return weight;
        }
        public void setWeight(int weight) {
            this.weight = weight;
            // 初始情況下,current = 0
            current.set(0);
        }
        public AtomicLong getCurrent() {
            return current;
        }
        public void setCurrent(AtomicLong current) {
            this.current = current;
        }
        public long getLastUpdate() {
            return lastUpdate;
        }
        public void setLastUpdate(long lastUpdate) {
            this.lastUpdate = lastUpdate;
        }
    }
}

3.3 最小活躍數

**最小活躍數(Least Active)**算法 將請求分發到連接數 / 請求數最少的候選服務器(目前處理請求最少的服務器)。

由於每個請求的連接時長不一樣,如果採用簡單的輪循或隨機算法,都可能出現某些服務器當前連接數過大,而另一些服務器的連接過小的情況,這就造成了負載並非真正均衡。雖然,輪詢或算法都可以通過加權重屬性的方式進行負載調整,但加權方式難以應對動態變化。

例如下圖中,(1, 3, 5) 請求會被髮送到服務器 1,但是 (1, 3) 很快就斷開連接,此時只有 (5) 請求連接服務器 1;(2, 4, 6) 請求被髮送到服務器 2,只有 (2) 的連接斷開。該系統繼續運行時,服務器 2 會承擔過大的負載。

圖片

最小活躍數算法會記錄當前時刻,每個候選節點正在處理的連接數,然後選擇連接數最小的節點。該策略能夠動態、實時地反應服務器的當前狀況,較爲合理地將負責分配均勻,適用於對當前系統負載較爲敏感的場景。

例如下圖中,服務器 1 當前連接數最小,那麼新到來的請求 6 就會被髮送到服務器 1 上。

圖片

**加權最小活躍數(Weighted Least Connection)**在最小活躍數的基礎上,根據服務器的性能爲每臺服務器分配權重,再根據權重計算出每臺服務器能處理的連接數。

最小活躍數算法實現要點:活躍調用數越小,表明該服務節點處理能力越高,單位時間內可處理更多的請求,應優先將請求分發給該服務。在具體實現中,每個服務節點對應一個活躍數 active。初始情況下,所有服務提供者活躍數均爲 0。每收到一個請求,活躍數加 1,完成請求後則將活躍數減 1。在服務運行一段時間後,性能好的服務提供者處理請求的速度更快,因此活躍數下降的也越快,此時這樣的服務提供者能夠優先獲取到新的服務請求、這就是最小活躍數負載均衡算法的基本思想。

【示例】最小活躍數算法實現

以下實現基於 Dubbo 最小活躍數負載均衡算法做了些許改動。

public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = new Random();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        // 最小的活躍數
        int leastActive = -1;
        // 具有相同“最小活躍數”的服務者提供者(以下用 Node 代稱)數量
        int leastCount = 0;
        // leastIndexs 用於記錄具有相同“最小活躍數”的 Node 在 nodes 列表中的下標信息
        int[] leastIndexs = new int[length];
        int totalWeight = 0;
        // 第一個最小活躍數的 Node 權重值,用於與其他具有相同最小活躍數的 Node 的權重進行對比,
        // 以檢測是否“所有具有相同最小活躍數的 Node 的權重”均相等
        int firstWeight = 0;
        boolean sameWeight = true;
        // 遍歷 nodes 列表
        for (int i = 0; i < length; i++) {
            N node = nodes.get(i);
            // 發現更小的活躍數,重新開始
            if (leastActive == -1 || node.getActive() < leastActive) {
                // 使用當前活躍數更新最小活躍數 leastActive
                leastActive = node.getActive();
                // 更新 leastCount 爲 1
                leastCount = 1;
                // 記錄當前下標值到 leastIndexs 中
                leastIndexs[0] = i;
                totalWeight = node.getWeight();
                firstWeight = node.getWeight();
                sameWeight = true;
                // 當前 Node 的活躍數 node.getActive() 與最小活躍數 leastActive 相同
            } else if (node.getActive() == leastActive) {
                // 在 leastIndexs 中記錄下當前 Node 在 nodes 集合中的下標
                leastIndexs[leastCount++] = i;
                // 累加權重
                totalWeight += node.getWeight();
                // 檢測當前 Node 的權重與 firstWeight 是否相等,
                // 不相等則將 sameWeight 置爲 false
                if (sameWeight && i > 0
                    && node.getWeight() != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // 當只有一個 Node 具有最小活躍數,此時直接返回該 Node 即可
        if (leastCount == 1) {
            return nodes.get(leastIndexs[0]);
        }
        // 有多個 Node 具有相同的最小活躍數,但它們之間的權重不同
        if (!sameWeight && totalWeight > 0) {
            // 隨機生成一個 [0, totalWeight) 之間的數字
            int offsetWeight = random.nextInt(totalWeight);
            // 循環讓隨機數減去具有最小活躍數的 Node 的權重值,
            // 當 offset 小於等於0時,返回相應的 Node
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];
                // 獲取權重值,並讓隨機數減去權重值
                offsetWeight -= nodes.get(leastIndex).getWeight();
                if (offsetWeight <= 0) {
                    return nodes.get(leastIndex);
                }
            }
        }
        // 如果權重相同或權重爲0時,隨機返回一個 Node
        return nodes.get(leastIndexs[random.nextInt(leastCount)]);
    }
}

3.4 源地址哈希

**源地址哈希(IP Hash)**算法 根據請求源 IP,通過哈希計算得到一個數值,用該數值在候選服務器列表的進行取模運算,得到的結果便是選中的服務器。

可以保證同一 IP 的客戶端的請求會轉發到同一臺服務器上,用來實現會話粘滯(Sticky Session)。

特點:保證特定用戶總是請求到相同的服務器,若服務器宕機,會話會丟失。

【示例】源地址哈希算法實現示例

public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        if (StrUtil.isBlank(ip)) {
            ip = "127.0.0.1";
        }
        int length = nodes.size();
        int index = hash(ip) % length;
        return nodes.get(index);
    }
    public int hash(String text) {
        return HashUtil.fnvHash(text);
    }
}

3.5 一致性哈希

一致性哈希(Consistent Hash)算法的目標是:相同的請求儘可能落到同一個服務器上。

一致性哈希 可以很好的解決 穩定性問題,可以將所有的 存儲節點 排列在 首尾相接 的 Hash 環上,每個 key 在計算 Hash 後會 順時針 找到 臨接 的 存儲節點 存放。而當有節點 加入 或 退出 時,僅影響該節點在 Hash 環上順時針相鄰的後續節點。

圖片

1)相同的請求是指:一般在使用一致性哈希時,需要指定一個 key 用於 hash 計算,可能是:

用戶 ID

請求方 IP

請求服務名稱,參數列表構成的串

2)儘可能是指:服務器可能發生上下線,少數服務器的變化不應該影響大多數的請求。

當某臺候選服務器宕機時,原本發往該服務器的請求,會基於虛擬節點,平攤到其它候選服務器,不會引起劇烈變動。

**優點:**加入 和 刪除 節點隻影響 哈希環 中 順時針方向 的 相鄰的節點,對其他節點無影響。

**缺點:**加減節點 會造成 哈希環 中部分數據 無法命中。當使用 少量節點 時,節點變化 將大範圍影響 哈希環 中 數據映射,不適合 少量數據節點 的分佈式方案。普通 的 一致性哈希分區 在增減節點時需要 增加一倍 或 減去一半 節點才能保證 數據 和 負載的均衡。

**注意:**因爲 一致性哈希分區 的這些缺點,一些分佈式系統採用 虛擬槽 對 一致性哈希 進行改進,比如 Dynamo 系統。

【示例】一致性哈希算法示例

public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
    @SuppressWarnings("unchecked")
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        // 分片數,這裏設爲節點數的 4 倍
        Integer replicaNum = nodes.size() * 4;
        // 獲取 nodes 原始的 hashcode
        int identityHashCode = System.identityHashCode(nodes);
        // 如果 nodes 是一個新的 List 對象,意味着節點數量發生了變化
        // 此時 selector.identityHashCode != identityHashCode 條件成立
        ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
        if (selector == null || selector.identityHashCode != identityHashCode) {
            // 創建新的 ConsistentHashSelector
            selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
            selector = (ConsistentHashSelector<N>) selectors.get(ip);
        }
        // 調用 ConsistentHashSelector 的 select 方法選擇 Node
        return selector.select(ip);
    }
    /**
     * 一致性哈希選擇器
     */
    private static final class ConsistentHashSelector<N extends Node> {
        /**
         * 存儲虛擬節點
         */
        private final TreeMap<Long, N> virtualNodes;
        private final int identityHashCode;
        /**
         * 構造器
         *
         * @param nodes            節點列表
         * @param identityHashCode hashcode
         * @param replicaNum       分片數
         */
        ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
            this.virtualNodes = new TreeMap<>();
            this.identityHashCode = identityHashCode;
            // 獲取虛擬節點數,默認爲 100
            if (replicaNum == null) {
                replicaNum = 100;
            }
            for (N node : nodes) {
                for (int i = 0; i < replicaNum / 4; i++) {
                    // 對 url 進行 md5 運算,得到一個長度爲16的字節數組
                    byte[] digest = md5(node.getUrl());
                    // 對 digest 部分字節進行 4hash 運算,得到四個不同的 long 型正整數
                    for (int j = 0; j < 4; j++) {
                        // h = 0 時,取 digest 中下標爲 0 ~ 3 的4個字節進行位運算
                        // h = 1 時,取 digest 中下標爲 4 ~ 7 的4個字節進行位運算
                        // h = 2, h = 3 時過程同上
                        long m = hash(digest, j);
                        // 將 hash 到 node 的映射關係存儲到 virtualNodes 中,
                        // virtualNodes 需要提供高效的查詢操作,因此選用 TreeMap 作爲存儲結構
                        virtualNodes.put(m, node);
                    }
                }
            }
        }
        public N select(String key) {
            // 對參數 key 進行 md5 運算
            byte[] digest = md5(key);
            // 取 digest 數組的前四個字節進行 hash 運算,再將 hash 值傳給 selectForKey 方法,
            // 尋找合適的 Node
            return selectForKey(hash(digest, 0));
        }
        private N selectForKey(long hash) {
            // 查找第一個大於或等於當前 hash 的節點
            Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
            // 如果 hash 大於 Node 在哈希環上最大的位置,此時 entry = null,
            // 需要將 TreeMap 的頭節點賦值給 entry
            if (entry == null) {
                entry = virtualNodes.firstEntry();
            }
            // 返回 Node
            return entry.getValue();
        }
    }
    /**
     * 計算 hash 值
     */
    public static long hash(byte[] digest, int number) {
        return (((long) (digest[3 + number * 4] & 0xFF) << 24)
            | ((long) (digest[2 + number * 4] & 0xFF) << 16)
            | ((long) (digest[1 + number * 4] & 0xFF) << 8)
            | (digest[number * 4] & 0xFF))
            & 0xFFFFFFFFL;
    }
    /**
     * 計算 MD5 值
     */
    public static byte[] md5(String value) {
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e.getMessage(), e);
        }
        md5.reset();
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        md5.update(bytes);
        return md5.digest();
    }
}

以上示例基於 Dubbo 的一致性哈希負載均衡算法做了一些簡化。

四、參考資料

  1. Comparing Load Balancing Algorithms

  2. 《大型網站技術架構:核心原理與案例分析》

  3. 大型網站架構系列:負載均衡詳解(1)

  4. 什麼是負載均衡

  5. What Is Load Balancing

  6. Dubbo 官方負載均衡算法說明

  7. 負載均衡算法及手段

  8. 利用 dns 解析來實現網站的負載均衡

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/69AGivVfwjEzCNvwJ1_2tQ