架构师训练营第五章作业

算法背景

一致性哈希算法在 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]);

}

}

}