写点什么

第五周 技术选型(1)作业

用户头像
钟杰
关注
发布于: 2020 年 10 月 24 日

一致性哈希算法

package com.company.gitdemo;
import java.util.*;
public class ConsistenceHash {
public ConsistenceHash() {
}
public ConsistenceHash(int viretalNums) {
this.viretalNums = viretalNums;
}
// 物理节点集合
private List<String> realNodes = new ArrayList<>();
// 虚拟节点数,用户指定
private int viretalNums = 100;
// 物理节点存储数据数量
private Map<String,Integer> nodeKvCount = new HashMap<>();
// 排序存储结构红黑树,key是虚拟节点的hash值,value是物理节点
private SortedMap<Long,String> sortedMap = new TreeMap<>();
//添加服务器节点
public void addNode(String node) {
String vnode = null;
int i = 0;
for (int count = 0; count < viretalNums; ) {
i++;
vnode = node + "_" + i;
long hasValue = hash(vnode);
if(!this.sortedMap.containsKey(hasValue)){
count++;
sortedMap.put(hasValue, node);
}
}
nodeKvCount.put(node,0);
this.realNodes.add(node);
}
//获取服务器节点
public String getNode(String key) {
long hash = hash(key);
SortedMap<Long, String> map = this.sortedMap.tailMap(hash);
String node;
if (map.isEmpty()) {
node= this.sortedMap.get(sortedMap.firstKey());
} else {
node= map.get(map.firstKey());
}
nodeKvCount.put(node,nodeKvCount.get(node)+1);
return node;
}
//获取服务器节点数据分布标准差
public double getStandardDeviation(int sumCount) {
//平均值
double avg=sumCount/realNodes.size();
//方差
int total = 0;
for (Map.Entry<String, Integer> entry : nodeKvCount.entrySet()) {
total += (entry.getValue() - avg) * (entry.getValue() - avg);
}
//标准差
double standardDeviation = Math.sqrt(total / realNodes.size());
return standardDeviation;
}
/**
* 使用FNV1_32_HASH
*/
private long hash(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) {
hash = (hash ^ key.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;
}
}

100 万 KV 数据存储分布测试(标准差)

package com.company.gitdemo;
public class Main {
public static void main(String[] args) {
ConsistenceHash consistenceHash = new ConsistenceHash(150);
consistenceHash.addNode("193.168.1.9");
consistenceHash.addNode("193.168.1.11");
consistenceHash.addNode("193.168.1.53");
consistenceHash.addNode("193.168.1.13");
consistenceHash.addNode("193.168.1.14");
consistenceHash.addNode("193.168.1.77");
consistenceHash.addNode("193.168.1.26");
consistenceHash.addNode("193.168.1.36");
consistenceHash.addNode("193.168.1.45");
consistenceHash.addNode("193.168.1.14");
//存储
int sumCount=1000000;
for (int i = 0; i < sumCount; i++) {
consistenceHash.getNode("a" + i);
}
double standardDeviation=consistenceHash.getStandardDeviation(sumCount);
System.out.println("标准差:" + standardDeviation);
}
}



什么是一致性哈希算法

在分布式系统中,扩容缩容操作极为常见,如果频繁进行重Hash操作显然是不可取的,一是消耗太大,而是可能引发服务的中断。此时,就要采用一致性Hash算法。



一致性Hash算法(Consistent Hashing)是一种hash算法,它能够在Hash输出空间发生变化时,引起最小的变动。以我们的例子来讲,增加或者移除一台服务器时,对原有的服务器和用户之间的映射关系产生的影响最小。



好的一致性Hash算法应该能够满足以下要求:



平衡性:这是Hash算法的基本要求,是指哈希的结果均匀地分配在整个输出空间中。



单调性:当发生数据节点变动时,对于相同的数据始终映射到相同的缓冲节点中或者新增加的缓冲节点中,避免无法找到原来的数据。



稳定性:当出现节点坏掉或热点访问而需要动态扩容时,尽量减少数据的移动。显然一般的Hash方法不满足这一点



用户头像

钟杰

关注

还未添加个人签名 2019.02.12 加入

还未添加个人简介

评论

发布
暂无评论
第五周 技术选型(1)作业