負(fù)載均衡在分布式系統(tǒng)中異常地重要壁畸，下面主要講解一下幾種負(fù)載均衡算法的實(shí)現(xiàn)阀趴。

先給個(gè)基本類氢架，下面的類都是在這個(gè)類的基礎(chǔ)上實(shí)現(xiàn)的

public class IpMap {
    public static HashMap<String, Integer> serverMap = new HashMap<>();

    static {
        serverMap.put("192.168.1.1", 1);
        serverMap.put("192.168.1.2", 1);
        serverMap.put("192.168.1.3", 3);
        serverMap.put("192.168.1.4", 1);
        serverMap.put("192.168.1.5", 4);
        serverMap.put("192.168.1.6", 1);
        serverMap.put("192.168.1.7", 1);
        serverMap.put("192.168.1.10", 2);
        serverMap.put("192.168.1.11", 1);
        serverMap.put("192.168.1.12", 1);
    }
}

RoundRobin 輪詢法

輪詢法，是按公約后的權(quán)重設(shè)置輪詢比率，到達(dá)邊界之后券敌，繼續(xù)繞接唾戚。主要分為普通輪詢和權(quán)重輪詢

普通輪詢法

public class RoundRobin {

    // 輪詢的位置
    private static Integer position = 0;

    public static String getString () {
        // 本地保留服務(wù)端列表，避免服務(wù)器上下線導(dǎo)致并發(fā)問(wèn)題
        Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);

        // 獲取服務(wù)端ip列表
        Set<String> keySet = serverMap.keySet();
        List<String> serverList = new ArrayList<>(keySet);

        String server = null;

        // 防止并發(fā)問(wèn)題
        synchronized (position) {
            // 環(huán)形輪詢
            if (position >= keySet.size()) {
                position = 0;
            }
            server = serverList.get(position);
            position++;
        }
        return server;
    }
}

IpMap.serverMap是動(dòng)態(tài)變化的陪白，上下線宕機(jī)都是隨時(shí)隨地的颈走。為了避免IpMap.serverMap被多線程修改導(dǎo)致并發(fā)問(wèn)題，特此將列表緩存在本地咱士。但是這樣可能會(huì)導(dǎo)致服務(wù)端列表修改后立由，不能及時(shí)同步，這個(gè)時(shí)候就需要集群容錯(cuò)策略了序厉。

對(duì)于當(dāng)前輪詢的位置變量position锐膜，為了保證服務(wù)器選擇的順序性，需要在操作的時(shí)候加鎖或者cas

• 優(yōu)點(diǎn)：能夠做到流量分配的絕對(duì)平衡
• 缺點(diǎn)：需要對(duì)position加鎖弛房，并發(fā)吞吐量明顯下降

加權(quán)輪詢法

public class WeightRoundRobin {

    private static AtomicInteger position = new AtomicInteger(0);

    public static String getString () {
        Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
        List<String> serverList = new ArrayList<>();
        serverMap.forEach((serverIp, weight) -> {
            for (int i = 0; i < weight; i++) {
                serverList.add(serverIp);
            }
        });
        if (position.get() >= serverList.size()) {
            position.set(0);
        }
        position.getAndIncrement();
        return serverList.get(position.get());
    }
}

與輪詢法類似道盏，但是列表中根據(jù)權(quán)重會(huì)增加serverIp的個(gè)數(shù)，權(quán)重多的訪問(wèn)的就多文捶。

輪詢法分析

1. 輪詢法其實(shí)主要還是想打到一種絕對(duì)的流量平衡荷逞，但是進(jìn)行了并發(fā)控制，會(huì)比較影響并發(fā)和吞吐量
2. 如果某一服務(wù)器響應(yīng)過(guò)慢粹排，但是還沒(méi)達(dá)到宕機(jī)的地步种远，這會(huì)導(dǎo)致多個(gè)請(qǐng)求打到同一臺(tái)機(jī)器上，產(chǎn)生數(shù)據(jù)傾斜

隨機(jī)法

隨機(jī)法主要分為普通隨機(jī)和權(quán)重隨機(jī)

普通隨機(jī)法

public class Random {

    public static String getString () {
        Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);

        Set<String> keySet = serverMap.keySet();
        List<String> serverList = new ArrayList<>(keySet);
        java.util.Random random = new java.util.Random();
        return serverList.get(random.nextInt(keySet.size()));
    }
}

這塊其實(shí)就是在整體的server列表進(jìn)行隨機(jī)顽耳。

加權(quán)隨機(jī)法

public class WeightRandom {

    public static String getString () {
        Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
        List<String> serverList = new ArrayList<>();
        serverMap.forEach((serverIp, weight) -> {
            for (int i = 0; i < weight; i++) {
                serverList.add(serverIp);
            }
        });
        Random random = new Random();
        return serverList.get(random.nextInt(serverList.size()));
    }
}

這塊不解釋了

隨機(jī)法分析

1. 既然是隨機(jī)法坠敷，可理解為，當(dāng)請(qǐng)求量比較大的時(shí)候射富，請(qǐng)求分布會(huì)相對(duì)均勻一些膝迎。類似于硬幣，當(dāng)你拋100000次胰耗，基本上正反面出現(xiàn)次數(shù)是1比1限次。而且沒(méi)有加鎖，對(duì)并發(fā)和吞吐會(huì)比較友好
2. 請(qǐng)求量比較低的時(shí)候柴灯，可能會(huì)出現(xiàn)數(shù)據(jù)傾斜
3. 非對(duì)等集群組網(wǎng)卖漫，硬件配置較大時(shí)，會(huì)導(dǎo)致各個(gè)節(jié)點(diǎn)負(fù)載不均勻

哈希法

哈希法主要分為普通哈希和一致性hash

普通哈希法

public class OriginHash {

    public static String getString () {
        Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);

        Set<String> keySet = serverMap.keySet();
        List<String> serverList = new ArrayList<>(keySet);
        String clientIp = "127.0.0.1";
        int clientIpHashcode = clientIp.hashCode();
        return serverList.get(clientIpHashcode % keySet.size());
    }
}

主要是根據(jù)客戶端某一個(gè)數(shù)據(jù)進(jìn)行hash弛槐，可以為ip，mac等信息

一致性哈希

一致性hash最初是為了memcache提出的負(fù)載均衡算法依啰，但是由于該算法優(yōu)良乎串，性能比較好，所以目前已經(jīng)用于各種分布式架構(gòu)上了。

基本概念

一致性hash將整個(gè)hash空間組織成一個(gè)虛擬的圓環(huán)叹誉，普通的hash算法可能是對(duì)服務(wù)器的數(shù)量進(jìn)行取模鸯两，而一致性hash是對(duì)2^32取模， 也就是說(shuō)长豁，哈希函數(shù)的H值的空間為0-(2^32 - 1)

[站外圖片上傳中...(image-456ebf-1563700555907)]

整個(gè)空間按順時(shí)針組織钧唐，0 和 2^32 - 1重合

下面將各個(gè)服務(wù)端的服務(wù)器進(jìn)行hash，hash的key可以為ip或主機(jī)名或mac匠襟，這樣每臺(tái)機(jī)器能夠確定在這個(gè)環(huán)中的位置钝侠，假設(shè)四臺(tái)服務(wù)端服務(wù)器用ip地址映射到下面的環(huán)上

1.jpeg

接下來(lái)使用如下算法定位數(shù)據(jù)訪問(wèn)的相應(yīng)服務(wù)器：將數(shù)據(jù)key（客戶端服務(wù)器）使用相同的函數(shù)hash計(jì)算出哈希值，確定在環(huán)中的位置酸舍，從這個(gè)位置沿著順時(shí)針遍歷帅韧，第一臺(tái)遇到的服務(wù)器就是定位到的服務(wù)器

假設(shè)有A，B, C, D四個(gè)客戶端啃勉，經(jīng)過(guò)hash后忽舟，位置在環(huán)上如下位置

客戶端節(jié)點(diǎn)分布在hash圓環(huán)上

通過(guò)一致性hash的算法，可以看出淮阐，最終A定位在NodeA上叮阅，B定位在NodeB上，C定位在NodeC上泣特，D定位在NodeD上浩姥。

性質(zhì)分析

分析一下一致性hash的容錯(cuò)性和可擴(kuò)展性。假設(shè)C不行宕機(jī)群扶，客戶端ABD都不會(huì)受到影響及刻，只有C受到影響。假設(shè)增加一臺(tái)服務(wù)器X竞阐，如下圖所示

添加節(jié)點(diǎn)

其實(shí)也只是影響了C一個(gè)客戶節(jié)點(diǎn)缴饭。則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即沿著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器）之間數(shù)據(jù)，其它數(shù)據(jù)也不會(huì)受到影響骆莹。

這個(gè)時(shí)候考慮如果是普通的hash算法颗搂，看下表：

可以看到，其實(shí)全亂了....

虛擬節(jié)點(diǎn)

如果一致性hash中節(jié)點(diǎn)較少幕垦，會(huì)產(chǎn)生因?yàn)楣?jié)點(diǎn)分布不均勻的數(shù)據(jù)傾斜問(wèn)題丢氢。

少量數(shù)據(jù)產(chǎn)生數(shù)據(jù)傾斜問(wèn)題

會(huì)導(dǎo)致大部分?jǐn)?shù)據(jù)集中在A上，少量定位在B上先改，為了解決這個(gè)問(wèn)題疚察，引入了虛擬節(jié)點(diǎn)。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號(hào)來(lái)實(shí)現(xiàn)仇奶。例如上面的情況貌嫡，可以為每臺(tái)服務(wù)器計(jì)算三個(gè)虛擬節(jié)點(diǎn)，于是可以分別計(jì)算 “Node A#1”、“Node A#2”岛抄、“Node A#3”别惦、“Node B#1”、“Node B#2”夫椭、“Node B#3”的哈希值掸掸，于是形成六個(gè)虛擬節(jié)點(diǎn)：

添加虛擬節(jié)點(diǎn)

那么虛擬節(jié)點(diǎn)其實(shí)最終指向的也是實(shí)際節(jié)點(diǎn)

實(shí)現(xiàn)

public class ConsistentHash<T> {

    /**
     * 節(jié)點(diǎn)的復(fù)制因子
     */
    private int numberOfReplicas;

    /**
     * 虛擬節(jié)點(diǎn)個(gè)數(shù)
     */
    private final SortedMap<Integer, T> circle = new TreeMap<>();

    /**
     * 初始化節(jié)點(diǎn)
     * @param numberOfReplicas
     * @param nodes
     */
    public ConsistentHash (int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 將節(jié)點(diǎn)加入環(huán)內(nèi)
     * @param node
     */
    public void add (T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String nodeStr = node.toString() + i;
            System.out.println("nodeStr:" + nodeStr);
            int hashCode = nodeStr.hashCode();
            System.out.println("hashCode:" + hashCode);
            circle.put(hashCode, node);
        }
    }

    /**
     * 從環(huán)中刪除節(jié)點(diǎn)
     * @param node
     */
    public void remove (T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(node.toString() + i);
        }
    }

    /**
     * 從環(huán)中查找對(duì)應(yīng)的數(shù)據(jù)
     * @param key
     * @return
     */
    public T get (Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = key.hashCode();
        if (!circle.containsKey(hash)) {
            // 從環(huán)中hash的位置開(kāi)始，找到值大于hash的列表
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            // 如果為空蹭秋，說(shuō)明已經(jīng)到末尾了扰付，取第一個(gè)；如果非空感凤，取最近的第一個(gè)節(jié)點(diǎn)
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    public long getSize () {
        return circle.size();
    }

    public void testBalance () {
        Set<Integer> set = circle.keySet();
        SortedSet<Integer> sortedSet = new TreeSet<>(set);
        System.out.println(sortedSet);
        System.out.println("------------------------------------");
    }

    public static void main (String[] args) {
        Set<String> nodes = new HashSet<>();
        nodes.add("a");
        nodes.add("b");
        nodes.add("c");
        ConsistentHash<String> consistentHash = new ConsistentHash<>(2, nodes);
        consistentHash.add("d");
        System.out.println("hash circle size:" + consistentHash.getSize());
        consistentHash.testBalance();
        System.out.println(consistentHash.get("a3"));
    }
}

其實(shí)上面例子中的節(jié)點(diǎn)并不是很好悯周，取的a,b,c,d，導(dǎo)致hash的比較集中陪竿，但是意思是這樣禽翼，具體時(shí)間盡量避免節(jié)點(diǎn)集中，而且虛擬節(jié)點(diǎn)要選好散列

服務(wù)調(diào)用時(shí)延

消費(fèi)者會(huì)緩存所有服務(wù)提供者的服務(wù)調(diào)用時(shí)延族跛，周期性地計(jì)算服務(wù)調(diào)用平均時(shí)延闰挡，然后計(jì)算每個(gè)服務(wù)提供者服務(wù)調(diào)用時(shí)延與平均時(shí)延的差值，根據(jù)差值大小調(diào)整權(quán)重礁哄，盡量保證服務(wù)調(diào)用時(shí)延大的接受更少的請(qǐng)求

粘滯連接

粘滯連接用于有狀態(tài)的服務(wù)长酗，盡可能讓客戶端總是像同一服務(wù)提供者發(fā)起服務(wù)調(diào)用，除非它宕機(jī)桐绒。但是服務(wù)一般都是無(wú)狀態(tài)的夺脾，所以很少使用