第五周:作业一

发布于: 2020 年 07 月 08 日
第五周:作业一

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

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

  1. 带虚拟节点

package com.js.framework.util;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
/**
* @author lihaiming
* @version 1.0
* @date 2020/7/6 11:33
*/
public class ConsistentHashVNodeAlgo {
private TreeMap<Long, String> virtualNodes = new TreeMap<>();
private LinkedList<String> nodes;
//每个真实节点对应的虚拟节点数
private final int replicCnt;
public ConsistentHashVNodeAlgo(LinkedList<String> nodes, int replicCnt){
this.nodes = nodes;
this.replicCnt = replicCnt;
initalization();
}
/**
* 初始化哈希环
* 循环计算每个node名称的哈希值,将其放入treeMap
*/
private void initalization(){
for (String nodeName: nodes) {
for (int i = 0; i < replicCnt/4; i++) {
String virtualNodeName = getNodeNameByIndex(nodeName, i);
for (int j = 0; j < 4; j++) {
virtualNodes.put(hash(virtualNodeName, j), nodeName);
}
}
}
}
private String getNodeNameByIndex(String nodeName, int index){
return new StringBuffer(nodeName)
.append("##")
.append(index)
.toString();
}
/**
* 根据资源key选择返回相应的节点名称
* @param key
* @return 节点名称
*/
public String selectNode(String key){
Long hashOfKey = hash(key, 0);
if (! virtualNodes.containsKey(hashOfKey)) {
Map.Entry<Long, String> entry = virtualNodes.ceilingEntry(hashOfKey);
if (entry != null)
return entry.getValue();
else
return nodes.getFirst();
}else
return virtualNodes.get(hashOfKey);
}
private Long hash(String nodeName, int number) {
byte[] digest = md5(nodeName);
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
/**
* md5加密
*
* @param str
* @return
*/
public byte[] md5(String str) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.reset();
md.update(str.getBytes("UTF-8"));
return md.digest();
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
return null;
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
return null;
}
}
public void addNode(String node){
nodes.add(node);
String virtualNodeName = getNodeNameByIndex(node, 0);
for (int i = 0; i < replicCnt/4; i++) {
for (int j = 0; j < 4; j++) {
virtualNodes.put(hash(virtualNodeName, j), node);
}
}
}
public void removeNode(String node){
nodes.remove(node);
String virtualNodeName = getNodeNameByIndex(node, 0);
for (int i = 0; i < replicCnt/4; i++) {
for (int j = 0; j < 4; j++) {
virtualNodes.remove(hash(virtualNodeName, j), node);
}
}
}
private void printTreeNode(){
if (virtualNodes != null && ! virtualNodes.isEmpty()){
virtualNodes.forEach((hashKey, node) ->
System.out.println(
new StringBuffer(node)
.append(" ==> ")
.append(hashKey)
)
);
}else
System.out.println("Hash Cycle is Empty");
}
/**
* 找到离该key的hash值最新的一个节点
* 找不到取第一个节点
*
* @param key
* @return
*/
private String findNodeByKey(String key) {
Long keyHash = hash(key,0);
SortedMap<Long, String> subMap = virtualNodes.tailMap(keyHash);
return subMap.isEmpty()
? virtualNodes.get(virtualNodes.firstKey())
: subMap.get(subMap.firstKey());
}
/**
* 计算key在节点上的分布和标准差
*
* @param keyValus
*/
private void compute(Map<String, Object> keyValus) {
//每个节点分配的key个数
Map<String, Integer> result = new HashMap<>();
for (String key : keyValus.keySet()) {
String nodeName = findNodeByKey(key);
if (result.get(nodeName) == null) {
result.put(nodeName, 1);
} else {
Integer value = result.get(nodeName);
result.put(nodeName, value + 1);
}
}
System.out.println(result);
System.out.println("标准差:" + stdDev(result, keyValus.size()));
}
/**
* 标准差计算
*
* @param map
* @param totalNums
* @return
*/
private double stdDev(Map<String, Integer> map, long totalNums) {
int n = map.size();
long avgNums = totalNums / map.size();
double sum = 0;
for (String key : map.keySet()) {
int value = map.get(key);
sum += (value - avgNums) * (value - avgNums);
}
return Math.sqrt(sum / n);
}
public static void main(String[] args){
LinkedList<String> nodes = new LinkedList<>();
nodes.add("192.168.0.1:8080");
nodes.add("192.168.0.2:8080");
nodes.add("192.168.0.3:8080");
nodes.add("192.168.0.4:8080");
nodes.add("192.168.0.5:8080");
nodes.add("192.168.0.6:8080");
nodes.add("192.168.0.7:8080");
nodes.add("192.168.0.8:8080");
nodes.add("192.168.0.9:8080");
nodes.add("192.168.0.10:8080");
ConsistentHashVNodeAlgo consistentHash = new ConsistentHashVNodeAlgo(nodes, 160);
//需要1000000个key
Map<String, Object> keyValus = new HashMap<>();
for (int i = 1; i <= 1000000; i++) {
keyValus.put("key" + i, "value" + i);
}
//输出缓存key在节点上的分布及标准差
consistentHash.compute(keyValus);
//标准差:6435.031779253309
}
}

  1. 无虚拟节点哈希

public class ConsistentHashAlgo {
private TreeMap<Long, String> realNodes = new TreeMap<>();
private String[] nodes;
public ConsistentHashAlgo(String[] nodes){
this.nodes = Arrays.copyOf(nodes, nodes.length);
initalization();
}
/**
* 初始化哈希环
* 循环计算每个node名称的哈希值,将其放入treeMap
*/
private void initalization(){
for (String nodeName: nodes) {
realNodes.put(hash(nodeName, 0), nodeName);
}
}
/**
* 根据资源key选择返回相应的节点名称
* @param key
* @return 节点名称
*/
public String selectNode(String key){
Long hashOfKey = hash(key, 0);
if (! realNodes.containsKey(hashOfKey)) { //ceilingEntry()的作用是得到比hashOfKey大的第一个Entry
Map.Entry<Long, String> entry = realNodes.ceilingEntry(hashOfKey);
if (entry != null)
return entry.getValue();
else
return nodes[0];
}else
return realNodes.get(hashOfKey);
}
private Long hash(String nodeName, int number) {
byte[] digest = md5(nodeName);
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
/**
* md5加密
*
* @param str
* @return
*/
public byte[] md5(String str) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.reset();
md.update(str.getBytes("UTF-8"));
return md.digest();
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
return null;
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
return null;
}
}
private void printTreeNode(){
if (realNodes != null && ! realNodes.isEmpty()){
realNodes.forEach((hashKey, node) ->
System.out.println(
new StringBuffer(node)
.append(" ==> ")
.append(hashKey)
)
);
}else
System.out.println("Hash Cycle is Empty");
}
}
//标准差:53515.530179565634

  1. 余数哈希

public class HashAlgo {
private int keyNumber;
private int oldNodesNumber;
private int newNodesNumber;
public HashAlgo(int keyNumber, int oldNodesNumber, int newNodesNumber) {
this.keyNumber = keyNumber;
this.oldNodesNumber = oldNodesNumber;
this.newNodesNumber = newNodesNumber;
}
public int hash(int keyNumber,int nodesNumber){
return keyNumber%nodesNumber;
}
}

用户头像

carol

关注

还未添加个人签名 2018.04.13 加入

还未添加个人简介

评论

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