写点什么

架构师训练营作业 -20200705

用户头像
caibird1984
关注
发布于: 2020 年 07 月 05 日

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



以下代码通过JAVA语言实现:



/**

* 分布式缓存实现

* @author xiaofy

*/

public class MyCache {



/**

* 保存每个虚拟节点与服务器名称的对应关系

*/

private TreeMap<Integer, String> nodes = new TreeMap<Integer, String>();

/**

* 保存每个服务器中保存的数据量

*/

private Map<String, Long> serverDataMap = new HashMap<String, Long>();

/**

* 模拟添加数据

* @param key 数据的键

*/

public void addData(String key) {

if(key == null || "".equals(key.trim())) {

return;

}

Integer nodeHash = selectNode(key);

String serverName = nodes.get(nodeHash);

if(serverName != null && !"".equals(serverName.trim())) {

addServerDataCount(serverName);

}

}

/**

* 服务器内的数据量加1

* @param serverName 服务器名称

*/

private void addServerDataCount(String serverName) {

long dataCount = 0;

if(serverDataMap.containsKey(serverName)) {

dataCount = serverDataMap.get(serverName);

}

dataCount++;

serverDataMap.put(serverName, dataCount);

}

/**

* 选择数据存储节点

* @param key 数据的键

* @return 选择的节点哈希值

*/

private Integer selectNode(String key) {

int keyHash = key.hashCode();

SortedMap<Integer, String> node = nodes.tailMap(keyHash, true);

if(!node.isEmpty()) {

return node.firstKey();

}

return nodes.firstKey();

}



/**

* 构造虚拟节点名称

* @param serverName 服务器名称

* @param nodeIndex 节点编号

* @return 虚拟节点名称

*/

private String buildNodeName(String serverName, int nodeIndex) {

return serverName + "_" + nodeIndex;

}

/**

* 计算数据存储数量的标准差

* @return 数据存储数量的标准差

*/

public double getStandDeviation() {

double sum = 0;

for(String key : serverDataMap.keySet()) {

sum += serverDataMap.get(key);

}

long total = 0;

double average = sum / serverDataMap.size();

for(String key : serverDataMap.keySet()) {

long count = serverDataMap.get(key);

total += (count-average)*(count-average);

}

double result = Math.sqrt(total/serverDataMap.size());

return result;

}

/**

* 构造函数

* @param serverList 服务器列表

* @param nodesPerServer 每台服务器的虚拟节点数

*/

public MyCache(List<String> serverList, int nodesPerServer) {

initNodes(serverList, nodesPerServer);

}

/**

* 初始化每个服务器的虚拟节点信息

* @param serverList 服务器列表

* @param nodesPerServer 每台服务器的虚拟节点数

*/

private void initNodes(List<String> serverList, int nodesPerServer) {

for(int i = 0; i < serverList.size(); i++) {

String serverName = serverList.get(i);

for(int j = 0; j < nodesPerServer; j++) {

String nodeName = buildNodeName(serverName, j);

nodes.put(nodeName.hashCode(), serverName);

}

}

}

}






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



以每台服务器划分100个虚拟节点,编写简单的测试程序,如下:



/**

* 测试程序

* @author xiaofy

*/

public class CacheSampleMain {

/**

* 每台服务器的虚拟节点数

*/

private static final int NODECOUNTPER_SERVER = 100;

/**

* 模拟添加到缓存的记录数

*/

private static final int DATA_COUNT = 1000000;



public static void main(String[] args) {

List<String> serverList = createServerList();

MyCache myCache = new MyCache(serverList, NODECOUNTPER_SERVER);

for(int i = 0; i < DATA_COUNT; i++) {

//模拟数据的KEY

String key = UUID.randomUUID().toString().replace("-", "");

myCache.addData(key);

}

double standardDeviation = myCache.getStandDeviation();

System.out.println("标准差为:" + standardDeviation);

}



/**

* 构造服务器列表

* @return 服务器IP列表

*/

private static List<String> createServerList() {

List<String> list = new ArrayList<String>();

for(int i = 1; i <= 10; i++) {

String serverName = "192.168.0." + i;

list.add(serverName);

}

return list;

}

}



测试结果,标准差为:



用户头像

caibird1984

关注

还未添加个人签名 2018.04.28 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营作业-20200705