动手实现一致性 hash 算法

 关注
发布于: 2020 年 07 月 07 日
在分布式缓存场景中，我们在实现缓存集群线性伸缩的同时，还要保证失效或需要搬挪的key尽可能的少，而一致性hash算法正是解决该问题的很好方案。
﻿
一致性hash算法网上的资料很多，本文着重于实例讲解。问题如下：
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
类设计及简介ConsistentHashingWithVirtualNode
通过ConcurrentSkipListMap来模拟环，保存所有虚拟节点的hash值（及实际节点映射）；
通过virtualNode来调整一个实际节点映射的虚拟节点数；
通过IHash接口隔离不同的hash值计算；
IHash
提供了两个实现：HashImpl01和HashImpl02
﻿
具体实现如下：
﻿
package com.example.consistenthashing.demo;
﻿
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
﻿
/**
 * @author linyurong
 * @date 2020/7/3 9:57
 */
public class ConsistentHashingWithVirtualNode {
    private ConcurrentSkipListMap<Integer, String> circle;
    private IHash hashHelper;
    private int virtualNode;
﻿
    private static final int DEFAULT_VIRTUAL_NODE = 150;
    private static final String SPILT_FOR_VIRTUAL = "&&VN";
﻿
    public ConsistentHashingWithVirtualNode(String configs, int virtualNode, IHash hashHelper) {
        this.circle = new ConcurrentSkipListMap();
        this.virtualNode = virtualNode;
        this.hashHelper = hashHelper == null ? new HashImpl01() : hashHelper;
        setVirtualNodeForRealNode(configs);
    }
﻿
    public ConsistentHashingWithVirtualNode(String configs) {
        this(configs, DEFAULT_VIRTUAL_NODE, null);
    }
﻿
    /**
     * 分配节点
     * @param key
     * @return
     */
    public String getServer(String key) {
        int hash = hashHelper.getHash(key);
        ConcurrentNavigableMap<Integer, String> subMap = circle.tailMap(hash);
        String value = subMap.isEmpty() ? circle.firstEntry().getValue() : subMap.firstEntry().getValue();
        String server = value.substring(0, value.indexOf(SPILT_FOR_VIRTUAL));
        return server;
    }
﻿
		/**
     * 获取实际节点映射的虚拟节点数
     * @return
     */
    public int getVirtualNode() {
        return this.virtualNode;
    }
﻿
    /**
     * 获取IHash实现名称
     * @param key
     * @return
     */
    public String getHashHelper() {
        return this.hashHelper.getClass().getSimpleName();
    }
﻿
    /**
     * 构建真实节点和虚拟节点的映射关系，保存在circle成员变量中
     * @param configs
     * @return
     */
    private void setVirtualNodeForRealNode(String configs) {
        String[] nodes = configs.split(",");
        for (String node : nodes) {
            for (int i = 0; i < virtualNode; i++) {
                String virtualNodeName = node + SPILT_FOR_VIRTUAL + i;
                int hash = hashHelper.getHash(virtualNodeName);
                this.circle.put(hash, virtualNodeName);
            }
        }
    }
}
﻿
﻿
package com.example.consistenthashing.demo;
﻿
public interface IHash {
﻿
    int getHash(String key);
}
﻿
﻿
package com.example.consistenthashing.demo;
﻿
import org.apache.commons.codec.digest.Md5Crypt;
﻿
public class HashImpl01 implements IHash {
﻿
    @Override
    public int getHash(String key) {
        String crypt = Md5Crypt.md5Crypt(key.getBytes());
        return Math.abs(crypt.hashCode());
    }
}
﻿
﻿
package com.example.consistenthashing.demo;
﻿
public class HashImpl02 implements IHash {
﻿
    @Override
    public int getHash(String key) {
        final int p = 16777619;
        Long hash = 2166136261L;
        for(int ind = 0,num = key.length();ind<num;ind++){
            hash = (hash^key.charAt(ind))*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.intValue();
    }
}
﻿
﻿
测试类：
package com.example.consistenthashing.demo;
﻿
import java.util.HashMap;
import java.util.Map;
import java.util.UUID;
﻿
public class ConsistentHashingTest {
﻿
    //标准方差
    public static double getStd(Map<String, Integer> map) {
        double sum = 0;
        int cnt = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            cnt++;
        }
        double average = sum / cnt;
        int total = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            total += (entry.getValue() - average) * (entry.getValue() - average);
        }
        double standardDeviation = Math.sqrt(total / cnt);
        return standardDeviation;
    }
﻿
    /**
     * 测试方法
     * @param consistentHashing
     * @param configs
     */
    public static void testConsistentHashing(ConsistentHashingWithVirtualNode consistentHashing, String configs) {
        Map<String, Integer> calcMap = new HashMap<>(4);
        String[] servers = configs.split(",");
        for (int i = 0; i < servers.length; i++) {
            calcMap.put(servers[i], 0);
        }
        int size = 1000000;
        for (int i = 0; i < size; i++) {
            String key = UUID.randomUUID().toString();
            String server = consistentHashing.getServer(key);
            calcMap.put(server, calcMap.get(server) + 1);
        }
        System.out.println(calcMap);
        System.out.println(consistentHashing.getHashHelper() + "[KV size: " + size + ", virtual size : "
                + consistentHashing.getVirtualNode() + ", standardDeviation: " + getStd(calcMap) + "]");
    }
﻿
    public static void main(String[] args) {
        String configs = "192.168.0.1,192.168.0.2,192.168.0.3,192.168.0.4,192.168.0.5,192.168.0.6,192.168.0.7,192.168.0.8,192.168.0.9,192.168.0.10";
﻿
        System.out.println("====================================");
        ConsistentHashingWithVirtualNode consistentHashing2 = new ConsistentHashingWithVirtualNode(configs, 100, null);
        testConsistentHashing(consistentHashing2, configs);
        System.out.println("====================================");
﻿
        ConsistentHashingWithVirtualNode consistentHashing = new ConsistentHashingWithVirtualNode(configs, 150, null);
        testConsistentHashing(consistentHashing, configs);
        System.out.println("====================================");
﻿
        ConsistentHashingWithVirtualNode consistentHashing3 = new ConsistentHashingWithVirtualNode(configs, 200, null);
        testConsistentHashing(consistentHashing3, configs);
        System.out.println("************************************");
﻿
        ConsistentHashingWithVirtualNode consistentHashing4 = new ConsistentHashingWithVirtualNode(configs, 100, new HashImpl02());
        testConsistentHashing(consistentHashing4, configs);
        System.out.println("====================================");
﻿
        ConsistentHashingWithVirtualNode consistentHashing5 = new ConsistentHashingWithVirtualNode(configs, 150, new HashImpl02());
        testConsistentHashing(consistentHashing5, configs);
        System.out.println("====================================");
﻿
        ConsistentHashingWithVirtualNode consistentHashing6 = new ConsistentHashingWithVirtualNode(configs, 200, new HashImpl02());
        testConsistentHashing(consistentHashing6, configs);
        System.out.println("====================================");
    }
}
﻿
﻿
测试结果：
/Library/Java/JavaVirtualMachines/jdk-13.0.2.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=50937:/Applications/IntelliJ IDEA.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Users/lyr/workspace/consistent-hashing/target/classes:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-starter/2.3.1.RELEASE/spring-boot-starter-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot/2.3.1.RELEASE/spring-boot-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-context/5.2.7.RELEASE/spring-context-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-aop/5.2.7.RELEASE/spring-aop-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-beans/5.2.7.RELEASE/spring-beans-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-expression/5.2.7.RELEASE/spring-expression-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-autoconfigure/2.3.1.RELEASE/spring-boot-autoconfigure-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-starter-logging/2.3.1.RELEASE/spring-boot-starter-logging-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/ch/qos/logback/logback-classic/1.2.3/logback-classic-1.2.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/ch/qos/logback/logback-core/1.2.3/logback-core-1.2.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/apache/logging/log4j/log4j-to-slf4j/2.13.3/log4j-to-slf4j-2.13.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/apache/logging/log4j/log4j-api/2.13.3/log4j-api-2.13.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/slf4j/jul-to-slf4j/1.7.30/jul-to-slf4j-1.7.30.jar:/Users/lyr/app/apache-maven-3.6.3/repository/jakarta/annotation/jakarta.annotation-api/1.3.5/jakarta.annotation-api-1.3.5.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-core/5.2.7.RELEASE/spring-core-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-jcl/5.2.7.RELEASE/spring-jcl-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/yaml/snakeyaml/1.26/snakeyaml-1.26.jar:/Users/lyr/app/apache-maven-3.6.3/repository/commons-codec/commons-codec/1.14/commons-codec-1.14.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/slf4j/slf4j-api/1.7.30/slf4j-api-1.7.30.jar com.example.consistenthashing.demo.ConsistentHashingTest
====================================
{192.168.0.2=101551, 192.168.0.1=120475, 192.168.0.4=105641, 192.168.0.3=97290, 192.168.0.10=87970, 192.168.0.9=103506, 192.168.0.6=84701, 192.168.0.5=106181, 192.168.0.8=93261, 192.168.0.7=99424}
HashImpl01[KV size: 1000000, virtual size : 100, standardDeviation: 9673.774857830835]
====================================
{192.168.0.2=97546, 192.168.0.1=107032, 192.168.0.4=96250, 192.168.0.3=98791, 192.168.0.10=108375, 192.168.0.9=99844, 192.168.0.6=102380, 192.168.0.5=102917, 192.168.0.8=92548, 192.168.0.7=94317}
HashImpl01[KV size: 1000000, virtual size : 150, standardDeviation: 4931.149561714794]
====================================
{192.168.0.2=100513, 192.168.0.1=107244, 192.168.0.4=104366, 192.168.0.3=109506, 192.168.0.10=86365, 192.168.0.9=109111, 192.168.0.6=100560, 192.168.0.5=97395, 192.168.0.8=90667, 192.168.0.7=94273}
HashImpl01[KV size: 1000000, virtual size : 200, standardDeviation: 7470.55071597804]
************************************
{192.168.0.2=99612, 192.168.0.1=86849, 192.168.0.4=108020, 192.168.0.3=85367, 192.168.0.10=96784, 192.168.0.9=108807, 192.168.0.6=101018, 192.168.0.5=107816, 192.168.0.8=94048, 192.168.0.7=111679}
HashImpl02[KV size: 1000000, virtual size : 100, standardDeviation: 8794.3269213738]
====================================
{192.168.0.2=105941, 192.168.0.1=102442, 192.168.0.4=107121, 192.168.0.3=90559, 192.168.0.10=86803, 192.168.0.9=105603, 192.168.0.6=95949, 192.168.0.5=109358, 192.168.0.8=95001, 192.168.0.7=101223}
HashImpl02[KV size: 1000000, virtual size : 150, standardDeviation: 7191.12564206745]
====================================
{192.168.0.2=106971, 192.168.0.1=112452, 192.168.0.4=104434, 192.168.0.3=88770, 192.168.0.10=85037, 192.168.0.9=92755, 192.168.0.6=106592, 192.168.0.5=102617, 192.168.0.8=95305, 192.168.0.7=105067}
HashImpl02[KV size: 1000000, virtual size : 200, standardDeviation: 8507.775619984344]
====================================
﻿
Process finished with exit code 0
﻿
﻿
总结从测试结果来看，影响一致性hash算法的分配均衡因素有：
﻿
真实节点映射的虚拟节点数；
hash值计算逻辑（该因素还会影响执行性能）；
发布于: 2020 年 07 月 07 日阅读数: 47
原文链接:【http://xie.infoq.cn/article/3ebf184613cdac82997135130】。
林昱榕

 关注
开心生活，努力工作。 2018.02.13 加入
还未添加个人简介
发布
暂无评论