架构师训练营第五章作业

发布于: 2020 年 07 月 08 日
架构师训练营第五章作业

算法背景

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用

作业内容

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

编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准

输出结果

结论:

  1. 获得hash值的算法对均衡性有一定的影响

  2. 命中率均衡是靠引入虚拟节点来解决的,虚拟节点越多,分布越均匀。虚拟节点越多,在服务增加或恢复时,涉及数据迁移的真实节点就越多,有数据迁移场景需求的需要考虑这一点

源码:

package hash;

/Node/

import java.util.HashMap;

import java.util.Map;

public class Node {

private int nodeNo;

private int serverNo;

private int nodeHashKey;

private Map<Integer, Integer> values = new HashMap<>(1000);

public int getServerNo() {

return serverNo;

}

public int getNodeHashKey() {

return nodeHashKey;

}

public Node(int serverNo, int nodeNo) {

this.serverNo = serverNo;

this.nodeNo = nodeNo;

this.nodeHashKey = Node.getHash("server" + this.serverNo + "#" + String.format("%3d", this.nodeNo));

}

public void cache(int key, int value) {

values.put(key, value);

}

public int getCount() {

return values.size();

}

// 选取了相对比较均衡的,改进的32位FNV算法

public static int getHash(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;

return hash;

}

}

package hash;

/Dht/

import java.util.Map;

import java.util.TreeMap;

public class Dht {

private int realNodes;

private int virtualNodes;

private TreeMap<Integer, Node> nodes;

public Dht(int realNodes, int virtualNodes) {

this.realNodes = realNodes;

this.virtualNodes = virtualNodes;

nodes = new TreeMap<>();

initServer();

}

private void initServer() {

for (int i = 0; i < realNodes; i++) {

for (int j = 0; j < virtualNodes; j++) {

Node node = new Node(i, j);

nodes.put(node.getNodeHashKey(), node);

}

}

}

public int[] getDistribution() {

int[] distribution = new int[realNodes];

for (Map.Entry<Integer, Node> node : nodes.entrySet()) {

distribution[node.getValue().getServerNo()] += node.getValue().getCount();

}

return distribution;

}

public void distribute(int[] data) {

for (int i = 0; i < data.length; i++) {

int hashCode = Node.getHash(data[i] + "");

Map.Entry<Integer, Node> entry = (entry = nodes.ceilingEntry(hashCode)) != null ? entry : nodes.firstEntry();

entry.getValue().cache(i, data[i]);

}

}

}

用户头像

吴吴

关注

还未添加个人签名 2018.03.02 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五章作业