解密負(fù)載均衡技術(shù)和負(fù)載均衡算法

作者 | 京東云開發(fā)者-紀(jì)卓志

什么是負(fù)載均衡技術(shù)

負(fù)載均衡器是一種軟件或硬件設(shè)備，它起到了將網(wǎng)絡(luò)流量分散到一組服務(wù)器的作用，可以防止任何一臺服務(wù)器過載。負(fù)載均衡算法就是負(fù)載均衡器用來在服務(wù)器之間分配網(wǎng)絡(luò)流量的邏輯（算法是一組預(yù)定義的規(guī)則），有時候也叫做負(fù)載均衡的類型。負(fù)載均衡算法的種類非常多，包括從簡單的輪詢負(fù)載均衡算法到基于響應(yīng)狀態(tài)信息的自適應(yīng)負(fù)載均衡算法。 負(fù)載均衡算法的選擇會影響負(fù)載分配機(jī)制的有效性，從而影響性能和業(yè)務(wù)連續(xù)性（也就是對外承諾的 SLA），選擇正確的負(fù)載均衡算法會對應(yīng)用程序性能產(chǎn)生重大影響。 本文將會介紹常見的負(fù)載均衡算法，并結(jié)合主流負(fù)載均衡軟件或硬件設(shè)備介紹各種負(fù)載均衡算法的實(shí)現(xiàn)方式。

常見負(fù)載均衡算法介紹

Round Robin（輪詢負(fù)載均衡算法）

在所有負(fù)載均衡算法中，輪詢負(fù)載均衡算法是最簡單的、最常用的負(fù)載均衡算法?？蛻舳苏埱笠院唵蔚妮啌Q方式分發(fā)到應(yīng)用程序服務(wù)器上。例如，假設(shè)有三臺應(yīng)用程序服務(wù)器：第一個客戶端請求發(fā)送到第一臺應(yīng)用程序服務(wù)器，第二個客戶端請求發(fā)送到第二臺應(yīng)用程序服務(wù)器，第三個客戶端請求發(fā)送到第三臺應(yīng)用程序服務(wù)器，第四個客戶端請求重新從第一臺應(yīng)用程序服務(wù)器開始，依次往復(fù)。

輪詢負(fù)載均衡適合所有客戶端請求都需要相同的服務(wù)器負(fù)載，并且所有的服務(wù)器實(shí)例都具有相同的服務(wù)器容量和資源（比如網(wǎng)絡(luò)帶寬和存儲）

Weighted Round Robin（加權(quán)輪詢負(fù)載均衡算法）

加權(quán)負(fù)載均衡算法與輪詢算法相似，增加了根據(jù)每個服務(wù)器的相對容量來將請求分散到不同服務(wù)器的能力。它適合將傳入的客戶端請求分散到一組具有不同功能或具有不同負(fù)載容量的服務(wù)器上。服務(wù)器集群管理員根據(jù)一個標(biāo)準(zhǔn)為每個應(yīng)用程序服務(wù)器分配一個權(quán)重，這個標(biāo)準(zhǔn)表示每個服務(wù)器對請求的相對處理能力。 例如，如果在其他資源都是無窮多的情況下，假如服務(wù)器 #1 的 CPU 核心數(shù)是服務(wù)器 #2 和服務(wù)器 #3 的 CPU 核心數(shù)的二倍，那么服務(wù)器 #1 的權(quán)重更高，而服務(wù)器 #2 和 #3 的權(quán)重相同（都比 #1 低）。如果我們有 4 個連續(xù)的客戶端請求，那么有 2 次請求發(fā)送到 #1，另外 2 次請求分別發(fā)送到 #2 和 #3。

加權(quán)輪詢負(fù)載均衡算法描述的是在一段時間內(nèi)負(fù)載的分布情況，不同的加權(quán)輪詢負(fù)載均衡算法可能會產(chǎn)生不同的選擇序列，不應(yīng)該對處理下一次負(fù)載的服務(wù)器進(jìn)行假設(shè)。

Least Connections（最少連接負(fù)載均衡算法）

最少連接負(fù)載均衡算法又叫做最少等待請求算法（Least Outstanding Request, LOR）。最少連接負(fù)載均衡是一種動態(tài)負(fù)載均衡算法，客戶端請求被分發(fā)到在接收到請求時活動連接數(shù)最少的應(yīng)用服務(wù)器。在應(yīng)用服務(wù)器具有類似規(guī)格的情況下，一臺服務(wù)器可能會因?yàn)檫B接數(shù)過多而過載（無法接收請求也屬于過載），這個算法考慮了活動連接負(fù)載。這種技術(shù)適合具有不同連接時間的傳入請求（多機(jī)房）以及一組在處理能力和可用資源方面相對相似的服務(wù)器。

Weighted Least Connections（加權(quán)最少連接負(fù)載均衡算法）

加權(quán)最少連接建立在最少連接負(fù)載均衡算法上，考慮不同的應(yīng)用程序服務(wù)器特性。與加權(quán)輪詢負(fù)載均衡算法相同，服務(wù)器集群管理員根據(jù)一個標(biāo)準(zhǔn)為每個應(yīng)用程序服務(wù)器分配一個權(quán)重，這個標(biāo)準(zhǔn)表示每個服務(wù)器對請求的相對處理能力。負(fù)載均衡器根據(jù)活動鏈接和分配的服務(wù)器權(quán)重做出負(fù)載平衡決策（例如，使用連接數(shù)乘以權(quán)重的倒數(shù)，選擇值最高的服務(wù)器）。

Resource Based（基于資源的負(fù)載均衡算法）

基于資源的負(fù)載均衡算法又叫做自適應(yīng)負(fù)載均衡算法。基于資源的負(fù)載均衡算法根據(jù)后端服務(wù)器提供的狀態(tài)指標(biāo)來做出決策。這個狀態(tài)指標(biāo)可以由一個運(yùn)行在服務(wù)器上的自定義應(yīng)用程序（比如 agent），或從基礎(chǔ)設(shè)施提供方的開放接口獲取。負(fù)載均衡器定期查詢每臺服務(wù)器的狀態(tài)指標(biāo)，然后適當(dāng)?shù)卣{(diào)整服務(wù)器的動態(tài)權(quán)重。 在這種方式下，負(fù)載均衡算法實(shí)際上是在每臺真實(shí)服務(wù)器上執(zhí)行健康檢查。這個算法適用于任何需要來自每臺服務(wù)器的詳細(xì)健康檢查信息來做出負(fù)載均衡決策的情況。 例如：此算法適用于工作負(fù)載多變且需要詳細(xì)的應(yīng)用程序性能和狀態(tài)來評估服務(wù)器運(yùn)行狀態(tài)的任何應(yīng)用程序（例如 CPU 密集型的最短路徑計(jì)算，或其他高性能計(jì)算場景）。

Fixed Weighting（固定權(quán)重負(fù)載均衡算法）

固定權(quán)重負(fù)載均衡算法允許服務(wù)器集群管理員根據(jù)他們的標(biāo)準(zhǔn)為每個應(yīng)用程序服務(wù)器分配一個權(quán)重，以表示每個服務(wù)器的相對流量處理能力。權(quán)重最高的應(yīng)用服務(wù)器將接收所有流量。如果權(quán)重最高的應(yīng)用服務(wù)器出現(xiàn)故障，所有流量將會被引導(dǎo)到下一個權(quán)重最高的應(yīng)用服務(wù)器。此方法適用于單個服務(wù)器能夠處理所有預(yù)期傳入請求的工作負(fù)載，如果當(dāng)前活動的服務(wù)器發(fā)生故障，一個或多個 “熱備用” 服務(wù)器可以直接用于承擔(dān)負(fù)載。

Weighted Response Time（加權(quán)響應(yīng)時間負(fù)載均衡算法）

加權(quán)響應(yīng)時間負(fù)載均衡算法使用應(yīng)用程序的響應(yīng)時間來計(jì)算服務(wù)器權(quán)重。響應(yīng)速度最快的應(yīng)用程序服務(wù)器接收下一個請求。此方法適用于應(yīng)用程序響應(yīng)時間是最重要的問題的場景。 當(dāng)應(yīng)用程序提供的是對外開放服務(wù)時尤為重要，因?yàn)閷ν忾_放服務(wù)都會為合作伙伴提供服務(wù)級別協(xié)議（Service Level Argument，SLA），而 SLA 中承諾的主要就是服務(wù)的可用性與服務(wù)的響應(yīng)時間（TP99、TP999 等）。

Source IP Hash（源地址哈希負(fù)載均衡算法）

源地址哈希負(fù)載均衡算法使用客戶端請求的源 IP 與目標(biāo) IP 地址生成唯一的哈希密鑰，用于將客戶端請求分配給特定的服務(wù)器。如果傳輸層會話中斷，可以重新密鑰，因此客戶端請求將會被定向到它之前使用的統(tǒng)一服務(wù)器。當(dāng)客戶端對于每個連續(xù)連接始終返回到同一服務(wù)器至關(guān)重要時，此方法最適用。

服務(wù)端研發(fā)經(jīng)常接觸的數(shù)據(jù)庫事務(wù)就適用于此場景

Consistent Hash（一致性哈希負(fù)載均衡算法）

一致性哈希負(fù)載均衡算法類似于源地址哈希，不同在于一致性哈希負(fù)載均衡算法可以使用任意應(yīng)用參數(shù)組成唯一的哈希密鑰，并且當(dāng)服務(wù)器集群發(fā)生變化時可以盡可能少地進(jìn)行數(shù)據(jù)遷移。

常見負(fù)載均衡算法實(shí)現(xiàn)

本節(jié)將會介紹各種常見負(fù)載均衡算法的實(shí)現(xiàn)方式，某些負(fù)載均衡算法具有多種不同的實(shí)現(xiàn)方式，并且每種實(shí)現(xiàn)方式都有各自適用的場景，這些不同的實(shí)現(xiàn)方式也會在本節(jié)進(jìn)行介紹。同時本節(jié)中會假設(shè)所有的請求都是線性的，不會處理并發(fā)安全相關(guān)的細(xì)節(jié)。

Round Robin（輪詢負(fù)載均衡算法）

在所有負(fù)載均衡算法中，輪詢負(fù)載均衡算法實(shí)現(xiàn)起來最簡單，只需要一個變量表示當(dāng)前位置并不斷增加即可。

public class RoundRobinLoadBalancer {

    private final List instances;

    private int position;

    public RoundRobinLoadBalancer(List instances) {
        this.instances = instances;
        this.position = ThreadLocalRandom.current().nextInt(instances.size());
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int peeked = (position++) & Integer.MAX_VALUE;
        return instances.get(peeked % instances.size());
    }
}

這里有兩個需要注意的點(diǎn)

當(dāng)我們初始化位置時，需要將其設(shè)置為一個隨機(jī)值，避免多個負(fù)載均衡器同時請求同一個服務(wù)器，造成服務(wù)器的瞬時壓力

在位置自增時，需要忽略符號位，因?yàn)?Java 沒有無符號整數(shù)，所以當(dāng)位置的值超出整型最大值時會變成負(fù)值導(dǎo)致拋出異常。至于為什么不能使用絕對值，是因?yàn)檎偷淖钚≈禌]有對應(yīng)的絕對值，得到的依舊是負(fù)值 (Spring Cloud #1074)

Weighted Round Robin（加權(quán)輪詢負(fù)載均衡算法）

加權(quán)輪詢負(fù)載均衡算法有很多主流的實(shí)現(xiàn)，并且各自都有各自的優(yōu)點(diǎn)。雖然加權(quán)負(fù)載均衡產(chǎn)生任意符合全總分配比例分布的選擇序列都是合適的，但在短時間窗口內(nèi)是否能夠選擇盡可能多的節(jié)點(diǎn)提供服務(wù)仍是評價加權(quán)負(fù)載均衡實(shí)現(xiàn)的質(zhì)量的關(guān)鍵指標(biāo)。

數(shù)組展開方式

數(shù)組展開實(shí)現(xiàn)方式是一種適用空間換時間的策略，適用于較小的服務(wù)器集群或?qū)Ｓ眯拓?fù)載均衡設(shè)備。它的優(yōu)點(diǎn)是速度非?？欤c Round Robin 實(shí)現(xiàn)完全一致。它的缺點(diǎn)也很明顯，當(dāng)權(quán)重的總和很大時會帶來很大的內(nèi)存開銷

public class WeightedLoadBalancer {

    private final List instances;

    private int position;

    public WeightedLoadBalancer(List instances) {
        this.instances = expandByWeight(instances);
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int peeked = (position++) & Integer.MAX_VALUE;
        return instances.get(peeked % instances.size());
    }

    private List expandByWeight(List instances) {
        List newInstances = new ArrayList<>();

        for (ServiceInstance instance : instances) {
            int bound = instance.getWeight();
            for (int w = 0; weight < bound; weight++) {
                newInstances.add(instance);
            }
        }

        Collections.shuffle(newInstances);
        return newInstances;
    }
}

這里有三個需要注意的點(diǎn)：

當(dāng)實(shí)例按權(quán)重展開成數(shù)組的時候，可能會出現(xiàn)實(shí)例權(quán)重都很大，但是它們的最大公約數(shù)不為 1，這個時候可以使用最大公約數(shù)來減少展開后的數(shù)組大小。因?yàn)樽畲蠊s數(shù)的諸多限制，例如任意自然數(shù) N 與 N+1 互質(zhì)，任意自然數(shù) N 與 1 互質(zhì)，所以很容易出現(xiàn)優(yōu)化失敗的情況，因此本示例并未給出，感興趣的可以去看 Spring Cloud 相關(guān) PR（Spring Cloud #1140）

在實(shí)例按權(quán)重展開成數(shù)組后，需要對得到的數(shù)組進(jìn)行洗牌，以保證流量盡可能均勻，避免連續(xù)請求相同實(shí)例（Java 中實(shí)現(xiàn)的洗牌算法是 Fisher-Yates 算法，其他語言可以自行實(shí)現(xiàn)）

因?yàn)槭窃跇?gòu)建負(fù)載均衡器的時候按權(quán)重展開成數(shù)組的，所以在負(fù)載均衡器構(gòu)建完成后無法再改變實(shí)例的權(quán)值，對于頻繁動態(tài)變更權(quán)重的場景不適用

上界收斂選擇方式

上界收斂選擇方式提前計(jì)算出所有權(quán)重的最大值，并將初始上界設(shè)置為所有權(quán)重的最大值，接下來我們一輪一輪地去遍歷所有實(shí)例，并找到權(quán)重大于等于上界的實(shí)例。當(dāng)前輪遍歷結(jié)束后，所有大于等于上界的元素都被選取到了，接下來開始嘗試權(quán)重更低的節(jié)點(diǎn)，直到最后上界為 0 時，將其重新置為最大值。目前 openresty （有人在issue #44上分析了這種算法）

public class WeightedLoadBalancer {

    private final List instances;

    private final int max;

    private final int gcd;

    private int bound;

    private int position;

    public WeightedLoadBalancer(List instances) {
        this.instances = instances;
        this.max = calculateMaxByWeight(instances);
        this.gcd = calculateGcdByWeight(instances);
        this.position = ThreadLocalRandom.current().nextInt(instances.size());
    }

    public ServiceInstance peek(HttpServletRequest request) {
        if (bound == 0) {
            bound = max;
        }

        while (instances.size() > 0) {
            for (int peeked = position; peeked < instances.size(); peeked++) {
                ServiceInstance instance = instances.get(peeked);
                if (instance.getWeight() >= bound) {
                    position = peeked + 1;
                    return instance;
                }
            }
            position = 0;
            bound = bound - gcd;
        }
        return null;
    }

    private static int calculateMaxByWeight(List instances) {
        int max = 0;
        for (ServiceInstance instance : instances) {
            if (instance.getWeight() > max) {
                max = instance.getWeight();
            }
        }
        return max;
    }

    private static int calculateGcdByWeight(List instances) {
        int gcd = 0;
        for (ServiceInstance instance : instances) {
            gcd = gcd(gcd, instance.getWeight());
        }
        return gcd;
    }

    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

這里面有四個需要注意的點(diǎn)：

如果是短頻率請求，將會一直訪問高權(quán)重實(shí)例，導(dǎo)致在短時間窗口內(nèi)負(fù)載看起來并不均勻。這個可以通過改變方向，從下界向上界逼近來解決。

每一輪后降低上界的值可以取所有權(quán)重的最大公約數(shù)，因?yàn)槿绻看蜗陆?1 的話，中間這些輪會反復(fù)請求權(quán)重最高的那些實(shí)例，導(dǎo)致負(fù)載不均衡。

雖然最大公約數(shù)可以減少下降次數(shù)，但是如果權(quán)重相差非常多，并且所有元素都是互質(zhì)的（n 與 n+1 互質(zhì)，任意自然數(shù) n 與 1 互質(zhì)，在實(shí)踐中非常容易出現(xiàn)），那么在上界下降的過程中將會帶來很多空轉(zhuǎn)。這個可以參考廣度優(yōu)先遍歷的思想，使用先入先出的隊(duì)列來減少空轉(zhuǎn)。

與數(shù)組展開方式遇到的問題相同，因?yàn)槭窃跇?gòu)建負(fù)載均衡器的時候計(jì)算最大公約數(shù)的值，所以對于頻繁動態(tài)變更權(quán)重的場景依舊會有很大的性能開銷，但是相較于數(shù)組展開方式可以避免頻繁動態(tài)分配數(shù)組導(dǎo)致的性能與內(nèi)存碎片問題

權(quán)重輪轉(zhuǎn)實(shí)現(xiàn)

權(quán)重輪轉(zhuǎn)算法中將會存儲兩個權(quán)重的值，一個是不會變化的原始權(quán)重，一個是會隨著每次選擇變化的當(dāng)前權(quán)重。權(quán)重輪轉(zhuǎn)實(shí)現(xiàn)中維護(hù)了一個循環(huán)不變量 —— 所有節(jié)點(diǎn)的當(dāng)前權(quán)重的和為 0。每輪遍歷過程中所有實(shí)例的有效權(quán)重都會增加它的原始權(quán)重，并選擇出當(dāng)前權(quán)重最高的節(jié)點(diǎn)。選擇出權(quán)重最高的節(jié)點(diǎn)后將它的當(dāng)前權(quán)重減去所有實(shí)例權(quán)重的總和，以避免它再次被選擇。NGINX 中加權(quán)輪詢負(fù)載均衡算法使用此實(shí)現(xiàn)（NGINX）。這種算法的優(yōu)勢是它很平滑，低權(quán)重節(jié)點(diǎn)的等待時間較短，并且每輪權(quán)重輪轉(zhuǎn)的最小正周期很小，是所有服務(wù)器實(shí)例權(quán)重的和。。

在 NGINX 中又叫做平滑加權(quán)負(fù)載均衡（Smooth Weighted Load Balancing，SWRR）。

public class WeightedLoadBalancer {

    private final List instances;

    public WeightedLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        int total = 0;
        for (ServiceInstance instance : instances) {
            total += instance.getWeight();
            instance.setCurrentWeight(instance.getCurrentWeight() + instance.getWeight());
            if (best == null || instance.getCurrentWeight() > best.getCurrentWeight()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setCurrentWeight(best.getCurrentWeight() - total);
        }
        return best;
    }
}

這里面有三個需要注意的點(diǎn)：

權(quán)重輪轉(zhuǎn)非常適合實(shí)例變化頻率非常高的集合，因?yàn)樗恍枰崆皹?gòu)建數(shù)據(jù)結(jié)構(gòu)

權(quán)重輪轉(zhuǎn)實(shí)現(xiàn)的效率與實(shí)例數(shù)量相關(guān)，時間復(fù)雜度是 O (n)，當(dāng)集群服務(wù)器數(shù)量非常大時需要限制每次參與選擇的服務(wù)器數(shù)量（Spring Cloud #1111）

權(quán)重輪轉(zhuǎn)實(shí)現(xiàn)需要修改服務(wù)器實(shí)例的數(shù)據(jù)結(jié)構(gòu)，當(dāng)服務(wù)實(shí)例是由其他機(jī)構(gòu)提供時無法使用此實(shí)現(xiàn)

EDF（Earliest Deadline First）實(shí)現(xiàn)

EDF 算法最早被用在 CPU 調(diào)度上，EDF 是搶占式單處理器調(diào)度的最佳調(diào)度算法。EDF 實(shí)現(xiàn)與權(quán)重輪轉(zhuǎn)實(shí)現(xiàn)相似，引入了名為 deadline 的額外變量，可以認(rèn)為權(quán)重越高的服務(wù)器實(shí)例完成任務(wù)的時間越快，那么在假設(shè)所有請求的成本相同時，所需要花費(fèi)的時間是權(quán)重的倒數(shù)，所以可以很自然地選擇可以最早空閑出來提供服務(wù)的服務(wù)器實(shí)例，并將任務(wù)分配給它。 實(shí)現(xiàn) EDF 算法只需要將每個下游服務(wù)器實(shí)例與 deadline 綁定，然后以 deadline 為優(yōu)先級維護(hù)到優(yōu)先隊(duì)列中，并不斷取出隊(duì)首元素，調(diào)整它的 deadline，并將它重新提交到優(yōu)先隊(duì)列中。知名 Service Mesh 代理 envoy 使用了此方法實(shí)現(xiàn)加權(quán)負(fù)載均衡（envoy），以及螞蟻開源網(wǎng)絡(luò)代理 mosn 中也實(shí)現(xiàn)了此方法（mosn #1920）

public class WeightedLoadBalancer {

    private final PriorityQueue entries;

    public WeightedLoadBalancer(List instances) {
        this.entries = instances.stream().map(EdfEntry::new).collect(Collectors.toCollection(PriorityQueue::new));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        EdfEntry entry = entries.poll();
        if (entry == null) {
            return null;
        }
        ServiceInstance instance = entry.instance;
        entry.deadline = entry.deadline + 1.0 / instance.getWeight();
        entries.add(entry);
        return instance;
    }

    private static class EdfEntry implements Comparable {

        final ServiceInstance instance;

        double deadline;

        EdfEntry(ServiceInstance instance) {
            this.instance = instance;
            this.deadline = 1.0 / instance.getWeight();
        }

        @Override
        public int compareTo(EdfEntry o) {
            return Double.compare(deadline, o.deadline);
        }
    }
}

EDF 每次選擇的算法復(fù)雜度為 O (log (n))，相較于數(shù)組展開要慢，但相較于上界收斂選擇在最壞情況下以及權(quán)重輪轉(zhuǎn)都需要 O (n) 的時間復(fù)雜度來說，其性能表現(xiàn)的非常好，并且對于超大集群，其性能下降不明顯。其空間復(fù)雜度為 O (n)，不會造成很大的內(nèi)存開銷。

Least Connections（最少連接負(fù)載均衡算法）

遍歷比較方式

最簡單的實(shí)現(xiàn)方式，遍歷所有實(shí)例，并找出當(dāng)前連接數(shù)最少的實(shí)例

public class LeastConnectionLoadBalancer {

    private final List instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        for (ServiceInstance instance : instances) {
            if (best == null || instance.getConnections() < best.getConnections()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setConnections(best.getConnections() + 1);
        }
        return best;
    }
}

堆維護(hù)方式 所有動態(tài)有序集合都可以通過優(yōu)先隊(duì)列來實(shí)現(xiàn)，與 EDF 算法相同，取出隊(duì)首的元素，修改它的優(yōu)先級，并放回隊(duì)列中

public class LeastConnectionLoadBalancer {

    private final PriorityQueue instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances.stream().collect(toCollection(
                () -> new PriorityQueue<>(comparingInt(ServiceInstance::getConnections))));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = instances.poll();
        if (best == null) {
            return null;
        }
        best.setConnections(best.getConnections() + 1);
        return best;
    }
}

Weighted Least Connections（加權(quán)最少連接負(fù)載均衡算法）

加權(quán)最少連接負(fù)載均衡算法的實(shí)現(xiàn)方式與最少連接負(fù)載均衡算法相同，只是在計(jì)算時增加了權(quán)重相關(guān)的參數(shù)

遍歷比較方式

public class LeastConnectionLoadBalancer {

    private final List instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        for (ServiceInstance instance : instances) {
            if (best == null || instance.getConnections() * best.getWeight() < best.getConnections() * instance.getWeight()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setConnections(best.getConnections() + 1);
        }
        return best;
    }
}

Tips，在不等式中 a/b < c/d 與 ad < bc 等價，并且可以避免除法帶來的性能與精度問題

堆維護(hù)方式

public class LeastConnectionLoadBalancer {

    private final PriorityQueue instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances.stream().collect(toCollection(
                () -> new PriorityQueue<>(comparingDouble(ServiceInstance::getWeightedConnections))));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = instances.poll();
        if (best == null) {
            return null;
        }
        best.setConnections(best.getConnections() + 1);
        best.setWeightedConnections(1.0 * best.getConnections() / best.getWeight());
        return best;
    }
}

Weighted Response Time（加權(quán)響應(yīng)時間負(fù)載均衡算法）

加權(quán)響應(yīng)時間負(fù)載均衡算法使用統(tǒng)計(jì)學(xué)的方法，通過歷史的響應(yīng)時間來得到預(yù)測值，使用這個預(yù)測值來選擇相對更優(yōu)的服務(wù)器實(shí)例。得到預(yù)測值的方法有很多，包括時間窗口內(nèi)的平均值、時間窗口內(nèi)的 TP99、歷史所有響應(yīng)時間的指數(shù)移動加權(quán)平均數(shù)（EWMA）等等。其中 Linkerd 與 APISIX 使用了 EWMA 算法（Linkerd和APISIX）。 通過歷史的響應(yīng)時間來得到預(yù)測值這個操作通常是 CPU 開銷很大的，實(shí)際使用時可以不用遍歷所有元素，而是使用 K - 臨近元素或直接隨機(jī)選擇兩個元素進(jìn)行比較即可，這種啟發(fā)式方法辦法無法保證全局最優(yōu)但是可以保證不至于全局最差。

Source IP Hash（源地址哈希負(fù)載均衡算法）

源地址哈希負(fù)載均衡以任意算法將請求地址映射成整型數(shù)，并將這個整型數(shù)映射到實(shí)例列表的下標(biāo)

public class IpHashLoadBalancer {

    private final List instances;

    public IpHashLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int h = hashCode(request);
        return instances.get(h % instances.size());
    }

    private int hashCode(HttpServletRequest request) {
        String xForwardedFor = request.getHeader("X-Forwarded-For");
        if (xForwardedFor != null) {
            return xForwardedFor.hashCode();
        } else {
            return request.getRemoteAddr().hashCode();
        }
    }
}

這里有一個需要注意的點(diǎn)：

面向公網(wǎng)提供服務(wù)的負(fù)載均衡器前面可能會經(jīng)過任意多層反向代理服務(wù)器，為了獲取到真實(shí)的源地址，需要先獲取 X-Forwarded-For 頭部，如果該頭部不存在再去獲取 TCP 連接的源地址

負(fù)載均衡技術(shù)擴(kuò)展

服務(wù)注冊表與發(fā)現(xiàn)（Service Registry and Service Discovery）

在維護(hù)大型服務(wù)器集群時，服務(wù)器實(shí)例隨時都有可能被創(chuàng)建或移除，當(dāng)服務(wù)器被創(chuàng)建或移除時，集群管理員需要到各個負(fù)載均衡設(shè)備上去更新服務(wù)器實(shí)例列表。 服務(wù)注冊表會在內(nèi)部維護(hù)服務(wù)對應(yīng)的服務(wù)器實(shí)例列表。在服務(wù)器實(shí)例被創(chuàng)建并成功運(yùn)行服務(wù)后，服務(wù)器實(shí)例會去服務(wù)注冊表中注冊自身，包括網(wǎng)絡(luò)地址（IPv4/IPv6）、服務(wù)端口號、服務(wù)協(xié)議（TCP/TLS/HTTP/HTTPS）以及自身提供的服務(wù)名稱等等，有的服務(wù)注冊表本身也會提供主動健康檢查的能力（如 Eureka 與 Consul）。在服務(wù)器實(shí)例正常退出時會在服務(wù)注冊表執(zhí)行反注冊邏輯，這個時候服務(wù)注冊表就會將這個服務(wù)器實(shí)例從服務(wù)器實(shí)例列表中移除。即使服務(wù)器實(shí)例異常退出導(dǎo)致無法執(zhí)行反注冊邏輯，服務(wù)注冊表也會通過主動健康檢查機(jī)制將這個異常的服務(wù)器實(shí)例從服務(wù)器實(shí)例列表中移除。 在擁有服務(wù)注冊表后，負(fù)載均衡設(shè)備不需要再手動維護(hù)服務(wù)器實(shí)例列表，而是當(dāng)請求到來時從服務(wù)注冊表中拉取對應(yīng)的服務(wù)器實(shí)例列表，并在這個服務(wù)器實(shí)例列表中進(jìn)行負(fù)載均衡。為了提高服務(wù)的可用性，負(fù)載均衡設(shè)備會在本地（內(nèi)存或本地文件注冊表）緩存這些服務(wù)器實(shí)例列表，以避免由于負(fù)載均衡設(shè)備與服務(wù)注冊表無法連接而導(dǎo)致服務(wù)不可用。 緩存及重新獲取服務(wù)器列表的策略根據(jù)不同業(yè)務(wù)場景有不同的實(shí)現(xiàn)，在 Spring Cloud Loadbalancer 中是通過緩存過期而觸發(fā)重新獲取的邏輯（Spring Cloud），當(dāng)服務(wù)注冊表不可用時，因?yàn)樨?fù)載均衡設(shè)備中無可用的服務(wù)器備份而導(dǎo)致服務(wù)完全不可用；在大部分的負(fù)載均衡設(shè)備中將緩存獲取與更新邏輯改為定時器主動刷新的機(jī)制，這樣當(dāng)服務(wù)注冊表不可用時可以主動決定是否將舊數(shù)據(jù)標(biāo)記為過期。盡管本地緩存可以提高服務(wù)的可用性，但是要注意負(fù)載均衡設(shè)備在使用的仍舊是舊的服務(wù)提供方列表，當(dāng)長時間無法獲取到新的服務(wù)提供方列表時，負(fù)載均衡設(shè)備應(yīng)當(dāng)舍棄舊的服務(wù)提供方列表，并將服務(wù)不可用的問題暴露出來，通過基礎(chǔ)設(shè)施提供的監(jiān)控與告警能力通知集群管理員來進(jìn)行處理。

健康檢查（Health Check）

健康檢查本質(zhì)是一個預(yù)定規(guī)則，它向負(fù)載均衡器背后的服務(wù)器集群中的所有成員發(fā)送相同的請求，以確定每個成員服務(wù)器是否可以接受客戶端請求。 對于某些類型的健康檢查，通過評估來自服務(wù)器的響應(yīng)以及收到服務(wù)器響應(yīng)所需的時間以確定每個成員服務(wù)器的運(yùn)行狀態(tài)。通常情況下，當(dāng)成員服務(wù)器的狀態(tài)變?yōu)椴唤】禃r，負(fù)載均衡器應(yīng)該快速地將其從服務(wù)器實(shí)例列表中移除，并在成員服務(wù)器狀態(tài)恢復(fù)正常時將其重新添加回服務(wù)器實(shí)例列表中。

對于網(wǎng)絡(luò)層負(fù)載均衡器（也叫做 NLB 或 L4LB），通過建立 TCP 連接，根據(jù)是否能夠成功建立連接以及建立連接所需要的時間來確定成員服務(wù)器的狀態(tài)。

對于應(yīng)用層負(fù)載均衡器（也叫做 ALB 或 L7LB），通過發(fā)送應(yīng)用層協(xié)議（不只是 HTTP 協(xié)議）定義的用于健康檢查的請求報文，并根據(jù)響應(yīng)報文內(nèi)容以及整個請求從建立連接到完整收到所有響應(yīng)所花費(fèi)的時間來確定成員服務(wù)器的狀態(tài)。

應(yīng)用負(fù)載均衡器沒有固定的模式。例如，對于提供 HTTP 協(xié)議服務(wù)的應(yīng)用，可以提供用于健康檢查的 URL，設(shè)置通過健康檢查的 HTTP 狀態(tài)碼（或狀態(tài)碼集），并驗(yàn)證響應(yīng)報文中用于表示服務(wù)器狀態(tài)的字段（通過 JSONPath 或 XMLPath 等提?。┦欠袷穷A(yù)期值等方式來確認(rèn)成員服務(wù)器狀態(tài)；對于 RPC 協(xié)議，可以提供專門的 ping-pong 服務(wù)，負(fù)載均衡器根據(jù) RPC 協(xié)議組裝請求報文，并發(fā)送 ping 請求到成員服務(wù)器上，并根據(jù)成員服務(wù)器返回的內(nèi)容是否為 pong 響應(yīng)來確認(rèn)成員服務(wù)器的狀態(tài)，具體設(shè)計(jì)可以參考 websocket 的 ping-pong 機(jī)制（RFC 6455）。

慢啟動（Slow Start）

負(fù)載均衡器中的慢啟動思想來自于 TCP 的擁塞控制理論，其核心也是為了避免大量請求涌入剛剛啟動完成的應(yīng)用程序，導(dǎo)致大量請求阻塞、超時或異常的情況。 眾所周知，Java 是半編譯半解釋型語言，包括 Java 語言在內(nèi)，現(xiàn)代解釋型語言的解釋器都帶有即時編譯器（Just In Time，JIT），JIT 編譯器會跟蹤每個方法的執(zhí)行點(diǎn)，對那些熱點(diǎn)路徑（Hotspot）進(jìn)行更高效的優(yōu)化，這也是 Hotspot JVM 名字的由來。而 JIT 對熱點(diǎn)路徑的優(yōu)化全都來自于自應(yīng)用程序啟動以來的所有方法調(diào)用，也就是說應(yīng)用程序的系統(tǒng)承載能力是隨著程序的運(yùn)行而不斷得到強(qiáng)化的，經(jīng)過 JIT 優(yōu)化的 Java 代碼甚至可以得到近似 GCC 中 O3（最高級別）優(yōu)化的性能。跟多關(guān)于 JIT 編譯器的細(xì)節(jié)可以看 Oracle 的 Java 開發(fā)者指南（Java Developer Guide）。 同時，現(xiàn)代應(yīng)用程序都不可避免的會使用本地緩存，當(dāng)應(yīng)用程序剛剛啟動時內(nèi)存中的緩存是空的，隨著應(yīng)用程序的運(yùn)行，不斷地訪問外部系統(tǒng)獲取數(shù)據(jù)并將數(shù)據(jù)寫入到內(nèi)存緩存中，應(yīng)用程序與外部系統(tǒng)的交互會不斷減少，應(yīng)用程序的系統(tǒng)承載能力也會逐漸達(dá)到峰值。 上面是應(yīng)用程序在啟動后性能不斷提升的因素中最常見的，初次之外還有很多的因素。所以為了避免大量請求涌入剛剛啟動完成的應(yīng)用程序的現(xiàn)象發(fā)生，負(fù)載均衡器會通過慢啟動的方式，隨著服務(wù)器運(yùn)行不斷增加這些服務(wù)器實(shí)例的權(quán)重，最終達(dá)到服務(wù)器的實(shí)際權(quán)重，從而達(dá)到動態(tài)調(diào)整分配給這些服務(wù)器實(shí)例的流量的效果。 服務(wù)器權(quán)重變化算法有很多，包括隨時間線性增長、隨時間對數(shù)增長、隨時間指數(shù)增長、隨時間變冪增長、與隨時間按 Logistic 增長等。目前京東服務(wù)框架（JSF）實(shí)現(xiàn)的是隨時間線性增長；envoy 實(shí)現(xiàn)了隨時間變冪增長，并引入了漸進(jìn)因子來調(diào)整變化速率（envoy slow start）。

總結(jié)

負(fù)載均衡技術(shù)是網(wǎng)絡(luò)代理與網(wǎng)關(guān)組件最核心的組成部分，本文簡單介紹了什么是負(fù)載均衡技術(shù)、常見的負(fù)載均衡算法以及常見負(fù)載均衡算法的實(shí)現(xiàn)，并給出了負(fù)載均衡技術(shù)的擴(kuò)展，為將來更深入學(xué)習(xí)網(wǎng)絡(luò)代理相關(guān)技術(shù)打下基礎(chǔ)。 因本人才學(xué)疏淺經(jīng)驗(yàn)?zāi)芰τ邢蓿闹须y免會有疏忽和遺漏，以及不連貫的地方，歡迎大家與我溝通交流給出建議。