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

用户头像
吴建中
关注
发布于: 2020 年 07 月 06 日
第五周作业-一致性hash算法实现





一致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多,再往后添加虚拟节点,标准差变化不大,趋于定。



用户头像

吴建中

关注

还未添加个人签名 2018.04.18 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业-一致性hash算法实现