第五周作业 (作业一)

用户头像
Geek_83908e
关注
发布于: 2020 年 10 月 25 日



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

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



/**
/**
* @author zhuhuiming
* @date 2020/10/25 3:51 下午
* @description
* 整个组成部分:
* 1、服务器ip集
* 2、单个服务器ip对应的虚拟节点数
* 3、虚拟节点和服务器ip映射关系集
*/
public class ConsistencyOperator {
//单个服务器ip对应的虚拟节点数
private static int virtual_num = 10;
//虚拟节点和服务器ip映射关系集(其中key为hash值,value为对应的服务器ip)
private final static TreeMap<Long,String> virtual_server_map = new TreeMap<>();
private Set<String> server_ip = null;
// 32位的 Fowler-Noll-Vo 哈希算法
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
private static Long FNVHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for (int idx = 0, num = key.length(); idx < num; ++idx) {
hash = (hash ^ key.charAt(idx)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
//一个服务器ip对应虚拟节点个数
public ConsistencyOperator(int virtual_num,Set<String> server_ip){
if(virtual_num > 0)
this.virtual_num = virtual_num;
this.server_ip = server_ip;
initVirtualServerNodes();
}
//生成虚拟节点
private boolean initVirtualServerNodes(){
Long hashcode = null;
int size = server_ip.size();
for(String ip:server_ip){
for(int i = 0; i < virtual_num; i++){
hashcode = FNVHash(ip+"#"+i);
virtual_server_map.put(hashcode,ip);
}
}
return true;
}
//加入服务节点
public boolean addServerNode(String serverip){
if(StringUtils.isBlank(serverip)) return false;
server_ip.add(serverip);
Long hashcode = null;
for(int i = 0; i < virtual_num; i++){
hashcode = FNVHash(serverip+"#"+i);
virtual_server_map.put(hashcode,serverip);
}
return true;
}
//删除服务节点
public boolean removeServerNode(String serverip){
if(StringUtils.isBlank(serverip)) return false;
server_ip.remove(serverip);
Long hashcode = null;
for(int i = 0; i < virtual_num; i++){
hashcode = FNVHash(serverip+"#"+i);
virtual_server_map.remove(hashcode);
}
return true;
}
// 查找对象映射的节点
public String getObjectNode(String object) {
long hash = FNVHash(object);
SortedMap<Long, String> tailMap = virtual_server_map.tailMap(hash); // 所有大于 hash 的节点
Long key = tailMap.isEmpty() ? virtual_server_map.firstKey() : tailMap.firstKey();
return virtual_server_map.get(key);
}
// 统计对象与节点的映射关系
public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
// 统计
Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
for (int object = objectMin; object <= objectMax; ++object) {
String nodeIp = getObjectNode(Integer.toString(object));
Integer count = objectNodeMap.get(nodeIp);
objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
}
// 打印
double totalCount = objectMax - objectMin + 1;
System.out.println("======== " + label + " ========");
for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
long percent = (int) (100 * entry.getValue() / totalCount);
System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
}
}
public static void main(String[] args) {
Set<String> server_ip = new TreeSet<String>();
//服务器ip地址集
for(int i = 0; i < 10; i++){
//写入10个server的ip
server_ip.add("192.168.3."+i);
}
ConsistencyOperator ch = new ConsistencyOperator(100,server_ip);
// 初始情况
ch.dumpObjectNodeMap("初始情况", 0, 1000000);
}
}

以上代码参考过https://blog.csdn.net/kefengwang/article/details/81628977

发布于: 2020 年 10 月 25 日 阅读数: 8
用户头像

Geek_83908e

关注

还未添加个人签名 2019.04.28 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业(作业一)