前几天关注蚂蚁金服sofa博客,偶然看到一篇在讲解sofaRegistry的文章,里头提到slotTable以及一致性hash算法。其实之前面试八股文也是经常会出现它的身影,今天我们深入看看它长什么样子
在很多开源中间件中都会用到这种设计,比如redis slot槽,会将数据拆分然后分布到不同槽,这样提高了数据的横向扩展能力。SofaRegistry在储存数据的时候,也采用了这种设计,这样可以采用集群的方式来部署中间件,数据通过一定规则散落在各个节点,整体扩展性上来了。
一般分为横向扩展、纵向扩展,纵向就是加配置,比如买辆汽车,开个天窗,配置个高档音响,配置拉满,同样服务器还有数据库也能将配置拉满。横向扩展加上一辆车不够,两辆,加到满足需求为止
横向扩展,如果说我们把数据都放在一张表,那么它的横向扩展肯定是不行的,这时我们想到分库分表,sharingjdbc,其实就是把某个字段进行一定的算法计算之后,决定它命中哪张表,哪个库,这样通过数据拆分,我们可以通过增加表的数量,数据库的数量来提高数据的存储量。
通过特定key,然后一定的算法计算,整除节点次数,这样数据就分配到这些节点
虽然整除算法可以实现数据拆分效果,但是对于节点增加、减少的情况,会导致所有数据得重新分配,这样无疑成本就提高了。针对这种情况,一致性hash算法就出现了。
首先这个算法会将所有值储存在一个环里头,比如说data1的位置,只要落在上面这片区域属于Node1,下面区域是属于Node2,所以data2落在Node2进行储存。
比如说现在增加节点Node3,data1数据不会变,只是data2的数据从原本Node2迁移到Node3去。这样只会影响一部分数据。
这时如果把Node2干掉,那么我们只需要将data2迁移到Node1,不会影响之前Node1的数据。
从上面情况来看,一致性hash算法对于新增、删除节点,只是会影响部分数据。
当我们节点分配不好的时候,就会出现某个节点数据贼多,这样会导致大部分请求都跑去某个节点,该节点压力会很多,其他节点又没有流量。那这个时候解决方案就是增加虚拟节点。
新增了Node1-1、Node2-1虚拟节点,这样数据就不会因为划分不均匀导致数据倾斜。
我尝试的是带有虚拟节点的方案
//总节点数据,包括实际上节点,还有虚拟节点
static NavigableMap> map = new TreeMap<>();
//收集实际上节点对应哪些虚拟节点
static Map> map1 = new HashMap<>();
public static void main(String[] args) {
int a = 0;
while (a < 4) {
String ip = "172.29.3." + a;
map.put(hashcode(ip), new ArrayList<>());
map1.put(ip, new ArrayList<>(List.of(hashcode(ip))));
for (int b = 0; b < 150; b++) {
int number = hashcode(ip + "#" + RandomUtil.randomInt(5));
map.put(number, new ArrayList<>());
List list = map1.get(ip);
if (CollectionUtil.isEmpty(list)) {
map1.put(ip, new ArrayList<>(List.of(number)));
} else {
map1.get(ip).add(number);
}
}
a++;
}
int i = 0;
while (i < 8000000) {
String msg = RandomUtil.randomString(20);
get(map, msg, map1).add(msg);
i++;
}
map1.forEach((k, v) -> {
System.out.println(k + " " + map.get(hashcode(k)).size());
});
}
private static void remove(String ip) {
List idList = map1.get(ip);
map1.remove(ip);
idList.forEach(id->map.remove(id));
}
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
private static int hashcode(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;
}
private static List get(NavigableMap> map, String msg, Map> map1) {
Map.Entry> entry = map.ceilingEntry(hashcode(msg));
AtomicReference> list = new AtomicReference<>();
if (entry == null) {
map1.forEach((k, v) -> {
if (v.contains(map.firstEntry().getKey())) {
list.set(map.get(hashcode(k)));
}
});
} else {
map1.forEach((k, v) -> {
if (v.contains(entry.getKey())) {
list.set(map.get(hashcode(k)));
}
});
}
return list.get();
}
//总节点数据,包括实际上节点,还有虚拟节点
static NavigableMap> map = new TreeMap<>();
//收集实际上节点对应哪些虚拟节点
static Map> map1 = new HashMap<>();
这里是往刚刚两个map储存数据
int a = 0;
while (a < 4) {
String ip = "172.29.3." + a;
map.put(hashcode(ip), new ArrayList<>());
map1.put(ip, new ArrayList<>(List.of(hashcode(ip))));
for (int b = 0; b < 150; b++) {
int number = hashcode(ip + "#" + RandomUtil.randomInt(5));
map.put(number, new ArrayList<>());
List list = map1.get(ip);
if (CollectionUtil.isEmpty(list)) {
map1.put(ip, new ArrayList<>(List.of(number)));
} else {
map1.get(ip).add(number);
}
}
a++;
}
private static List get(NavigableMap> map, String msg, Map> map1) {
Map.Entry> entry = map.ceilingEntry(hashcode(msg));
AtomicReference> list = new AtomicReference<>();
if (entry == null) {
map1.forEach((k, v) -> {
if (v.contains(map.firstEntry().getKey())) {
list.set(map.get(hashcode(k)));
}
});
} else {
map1.forEach((k, v) -> {
if (v.contains(entry.getKey())) {
list.set(map.get(hashcode(k)));
}
});
}
return list.get();
}
//使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
private static int hashcode(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;
}
172.29.3.3 1834587
172.29.3.2 1805299
172.29.3.1 1892821
172.29.3.0 2467293
我们可以看到数据蛮均匀的分配的。
上面的例子,比如说删除节点,里面数据没有做迁移的,这个纠结需不需要迁移呢?
需要迁移的,大家可以自行了解下redis slots槽的设计,如果集群里面新增节点,需要人工去手动将slot移动到新的节点,减少也是一样的操作。