面試官：負(fù)載均衡的算法你了解不？

作者：懿 2019-12-25 11:22:19

上一篇文章我講了關(guān)于負(fù)載均衡的三種算法，輪詢法，隨機(jī)法，最小連接法，這三種負(fù)載均衡的算法，但是關(guān)于負(fù)載均衡還有其他的算法，我們也需要你去看，而且在面試的過程中，很有可能是會(huì)問到的呦。

[[286766]]

對(duì)于要實(shí)現(xiàn)高性能集群，選擇好負(fù)載均衡器很重要，同時(shí)針對(duì)不同的業(yè)務(wù)場(chǎng)景選擇合適的負(fù)載均衡算法也是非常重要的。之前已經(jīng)羅列出幾個(gè)了，接下來在說剩下的幾個(gè)算法，

1. 源地址哈希算法

唯一不丟失策略的算法，但是負(fù)載均衡和源數(shù)據(jù)信息和哈希算法有很大關(guān)系。

源地址哈希法的思想是根據(jù)服務(wù)消費(fèi)者請(qǐng)求客戶端的 IP 地址，通過哈希函數(shù)計(jì)算得到一個(gè)哈希值，將此哈希值和服務(wù)器列表的大小進(jìn)行取模運(yùn)算，得到的結(jié)果便是要訪問的服務(wù)器地址的序號(hào)。采用源地址哈希法進(jìn)行負(fù)載均衡，相同的 IP 客戶端，如果服務(wù)器列表不變，將映射到同一個(gè)后臺(tái)服務(wù)器進(jìn)行訪問。

還是之前的操作，偽代碼：

private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>(); 
 
static { 
    serviceWeightMap.put("192.168.1.100", 1); 
    serviceWeightMap.put("192.168.1.101", 1); 
    serviceWeightMap.put("192.168.1.102", 4); 
    serviceWeightMap.put("192.168.1.103", 1); 
   } 
 
   public static String testConsumerHash(String remoteIp) { 
 
       Map<String, Integer> serverMap = new HashMap<String, Integer>(); 
       serverMap.putAll(serviceWeightMap); 
 
       //取得IP地址list 
       Set<String> keySet = serverMap.keySet(); 
       ArrayList<String> keyList = new ArrayList<String>(); 
       keyList.addAll(keySet); 
 
       int hashCode = remoteIp.hashCode(); 
       int pos = hashCode % keyList.size(); 
 
       return keyList.get(pos); 
   }

這段代碼來自 Will.Shun 所寫，我當(dāng)時(shí)看到的時(shí)候也不是很明白什么意思，后來看了一下，其實(shí)和它的解釋很類似，通過哈希函數(shù)計(jì)算得到一個(gè)哈希值，將此哈希值和服務(wù)器列表的大小進(jìn)行取模運(yùn)算，得到的結(jié)果便是要訪問的服務(wù)器地址的序號(hào)。

2. 加權(quán)輪詢算法

再來看一下加權(quán)輪訓(xùn)算法，我們先看一下在 Nginx 里面進(jìn)行的權(quán)重配置：

http { 
upstream cluster { 
server a weight=1; 
server b weight=2; 
server c weight=3; 
}

假如 Nginx 每收到 6 個(gè)客戶端的請(qǐng)求，會(huì)把其中的 1 個(gè)轉(zhuǎn)發(fā)給后端 a，把其中的 2 個(gè)轉(zhuǎn)發(fā)給后端 b，把其中的 3 個(gè)轉(zhuǎn)發(fā)給后端 c。

加權(quán)輪詢算法的結(jié)果，就是要生成一個(gè)服務(wù)器序列。每當(dāng)有請(qǐng)求到來時(shí)，就依次從該序列中取出下一個(gè)服務(wù)器用于處理該請(qǐng)求。

加權(quán)輪訓(xùn)算法偽代碼：

private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>(); 
 
static { 
    serviceWeightMap.put("192.168.1.100", 1); 
    serviceWeightMap.put("192.168.1.101", 1); 
    serviceWeightMap.put("192.168.1.102", 4); 
    serviceWeightMap.put("192.168.1.103", 1); 
   } 
 
 
    public static String testWeightRoundRobin() { 
 
        // 重新創(chuàng)建一個(gè)map，避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題 
        Map<String, Integer> serverMap = new HashMap<String, Integer>(); 
        serverMap.putAll(serviceWeightMap); 
 
        //取得IP地址list 
        Set<String> keySet = serverMap.keySet(); 
        Iterator<String> it = keySet.iterator(); 
 
        List<String> serverList = new ArrayList<String>(); 
 
        while (it.hasNext()) { 
            String server = it.next(); 
            Integer weight = serverMap.get(server); 
            for (int i=0; i<weight; i++) { 
                serverList.add(server); 
            } 
        } 
 
        String server = null; 
 
        synchronized (pos) { 
            if (pos > serverList.size()) { 
                pos = 0; 
            } 
 
            server = serverList.get(pos); 
            pos++; 
        } 
 
        return server; 
}

其實(shí)在加權(quán)輪訓(xùn)算法中，是有缺陷的，在某些特殊的權(quán)重下，加權(quán)輪詢調(diào)度會(huì)生成不均勻的實(shí)例序列，這種不平滑的負(fù)載可能會(huì)使某些實(shí)例出現(xiàn)瞬時(shí)高負(fù)載的現(xiàn)象，導(dǎo)致系統(tǒng)存在宕機(jī)的風(fēng)險(xiǎn)。而為了解決這個(gè)調(diào)度的缺陷，后邊就有平滑加權(quán)輪訓(xùn)調(diào)度，有興趣的同學(xué)一定要去看一下這個(gè)平滑加權(quán)輪訓(xùn)。

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

加權(quán)隨機(jī)法跟加權(quán)輪詢法類似，根據(jù)后臺(tái)服務(wù)器不同的配置和負(fù)載情況，配置不同的權(quán)重。不同的是，它是按照權(quán)重來隨機(jī)選取服務(wù)器的，而非順序。

private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>(); 
 
    static { 
        serviceWeightMap.put("192.168.1.100", 1); 
        serviceWeightMap.put("192.168.1.101", 1); 
        serviceWeightMap.put("192.168.1.102", 4); 
        serviceWeightMap.put("192.168.1.103", 1); 
       } 
 
    public static String testWeightRandom() { 
        // 重新創(chuàng)建一個(gè)map，避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題 
        Map<String, Integer> serverMap = new HashMap<String, Integer>(); 
        serverMap.putAll(serviceWeightMap); 
 
        //取得IP地址list 
        Set<String> keySet = serverMap.keySet(); 
        List<String> serverList = new ArrayList<String>(); 
        Iterator<String> it = keySet.iterator(); 
 
        while (it.hasNext()) { 
            String server = it.next(); 
            Integer weight = serverMap.get(server); 
            for (int i=0; i<weight; i++) { 
                serverList.add(server); 
            } 
        } 
 
        Random random = new Random(); 
        int randomPos = random.nextInt(serverList.size()); 
 
        String server = serverList.get(randomPos); 
 
        return server; 
    }

這里不同的地方就是服務(wù)器是通過隨機(jī)算法獲取。

其實(shí)我們可以想一個(gè)實(shí)例：比如說在以下場(chǎng)景：有一個(gè)集合 S，里面比如有 A,B,C,D 這四項(xiàng)。這時(shí)我們想隨機(jī)從中抽取一項(xiàng)，但是抽取的概率不同，比如我們希望抽到 A 的概率是 50%,抽到 B 和 C 的概率是 20%,D 的概率是 10%。一般來說，我們可以給各項(xiàng)附一個(gè)權(quán)重，抽取的概率正比于這個(gè)權(quán)重。

4.HTTP 國際化

HTTP 報(bào)文中可以承載以任何語言表示的內(nèi)容，就像它能承載圖像、影片，或任何類型的媒體那樣。對(duì) HTTP 來說，實(shí)體主體只是二進(jìn)制信息的容器而已。

為了支持國際性的內(nèi)容，服務(wù)器需要告知客戶端每個(gè)文檔的字母表和語言，這樣客戶端才能正確地把文檔中的信息解包為字符并把內(nèi)容呈現(xiàn)給用戶。

服務(wù)器通過 HTTP 協(xié)議的 Content-Type 首部中的 charset 參數(shù)和 Content-Language 首部告知客戶端文檔的字母表和語言。這些首部描述了實(shí)體主體的“信息盒子”里面裝的是什么，如何把內(nèi)容轉(zhuǎn)換成合適的字符以便顯示在屏幕上以及里面的詞語表示的是哪種語言。

同時(shí)，客戶端需要告知服務(wù)器用戶理解何種語言，瀏覽器上安裝了何種字母表編碼算法。客戶端發(fā)送 Accept-Charset 首部和 Accept-Language 首部，告知服務(wù)器它理解哪些字符集編碼算法和語言以及其中的優(yōu)先順序。

責(zé)任編輯：華軒來源： Java極客技術(shù)