架构师训练营 -week5- 作业

发布于: 2020 年 07 月 08 日
架构师训练营-week5-作业
  • 用你熟悉的编程语言实现一致性 hash 算法。

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

一致性hash算法:

构建环(可用map、链表、数组等实现),获取虚拟节点的哈希值,保存在环上。当一个key进来时,获取key的哈希值,顺时针查找离key的哈希值最近的虚拟节点,将kv数据保存在虚拟节点对应的物理节点上。

将数据结构定为“环”,是为了避免出现部分key无法在顺时针方向找到最近的虚拟节点。因此当key沿顺时针无法找到虚拟节点时,则将该kv数据保存在第一个虚拟节点对应的物理节点。由此,构成一个环。

作业中使用的是java语言,考虑到有多种hash算法,所以采用策略模式调用hash算法,可以观察不同hash算法的表现。在这里,仅展示FNV1算法的效果。

根据代码画出来的类图(感觉怪怪的,求指教)

模拟缓存接口

package week5;
public interface ICache {
public void put(String key, Object value);
public Object get(String key);
}

物理节点类

package week5;
import java.util.Vector;
public class PhysicalNode implements ICache {
String nodeName;
String nodeIp;
Vector<VirtualNode> virtualNodes;
private int total;
public PhysicalNode(String nodeName, String ip) {
// TODO Auto-generated constructor stub
this.nodeName = nodeName;
this.nodeIp = ip;
this.total = 0;
this.virtualNodes = new Vector<>();
}
public String getNodeName() {
return this.nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public String getNodeIp() {
return nodeIp;
}
public void setNodeIp(String nodeIp) {
this.nodeIp = nodeIp;
}
public int getTotal(){
return this.total;
}
public Vector<VirtualNode> getVirtualNodes() {
return virtualNodes;
}
public void addVirtualNode(VirtualNode node) {
virtualNodes.add(node);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("\r\n ----------Physical Node:----------");
sb.append("\r\n name:" + this.nodeName);
sb.append("\r\n ip:" + this.nodeIp);
sb.append("\r\n total:" + this.total);
sb.append("\r\n --------Virtual Node:--------");
for (VirtualNode virtualNode : virtualNodes) {
sb.append(virtualNode.toString());
}
return sb.toString();
}
// 模拟存储kv数据,统计物理节点缓存的kv数据个数。
@Override
public void put(String key, Object value) {
// TODO Auto-generated method stub
total++;
}
@Override
public Object get(String key) {
// TODO Auto-generated method stub
return null;
}
}

虚拟节点类

package week5;
public class VirtualNode implements ICache {
PhysicalNode parentNode;
int nodeHashCode;
String nodeName;
int total;
public VirtualNode(String name, int hashCode, PhysicalNode node) {
this.nodeHashCode = hashCode;
this.nodeName = name;
this.parentNode = node;
this.total = 0;
}
public PhysicalNode getParentNode() {
return parentNode;
}
public Integer getNodeHashCode() {
return nodeHashCode;
}
public String getNodeName() {
return nodeName;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("\r\n name:" + this.nodeName+" total:"+this.total);
return sb.toString();
}
// 模拟虚拟节点存储缓存,统计虚拟节点被命中的次数
@Override
public void put(String key, Object value) {
// TODO Auto-generated method stub
this.total++;
parentNode.put(key, value);
}
@Override
public Object get(String key) {
// TODO Auto-generated method stub
return parentNode.get(key);
}
}

hash算法接口

package week5;
public interface IHash {
public int getHashCode(String key);
}

哈希环(计算哈希值的算法从外部注入)

package week5;
import java.util.Map;
import java.util.TreeMap;
import java.util.Vector;
public class HashRing {
Vector<PhysicalNode> physicalNodes;//物理节点列表
TreeMap<Integer, VirtualNode> map;//虚拟节点
IHash hashCodeGetter;//计算哈希值算法
int virtualNodeTotal;//统计虚拟节点个数
int keyTotal;//统计kv数据个数
public HashRing(IHash hashCodeGetter) {
// TODO Auto-generated constructor stub
physicalNodes = new Vector<>();
map = new TreeMap<>();
virtualNodeTotal = 0;
this.hashCodeGetter = hashCodeGetter;
}
/**
* 添加物理节点
* @param physicalNodeName
* @param physicalNodeIp
* @param virtualNodeNum
*/
public void addPhysicalNode(String physicalNodeName, String physicalNodeIp, int virtualNodeNum) {
PhysicalNode node = new PhysicalNode(physicalNodeName, physicalNodeIp);
VirtualNode virtualNode = null;
for (int i = 0; i < virtualNodeNum; i++) {
virtualNodeTotal++;
String nodeName = node.nodeName + "_VN_" + String.format("%02d", i);
virtualNode = new VirtualNode(nodeName, getHashCode(nodeName), node);
map.put(virtualNode.nodeHashCode, virtualNode);
node.addVirtualNode(virtualNode);
}
physicalNodes.add(node);
System.out.println("name:" + physicalNodeName + " ip:" + physicalNodeIp);
}
public void setCache(String key, Object value) {
keyTotal++;
getVirtualNode(key).put(key, value);
}
private VirtualNode getVirtualNode(String key) {
return this.getEntry(key).getValue();
}
/**
* 根据哈希值,顺时针获取最近的虚拟节点
* @param key
* @return
*/
private Map.Entry<Integer, VirtualNode> getEntry(String key) {
int hashCode = getHashCode(key);
Map.Entry<Integer, VirtualNode> entry = map.ceilingEntry(hashCode);
if (entry == null) {
return map.firstEntry();
}
return entry;
}
public PhysicalNode getPhysicalNode(String key) {
return this.getEntry(key).getValue().parentNode;
}
public Vector<PhysicalNode> getPhysicalNodes() {
return this.physicalNodes;
}
/**
* 计算标准差
* @return
*/
public double getStandardDeviation() {
double avg = keyTotal / physicalNodes.size();
double distance = 0;
int total = 0;
for (PhysicalNode physicalNode : physicalNodes) {
total = physicalNode.getTotal();
distance += (total - avg) * (total - avg);
}
double sd = Math.sqrt(distance / physicalNodes.size());
return sd;
}
/**
* 获取打印头部段落
* @return
*/
private StringBuilder getOutputTitle() {
StringBuilder sb = new StringBuilder();
sb.append("-------------Hash Ring:-------------");
sb.append("\r\nPhyscial Node Total:" + this.physicalNodes.size());
sb.append("\r\nVirtual Node Total:" + this.virtualNodeTotal);
sb.append("\r\nKey Total:" + this.keyTotal);
return sb;
}
@Override
public String toString() {
StringBuilder sb = getOutputTitle();
for (PhysicalNode physicalNode : physicalNodes) {
// sb.append(physicalNode.toString());
sb.append("\r\nname:" + physicalNode.nodeName + " total:" + physicalNode.getTotal());
}
sb.append("\r\n\r\nStandard Deviation:" + getStandardDeviation());
return sb.toString();
}
/**
* 计算哈希值
* @param key
* @return
*/
private int getHashCode(String key) {
return this.hashCodeGetter.getHashCode(key);
}
}

FN1Hash算法

package week5;
public class FNV1Hash implements IHash {
@Override
public int getHashCode(String key) {
// TODO Auto-generated method stub
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++)
hash = (hash ^ key.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;
}
}

测试类

package week5;
import java.util.UUID;
import junit.framework.TestCase;
public class ConsistentHashTest extends TestCase {
private String[] physicalNodeIps;
private String[] physicalNodeNames;
private int maxDataSize;
private int nodeTotal;
private int virtualNodeNum;
private HashRing ring;
@Override
protected void setUp() {
maxDataSize = 1000000;
nodeTotal = 10;
virtualNodeNum = 250;
physicalNodeIps = new String[nodeTotal];
physicalNodeNames = new String[nodeTotal];
// 初始化物理节点ip与节点名
for (int i = 0; i < nodeTotal; i++) {
physicalNodeIps[i] = "192.168.1.10" + i + ":7003";
physicalNodeNames[i] = "节点" + i;
}
// 初始化哈希环,添加物理节点
ring = new HashRing(new FNV1Hash());
for (int i = 0; i < nodeTotal; i++) {
ring.addPhysicalNode(physicalNodeNames[i], physicalNodeIps[i], virtualNodeNum);
}
}
public void testConsistentHash() {
// 模拟循环加入100万个kv缓存数据
for (int i = 0; i < maxDataSize; i++) {
ring.setCache(UUID.randomUUID().toString().substring(2, 10), new Object());
}
// 打印哈希环信息
System.out.println(ring.toString());
}
}

输出结果:

按理论计算,10台服务器,100万个数据,平均到每台服务器上应该是10万条数据。从图上的结果可以看出,节点间存储的数据量差距较大,体现了存储的不均衡性。

将虚拟节点数增加到250的输出结果:

对比每台物理节点有100台虚拟节点的数据,其标准差是下降的,表明在虚拟节点的数量增加,对降低数据存储差距有一定的帮助。

在以上的代码中,还可以再包装一层测试类,用于比较不同的hash算法在hash一致性算法中的表现,待我不用再赶作业的时候补上

发布于: 2020 年 07 月 08 日 阅读数: 13
用户头像

晓-Michelle

关注

还未添加个人签名 2020.05.30 加入

还未添加个人简介

评论

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