Java 一致性 Hash 算法及测试标准差

 关注
发布于: 2020 年 10 月 25 日
概述哈希算法是将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。
﻿
可以将hash算法分为普通hash算法和一致性hash算法（大家不要纠结这个分类，只是想说一致性hash算法在分布式中用哪种思想补充普通hash算法）
﻿
普通的hash算法在分布式应用中的不足：
比如，在分布式的存储系统中，要将数据存储到具体的节点上，如果我们采用普通的hash算法进行路由，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
﻿
一致性hash算法提出了在动态变化的Cache环境中，哈希算法应该满足的均衡性，单调性，分散性和负载均衡
均衡性(Balance)哈希的结果尽可能分布到所有的缓冲中，使所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
单调性(Monotonicity)当缓冲区大小变化时，一致性哈希尽量保证已分配的内容不会被重新映射到新缓冲区。
分散性(Spread)好的hash算法应该尽量保证相同的内容始终在同一个缓冲中，降低相同内容的分散性。
如果相同的内容被存储到不同的缓冲，这样降低了存储的效率。
负载(Load)负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
﻿
注意：一致性hash算法，不是一定有虚拟节点，加上虚拟节点是为了保证均衡性，让所有的缓冲中的数据数尽量保持在一个水平线上。
﻿
节点代码
import java.util.concurrent.atomic.AtomicInteger;
public class Node {
    private String server;
    private AtomicInteger count = new AtomicInteger(0);
    public Node(String server) {
        this.server = server;
    }
    public void increase() {
        count.incrementAndGet();
    }
    public String getServerAndIncrease() {
        increase();
        return getServer();
    }
    public String getServer() {
        return server;
    }
    public Integer getCount() {
        return count.get();
    }
    @Override
    public String toString() {
        return "Node{" +
                "server='" + server + '\'' +
                ", count=" + count.get() +
                '}';
    }
}
虚拟节点代码﻿
public class VirtualNode {
    private Node realServer;
    private String virtualServer;
    private int hash;
    public VirtualNode(Node realServer, String virtualServer, int hash) {
        this.realServer = realServer;
        this.virtualServer = virtualServer;
        this.hash = hash;
    }
    public Node getRealServer() {
        return realServer;
    }
    public String getVirtualServer() {
        return virtualServer;
    }
    public int getHash() {
        return hash;
    }
}
一致性Hash算法代码
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashing {
    private List<Node> servers;
    private SortedMap<Integer, VirtualNode> mapping = new TreeMap<>();
    private int virtualNodeNum = 5;
    public ConsistentHashing(List<Node> servers) {
        this.servers = servers;
        init();
    }
    public ConsistentHashing(List<Node> servers, int virtualNodeNum) {
        this.servers = servers;
        this.virtualNodeNum = virtualNodeNum;
        init();
    }
    private void init() {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException();
        }
        for (Node server : servers) {
            for (int i = 0; i < virtualNodeNum; i++) {
                String virtualServer = server.getServer() + "@" + i;
                int hash = getHash(virtualServer);
                VirtualNode virtualNode = new VirtualNode(server, virtualServer, hash);
                mapping.put(hash, virtualNode);
            }
        }
    }
    public String getServer(String key) {
        int hash = getHash(key);
        SortedMap<Integer, VirtualNode> subMapping = mapping.tailMap(hash);
        SortedMap<Integer, VirtualNode> selectMapping = (subMapping == null || subMapping.isEmpty()) ? mapping : subMapping;
        VirtualNode virtualNode = selectMapping.get(selectMapping.firstKey());
        return virtualNode.getRealServer().getServerAndIncrease();
    }
    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;
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
}
测试代码
import java.util.ArrayList;
import java.util.List;
public class Client {
    public static void main(String[] args) {
        int serverNum = 10;
        int execTimes = 1000000;
        List<Node> servers = new ArrayList<>();
        for (int i = 1; i <= serverNum; i++) {
            Node node = new Node("127.0.0." + i);
            servers.add(node);
        }
        ConsistentHashing consistentHashing = new ConsistentHashing(servers);
        long startTime = System.currentTimeMillis();
        for (int n = 0; n < execTimes; n++) {
            String key = Math.random() + "";
            consistentHashing.getServer(key);
        }
        long endTime = System.currentTimeMillis();
        double std = 0;
        double avg = execTimes / serverNum;
        for (int i = 0; i < serverNum; i++) {
            Node node = servers.get(i);
            std = std + Math.abs(avg - (double) node.getCount()) * Math.abs(avg - (double) node.getCount());
        }
        std = std / serverNum;
        std = Math.sqrt(std);
        System.out.println(" 虚拟节点个数：" + serverNum + "  100万次查找算法程序运行时间： " + (endTime - startTime) + "ms" + " 标准差：" + std);
        for (Node server : servers) {
            System.out.println(server);
        }
    }
}
测试截图
﻿
发布于: 2020 年 10 月 25 日阅读数: 12
原文链接:【http://xie.infoq.cn/article/e382238048a5a2764665c77b8】。
A p7+

 关注
还未添加个人签名 2020.06.05 加入
还未添加个人简介
发布
暂无评论