一致性哈希算法-源码篇

￡神魔★判官ぃ 2022-12-29 14:19 115阅读 0赞

# 背景 #

分布式缓存的前景下，如何实现缓存内容能够**均衡的分布**到缓存集群中？  
假设三台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);
        }
    }