写点什么

一致性哈希 -- java 实现

用户头像
lei Shi
关注
发布于: 2020 年 07 月 06 日

一致性哈希介绍

https://zh.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C

代码 - 测试类

package com.geektime.consistenthash.geektime;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;


@Slf4j
class ConsistentHashTest {

private static Set<String> requests = new HashSet<>();

private static final int requestCount = 10000;

private static final int physicalNodeCount = 10;

private static Map<Integer, Double> trend = new LinkedHashMap<>();

static {
initRequests();
}

@Test
public void nodeRouter() {

for (int virtualNodeCount = 0; virtualNodeCount < 300; virtualNodeCount++) {


ConsistentHash consistentHash = new ConsistentHash(physicalNodeCount, virtualNodeCount);

TreeMap<String, Integer> nodeLoad = new TreeMap<>();
requests.forEach(ele -> {
String nodeName = consistentHash.nodeRouter(ele);
if (nodeLoad.containsKey(nodeName)) {
Integer load = nodeLoad.get(nodeName);
nodeLoad.replace(nodeName, load + 1);
} else {
nodeLoad.put(nodeName, 1);
}
});

double standardDeviation = getStandardDeviation(nodeLoad, virtualNodeCount);
// log.info("============= physicalNodeCount = {}, virtualNodeCount = {}, standardDeviation = {}", physicalNodeCount, virtualNodeCount, standardDeviation);

trend.put(virtualNodeCount, standardDeviation);
}

trend.forEach((key, val) -> {
log.info("{},{}", key, val);
});
}

private static void initRequests() {
for (int index = 0; index < requestCount; index++) {
UUID uuid = UUID.randomUUID();
requests.add(uuid.toString());
}
// log.info("---------------------------- requests.size = {}", requests.size());
}

private double getStandardDeviation(Map<String, Integer> nodeLoad, Integer virtualNodeCount) {
int sum = nodeLoad.values().stream().mapToInt(Integer::intValue).sum();
float average = (float) sum / (float) physicalNodeCount;
AtomicReference<Double> deviation = new AtomicReference<>(0.0);

nodeLoad.values().forEach(ele -> {
// deviation.updateAndGet(v -> (float) (v + Math.pow(ele - average, 2)));
deviation.updateAndGet(v -> v + (ele - average) * (ele - average));

});
return Math.sqrt(deviation.get() / (float) physicalNodeCount);

}
}



代码 - 主类

package com.geektime.consistenthash.geektime;

import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

import java.util.List;
import java.util.TreeMap;
import java.util.UUID;
import java.util.stream.Collectors;

@Setter
@Getter
@Slf4j
public class ConsistentHash {

private TreeMap<Integer, String> CYCLE = new TreeMap<>();
private TreeMap<Integer, String> PHYSICAL_NODES = new TreeMap<>();
private TreeMap<Integer, String> VIRTUAL_NODES = new TreeMap<>();

private int physicalNodeCount = 0;
private int virtualNodeCount = 0;

public ConsistentHash(int physicalNodeCount, int virtualNodeCount) {
setPhysicalNodeCount(physicalNodeCount);
setVirtualNodeCount(virtualNodeCount);
initPhysicalNodes();
initVirtualNodes();
initCycle();
// log.info("***************************first CYCLE ele = {}, last CYCLE ele = {}, CYCLE.eles.count = {}", CYCLE.firstEntry().getValue(), CYCLE.lastEntry().getValue(), CYCLE.size());
}

private void initCycle() {
CYCLE.putAll(PHYSICAL_NODES);
CYCLE.putAll(VIRTUAL_NODES);

}

private void initPhysicalNodes() {
for (int index = 0; index < physicalNodeCount; index++) {
String nodeName = "node_" + index;
int hashCode = UUID.randomUUID().hashCode();
PHYSICAL_NODES.put(hashCode, nodeName);
}
}

private void initVirtualNodes() {
PHYSICAL_NODES.values().forEach(cNodeName -> {
for (int index = 0; index < virtualNodeCount; index++) {
String cVirtualNodeName = cNodeName + ".virtualNode_" + index;
int hashCode = UUID.randomUUID().hashCode();
VIRTUAL_NODES.put(hashCode, cVirtualNodeName);
}
});
}

public String nodeRouter(String requestKey) {
int hashCode = requestKey.hashCode();
int l_targetNodeHash = Integer.MIN_VALUE;
int r_targetNodeHash = Integer.MAX_VALUE;
List<Integer> collect = CYCLE.keySet()
.stream()
.sorted()
.collect(Collectors.toList());
for (int cIndex = 0; cIndex < collect.size(); cIndex++) {
if (collect.size() - 1 == cIndex) {
l_targetNodeHash = collect.get(cIndex - 2);
r_targetNodeHash = collect.get(cIndex - 1);
break;
}

if (collect.get(cIndex) > hashCode) {


if (0 == cIndex) {
l_targetNodeHash = collect.get(cIndex);
r_targetNodeHash = collect.get(cIndex + 1);
break;
}

l_targetNodeHash = collect.get(cIndex - 1);
r_targetNodeHash = collect.get(cIndex);
break;
}
}

int hash;
if (Math.abs(l_targetNodeHash - hashCode) < Math.abs(r_targetNodeHash - hashCode)) {
hash = l_targetNodeHash;
} else {
hash = r_targetNodeHash;
}

String nodeName = CYCLE.get(hash);
try {
if (nodeName.contains(".")) {
int index = nodeName.indexOf(".");
return nodeName.substring(0, index);
}
return nodeName;
} catch (IndexOutOfBoundsException e) {
log.error("============================ node name = {}", nodeName);
return "";
} catch (NullPointerException e) {
log.error("**************************** node name = {}", nodeName);
return "";
}
}


}


标准差可视化



关键点

  1. KV使用hash作为key,node name作为value

  2. 涉及到排序以及查找,使用 TreeMap 存储映射关系

  3. 标准差直接打印在控制台,在excel绘制趋势图(JFrame没搞定,害)

  4. 其实,感觉物理节点有没有映射到 hash 环上并没有关系

坑点

  1. 生成节点节点hash值 不能直接采用string的hash值,最好使用 random UUID的字符串的hash

  2. 实际的趋势图并不是并不是向老师说的150到200的时候基本趋于稳定,而是在一百个虚拟节点的时候就比较稳定了



发布于: 2020 年 07 月 06 日阅读数: 63
用户头像

lei Shi

关注

还未添加个人签名 2018.05.24 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希 -- java 实现