第五周作业

关注
发布于: 2020 年 07 月 08 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
Main类
import org.apache.commons.lang3.RandomStringUtils;
public class Main {
    //虚拟节点数量
    static final int virtualNodeNum = 100;
    public static void main(String[] args) {
        //生成随机的KV数据集合,数据为长度为10位的随机字符串
        String[] testData = new String[1000000];
        for (int i = 0; i < testData.length; i++) {
            testData[i] = RandomStringUtils.randomAlphanumeric(10);
        }
        //生成hash环，环的大小为2的32次方.
        HashCircle hashCircle = new HashCircle(0x7fffffff - 3);
        HashNode[] hashNodes = hashCircle.getNode();
        //生成服务器节点
        ServerNode[] serverNode = new ServerNode[10];
        for (int i = 0; i < 10; i++) {
            serverNode[i] = new ServerNode(virtualNodeNum);
            serverNode[i].setVirtualNodeNum(virtualNodeNum);
            serverNode[i].setServerId(i);
            serverNode[i].setConunt(0);
            serverNode[i].setIpAddress("192.168.1." + i );
            serverNode[i].setPosition(serverNode[i].getIpAddress().hashCode() & Integer.MAX_VALUE);
            hashNodes[i] = new HashNode();
            hashNodes[i].setPosition(serverNode[i].getPosition());
            hashNodes[i].setFlag(true);
            hashNodes[i].setIdOfServer(serverNode[i].getServerId());
        }
        //生成虚拟节点
        for (int i = 0; i <10; i++) {
            serverNode[i].setVirtualNode(new ServerNode[virtualNodeNum]);
            ServerNode[] virtalNode = serverNode[i].getVirtualNode();
            for (int j = 0; j < virtualNodeNum; j++) {
                virtalNode[j] = new ServerNode(virtualNodeNum);
                virtalNode[j].setIpAddress(serverNode[i].getIpAddress() + "#" + j);
                virtalNode[j].setPosition(virtalNode[j].getIpAddress().hashCode() & Integer.MAX_VALUE);
                hashNodes[j] = new HashNode();
                hashNodes[j].setPosition(serverNode[i].getPosition());
                hashNodes[j].setFlag(true);
                hashNodes[j].setIdOfServer(serverNode[i].getServerId());
            }
        }
        //计算测试数据的hashcode，并找到和它最近的服务器节点的数量
        for (int i = 0; i < testData.length; i++) {
            int hash = testData.hashCode() & Integer.MAX_VALUE;
            while (!hashNodes[hash].isFlag() && hash < hashCircle.getSize()){
                hash ++;
            }
            int id = hashNodes[hash].getIdOfServer();
            serverNode[id].hit();
        }
        //输出每个服务器承载的数据量
        for (int i = 0; i < 10; i++) {
            System.out.println(serverNode[i].getConunt());
        }
    }
}
HashCircle类
public class HashCircle {
    private int size;
    private HashNode[] node;
    public int getSize() {
        return size;
    }
    public HashCircle(int size) {
        node = new HashNode[size];
    }
    public void setSize(int size) {
        this.size = size;
    }
    public HashNode[] getNode() {
        return node;
    }
    public void setNode(HashNode[] node) {
        this.node = node;
    }
}
HashNode类
public class HashNode {
    private int position;
    private int IdOfServer;
    private boolean flag;
﻿
    public boolean isFlag() {
        return flag;
    }
﻿
    public void setFlag(boolean flag) {
        this.flag = flag;
    }
﻿
    public int getPosition() {
        return position;
    }
﻿
    public void setPosition(int position) {
        this.position = position;
    }
﻿
    public int getIdOfServer() {
        return IdOfServer;
    }
﻿
    public void setIdOfServer(int idOfServer) {
        IdOfServer = idOfServer;
    }
}
﻿
ServerNode类
public class ServerNode {
    private int virtualNodeNum;
    private String ipAddress;
    private int position;
    private int conunt;
    private int serverId;
    private ServerNode[] virtualNode ;
    public ServerNode(int virtualNodeNum) {
        this.virtualNodeNum = virtualNodeNum;
        virtualNode = new ServerNode[virtualNodeNum];
    }
    public int getVirtualNodeNum() {
        return virtualNodeNum;
    }
    public void setVirtualNodeNum(int virtualNodeNum) {
        this.virtualNodeNum = virtualNodeNum;
    }
    public String getIpAddress() {
        return ipAddress;
    }
    public void setIpAddress(String ipAddress) {
        this.ipAddress = ipAddress;
    }
    public int getPosition() {
        return position;
    }
    public void setPosition(int position) {
        this.position = position;
    }
    public int getConunt() {
        return conunt;
    }
    public void setConunt(int conunt) {
        this.conunt = conunt;
    }
    public int getServerId() {
        return serverId;
    }
    public void setServerId(int serverId) {
        this.serverId = serverId;
    }
    public void setVirtualNode(ServerNode[] virtualNode) {
        this.virtualNode = virtualNode;
    }
    public ServerNode[] getVirtualNode() {
        return virtualNode;
    }
    public void hit(){
        this.conunt ++;
    }
}
我感觉自己的算法是正确的，但是在构造哈希环的时候，2的32次方的大小的环一直无法构建，提示溢出。这个还要进一步考虑优化。