一致性 hash 算法

用户头像
Z冰红茶
关注
发布于: 2020 年 07 月 07 日

定义:一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个空间按顺时针方向组织。0和232-1在零点中方向重合。

应用场景:分布式缓存Memcached等。

目标:尽量把数据平均分配到每个分布式节点,且增加删除节点对数据没影响或是影响最小。

实现:java中的TreeMap.ceilingEntry(key)方法返回与该键至少大于或等于给定键的实体,所以实现相对简单,HashCode先用Guava的Hashing.hmacMd5()

public class ConsistentHash {
private TreeMap<Integer, String> virtualNodeMap = new TreeMap<>();
private List<String> nodes;
private Integer virtualSize = 32;
public ConsistentHash(List<String> nodes){
this.nodes = nodes;
init();
}
public ConsistentHash(List<String> nodes, Integer virtualSize){
this.nodes = nodes;
this.virtualSize = virtualSize;
init();
}
/**
* 初始化,计算虚拟节点hashcode
*/
private void init(){
for(String node : nodes){
addNodeWithVirtual(node);
}
}
/**
* 获取分配节点
* @param key
* @return
*/
public String getNode(String key){
// 计算hashcode
int hashCode = HashUtils.getHashCode(key);
// 取hashcode对应节点
String node = virtualNodeMap.get(hashCode);
// 如果节点不存在,就找最近的下一个节点,TreeMap.ceilingEntry 方法用来返回与该键至少大于或等于给定键的实体
if(node == null){
Map.Entry<Integer, String> ceilingEntry = virtualNodeMap.ceilingEntry(hashCode);
if(ceilingEntry == null){// 如果没有符合条件的节点,就返回开始节点
node = nodes.get(0);
}else{
node = ceilingEntry.getValue();
}
}
return node;
}
/**
* 添加新节点
* @param node
*/
public void addNodeWithVirtual(String node){
for(int i=0; i<virtualSize; i++){
String virtualNode = node+"@"+i;
virtualNodeMap.put(HashUtils.getHashCode(virtualNode), node);
}
}
/**
* 添加新节点
* @param node
*/
public void addNode(String node){
if(this.nodes.contains(node)){
return;
}
this.nodes.add(node);
addNodeWithVirtual(node);
}
/**
* 删除节点
* @param node
*/
public void removeNode(String node){
if(!this.nodes.contains(node)){
return;
}
this.nodes.remove(node);
for(int i=0; i<virtualSize; i++){
String virtualNode = node+"@"+i;
virtualNodeMap.remove(HashUtils.getHashCode(virtualNode));
}
}
}

用到的工具类:

public class HashUtils {
/**
* hashcode
* @param node
* @return
*/
public static int getHashCode(String node) {
// return node.hashCode();
return Hashing.hmacMd5(node.getBytes()).hashInt(0).asInt();
}
}

MathUtils工具类主要是测试统计结果用

public class MathUtils {
/**
* 求和
* @param values
* @return
*/
public static int sum(int[] values){
int sum = 0;
for(int value : values){
sum += value;
}
return sum;
}
/**
* 平均数
* @param values
* @return
*/
public static double avg(int[] values){
return sum(values)/values.length;
}
/**
* 方差
* @param values
* @return
*/
public static double deviation(int[] values){
double avg = avg(values);
double total = 0d;
for(int value : values){
total += (value - avg)*(value - avg);
}
return total;
}
/**
* 标准差
* standard deviation
* @param values
* @return
*/
public static double std(int[] values){
return Math.sqrt(deviation(values)/values.length);
}
}

测试类:

public class ConsistentHashTest {
String[] nodes = new String[]{
"192.168.1.1",
"192.168.1.2",
"192.168.1.3",
"192.168.1.4",
"192.168.1.5",
"192.168.1.6",
"192.168.1.7",
"192.168.1.8",
"192.168.1.9",
"192.168.1.10"};
ConcurrentHashMap<String, ServerNode<String, String>> nodeMap = new ConcurrentHashMap<>(10);
@Before
public void init(){
for(String node : nodes){
nodeMap.put(node, new ServerNode<>());
}
}
@Test
public void testNodeHasVirtual() {
ConsistentHash chvn = new ConsistentHash(Arrays.asList(nodes));
// 模拟100万KV
for(int i=0; i<100_000_0; i++){
String key = String.valueOf(i);//UUID.randomUUID().toString();
String value = String.valueOf(i);
String node = chvn.getNode(key);
nodeMap.get(node).set(key, value);
}
// 统计标准差
statistics();
}
/**
* 结果统计
*/
public void statistics(){
int[] nodeSize = new int[nodes.length];
for(int i=0; i<nodes.length; i++){
String node = nodes[i];
int size = nodeMap.get(node).getSize();
nodeSize[i] = size;
System.out.println("节点["+node+"]缓存数据量:"+size);
}
System.out.println("标准差:"+MathUtils.std(nodeSize));
}
}

统计结果:

节点[192.168.1.1]缓存数据量:81012
节点[192.168.1.2]缓存数据量:70351
节点[192.168.1.3]缓存数据量:109951
节点[192.168.1.4]缓存数据量:95222
节点[192.168.1.5]缓存数据量:118972
节点[192.168.1.6]缓存数据量:99679
节点[192.168.1.7]缓存数据量:132763
节点[192.168.1.8]缓存数据量:87460
节点[192.168.1.9]缓存数据量:105101
节点[192.168.1.10]缓存数据量:99489
标准差:17258.1747180865



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

Z冰红茶

关注

还未添加个人签名 2018.09.17 加入

还未添加个人简介

评论

发布
暂无评论
一致性 hash 算法