負載均衡中的一致性hash算法

hash簡介

說到底，他是一種hash算法，那什么是hash算法？
hash算法是一種散列算法，常用的比如MD5。抽象來說，他是將任意長度的輸入X，經(jīng)過hash算法后，變成固定長度的輸出Y（輸出Y稱為散列值），多個X可能對應同一個Y（hash碰撞，概率極小極小極小，MD5的碰撞概率為2/2的64次方），且從Y不能反推出X，對X的任意修改，都將導致輸出的Y完全不一樣。
基于以上的這些特性，hash算法可以有以下這些應用場景：

  • 用hash算法對網(wǎng)站的登陸密碼使用散列值保存（利用的是不可反推這一特性，這樣即便淘寶的數(shù)據(jù)庫被盜了，誰也不會知道你到底在淘寶買了些什么...東西）

  • 對比兩個文件是否完全一樣，假如要對比的txt文件中有上萬的字符，如何一個一個去作對比，效率很差，直接對比文件的散列值是否一致即可知道文件是否一致（利用的是輸出的散列值是固定長度）

  • 負載均衡算法
    作為負載均衡算法時，輸入X是客戶端請求的某個唯一ID或者key，hash之后的輸出Y是一個一定范圍內(nèi)的Long類型數(shù)字，然后我們對這個Long類型的數(shù)字進行取模，取模得到的余數(shù)就是需要訪問的節(jié)點唯一編號，利用取模的特性（假如集群中服務器數(shù)量為3臺，那么模數(shù)是3，可以將大量的數(shù)字，映射到[0-3)這個區(qū)間段）將key均勻的映射到集群中的機器上，這樣就達到了負載均衡的目的，算法公式：hash(key) % n，如下圖：

    image.png

最終key1 - keyn會被均勻的分布在圖中的三個節(jié)點上，看似已經(jīng)達到了我們想要的負載均衡的效果了，但是，當客戶端請求在某一時段激增的時候（比如雙十一），我們常常需要增加服務器，雙十一過后，這些增加的服務器又需要下線，那么上圖中的算法，就不足以支撐這種情況，假如這時候node3需要被下線，那么客戶端請求對應的負載均衡算法就變成了hash(key) % 2，這時候客戶端所有請求和節(jié)點之間的映射關(guān)系就全變了，許多請求會被負載均衡到"錯誤的"節(jié)點上去從而拿不到想要的數(shù)據(jù)（如果是緩存，那么絕大部分的獲取緩存的請求都會失效，大量請求會打到DB），人為的去轉(zhuǎn)移數(shù)據(jù)，那只能996.ICU網(wǎng)站見了。為了解決這個問題，所以，我們需要一致性hash算法

一致性hash算法原理

假設(shè)我們采用的hash算法的值空間為0-P，將0-P構(gòu)建成一個hash環(huán)，如下圖：


image.png

在普通的hash算法中，我們僅僅對請求唯一標識做了hash，并且它是一個線性的hash空間，而在一致性hash算法中，還會使用同樣的hash算法對服務器標識做一次hash運算（一般對服務器IP或者主機名做hash運算），然后將兩種hash值映射在這個hash環(huán)（java中可以用TreeMap實現(xiàn)）上面，如下圖：

image.png

一致性hash算法具備以下特性：

  1. 客戶端請求最終會落到他所在hash環(huán)的順時針方向的第一個節(jié)點上，在上圖中，key3，key14，key1024請求最終會落到node1上面，而key5，key76982，key18會落到node3上面。
  2. 當集群中刪除節(jié)點nodex時，原本應該落在nodex上面的請求，會被轉(zhuǎn)移到nodex順時針的下一個節(jié)點，新增節(jié)點同理，可以看到，無論新增還是刪除一個節(jié)點，受影響的都只有一個節(jié)點的數(shù)據(jù)，如下圖：
    image.png

    image.png

    以上的一致性hash算法相比較普通的hash算法有了很大的改進，但是依然存在問題，以刪除節(jié)點為例，刪除一個節(jié)點后，集群中大部分的請求key都會落到node2這個節(jié)點上，已經(jīng)并不是"負載均衡"了。一般的hash環(huán)空間會很大，而如果當集群中節(jié)點數(shù)量不是很多的時候，節(jié)點在環(huán)上面的位置可能會擠在很小的一部分區(qū)域，這樣就導致一大部分請求會落到某個節(jié)點上（數(shù)據(jù)傾斜），為了解決這個問題，一致性hash算法引入虛擬節(jié)點。

虛擬節(jié)點

對每一個服務器節(jié)點進行多次hash，將生成的hash值也分布在hash環(huán)上，這些新生成的節(jié)點稱為虛擬節(jié)點。假設(shè)我們用服務器IP地址來做hash，那么可以在IP地址后面增加編號來做hash運算生成虛擬節(jié)點，增加虛擬節(jié)點后，hash環(huán)如下圖：


image.png

從圖中看到，沒有增加虛擬節(jié)點的時候，大部分的請求會落到node2這個節(jié)點上面，導致node2節(jié)點請求壓力過大，當我們增加虛擬節(jié)點后，node1，node2，node3都能均勻的接收到客戶端的請求。而刪除某個節(jié)點nodex的時候，原本應該落在nodex上面的請求，也會被均勻的分配給其他節(jié)點。

java實現(xiàn)一致性hash算法

首先我們得需要一個hash算法，hash算法有很多種，這里提供兩種實現(xiàn)，一種基于MD5，一種基于FNV1_32_HASH（這種其實是我抄來的，哈哈哈哈~~~~）
基于MD5：

/**
     * hash 運算
     * @param value
     * @return
     */
    public Long hash(String value){
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5.reset();
        byte[] keyBytes = null;
        try {
            keyBytes = value.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("Unknown string :" + value, e);
        }

        md5.update(keyBytes);
        byte[] digest = md5.digest();

        // hash code, Truncate to 32-bits
        long hashCode = ((long) (digest[3] & 0xFF) << 24)
                | ((long) (digest[2] & 0xFF) << 16)
                | ((long) (digest[1] & 0xFF) << 8)
                | (digest[0] & 0xFF);

        long truncateHashCode = hashCode & 0xffffffffL;
        return truncateHashCode;
    }

基于FNV1_32_HASH：

public class HashUtil {
    /**
     * 計算Hash值, 使用FNV1_32_HASH算法
     * @param str
     * @return
     */
    public static int getHash(String str) {
        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash =( hash ^ str.charAt(i) ) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }
}

接下來我們實現(xiàn)hash環(huán)，負載均衡一般是讀多寫少（新增或者刪除節(jié)點畢竟少數(shù)），在讀多寫少的情況下，我們?nèi)菀紫氲接枚鏄鋪韺崿F(xiàn)，在java中一般直接可以用TreeMap來實現(xiàn)，TreeMap是由紅黑樹實現(xiàn)的，很適合作為hash環(huán)的存儲結(jié)構(gòu)，先實現(xiàn)一個沒有虛擬節(jié)點的hash環(huán)：

public class ConsistentHashingWithoutVirtualNode {

    /**
     * 集群地址列表
     */
    private static String[] groups = {
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
        "192.168.0.3:111", "192.168.0.4:111"
    };

    /**
     * 用于保存Hash環(huán)上的節(jié)點
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();

    /**
     * 初始化，將所有的服務器加入Hash環(huán)中
     */
    static {
        // 使用紅黑樹實現(xiàn)，插入效率比較差，但是查找效率極高
        for (String group : groups) {
            int hash = HashUtil.getHash(group);
            System.out.println("[" + group + "] launched @ " + hash);
            sortedMap.put(hash, group);
        }
    }

    /**
     * 計算對應的請求應該落到哪一個節(jié)點上
     *
     * @param key
     * @return
     */
    private static String getServer(String key) {
        int hash = HashUtil.getHash(key);
        // 只取出所有大于該hash值的部分而不必遍歷整個Tree
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，應該映射到第一個group上
            return sortedMap.get(sortedMap.firstKey());
        }
        return subMap.get(subMap.firstKey());
    }

    public static void main(String[] args) {
        // 生成隨機數(shù)進行測試
        Map<String, Integer> resMap = new HashMap<>();

        for (int i = 0; i < 100000; i++) {
            Integer widgetId = (int)(Math.random() * 10000);
            String server = getServer(widgetId.toString());
            if (resMap.containsKey(server)) {
                resMap.put(server, resMap.get(server) + 1);
            } else {
                resMap.put(server, 1);
            }
        }

        resMap.forEach(
            (k, v) -> {
                System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");
            }
        );
    }
}

生成10000個隨機數(shù)字進行測試，最終得到的壓力分布情況如下：

[192.168.0.1:111] launched @ 8518713
[192.168.0.2:111] launched @ 1361847097
[192.168.0.3:111] launched @ 1171828661
[192.168.0.4:111] launched @ 1764547046
group 192.168.0.2:111: 8572(8.572%)
group 192.168.0.1:111: 18693(18.693%)
group 192.168.0.4:111: 17764(17.764%)
group 192.168.0.3:111: 27870(27.87%)
group 192.168.0.0:111: 27101(27.101%)

可以看到，請求分布負載不均衡，接下來我們引入虛擬節(jié)點：

public class ConsistentHashingWithVirtualNode {
    /**
     * 集群地址列表
     */
    private static String[] groups = {
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
        "192.168.0.3:111", "192.168.0.4:111"
    };

    /**
     * 真實集群列表
     */
    private static List<String> realGroups = new LinkedList<>();

    /**
     * 虛擬節(jié)點映射關(guān)系
     */
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();

    private static final int VIRTUAL_NODE_NUM = 1000;

    static {
        // 先添加真實節(jié)點列表
        realGroups.addAll(Arrays.asList(groups));

        // 將虛擬節(jié)點映射到Hash環(huán)上
        for (String realGroup: realGroups) {
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                String virtualNodeName = getVirtualNodeName(realGroup, i);
                int hash = HashUtil.getHash(virtualNodeName);
                System.out.println("[" + virtualNodeName + "] launched @ " + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
    }

    private static String getVirtualNodeName(String realName, int num) {
        return realName + "&&VN" + String.valueOf(num);
    }

    private static String getRealNodeName(String virtualName) {
        return virtualName.split("&&")[0];
    }

    private static String getServer(String key) {
        int hash = HashUtil.getHash(key);
        // 只取出所有大于該hash值的部分而不必遍歷整個Tree
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNodeName;
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，應該映射到第一個group上
            virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
        }else {
            virtualNodeName = subMap.get(subMap.firstKey());
        }
        return getRealNodeName(virtualNodeName);
    }

    public static void main(String[] args) {
        // 生成隨機數(shù)進行測試
        Map<String, Integer> resMap = new HashMap<>();

        for (int i = 0; i < 100000; i++) {
            Integer widgetId = i;
            String group = getServer(widgetId.toString());
            if (resMap.containsKey(group)) {
                resMap.put(group, resMap.get(group) + 1);
            } else {
                resMap.put(group, 1);
            }
        }

        resMap.forEach(
            (k, v) -> {
                System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");
            }
        );
    }
}

在上面的代碼中，我給每個節(jié)點增加了1000個虛擬節(jié)點，測試結(jié)果如下：

group 192.168.0.2:111: 18354(18.354%)
group 192.168.0.1:111: 20062(20.062%)
group 192.168.0.4:111: 20749(20.749%)
group 192.168.0.3:111: 20116(20.116%)
group 192.168.0.0:111: 20719(20.719%)

可以看到負載已經(jīng)基本均衡了。我們試一下刪除和新增節(jié)點的情況：

private static void refreshHashCircle() {
    // 當集群變動時，刷新hash環(huán)，其余的集群在hash環(huán)上的位置不會發(fā)生變動
    virtualNodes.clear();
    for (String realGroup: realGroups) {
        for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
            String virtualNodeName = getVirtualNodeName(realGroup, i);
            int hash = HashUtil.getHash(virtualNodeName);
            System.out.println("[" + virtualNodeName + "] launched @ " + hash);
            virtualNodes.put(hash, virtualNodeName);
        }
    }
}
private static void addGroup(String identifier) {
    realGroups.add(identifier);
    refreshHashCircle();
}

private static void removeGroup(String identifier) {
    int i = 0;
    for (String group:realGroups) {
        if (group.equals(identifier)) {
            realGroups.remove(i);
        }
        i++;
    }
    refreshHashCircle();
}

測試結(jié)果如下：

running the normal test.
group 192.168.0.2:111: 19144(19.144%)
group 192.168.0.1:111: 20244(20.244%)
group 192.168.0.4:111: 20923(20.923%)
group 192.168.0.3:111: 19811(19.811%)
group 192.168.0.0:111: 19878(19.878%)
removed a group, run test again.
group 192.168.0.2:111: 23409(23.409%)
group 192.168.0.1:111: 25628(25.628%)
group 192.168.0.4:111: 25583(25.583%)
group 192.168.0.0:111: 25380(25.38%)
add a group, run test again.
group 192.168.0.2:111: 15524(15.524%)
group 192.168.0.7:111: 16928(16.928%)
group 192.168.0.1:111: 16888(16.888%)
group 192.168.0.4:111: 16965(16.965%)
group 192.168.0.3:111: 16768(16.768%)
group 192.168.0.0:111: 16927(16.927%)

我們可以看到刪除和新增節(jié)點，一致性hash算法依然能保持良好的負載均衡。

redis中的一致性hash算法

未完，待續(xù)。。。。。睡覺！

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容