一致性哈希算法

目的为了解决分布式系统中缓存key的雪崩问题。一致性哈希算法在 1997 年由麻省理工学院提出是一种特殊的哈希算法在移除或者添加一个服务器时能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系一致性哈希解决了简单哈希算法在分布式哈希表Distributed Hash TableDHT中存在的动态伸缩等问题一致性hash是对固定值2^32取模一致性Hash的工作原理或算法① hash环② 服务器映射到hash环使用hash服务器ip% 2^32③ 对象key映射到服务器Key的Hash值hashkey% 2^32此处的Hash函数可以和之前计算服务器映射至Hash环的函数不同从缓存对象key的位置开始沿顺时针方向遇到的第一个服务器便是当前对象将要缓存到的服务器**①②③便是一致性Hash的工作原理**将原本单个点的Hash映射转变为了在一个环上的某个片段上的映射服务器扩缩容场景① 服务器减少把缩减服务器上的所有key顺时针移到下一个服务器即可② 服务器增加对相邻的两个服务器上的key进行重分配数据偏斜服务器性能平衡问题原因在Hash环上分配的点太少。导致把环分配的不均衡。点多则相应会把环分配的比较均衡。则引入虚拟节点的计算虚拟节点的计算hash10.24.23.227#1% 2^32hash10.24.23.227#2% 2^32hash10.24.23.227#3% 2^32三、一致性Hash算法java实现一致性Hash算法实现下面我们根据上面的讲述实现一个一致性Hash算法这个算法具有一些下面的功能特性一致性Hash核心算法支持自定义Hash算法支持自定义虚拟节点个数packagecom.job.hash;importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjava.util.TreeMap;/** * 一致性hash算法 */publicclassHashUtil{privatestaticMapInteger,StringnodeMapnewHashMapInteger,String();//1024个虚拟节点privatestaticintV_NODES1024;privatestaticTreeMapInteger,StringvNodeMapnewTreeMapInteger,String();privatestaticfinalintREAL_NODE_COUNT8;static{nodeMap.put(0,node_0);nodeMap.put(1,node_1);nodeMap.put(2,node_2);nodeMap.put(3,node_3);nodeMap.put(4,node_4);nodeMap.put(5,node_5);nodeMap.put(6,node_6);nodeMap.put(7,node_7);/** * 虚拟节点和真实节点的映射 */for(inti0;iV_NODES;i){vNodeMap.put(i,nodeMap.get(i%REAL_NODE_COUNT));}}/** * 获取真实节点 * param value * return */publicstaticStringgetRealServerNode(Stringvalue){Integercode(value.hashCode()0x7FFFFFFF)%1024;returnvNodeMap.ceilingEntry(code).getValue();}/** * 删除一个节点 * param nodeName */publicstaticvoiddropNode(StringnodeName){intnode-1;for(Map.EntryInteger,Stringentry:nodeMap.entrySet()){if(entry.getValue().equalsIgnoreCase(nodeName)){nodeentry.getKey();break;}}if(node-1){System.out.println(未找到节点:nodeName);return;}IteratorMap.EntryInteger,StringitervNodeMap.entrySet().iterator();while(iter.hasNext()){Map.EntryInteger,Stringentryiter.next();Integerkeyentry.getKey();if(key%REAL_NODE_COUNTnode){System.out.println(删除节点:key,value:entry.getValue());iter.remove();;}}}publicstaticvoidmain(String[]args){StringrequestValuehello jason;System.out.println(映射关系vNodeMap);System.out.println(getRealServerNode(requestValue));System.out.println(删除节点);dropNode(node_3);System.out.println(映射关系vNodeMap);System.out.println(getRealServerNode(requestValue));}}