一致性哈希算法-源码篇
程序员文章站
2024-03-19 21:40:34
...
背景
分布式缓存的前景下，如何实现缓存内容能够均衡的分布到缓存集群中？
假设三台redis集群，有6个数据源对象需要缓存，期望分别缓存到每个redis中，每个存2个。
思考
方式一： for ？
方式二：取模 ？
均可行。But
for的耦合性极高，后期维护成本大，性能也低，无法灵活的获取缓存，抛弃！
取模的方式是可行的，但是存在一个致命的问题：如果我临时添加了一台redis呢？直接就缓存雪崩了
参考原理地址
这篇写的很好：
https://blog.csdn.net/kefengwang/article/details/81628977
我写的代码参考地址：
https://blog.csdn.net/WANGYAN9110/article/details/70185652
注意：上面这个地址上的代码存在问题，慎用。
请务必了解过原理之后再看下面的代码！
原理概要：
虚拟出一个数值(非负整数)范围，将集群属性（也可以理解为唯一标识）hashCode后，标记到虚拟范围数值上的某个点上，并通过有序二叉树Map维护其关系，将缓存的Key进行hashCode后，通过map的二分查找法找到对应的缓存节点。
源码
简单属性模式 - 仅供参考
import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
/**
*
* @Package: PACKAGE_NAME
* @ClassName: HashConsistenceAlgorithm
* @Author: MC
* @Description: ${description}
* @Date: 2020/12/23 0023 9:06
* @Version: 1.0
*/
public class HashConsistenceAlgorithm {
//集群集合
private List<String> serverList = new ArrayList<>();
//虚拟槽点
private int node = 100;
//集群与槽点关系
SortedMap<Long,String> hash2Server = new TreeMap<>();
//暴露构造
public HashConsistenceAlgorithm(List<String> serverList,int node){
this.serverList = serverList;
this.node = node;
}
//获取serverName
public String getServer(String key){
long hashCode = HashCodeUtil.FNVHash(key);
SortedMap<Long, String> integerStringSortedMap = hash2Server.tailMap(hashCode);
if(integerStringSortedMap.isEmpty()){
return hash2Server.get(hash2Server.firstKey());
}
return integerStringSortedMap.get(hashCode);
}
//设置槽点
public void setNode(int node){
this.node = node;
}
//添加地址
public void addServer(String serverName){
this.serverList.add(serverName);
for (int i = 0; i < node; i++) {
String h = "MC-"+serverName+i;
long hashCode = HashCodeUtil.FNVHash(h);
this.hash2Server.put(hashCode,serverName);
}
}
}
由简入繁
基础准备
为了扩大数值范围，通过32位的 Fowler-Noll-Vo 哈希算法扩充散列，直接复制使用即可。
之所以这么做是为了加大命中率。 感兴趣的可以尝试下使用不同字符进行hashCode方法调用后的数值分布区间。
/**
*
* @Package: PACKAGE_NAME
* @ClassName: HashCodeUtil
* @Author: MC
* @Description: ${description}
* @Date: 2020/12/23 0023 11:09
* @Version: 1.0
*/
public class HashCodeUtil {
// 32位的 Fowler-Noll-Vo 哈希算法
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
public static Long FNVHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for (int idx = 0, num = key.length(); idx < num; ++idx) {
hash = (hash ^ key.charAt(idx)) * 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;
}
}
定义缓存节点实体 Node
import lombok.Data;
import java.util.HashMap;
import java.util.Map;
/**
*
* @Package: PACKAGE_NAME
* @ClassName: Node
* @Author: MC
* @Description: 集群节点
* @Date: 2020/12/23 0023 9:34
* @Version: 1.0
*/
@Data
public class Node {
private String domain;//域名
private String ip;//IP
private Map<String,Object> data;//节点存储的数据
public Node(String domain,String ip){
this.domain = domain;
this.ip = ip;
this.data = new HashMap<>();
}
public <T> void put(String key,T value){
this.data.put(key,value);
}
public void remove(String key){
this.data.remove(key);
}
public <T> T get(String key){
return (T) this.data.get(key);
}
}
定义集群抽象父类
import java.util.ArrayList;
import java.util.List;
/**
*
* @Package: PACKAGE_NAME
* @ClassName: Cluster
* @Author: MC
* @Description: ${description}
* @Date: 2020/12/23 0023 9:39
* @Version: 1.0
*/
public abstract class Cluster {
protected List<Node> nodes;
public Cluster(){
this.nodes = new ArrayList<>();
}
public Cluster(List<Node> nodes){
this.nodes = nodes;
}
public abstract void addNode(Node node);
public abstract void removeNode(Node node);
public abstract Node get(String key);//根据Key获取当前缓存数据所在的节点
}
取模方式
import java.util.List;
/**
*
* @Package: PACKAGE_NAME
* @ClassName: NormalHashCluster
* @Author: MC
* @Description: 取模方式
* @Date: 2020/12/23 0023 9:44
* @Version: 1.0
*/
public class NormalHashCluster extends Cluster {
public NormalHashCluster(){
super();
}
public NormalHashCluster(List<Node> nodes){
super(nodes);
}
@Override
public void addNode(Node node) {
this.nodes.add(node);
}
@Override
public void removeNode(Node node) {
this.nodes.removeIf(o -> o.getIp().equals(node.getIp()) && o.getDomain().equals(node.getDomain()));
}
@Override
public Node get(String key) {
Long hashCode = HashCodeUtil.FNVHash(key);
int nodesIndex = hashCode.intValue() % this.nodes.size();
return this.nodes.get(nodesIndex);
}
}
核心方法为get
测试
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
/**
* @Package: PACKAGE_NAME
* @ClassName: Test
* @Author: MC
* @Description: ${description}
* @Date: 2020/12/23 0023 9:51
* @Version: 1.0
*/
public class Test {
//取模算法实现均衡存储
public static void main(String[] args) {
String testKey = "mc";
int clusterSize = 5;
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < 5; i++) {
Node node = new Node("MC-Hash","192.168.0."+(i+1));
nodes.add(node);
}
Cluster cluster = new NormalHashCluster(nodes);
IntStream.range(0,clusterSize).forEach(index -> {
Node node = cluster.get(testKey + index);
node.put(testKey+index,"test-data");
});
System.out.println("--------------------数据分布情况：");
cluster.nodes.forEach(node ->{
System.out.println("IP:"+node.getIp()+";数据量："+node.getData().size());
});
//缓存命中率
long count = IntStream.range(0, clusterSize).filter(index -> cluster.get(testKey + index).get(testKey + index) != null)
.count();
System.out.println("缓存命中率："+ count*1f/clusterSize);
//增加一个节点
// cluster.addNode(new Node("MC-Hash", "192.168.0.6"));
//删除一个节点
// cluster.removeNode(new Node("MC-Hash", "192.168.0.2"));
//缓存命中率
// long count1 = IntStream.range(0, clusterSize).filter(index -> cluster.get(testKey + index).get(testKey + index) != null)
// .count();
// System.out.println("缓存命中率："+ count1*1f/clusterSize);
}
}
一致性算法方式
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.stream.IntStream;
/**
* @ProjectName: ruoyi
* @Package: PACKAGE_NAME
* @ClassName: ConsistencyHashCluster
* @Author: MC
* @Description: 一致性 hash散列环形算法
* @Date: 2020/12/23 0023 10:15
* @Version: 1.0
*/
public class ConsistencyHashCluster extends Cluster{
private static final String splitFlg = "&MC";//扩大hash散列环形范围,同时进行切割标记
private static int fictitiousDrawback = 100;//虚拟槽点数量 默认100
//基于二叉树存储节点hash值与节点关系，不使用普通map与List原因是为了能够快速方便的二分查找
private SortedMap<Long,Node> hash2Node = new TreeMap<>();
public ConsistencyHashCluster(){
super();
}
public ConsistencyHashCluster(List<Node> nodes){
super(nodes);
}
public ConsistencyHashCluster(List<Node> nodes,int fictitiousDrawback){
super(nodes);
this.fictitiousDrawback = fictitiousDrawback;
}
@Override
public void addNode(Node node) {
this.nodes.add(node);
//进行hash散列处理并保存对应关系
IntStream.range(0,fictitiousDrawback)
.forEach(index ->{
String s = node.getDomain() + splitFlg + node.getIp() + index;
long hashCode = HashCodeUtil.FNVHash(s);
this.hash2Node.put(hashCode,node);
});
}
@Override
public void removeNode(Node node) {
this.nodes.removeIf(o -> o.getDomain().equals(node.getDomain()) && o.getIp().equals(node.getIp()));
//从关系列表中剔除
IntStream.range(0,fictitiousDrawback)
.forEach(index ->{
String s = node.getDomain() + splitFlg + node.getIp() + index;
long hashCode = HashCodeUtil.FNVHash(s);
this.hash2Node.remove(hashCode);
});
}
@Override
public Node get(String key) {
long hashCode = HashCodeUtil.FNVHash(key);
//获取该hashCode最近的下一个map，tailMap方法是基于Key做的
SortedMap<Long, Node> integerNodeSortedMap = this.hash2Node.tailMap(hashCode);
if(integerNodeSortedMap.isEmpty()){
//直接取第一个
return this.hash2Node.get(this.hash2Node.firstKey());
}
return integerNodeSortedMap.get(hashCode);
}
}
下一篇： 【Python】bisect二分查找