架构师训练营第 1 期 -- 第五周作业

用户头像
发酵的死神
关注
发布于: 2020 年 10 月 25 日



  1. 用你熟悉的编程语言实现一致性 hash 算法。

  2. 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。



代码实现如图。main方法里包含了方差的计算。



import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class ConsistentHashMain {
public static void main(String[] args) throws Exception {
String[] servers = new String[]{"server1", "server2", "server3", "server4", "server5", "server6", "server7", "server8", "server9", "server10"};
ExecutorService threadPool = Executors.newFixedThreadPool(10);
final int maxVirtualNodes = 300;
final int visitTime = 1000000;
final int avgLoad = visitTime/servers.length;
for (int virtualNodes = 1; virtualNodes <= maxVirtualNodes; virtualNodes++) {
final int vNodes = virtualNodes;
threadPool.execute(() -> {
HashCircle circle = new HashCircle(vNodes, servers);
for (int i = 0; i < visitTime; i++) {
UUID uuid = UUID.randomUUID();
circle.visitCluster(uuid.toString());
}
int x = 0;
for (int i = 0; i < servers.length; i++) {
int a = circle.getVisitorLogMap().get(servers[i]).size() - avgLoad;
x += a * a;
}
int y = x / servers.length;
System.out.println(String.format("%d:%d", vNodes, y));
});
}
threadPool.awaitTermination(1, TimeUnit.HOURS);
}
}


class HashCircle {
/**
* 主环
*/
private String[] circle;
private int[] addressMapper;
/**
* 虚节点数量
*/
private int virtualNodeFactor;
/**
* 地址记录字典
*/
private Map<String, List<Integer>> nodeAddressMap = new HashMap<>();
private Map<String, List<String>> visitorLogMap = new HashMap<>();
HashCircle(int virtualNodeFactor, String[] nodes) {
this.virtualNodeFactor = virtualNodeFactor;
circle = new String[virtualNodeFactor * nodes.length];
addressMapper = new int[circle.length];
this.assignNodes(nodes);
}
private void assignNodes(String[] nodes) {
int interval = Integer.MAX_VALUE / nodes.length / this.virtualNodeFactor;
int currentAddress = 0;
int mapperIndex = 0;
for (int i = 0; i < this.virtualNodeFactor; i++) {
for (int j = 0; j < nodes.length; j++) {
currentAddress += interval;
currentAddress = convertNeg(currentAddress);
addressMapper[mapperIndex] = currentAddress;
circle[mapperIndex++] = nodes[j];
recordAddress(nodes[j], currentAddress);
}
}
}

private void recordAddress(String content, int currentAddress) {
List<Integer> addrList = nodeAddressMap.get(content);
if (addrList == null) {
addrList = new ArrayList<Integer>(this.virtualNodeFactor);
nodeAddressMap.put(content, addrList);
}
addrList.add(currentAddress);
}
/**
* 不同的用户过来,返回访问的服务器id
* @param visitorId
* @return
*/
public String visitCluster(String visitorId) {
int address = visitorId.hashCode();
String server = getNode(address);
List<String> userIdList = visitorLogMap.get(server);
if (userIdList == null) {
userIdList = new ArrayList<String>();
visitorLogMap.put(server, userIdList);
}
userIdList.add(visitorId);
return server;
}

public Map<String, List<Integer>> getNodeAddressMap() {
return nodeAddressMap;
}

public Map<String, List<String>> getVisitorLogMap() {
return visitorLogMap;
}
public String getNode(int hashCode) {
hashCode = convertNeg(hashCode);
for (int i = 0; i < addressMapper.length; i++) {
if (hashCode < addressMapper[i]) {
return circle[i];
}
}
return circle[0];
}

private int convertNeg(int hashCode) {
if (hashCode < 0) {
hashCode = hashCode & 0x7fffffff;
}
return hashCode;
}
}

跑了三次,绘出方差图 (x轴:虚节点数,y轴:方差)





感觉从图中并没有能看得出虚节点数量的多少对均衡性有多大的影响。有时间的时候,再仔细研究一番。



用户头像

发酵的死神

关注

还未添加个人签名 2019.03.19 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 1 期 -- 第五周作业