上篇讲了一致性哈希的原理，本篇就用代码一步步实现 一致性哈希的基础功能 ！！！
构建哈希环（DHT）
由于一致性哈希讲究有序，所以哈希环的数据结构选择 TreeMap(key位置坐标，value为实际节点) ，可以方便的顺时针查找下一个节点。
列举一下DHT的主要方法
- 节点对自己
IP和端口进行哈希映射到环上不同的位置 - 数据对
key映射到环上的节点进行存储
哈希算法的选择
Java内建的散列码[hash code]概念被限制为32位，并且没有分离散列算法和它们所作用的数据，因此很难用备选算法进行替换，Object.hashCode往往很快，但是在预防碰撞上却很弱，也没有对分散性的预期。
我们选择 Guava 包 MurmurHash() 算法，运算效率高，预防碰撞也很强。
直接上代码
我们模拟 实际存储节点 类，如下
public class ServerNode {
private String ip;
private List dataList = new ArrayList();
public void addData(String data) {
dataList.add(data);
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public ServerNode(String ip) {
this.ip = ip;
}
@Override
public String toString() {
return "ServerNode{" +
"ip='" + ip + ''' +
", dataList=" + dataList +
'}';
}
}
哈希环 定义如下
public class DHT {
private TreeMap dht = new TreeMap();
HashFunction hashFunction = Hashing.murmur3_128(64);
/**
* 节点映射
*
* 添加节点 对节点 hash（IP + port）%16384结果 作为哈希环下标
*/
public void addNode(ServerNode serverNode) {
HashCode hashCode = getHashCode(serverNode.getIp());
long index = hashCode.asLong() % 16384L;
System.out.println(serverNode.getIp() + ": " + Math.abs(index));
dht.put(Math.abs(index), serverNode);
}
private HashCode getHashCode(String ip) {
return hashFunction.newHasher()
.putString(ip, StandardCharsets.UTF_8)
.hash();
}
/**
* 根据key 选择一个节点，如果没有命中节点，则顺时针查找下一个节点
*/
public ServerNode selectNode(String key) {
HashCode hashCode = hashFunction.newHasher()
.putString(key, StandardCharsets.UTF_8)
.hash();
long index = Math.abs(hashCode.asLong()) % 16384L;
SortedMap subDht = dht.tailMap(index);
System.out.print("key:" + key + "的位置: " + index + " 选择的节点: ");
return dht.get(subDht.firstKey());
}
/**
* 向集群中 添加数据
*/
public void addData(String key) {
//先通过哈希算法选择 一个实际节点
ServerNode serverNode = selectNode(key);
System.out.println(serverNode.getIp());
serverNode.addData(key);
}
}
然后我们创建测试程序
public class Main {
public static void main(String[] args) {
DHT dht = new DHT();
System.out.println("初始化节点映射.....");
ServerNode serverNode = new ServerNode("10.6.3.178");
ServerNode serverNode2 = new ServerNode("10.6.3.191");
ServerNode serverNode3 = new ServerNode("10.6.3.183");
ServerNode serverNode4 = new ServerNode("10.6.3.189");
dht.addNode(serverNode);
dht.addNode(serverNode2);
dht.addNode(serverNode3);
dht.addNode(serverNode4);
System.out.println("添加数据");
dht.addData("shop:sku:4");
dht.addData("shop:sku:7");
}
}
运行结果如下图
虚拟节点优化
上面的节点数量太少，容易造成数据倾斜问题。如果对数据分布想要达到更均匀，可以采取虚拟节点优化。
实践
我们维护虚拟节点 和 实际节点的映射关系。key为虚拟节点IP，value为实际节点。
举个例子对于ip为10.6.3.178的节点， 对应的虚拟节点IP就可以是10.6.3.178#1，10.6.3.178#2，10.6.3.178#3。映射关系可以如下设计
private final HashMap vit = new HashMap();
然后在修改 节点映射方法
public void addNode(ServerNode serverNode) {
HashCode hashCode = getHashCode(serverNode.getIp());
long index = hashCode.asLong() % 16384L;
System.out.println(serverNode.getIp() + ": " + Math.abs(index));
dht.put(Math.abs(index), serverNode);
//添加虚拟节点
for (int i = 0; i < 15;i++) {
//获得虚拟节点的哈希值
HashCode hashCodeVit = getHashCode(serverNode.getIp() + "#" + i);
long indexV = hashCodeVit.asLong() % 16384L;
ServerNode serverNodeV = new ServerNode(serverNode.getIp() + "#" + i);
//将虚拟节点添加到哈希环，
dht.put(Math.abs(indexV), serverNodeV);
//建立虚拟IP和 真实节点的映射关系
vit.put(serverNode.getIp() + "#" + i, serverNodeV);
}
}
添加数据时， sleectNode() 获得的节点ip，接着去映射获取serverNode，获取为空则该节点就是真实节点；不为空，则获取的serverNode就是真实节点。
总结
以上的是实现提供了一致性哈希的实现思路。实际在生产中还要考虑读写性能，数据迁移等等。
对于数据倾斜问题，虚拟节点的总数量一定要足够大，数据才可以分布均匀。在实际项目里，为了避免机器太少造成的数据倾斜问题，往往会把 哈希环的容纳总量（16384）调小，也可以使数据分布均匀。
我是爱聊技术的山人，我们下期再见🤗🤗
