架构师训练营 Week5 作业

发布于: 2020 年 07 月 08 日

一致性hash算法及java实现

一致性hash算法是分布式中一个常用且好用的分片算法、或者数据库分库分表算法。现在的互联网服务架构中,为避免单点故障、提升处理效率、横向扩展等原因,分布式系统已经成为了居家旅行必备的部署模式,所以也产出了几种数据分片的方法:

  • 取模

  • 划段

  • 一致性hash

前两种有很大的一个问题就是需要固定的节点数,即节点数不能变,不能某一个节点挂了或者实时增加一个节点,变了分片规则就需要改变,需要迁移的数据也多。

那么一致性hash是怎么解决这个问题的呢?

一致性hash:对节点和数据,都做一次hash运算,然后比较节点和数据的hash值,数据值和节点最相近的节点作为处理节点。为了分布得更均匀,通过使用虚拟节点的方式,每个节点计算出n个hash值,均匀地放在hash环上这样数据就能比较均匀地分布到每个节点

通过学习做了一个简单的实现:

package me.lichun.homework.week5;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* 一致性hash算法
* </br>
* 重点:1.如何造一个hash环,2.如何在哈希环上映射服务器节点,3.如何找到对应的节点
*
* @author: lichun
* @date: 2020/7/8
*/
public class ConsistentHashingWithoutNode {
//待添加入Hash环的服务器列表,10个服务节点
private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111",
"192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111", "192.168.0.5:111", "192.168.0.6:111",
"192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111" };
//key表示服务器的hash值,value表示服务器
private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
//程序初始化,将所有的服务器放入sortedMap中
static {
for (int i=0; i<servers.length; i++) {
int hash = getHash(servers[i]);
System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
sortedMap.put(hash, servers[i]);
}
System.out.println();
}
//得到应当路由到的结点
private static String getServer(String key) {
//得到该key的hash值
int hash = getHash(key);
//得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(subMap.isEmpty()){
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
return sortedMap.get(i);
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
return subMap.get(i);
}
}
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
private 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;
}
// 如果算出来的值为负数则取其绝对值
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
public static void main(String[] args) {
long node0Count = 0L;
long node1Count = 0L;
long node2Count = 0L;
long node3Count = 0L;
long node4Count = 0L;
long node5Count = 0L;
long node6Count = 0L;
long node7Count = 0L;
long node8Count = 0L;
long node9Count = 0L;
// 模拟100W的KV数据
Map<String, String> testMap = new HashMap<>();
for(int i=0; i< 1000000; i++) {
testMap.put("key" + i, "value" + i);
}
for(Map.Entry<String, String> entry : testMap.entrySet()) {
String mapStr = entry.getKey() + ":" + entry.getValue();
String nodeStr = getServer(mapStr);
if (servers[0].equals(nodeStr)){
node0Count++;
}
if (servers[1].equals(nodeStr)){
node1Count++;
}
if (servers[2].equals(nodeStr)){
node2Count++;
}
if (servers[3].equals(nodeStr)){
node3Count++;
}
if (servers[4].equals(nodeStr)){
node4Count++;
}
if (servers[5].equals(nodeStr)){
node5Count++;
}
if (servers[6].equals(nodeStr)){
node6Count++;
}
if (servers[7].equals(nodeStr)){
node7Count++;
}
if (servers[8].equals(nodeStr)){
node8Count++;
}
if (servers[9].equals(nodeStr)){
node9Count++;
}
}
System.out.println("[" + "服务节点" + servers[0] + "路由到的个数为:" + String.valueOf(node0Count) +"]");
System.out.println("[" + "服务节点" + servers[1] + "路由到的个数为:" + String.valueOf(node1Count) +"]");
System.out.println("[" + "服务节点" + servers[2] + "路由到的个数为:" + String.valueOf(node2Count) +"]");
System.out.println("[" + "服务节点" + servers[3] + "路由到的个数为:" + String.valueOf(node3Count) +"]");
System.out.println("[" + "服务节点" + servers[4] + "路由到的个数为:" + String.valueOf(node4Count) +"]");
System.out.println("[" + "服务节点" + servers[5] + "路由到的个数为:" + String.valueOf(node5Count) +"]");
System.out.println("[" + "服务节点" + servers[6] + "路由到的个数为:" + String.valueOf(node6Count) +"]");
System.out.println("[" + "服务节点" + servers[7] + "路由到的个数为:" + String.valueOf(node7Count) +"]");
System.out.println("[" + "服务节点" + servers[8] + "路由到的个数为:" + String.valueOf(node8Count) +"]");
System.out.println("[" + "服务节点" + servers[9] + "路由到的个数为:" + String.valueOf(node9Count) +"]");
}
}

执行结果:

[192.168.0.0:111]加入集合中, 其Hash值为1767802393
[192.168.0.1:111]加入集合中, 其Hash值为406441873
[192.168.0.2:111]加入集合中, 其Hash值为800212117
[192.168.0.3:111]加入集合中, 其Hash值为475180206
[192.168.0.4:111]加入集合中, 其Hash值为514183420
[192.168.0.5:111]加入集合中, 其Hash值为854676609
[192.168.0.6:111]加入集合中, 其Hash值为995851316
[192.168.0.7:111]加入集合中, 其Hash值为1193712218
[192.168.0.8:111]加入集合中, 其Hash值为987443045
[192.168.0.9:111]加入集合中, 其Hash值为441056192
[服务节点192.168.0.0:111路由到的个数为:267494]
[服务节点192.168.0.1:111路由到的个数为:365524]
[服务节点192.168.0.2:111路由到的个数为:133545]
[服务节点192.168.0.3:111路由到的个数为:16077]
[服务节点192.168.0.4:111路由到的个数为:18135]
[服务节点192.168.0.5:111路由到的个数为:25427]
[服务节点192.168.0.6:111路由到的个数为:3796]
[服务节点192.168.0.7:111路由到的个数为:92054]
[服务节点192.168.0.8:111路由到的个数为:61949]
[服务节点192.168.0.9:111路由到的个数为:15999]

通过对比发现数据通过一致性hash算法,存在着负载不均衡的情况,这个怎么解决?需要我们后续在学习,再总结

用户头像

平淡人生

关注

还未添加个人签名 2018.11.05 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 Week5作业