摘要：負(fù)載均衡算法的選擇常用的負(fù)載均衡算法有哪些呢隨機(jī)算法，輪詢，算法，加權(quán)隨機(jī)算法，加權(quán)輪詢算法，一致性算法。首選，我們會(huì)有集群對(duì)應(yīng)的的地址列表，然后我們通過某種算法這里指的就是負(fù)載均衡算法，獲取其中一個(gè)的地址進(jìn)行任務(wù)提交這就是任務(wù)調(diào)度。

有這么一個(gè)場(chǎng)景，我們有兩個(gè)Hive集群，Hive集群1（后面成為1號(hào)集群）是一直專享于數(shù)據(jù)計(jì)算平臺(tái)的，而Hive集群2（后面成為2號(hào)集群）是用于其他團(tuán)隊(duì)使用的，比如特征，廣告等。而由此存在兩個(gè)主要問題：a) 兩個(gè)Hive集群共享了同一份MetaData，導(dǎo)致經(jīng)常會(huì)出現(xiàn)在HUE（建立與2號(hào)集群上）上建表成功后，但是在計(jì)算平臺(tái)上卻無法查詢到新建表信息；b) 讓運(yùn)維同學(xué)們同時(shí)維護(hù)兩套集群，管理和資源分配調(diào)整起來的確是麻煩很多，畢竟也不利于資源的彈性分配。那么鑒于此，經(jīng)過討論，需要做這么一樣工作：兩個(gè)集群合二為一，由1號(hào)集群合并到2號(hào)集群上來。

但是，集群合并是不可能一下子全部合并，需要逐步遷移合并（比如每次20個(gè)結(jié)點(diǎn)）到2號(hào)集群。但是這樣存在一個(gè)問題，計(jì)算平臺(tái)每天使用的計(jì)算資源是差不多固定的，而在遷移過程中，1號(hào)集群的資源在逐漸減少，顯然是不滿足計(jì)算需求的，所以我們也需要由得到遷移資源的2號(hào)集群分擔(dān)一些壓力。那么重點(diǎn)來了，這就需要我們?nèi)蝿?wù)調(diào)度器合理的分配任務(wù)到1號(hào)集群以及2號(hào)集群的某個(gè)隊(duì)列。其實(shí)，所謂的任務(wù)分配也就是一種負(fù)載均衡算法，即任務(wù)來了，通過負(fù)載均衡算法調(diào)度到哪個(gè)集群去執(zhí)行，但是使用哪種負(fù)載均衡算法就需要好好探究一下。

Q：常用的負(fù)載均衡算法有哪些呢？
A：隨機(jī)算法，輪詢，hash算法，加權(quán)隨機(jī)算法，加權(quán)輪詢算法，一致性hash算法。

隨機(jī)算法

該算法通過產(chǎn)生隨機(jī)數(shù)的方式進(jìn)行負(fù)載，可能會(huì)導(dǎo)致任務(wù)傾斜，比如大量任務(wù)調(diào)度到了1好集群，顯然不可取，pass。

輪詢

該算法是通過一個(gè)接一個(gè)循環(huán)往復(fù)的方式進(jìn)行調(diào)度，會(huì)保證任務(wù)分配很均衡，但是我們的1號(hào)集群資源是在不斷減少的，2號(hào)集群資源是在不斷增加的，如果均衡分配計(jì)算任務(wù)，顯然也是不合理的，pass。

hash算法

該算法是基于當(dāng)前結(jié)點(diǎn)的ip的hashCode值來進(jìn)行調(diào)度，那么只要結(jié)點(diǎn)ip不變，那么hashCode值就不會(huì)變，所有的任務(wù)豈不是都提交到一個(gè)結(jié)點(diǎn)了嗎？不合理，pass。

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

同隨機(jī)算法，只不過是對(duì)每個(gè)結(jié)點(diǎn)增加了權(quán)重，但是因?yàn)槭请S機(jī)調(diào)度，不可控的，直接pass。

加權(quán)輪詢算法

上面說到，輪詢算法可以保證任務(wù)分配很均衡，但是無法保證隨集群資源的調(diào)整進(jìn)行任務(wù)分配的動(dòng)態(tài)調(diào)整。此時(shí)，如果我們可以依次根據(jù)集群遷移情況，設(shè)置1號(hào)集群與2號(hào)集群的任務(wù)比重為：7:5 -> 3:2 -> 2:3 -> 完整切換。可行。

一致性hash算法

該算法較為復(fù)雜，鑒于我們是為了進(jìn)行集群合并以及保證任務(wù)盡量根據(jù)集群資源的調(diào)整進(jìn)行合理調(diào)度，無需設(shè)計(jì)太復(fù)雜的算法進(jìn)行處理，故也pass。

雖然我們最終方法選定為加權(quán)輪詢算法，但是它起源于輪詢算法，那么我們就從輪詢算法說起。

首選，我們會(huì)有Hive集群對(duì)應(yīng)的HS2的ip地址列表，然后我們通過某種算法（這里指的就是負(fù)載均衡算法），獲取其中一個(gè)HS2的ip地址進(jìn)行任務(wù)提交（這就是任務(wù)調(diào)度）。

我們先定義一個(gè)算法抽象接口，它只有一個(gè)select方法。

import java.util.List;

/**
 * @author buildupchao
 * @date: 2019/5/12 21:51
 * @since JDK 1.8
 */
public interface ClusterStrategy {

    /**
     * 負(fù)載均衡算法接口
     * @param ipList ip地址列表
     * @return 通過負(fù)載均衡算法選中的ip地址
     */
    String select(List ipList);
}

輪詢算法實(shí)現(xiàn)：

import org.apache.commons.lang3.StringUtils;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author buildupchao
 * @date: 2019/5/12 21:57
 * @since JDK 1.8
 */
public class PollingClusterStrategyImpl implements ClusterStrategy {

    private AtomicInteger counter = new AtomicInteger(0);

    @Override
    public String select(List ipList) {
        String selectedIp = null;
        try {
            int size = ipList.size();
            if (counter.get() >= size) {
                counter.set(0);
            }
            selectedIp = ipList.get(counter.get());
            counter.incrementAndGet();

        } catch (Exception ex) {
            ex.printStackTrace();
        }
        if (StringUtils.isBlank(selectedIp)) {
            selectedIp = ipList.get(0);
        }
        return selectedIp;
    }

    public static void main(String[] args) {
        List ipList = Arrays.asList("172.31.0.191", "172.31.0.192");
        PollingClusterStrategyImpl strategy = new PollingClusterStrategyImpl();
        ExecutorService executorService = Executors.newFixedThreadPool(100);
        for (int i = 0; i < 100; i++) {
            executorService.execute(() -> {
                System.out.println(Thread.currentThread().getName() + ":" + strategy.select(ipList));
            });
        }
    }
}

運(yùn)行上述代碼，你會(huì)發(fā)現(xiàn)，線程號(hào)為奇數(shù)的輪詢到的是"172.31.0.191"這個(gè)ip，偶數(shù)是‘172.31.0.192’這個(gè)ip。至于打印出來的日志亂序，那是并發(fā)打印返回的ip的問題，并不是獲取ip進(jìn)行任務(wù)調(diào)度的問題。

既然我們已經(jīng)實(shí)現(xiàn)了輪詢算法，那加權(quán)輪詢?cè)趺磳?shí)現(xiàn)呢？無非是增加結(jié)點(diǎn)被輪詢到的比例罷了，我們只需要根據(jù)指定的權(quán)重，進(jìn)行輪詢即可。因?yàn)樾枰袡?quán)重等信息，我們需要重新設(shè)計(jì)接口。

提供一個(gè)Bean進(jìn)行封裝ip以及權(quán)重等信息：

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.io.Serializable;

/**
 * @author buildupchao
 *         Date: 2019/2/1 02:52
 * @since JDK 1.8
 */
@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class ProviderService implements Serializable {
    private String ip;
    // the weight of service provider
    private int weight;
}

新的負(fù)載均衡算法接口：

import com.buildupchao.zns.client.bean.ProviderService;

import java.util.List;

/**
 * @author buildupchao
 *         Date: 2019/2/1 02:44
 * @since JDK 1.8
 */
public interface ClusterStrategy {

    ProviderService select(List serviceRoutes);
}

加權(quán)輪詢算法的實(shí)現(xiàn)：

import com.buildupchao.zns.client.bean.ProviderService;
import com.buildupchao.zns.client.cluster.ClusterStrategy;
import com.google.common.collect.Lists;

import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author buildupchao
 *         Date: 2019/2/4 22:39
 * @since JDK 1.8
 */
public class WeightPollingClusterStrategyImpl implements ClusterStrategy {

    private int counter = 0;
    private Lock lock = new ReentrantLock();

    @Override
    public ProviderService select(List serviceRoutes) {
        ProviderService providerService = null;

        try {
            lock.tryLock(10, TimeUnit.SECONDS);
            List providerServices = Lists.newArrayList();
            for (ProviderService serviceRoute : serviceRoutes) {
                int weight = serviceRoute.getWeight();
                for (int i = 0; i < weight; i++) {
                    providerServices.add(serviceRoute);
                }
            }

            if (counter >= providerServices.size()) {
                counter = 0;
            }
            providerService = providerServices.get(counter);
            counter++;
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        } finally {
            lock.unlock();
        }

        if (providerService == null) {
            providerService = serviceRoutes.get(0);
        }
        return providerService;
    }
}

你會(huì)發(fā)現(xiàn)這里的算法實(shí)現(xiàn)中不再是通過AtomicInteger來做計(jì)數(shù)器了，而是借助于private int counter = 0;同時(shí)借助于Lock鎖的技術(shù)保證計(jì)數(shù)器的安全訪問。只是寫法的不同，不用糾結(jié)啦！

這樣，我們就可以應(yīng)用這個(gè)加權(quán)輪詢算法到我們的任務(wù)調(diào)度器中了，快速配合運(yùn)維完成集群遷移合并工作吧！

常用的負(fù)載均衡算法有：隨機(jī)算法，輪詢，hash算法，加權(quán)隨機(jī)算法，加權(quán)輪詢算法，一致性hash算法

和業(yè)務(wù)場(chǎng)景最契合的負(fù)載均衡算法才是最合適的

加權(quán)輪詢負(fù)載均衡算法只是在輪詢算法基礎(chǔ)上根據(jù)權(quán)重把對(duì)應(yīng)的信息進(jìn)行平鋪多份，從而提高比重實(shí)現(xiàn)加權(quán)的效果

負(fù)載均衡算法的實(shí)現(xiàn)可以參考zns項(xiàng)目中的運(yùn)用