第五周作业
发布于: 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次方的大小的环一直无法构建,提示溢出。这个还要进一步考虑优化。
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 45
![用户头像](http://static001.geekbang.org/account/avatar/00/0f/b7/22/84f92c04.jpg?x-oss-process=image/resize,w_200,h_200)
qqq
关注
还未添加个人签名 2017.12.08 加入
还未添加个人简介
评论 (1 条评论)