一致性 Hash 算法的实现及分析

 关注
发布于: 2020 年 10 月 25 日
﻿
1、一致性Hash算法
import java.util.*;
public class ConsistentHash<T> {
    /**
     *  每个服务器节点的虚拟节点的个数，默认150个
     */
    private int virtualNodeNum = 150;
    /**
     * 虚拟结点在Hash环上的位置
     */
    public TreeSet<Integer> hashRing = new TreeSet<>();
    /**
     * 虚拟结点和服务器结点的映射关系
     */
    public Map<Integer, T> virtualNodeMapping = new HashMap<>();
    /**
     * 实际的服务器结点
     */
    public List<T> nodes = new ArrayList<>();
    public ConsistentHash(int virtualNodeNum, List<T> nodes) {
        this.virtualNodeNum = virtualNodeNum;
        initVirtualNodes(nodes);
    }
    public int getVirtualNodeNum() {
        return virtualNodeNum;
    }
    private void initVirtualNodes(List<T> nodes) {
        for (int i = 0; i < nodes.size(); i++) {
            addNode(nodes.get(i));
        }
    }
    
    public void addNode(T node) {
        this.nodes.add(node);
        for (int i = 0; i < virtualNodeNum; i++) {
            Integer virtualNode = createVirtualNode(createVirtualNodeName(node.hashCode(), i));
            hashRing.add(virtualNode);
            virtualNodeMapping.put(virtualNode, node);
        }
    }
    private String createVirtualNodeName(int nodeHashCode, int virtualNodeIndex) {
        return "node" + nodeHashCode + "#" + virtualNodeIndex;
    }
    private Integer createVirtualNode(String virtualNodeName) {
        Random random = new Random();
        while (true) {
            String s = virtualNodeName + "#" + random.nextInt();
            Integer index = Math.abs(s.hashCode());
            if (!hashRing.contains(index)) {
                return index;
            }
        }
    }
    private Integer getVirtualNode(Integer parameterHash) {
        Integer virtualNode = hashRing.first();
        Iterator<Integer> iterator = hashRing.iterator();
        while (iterator.hasNext()) {
            Integer temp = iterator.next();
            if (temp > parameterHash) {
                virtualNode = temp;
                break;
            }
        }
        return virtualNode;
    }
    public T getNode(Integer parameterHashCode) {
        Integer virtualNode = getVirtualNode(parameterHashCode);
        return virtualNodeMapping.get(virtualNode);
    }
}
﻿
Server类用来对调用进行计数
import java.util.concurrent.atomic.AtomicInteger;
public class Server {
    private AtomicInteger count = new AtomicInteger(0);
    private String ip;
    public Server(String ip) {
        this.ip = ip;
    }
    public void service() {
        count.addAndGet(1);
    }
    public int getCount() {
        return count.get();
    }
    public String getIp() {
        return ip;
    }
}
﻿
构建10个服务器结点的服务
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class Service {
    private List<Server> servers = new ArrayList<>();
    private ConsistentHash<Server> consistentHash;
    public Service(int virtualNodeNum) {
        servers.add(new Server("192.168.0.1"));
        servers.add(new Server("192.168.0.2"));
        servers.add(new Server("192.168.0.3"));
        servers.add(new Server("192.168.0.4"));
        servers.add(new Server("192.168.0.5"));
        servers.add(new Server("192.168.0.6"));
        servers.add(new Server("192.168.0.7"));
        servers.add(new Server("192.168.0.8"));
        servers.add(new Server("192.168.0.9"));
        servers.add(new Server("192.168.0.10"));
        consistentHash = new ConsistentHash(virtualNodeNum, servers);
    }
    public void service(Integer i) {
        Server server = consistentHash.getNode(i);
        server.service();
    }
    public void printBalanceResult() {
        System.out.println("虚拟结点数为" + consistentHash.getVirtualNodeNum() + "时，标准差为" + standardDeviation());
         for (int i = 0; i < servers.size(); i++) {
            Server server = servers.get(i);
            System.out.println("服务器" + server.getIp() + "接收到的请求数为：" + server.getCount());
        }
    }
    private double standardDeviation() {
        Integer num = servers.size();
        BigDecimal sum = BigDecimal.ZERO;
        for (int i = 0; i < num; i++) {
            sum = sum.add(new BigDecimal(servers.get(i).getCount()));
        }
        BigDecimal avg = sum.divide(new BigDecimal(num), 2, BigDecimal.ROUND_DOWN);
        BigDecimal deviationVar = BigDecimal.ZERO;
        for (int i = 0; i < num; i++) {
            deviationVar = deviationVar.add((new BigDecimal(servers.get(i).getCount()).subtract(avg)).pow(2));
        }
        return Math.sqrt(deviationVar.divide(new BigDecimal(num), 2, BigDecimal.ROUND_DOWN).doubleValue());
    }
}
﻿
2、测试结果
import org.junit.Test;
import java.util.Random;
public class ConsistentHashTest {
    private void test(int virtualNodeNum) {
        Service service = new Service(virtualNodeNum);
        Random random = new Random(Integer.MAX_VALUE);
        for (int i = 0; i < 1000000; i++) {
            service.service(Math.abs(random.nextInt()));
        }
        service.printBalanceResult();
    }
    @Test
    public void test100VirtualNode() {
        test(100);
    }
    @Test
    public void test150VirtualNode() {
        test(150);
    }
    @Test
    public void test200VirtualNode() {
        test(200);
    }
  
}
150个虚拟结点的测试结果：
虚拟结点数为150时，标准差为5082.597229763539
服务器192.168.0.1接收到的请求数为：97285
服务器192.168.0.2接收到的请求数为：104577
服务器192.168.0.3接收到的请求数为：96278
服务器192.168.0.4接收到的请求数为：111228
服务器192.168.0.5接收到的请求数为：104670
服务器192.168.0.6接收到的请求数为：98761
服务器192.168.0.7接收到的请求数为：97731
服务器192.168.0.8接收到的请求数为：92970
服务器192.168.0.9接收到的请求数为：96511
服务器192.168.0.10接收到的请求数为：99989
100个虚拟结点的测试结果：
虚拟结点数为200时，标准差为9887.882725841766
服务器192.168.0.1接收到的请求数为：91733
服务器192.168.0.2接收到的请求数为：104090
服务器192.168.0.3接收到的请求数为：101407
服务器192.168.0.4接收到的请求数为：99101
服务器192.168.0.5接收到的请求数为：118211
服务器192.168.0.6接收到的请求数为：101417
服务器192.168.0.7接收到的请求数为：110598
服务器192.168.0.8接收到的请求数为：90961
服务器192.168.0.9接收到的请求数为：81025
服务器192.168.0.10接收到的请求数为：101457
200个虚拟结点的测试结果：
虚拟结点数为100时，标准差为11033.066890035609
服务器192.168.0.1接收到的请求数为：121222
服务器192.168.0.2接收到的请求数为：104118
服务器192.168.0.3接收到的请求数为：91737
服务器192.168.0.4接收到的请求数为：89922
服务器192.168.0.5接收到的请求数为：87783
服务器192.168.0.6接收到的请求数为：98833
服务器192.168.0.7接收到的请求数为：118913
服务器192.168.0.8接收到的请求数为：93781
服务器192.168.0.9接收到的请求数为：99416
服务器192.168.0.10接收到的请求数为：94275
﻿
将服务器数量修改为3台，测试结果：
虚拟结点数为150时，标准差为15951.119862881102
服务器192.168.0.1接收到的请求数为：355792
服务器192.168.0.2接收到的请求数为：320270
服务器192.168.0.3接收到的请求数为：323938
虚拟结点数为200时，标准差为8785.087452609678
服务器192.168.0.1接收到的请求数为：322892
服务器192.168.0.2接收到的请求数为：332723
服务器192.168.0.3接收到的请求数为：344385
虚拟结点数为100时，标准差为24151.648975173517
服务器192.168.0.1接收到的请求数为：367477
服务器192.168.0.2接收到的请求数为：315480
服务器192.168.0.3接收到的请求数为：317043
﻿
发布于: 2020 年 10 月 25 日阅读数: 10
天天向上

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