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

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

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

常見負載均衡算法介紹

Round Robin（輪詢負載均衡算法）

在所有負載均衡算法中，輪詢負載均衡算法是最簡單的、最常用的負載均衡算法?？蛻舳苏埱笠院唵蔚妮啌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ù)。

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

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

加權(quán)負載均衡算法與輪詢算法相似，增加了根據(jù)每個服務(wù)器的相對容量來將請求分散到不同服務(wù)器的能力。它適合將傳入的客戶端請求分散到一組具有不同功能或具有不同負載容量的服務(wù)器上。服務(wù)器集群管理員根據(jù)一個標準為每個應(yīng)用程序服務(wù)器分配一個權(quá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)輪詢負載均衡算法描述的是在一段時間內(nèi)負載的分布情況，不同的加權(quán)輪詢負載均衡算法可能會產(chǎn)生不同的選擇序列，不應(yīng)該對處理下一次負載的服務(wù)器進行假設(shè)。

Least Connections（最少連接負載均衡算法）

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

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

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

Resource Based（基于資源的負載均衡算法）

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

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

固定權(quán)重負載均衡算法允許服務(wù)器集群管理員根據(jù)他們的標準為每個應(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ù)期傳入請求的工作負載，如果當前活動的服務(wù)器發(fā)生故障，一個或多個 “熱備用” 服務(wù)器可以直接用于承擔(dān)負載。

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

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

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

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

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

Consistent Hash（一致性哈希負載均衡算法）

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

常見負載均衡算法實現(xiàn)

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

Round Robin（輪詢負載均衡算法）

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

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());
    }
}

這里有兩個需要注意的點

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

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

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

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

數(shù)組展開方式

數(shù)組展開實現(xiàn)方式是一種適用空間換時間的策略，適用于較小的服務(wù)器集群或?qū)Ｓ眯拓撦d均衡設(shè)備。它的優(yōu)點是速度非常快，與 Round Robin 實現(xiàn)完全一致。它的缺點也很明顯，當權(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;
    }
}

這里有三個需要注意的點：

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

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

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

上界收斂選擇方式

上界收斂選擇方式提前計算出所有權(quán)重的最大值，并將初始上界設(shè)置為所有權(quán)重的最大值，接下來我們一輪一輪地去遍歷所有實例，并找到權(quán)重大于等于上界的實例。當前輪遍歷結(jié)束后，所有大于等于上界的元素都被選取到了，接下來開始嘗試權(quán)重更低的節(jié)點，直到最后上界為 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);
    }
}

這里面有四個需要注意的點：

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

每一輪后降低上界的值可以取所有權(quán)重的最大公約數(shù)，因為如果每次下降 1 的話，中間這些輪會反復(fù)請求權(quán)重最高的那些實例，導(dǎo)致負載不均衡。

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

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

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

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

在 NGINX 中又叫做平滑加權(quán)負載均衡（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;
    }
}

這里面有三個需要注意的點：

權(quán)重輪轉(zhuǎn)非常適合實例變化頻率非常高的集合，因為它不需要提前構(gòu)建數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

遍歷比較方式

最簡單的實現(xià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.getConnections()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setConnections(best.getConnections() + 1);
        }
        return best;
    }
}

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

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)最少連接負載均衡算法）

加權(quán)最少連接負載均衡算法的實現(xiàn)方式與最少連接負載均衡算法相同，只是在計算時增加了權(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 等價，并且可以避免除法帶來的性能與精度問題

堆維護方式

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)時間負載均衡算法）

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

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

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

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();
        }
    }
}

這里有一個需要注意的點：

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

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

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

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

健康檢查（Health Check）

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

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

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

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

慢啟動（Slow Start）

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

總結(jié)

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