架构师训练营 - 作业 - 第五周

发布于: 22 小时前
  1. 用你熟悉的编程语言实现一致性哈希算法。

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

标准差(均方差)公式:(每个样本 - 平均值)的平方和 / 服务器数,结果再取平方根

标准差越小,代表越稳定(较接近平均值)。

例如,两组数的集合{0,5,9,14}和{5,6,8,9}其平均值都是7,但第二个集合具有较小的标准差。

分布式一致性哈希算法原理

构造一个长度为2的32次方的正整数哈希环(去掉负数,分布为[0, 2的32次方-1],0 和 2的32次方-1为重合点)。

将服务器节点的哈希值存入环(分布为:[0 - 2的32次方-1])。然后计算用户 Key 的哈希值(分布也为:[0 - 2的32次方-1]),接着在哈希环上顺时针查找距离这个用户 Key 值的哈希值最近的服务器节点,完成 Key 到服务器的映射查找。

思路

  1. 选择一个哈希算法,使 Key 能够均匀分布到哈希换上。如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法。

  2. 对服务器节点建立虚拟节点,将虚拟节点的哈希值均匀分布到哈希环上。

  3. 建立虚拟节点和真实节点的映射关系,映射关系的数据结构直接影响整个算法的运行效率,建议采用树结构的Map。

  4. 根据用户 Key 哈希值查找对映的虚拟节点和真实节点。

Code
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
interface HashFunction {
public int hash(String data);
}
class FNVHash1 implements HashFunction {
@Override
public int hash(final String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++) {
hash = (hash ^ data.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return Math.abs(hash);
}
}
class ConsistantHash {
private final HashFunction hashFunction;
private final int virtualNodeNum;
private final SortedMap<Integer, String> hashCircle = new TreeMap<>();
ConsistantHash(final List<String> nodes, final int virtualNodeNum, final HashFunction hashFunction) {
this.hashFunction = hashFunction;
this.virtualNodeNum = virtualNodeNum;
for (final String node : nodes) {
add(node);
}
}
public void add(final String node) {
hashCircle.put(hashFunction.hash(node), node);
for (int i = 0; i < virtualNodeNum; i++) {
hashCircle.put(hashFunction.hash(node + i), node);
}
}
public void remove(final String node) {
hashCircle.remove(hashFunction.hash(node));
for (int i = 0; i < virtualNodeNum; i++) {
hashCircle.remove(hashFunction.hash(node + i));
}
}
public String get(final String key) {
if (hashCircle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!hashCircle.containsKey(hash)) {
final SortedMap<Integer, String> tailMap = hashCircle.tailMap(hash);
hash = tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey();
}
return hashCircle.get(hash);
}
}
public class ConsistantHashTest {
public static void main(final String[] args) {
final int NODE_NUM = 10;
final int VIRTUAL_NODE_NUM = 200;
final int USER_KEY_NUM = 100_0000;
// init server node
final List<String> nodes = new ArrayList<>();
for (int i = 0; i < NODE_NUM; i++) {
nodes.add("server-" + i);
}
final HashFunction fnvHash = new FNVHash1();
final ConsistantHash hashCircle = new ConsistantHash(nodes, VIRTUAL_NODE_NUM, fnvHash);
// init user keys
final List<String> keys = new ArrayList<>();
for (int i = 0; i < USER_KEY_NUM; i++) {
keys.add("user-key-" + i);
}
// search server node by user key then record result
final SortedMap<String, Integer> result = new TreeMap<>();
for (final String key : keys) {
final String node = hashCircle.get(key);
result.put(node, result.getOrDefault(node, 0) + 1);
// System.out.println(node + ":" + key);
}
// calculate standard deviation and print
double sum = 0;
double standardDeviation = 0;
final int average = USER_KEY_NUM / NODE_NUM;
for (final Map.Entry<String, Integer> entry : result.entrySet()) {
final String node = entry.getKey();
final Integer numberOfKeysPerNode = entry.getValue();
System.out.println(node + " -> " + numberOfKeysPerNode);
sum += Math.pow( Math.abs(average - numberOfKeysPerNode), 2);
}
standardDeviation = Math.sqrt(sum / NODE_NUM);
System.out.println("Standard Deviation: " + standardDeviation);
}
}

Output:

Reference

https://web.archive.org/web/20120605030524/http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html

https://www.cnblogs.com/jajian/p/10896624.html

https://blog.csdn.net/b6ecl1k7BS8O/article/details/87219516

https://xie.infoq.cn/article/81aed863f23f63421af1b86bb

https://xie.infoq.cn/article/f6c25a2572ad153375b780e11

https://xie.infoq.cn/article/b7e493519483fb1d4992ee522

用户头像

心在飞

关注

还未添加个人签名 2017.10.15 加入

2个女儿的爸爸 | 程序员 | CS 反恐精英

评论 (1 条评论)

发布
用户头像
求 hash 算法不错,赞一个
11 小时前
回复
没有更多了
架构师训练营 - 作业 - 第五周