架构师训练营 -week5- 作业
发布于: 2020 年 07 月 08 日
用你熟悉的编程语言实现一致性 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 日阅读数: 65
版权声明: 本文为 InfoQ 作者【晓－Michelle】的原创文章。
原文链接:【http://xie.infoq.cn/article/4c723bbafa5ed082dc141017e】。未经作者许可，禁止转载。
晓－Michelle
关注
还未添加个人签名 2020.05.30 加入
还未添加个人简介
评论