第五周作业 - 命题作业

发布于: 2020 年 07 月 08 日

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

1).一致性 hash 算法,未使用虚拟节点

ConsistencyHash.java

package com.imolly.hash;
import java.util.*;
/**
* 一致性 hash 算法,未使用虚拟节点
*/
public class ConsistencyHash {
private SortedMap<Integer,String> nodeSortedMap;
private List<String> serverNodes;
public void setServerNodes(List<String> serverNodes){
this.serverNodes = serverNodes;
nodeSortedMap = new TreeMap<Integer, String>();
for (String nodeName : serverNodes){
nodeSortedMap.put(getHashCode(nodeName),nodeName);
}
}
public String getServerNode(String key){
int hashCode = getHashCode(key);
SortedMap<Integer,String> sortedMap = nodeSortedMap.tailMap(hashCode);
if(sortedMap.isEmpty()){
Integer i = nodeSortedMap.firstKey();
return nodeSortedMap.get(i);
}else{
Integer i = sortedMap.firstKey();
return sortedMap.get(i);
}
}
//FNV1_32_HASH
public int getHashCode(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * 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;
}
}

2).一致性 hash 算法,使用虚拟节点

ConsistencyHashVirtualNode.java

package com.imolly.hash;
import java.util.*;
/**
* 一致性 hash 算法,使用虚拟节点
*/
public class ConsistencyHashVirtualNode {
private List<String> realServerNodes; //真实节点
private int virtualNodeCount; //虚拟节点数
private SortedMap<Integer,String> virtualNodeSortedMap;
public ConsistencyHashVirtualNode(int virtualNodeCount){
this.virtualNodeCount = virtualNodeCount;
}
public void setRealServerNodes(List<String> realServerNodes){
this.realServerNodes = realServerNodes;
virtualNodeSortedMap = new TreeMap<Integer, String>();
String virtualNodeName = "";
for (String realNodeName : realServerNodes){
for (int i = 0; i < virtualNodeCount; i++){
virtualNodeName = realNodeName+"#"+(i+1);
virtualNodeSortedMap.put(getHashCode(virtualNodeName),virtualNodeName);
}
}
}
public String getServerNode(String key){
int hashCode = getHashCode(key);
SortedMap<Integer,String> sortedMap = virtualNodeSortedMap.tailMap(hashCode);
if(sortedMap.isEmpty()){
Integer i = virtualNodeSortedMap.firstKey();
return virtualNodeSortedMap.get(i);
}else{
Integer i = sortedMap.firstKey();
return sortedMap.get(i);
}
}
//FNV1_32_HASH
public int getHashCode(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * 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;
}
}

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

1).一致性 hash 算法,未使用虚拟节点

ConsistencyHashTest.java

package com.imolly.hash;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
/**
* 一致性 hash 算法,未使用虚拟节点测试类
*/
public class ConsistencyHashTest {
private List<String> serverNodes;
private List<String > keys;
@Before
public void before(){
int nodeCount = 10; //节点数
serverNodes = new LinkedList<String>(); //节点集合
String baseIp = "192.168.0.10";
String basePort = "9000";
for (int i = 0; i < nodeCount; i++){
serverNodes.add(baseIp + i + ":" + basePort);
}
int kvObjectCount = 1000000; //KV对象数
keys = new ArrayList<String>(); //KV对象集合
for (int i = 0; i < kvObjectCount; i++){
keys.add("键"+(i+1));
}
}
@Test
public void testHash(){
ConsistencyHash consistencyHash = new ConsistencyHash();
consistencyHash.setServerNodes(serverNodes);
SortedMap<String,Integer> sortedMap = new TreeMap<String, Integer>();
String nodeName = "";
for (String key : keys){
nodeName = consistencyHash.getServerNode(key);
if(sortedMap.containsKey(nodeName)){
sortedMap.put(nodeName,sortedMap.get(nodeName)+1);
}else{
sortedMap.put(nodeName,1);
}
System.out.println(key + " 的 hashCode : " + consistencyHash.getHashCode(key) + " , 被路由到节点: " + nodeName + " 中.");
}
System.out.println("****** 100万 KV数据在 10个服务器节点上的分布数量情况(未使用虚拟节点) ******");
for (String key : sortedMap.keySet()){
System.out.println(key + " 节点有:" + sortedMap.get(key) + " 个KV对象");
}
System.out.println("标准差:" + calcStandardDeviation(sortedMap));
}
//计算标准差
private double calcStandardDeviation(SortedMap<String,Integer> sortedMap){
int totalCount = sortedMap.size();
List<Integer> datas = new ArrayList<Integer>();
for (String key : sortedMap.keySet()){
datas.add(sortedMap.get(key));
}
int sum = 0; //总和
int avg = 0; //平均值
for (int data : datas){
sum += data;
}
avg = sum / totalCount;
int variance = 0; //方差
for (int data : datas){
variance += Math.pow(data - avg,2);
}
variance = variance / totalCount;
return Math.sqrt(variance);
}
}

运行结果:

****** 100万 KV数据在 10个服务器节点上的分布数量情况(未使用虚拟节点) ******
192.168.0.100:9000 节点有:9090 个KV对象
192.168.0.101:9000 节点有:85028 个KV对象
192.168.0.102:9000 节点有:52496 个KV对象
192.168.0.103:9000 节点有:175789 个KV对象
192.168.0.104:9000 节点有:150532 个KV对象
192.168.0.105:9000 节点有:17828 个KV对象
192.168.0.106:9000 节点有:95871 个KV对象
192.168.0.107:9000 节点有:288949 个KV对象
192.168.0.108:9000 节点有:27149 个KV对象
192.168.0.109:9000 节点有:97268 个KV对象
标准差:14654.29507004687

2).一致性 hash 算法,使用虚拟节点

ConsistencyHashVirtualNodeTest.java

package com.imolly.hash;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
/**
* 一致性 hash 算法,使用虚拟节点的测试类
*/
public class ConsistencyHashVirtualNodeTest {
private List<String> realServerNodes;
private List<String > keys;
@Before
public void before(){
int nodeCount = 10; //真实节点数
realServerNodes = new LinkedList<String>(); //真实节点集合
String baseIp = "192.168.0.10";
String basePort = "9000";
for (int i = 0; i < nodeCount; i++){
realServerNodes.add(baseIp + i + ":" + basePort);
}
int kvObjectCount = 1000000; //KV对象数
keys = new ArrayList<String>(); //KV对象集合
for (int i = 0; i < kvObjectCount; i++){
keys.add("键"+(i+1));
}
}
@Test
public void testHash(){
int virtualNodeCount = 190; //虚拟节点个数(每个真实节点对应的虚拟节点数)
ConsistencyHashVirtualNode consistencyHashVirtualNode = new ConsistencyHashVirtualNode(virtualNodeCount);
consistencyHashVirtualNode.setRealServerNodes(realServerNodes);
SortedMap<String,Integer> sortedMap = new TreeMap<String, Integer>();
String virtualNodeIp = "";
for (String key : keys){
virtualNodeIp = consistencyHashVirtualNode.getServerNode(key);
for (String realServerNodeIp : realServerNodes){
if(virtualNodeIp.startsWith(realServerNodeIp)){
if(sortedMap.containsKey(realServerNodeIp)){
sortedMap.put(realServerNodeIp,sortedMap.get(realServerNodeIp)+1);
}else{
sortedMap.put(realServerNodeIp,1);
}
}
}
System.out.println(key + " 的 hashCode : " + consistencyHashVirtualNode.getHashCode(key) + " , 被路由到节点: " + virtualNodeIp + " 中.");
}
System.out.println("****** 100万 KV数据在 10个服务器节点上的分布数量情况(使用虚拟节点) ******");
for (String key : sortedMap.keySet()){
System.out.println(key + " 节点有:" + sortedMap.get(key) + " 个KV对象");
}
System.out.println("标准差:" + calcStandardDeviation(sortedMap));
}
//计算标准差
private double calcStandardDeviation(SortedMap<String,Integer> sortedMap){
int totalCount = sortedMap.size();
List<Integer> datas = new ArrayList<Integer>();
for (String key : sortedMap.keySet()){
datas.add(sortedMap.get(key));
}
int sum = 0; //总和
int avg = 0; //平均值
for (int data : datas){
sum += data;
}
avg = sum / totalCount;
int variance = 0; //方差
for (int data : datas){
variance += Math.pow(data - avg,2);
}
variance = variance / totalCount;
return Math.sqrt(variance);
}
}

运行结果:

****** 100万 KV数据在 10个服务器节点上的分布数量情况(使用虚拟节点) ******
192.168.0.100:9000 节点有:102269 个KV对象
192.168.0.101:9000 节点有:112525 个KV对象
192.168.0.102:9000 节点有:92764 个KV对象
192.168.0.103:9000 节点有:99021 个KV对象
192.168.0.104:9000 节点有:99806 个KV对象
192.168.0.105:9000 节点有:91132 个KV对象
192.168.0.106:9000 节点有:103030 个KV对象
192.168.0.107:9000 节点有:91386 个KV对象
192.168.0.108:9000 节点有:103203 个KV对象
192.168.0.109:9000 节点有:104864 个KV对象
标准差:6413.429503783448

用户头像

molly

关注

还未添加个人签名 2017.12.14 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业 - 命题作业