第五周作业

发布于: 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次方的大小的环一直无法构建,提示溢出。这个还要进一步考虑优化。

用户头像

qqq

关注

还未添加个人签名 2017.12.08 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业