写点什么

一致性 Hash 实现

用户头像
olderwei
关注
发布于: 2020 年 07 月 08 日

本文主要讨论一致性Hash的 Java 实现,使用了 Java 的 TreeMap 来实现,采用了 CRC32 和 FNV1_32 两种散列算法来算 Hash 值,也加入了虚拟节点的避免数据倾斜。

public interface HashAlgorithm {    public long hash(String originString);}
public class CRC32HashAlgorithm implements HashAlgorithm { public long hash(String originString) { CRC32 crc = new CRC32(); crc.update(originString.getBytes()); return crc.getValue(); }}
public class FNV132HashAlgorithm implements HashAlgorithm { public long hash(String originString) { final int p = 16777619; long hash = 2166136261L; for (int i = 0; i < originString.length(); i++) hash = (hash ^ originString.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; }}
public class Node { private String value;
public Node(String value) { this.value = value; }
public String getValue() { return value; }}
public class ConsistencyHash {
private SortedMap<Long, Node> virtualNodeMap = new TreeMap<Long, Node>();
private int virtualNodeNum;
private HashAlgorithm hashAlgorithm;
public ConsistencyHash(int virtualNodeNum, HashAlgorithm hashAlgorithm) { this.virtualNodeNum = virtualNodeNum; this.hashAlgorithm = hashAlgorithm; }
/** * 将服务器节点加入一致性Hash环 * @param node */ public void addNode(Node node) { for (int i = 0; i < virtualNodeNum; i++) { long hashValue = hashAlgorithm.hash(node.getValue() + "-" + i); virtualNodeMap.put(hashValue, node); } }
/** * 计算key对应的服务器节点 * @param key * @return */ public Node getNode(String key) { long hashValue = hashAlgorithm.hash(key); SortedMap<Long, Node> map = virtualNodeMap.tailMap(hashValue); Long resultKey = 0L; //如果找不到,则说明在最后一个节点和第一个节点之间,则分配到第一个节点 if (map.size() == 0) { resultKey = virtualNodeMap.firstKey(); } else { resultKey = map.firstKey(); } return virtualNodeMap.get(resultKey); }}
复制代码

以上是一致性 Hash 的实现,下面我们来验证一下均衡性,10 个服务器节点

public class Client {    public static void main(String[] args) {        String[] servers = new String[]{                "192.168.0.1:8080",                "192.168.0.2:8080",                "192.168.0.3:8080",                "192.168.0.4:8080",                "192.168.0.5:8080",                "192.168.0.6:8080",                "192.168.0.7:8080",                "192.168.0.8:8080",                "192.168.0.9:8080",                "192.168.0.10:8080"        };        //--------FNV132HashAlgorithm------------//        ConsistencyHash consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(80, new FNV132HashAlgorithm());        System.out.println("FNV132HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(160, new FNV132HashAlgorithm()); System.out.println("FNV132HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(200, new FNV132HashAlgorithm()); System.out.println("FNV132HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(320, new FNV132HashAlgorithm()); System.out.println("FNV132HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm)));
//--------CRC32HashAlgorithm------------// ConsistencyHash consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(80, new CRC32HashAlgorithm()); System.out.println("CRC32HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(160, new CRC32HashAlgorithm()); System.out.println("CRC32HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(200, new CRC32HashAlgorithm()); System.out.println("CRC32HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(320, new CRC32HashAlgorithm()); System.out.println("CRC32HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm)));
}
private static List<Long> computeNodeAllocation(String[] servers, ConsistencyHash consistencyHash) { for (int i = 0; i < servers.length; i++) { consistencyHash.addNode(new Node(servers[i])); }
Map<String, Long> result = new HashMap<String, Long>(); for (int i = 0; i < 1000000; i++) { Random random = new Random(); String key = "test" + random.nextInt(10000); Node node = consistencyHash.getNode(key); if (result.get(node.getValue()) == null) { result.put(node.getValue(), 1L); } else { result.put(node.getValue(), result.get(node.getValue()) + 1L); } }
List<Long> resultNum = new ArrayList<Long>(); for (Map.Entry<String, Long> entry : result.entrySet()) { resultNum.add(entry.getValue()); } return resultNum; }
private static Double computeStandardDeviation(List<Long> resultNum) { long sum = 0; int length = resultNum.size(); for(int i = 0; i < resultNum.size(); i++){ sum += resultNum.get(i); //求出数组的总和 } double average = sum / length; //求出数组的平均数 long total = 0; for (int i = 0; i < length; i++) { total += (resultNum.get(i) - average) * (resultNum.get(i) - average); //求出方差,如果要计算方差的话这一步就可以了 } double standardDeviation = Math.sqrt(total / length); //求出标准差 return standardDeviation; }}
复制代码

测试结果如下,根据测试结果其实能看出,虚拟节点也并不是越多越好,100-200 之间就好,而且和 hash 算法也有很大的关系。

FNV132HashAlgorithm with 80 virtual node, standard deviation is 45717.53488542443FNV132HashAlgorithm with 160 virtual node, standard deviation is 23627.90045687513FNV132HashAlgorithm with 200 virtual node, standard deviation is 19698.36820652919FNV132HashAlgorithm with 320 virtual node, standard deviation is 21673.15865304363CRC32HashAlgorithm with 80 virtual node, standard deviation is 27903.421080577198CRC32HashAlgorithm with 160 virtual node, standard deviation is 13226.479879393459CRC32HashAlgorithm with 200 virtual node, standard deviation is 13922.735435251221CRC32HashAlgorithm with 320 virtual node, standard deviation is 18066.353644274765
复制代码


发布于: 2020 年 07 月 08 日阅读数: 61
用户头像

olderwei

关注

还未添加个人签名 2018.04.26 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash实现