一致性Hash算法

最近在做Redis方面的一些工作，其中Redis3.0以前的版本，服務(wù)器端沒(méi)有提供集群的方式。需要在客戶端做sharding。redis客戶端做sharding的話，需要用到一致性Hash算法。

假設(shè)我們有3臺(tái)redis服務(wù)器。


一、普通Hash算法

1、首先對(duì)3臺(tái)redis服務(wù)器的ip地址，進(jìn)行hash運(yùn)算。得到一個(gè)int類型的值。hash算法如下：

private 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;

        // 如果算出來(lái)的值為負(fù)數(shù)則取其絕對(duì)值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
}

2、利用得到的hash值對(duì)3進(jìn)行取模

getHash(192.168.7.1)=196713682%3=1
getHash(192.168.7.2)=467665103%3=2
getHash(192.168.7.3)=542751888%3=0

3、假如我們想要把鍵值對(duì)name=linlin。存入到redis中，因?yàn)橛?臺(tái)redis存在，所以必須要決定將鍵值對(duì)存入到哪一臺(tái)中。對(duì)key值name進(jìn)行hash，然后對(duì)3進(jìn)行取模。

getHash("name")=117328155%3=0

所以鍵值對(duì)name=linlin會(huì)被路由到192.168.7.3這臺(tái)服務(wù)器中。
4、使用Java來(lái)實(shí)現(xiàn)

  1. 創(chuàng)建RedisNode類
package com.lin.hash.redis;

import java.util.HashMap;
import java.util.Map;

public class RedisNode {
    private String ip;

    private Map<String,Object> data;

    public RedisNode(String ip) {
        this.ip = ip;
        data = new HashMap<>();
    }
    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public Map<String, Object> getData() {
        return data;
    }

    public void setData(Map<String, Object> data) {
        this.data = data;
    }

    public Object getNodeValue(String key){
        return data.get(key);
    }
}

2.創(chuàng)建抽象類

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public abstract class RedisCluster {
    protected List<RedisNode> redisNodes;


    public RedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public abstract void addRedisNode(RedisNode redisNode);

    public abstract RedisNode getRedisNode(String key);

    public abstract void removeRedisNode(RedisNode redisNode);
}

3.創(chuàng)建NormalRedisCluster類

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class NormalRedisCluster extends RedisCluster {
    private List<RedisNode> redisNodes;


    public NormalRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);
    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        /**使用key的hash值對(duì)key進(jìn)行取模*/
        RedisNode redisNode = redisNodes.get(hash % redisNodes.size());
        return redisNode;
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

4.創(chuàng)建HashUtils

package com.lin.hash.redis;

public class HashUtils {
    /**
     * 使用FNV1_32_HASH算法計(jì)算服務(wù)器的Hash值,這里不使用重寫hashCode的方法，最終效果沒(méi)區(qū)別
     */
    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;

        // 如果算出來(lái)的值為負(fù)數(shù)則取其絕對(duì)值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
}

5.創(chuàng)建RedisHashTest類

package com.lin.hash.redis;

import com.alibaba.fastjson.JSONObject;

import java.util.List;
import java.util.Map;

public class RedisHashTest {
    public static void main(String[] args) {
        String[] servers = {"192.168.7.1","192.168.7.2","192.168.7.3"};

        /**
         * 添加redis節(jié)點(diǎn)
         */
        RedisCluster redisCluster = new NormalRedisCluster();
        for (String server:servers){
            redisCluster.addRedisNode(new RedisNode(server));
        }

        /**
         * 往redis集群中加入100條數(shù)據(jù)
         * */

        int dataCount = 100;

        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;

            /**獲取節(jié)點(diǎn)*/
            RedisNode redisNode = redisCluster.getRedisNode(key);
            Map<String, Object> data = redisNode.getData();
            data.put(key,value);
        }

        /**獲取redis節(jié)點(diǎn)中的數(shù)據(jù)分布*/
        List<RedisNode> redisNodes = redisCluster.getRedisNodes();
        for (RedisNode redisNode:redisNodes){
            System.out.println(JSONObject.toJSONString(redisNode.getData()));
        }

        /**查看節(jié)點(diǎn)不變的情況下，redis數(shù)據(jù)的命中率*/
        int hitCount = 0;
        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;
            Object nodeValue = redisCluster.getRedisNode(key).getNodeValue(key);
            if (nodeValue != null){
                hitCount++;
            }
        }

        System.out.println("數(shù)據(jù)命中率為："+hitCount*1.0/dataCount);

        /**新增一個(gè)節(jié)點(diǎn)的情況下數(shù)據(jù)的命中率*/
        redisCluster.addRedisNode(new RedisNode("192.168.7.4"));
        hitCount=0;
        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;
            Object nodeValue = redisCluster.getRedisNode(key).getNodeValue(key);
            if (nodeValue != null){
                hitCount++;
            }
        }
        System.out.println("新增節(jié)點(diǎn)的情況下，redis數(shù)據(jù)的命中率:"+hitCount*1.0/dataCount);

//        /**刪除一個(gè)節(jié)點(diǎn)的情況下數(shù)據(jù)的命中率*/
//        normalRedisCluster.removeRedisNode(new RedisNode("192.168.7.2"));
//        hitCount=0;
//        for (int i=0;i<dataCount;i++){
//            String key = "name"+i;
//            String value = "linlin"+i;
//            Object nodeValue = normalRedisCluster.getRedisNode(key).getNodeValue(key);
//            if (nodeValue != null){
//                hitCount++;
//            }
//        }
//        System.out.println("刪除節(jié)點(diǎn)的情況下，redis數(shù)據(jù)的命中率:"+hitCount*1.0/dataCount);
    }
}

5.我們可以看到在節(jié)點(diǎn)保持不變的情況下，數(shù)據(jù)的命中率為1.0。
新增一個(gè)節(jié)點(diǎn)的命中率為：0.27
刪除一個(gè)節(jié)點(diǎn)的命中率為：0.4
但是無(wú)論是新增一個(gè)節(jié)點(diǎn)或者刪除一個(gè)節(jié)點(diǎn)。數(shù)據(jù)的命中率都會(huì)顯著降低。

一致性Hash算法

關(guān)于一致性Hash算法的原理，網(wǎng)絡(luò)上已經(jīng)有很多非常棒的文章，我在這里就不解釋了，為了文章的完整性，在這里將原理貼出來(lái)：

先構(gòu)造一個(gè)長(zhǎng)度為232的整數(shù)環(huán)（這個(gè)環(huán)被稱為一致性Hash環(huán)），根據(jù)節(jié)點(diǎn)名稱的Hash值（其分布為[0, 232-1]）將服務(wù)器節(jié)點(diǎn)放置在這個(gè)Hash環(huán)上，然后根據(jù)數(shù)據(jù)的Key值計(jì)算得到其Hash值（其分布也為[0, 232-1]），接著在Hash環(huán)上順時(shí)針查找距離這個(gè)Key值的Hash值最近的服務(wù)器節(jié)點(diǎn)，完成Key到服務(wù)器的映射查找。

一直性Hash算法會(huì)導(dǎo)致數(shù)據(jù)分布不均勻的情況產(chǎn)生。如下圖所示


image.png

按照一致性Hash的原理，因?yàn)锳-B區(qū)間占了圓環(huán)的絕大部分，所以大部分的數(shù)據(jù)都會(huì)落入到B節(jié)點(diǎn)上，這樣就會(huì)導(dǎo)致數(shù)據(jù)不會(huì)均勻的分不到A-B兩個(gè)節(jié)點(diǎn)中。從而導(dǎo)致負(fù)載不均衡?？梢酝ㄟ^(guò)引入虛擬節(jié)點(diǎn)來(lái)解決這個(gè)問(wèn)題。

不帶虛擬節(jié)點(diǎn)的一致性Hash算法

下面是不帶虛擬節(jié)點(diǎn)的ConsistentWithoutVirtualNodeRedisCluster

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentWithoutVirtualNodeRedisCluster extends RedisCluster{
    private List<RedisNode> redisNodes;

    private SortedMap<Integer,RedisNode> hashNodeMap = new TreeMap<>();

    public ConsistentWithoutVirtualNodeRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);
        int hash = HashUtils.getHash(redisNode.getIp());
        hashNodeMap.put(hash,redisNode);
    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        SortedMap<Integer, RedisNode> subMap = hashNodeMap.tailMap(hash);
        int i = 0;
        if (subMap.size()==0){
            i = hashNodeMap.firstKey();
            return hashNodeMap.get(i);
        }else {
            i = subMap.firstKey();
            return subMap.get(i);
        }
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

如果要測(cè)試不帶虛擬節(jié)點(diǎn)的一直性Hash算法的命中率，將

RedisCluster redisCluster = new NormalRedisCluster();
替換成
RedisCluster redisCluster = new ConsistentWithoutVirtualNodeRedisCluster();

就可以進(jìn)行測(cè)試了

帶虛擬節(jié)點(diǎn)的一致性Hash算法

假設(shè)我們將一個(gè)真實(shí)節(jié)點(diǎn)映射成10個(gè)虛擬節(jié)點(diǎn)。例如真正節(jié)點(diǎn)的ip是192.168.7.1。那么對(duì)應(yīng)的十個(gè)虛擬ip分別是

真實(shí)：192.168.7.1
虛擬：
           192.168.7.1&&VN1
           192.168.7.1&&VN2
           192.168.7.1&&VN3
           192.168.7.1&&VN4
           192.168.7.1&&VN5
           192.168.7.1&&VN6
           192.168.7.1&&VN7
           192.168.7.1&&VN8
           192.168.7.1&&VN9
           192.168.7.1&&VN10

當(dāng)真正進(jìn)行數(shù)據(jù)存儲(chǔ)的時(shí)候，我們根據(jù)虛擬節(jié)點(diǎn)的ip信息， 取出真正的ip，然后進(jìn)行存儲(chǔ)。
算法如下：

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentWithVirtualNodeRedisCluster extends RedisCluster{
    private List<RedisNode> redisNodes;

    //定義每個(gè)真實(shí)節(jié)點(diǎn)對(duì)應(yīng)10個(gè)虛擬節(jié)點(diǎn)
    private Integer virtualCount = 10;

    private SortedMap<Integer,RedisNode> virtualHashNodeMap = new TreeMap<>();


    public ConsistentWithVirtualNodeRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);

        for (int i=0;i<10;i++){
            int hash = HashUtils.getHash(redisNode.getIp()+"&&VN"+(i+1));
            virtualHashNodeMap.put(hash,redisNode);
        }

    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        SortedMap<Integer, RedisNode> subMap = virtualHashNodeMap.tailMap(hash);
        int i = 0;
        if (subMap.size()==0){
            i = virtualHashNodeMap.firstKey();
            return virtualHashNodeMap.get(i);
        }else {
            i = subMap.firstKey();
            return subMap.get(i);
        }
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

如果要測(cè)試帶虛擬節(jié)點(diǎn)的一直性Hash算法的命中率，將

RedisCluster redisCluster = new NormalRedisCluster();
替換成
RedisCluster redisCluster = new ConsistentWithVirtualNodeRedisCluster();

就可以進(jìn)行測(cè)試了
從測(cè)試結(jié)果中可以看到，無(wú)論是新增節(jié)點(diǎn)還是刪除節(jié)點(diǎn)，帶虛擬節(jié)點(diǎn)的一致性Hash算法的命中率都大大的提高了。

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

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

  • 余數(shù)Hash 最簡(jiǎn)單、常用的Hash算法。hash(i) = i mod n缺點(diǎn)：伸縮性差，使用余數(shù)Hash的路由...
    萌媽碼碼閱讀 238評(píng)論 0贊 0
  • 01.引入 在業(yè)務(wù)開發(fā)中，我們常把數(shù)據(jù)持久化到數(shù)據(jù)庫(kù)中。如果需要讀取這些數(shù)據(jù)，除了直接從數(shù)據(jù)庫(kù)中讀取外，為了減輕數(shù)...
    Java技術(shù)范閱讀 674評(píng)論 0贊 7
  • consistent hashing算法早在1997年就在論文Consistent hashing and...
    北風(fēng)第一支閱讀 884評(píng)論 0贊 5
  • 轉(zhuǎn)載請(qǐng)說(shuō)明出處：http://blog.csdn.net/cywosp/article/details/23397...
    碼農(nóng)也越野閱讀 505評(píng)論 0贊 1
  • 10個(gè)你必須掌握的未來(lái)生存法則 將來(lái)為上，過(guò)往次之 學(xué)習(xí)為上，經(jīng)歷次之 付出為上，回報(bào)次之 表現(xiàn)為上，贊譽(yù)次之 感...
    tuanzifighting閱讀 212評(píng)論 0贊 0

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