第五周作业 - 一致性 hash 算法实现

 关注
发布于: 2020 年 07 月 06 日
﻿
﻿
一致hash算法数据结构
﻿
关键点：
1.物理节点与虚拟节点对应关系是固定的，一旦初始化后，就不能修改，不然会缓存失效。
2.虚拟节点不能绝对的均匀的分配在环上。
3.用专门的数据结构维护虚拟节点与物理节点关系，以及每个虚拟节点对应的hash(key)的上限，如右上角的数据结构，该数据结构内部有序，便于查找。
4. 每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。每一个缓存节点也遵循同样的Hash算法，比如利用IP或者主机名做Hash，映射到环形空间当中。特别注意业务key 和虚拟节点Name必须使用相同的Hash算法。
5.查找时看落在哪两个虚拟节点区间,更靠近的虚拟节点，选定虚拟节点后，根据虚拟节点与物理节点的映射关系，找到物理节点，进行读写。这个映射表应该缓存在各客户端的本地内存中，通过某种机制定期更新。
﻿
类说明：
NodeMappingBean.java 对应着虚拟节点，包含物理节点名称、虚拟节点名称、虚拟节点在环上的位置，虚拟节点的存储空间（用map模拟redis存储空间），NodeMappingBean实现了Comparable接口，对各虚拟节点的下标排序，目的是为了key的hash值在环上定位时，按顺序查找即可，简化定位算法和性能。
﻿
NodeMappingProxy.java 是一致性hash算法的实现类，负责初始化物理节点和虚拟节点的对应关系，负责setKey ,负责getKey。
﻿
HashUtil.java ，FNV132HASH工具类，虚拟节点和业务key，都使用该hash工具类，计算hash值映射到环上。
﻿
Client.java ，客户端方法，负责实例化NodeMappingProxy.java，插入100W key ,负责统计各物理节点存储的key数量。
﻿
NodeMappingBean.java
package fiveday;
import java.util.HashMap;
import java.util.Map;
﻿
/**
 * 虚拟节点数据结构
 */
public class NodeMappingBean implements Comparable {
    private String nodeName;
    private String virNodeName;
    private int index;
    private Map redisMap = new HashMap(); // 使用hashmap 模拟物理 redis
﻿
    public String getNodeName() {
        return nodeName;
    }
﻿
    public void setNodeName(String nodeName) {
        this.nodeName = nodeName;
    }
﻿
    public String getVirNodeName() {
        return virNodeName;
    }
﻿
    public void setVirNodeName(String virNodeName) {
        this.virNodeName = virNodeName;
    }
﻿
    public int getIndex() {
﻿
        return this.index;
    }
﻿
    public void setIndex(int index) {
        this.index = index;
    }
﻿
﻿
    public Map getRedisMap() {
        return redisMap;
    }
﻿
    public void setRedisMap(Map redisMap) {
        this.redisMap = redisMap;
    }
﻿
    public int compareTo(Object o) {
        // TODO Auto-generated method stub
﻿
        NodeMappingBean oo = (NodeMappingBean)o;
           return new Integer(this.index).compareTo( oo.index);
    }
}
﻿
﻿
NodeMappingProxy.java
package fiveday;
﻿
import java.util.ArrayList;
import java.util.List;
﻿
public class NodeMappingProxy {
﻿
    private List nodeMappinps = new ArrayList();
    public List getNodeMappinps() {
        return nodeMappinps;
    }
﻿
    public void setNodeMappinps(List nodeMappinps) {
        this.nodeMappinps = nodeMappinps;
    }
﻿
    /**
     * 指定物理节点和指定虚拟节点数，获取虚拟节点在环上位置，及物理节点、虚拟节点、位置的映射关系，
     * @param nodeName ，物理节点名称
     * @param virNodeCount ，虚拟节点个数
     */
    public static List initNodeHash(String nodeName,int virNodeCount ){
﻿
        List <NodeMappingBean> list = new ArrayList();
        for(int i=0;i<virNodeCount;i++){
            String virNodeName = nodeName+"#"+i;
            int nodeHashValue = HashUtil.getHash(virNodeName);
            NodeMappingBean bean = new NodeMappingBean();
            bean.setNodeName(nodeName);
            bean.setVirNodeName(virNodeName);
            bean.setIndex(nodeHashValue);
            list.add(bean);
        }
﻿
        return list;
    }
﻿
﻿
    /**
     * 插入key value
     *
     * @param key
     * @param value
     */
    public void setKey(String key, Object value) {
﻿
        NodeMappingBean bean = null; // 记录被命中虚拟节点
﻿
        // 使用与虚拟节点相同的hash算法,获取key在环上的位置
        int keyIndex = HashUtil.getHash(key);
﻿
        // 按照顺时针进行搜索，找到第一个比较自己大的位置，就停下搜索，锁定虚拟节点。
        int begin = 0; //
        int end = 0;
        for (int i = 0; i < nodeMappinps.size(); i++) {
﻿
            NodeMappingBean currentBean = (NodeMappingBean) nodeMappinps.get(i);
            bean = currentBean;
            if (i == 0) { // 表示环上第一个虚拟节点
﻿
                end = currentBean.getIndex();
                if (keyIndex <= end) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    currentBean.getRedisMap().put(key, value);
                    break;
                }
            } else if (i == nodeMappinps.size() - 1) { // 如果循环到最后一个
﻿
                begin = currentBean.getIndex();
﻿
                if (begin <= keyIndex) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    currentBean.getRedisMap().put(key, value);
                    break;
                }
﻿
            } else { // 中间节点
﻿
                NodeMappingBean preBean = (NodeMappingBean) nodeMappinps.get(i - 1);
                begin = preBean.getIndex();
                end = currentBean.getIndex();
                if (begin <= keyIndex && keyIndex <= end) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    currentBean.getRedisMap().put(key, value);
                    break;
                }
﻿
            }
﻿
        }
﻿
/*        if(bean!=null){
            System.out.println(bean.getNodeName()+" "+bean.getVirNodeName()+ " " +bean.getIndex());
        }*/
﻿
﻿
    }
﻿
    /**
     * 通过key 获取value
     *
     * @param key
     * @return
     */
    public Object getValue(String key) {
﻿
        NodeMappingBean bean = null; // 记录被命中虚拟节点
﻿
        Object returnValue=null;
        // 使用与虚拟节点相同的hash算法,获取key在环上的位置
        int keyIndex = HashUtil.getHash(key);
﻿
        // 按照顺时针进行搜索，找到第一个比较自己大的位置，就停下搜索，锁定虚拟节点。
        int begin = 0; //
        int end = 0;
        for (int i = 0; i < nodeMappinps.size(); i++) {
﻿
            NodeMappingBean currentBean = (NodeMappingBean) nodeMappinps.get(i);
            bean = currentBean;
            if (i == 0) { // 表示环上第一个虚拟节点
﻿
                end = currentBean.getIndex();
                if (keyIndex <= end) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    returnValue =  currentBean.getRedisMap().get(key);
                    break;
                }
            } else if (i == nodeMappinps.size() - 1) { // 如果循环到最后一个
﻿
﻿
                begin = currentBean.getIndex();
﻿
                if (begin <= keyIndex) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    returnValue =  currentBean.getRedisMap().get(key);
                    break;
                }
﻿
            } else { // 中间节点
﻿
                NodeMappingBean preBean = (NodeMappingBean) nodeMappinps.get(i - 1);
﻿
                begin = preBean.getIndex();
                end = currentBean.getIndex();
                if (begin <= keyIndex && keyIndex <= end) {
                    // 根据虚拟节点和物理阶段的映射关系，找到物理节点，用map模拟物理节点的key-value存储模型
                    returnValue =  currentBean.getRedisMap().get(key);
                    break;
                }
﻿
            }
﻿
        }
/*        if(bean!=null){
            System.out.println(bean.getNodeName()+" "+bean.getVirNodeName()+ " " +bean.getIndex());
        }*/
        return returnValue;
    }
}
﻿
﻿
HashUtil.java ，FNV1_32_HASH工具类
package fiveday;
﻿
import java.security.MessageDigest;
﻿
public class HashUtil {
    /**
     * 使用FNV1_32_HASH获取key的散列值
     *
     * @param str key 值
     * @return int值
     */
﻿
    public static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.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;
    }
}
﻿
﻿
﻿
Client.java ，客户端方法
package fiveday;
﻿
import java.util.*;
﻿
public class Client {
    public static void main(String args[]) {
        int NODECOUNT = 10; //物理节点数量
        int VIRNODECOUNT = 300; // 每个物理节点对应的虚拟节点个数
﻿
        //实例化一致性hash的代理
        NodeMappingProxy nmf = new NodeMappingProxy();
        
        // 10个物理节点，每个物理节点对应300个虚拟节点
        for(int i=0;i<NODECOUNT;i++) {
            List nodeHashMapping = nmf.initNodeHash("node"+i, VIRNODECOUNT);
            nmf.getNodeMappinps().addAll(nodeHashMapping);
﻿
        }
        // 按照环上位置排序，可优化key查找性能
        Collections.sort(nmf.getNodeMappinps());
        
        // 插入100W个key
        for(int i=0;i<1000000;i++){
            nmf.setKey(""+i,i);
            //nmf.getValue(""+i);
        }
        
        // 统计每个物理节点上存储的key
        for(int i=0;i<NODECOUNT;i++) {
            int size = 0;
            for(int j=0;j<NODECOUNT*VIRNODECOUNT;j++)
            {
                NodeMappingBean bean = (NodeMappingBean)nmf.getNodeMappinps().get(j);
                if(bean.getNodeName().equals("node"+i)){
                    size = size +bean.getRedisMap().size();
                }
            }
            System.out.println(size);
        }
    }
﻿
}
﻿
﻿
运行效果：
每个物理节点对应300-400个虚拟节点时，标准差较低：2000多，再往后添加虚拟节点，标准差变化不大，趋于定。
﻿
发布于: 2020 年 07 月 06 日阅读数: 63
吴建中

 关注
还未添加个人签名 2018.04.18 加入
还未添加个人简介
发布
暂无评论